第一篇：数据结构实验报告--八皇后（写写帮整理）
数据结构实验报告
1．实验要求
实验目的：利用栈结构实现八皇后问题
八皇后问题如下：八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是，在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列，同一斜线上。
实验内容：利用所学的栈结构用递归或非递归解决八皇后问题。
2.程序分析
程序使用程序最主要只是在主函数用了一个递归函数Queen。
Queen函数使用了三个参数m,flag[][],chess[][]。其中m是行数，flag[][]是判断二维数组何处可以放置皇后，chess[][]是存储字符串的二维数组。
主函数中对Queen函数中的形参数组flag[][],chess[][]进行初始化，在Queen函数中再进行各种操作。
Queen函数执行代码，首先行数m为0，当m小于7时，通过if…else…语句，利用Queen(m+1,f,c)重新执行递归函数到下一行。
2.1 存储结构
存储结构：数组存储。
flag[][]数组存储数字判断输出和储能放置皇后,chess[][]数组存储字符串即皇后和非皇后的形状。
2.2 关键算法分析
1、关键算法： a．
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
f[i][j]=0;
c[i][j]='*';
说明：对棋盘进行初始化 未放置皇后的为“*” b．
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
c[i][j]=chess[i][j];
f[i][j]=flag[i][j];
} 说明：对c[][]，f[][]进行初始化。c．
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if(f[i][j]==0 &&(i+j==m+k || m==i || k==j || m-k==i-j))
f[i][j]=-1;
}
c[m][k]='#';
说明：已放置皇后的行、列以及对角线都不能再放置皇后。
已放置皇后的显示为“#”。d.if(m==7)
{
cout<<“算法的第”<<++count<<“个解为：”< for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cout< } cout< } cout< cout< return; } else Queen(m+1,f,c); 说明：首先判断是否已执行到最后一行 每输出一个算法，count计数器加1 若没有执行到最后一行，m+1继续执行Queen函数 2.3 其他 要求程序在一开始创建一个统计算法解个数的加法器。 3.程序运行结果 1、测试主函数流程：流程图如图所示 2、测试结论：输出解决算法的个数及八皇后问题的图解。 4.总结 一．问题及解决办法 1.一开始编的时候对同一行，同一列以及同一斜行不能排皇后的算法不能准确编写，后来通过画图发现了这三个情况数组行标和列标的特点，从而解决了这个问题。 2.程序只能输出从65至99的解，其他解不显示，后来发现是因为界面太小的原因。二．心得体会 对于刚学的栈表以及递归函数一定要多用才能熟悉，才能知道实现的具体细节问题。对一些出现的错误一点要仔细分析，明白以后就会掌握的很牢固。对于递归函数一定要充分理解它的意义才能用好它。 在编写代码中如果对于一些抽象的算法构思感到困难，可以通过画图，在纸上先进行演算推导出各变量之间的关系，再进行编写可能会使问题变得简单明了一些。三．改进 递归算法解决八皇后问题比较简单明了，下次可以尝试不使用递归而用非递归编写算法，这样可能会更牢固更好的掌握栈的思想，巩固已学的知识。 数据结构 实习报告 专业：数字媒体技术 姓名：李义 年级：2013级 学号：201301052015 完成日期：2015.12.31 题目：八皇后问题 一、项目简介 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在88格的国际象棋棋盘上，安放八个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即任意两个皇后都不能处于同一行、同一列或同一条对角线上，求解有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法得出结论，有92种摆法。 二、概要设计 2.1 主要模块： 这个程序主要由4个模块组成，分别是画棋盘模块，画皇后模块，输出皇后摆法模块，和解决如何摆置皇后模块。这4个模块隶属于主函数模块。既主函数通过对这4个模块的合理调用解决“8皇后问题”，同时这4个模块之间也互有调用。 2.2 程序设计的数据结构及其关系： 数据结构的实现：数组a[i]：a [i]表示第i个皇后放置的列；i的范围：1-8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后；然后进行数据的初始化。从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于０（未被占领）:如果是，摆放第n个皇后，并宣布占领(切记要横列竖列斜列一起来)，接着进行递归；如果不是，测试下一个位置(n,m+1)，但是如果当时，却发现此时已经无法摆放时，便要进行回溯。 三、详细设计 3.1 定义相关的数据类型： 3.1.1 定义的相关数据类型： int A[21],B[21],C[21],Y[8];void *buff1,*buff2 3.1.2 设计思想： 本程序通过对子函数void qu(int i)的调用，将八皇后的问题关键通过数据结构的思想予以了实现。虽然题目以及演算看起来都比较复杂，繁琐，但在实际中，只要当一只皇后放入棋盘后，在横与列、斜线上没有另外一只皇后与其冲突，再对皇后的定位进行相关的判断。即可完成。如果在这个程序中，我们运用的是非递归的思想，那么将大量使用if等语句，并通过不断的判断，去推出答案，而且这种非递归的思想，大大的增加了程序的时间复杂度。如果我们使用了数据结构中的算法后，那么程序的时间复杂度，以及相关的代码简化都能取得不错的改进。这个程序，我运用到了数据结构中的栈、数组，以及树和回溯的方法。特别是在对于树以及二叉树的学习，更是为八皇后的问题提供了科学的解决方案，通过对树的分析，把八皇后的问题看成了树，而在衍生第一个变化后，上面的第一层八个变化就变成了八个结点，而这八个结点再继续的衍生„„，这样比较形象的将八皇后的问题简单化了。然后再通过回溯法进行设计，回溯法是设计递归过程的一个重要的方法。它的求解过程实质上是一个先序遍历一棵“状态树“的过程。在这个程序设计中，它先进行判断，棋盘上是否已经得到一个完整的布局（即棋盘是否已经摆上8个棋子），如果是，则输出布局；如果不是则依次先根遍历满足约束条件的各棵子树，流程即是： 判断该子树根的布局是否合法：如果合法的话，则先根遍历该子树；如果不合法的话，则剪去该子树的分支。 3.2 相关代码及算法 3.2.1 主模块C码算法： void main(void){ Queen Q; int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,“D://Win-TC”); SetQueen(&Q); setcolor(YELLOW); QueenPic(); cleardevice(); setcolor(LIGHTGREEN); settextstyle(0,0,3); outtextxy(180,10,“Eight Queens”); setcolor(WHITE); settextstyle(0,0,1); outtextxy(250,400,“2009.11.8 3:30pm”); QueenRe(&Q,0); getch(); closegraph();} 3.2.2 棋盘模块C码算法 void Checker(void) /* 画棋盘函数 */ { int i,k; for(k=0;k<8;k++) for(i=0;i<8;i++) if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE); setcolor(LIGHTBLUE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE); setcolor(WHITE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,WHITE);} } 3.2.3 皇后模块C码算法： void QueenPic(void) /* 画皇后图象，然后存储到缓冲区 */ { int size，polypoints1[10]={9,1,11,1,20,20,1,20,9,1}，polypoints2[10]={29,1,31,1,40,20,21,20,29,1}; setfillstyle(SOLID_FILL,LIGHTBLUE); /* 画淡蓝色棋格 */ setcolor(LIGHTBLUE); rectangle(1,1,20,20); floodfill(10,10,LIGHTBLUE); setfillstyle(SOLID_FILL,WHITE); /* 画白色棋格 */ setcolor(WHITE); rectangle(21,1,40,20); floodfill(30,10,WHITE); setfillstyle(SOLID_FILL,DARKGRAY); setcolor(YELLOW); drawpoly(5,polypoints1); drawpoly(5,polypoints2); floodfill(10,10,YELLOW); floodfill(30,10,YELLOW); size=imagesize(1,1,20,20); /* 计算缓冲区大小，然后存储 */ buff1=(void *)malloc(size); buff2=(void *)malloc(size); getimage(1,1,20,20,buff1); getimage(21,1,40,20,buff2); cleardevice();} 3.2.4 八皇后摆放方法模块C码: void QueenRe(Queen *Q, int y) 八皇后的递归算法 {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])下一棵要遍历的子树由状态数确定 { Q->Y[y]=x;放置皇后 Q->A[x+7]=1;标记下次这里不能放置皇后 Q->B[x+y+7]=1;标记下次这里不能放置皇后 Q->C[x-y+7]=1;标记下次这里不能放置皇后 if(y==7) PrintQueen(Q);调用输出图形函数 QueenRe(Q,y+1);进入下一层递归 Q->A[x+7]=0;如果上次摆法导致后面不能继续摆放则重置标记为0 Q->B[x+y+7]=0; Q->C[x-y+7]=0; } } 3.2.5 初始化模块C码: void SetQueen(Queen *Q) /* 初始化 */ {int i; for(i=0;i<21;i++) {Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;初始化为0，表示可以放置皇后。} for(i=0;i<8;i++) Q->Y[i]=-1;} 3.2.6 图形输出： void PrintQueen(Queen *t) /* 图形输出函数 */ {int k; char str[20]; static total=0; total++; setviewport(240,80,400,260,1); /* 设置窗口 */ sprintf(str,“NO.%d”,total); setcolor(GREEN); settextstyle(0,0,1); outtextxy(0,0,str); Checker(); for(k=0;k<8;k++) if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0) putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);else putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT); getch(); if(getch()==27)exit(0); clearviewport();} void QueenRe(Queen *Q, int y) /* 八皇后的递归算法 */ {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍历的子树由状态数确定 */ {Q->Y[y]=x; Q->A[x+7]=1; Q->B[x+y+7]=1; Q->C[x-y+7]=1; if(y==7) PrintQueen(Q); QueenRe(Q,y+1); /* 进入下一层递归 */ Q->A[x+7]=0; Q->B[x+y+7]=0; Q->C[x-y+7]=0;} } } 3.3函数调用图 3.4项目流程图 通过编译连接后，程序基本上把八皇后的92种摆法的都进行了演示； 但程 四、调试分析 序运行中也出现了以下缺点： 因为八皇后的表现方法甚多，输出后虽能全部显示，但未能使屏幕停留，把一个一个的将其显示出来,但是这样便使得操作步骤太多,也会造成不必要的麻烦!所以只画出了第一种和最后一种的输出结果，演示如图所示： 五、设计体会 该程序在调试的过程中出现了不少的问题！如数据溢出等（是自己过于粗心而造成的）。在调试的过程中出现的一个最大的问题就是：在运行的时候出现解的个数大于自己所预计的。经过不断的查看内存变量，操作次数但还是没有找出问题的所在。终于在晚上十二点的时候，决定睡觉！但一关上电脑，躺在床上的时候，突然想到了一个问题：经过读了一些资料，知道八皇后问题有12组实质解，92组全解——这说明在这12组实质解中有其中的一组解是比其它的解要特殊一点的：其它的解经过等价的变换之后都会产生8组等价的解，只有这个特殊的解只有4组等价的解。说不定我的问题就出在这里！我之前也写了一些有关的代码处理这个问题，但我之前以为这个特殊的解是一个完全中心对称的图形（每转90度得到的图形就是它自己本身），所以我的在这里的判断就出现错误了！后来经过相关代码的修改，问题终于解决了，程序正确运行。 本课程设计本人的目的也是通过用WIN-TC程序设计平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．最终将其问题变得一目了然，更加易懂。 六、用户使用说明 6.1 程序的使用平台： 系统要求：windows2000以上操作系统； 语言开发平台：WIN-TC； 6.2 源代码分析： 首先对程序中的函数头文件进行引入，定位；在这个程序中，与其他C++的程序一样，都是引入：#include 七、附录 #include void *buff1,*buff2;typedef struct { int A[21],B[21],C[21],Y[8];} Queen;void SetQueen(Queen *Q) /* 初始化 */ { int i;for(i=0;i<21;i++){ Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;} for(i=0;i<8;i++)Q->Y[i]=-1;} void QueenPic(void) /* 画皇后图象，然后存储到缓冲区 */ { int size, polypoints1[10]={9,1,11,1,20,20,1,20,9,1}, polypoints2[10]={29,1,31,1,40,20,21,20,29,1};setfillstyle(SOLID_FILL,LIGHTBLUE); /* 画淡蓝色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 画白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 计算缓冲区大小，然后存储 */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();} void Checker(void) /* 画棋盘函数 */ { int i,k; for(k=0;k<8;k++)for(i=0;i<8;i++)if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);} } void PrintQueen(Queen *t) /* 图形输出函数 */ {int k;char str[20];static total=0;total++;setviewport(240,80,400,260,1); /* 设置窗口 */ sprintf(str,“NO.%d”,total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k<8;k++)if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍历的子树由状态数确定 */ {Q->Y[y]=x;Q->A[x+7]=1;Q->B[x+y+7]=1;Q->C[x-y+7]=1;if(y==7)PrintQueen(Q);QueenRe(Q,y+1); /* 进入下一层递归 */ Q->A[x+7]=0;Q->B[x+y+7]=0;Q->C[x-y+7]=0;} } void main(void){ Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,“D://Win-TC”);SetQueen(&Q);setcolor(YELLOW);QueenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,“Eight Queens”);setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,“2009.11.8 3:30pm”);QueenRe(&Q,0);getch();closegraph();} 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：E01214058宋思怡 《数据结构》实验报告 （一）学号：姓名：专业年级： 实验名称：线性表 实验日期：2014年4月14日 实验目的： 1、熟悉线性表的定义及其顺序和链式存储结构； 2、熟练掌握线性表在顺序存储结构上实现基本操作的方法； 3、熟练掌握在各种链表结构中实现线性表基本操作的方法； 4、掌握用 C/C++语言调试程序的基本方法。 实验内容： 一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素24的位置； （8）在L的第4个元素前插入元素0； （9）输出顺序表L； （10）删除L的第5个元素； （11）输出顺序表L。 源代码 调试分析（给出运行结果界面） 二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： „„„„ „„„„ 小结或讨论: （1）实验中遇到的问题和解决方法 （2）实验中没有解决的问题 （3）体会和提高 南京信息工程大学实验（实习）报告 实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍 系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700 3实验一顺序表的基本操作及C语言实现 【实验目的】 1、顺序表的基本操作及 C 语言实现 【实验要求】 1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。 2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。 【实验内容】 1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作； 2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重 复的元素），并求这样的两个集合的并。 【实验结果】 [实验数据、结果、遇到的问题及解决] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。 数据结构实验报告 一． 题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i //数据域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子树为空重接它的左子树 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子树空则重新接它的右子树 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被删除结点的前驱 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函数 printf(“ ---------------------二叉排序树的实现-------------------”);printf(“n”);int layer;inti;intnum;printf(“输入节点个数:”);scanf(“%d”,&num);printf(“依次输入这些整数（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉树创建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“树状图为:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示输入操作符************************:”);printf(“n”);printf(“ 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“输入要插入的节点:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“树状图为:n”); printtree(bst,layer); break; case 2: } printf(“输入要删除的节点”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“删除成功!”);printf(“树状图为:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非递归遍历二叉树”);printf(“先序遍历:n”);PreOrderNoRec(bst);printf(“中序遍历:n”);InOrderNoRec(bst); printf(“后序遍历:n”); PostOrderNoRec(bst); printf(“树状图为:n”); printtree(bst,layer); break;case 5: printf(“程序执行完毕!”); return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType; //数据类型 typedefstring SlemType; typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含参函数也类似 即可完成50个信息存储 用数组存储50个信息，查看以往代码 #include int main(){ cout<<“ 欢迎来到学生管理系统”< cout<<“该学号信息已经存在，添加失败”< break;} cout<<“重新输入添加的学号”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“谢谢使用”< 二叉排序树储存数据界面（储存学生信息略） 创建二叉树： 插入节点： 删除节点： 非递归遍历： 退出： 数组储存学生信息界面 分析查找效率： 因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。 四． 总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。 一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。 递归遍历的实现比非递归的遍历真的简单很多。 开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。第二篇：数据结构八皇后问题实习报告（写写帮整理）
第三篇：数据结构实验报告
第四篇：数据结构实验报告
第五篇：数据结构实验报告
点击咨询 