1、实验二链表的基本操作实验报告实验名称链表的基本操作及应用实验日期2019.10.09实验成绩1、实验目的： 1掌握线性表的链式存储结构的表示和实现方法。2掌握单链表基本操作的算法实现。3了解单链表的应用。2、实验内容： 1.编写一个程序，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个主程序完成如下功能：（1）初始化单链表h；（2）依次采用尾插法插入a、b、c、d、e元素；（3）输出单链表h；（4）输出单链表h的长度；（5）判断单链表h是否为空；（6）输出单链表h的第3个元素；（7）输出元素a的位置（8）在第4个元素位置上插入f元素（9）输出单链表h；（10）删
2、除h的第3个元素；（11）输出单链表h；（12）释放单链表h。3、核心算法或代码片段：核心算法：1 链表建立操作的基本步骤：链表是一个动态的结构，它不需要分配空间，因此建立链表的过程是一个结点“逐个插入” 的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。2 链表查找操作的基本步骤：因链表是一种顺序存取的结构，则要在带头结点的链表中查找到第 i个元素，必须从头结点开始沿着后继指针依次点数，直到点到第 i 个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。3 链表插入操作的基本步骤：先确定要
3、插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。4 链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。单链表的存储结构描述如下：typedef struct LNode /定义单链表结点类型 ElemType data; struct LNode *next; LinkList;初始化链表：void InitList(LinkList *&L) L=(LinkList *)malloc(sizeof(LinkList); /创建头结点 L-next=NULL;销毁线性表：vo
4、id DestroyList(LinkList *&L) /销毁线性表 LinkList *p=L,*q=p-next; while (q!=NULL) free(p); p=q; q=p-next; free(p);判断是否为空表：bool ListEmpty(LinkList *L) /判线性表是否为空表 return(L-next=NULL);求线性表长度：int ListLength(LinkList *L) /求线性表的长度 LinkList *p=L;int i=0; while (p-next!=NULL) i+; p=p-next; return(i);输出线性表：void D
5、ispList(LinkList *L) /输出线性表 LinkList *p=L-next; while (p!=NULL) printf(%c ,p-data); p=p-next; printf(n);求线性表某个数据元素值：bool GetElem(LinkList *L,int i,ElemType &e) /求线性表中某个数据元素值 int j=0; LinkList *p=L; /p指向头节点,j置为0(即头节点的序号为0) while (jnext; if (p=NULL) /不存在第i个数据节点,返回0 return false; else /存在第i个数据节点,返回1 e=
6、p-data; return true; 按元素值查找：int LocateElem(LinkList *L,ElemType e) /按元素值查找 int i=1; LinkList *p=L-next; /p指向开始节点,i置为1(即开始节点的序号为1) while (p!=NULL & p-data!=e) /查找data值为e的节点,其序号为i p=p-next; i+; if (p=NULL) /不存在元素值为e的节点,返回0 return(0); else /存在元素值为e的节点,返回其逻辑序号i return(i);链表的插入：bool ListInsert(LinkList *
7、&L,int i,ElemType e) /插入数据元素 int j=0; LinkList *p=L,*s; /p指向头节点,j置为0(即头节点的序号为0) while (jnext; if (p=NULL) /未找到第i-1个节点,返回false return false; else /找到第i-1个节点*p,插入新节点并返回1 s=(LinkList *)malloc(sizeof(LinkList); s-data=e; /创建新节点*s,其data域置为e s-next=p-next; /将*s插入到*p之后 p-next=s; return true; 线性表的删除：bool Li
8、stDelete(LinkList *&L,int i,ElemType &e) /删除数据元素 int j=0; LinkList *p=L,*q; /p指向头节点,j置为0(即头节点的序号为0) while (jnext; if (p=NULL) /未找到第i-1个节点,返回false return false; else /找到第i-1个节点*p q=p-next; /q指向第i个节点 if (q=NULL) /若不存在第i个节点,返回false return false; e=q-data; p-next=q-next; /从单链表中删除*q节点 free(q); /释放*q节点 re
9、turn true; /返回true表示成功删除第i个节点 代码：#include #include typedef char ElemType;#define Maxsize 50typedef struct LNode /定义单链表结点类型 ElemType data; struct LNode *next;LinkList;void InitList(LinkList *&L) /初始化单链表 L=(LinkList *)malloc(sizeof(LinkList); /创建头结点 L-next=NULL;void DestroyList(LinkList *L) /销毁单链表 Lin
10、kList *p=L,*q=L-next; while(q!=NULL) free(p); p=q; q=p-next; free(p);bool ListEmpty(LinkList *L) /判断单链表是否为空 return (L-next=NULL);int ListLength(LinkList *L) /求单链表的长度 LinkList *p=L; int i=0; while(p-next!=NULL) i+; p=p-next; return (i);void DispList(LinkList *L) /输出单链表 LinkList *p=L-next; / int i=0;
11、while(p-next!=NULL) printf(%c ,p-data); p=p-next; printf(%c ,p-data); printf(n);bool GetElem(LinkList *L,int i,ElemType &e) /求单链表中某个元数的值 LinkList *p=L; int j=0; while(p!=NULL&jnext; if(p=NULL) return false; else e=p-data; return true; int LocateElem (LinkList *L,ElemType e) /按元素值查找 LinkList *p=L; in
12、t j=0; while(p!=NULL&p-data=e) j+; p=p-next; if(p=NULL) return 0; else return (j+1); bool ListInsert(LinkList *L,int i,ElemType e) /插入数据元素 LinkList *p=L,*s; int j=0; while(p!=NULL&jnext; if(p=NULL) return false; else s=(LinkList *)malloc(sizeof(LinkList); s-data=e; s-next=p-next; p-next=s; return tr
13、ue; bool ListDelete(LinkList *L,int i,ElemType &e) LinkList *p=L,*s; int j=0; while(p!=NULL&jnext; if(p=NULL) return false; else s=p-next; if(s=NULL) return false; e=s-data; p-next=s-next; free(s); return true; int main() LinkList *h; ElemType e; printf(单链表的基本运算如下：n) ; printf(1)初始化单链表h：n); InitList(
14、h); printf(2)依此采用尾插法插入a,b,c,d,e元素：n); ListInsert(h,1,a); ListInsert(h,2,b); ListInsert(h,3,c); ListInsert(h,4,d); ListInsert(h,5,e); printf(3)输出单链表h：n); DispList(h); printf(4)单链表h长度为：n); printf(%dn,ListLength(h); printf(5)单链表h为%sn,(ListEmpty(h)?空:非空); GetElem(h,3,e); printf(6)单链表h的第3个元素是：n); printf(
15、%cn,e); printf(7)元素a的位置：n); printf(%dn,LocateElem(h,a); printf(8)在第四个元素位置上插入f元素：n); ListInsert(h,4,f); printf(9)输出单链表h:); DispList(h); printf(10)删除h的第3个元素：n); ListDelete(h,3,e); printf(11)输出单链表h：n); DispList(h); printf(12)释放单链表h：); DestroyList(h);4、实验结果分析及总结体会：实验结果：对单链表h InitList()创建头结点并初始化L-next=NU
16、LL;利用尾插法ListInsert()依次插入a,b,c,d,e。即改变最后一个结点的next域指向新插入的数据。输出单链表DispList()和输出单链表的长度ListLength(),需要对于判断每一个结点的next域直到next域等于NULL，单链表是否为空ListEmpty()对头结点的(L-next)域判断是否为null。确定某一个位置的数据GetElem()时，同样也要考虑结点的next域,在没有达到i值但p-next=null,则返回错误。在单链表中间的某一个位置插入数据ListInsert()时对指针的改变要注意,要先将被插入结点的指针指向他后面位置的结点然后将前面的结点的next域指向被插入结点，否则后面的数据会发生丢失。再删除数据时ListDelete()只需要对指针进行改变，最后释放内存DestroyList();总结体会：通过本次实验掌握了线性表的链式存储结构的表示和实现方法，还学会了单链表基本操作的算法实现。同时还了解单链表的应用，理解了单链表的用途，同时并能通过单链表解决一些简单问题，但同时也发现了自己的不足，基础不足，还需多练习。
