实现单链表的各种基本运算

1、实现单链表的各种基本运算一、实验目的了解单链表表的结构特点及有关概念，掌握单链表的各种基本操作算法思想及其实现。二、实验内容编写一个程序，实现顺序表的各种基本运算：1、初始化单链表；2、单链表的插入；3、单链表的输出；4、求单链表的长度5、判断单链表是否为空；6、输出单链表的第i位置的元素；7、在单链表中查找一个给定元素在表中的位置；8、单链表的删除；9、释放单链表三、算法思想与算法描述简图四、实验步骤与算法实现#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructLNode/定义单链表E

2、lemTypedata;structLNode*next;LinkList;创建头结点voidInitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/L->next=NULL;/头结点赋值为空销毁单链表（释放单链表L占用的内存空间voidDestroyList(LinkList*&L)/即逐一释放全部结点的空间)LinkList*p=L,*q=p->next;while(q!=NULL)free(p);p=q;q=p->next;free(p);intListEmpty(LinkList*L)/判线

3、性表是否为空表ListEmpty(L)return(L->next=NULL);/若单链表L没有数据结点，则返回真，否则返回假。intListLength(LinkList*L)/求线性表的长度ListLength(L)LinkList*p=L;inti=0;while(p->next!=NULL)i+;p=p->next;)return(i);/|返回单链表L中数据结点的个数)voidDispList(LinkList*L)/输出线性表DispList(L)LinkList*p=L->next;while(p!=NULL)/逐一扫描单链表L的每个数据结点，并显示各结点

4、的data域值。printf("%c”,p->data);p=p->next;)printf("n");)intGetELem(LinkList*L,inti,ElemType&e)/|求线性表L中指定位置的某个数据元素GetElem(L,i,&e)intj=0;LinkList*p=L;while(j<i&&p!=NULL)/1在单链表L中从头开始找到第i个结点，若存在第i个数据结点，则将其data域值赋2&变量e。j+;p=p->next;)if(p=NULL)return0;/不存在第i个数据结

5、点elsee=p->data;/存在第i个数据结点return1;)intLocateElem(LinkList*L,ElemTypee)/按元素值查找LocateElem(L,e)LinkList*p=L->next;intn=1;while(p!=NULL&&p->data!=e)|在单链表L中从头开始找第1个值域与e相等的结点，若存在这样的结点，则返回位置，否则返回00p=p->next;n+;)if(p=NULL)return(0);elsereturn(n);)intListInsert(LinkList*&L,inti,ElemTyp

6、ee)*插入数据元素ListInsert(&L,i,e)intj=0;LinkList*p=L,*s;while(j<i-1&&p!=NULL)/先在单链表L中找到第i-1个结点*p,若存在这样的结点，将值为e的结点*s插入到其后。j+;p=p->next;)if(p=NULL)return0;/|未找到位序为i-1的结点elses=(LinkList*)malloczeof(LinkList);s->data=e;s->next=p->next;/*将*s插入到之后p->next=s;return1;)intListDelete(L

7、inkList*&L,inti,ElemType&e)/|删除数据元素ListDelete(&L,i,&e)intj=0;LinkList*p=L,*q;while(j<i-1&&p!=NULL)查找第i-1个结点j+;p=p->next;if(p=NULL)d未找到位序为i-1的结点return0;else/1找到位序为i-1的结点*pq=p->next;/q|指向要删除的结点if(q=NULL)return0;/|若不存在第i个结点，返回e=q->data;p->next=q->next;/|从单链表中删除

8、*q结点free(q);/|释放*q结点return1;voidmain()LinkList*h;ElemTypee;printf("(1)初始化单链表hn");InitList(h);printf("(2)依次采用尾插入abcd,efgh,jilk,nnnn,kkkk元素n");ListInsert(h,1,'abcd');ListInsert(h,2,'efgh');ListInsert(h,3,'jilk');ListInsert(h,4,'nnnn');ListInsert(h,5,

9、'kkkk');printf("(3)输出单链表h:");DispList(h);printf("(4)单链表h长度=%dn",ListLength(h);printf("(5)单链表h为sn",(ListEmpty(h)?"空":"非空");GetELem(h,3,e);printf("(6)单链表h的第三个元素=%cn",e);printf("(7)元素a的位置=%dn",LocateElem(h,'a');printf

10、("(8)在第四个元素的位置上插入9元素n");ListInsert(h,4,'9');printf("(9)输出单链表h:");DispList(h);printf("(10)删除h的第三个元素n");ListDelete(h,3,e);printf("(11)输出单链表h:");DispList(h);printf("(12)释放单链表hn");DestroyList(h);五、实验测试及结果六、思考题1、单链表有带头结点和不带头结点两种形式，则相应的操作实现有何区别？答：在

11、带头节点的单链表中，头指针（head）只有一个域，即链指针，它指向头结点，头结点有两个域，一个是数据域，值为0（NULL,还有一个域，链指针，这个链指针指向单链表的第一个数据元素。而在不带头结点的单链表中，头指针也只有一个链指针，但它指向单链表的第一个数据元素。2、单向循环链表、双向链表、双向循环链表基本操作的实现。答：（1）单向循环链表循环链表的基本运算实现算法与非循环链表的算法基本相同，只是对表尾的判断作了改变。因此单向循环链表与单链表基本上操作相同，只不过表尾的条件将发生变化。（2）双向链表基本操作实现双链表中有两个指针域，一个指向其直接后继结点，另一个指向其直接前驱结点。建立双链表有头

12、插法和尾插法。【1】头插法：VoidCreateListF(DLinkList*&L,ElemTypea,intn)/由含有n个元素的数组a创建带头结点的双链表LDLinkList*s;inti;L=(DLinkList*)malloc(sizeof(DLinkList);L->prior=L->next=NULL;for(i=0;i<n;i+)s=(DLinkList*)malloc(sizeof(DLinkList);s->data=ai;s->next=L->next;if(L->next!=NULL)L->next=L->p

13、rior=s;L->next=s;s->prior=L;【2】尾插法VoidCreateListF(DLinkList*&L,ElemTypea,intn)/由含有n个元素的数组a创建带头结点的双链表LDLinkList*s,*r;intI;L=(DLinkList*)malloc(sizeof(DLinkList);L->prior=L->next=NULL;r=L;/r始终指向尾结点，开始时指向头结点for(i=0;i<n;i+)s=(DLinkList*)malloc(sizeof(DLinkList);s->data=ai;r->nex

14、t=s;s->prior=r;r=s;r->next=NULL;在双链表中，大部分基本操作运算与单链表相同，除插入与删除有所区别。【插入】intListInsert(DLinkList*&L,intI,ElemTypee)intj=0;DLinkList*p=L,*s;/p(指向头结点While(j<i-1&&p!=NULL)/查找第i-1个结点j+;p=p->next;if(p=NULL)/|未找到逻辑位序位i-1的结点return0;else/|找到逻辑位序为i-1的结点*ps=(DLinkList*)malloczeof(DLinkList

15、)/创建结点*s;s->data=e;s->next=p->next;/|将*s插入到*p之后if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return1;【删除】intListDelete(DLinkList*&L,intI,ElemType&e)DLinkList*p=L,*q;/p指向头结点intj=0;while(j<i-1&&p!=NULL)查找第i-1个结点j+;p=p->next;if(p=NULL)return0;elseq

16、=p->next;if(q=NULL)return0;e=q->data;p->next=q->next;/从单链表中删除*q结点if(p->next!=NULL)p->next->prior=p;free(q);/|释放*p结点return1;(2)双向循环链表实现：插入操作(在p所指结点之前插入q结点的过程)StatusListInsert_Dl(DLinkList&L,inti,ElemTypex)/在带头结点的向循环链表L中第i个位置之前插入元素x,i的合法值为1&i0表长+1if(!(p=GetElemP_Dul(L,i)/在L中确定第i个元素的位置指针preturnERROR;if(!(q=(DuLNode)malloc(sizeof(DuLNode)returnERROR;q->data=x;q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q;returnOK;)删除操作算法(删