单链表的定义及基本操作

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

2、操作还有销毁链表、将链表置为空表、求链表的长度、 获取某位置结点的内容、搜索结点。三、实验所涉及的知识点数据结构、C语言语法函数、结构体类型指针、单链表（建表、初始化链表、 求表长、插入、删除、查询算法）等。四、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采 用截图方式给出。）五、总结与体会（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分 析原因等。）调试程序时，出现了许多错误。如：结构体类型指针出错，忽略了释放存 储空间，对头插法建表、尾插法建表不熟悉等。另外还有一些语法上的错误。 由于对所学知识点概念模糊，试验课上未能完成此次上机作业。后来经

3、过查阅 教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对 课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，以完 善自己的不足。六、程序清单（包含注释）/单链表#i nclude#i nclude#define OK 1#defi ne ERROR 0typedef char ElemType;typedef int Status;/线性表的单链表的存储结构typedef struct LNodeElemType data;struct LNode *n ext;LNode,*L in kList;/LinkList为结构体类型的指针，可以直接定义变量，比如L

4、inkList p;/建表（头插法）void CreatListF（L in kList & L,ElemType a,i nt n）/初始化线性表L=(Li nkList)malloc(sizeof(LNode);/分配内存空间L- next二NULL;/在表中插入元素Lin kList S;int i;/头插法for(i=0;i data=ai;/ 数据域S-n ext=L- n ext;L-n ext=S;/建表(尾插法)void CreatListR(L in kList & L,ElemType a,i nt n)L=(Li nkList)malloc(sizeof(LNode);L

5、- next二NULL;Lin kList p;P=L；Lin kList S;int i;/尾插法for(i=0;i data二ai;p-n ext=S;P=S;p- next二NULL;/初始化线性表void In itList(L in kList &L)L=(Li nkList)malloc(sizeof(LNode);L- next二NULL;/获得链表元素Status GetElem(Li nkList L,i nt i,ElemType &e)L为带头结点的单链表的头指针Lin kList p;int j；/初始化，p指向第一个结点p=L-n ext;j为计数器j=1；顺指针往后

6、查找，直到p指向第i个元素或p为空while(p & jn ext;j+；/第i个元素不存在if(!p II ji)retur n ERROR;/取第i个元素e=p-data;retur n OK;5 / 12宀 kfo una) -sJLxeucd -i-rx ucdJLx UASQdepcS艰糅荒封_( PON_I)4O Nsoo_euJasnMunlls-s -snMuntzo 山 un05 (LA 二-di)七+-i-rx UAdud next)!二NULL & jn ext;j+;i个元素不存在）!(p-next):指向第i个结点的指针为空(第if(!(p- next) | ji-1

7、)retur n ERROR;q=p-n ext;p-n ext=q-n ext;e二q-data;free(q);retur n OK;/求表的长度13 / 12int ListLe ngth(Li nkList L) Lin kList p;P=L;int j=0;/线性链表最后一个结点的指针为空while(p- next)!二NULL)j+;p=p-n ext;retur n j;/输出void visit(L in kList L)Lin kList p;p=L-n ext;while(p!=NULL)prin tf(%c ”,p-data);p=p-n ext;free/销毁要销毁的

8、话从头结点开始依次free但要先得到下一个节点再void DestroyList(L in kList &L)Lin kList p;Lin kList q;P=L;q=p-n ext;while(p!二NULL)free(p);p=q;q=p-n ext;/ free(p);/判空int ListEmpty(L in kList L)/为空表则执行该语句，否则返回return 0 ;retur n (L- next=NULL);/查找int ListSearch(Li nkList L,ElemType e)Lin kList p;p=L-n ext;int i=1;while(p!二NUL

9、L & p-data!=e)p=p-n ext;i+;if(p=NULL)return 0;retur n i;int mai n()ElemType e;ElemType a 6=a,b,c,d,e,f;Lin kList L;链表的头指针printf(头插法建表：”)；CreatListF(L,a,6);visit(L);prin tf(nn ”)；/初始化Ini tList(L);printf(初始化后的表：”)；visit(L);prin tf(nn ”)；printf(尾插法建表：”)；CreatListR(L,a,6);visit(L);prin tf(nn ”)；GetElem()/初始化后表为空，此时不要调用GetElem(L,3,e);printf(表中第3个元素为：”)； prin tf(%c nn,e);/在第5个位置插入字符kListI nsert(L,5,k);printf（在表中第5个位置插入字符k后：”）;visit(L);prin tf(nn ”)；p