数据结构单链表实验报告

洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期11.7实验名称链表的基本操作成绩实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，VisualC++6.0实验内容：1.问题描述以单链表为存储结构实现以下基本操作：(1)在第i个元素前插入一个新元素。(2)查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提示信息。(3)删除第i个元素，若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息。2.数据结构类型定义typedefstructLinkNode{intValue;structLinkNode*Next;}Node,*LinkList;3.模块划分（1）初始化链表：voidInitList(LinkList*L);（2）创建链表:尾插法：intCreateFromTail(LinkListL);（3）在指定位置插入元素：intInsList(LinkListL,inti,inte);（4）在指定位置删除元素：intDelList(LinkListL,inti,int*e);返回值说明：返回ERROR插入失败，返回OK插入成功;（5）按位置查找链表元素：intGetList(LinkListL,inti,int*e);4.详细设计voidinit_linklist(LinkList*l)/*对单链表进行初始化*/{*l=(LinkList)malloc(sizeof(Node));/*申请结点空间*/(*l)-next=NULL;/*置为空表*/}voidCreateFromHead(LinkListL){Node*s;charc;intflag=1;while(flag)/*flag初值为1，当输入$时，置flag为0，建表结束*/{c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node));/*建立新结点s*/s-data=c;s-next=L-next;/*将s结点插入表头*/L-next=s;}elseflag=0;}}voidCreateFromTail(LinkListL){Node*r,*s;charc;intflag=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;}else{flag=0;r-next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/}}}Node*Get(LinkListL,inti)/*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置;否则返回NULL*/{intj;Node*p;p=L;j=0;/*从头结点开始扫描*/while((p-next!=NULL)&&(ji)){p=p-next;/*扫描下一结点*/j++;/*已扫描结点计数器*/}if(i==j)returnp;/*找到了第i个结点*/elsereturnNULL;/*找不到，i≤0或in*/}Node*Locate(LinkListL,ElemTypekey)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/{Node*p;p=L-next;/*从表中第一个结点开始*/while(p!=NULL){if(p-data!=key)p=p-next;elsebreak;/*找到结点值=key时退出循环*/}returnp;}intInsList(LinkListL,inti,ElemTypee)/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/{Node*pre,*s;intk;pre=L;k=0;/*从头开始，查找第i-1个结点*/while(pre!=NULL&&ki-1)/*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/{pre=pre-next;k=k+1;}/*查找第i-1结点*/if(!pre)/*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/{printf(插入位置不合理!);returnERROR;}s=(Node*)malloc(sizeof(Node));/*申请一个新的结点S*/s-data=e;/*值e置入s的数据域*/s-next=pre-next;/*修改指针，完成插入操作*/pre-next=s;returnOK;}intDelList(LinkListL,inti,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/{Node*pre,*r;intk;pre=L;k=0;while(pre-next!=NULL&&ki-1)/*寻找被删除结点i的前驱结点i-1使p指向它*/{pre=pre-next;k=k+1;}/*查找第i-1个结点*/if(!(pre-next))/*即while循环是因为p-next=NULL或i1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/{printf(删除结点的位置i不合理!);returnERROR;}r=pre-next;pre-next=pre-next-next;/*修改指针，删除结点r*/*e=r-data;free(r);/*释放被删除的结点所占的内存空间*/printf(成功删除结点!);returnOK;}intListLength(LinkListL)/*求带头结点的单链表L的长度*/{Node*p;intj;p=L-next;j=0;/*用来存放单链表的长度*/while(p!=NULL){p=p-next;j++;}returnj;/*j为求得的单链表长度*/}5.测试数据及结果实验总结：在调试的时候发现在头插法的时候出现错误，经过逻辑思考与调试，发现错误所在，并且更改。