单链表的查找、插入与删除

1、数据结构实验报告一题目：单链表的查找、插入与删除 班级： 电子0802 学号： 姓名： 日期： 2011.03.08 程序名： cqq1.c 一、上机实验的问题和要求：单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：1. 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。2. 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。4. 从键盘输入1个整数

2、，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。8. （）将单链表分解成两个单链表a和b，使a链表中含有原链表中序号为奇数的元素，而b链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表a和单链表b的所有结点值，观察输出结果。二、程序设计的基本思想，原理和算法描述：1、基本操作函数link * get(lin

3、k *l, int i)； /创建链表link * ins (link *l, int 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请选择您要的操作：;cout 1、插入;c

4、out 2、查找;cout 3、删除;cout 4、删除重复结点;cout 5、删除偶数结点;cout 6、构建循环链表;cout 7、分解为两个链表;cout 0、退出;三、源程序及注释：#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 n

5、ull;link * ins (link *l, int a,int i) link *p,*s;p=get(l,i-1);if(p=null)cout输入有误data=a;s-next=p-next;p-next=s;return l;link * 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 cout您查找的数据在第i-1个位置.next;if(j!=1)cout您查找的数据不在线性表中.endl;return l;link * del(link *

6、l, int i)link *p,*s; p=get(l,i-1);if(p=null)cout输入有误next;p-next=s-next;free(s);return l;link * delrepeat( link *l) / 删除相同元素并释放内存 link *s, *r, *t; if ( l- next = null ) return l; s = l- next; while ( s- next ) t = s; r = s- next; while ( t- next ) if ( s- data = r- data ) t- next = r- next; free(r);

7、r = t- next; else t = t- next; r = t- next; s = s- next; if ( !s ) return l; return l; link * deleven(link *l) link *q=l;link *p=l-next; while(p)if(p-data%2=0)link *r=p;q-next=p-next;p=p-next;free(r);elsep=p-next;q=q-next;return l;link * rotate(link *l) link * p=l;while(p-next)p=p-next;p-next=l; lin

8、k * t=l-next;while(t!=l)t=t-next;cout已经变为循环链表，其他操作将受影响,程序结束！next=null;link *lb=b; int i=1; link * la=l;link * 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;cout链表a; print1(a); cout链表b; print1(b); void print1(link *l) int i,k;int a;link

9、 *p,*q;cout当前线性表为：next;if(l!=null)do coutdatanext;while(p!=null);coutendl;link * print(link *l) int i,k;int a;link *p,*q;cout当前线性表为：next;if(l!=null)do coutdatanext;while(p!=null);coutendl;cout请选择您要的操作：;cout 1、插入;cout 2、查找;cout 3、删除;cout 4、删除重复结点;cout 5、删除偶数结点;cout 6、构建循环链表;cout 7、分解为两个链表;cout 0、退出;c

10、outk;if(k=1)couta;couti;p=ins(l,a,i);q=print(l);else if(k=2)couta;p=find(l,a);q=print(l);else if(k=3) couti;p=del(l,i);q=print(l);else if(k=4) cout删除重复结点后的;p=delrepeat(l);q=print(l);else if(k=5) cout删除偶数结点后的;p=deleven(l);q=print(l);else if(k=6)p=rotate(l);q=print(l);else if(k=7)divide(l);else if(k=0

11、);elsecout输入错误!endl;return l;int main()cout请输入20个整数：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;四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：1、本次实验采用c+语言，程序基本能实现实验所要求的操作功能，但是首次使用c+来完成所有链表的操作，有很多小细节不够注意，比如定义结点与结点的使用，需要多操作，多熟悉语。2、最后两个操作 void rotate(link *l); /变为循环链表 void divide(link *l); /分解成两个链表一旦执行，将破坏链表的结构，无法再进行其他操作，需要结束整个程序。可以设置一个主函数结束标志，此处就不详细说明。六、对算法的程序的讨论、分析，改进设想，其它经验教训：程序是8个基本操作，设置不同的数字对应这些基本操作，由用户自己选择执行，这样程序灵活