单链表的定义与基本操作.pdf

《单链表的定义与基本操作.pdf》由会员分享，可在线阅读，更多相关《单链表的定义与基本操作.pdf（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、.单链表的定义及基本操作单链表的定义及基本操作一、实验目的、意义一、实验目的、意义（1）理解线性表中带头结点单链表的定义和逻辑图表示方法。（2）熟练掌握单链表的插入，删除和查询算法的设计与实现。（3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。二、实验内容及要求二、实验内容及要求说明说明 1 1：本次实验中的链表结构均为带头结点的单链表。说明说明 2:2:学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：具体要求：建立单

2、链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。三、实验所涉及的知识点三、实验所涉及的知识点数据结构、数据结构、C C 语言语法函数、结构体类型指针、单链表（建表、初始语言语法函数、结构体类型指针、单链表（建表、初始化链表、求表长、插入、删除、查询算法）等。化链表、求表长、插入、删除、查询算法）等。四、实验结果及分析四、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）.下载可编辑.五、总结与体会五、总结与体会（调试程序的心得与体会，若

3、实验课上未完成调试，要认真找出错误并分析原因等。）调试程序时，出现了许多错误。如：结构体类型指针出错，忽略了释调试程序时，出现了许多错误。如：结构体类型指针出错，忽略了释放存储空间，对头插法建表、尾插法建表不熟悉等。另外还有一些语放存储空间，对头插法建表、尾插法建表不熟悉等。另外还有一些语法上的错误。由于对所学知识点概念模糊，试验课上未能完成此次上法上的错误。由于对所学知识点概念模糊，试验课上未能完成此次上机作业。后来经过查阅教材，浏览网页等方式，才完成试验。这次试机作业。后来经过查阅教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码验出现错误

4、最重要的原因就是对课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，以完善自己的不足。时的粗心。以后要都去练习、实践，以完善自己的不足。六、程序清单六、程序清单(包含注释)/单链表#include#include#define OK 1.下载可编辑.#define ERROR 0typedef char ElemType;typedef int Status;/线性表的单链表的存储结构typedef struct LNodeElemType data;struct LNode*next;LNode,*LinkList;/LinkList 为结构体类型的指针，可以直接定义变量，比如

5、LinkList p；/建表（头插法）void CreatListF(LinkList&L,ElemType a,int n)/建表（尾插法）void CreatListR(LinkList&L,ElemType a,int n).下载可编辑./初始化线性表L=(LinkList)malloc(sizeof(LNode);/分配内存空间L-next=NULL;/在表中插入元素LinkList S;int i;/头插法for(i=0;idata=ai;/数据域S-next=L-next;L-next=S;.L=(LinkList)malloc(sizeof(LNode);L-next=NULL;

6、LinkList p;p=L;LinkList S;int i;/尾插法for(i=0;inext=NULL;S=(LinkList)malloc(sizeof(LNode);S-data=ai;p-next=S;p=S;/初始化线性表void InitList(LinkList&L)/获得链表元素Status GetElem(LinkList L,int i,ElemType&e)/L 为带头结点的单链表的头指针LinkList p;int j;/初始化，p 指向第一个结点p=L-next;/j 为计数器L=(LinkList)malloc(sizeof(LNode);L-next=NULL

7、;.下载可编辑.j=1;/顺指针往后查找，直到p 指向第 i 个元素或 p 为空while(p&ji)return ERROR;p=p-next;j+;/取第 i 个元素e=p-data;return OK;/插入Status ListInsert(LinkList&L,int i,ElemType e)int j=0;LinkList p;p=L;while(p!=NULL&ji-1)return ERROR;p=p-next;j+;LinkList S;S=(LinkList)malloc(sizeof(LNode);/生成新结点S-data=e;S-next=p-next;.下载可编辑.

8、p-next=S;return OK;/删除Status ListDelete(LinkList&L,int i,ElemType&e)LinkList p;LinkList q;int j=0;p=L;while(p-next)!=NULL&jnext;j+;/!(p-next)：指向第 i 个结点的指针为空（第i 个元素不存在）/求表的长度int ListLength(LinkList L)LinkList p;p=L;int j=0;/线性链表最后一个结点的指针为空if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data

9、;free(q);return OK;.下载可编辑.while(p-next)!=NULL)return j;j+;p=p-next;/输出void visit(LinkList L)/销毁:要销毁的话从头结点开始依次free 但要先得到下一个节点再freevoid DestroyList(LinkList&L)LinkList p;LinkList q;p=L;q=p-next;while(p!=NULL)free(p);p=q;q=p-next;LinkList p;p=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;.下载可编辑./free

10、(p);/判空int ListEmpty(LinkList L)/查找int ListSearch(LinkList L,ElemType e)int main()ElemType e;ElemType a6=a,b,c,d,e,f;LinkList L;/链表的头指针printf(头插法建表：);CreatListF(L,a,6);LinkList p;p=L-next;int i=1;while(p!=NULL&p-data!=e)if(p=NULL)return 0;p=p-next;i+;/为空表则执行该语句，否则返回return 0；return(L-next=NULL);retur

11、n i;.下载可编辑.visit(L);printf(nn);/初始化 InitList(L);printf(尾插法建表：);CreatListR(L,a,6);printf(初始化后的表：);visit(L);printf(nn);visit(L);.下载可编辑.printf(nn);/初始化后表为空，此时不要调用GetElem()GetElem(L,3,e);printf(表中第 3 个元素为：);printf(%cnn,e);/在第 5 个位置插入字符kListInsert(L,5,k);printf(在表中第 5 个位置插入字符k后：);visit(L);printf(nn);printf(表的长度为:%dnn,ListLength(L);int z;z=ListSearch(L,d);printf(d 是第%d 个元素nn,z);.ListDelete(L,2,e);printf(删除第 2 个元素：%cnn,e);/销毁/DestroyList(L);return 0;.下载可编辑.