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

1、实现单链表的各种基本运算一、实验目的了解单链表表的结构特点及有关概念，掌握单链表的各种基本操作算法思想及其实现。二、实验内容编写一个程序，实现顺序表的各种基本运算：1 、初始化单链表；2、单链表的插入；3、单链表的输出；4、求单链表的长度5、判断单链表是否为空；6、输出单链表的第i位置 的元素；7、在单链表中查找一个给定元素在表中的位置；8、单链表的删除；9、释放单链表三、算法思想与算法描述简图void InitList(LinkList*&L)初始化单链表 LLJvoid DestroyList(LinkList*&L)释放单链表 LkJint ListEmpty(Li nk

2、List*L)/判断单链表L是否为空集int Listle ngth(Li nkList*L)/返回单链表L的元素个数Jvoid DispList(L in kListt*L)/输出单链表Lint GetElem(Li nkList*L,i nt i,char e)/*ElemType e)获取单链表L中的第i个元素*/Jrint LocateEmpty(L in kList*L,char e)/*ElemType e)在单链表L中查找元素e*/JrFint ListInsert(LinkList*&L,inti,char e)/*ElemType e)在单链表中第i个位置上插入元素e

3、*/,intListDelete(Li nkList*&L,i nti,char& e)/*ElemTypeL)在单链表L中删除第i个元素*/J四、实验步骤与算法实现#i nclude<stdio.h>#i nclude<malloc.h> typedef char ElemType;定义单链表typedef struct LNode/ ElemType data;struct LNode *n ext;Li nkList;void In itList(Li nkList* &L) L=(Li nkList*)malloc(sizeof(Li n

4、kList);/创建头结点L->next=NULL;头结点赋值为空void DestroyList(LinkList*&L)销毁单链表(释放单链表 L占用的内存空间即逐一释放全部结点的空间)Lin kList*p=L,*q=p->n ext;while(q!=NULL)free(p);p=q;q=p->n ext; free(p);判线性表是否为空表ListEmpty(L)int ListEmpty(Li nkList*L)/return(L-> next=NULL);若单链表L没有数据结点，则返回真,否则返回求线性表的长度ListLength(L)假。int

5、ListLe ngth(Li nkList*L)/LinkList*p=L;int i=0;while(p-> next!=NULL)i+；p=p->n ext;return(i);/ |返回单链表L中数据结点的个数void DispList(LinkList*L)输出线性表 DispList(L)Li nkList*p=L-> next;while (p!=NULL) 逐一扫描单链表L的每个数据结点，并显示各结点的data域 值。pri ntf("%c",p->data);p=p->n ext;prin tf("n");i

6、nt GetELem(LinkList*L,inti,ElemType&e) | 求线性表 L 中指定位置的某个数据元素 GetElem(L,i,&e)int j=0;Lin kList*p=L;while(j<i&&p!=NULL) |在单链表L中从头开始找到第i个结点，若存在第i 个数据结点,则将其data域值赋给变量e。j+;p=p->n ext;if(p=NULL)return 0;/不存在第i个数据结点elsee=p->data;/ 存在第i个数据结点return 1;int LocateElem(LinkList*L,ElemTyp

7、e e)按元素值查找 LocateElem(L,e)Li nkList *p=L-> next;int n=1;while (p!=NULL&&p->data!=e) |在单链表L中从头开始找第1个值域与e相等 的结点，若存在这样的结点，则返回位置，否则返回0。p=p->n ext;n+;if(p=NULL)return (0);elsereturn (n);intListInsert(LinkList*&L,inti,ElemTypee)/| 插入数据元素List In sert(&L,i,e)int j=0;Lin kList*p=L,*s

8、;while(j<i-1 &&p!=NULL)先在单链表L中找到第i-1个结点*p,若存在这样的结点,将值为e的结点*s插入到其后。j+;p=p->n ext;if(p=NULL)return 0;/ 未找到位序为i-1的结点elses=(Li nkList*)malloc(sizeof(L in kList);s->data=e;s->next=p->next;/眉将*s插入到*p之后p->n ext=s;return 1; intListDelete(LinkList*&L,inti,ElemType&e)删除数据元素Li

9、stDelete(&L,i,&e)int j=0;Lin kList*p=L,*q;while(j<i-1 &&p!=NULL)查找第 i-1 个结点j+;p=p->n ext;if(p=NULL)/|未找到位序为i-1的结点 return 0;else/|找到位序为i-1的结点*pq=p->next;/ql指向要删除的结点if(q=NULL)return 0;/ |若不存在第i个结点,返回e=q->data;p->next=q->next;/ 从单链表中删除*q结点free(q);/ 释放 *q 结点return 1;voi

10、d mai n()Lin kList *h;ElemType e;printf("(1)初始化单链表hn");In itList(h);printf("(2)依次采用尾插入 abcd,efgh,jilk,nnnn,kkkk元素n");List In sert(h,1,'abcd');Listl nsert(h,2,'efgh');List In sert(h,3,'jilk');Listl nsert(h,4,' nnnn');Listl nsert(h,5,'kkkk');

11、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("(

12、8)在第四个元素的位置上插入9元素n");ListI nsert(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、 单链表有带头结点和不带头结点两种形式，则相应的操作实 现有何区别？答：在带头

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

14、链表有头插法和尾插法。【1】头插法：Void CreateListF(DLinkList *&L,ElemType a,int n)/由含有n个元素的数组a创建带头结点的双链表LDLinkList *s;int i;L=(DLi nkList *)malloc(sizeof(DLi nkList);L->prior=L- >n ext=NULL;for(i=0;i <n ;i+)s=(DLi nkList *)malloc(sizeof(DLi nkList);s->data=ai;s->n ext=L->n ext;if(L->n ext!=

15、NULL)L->n ext=L->prior=s;L->n ext=s;s->prior=L;【2】尾插法Void CreateListF(DLinkList *&L,ElemType a,int n)/由含有n个元素的数组a创建带头结点的双链表LDLi nkList *s,*r;i nt I;L=(DLi nkList *)malloc(sizeof(DLi nkList);L->prior=L- >n ext=NULL;r=L;/r始终指向尾结点，开始时指向头结点for(i=0;i <n ;i+)s=(DLi nkList *)malloc

16、(sizeof(DLi nkList);s->data=ai;r->n ext=s;s->prior=r;r=s;r->n ext=NULL;在双链表中，大部分基本操作运算与单链表相同，除插入与删除有所区别。【插入】int ListInsert(DLinkList *&L,int l,ElemType e)int j=0;DLinkList *p=L,*s;/p(指向头结点While(j<i-1 &&p!=NULL)/查找第 i-1 个结点j+;p=p->n ext;if(p=NULL)/ |未找到逻辑位序位i-1的结点return

17、0;else /匚找到逻辑位序为i-1的结点*ps=(DLinkList *)malloc(sizeof(DLinkList)/创建结点 *s;s->data=e;s->next=p->next;/ 将 *s 插入到 *p 之后if(p->n ext!=NULL)p->n ext->prior=s; s->prior=p;p->n ext=s;return 1;【删除】int ListDelete(DLinkList *&L,int l,ElemType &e)DLinkList *p=L,*q;/p 指向头结点int j=0;w

18、hile (j<i-1 &&p!=NULL) / 查找第 i-1 个结点j+;p=p->n ext;if(p=NULL)return 0;elseq=p->n ext;if(q=NULL)return 0;e=q->data;p->next=q->next;/从单链表中删除*q结点if (p->n ext!=NULL)p->n ext->prior=p;free(q);/ 释放 *p 结点return 1;(2)双向循环链表实现:插入操作(在p所指结点之前插入q结点的过程)Status Listl nsert_DI(DL in kList & L, i nt i, ElemType x)/在带头结点的双向循环链表L中第i个位置之前插入元素x, i的合 法值为K i w表长+1if (!(p = GetElemP_Dul(L, i) /在L中确定第i个元素的位置指针preturn ERROR;if (!(q = (DuLNode)malloc(sizeof(DuLNode) return ERROR; q->data = x;q->n ext = p; return OK;p->prio