数据结构单链表实验报告

洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期

11.7实验名称链表的基本操作成绩实验目的熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力实验条件计算机一台，Visual C++600实验内容

1.问题描述以单链表为存储结构实现以下基本操作1在第i个元素前插入一个新元素2查找值为x的某个元素.若成功，给出x在表中的位置；不成功给出提示信息3删除第i个元素，若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息

2.数据结构类型定义typedef struct LinkNode{int Value;structLinkNode*Next；}Node,*LinkList;

3.模块划分1初始化链表void InitListLinkList*L；2创建链表尾插法int CreateFromTailLinkList L;3在指定位置插入元素int InsListLinkList L,int i,int e；4在指定位置删除元素int DclListLinkList L,int i,int*c；返回值说明返回ERROR插入失败，返回OK插入成功；5按位置查找链表元素int GetListLinkList L,int i,int*e;

4.详细设计void init_linklistLinkList*1/*对单链表进行初始化*/{*1=LinkList mallocsizeof Node；/*申请结点空间*/*1—next=NULL；/*置为空表*/}void CreateFromHeadLinkList LNode*s；char c；int flag=l;whileflag/*flag初值为1,当输入$〃时，置flag为0,建表结束*/{c=getchar;ifc!=${s二Node*mallocsizeof Node;/*建立新结点s*/s一〉data=c;s一〉next=L一next；/*将s结点插入表头*/L-next=s;}else flag=0；}void CreateFromTai1LinkList LNode*r,*s；char c;int flag=1；/*设置一个标志，初值为1,当输入$”时，flag为0,建表结束*/r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while flag/大循环输入表中元素值，将建立新结点s插入表尾*/{c=getchar；if c!=$s=Nodemalloc sizeofNode；s一〉data=c;r-next=s;r=s；elseflag=0；r-〉next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/}}Node*Get LinkList L,int i/*在带头结点的单链表L中查找第i个结点，若找到IWiWn,则返回该结点的存储位置；否则返回NULL*/int j；Node*p;P=L；j=o；/*从头结点开始扫描*/whilep-next!=NULLj〈iP=p-next;/*扫描下一结点*/j++；/*已扫描结点计数器大/}ifi==j return p;/*找到了第i个结点*/elsereturn NULL;/*找不到，iWO或in*/}Node*LocateLinkList L,ElemType key/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置P，否则返回NULL*/Node*p；P=L一〉next；/*从表中第一个结点开始*/while p!=NULL{if p-data!=key p=p―〉next;else break；/*找到结点值二key时退出循环*/}returnp；}int InsListLinkList L,int i,ElemType e/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/Node*pre,*s；int k；pre=L；k=0/*从”头”开始，查找第i—1个结;点*/while pre!=NULLk i-1/*表未查完且未查到第iT个时重复，找到pre指向第iT个*/pre=pre一〉next；k=k+l；}/*查找第i—1结点*/if!pre/*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/{printf插入位置不合理！”；return ERROR；}s=Node*malloc sizeofNode；/*申请一个新的结点S*/s-data=e；/*值e置入s的数据域*/s-next=pre一〉next；/*修改指针，完成插入操作*/pre―〉next=s；return OK；int DelListLinkListL,int i,ElemType*e/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中文/Node*pre,*r;int k;pre二L;k=0；whilepre-next!=NULLki-1/*寻找被删除结点i的前驱结点i-1使p指向它*/{pre=pre—〉next；k=k+l；}/*查找第i—1个结点*/if!pre-next/*即while循环是因为p一〉next=NULL或i〈l而跳出的，而是因为没有找到合法的前驱位置，说明删除位置i不合法*/printf〃删除结点的位置i不合理！〃;return ERROR；}r=pre-next；pre一next=pre-next-next;/*修改指针，删除结点r*/*e=r-data；freer;/*释放被删除的结点所占的内存空间*/printf成功删除结点！”；return OK；int ListLengthLinkListL/*求带头结点的单链表L的长度*/Node*p；int j；p=L-next；j=0;/*用来存放单链表的长度*/whilep!=NULL{p=p-next;j++;}return j;/*j为求得的单链表长度*/}

5.测试数据及结果实验总结在调试的时候发现在头插法的时候出现错误，经过逻辑思考与调试，发现错误所在，并且更改.。