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

计算机学院实验报告课程名称： 数据结构 实验名称： 单链表 学生姓名： 朱孝彬 学生学号： 20110511001 实验日期： 2012 一、实验目的1理解数据结构中带头结点单链表的定义和逻辑图表示方法。2掌握单链表中结点结构的C+描述。3熟练掌握单链表的插入、删除和查询算法的设计与C+实现。二、实验内容1 编制一个演示单链表插入、删除、查找等操作的程序。三、实验步骤1需求分析本演示程序用C+6.0编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成单链表的生成（通过插入操作）、插入、删除、查找操作。 测试数据：A 插入操作中依次输入11，12，13，14，15，16，生成一个单链表B 查找操作中依次输入12，15，22返回这3个元素在单链表中的位置C 删除操作中依次输入2，5，删除位于2和5的元素2概要设计1）为了实现上述程序功能，需要定义单链表的抽象数据类型： （1）insert 初始化状态：单链表可以不为空集；操作结果：插入一个空的单链表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#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; 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-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=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,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); 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.修改第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: 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(); break; case 9: exit(0); break; default : cout输入有误，请重新输入endl; break; 6 测试结果 四、实验总结（结果分析和体会）单链表的最后一个元素的next为null ,所以, 一旦遍历到末尾结点就不能再重新开始;而循环链表的最后一个元素的next为第一个元素地址,可返回头结点进行重新遍历和查找。10