单链表定义及基本操作.doc

单链表的定义及基本操作 一、实验目的、意义（1）理解线性表中带头结点单链表的定义和逻辑图表示方法。（2）熟练掌握单链表的插入，删除和查询算法的设计与实现。（3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。二、实验内容及要求说明1：本次实验中的链表结构均为带头结点的单链表。说明2: 学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：建立单链表，完成链表（带表头结点）的基本操作：建立链表、插入、删除、查找、输出；其它基本操作还有销毁链表、将链表置为空表、求链表的长度、获取某位置结点的内容、搜索结点。三、实验所涉及的知识点数据结构、C语言语法函数、结构体类型指针、单链表（建表、初始化链表、求表长、插入、删除、查询算法）等。四、实验结果及分析（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 五、总结与体会（调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。）调试程序时，出现了许多错误。如：结构体类型指针出错，忽略了释放存储空间，对头插法建表、尾插法建表不熟悉等。另外还有一些语法上的错误。由于对所学知识点概念模糊，试验课上未能完成此次上机作业。后来经过查阅教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，以完善自己的不足。六、程序清单(包含注释)/单链表#include#include#define OK 1#define ERROR 0typedef char ElemType;typedef int Status;/线性表的单链表的存储结构typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/LinkList为结构体类型的指针，可以直接定义变量，比如LinkList p；/建表（头插法）void CreatListF(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;/建表（尾插法）void CreatListR(LinkList &L,ElemType a,int n)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;LinkList p;p=L;LinkList S;int i;/尾插法for(i=0;idata=ai;p-next=S;p=S;p-next=NULL;/初始化线性表void InitList(LinkList &L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/获得链表元素Status GetElem(LinkList L,int i,ElemType &e)/L为带头结点的单链表的头指针LinkList p;int j;/初始化，p指向第一个结点p=L-next;/j为计数器j=1;/顺指针往后查找，直到p指向第i个元素或p为空while(p & jnext;j+;/第i个元素不存在if(!p | ji)return ERROR;/取第i个元素e=p-data;return OK;/插入Status ListInsert(LinkList &L,int i,ElemType e)int j=0;LinkList p;p=L;while(p!=NULL & jnext;j+;if(!p | ji-1)return ERROR;LinkList S;S=(LinkList)malloc(sizeof(LNode);/生成新结点S-data=e;S-next=p-next;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个元素不存在）if(!(p-next) | ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;/求表的长度int ListLength(LinkList L)LinkList p;p=L;int j=0;/线性链表最后一个结点的指针为空while(p-next)!=NULL)j+;p=p-next;return j;/输出void visit(LinkList L)LinkList p;p=L-next;while(p!=NULL)printf(%c ,p-data);p=p-next;/销毁:要销毁的话从头结点开始依次free 但要先得到下一个节点再freevoid DestroyList(LinkList &L)LinkList p;LinkList q;p=L;q=p-next;while(p!=NULL)free(p);p=q;q=p-next;/free(p);/判空int ListEmpty(LinkList L)/为空表则执行该语句，否则返回return 0；return (L-next=NULL);/查找int ListSearch(LinkList L,ElemType e)LinkList p;p=L-next;int i=1;while(p!=NULL & p-data!=e)p=p-next;i+;if(p=NULL)return 0;return i;int main()ElemType e;ElemType a6=a,b,c,d,e,f;LinkList L;/链表的头指针printf(头插法建表：);CreatListF(L,a,6);visit(L);printf(nn);/初始化 InitList(L);printf(初始化后的表：);visit(L);printf(nn);printf(尾插法建表：);CreatListR(L,a,6); 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;