数据结构的课件实验二线性表的链式表示和实现

实验二 线性表的链式表示和实现实验内容 1.单向链表的存储结构C语言中的单向链表存储结构描述： 单向链表的存储结构typedef struct LNode ElemType data; /* 存放结点中的数据信息*/ Struct Lnode *next; /*指向下一个结点地址的指针*/ LNode, *LinkList; /* LinkList 即struct LNode *类型*/2.单向链表的基本操作（1）初始化操作：为链表设置一个头结点，头结点的data数据域不赋任何值，头结点的指针域next则为空。（2）销毁操作：将链表中包括头结点在内的所有结点依次全部删除，结点所占空间释放给系统。（3）清空操作：将链表的指针域next设为空。（4）求链表中元素的个数操作：从链表的第一个结点开始计算出链表中结点的个数。（5）输出操作：依次输出L 中的每一个数据元素的值。（6）定位操作：查找数据值与给定值e相同的第一个结点，并将结点在链表中的为序值返回，若链表中不存在该结点，则返回0。（7）插入操作：在第i个结点前插入新的结点。首先要找到指定的位置，然后定义一个新的结点，最后将结点插入到指定位置。（8）删除操作：删除链表中第i个结点。首先要找到指定的位置，即用指针p定位到一个结点，然后指针q指向p的后一个结点，接着将p指向的结点与q后一个结点相连，最后将q指向的结点删除。3.链表操作实现的操作步骤（1）实现将链表的存储结构和基本操作程序代码。（2）实现main主函数。4.程序代码完整清单#include #include typedef char ElemType;typedef struct LNode/*定义单链表结点类型*/ElemType data; struct LNode *next; LinkList;/基本操作函数声明 void InitList(LinkList *&L); /*初始化链表*/ void DestroyList(LinkList *&L); /*销毁链表*/ int ListEmpty(LinkList *L); /*清空链表*/ int ListLength(LinkList *L); /*求链表长度*/ void DispList(LinkList *L); /*输出链表*/ int GetElem(LinkList *L,int i,ElemType &e); /*取链表中元素*/ int LocateElem(LinkList *L,ElemType e); /*定位链表中元素*/ int ListInsert(LinkList *&L,int i,ElemType e); /*链表中插入元素*/ int ListDelete(LinkList *&L,int i,ElemType &e); /*删除链表中元素*/void main()LinkList *h;ElemType e;printf(1)初始化单链表hn);InitList(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:);DispList(h);printf(4)单链表h长度=%dn,ListLength(h);printf(5)单链表h为%sn,(ListEmpty(h)?空:非空);GetElem(h,3,e);printf(6)单链表h的第3个元素=%cn,e);printf(7)元素a的位置=%dn,LocateElem(h,a);printf(8)在第4个元素位置上插入f元素n);ListInsert(h,4,f);printf(9)输出单链表h:);DispList(h);printf(10)删除h的第3个元素n); ListDelete(h,3,e);printf(11)输出单链表h:);DispList(h);printf(12)释放单链表hn);DestroyList(h);void InitList(LinkList *&L) /*初始化链表 操作结果：构造一个空的线性表*/L=(LinkList *)malloc(sizeof(LinkList); /*创建头结点*/L-next=NULL;void DestroyList(LinkList *&L) /*释放链表 操作结果：销毁线性表L*/LinkList *p=L,*q=p-next;while (q!=NULL)free(p);p=q;q=p-next;free(p);int ListEmpty(LinkList *L) /*清空链表 操作结果：将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;while (p!=NULL)printf(%c,p-data);p=p-next;printf(n);int GetElem(LinkList *L,int i,ElemType &e) /*取表中元素 操作结果：用e返回L */ /*中的第 i个元素的值*/int j=0;LinkList *p=L;while (jnext;if (p=NULL)return 0;elsee=p-data;return 1;int LocateElem(LinkList *L,ElemType e) /*定位表中元素 操作结果：返回L中第1个*/ /* 与e相等的元素位序*/LinkList *p=L-next;int n=1;while (p!=NULL & p-data!=e)p=p-next;n+;if (p=NULL)return(0);elsereturn(n);int ListInsert(LinkList *&L,int i,ElemType e) /*向表中插入元素 操作结果：在带头结点的*/ /*单链线性表L中第i个位置之前插入e*/int j=0;LinkList *p=L,*s;while (jnext;if (p=NULL)/*未找到第i-1个结点*/return 0;else/*找到第i-1个结点*p*/s=(LinkList *)malloc(sizeof(LinkList);/*创建新结点*s*/s-data=e;s-next=p-next;/*将*s插入到*p之后*/p-next=s;return 1;int ListDelete(LinkList *&L,int i,ElemType &e) /*将表中元素删除 操作结果：在L 中删除*/ /*第i个结点，如果i越界或空表，返回0；*/ int j=0; /*否则，返回1，并将删除的元素值用e带*/LinkList *p=L,*q; /*回到上级函数*/while (jnext;if (p=NULL)/*未找到第i-1个结点*/return 0;else/*找到第i-1个结点*p*/q=p-next;/*q指向要删除的结点*/p-next=q-next;/*从单链表中删除*q结点*/free(q);/*释放*q结点*/return 1;5. 运行结果清单(1