数据结构单链表插入、删除和修改实验报告

1、计算机学院实验报告课程名称： 数据结构 实验名称： 单链表 学生姓名： 朱孝彬 学生学号： 20110511001 实验日期： 2012 一、实验目的1理解数据结构中带头结点单链表的定义和逻辑图表示方法。2掌握单链表中结点结构的c+描述。3熟练掌握单链表的插入、删除和查询算法的设计与c+实现。二、实验内容1 编制一个演示单链表插入、删除、查找等操作的程序。三、实验步骤1需求分析本演示程序用c+6.0编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元

2、素的值。在所有输入中，元素的值都是整数。 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。 测试数据：a 插入操作中依次输入11，12，13，14，15，16，生成一个单链表b 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置c 删除操作中依次输入2，5，删除位于2和5的元素2概要设计1）为了实现上述程序功能，需要定义单链表的抽象数据类型： （1）insert 初始化状态：单链表可以不为空集；操作结果：插入一个空的

3、单链表l。 （2）decelt操作结果：删除已有的单链表的某些结点。（3）display操作结果：将上述输入的元素进行排列显示。（4）modify操作结果：将上述输入的某些元素进行修改。（5）save 操作结果：对上述所有元素进行保存。 （6）load操作结果：对上述元素进行重新装载。3使用说明程序执行后显示= 1.单链表的创建 2.单链表的显示 3.单链表的长度 4.取第i个位置的元素 5.修改第i个位置的元素 6.插入元素到单链表里 7.删除单链表里的元素 8.合并两个单链表 9.退出系统 =5.源代码：#includeusing namespace std;#define true 1#

4、define false 0#define ok 1#define error 0#define overflow -2typedef int status;typedef int elemtype;typedef struct lnode elemtype data; struct lnode *next;lnode,*linklist;void createlist(linklist &l,int n) linklist p; l=new lnode; l-next=null; linklist q=l; for(int i=1;ip-data; p-next=null; q-next=p

5、; q=p; status getelem(linklist l,int i,elemtype &e) linklist p=l-next; int j=1; while(p&jnext; +j; if(!p|ji) return error; e=p-data; return ok;status linkinsert(linklist &l,int i,elemtype e) linklist p=l; int j=0; while(p&jnext; +j; if(!p|ji-1) return error; linklist s=new lnode; s-data=e; s-next=p-

6、next; p-next=s; return ok; status listdelete(linklist &l,int i,elemtype &e) linklist p=l; linklist q; int j=0; while(p-next&jnext; +j; if(!(p-next)|ji-1) return error; q=p-next; p-next=q-next; e=q-data; delete(q); return ok;void mergelist(linklist &la,linklist &lb,linklist &lc) linklist pa,pc,pb;pa=

7、la-next;pb=lb-next;lc=pc=la;while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pc-next=pa?pa:pb; delete(lb); void show(linklist l) linklist p; p=l-next; while(p) coutdata; p=p-next; coutnext; while(p) +i; p=p-next; return i; void xiugai(linklist l) int i,

8、j=1; elemtype k; elemtype e,m; linklist p=l-next; cout请输入要修改的元素位置(0ii; getelem(l,i,e); cout该位置的元素:eendl; coutk; while(p&jnext; +j; m=p-data; p-data=k; cout修改后的单链表显示如下:endl; show(l); void hebing() int a,b; linklist la,lb,lc; cout请输入第一个有序链表的长度:a; cout请输入第一个有序链表的元素共（a个）：endl; createlist(la,a); show(la)

9、; cout请输入第二个有序链表的长度:b; cout请输入第二个有序链表的元素共（b个）：endl; createlist(lb,b); show (lb); mergelist(la,lb,lc); cout合并后的有序链表如下：endl; show(lc);int main() int select; int x; elemtype y; linklist list; for(;) cout 单链表的基本操作endl; cout 1.单链表的创建endl; cout 2.单链表的显示endl; cout 3.单链表的长度endl; cout 4.取第i个位置的元素endl; cout 5

10、.修改第i个位置的元素endl; cout 6.插入元素到单链表里endl; cout 7.删除单链表里的元素endl; cout 8.合并两个单链表endl; cout 9.退出系统endl; coutselect; switch(select) case 1:cout请输入单链表的长度:x; cout请输入x个元素endl; createlist(list,x); break; case 2: cout单链表显示如下:endl; show(list); break; case 3: int s; cout单链表的长度为:length(list,s)endl; break; case 4:

11、coutx; while(xlength(list,s) cout输入有误，请重新输入endl; coutx; getelem(list,x,y); cout该位置的元素为:yendl; break; case 5: xiugai(list); break; case 6: coutx; while(xlength(list,s) cout输入有误，请重新输入endl; coutx; couty; linkinsert( list,x,y); cout插入后单链表显示如下:endl; show(list); break; case 7: coutx; while(xlength(list,s) cout输入有误，请重新输入endl; coutx; listdelete(list,x,y); cout要删除的元素值:yendl; cout删除后的单链表显示如下:endl; show(list); break; case 8: hebing