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

实现单链表的各种基本运算一、实验目的了解单链表表的结构特点及有关概念，掌握单链表的各种基本操作算法思想及其实现。二、实验内容编写一个程序，实现顺序表的各种基本运算： 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)/*ElemType e)在单链表L中删除第i个元素*/四、实验步骤与算法实现#include#includetypedef 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);int GetELem(LinkList*L,int i,ElemType&e)/求线性表L中指定位置的某个数据元素GetElem(L,i,&e)int j=0;LinkList*p=L;while(jnext;if(p=NULL)return 0;/不存在第i个数据结点elsee=p-data;/存在第i个数据结点return 1;int LocateElem(LinkList*L,ElemType e)/按元素值查找LocateElem(L,e)LinkList *p=L-next;int n=1;while (p!=NULL&p-data!=e)/在单链表L中从头开始找第1个值域与e相等的结点,若存在这样的结点,则返回位置,否则返回0。p=p-next;n+;if(p=NULL)return (0);else return (n);int ListInsert(LinkList*&L,int i,ElemType e)/插入数据元素ListInsert(&L,i,e)int j=0;LinkList*p=L,*s;while(jnext;if(p=NULL)return 0;/未找到位序为i-1的结点elses=(LinkList*)malloc(sizeof(LinkList);s-data=e;s-next=p-next;/将*s插入到*p之后p-next=s;return 1;int ListDelete(LinkList*&L,int i,ElemType &e)/删除数据元素ListDelete(&L,i,&e)int j=0;LinkList*p=L,*q;while(jnext;if(p=NULL)/未找到位序为i-1的结点return 0;else/找到位序为i-1的结点*pq=p-next;/q指向要删除的结点if(q=NULL)return 0;/若不存在第i个结点,返回0e=q-data;p-next=q-next;/从单链表中删除*q结点free(q);/释放*q结点return 1;void main()LinkList *h;ElemType e;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,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(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、单链表有带头结点和不带头结点两种形式，则相应的操作实现有何区别?答：在带头节点的单链表中，头指针(head)只有一个域，即链指针，它指向头结点，头结点有两个域，一个是数据域，值为0（NULL），还有一个域，链指针，这个链指针指向单链表的第一个数据元素。 而在不带头结点的单链表中，头指针也只有一个链指针，但它指向单链表的第一个数据元素。2、单向循环链表、双向链表、双向循环链表基本操作的实现。答：（1）单向循环链表循环链表的基本运算实现算法与非循环链表的算法基本相同，只是对表尾的判断作了改变。因此单向循环链表与单链表基本上操作相同，只不过表尾的条件将发生变化。（2）双向链表基本操作实现双链表中有两个指针域，一个指向其直接后继结点，另一个指向其直接前驱结点。建立双链表有头插法和尾插法。【1】 头插法:Void CreateListF(DLinkList *&L,ElemType a,int n)/由含有n个元素的数组a创建带头结点的双链表LDLinkList *s;int i;L=(DLinkList *)malloc(sizeof(DLinkList);L-prior=L-next=NULL;for(i=0;idata=ai;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创建带头结点的双链表LDLinkList *s,*r;int I;L=(DLinkList *)malloc(sizeof(DLinkList);L-prior=L-next=NULL;r=L;/r始终指向尾结点，开始时指向头结点for(i=0;idata=ai;r-next=s;s-prior=r;r=s;r-next=NULL;在双链表中，大部分基本操作运算与单链表相同，除插入与删除有所区别。【插入】int ListInsert(DLinkList *&L,int I,ElemType e)int j=0;DLinkList *p=L,*s;/p指向头结点While(jnext;if(p=NULL)/未找到逻辑位序位i-1的结点return 0;else /找到逻辑位序为i-1的结点*ps=(DLinkList *)malloc(sizeof(DLinkList)/创建结点*s;s-data=e;s-next=p-next;/将*s插入到*p之后if(p-next!=NULL)p-next-prior=s;s-prior=p;p-next=s;return 1;【删除】int ListDelete(DLinkList *&L,int I,ElemType &e)DLinkList *p=L,*q; /p指向头结点int j=0;while (jnext;if(p=NULL)return 0;else q=p-next;if(q=NULL)return 0;e=q-data;p-next=q-next;/从单链表中删除*q结点if (p-next!=NULL)p-next-prior=p;free(q);/释放*p结点return 1;（2）双向循环链表实现：插入操作 (在p 所指结点之前插入q 结点的过程 )Status ListInsert_Dl(DLinkList &L, int i, ElemType x)/在带头结点的双向循环链表L中第i个位置之前插入元素x, i的合法值为1i表长+1 if (!(p = GetElemP_Dul(L, i) /在中确定第i个元素的位置指针p return ERROR; if (!(q = (DuLNode)malloc(sizeof(DuLNode) return ERROR; q-data = x; q-prior = p-prior; p-prior-next = q; q-next = p; p-prior = q; return OK;删除操作算法 (删除p所