《数据结构验证作业资料》由会员分享，可在线阅读，更多相关《数据结构验证作业资料（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告一、上机实验的问题和要求:单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、 插入与删除。具体实现要求：1. 从键盘输入20 个整数，产生不带表头的单链表，并输入结点值。2. 从键盘输入1 个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。3. 从键盘输入 2 个整数，一个表示欲插入的位置i ，另一个表示欲插入的数值x ，将 x 插入在对应位置上，输出单链表所有结点值，观察输出结果。4. 从键盘输入 1 个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。5. 将单链表中值重复的结点删除，使所得的结
2、果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。8. （）将单链表分解成两个单链表A 和 B ，使 A 链表中含有原链表中序号为奇数的元素，而B 链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A 和单链表 B 的所有结点值，观察输出结果。、程序设计的基本思想，原理和算法描述:1、基本操作函数link * get(link *l, int i) ；/创建链表link * ins (link *l, int
3、a,int i)/在链表内插入值link * find(link *l, int a) ；/在链表内查找值link * del(link *l, int i);/在链表内删除值link * delrepeat( link *l);/ 在链表内删除重复值link * deleven(link *l);/删除链表内偶数值link * rotate(link *l);/ 形成循环链表void divide(link *l);/分解成两个链表coutendl;2、基本操作瑾？请选择您要的操作：cout 1 、插入;cout 2 、查找;cout 3 、删除;cout 4 、删除重复结点cout 5 、
4、删除偶数结点cout 6 、构建循环链表cout 7 、分解为两个链表cout 0 、退出1三、源程序及注释： #include using namespace std;typedef struct nodeint data;struct node *next;link;void print1(link *l);link * get(link *l, int i)link *p;int j=0;p=l;while(jnext!=NULL)p=p-next;j+;if(j=i)return p;elsereturn NULL;link * ins (link *l, int a,int i)li
5、nk *p,*s;p=get(l,i -1);if(p=NULL)data=a;s-next=p -next;return l;2link * find(link *l, int a)link *p;int i=0;int j=0;p=l;while(p!=NULL)i+;if(p -data!=a)p=p -next;else瑾？您查找的数据在第？北?个位置.next;if(j!=1)瑾？您查找的数据不在线性表中.endl;return l;link * del(link *l, int i)link *p,*s;p=get(l,i -1);if(p=NULL)瑾？输入有误next;p-ne
6、xt=s -next;free(s);return l;/ 删除相同元素并释放内存link * delrepeat( link *l) link *s,*r,*t;if (l- next = NULL )3return l;s =l- next;while (s- next )t =s; r =s- next;while(t- next)if (s- data =r- datat- next =r- next;free(r);r =t- next; elset =t- next;r =t- next;s=s- next;if(!s )return l; return l;link * dele
7、ven(link *l)link *q=l;link *p=l -next; while(p)if(p -data%2=0)link *r=p;q-next=p -next;free(r);elsep=p -next;q=q -next;4return l;link * rotate(link *l)link * p=l;while(p -next)p=p-next;p-next=l;link * t=l -next;while(t!=l)t=t-next;瑾？已经变为循环链表，其他操作将受影响，程序结束！ next=NULL;link *Lb=b;int i=1;link * La=l;li
8、nk * p=l -next;while(p)if(i+%2=0)La-next=p -next;p-next=NULL;Lb-next=p;Lb=Lb -next;p=La-next;elsep=p -next;La=La -next;5a; 瑾？链表print1(a);b; 瑾？链表print1(b);void print1(link *l)int i,k;int a;link *p,*q;next;if(l!=NULL)docoutdatanext;while(p!=NULL);coutendl;link * print(link *l)int i,k;int a;link *p,*q;
9、next;if(l!=NULL)do coutdatanext;while(p!=NULL);coutendl;瑾？请选择您要的操作：; cout 1 、插入; 、查找 cout 2; 、删除 cout 3; cout 4 、删除重复结点; 、删除偶数结点 cout 5;、构建循环链表cout 6 6cout 7 、分解为两个链表;cout 0 、退出 ;coutk;if(k=1)瑾?请输入您要插入的数据值：；cina;瑾？请输入您要插入的位置：；cini;p=ins(l,a,i);q=print(l);else if(k=2)瑾？请输入您要查找的数据值：；cina;p=find(l,a);q
10、=print(l);else if(k=3)瑾？请输入您要删除的数据的位置：；cini;p=del(l,i);q=print(l);else if(k=4)瑾?删除重复结点后的p=delrepeat(l);q=print(l);else if(k=5)瑾姗除偶数结点后的 p=deleven(l);q=print(l);else if(k=6)p=rotate(l);q=print(l);7else if(k=7)divide(l);else if(k=0);else!endl; 捻畯?尼输入错误return l; int main()next=NULL;r=l;for(i=0;ichi;p=(link *)malloc(sizeof(link);p-data=chi;p -next=NULL;r-next=p;r=r -next; q=print(l); return 0;8
