数据结构单链表实验报告.doc

洛阳理工学院洛阳理工学院实验报告实验报告 系别 计算机系 班级 学号 姓名 课程名称 数据结构 实验日期 11。7 实验名称 链表的基本操作 成绩 实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法,训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，Visual C+6.0 实验内容：1.问题描述 以单链表为存储结构实现以下基本操作:(1)在第 i 个元素前插入一个新元素。(2)查找值为 x 的某个元素。若成功，给出 x 在表中的位置；不成功给出提示信息。(3)删除第 i 个元素,若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息。2.数据结构类型定义 typedef struct LinkNode int Value;struct LinkNode*Next;Node，LinkList；3.模块划分（1）初始化链表:void InitList(LinkList*L)；（2）创建链表：尾插法:int CreateFromTail(LinkList L);(3）在指定位置插入元素：int InsList（LinkList L，int i,int e)；(4)在指定位置删除元素：int DelList（LinkList L，int i，int e）;返回值说明：返回 ERROR 插入失败,返回 OK 插入成功；（5）按位置查找链表元素:int GetList（LinkList L,int i,int e）;4.详细设计 void init_linklist（LinkList l）/对单链表进行初始化*/l=（LinkList)malloc(sizeof（Node）；/申请结点空间*/(l）next=NULL；/*置为空表*/void CreateFromHead（LinkList L)Node s；char c；int flag=1；while(flag）/flag 初值为 1，当输入$时，置 flag 为 0,建表结束/c=getchar(）;if（c！=)s=（Node)malloc(sizeof(Node）；/*建立新结点 s/sdata=c；s-next=Lnext;/将 s 结点插入表头/Lnext=s；else flag=0；void CreateFromTail(LinkList L）Node r，s;char c；int flag=1;/设置一个标志，初值为 1，当输入时，flag 为 0,建表结束/r=L;/*r 指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点/while（flag)/*循环输入表中元素值，将建立新结点 s 插入表尾/c=getchar(）；if(c！=）s=（Node）malloc（sizeof（Node）；sdata=c；rnext=s；r=s;else flag=0；r-next=NULL;/将最后一个结点的 next 链域置为空，表示链表的结束*/Node Get（LinkList L，int i)/*在带头结点的单链表 L 中查找第 i 个结点，若找到（1in)，则返回该结点的存储位置；否则返回 NULL*/int j；Node p;p=L;j=0；/*从头结点开始扫描/while（(p-next!=NULL)&（ji)p=pnext；/扫描下一结点/j+；/已扫描结点计数器/if（i=j）return p；/*找到了第 i 个结点/else return NULL；/*找不到,i0 或 in/Node*Locate（LinkList L，ElemType key）/*在带头结点的单链表 L 中查找其结点值等于 key 的结点，若找到则返回该结点的位置 p，否则返回 NULL*/Node p;p=Lnext;/从表中第一个结点开始/while(p！=NULL)if（pdata！=key)p=pnext；else break;/找到结点值=key 时退出循环/return p；int InsList（LinkList L，int i，ElemType e）/在带头结点的单链表 L 中第 i 个位置插入值为 e 的新结点 s*/Node pre,*s;int k；pre=L；k=0；/从头开始，查找第 i-1 个结点/while(pre！=NULLkdata=e；/*值 e 置入 s 的数据域*/snext=pre-next;/修改指针，完成插入操作*/pre-next=s；return OK；int DelList（LinkList L,int i，ElemType e）/在带头结点的单链表 L 中删除第 i 个元素，并将删除的元素保存到变量e中*/Node*pre,r；int k；pre=L；k=0;while(prenext！=NULL&ki-1）/寻找被删除结点 i 的前驱结点 i1 使 p 指向它*/pre=prenext；k=k+1;/查找第 i1 个结点/if(！（prenext)）/即 while 循环是因为 p-next=NULL 或 i1而跳出的，而是因为没有找到合法的前驱位置，说明删除位置 i 不合法./printf（删除结点的位置 i 不合理!”）；return ERROR；r=prenext；prenext=prenextnext；/修改指针，删除结点 r/e=r-data;free(r)；/释放被删除的结点所占的内存空间/printf（成功删除结点!”）；return OK；int ListLength（LinkList L)/求带头结点的单链表 L 的长度/Node*p；int j;p=Lnext；j=0；/*用来存放单链表的长度/while(p！=NULL）p=pnext；j+；return j；/*j 为求得的单链表长度/5。测试数据及结果 实验总结：在调试的时候发现在头插法的时候出现错误，经过逻辑思考与调试,发现错误所在，并且更改.