线性表的建立与应用--实验报告

实 验 报 告课程名称 数据结构实验实验名称 线性表的建立与应用 实验类型 设计型 实验地点 实验日期 指导教师 杨 崇专 业 班 级 学 号 姓 名 成 绩辽宁石油化工大学计算机与通信工程学院实验一一 实验目的：通过实验，了解并掌握线性表逻辑特性和物理特性，了解并掌握队列和栈的运算方法，培养结合理论知识进行实际应用的实践能力。二 实验内容：栈和队列的初始化及基本运算的实现，实现栈和队列的初始化、栈的入栈、退栈操作、队列的入队、退队运算，以及将退栈结果入队、退队结果入栈等基本操作。三 实验原理：栈是限制在线性表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈的运算包括初始化、入栈、退栈、读取栈顶元素等。当栈为空的时候不允许退栈，当栈为满的时候不允许入栈。标识栈的特性的是四个变量：栈的首地址V，栈的容量m，栈顶指针Top。栈的初始化：void init-stack(s,m.top)ET s; int m,*top;s=malloc(m*sizeof(ET);*top=0;return;入栈运算void push(s,m,top,x)ET s,x; int m,*top; if *top= =m printf(“stack overflown”);return;*top=*top+1;s*top-1=x; return;退栈运算void pop(s,m.top,y)ET s,*y;int m,*top; if (*top= =0) printf(“stack underflown”);return;y=s*top-1;*top=*top-1;return;读取栈顶元素void top(s,m,top,y)ET s,*y;int m,*top; if (*top = =0) printf(“stack emptyn”);return;y=s*top-1;return;插入在线性表的一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。当队列中没有数据时，我们称这个时候的队列为空队队列也是一种运算受限制的线性表，它的运算包括：初始化队、入队、退队、读取队首和队尾的数据。当队列为空时不允许退队，当队列未满的时候不允许入队。 在实际应用中，通常使用循环队列初始化循环队列void init_queue(q,m,front,rear,s)ET q;int m,*front,*rear,*s; q=malloc(m*sizeof(ET);*front=m;*rear=m;*s=0;return;循环队列入队运算vsid addcq(q,m,rear,front,s,x)ET q;int m,*front,*rear,*s; if (*s=1) & (*rear= =*front)printf(“queue overflown”);return;*rear=*rear+1;if (*rear= =m+1) *rear=1;q*rear-1=x;*s=1;return;循环队列退队运算void delcq(q,m,rear,front,s,y)ET q,*y;int m,*front,*rear,*s; if (*s= =0) printf(“queue underflow n”);return;*front=*front+1;if (*front= =m+1) *front=1;*y=qfront-1;if(*front= =*rear) *s=0;return;四、实验步骤: 1 进入Turbo C 2.0，新建一个文件。2 输入程序，程序要求使用子函数进行组织。3 将源程序保存到指定文件夹“D:学生姓名”。4 按F9调试，纠正语法错误。5按CtrlF9运行，调试逻辑错误。6 按AltF5查看结果。五、实验截图：六、程序源代码：#includemath.h#includestdlib.h#define nd struct nodestruct nodeint d;struct node *next;nd *create(head)nd *head;int d;nd *p;nd *q;d=1;head=(nd *)malloc(sizeof(nd);head-next=NULL;p=head;while (d0)printf(n Please input the number:);scanf(%d,&d);if (d0)q=(nd *)malloc(sizeof(nd);q-d=d;q-next=NULL;p-next=q;p=p-next;return(head);prt(head)nd *head;nd *p;if (head!=NULL)p=head-next;printf(The element in the list are: );while (p!=NULL)printf(%d ,p-d);p=p-next;printf(n);nd *look(head,x)nd *head;int x;nd *p;p=head;while(p-next!=NULL)&(p-next)-d)!=x) p=p-next;return(p);ins(head,x,y)nd *head; int x;int y;nd *p,*q;p=look(head,x);q=(nd *)malloc(sizeof(nd);q-d=y;q-next=p-next;p-next=q;del(head,x)nd *head;int x;nd *p;nd *q;p=head-next;q=head;while (p-d!=x)&(p-next!=NULL)p=p-next;q=q-next;if(p-d=x)q-next=p-next;free(p);elseprintf(No thie element in the listn);nd *un(l1,l2)nd *l1,*l2; nd *p,*q;if (l2!=NULL)p=l1;while (p-next!=NULL) p=p-next;p-next=l2-next;free(l2);return(l1);nd *re(head)nd *head;nd *p,*q,*h;p=head-next;q=p-next;h=q;p-next=NULL;while (q!=NULL)head-next=q;h=h-next;q-next=p;p=q;q=h;return(head);nd *copy(head)nd *head;nd *p,*q,*h,*t;p=(nd *)malloc(sizeof(nd);p-next=NULL;q=head-next;h=p;while (q!=NULL)t=(nd *)malloc(sizeof(nd);t-d=q-d;t-next=NULL;h-next=t;h=h-next;q=q-next;return(p);nd *dec(head,x)nd *head; int x;nd *p,*q;int i=0;p=head;while (p!= NULL)&(i!=x)p=p-next;i+;if (inext=p-next; p-next=NULL; return(q); int wel()int x;printf(n);printf($n);printf($ Welcome use this program! $n);printf($ Please input the command! $n);printf($ 1.Create1 2.insert 3.delete $n);printf($ 4.unite 5.reverse 6.copy $n);printf($ 7.find 8.decompose 9.Create2 $n);printf($n);printf(The command is:);scanf(%d,&x);return(x);int find(head,x)nd *head;int x;int i=0;nd *p;p=head;while (p!=NULL)&(p-d!=x) p=p-next; i+;if (p-d=x) return(i);elsereturn(0);main()nd *head,*head2,*p;int command;int num,sta,x,t;command=wel();while (command!=0)switch(command) case 1:head=create(head);prt(head); break;case 2:printf(Please input the station:);scanf(%d,&sta);printf(Please input the number:);scanf(%d,&num);ins(head,sta,num);prt(head);break;case 3:printf(Please input the number:);scanf(%d,&num);del(head,num);prt(head);break;case 4:prt(head);if (head2!=NULL) prt(head2);head=un(head,head2); free(head2); prt(head);break;case 5:head=re(head);prt(head);break;case 6:head2=copy(head);printf(List1 ); prt(head); printf(List2 );prt(head2);break;case 7:printf(Please input the number you find: );scanf(%d,&x);t=find(head,x);if (t=0) printf(No this element in the listn);elseprintf(The elements station is: %dn,t);break;case 8:printf(Please input the station youll decompose); scanf(%d,&x); head2=dec(head,x); prt(head);prt(head2); break;case 9: head2=create(head2);prt(head2);command=wel();free(head);free(head2);七、实验中应注意的问题与思考题：1 在对栈和队列的运算过程中保证数据结构的逻辑完整性。2 栈和循环队列元素的打印。在打印过程中应该正确分析循环队列的具体情况，做到正确打印。3 栈与队列均不允许在中间插入数据，保证运算的正确性；线性队列不能重复使用，不符合流程化要求，应采取循环队列。4 当栈满，而此时要进行退队入栈运算时应进行怎样的处理才能避免数据的丢失？答：先判断若栈满，则另外进行存储。5 当队列满，而此时要进行退栈入队运算时应进行怎样的