单链表地定义及基本操作

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

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

3、，浏览网页等方式，才完成试验。这次试 验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码 时的粗心。以后要都去练习、实践，以完善自己的不足。六、程序清单（包含注释）/单链表#in clude<stdio.h>#in clude<malloc.h> #defi ne OK 1文档大全#defi ne ERROR 0 typedef char ElemType;typedef int Status;/线性表的单链表的存储结构typedef struct LNodeElemType data;struct LNode *n ext;LinkList p ；LNode

4、,*Li nkList;/LinkList为结构体类型的指针，可以直接定义变量，比如建表(头插法)void CreatListF(Li nkList & L,ElemType a,i nt n)/初始化线性表L=(Li nkList)malloc(sizeof(LNode);分配存空间L-> next=NULL;/在表中插入元素Lin kList S;int i;/头插法for(i=0;i< n;i+)S=(L in kList)malloc(sizeof(LNode);/ 生成新结点S->data=ai; 数据域S->n ext=L->n ext;L-&

5、gt;n ext=S;建表(尾插法)void CreatListR(L in kList & L,ElemType a,i nt n)L=(L in kList)malloc(sizeof(LNode);L-> next=NULL;Lin kList p;p=L;Lin kList S;int i;/尾插法for(i=0;i< n;i+)S=(L in kList)malloc(sizeof(LNode);S->data=ai;p_>n ext=S;P=S;p-> next=NULL;/初始化线性表void In itList(L in kList &am

6、p;L)L=(L in kList)malloc(sizeof(LNode);L-> next=NULL;II获得链表元素Status GetElem(L in kList L,i nt i,ElemType &e)IIL为带头结点的单链表的头指针Lin kList p;int j;II初始化，p指向第一个结点p=L->n ext;IIj为计数器文档大全j=1;顺指针往后查找，直到p指向第i个元素或p为空while(p && j<i)p=p->n ext;j+；/第i个元素不存在if(!p II j>i)return ERROR;取第i个元

7、素e=p_>data;return OK;/插入Status List In sert(L in kList &L,i nt i,ElemType e)int j=0;Lin kList p;p=L;while(p!=NULL && j<i-1)找第 i-1 个结点p=p->n ext;j+;if(!p | j>i-1)return ERROR;Lin kList S;S=(Li nkList)malloc(sizeof(LNode); 生成新结点S->data=e;S->n ext=p->n ext;文档大全p->n e

8、xt=S;return OK;删除Status ListDelete(LinkList &L,int i,ElemType &e)Lin kList p;Lin kList q;int j=0;p=L;while(p->next)!=NULL && j<i-1)找第 i 个结点p=p->n ext;j+;!(p->next):指向第i个结点的指针为空(第i个元素不存在)if(!(p-> next) | j>i-1)return ERROR;q=p->n ext;p_>n ext=q _>n ext;e=q_&

9、gt;data;free(q);return OK;求表的长度int ListLe ngth(L in kList L)Lin kList p;p=L;int j=0;线性链表最后一个结点的指针为空文档大全while(p-> next)!=NULL)j+；p=p->n ext;return 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销毁:要销毁的话从头结点开始依次free但要先得到下一个节点

10、再void DestroyList(LinkList &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 ；/为空表则执行该语句，否则返回return (L-> next=NULL);/查找int ListSearch(L in kList L,ElemType e)Lin kList p;p=L->n ext;int i=1;while(p!=NULL &am

11、p;& p->data!=e)p=p->n ext;i+; if(p=NULL)return 0;return i;int mai n()ElemType e;ElemType a 6='a','b','c','d','e','f;LinkList L;链表的头指针printf("头插法建表：");CreatListF(L,a,6);文档大全visit(L);prin tf("nn");/初始化In itList(L);printf("初

12、始化后的表：");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个位置插入字符'k'ListI nsert(L,5,'k');printf("在表中第5个位置插入字符'k'后：”)；visit(L);prin tf(&quo