数据结构单链表实验报告

1、洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期11。7实验名称链表的基本操作成绩实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法,训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台,Visual C+6.0实验内容：1. 问题描述以单链表为存储结构实现以下基本操作：(1) 在第i个元素前插入一个新元素。(2) 查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提示信息。(3) 删除第i个元素,若成功，给出提示信息并显示被删元素的值;不成功给出失败的提示信息。2. 数据结构类型定义typedef struct LinkN

2、odeint 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

3、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

4、;s->next=Lnext；/将s结点插入表头/L-next=s;elseflag=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);s-data=c；r-next=s；r=s;elsefl

5、ag=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）&（j<i） p=p>next; /* 扫描下一结点*/j+； /* 已扫描结点计数器 /if(i = j）return p； / 找到了第i个结点 /else return NULL; / 找不到,i0或

6、i>n / Node Locate（ LinkList L,ElemType key)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/ Node p;p=L-next; /从表中第一个结点开始 /while (p！=NULL）if （pdata！=key）p=p>next； else break; /找到结点值=key时退出循环 /return p； int InsList(LinkList L，int i，ElemType e)/在带头结点的单链表L中第i个位置插入值为e的新结点s/ Node pre，s；int k;pre

7、=L； k=0； /*从"头”开始，查找第i1个结点/while（pre！=NULL&&ki1） /表未查完且未查到第i1个时重复,找到pre指向第i1个/ pre=pre->next；k=k+1； /*查找第i1结点/if（！pre） /如当前位置pre为空表已找完还未数到第i个,说明插入位置不合理/ printf（”插入位置不合理!"）;return ERROR；s=(Node）malloc(sizeof(Node）； /*申请一个新的结点S /sdata=e; /值e置入s的数据域/s->next=pre>next;/*修改指针,完成

8、插入操作/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（pre-next！=NULL && ki1)/*寻找被删除结点i的前驱结点i1使p指向它*/ pre=pre>next； k=k+1；/查找第i1个结点/if(！（pre->next） / 即while循环是因为pnext=NULL或i<1而跳出的，而是因为没有找到合法的前驱位置，说明删除位置i不合法./printf（”删除结点的位置i不合理!”）;return ERROR；r=prenext;pre-next=prenextnext； /修改指针，删除结点r*/*e = r-data;free（r)； /*释放被删除的结点所占的内存空间/printf("成功删除结点!"）；return OK；intListLength（LinkList L)/求带头结点的单链表L的长度/ Node p；int