数据结构顺序表链表试验报告.doc

数据结构课程设计数据结构课程设计 -个人设计报告 学院： 计算机科学与技术学院 专业： 班级： 姓名： 学号： 指导教师： 完成日期：-目录-1 实验一分录- 31.1 实验名称 - 31.2 实验内容 - 41.3 概要分析 - 41.4 实验代码 - 51.5 运行结果 - 51.6 思想小结 - 72 实验二分录- 72.1 实验名称 - 72.2 实验内容 - 72.3 概要分析 - 82.4 实验代码 - 82.5 运行结果 - 92.6 思想小结 - 93 附录- 10 3.1 实验一代码- 10 3.2 实验二代码- 14实验一分录1.1实验名称顺序表的应用1.2 实验内容（1） 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度为0(1)的算法，该算法删除线性表中所有值为item的数据元素。要求：线性表元素个数n很大，而值为item的数据元素个数很少，要求移动元素个数尽量少；删除后的数组元素与原数组元素不必保持顺序一致。（2）编写一个函数将一个顺序表A（有n个元素，且任何元素均不为0）分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。（3）假设一个算术表达式中包含圆括号，方括号和花号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数correct（exp，tag）；其中：exp为字符串类型量，表示被判别的表达式，tag为布尔型的变量。（4）编写向顺序分配的循环队列QU0,m-1中插入一个结点的函数enqueue和从该队列中取出一个节点的dequeue函数。（5）编写一个主函数,调试上述算法。1.3 概要分析想要完成顺序表的相关操作首先要建立顺序表：void Creatlist(Sqlist &L)；void Deleteitem(Sqlist &L)初始条件：顺序表已经建立操作结果：将顺序表中指定的元素删除，并重新输出删除元素后的序列元素； void Despart(Sqlist &p,Sqlist &r,Sqlist &c)初始条件：顺序表已经建立操作结果：拆分顺序表，将顺序表中的元素大于0的元素重新放入另一顺序表，将小于等于0的元素放入另一新建顺序表，并输出新建的两个顺序表的元素； void InitStack(seqstack *s)操作结果：进行栈的建立的操作；void Push(seqstack *s, char x)初始条件：栈已经建立操作结果：元素的入栈操作；char Pop(seqstack *s)初始条件：栈已经建立操作结果：元素的出栈操作；int MatchingCheck()初始条件：栈已经建立操作结果：利用进栈出栈的操作进行括号的匹配检验；void initqueue(queue &q)操作结果：进行队列的建立操作；void qinsert(queue &q)初始条件：队列已经建立操作结果：进行元素插入队列的操作，将元素插入到队列的尾部；void qdelete(queue &q)初始条件：队列已经建立操作结果：进行元素从队列中的删除操作，删除队列的首部元素。1.4 实验代码 见附录一；1.5 运行结果 程序执行后出现下图样式的菜单：新建顺序表：删除顺序表中所要求的元素：拆分顺序表：判别括号是否配对：正确的匹配：建立一个循环队列：向循环队列中插入元素：从循环队列中删除元素：退出操作：1.6 思想小结：实验二分录2.1 实验名称链表的应用2.2 实验内容(1) 假设有两个按元素值递增次序排列的线性表A和B，均以单链表形式存储，里面的大部分元素对应相等，请删除一些元素（A中有而B中没有，或B中有而A中没有），使得两个有序表中保留下来的元素对应相等。比如，A中元素为（1,3,5,8,10,13,18），B中元素为（1,3,6,8,9,10,13,15），则删除元素后A、B里的元素为（1,3,8,10,13）。(2) 猴子选大王。n只猴子围成一圈，从1到m报数，报m的猴子出局。余下的猴子从第m+1只开始继续从1到m报数，报m的猴子出局。第n只猴子报数后，第1只猴子接着报数（因为围成了圈）。待整个圈只剩下一只猴子时，该猴子即为大王。n和m由用户输入，请输出当选大王的猴子的编号。(3) 设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有prev（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。 (4) 在主函数中设计一个简单的菜单，分别调试上述算法。2.3 概要分析要完成实验的内容首先要进行链表的建立：DLinkList *Created()；void CreateSame(Sqlist &L1, Sqlist &L2)初始条件：链表已经建立操作结果：将两个链表中的不同元素进行删除处理，并最后输出删除不同元素的立案表内容；void Chooseking(DNode *head)初始条件：链表已经建立操作结果：循环链表的应用，进行指定数字的元素删除，知道甚于最后以元素，也就是所谓的猴子大王；void printed(DLinkList* head)操作结果：链表的内容输出函数；DLinkList *Locate(DLinkList *L, int x)初始条件：带有表头结点的非循环双向链表已经建立操作结果：进行访问元素的频度记录和换位操作；void LocateLine()初始条件：进行访问元素输入操作并进行最后换位后的链表内容输出。2.4 实验代码 见附录二；2.5 运行结果程序执行后出现下图样式的菜单：删除两个链表中的不同元素：猴子选大王问题：当所报号码为1时：非循环双向链表的访问频度排序：退出操作：思想小结：附录：3.1 实验一代码#include#include#define MAXSIZE 100typedef int ElemType;typedef struct listElemType elemMAXSIZE; int length;Sqlist;typedef struct NodeElemType date;struct Node *next;DNode;typedef struct DulNodeElemType date;struct DulNode *prev,*next;int freq;DLinkList;/定义双向链表void Creatlist(Sqlist &L)int i;printf(请输入顺序表的长度：);scanf(%d,&L.length);for(i=0;iL.length;i+)scanf(%d,&L.elemi);void CreateSame(Sqlist &L1, Sqlist &L2)int counter=0;Sqlist L3;Creatlist (L1);Creatlist (L2);for(int i=0;iL1.length;i+)for(int j=0;jL2.length;j+)if(L1.elemi=L2.elemj)L3.elemcounter=L1.elemi;counter+;printf(删除相同元素后的链表元素：);for(i=0;icounter;i+)printf(%d ,L3.elemi);printf(n);void Chooseking(DNode *head)int m,num;printf(请输入猴子的总数：); scanf(%d,&num);printf(出局的猴子所报的号码是：); scanf(%d,&m);DNode *s,*q,*t;int i,counter=0;if(m=1)printf(最后一只猴子是%d号。n,num);elsefor(i=0;idate=i+1;s-next=NULL;if(i=0)head=s;q=head;elseq-next =s;q=q-next;q-next=head;q=head;while(q-next!=q)counter+;if(counter=m-1)t=q-next;q-next=t-next;counter=0;free(t);q=q-next;printf(最后一只猴子是%d号。n,q-date);DLinkList *Created()int num=0;DLinkList *head;DLinkList *p1,*p2;p1=p2=(DLinkList *)malloc(sizeof (DLinkList);scanf(%d,&p1-date);head=NULL;while(p1-date!=0)num+;if(num=1)head=p1;elsep2-next=p1;p1-prev=p2;p2=p1;p1=(DLinkList *)malloc(sizeof (DLinkList);scanf(%d,&p1-date);p2-next=NULL;return(head);void printed(DLinkList* head)DLinkList *p=head;while(p!=NULL)printf(%d ,p-date);p=p-next;printf(n);DLinkList *Locate(DLinkList *L, int x) DLinkList *p=L-next; DLinkList *q;while(p & (p-date!=x) p=p-next;if(!p) return NULL; elsep-freq+; q=p-prev; while( (q!=L) & (q-freq)freq) q=q-prev;if(q!=p-prev) p-prev-next=p-next;if(p-next)p-next-prev=p-prev; p-prev=q;p-next=q-next;q-next=p;p-next-prev=p; return p; void LocateLine()DLinkList *p,*head; int i;head=(DLinkList *)malloc(sizeof(DLinkList);head-date=0;printf(输入链表各个结点的值(数字0代表结束):n);p=Created();head-next=p;p-prev=head;printed(head);int num;printf(输入要访问的元素(数字0代表访问结束):n);for(;i!=0;)scanf(%d,&num);i=num;p=Locate(head,num);printf(根据访问频度重新排序后的链表变为:n);printed(head-next);void main()int n;Sqlist head1,head2;DNode *head3;printf(*n);printf(0.退出程序。n);printf(1.删除两个链表中的不同元素。n);printf(2.猴子选大王的问题.n);printf(3.带有表头结点的非循环双向链表问题。n);printf(*n);while(n!=0)printf(请选择：);scanf(%d,&n);switch(n)case 0:printf(退出系统！n);exit(0);break;case 1:CreateSame(head1,head2); break; case 2:Chooseking(head3);break; case 3:LocateLine();break; 实验二代码：#include#include#define MAXSIZE 100typedef int ElemType;typedef struct listElemType elemMAXSIZE; int length;Sqlist;typedef struct NodeElemType date;struct Node *next;DNode;typedef struct DulNodeElemType date;struct DulNode *prev,*next;int freq;DLinkList;/定义双向链表void Creatlist(Sqlist &L)int i;printf(请输入顺序表的长度：);scanf(%d,&L.length);for(i=0;iL.length;i+)scanf(%d,&L.elemi);void CreateSame(Sqlist &L1, Sqlist &L2)int counter=0;Sqlist L3;Creatlist (L1);Creatlist (L2);for(int i=0;iL1.length;i+)for(int j=0;jL2.length;j+)if(L1.elemi=L2.elemj)L3.elemcounter=L1.elemi;counter+;printf(删除相同元素后的链表元素：);for(i=0;icounter;i+)printf(%d ,L3.elemi);printf(n);void Chooseking(DNode *head)int m,num;printf(请输入猴子的总数：); scanf(%d,&num);printf(出局的猴子所报的号码是：); scanf(%d,&m);DNode *s,*q,*t;int i,counter=0;if(m=1)printf(最后一只猴子是%d号。n,num);elsefor(i=0;idate=i+1;s-next=NULL;if(i=0)head=s;q=head;elseq-next =s;q=q-next;q-next=head;q=head;while(q-next!=q)counter+;if(counter=m-1)t=q-next;q-next=t-next;counter=0;free(t);q=q-next;printf(最后一只猴子是%d号。n,q-date);DLinkList *Created()int num=0;DLinkList *head;DLinkList *p1,*p2;p1=p2=(DLinkList *)malloc(sizeof (DLinkList);scanf(%d,&p1-date);head=NULL;while(p1-date!=0)num+;if(num=1)head=p1;elsep2-next=p1;p1-prev=p2;p2=p1;p1=(DLinkList *)malloc(sizeof (DLinkList);scanf(%d,&p1-date);p2-next=NULL;return(head);void printed(DLinkList* head)DLinkList *p=head;while(p!=NULL)printf(%d ,p-date);p=p-next;printf(n);DLinkList *Locate(DLinkList *L, int x) DLinkList *p=L-next; DLinkList *q;while(p & (p-date!=x) p=p-next;if(!p) return NULL; elsep-freq+; q=p-prev; while( (q!=L) & (q-freq)freq) q=q-prev;if(q!=p-prev) p-prev-next=p-next;if(p-next)p-