第一篇：数据结构 队列实验报告
队列实验报告
小组成员：xxxxxxxx日期：xxxxxxxx
一、需求分析（xxx）
1.链队列
1）在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。最后销毁队列，释放空间。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“销毁队列”“清空队列”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到链队列 1输出队列长度 2元素入队 3元素出队 4销毁队列 5清空队列 6对头元素 7退出链队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”“销毁队列”“清空队列”等操作。2.顺序队列
1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到顺序队列 1入队 2出队
3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。3循环队列
1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到循环队列 1入队 2出队
3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。
二．概要设计(xxxx)
⒈ 为实现上述算法，需要顺序表的抽象数据类型，抽象数据类型定义如下：
ADT Queue { 数据对象：D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 } 数据关系: R={
操作结果：队列Q已被销毁。ClearQueue(&Q)初始条件：队列Q已存在。
操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。
操作结果：若Q为空队列，则返回TRUE,否则FALSE。QueueLength(Q)初始条件：队列Q已存在。
操作结果：返回Q元素的个数，即队列的长度。GetHead(Q,&e)初始条件:Q为非空队列。
操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。
操作结果：插入e返回Q的新的队尾元素。DeQueue(&Q，&e)初始条件：Q为非空队列。
操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue
2.单链队列
typedefstructQNode { QElemType;structQNode *next;//指针域 }QNode,*QueuePtr;Typedefstruct{ QueuePtr front;QueuePtr rear;}LinkQueue;Status InitQueue(LinkQueue&Q)//构造一个空队列。
Status DestroyQueue(LinkQueue&Q)//销毁队列Q，Q不存在。
Status ClearQueue(LinkQueue&Q)//将Q清为空队列。
Status QueueEmpty(LinkQueueQ)//若Q为空队列，则返回TRUE,否则FALSE。intQueueLength(LinkQueueQ)//返回Q元素的个数，即队列的长度。
Status GetHead(LinkQueueQ,QElemType&e)//若队列不为空，则用e返回Q的队头元素，并返回OK;否则返回ERROR。
Status EnQueue(LinkQueue&Q,QElemType e)//插入e返回Q的新的队尾元素。
Status DeQueue(LinkQueue&Q,QElemType&e)//若队列不空，则删除Q的队头元素，并用e返回其值，并返回OK;否则返回ERROR。
三．详细设计（xxx）
1.顺序队列的实现和运算
1）元素的类型 typedefstruct { Datatypedata[MAXSIZE];intfront,rear;}Squeue;2）空的队列的构造
void InitSqueue(Squeue *p)/*初始化队列*/ { p->front=0;p->rear=0;} 3）元素的入队
int Ensqueue1(Squeue1 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} 4）元素的出队
int DeSqueue1(Squeue1 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 5）判断队列是否为空
int QueueEmpty1(Squeue1 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 6）队头元素的取值的算法
int Gethead1(Squeue1 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->data[q->front];return 1;} 7）遍历顺序队列的算法
void display1(Squeue1 q)//遍历顺序对列 { printf(“此队列数据为:n”);if(q.front==q.rear)printf(“此队列为空!”);else { while(q.front void InitQueue2(LinkQueue *q){ // 构造一个空队列Q q->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;} 2）元素的入队算法 void EnQueue2(LinkQueue *q, QElemType e)//将元素e进队 { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//创建新节点 if(!p)//如果内存分配成功 exit(1); p->data=e;//初始化新节点数据为e p->next=NULL; q->rear->next=p; q->rear=p;} 3）元素的出队的算法 int DeQueue2(LinkQueue *q,QElemType e)//队头结点出队,将出队的元素存入e { QueuePtr p;if(q->front==q->rear)//队列为空 return 0;p=q->front->next;//初始化temp为要出队的结点指针 if(q->front->next==q->rear)//要出队的结点为最后一个结点 q->rear=q->front;e=p->data;//要出队的数据元素为e q->front->next=p->next;//使下一个结点变为对头 free(p);//删除要出队的结点 return e;} 4）队列的长度算法 void QueueLength2(LinkQueue *q)//返回队列长度 { QueuePtr p;int i=0;p=q->front->next;while(p){ ++i; p=p->next;} printf(“链队列长度为:%dn”,i);} 5）队列的销毁 void DestroyQueue2(LinkQueue *q){ while(q->front){ q->rear=q->front->next; free(q->front); q->front=q->rear; if(!q->rear) free(q->rear);} free(q->front);} 6）队列的输出算法 void output2(LinkQueue *q)//输出队列 { QueuePtr p;p=q->front->next;printf(“链队列元素依次为:”);while(p){ printf(“%d->”,p->data); p=p->next;} printf(“n”);} 7）队列的清空的算法 void Clear2(LinkQueue *q)//清空队列 { QueuePtr temp=q->front->next;while(temp){ QueuePtrtp=temp; temp=temp->next; free(tp);} temp=q->front; q->front=q->rear=NULL;free(temp);} 8）返回对头元素的算法 int GetHead2(LinkQueue *q, int *e)//返回对头结点元素，存入e { if(q->front==q->rear) return 0;*e=q->front->next->data;return 1;} 3.循环队列的实现和运算 1）队列的初始化算法 void InitSqueue3(Squeue3 *p)/*初始化队列*/ { p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE);p->front=0;p->rear=0;} 2）入队的算法 int Ensqueue3(Squeue3 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} else q->base[q->rear]=e;/*将接收到得值付给队尾所指的节点*/ q->rear=(q->rear+1)% MAXSIZE;/*队尾向后移一位完成入队*/ return 1;} 3）出队的算法 int DeSqueue3(Squeue3 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 4判断队列是否为空的算法 int QueueEmpty3(Squeue3 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 5）对头元素的返还的算法 int Gethead3(Squeue3 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->base[q->front];return 1;} 6）遍历循环队列的算法 void display3(Squeue3 *q)//遍历循环对列 { int tail;tail=q->front;printf(“此队列数据为:n”);if(q->front==q->rear)printf(“此队列为空!”);else { while(tail!=q->rear){ printf(“%dt”, q->base[tail]);tail=(tail+1)%MAXSIZE;} printf(“n”);} } 4.主函数的算法 void main(){ int choice;Datatype e1;int i1,a1,x1,s1,j1;//顺序队列定义的量 int e2,i2,n2,s2,a2;//链队列定义的量 int i3,a3,x3,s3,j3;//循环队列定义的量 Datatype e3; Squeue1 Q1; //******************************* LinkQueue q; //******************************** Squeue3 Q; //**************************** choice=-1;Begin();while(choice!=0){ scanf(“%d”,&choice);switch(choice){ case 1://顺序队列 { system(“cls”);InitSqueue1(&Q1);printf(“创建队列完成!n”);printf(“请输入数据个数j1=”);scanf(“%d”,&j1);for(i1=1;i1<=j1;i1++)//输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列 { printf(“请输入第%d个数据:”,i1);scanf(“%d”,&a1);Ensqueue1(&Q1,a1); } printf(“对头为:%dn”,Q1.data[Q1.front]);printf(“队尾为:%dn”,Q1.data[Q1.front+j1-1]);display1(Q1);s1=-1;start1();while(s1!=0) { scanf(“%d”,&s1);switch(s1) { case 0: system(“cls”); choice=-1; Begin(); break;case 1: { system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x1);Ensqueue1(&Q1,x1);display1(Q1); s1=-1; start1();break; } case 2: { system(“cls”);DeSqueue1(&Q1,&e1);display1(Q1);s1=-1; start1();break; } case 3: { system(“cls”);if(QueueEmpty1(Q1))printf(“此队列为空!n”);else printf(“此队列不为空!n”); } s1=-1; start1();break;case 4: { system(“cls”); Gethead1(&Q1,&e1);printf(“对头元素为:%dn”,e1); s1=-1; start1();break; } case 5: { system(“cls”);display1(Q1);s1=-1; start1();break; } }//switch } //while }//case1 break;//************************************************* case 2: { system(“cls”); InitQueue2(&q);printf(“创建队列完成!n”);printf(“输入将建立链队列元素的个数:n2=”);scanf(“%d”,&n2);printf(“请输入队列的元素：n”);for(i2=1;i2<=n2;i2++) { printf(“请输入第%d个元素:”,i2); scanf(“%d”,&e2); EnQueue2(&q,e2); } a2=-1;start2();while(a2!=0) { scanf(“%d”,&a2); switch(a2) { case 1:system(“cls”); QueueLength2(&q); a2=-1;start2(); break; case 2:{ system(“cls”); printf(“请输入入队元素:”); scanf(“%d”,&e2);EnQueue2(&q,e2); output2(&q);a2=-1;start2(); }break; case 3: system(“cls”); e2=DeQueue2(&q,e2); output2(&q); printf(“出队元素为:%dn”,e2);a2=-1;start2(); break; case 4:DestroyQueue2(&q);printf(“队列已销毁!n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 5: Clear2(&q);printf(“队列已清空n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 6: system(“cls”);GetHead2(&q,&e2); printf(“队头元素为:%dn”,e2);s2=-1; start2(); break; case 0: system(“cls”); choice=-1; Begin(); break; }//switch }//while }//case2 break;//************************************************** case 3: { system(“cls”); InitSqueue3(&Q);printf(“创建队列完成!n”);printf(“请输入数据个数j3=”);scanf(“%d”,&j3);for(i3=1;i3<=j3;i3++)//输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列 { printf(“请输入第%d个数据:”,i3);scanf(“%d”,&a3);Ensqueue3(&Q,a3); } printf(“对头为:%dn”,Q.base[Q.front]);printf(“队尾为:%dn”,Q.base[Q.front+j3-1]);display3(&Q);s3=-1;start3();while(s3!=0) { scanf(“%d”,&s3);switch(s3) { case 0: system(“cls”); choice=-1; Begin(); break;case 1: { system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x3);Ensqueue3(&Q,x3);display3(&Q); s3=-1; start3();break; } case 2: { system(“cls”);DeSqueue3(&Q,&e3);display3(&Q);s3=-1; start3();break; } case 3: { system(“cls”);if(QueueEmpty3(Q))printf(“此队列为空!n”);else printf(“此队列不为空!n”); } s3=-1; start3();break;case 4: { system(“cls”); Gethead3(&Q,&e3);printf(“对头元素为:%dn”,e3); s3=-1; start3();break; } case 5: { system(“cls”);display3(&Q);s3=-1; start3();break; } }//switch } //while }//case 3 break; case 0: printf(“ 谢谢使用！！n”); break; //*************************** }//switch }//while }//main 四．调试分析（xxx） 顺序队列 1.编译并调试，运行程序。 2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。3.判断队列是否为空。队列是否为空的标志就是队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等。 4.队列满时候不能入队列，否则会出现溢出现象。即先要判断队列是否已经已满，因为队尾指针的最大值是MAXQSIZE，所以通过检查队尾指针rear是否等于MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。 5.在元素出队操作，先通过队头指针和队尾指针是否相等判断队列是否已空，空时不能操作，这是要注意的。 6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。 7.本程序存在较多不足，如有问题，参考用户手册。 8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。 链队列 1.编译并调试，运行程序。2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。 3.要注意设定一个在链队列添加一个头结点并令指针指向头结点。同时，删除不可以在最后面进行删除，但是插入可以最后一个进行插入，这点需要注意 4.需要分别指向队头和队尾的指针。 5.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。 6.本程序存在较多不足，如有问题，参考用户手册。 7.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。 循环队列 1.编译并调试，运行程序。 2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。 3.为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。4.队头指针和对尾指针与队列元素之间关系和顺序队列一样，不变。5.先判断队列是否为空。就是看队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等，空时不能操作，这是要注意的。 6.在将元素插入到队列之前首先要判断队列是否已经已满，根据顺序循环队列队满条件front==(rear+1)%MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。 6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。 7.本程序存在较多不足，如有问题，参考用户手册。 8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。 五、用户手册(xx)1.链队列 (1)本程序的运行环境为DOS操作系统，执行文件名为：j.exe.(2)进入演示程序后即显示文本方式的用户界面，输入元素1,2,3,4,5创建队列。 （3）根据提示，选择操作2执行元素入队操作。回车，输入入队元素0，回车，将0插入到队列中。 （4）选择操作3执行元素出队操作，回车，队首元素1出队。 （5）选择操作1执行输出队列长度操作，回车，输出队列长度为5.（6）选择操作5执行清空队列操作，回车，清空。 （7）选择操作6执行输出队头元素操作，回车，输出元素2。 2.顺序队列 （1）创建队列，输入数据 1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0 （3）选择操作2，执行出队操作。 队首元素1出队.（4）选择操作3，判断对是否为空 （5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素 3、循环队列 （1）创建队列，输入数据 1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0 （3）选择操作2，执行出队操作。队首元素1出队.（3）选择操作3，判断对是否为空 （5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素为,2,3,4,5,0 六．测试结果（xxx）1.顺序队列的实现和运算 1）输入1即可进行进入到顺序队列 2）顺序队列的建立，输入元素的个数为5，输入的数据分别为1，2，3，4，5，对头为1，队尾为5，此时队列的数据为1 2 3 3）输入2即可进行入队运算，输入的入队元素为0，此时的队列的数据为1 2 3 4 5 0 4）输入3即可进行判断队列的是否为空，如下图： 5）输入4即可进行去的对头元素的算法，如下图所示： 6）此时的队列的数 据 为 0，如 下 图 ： 7）输入0即可退出顺序队列，如下图： 8）输入3即可进行顺序队列的算法，如下图所示： 9）输入1即可进 行 相 应的入 队 运 算，如 下 10）输入2即可进行队列的出队运算，如下图所示： 所 示 图 ：11）输入3 即可判断顺序队列是否为空的算法，如下图所示： 12）输入4即可进行去的头结点的运算，如下图所示： 13）输入5即可进行队列的输出显示的运算，如 14）输入0即可进行退出顺序队列的算法，如下图所示： 下图所示：2.链式队列的实现和运算 1）队列的建立以及队列的个数输入为5，输入的数据分别为1，2，3，4，5.如下图： 2）输入2即可进入到元素的入队运算，输入入队的元素的为0，输入3即可进行相应的元素的出队运算，出队元素为1.如下图： 3）则此时的队列的长度为5，输入4即可进行队列的销毁以及输入5即可进行队列的清空运算，如下图： 4）输入6即可进行输出队列的对头元素，输入0即可进行退出链队列的运算 3．循环队列的实现和运算 1）输入3即可进行循环队列的操作，输入5个数据，它们分别为1 2 3 4 5，输入1，即可进行入队操作，输入入队的元素为0，则此时的数据为1 2 3 4 5 0，如下图所示： 2）输入2即可进行出队运算，如下图所示： 3）输入3即可进行判断队列的是否为空，如下图所示： 4）输入4即可进行取得对头元素，如 下 5)输入5即可进行输出所有的数据显示，如下图所示： 所示图： 七．心得体会（xx） 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出” 的线性表。注意的是为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。还有要注意的是在C语言中不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法估计所用队列的最大长度，则宜采用链式队列。 实验二 栈和队列及其应用 一、实验目的 1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2.熟练掌握栈类型的两种实现方法。 3.熟练掌握循环队列和链队列的基本操作实现算法。 二、实验内容 用队列求解迷宫问题 [问题描述] 以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。[基本要求] 实现一个以顺序存储结构的队列类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，pre）的形式输出，其中：（i，j）指示迷宫中的一个坐标，pre表示本路径中上一个方块在队列中的下标。 [测试数据] 由学生任意指定。 三、源代码 # include //行数 //列数 //队最多元素个数 //一个迷宫,其四周要加上均为1的外框{1,1, #define MaxSize 100 int mg[M+2][N+2]={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,0,1,1}, {1,0,1,0,0,1,1}, {1,0,1,0,1,0,1}, {1,0,0,0,0,0,1}, {1,1,1,1,1,1,1} }; typedef struct {int i,j;int pre;} Box;typedef struct { Box data[MaxSize];int front, rear;}QuType;void mgpath1(int xi,int yi,int xe,int ye)//搜索路径为：（xi，yi）{ void print(QuType qu, int front);->(xe,ye) int i,j,find=0,di;QuType qu;//定义顺序队 qu.front=qu.rear=-1;qu.rear++;qu.data[qu.rear].i=xi;//(xi,yi)进队 qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;while(qu.front!=qu.rear&&!find){qu.front++;i=qu.data[qu.front].i;j=qu.data[qu.front].j;if(i==xe&&j==ye){find=1;print(qu,qu.front); } for (di=0;di<4;di++) { switch(di) { case 0 :i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case 1 :i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case 2 :i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break;case 3 :i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break; } if(mg[i][j]==0) {find=1; qu.rear++; qu.data[qu.rear].i=i;qu.data[qu.rear].j=j; qu.data[qu.rear].pre=qu.front; mg[i][j]=-1; } } } } void print(QuType qu, int front){ int k=front,j,ns=0; printf(“n”);do {j=k; k=qu.data[k].pre; qu.data[j].pre=-1; } while(k!=0);printf(“迷宫路径如下：n”);k=0;while(k ns++; printf(“t(%d,%d)”,qu.data[k].i,qu.data[k].j); if(ns%5==0)printf(“n”);} k++;} printf(“n”);} void main() { mgpath1(1,1,M,N);printf(“迷宫所有路径如下:n”); } 四、测试结果： 五、心得体会 做实验首先要掌握大量的理论知识，然后认真去完成实验。做实验过程会碰见较大的困难，这就要需要我们的毅力。小小的迷宫隐藏大大的奥秘。 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：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（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。第二篇：2数据结构-实验报告二(栈和队列及其应用)
第三篇：数据结构实验报告
第四篇：数据结构实验报告
第五篇：数据结构实验报告
点击咨询 