单链表定义及基本操作

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

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

3、教材，浏览网页等方式，才完成试验。这次试 验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码 时的粗心。以后要都去练习、实践，以完善自己的不足。六、程序清单（包含注释）/单链表# iiiclude# mclude#define OK 1 #define ERROR 0 tvpedef char ElemTvpe; tvpedef mt Status;线性表的单链表的存储结构tvpedef stmct LNodeElemTvpe data;stmct LNode *next;JLNode, *LnikList;/LuikList为结构体类型的指针，可以直接定义变量，比如LuikList

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

5、kList S;int i;尾插法for(i=O;idata=ai;p-next=S;P=S；p-next=NULL;初始化线性表void InitList(LnikList &L)L=(LuikList)malloc(sizeof(LNode);L-next=NULL;获得链表元素Status GetElem(LinkList Ljnt i,ElemType &e)/L为带头结点的单链表的头指针LinkList p;mt j;初始化，p指向第一个结点p=L-next;/j为计数器J=l;顺指针往后查找，直到P指向第1个元素或P为空while(p & jnext;J卄；第1个元素不存在讽!P

6、II ji)retimi ERROR;取第1个元素e=p-data;return OK;插入Status ListInsert(LuikList &L.int i.ElemTvpe e)mt 尸 0;LinkList p;P=L；wlule(p!=NULL & jnext;j卄；if(!p |ji-l)return ERROR:LinkList S;S=(LuikList)malloc(sizeof(LNode);/ 生成新结点S-data=e;S-next=p-next;p-next=S;return OK;删除Status ListDelete(LuikList &L,int i.Elem

7、Type &e)LinkList p;LinkList q;mt 尸 0;P=L；while(p-next) ? =NULL & jnext;j卄；/!(p-next):指向第i个结点的指针为空(第1个元素不存在)if(!(p-next) |ji-l)return ERROR:q=p-next;p-next=q-next;e=q-data;fiee(q);return OK;求表的长度mt ListLength(LinkList L)LinkList p;P=L；mt 尸 0;线性链表最后一个结点的指针为空while(p-next)! =NULL)J卄;p=p-next;return j;输出

8、void visit(LinkList L)LinkList p;p=L-next;while(p!=NULL)printf(n%c *p-data);p=p-next;销毁:要销毁的话从头结点开始依次free但要先得到下一个节点再freevoid DestioyList(LinkList &L)LinkList p;LinkList q;P=L；q=p-next;while(p!=NULL)p=q;q=p-next;/ fiee(p);判空7 / 9mt ListEmpty(LuikList L)为空表则执行该语句，否则返回leturn 0： return (L-next=NULL);查找m

9、t ListSearch(LinkList L.ElemType e)LinkList p;p=L-next;int i=l;while(p!=NULL & p-data!=e)p=p-next;i+;if(p=NULL)return 0;return i;mt mam()ElemTvpe e;ElemTvpe a6=ta,：b7c,；d,；e,f ;LinkList L;/表的头指针pmHff头插法建表：”);CieatListF(L,a,6);visit(L);/初始化IiutList(L);printf(初始化后的表：”)；visit(L);pnntfC，nnM);putf(”尾插法建表：”)；CreatListR(L,a.6);visit(L);pnntfC，nnM);初始化后表为空，此时不要调用GetElemQGetElem(L,3,e);pmitf(”表中第3个元素为：”)；在第5个位置插入字符疋ListInsert(L,5 /k*);prmtf(”在表中第5个位置插入字符X后：”); visit(L);pnntfC，nn