实现单链表地各种基本运算.docx

实用标准文案实现单链表的各种基本运算一、实验目的了解单链表表的结构特点及有关概念，掌握单链表的各种基本操作算法思想及其实现二、实验内容编写一个程序，实现顺序表的各种基本运算：1、初始化单链表； 2、单链表的插入；3、单链表的输出； 4、求单链表的长度5、判断单链表是否为空； 6、输出单链表的第 i 位置的元素 ；7、在单链表中查找一个给定元素在表中的位置；8、单链表的删除； 9、释放单链表三、算法思想与算法描述简图文档大全主函数 mainvoid InitList(LinkList*&L) 初始化单链表Lvoid DestroyList(LinkList*&L)//释放单链表Lint ListEmpty(LinkList*L)//判断单链表 L 是否为空集int Listlength(LinkList*L)//返回单链表L 的元素个数void DispList(LinkListt*L)//输出单链表 Lint GetElem(LinkList*L,int i,char e)/*ElemType e) 获取单链表 L 中的第 i 个元素*/int LocateEmpty(LinkList*L,char e)/*ElemType e) 在单链表 L 中查找元素 e*/int ListInsert(LinkList*&L,int i,char e)/*ElemType e)在单链表中第 i 个位置上插入元素e*/int ListDelete(LinkList*&L,int i,char &e)/*ElemTypee)在单链表 L 中删除第i 个元素*/实用标准文案文档大全实用标准文案四、实验步骤与算法实现#include #include typedef char ElemType;typedef struct LNode//定义单链表{ ElemType data; struct LNode *next;}LinkList;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)//判线性表是否为空表 ListEmpty(L)假。

{ return(L->next==NULL);}//若单链表 L 没有数据结点,则返回真,否则返回int ListLength(LinkList*L)//求线性表的长度 ListLength(L){ LinkList*p=L;int i=0; while(p->next!=NULL)文档大全实用标准文案{i++;p=p->next;}return(i);//返回单链表 L 中数据结点的个数}void DispList(LinkList*L)//输出线性表 DispList(L){LinkList*p=L->next;值while (p!=NULL)//逐一扫描单链表 L 的每个数据结点,并显示各结点的 data 域{printf("%c",p->data); p=p->next;}printf("\n");}据元素 GetElem(L,i,&e)int GetELem(LinkList*L,int i,ElemType&e)//求线性表 L 中指定位置的某个数{int j=0; LinkList*p=L;个数据结点,则将其 data 域值赋给变量 ewhile(jnext;} if(p==NULL)return 0;//不存在第 i 个数据结点else{e=p->data;//存在第 i 个数据结点return 1;}文档大全实用标准文案}int LocateElem(LinkList*L,ElemType e)//按元素值查找 LocateElem(L,e){LinkList *p=L->next; int n=1;的结点,若存在这样的结点,则返回位置,否则返回 0。

while (p!=NULL&&p->data!=e)//在单链表 L 中从头开始找第 1 个值域与 e 相等{p=p->next; n++;} if(p=NULL) return (0); elsereturn (n);}ListInsert(&L,i,e)e)// 插 入 数 据 元 素int ListInsert(LinkList*&L,int i,ElemType{int j=0; LinkList*p=L,*s;点,将值为 e 的结点*s 插入到其后while(jnext;} if(p==NULL)return 0;//未找到位序为 i-1 的结点else{s=(LinkList*)malloc(sizeof(LinkList)); s->data=e;s->next=p->next;//将*s 插入到*p 之后文档大全实用标准文案p->next=s; return 1;}}ListDelete(&L,i,&e)int ListDelete(LinkList*&L,int i,ElemType &e)// 删 除 数 据 元 素{int j=0; LinkList*p=L,*q;while(jnext;}if(p==NULL)//未找到位序为 i-1 的结点return 0;else//找到位序为 i-1 的结点*p{q=p->next;//q 指向要删除的结点if(q==NULL)return 0;//若不存在第 i 个结点,返回 0 e=q->data;p->next=q->next;//从单链表中删除*q 结点free(q);//释放*q 结点return 1;}}void main(){LinkList *h; ElemType e;printf("(1)初始化单链表 h\n"); 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,'kkkk');printf("(3)输出单链表 h:"); DispList(h);printf("(4)单链表 h 长度=%d\n",ListLength(h)); printf("(5)单链表 h 为%s\n",(ListEmpty(h)?"空":"非空")); GetELem(h,3,e);printf("(6)单链表 h 的第三个元素=%c\n",e); printf("(7)元素 a 的位置=%d\n",LocateElem(h,'a')); printf("(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)释放单链表 h\n"); DestroyList(h);}文档大全实用标准文案五、实验测试及结果六、思考题1、 单链表有带头结点和不带头结点两种形式，则相应的操作实现有何区别?答：在带头节点的单链表中，头指针(head)只有一个域，即链指针，它指向头结点，头结点有两个域，一个是数据域，值为 0（NULL），还有一个域，链指针，这个链指针指向单链表的第一个数据元素。

而在不带头结点的单链表中， 头指针也只有一个链指针，但它指向单链表的第一个数据元素2、单向循环链表、双向链表、双向循环链表基本操作的实现答：（1）单向循环链表循环链表的基本运算实现算法与非循环链表的算法基本相同，只是对表尾的判断作了改变因此单向循环链表与单链表基本上操作相同，只不过表尾的条件将发生变化2）双向链表基本操作实现文档大全实用标准文案双链表中有两个指针域，一个指向其直接后继结点，另一个指向其直接前驱结点建立双链表有头插法和尾插法1】头插法:Void CreateListF(DLinkList *&L,ElemType a[],int n)//由含有 n 个元素的数组 a 创建带头结点的双链表 L{DLinkList *s;int i;L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL;for(i=0;idata=a[i];s->next=L->next;if(L->next!=NULL)L->next=L->prior=s; L->next=s;s->prior=L;}}【2】尾插法Void CreateListF(DLinkList *&L,ElemType a[],int n)//由含有 n 个元素的数组 a 创建带头结点的双链表 L{DLinkList *s,*r;int I;L=(DLinkList *)malloc(sizeof(DLinkList)); L->prior=L->next=NULL;r=L;//r 始终指向尾结点，开始时指向头结点for(i=0;i