實現(xiàn)單鏈表的各種基本運算

1、實現(xiàn)單鏈表的各種基本運算一、實驗?zāi)康牧私鈫捂湵肀淼慕Y(jié)構(gòu)特點及有關(guān)概念，掌握單鏈表的各種基本操作算法思想及其實現(xiàn)。二、實驗內(nèi)容編寫一個程序，實現(xiàn)順序表的各種基本運算：1、初始化單鏈表；2、單鏈表的插入；3、單鏈表的輸出；4、求單鏈表的長度5、判斷單鏈表是否為空；6、輸出單鏈表的第i位置的元素；7、在單鏈表中查找一個給定元素在表中的位置；8、單鏈表的刪除；9、釋放單鏈表三、算法思想與算法描述簡圖四、實驗步驟與算法實現(xiàn)#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructLNode/定義單鏈表E

2、lemTypedata;structLNode*next;LinkList;創(chuàng)建頭結(jié)點voidInitList(LinkList*&L)L=(LinkList*)malloc(sizeof(LinkList);/L->next=NULL;/頭結(jié)點賦值為空銷毀單鏈表（釋放單鏈表L占用的內(nèi)存空間voidDestroyList(LinkList*&L)/即逐一釋放全部結(jié)點的空間)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沒有數(shù)據(jù)結(jié)點，則返回真，否則返回假。intListLength(LinkList*L)/求線性表的長度ListLength(L)LinkList*p=L;inti=0;while(p->next!=NULL)i+;p=p->next;)return(i);/|返回單鏈表L中數(shù)據(jù)結(jié)點的個數(shù))voidDispList(LinkList*L)/輸出線性表DispList(L)LinkList*p=L->next;while(p!=NULL)/逐一掃描單鏈表L的每個數(shù)據(jù)結(jié)點，并顯示各結(jié)點

4、的data域值。printf("%c”,p->data);p=p->next;)printf("n");)intGetELem(LinkList*L,inti,ElemType&e)/|求線性表L中指定位置的某個數(shù)據(jù)元素GetElem(L,i,&e)intj=0;LinkList*p=L;while(j<i&&p!=NULL)/1在單鏈表L中從頭開始找到第i個結(jié)點，若存在第i個數(shù)據(jù)結(jié)點，則將其data域值賦2&變量e。j+;p=p->next;)if(p=NULL)return0;/不存在第i個數(shù)據(jù)結(jié)

5、點elsee=p->data;/存在第i個數(shù)據(jù)結(jié)點return1;)intLocateElem(LinkList*L,ElemTypee)/按元素值查找LocateElem(L,e)LinkList*p=L->next;intn=1;while(p!=NULL&&p->data!=e)|在單鏈表L中從頭開始找第1個值域與e相等的結(jié)點，若存在這樣的結(jié)點，則返回位置，否則返回00p=p->next;n+;)if(p=NULL)return(0);elsereturn(n);)intListInsert(LinkList*&L,inti,ElemTyp

6、ee)*插入數(shù)據(jù)元素ListInsert(&L,i,e)intj=0;LinkList*p=L,*s;while(j<i-1&&p!=NULL)/先在單鏈表L中找到第i-1個結(jié)點*p,若存在這樣的結(jié)點，將值為e的結(jié)點*s插入到其后。j+;p=p->next;)if(p=NULL)return0;/|未找到位序為i-1的結(jié)點elses=(LinkList*)malloczeof(LinkList);s->data=e;s->next=p->next;/*將*s插入到之后p->next=s;return1;)intListDelete(L

7、inkList*&L,inti,ElemType&e)/|刪除數(shù)據(jù)元素ListDelete(&L,i,&e)intj=0;LinkList*p=L,*q;while(j<i-1&&p!=NULL)查找第i-1個結(jié)點j+;p=p->next;if(p=NULL)d未找到位序為i-1的結(jié)點return0;else/1找到位序為i-1的結(jié)點*pq=p->next;/q|指向要刪除的結(jié)點if(q=NULL)return0;/|若不存在第i個結(jié)點，返回e=q->data;p->next=q->next;/|從單鏈表中刪除

8、*q結(jié)點free(q);/|釋放*q結(jié)點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);五、實驗測試及結(jié)果六、思考題1、單鏈表有帶頭結(jié)點和不帶頭結(jié)點兩種形式，則相應(yīng)的操作實現(xiàn)有何區(qū)別？答：在

11、帶頭節(jié)點的單鏈表中，頭指針（head）只有一個域，即鏈指針，它指向頭結(jié)點，頭結(jié)點有兩個域，一個是數(shù)據(jù)域，值為0（NULL,還有一個域，鏈指針，這個鏈指針指向單鏈表的第一個數(shù)據(jù)元素。而在不帶頭結(jié)點的單鏈表中，頭指針也只有一個鏈指針，但它指向單鏈表的第一個數(shù)據(jù)元素。2、單向循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表基本操作的實現(xiàn)。答：（1）單向循環(huán)鏈表循環(huán)鏈表的基本運算實現(xiàn)算法與非循環(huán)鏈表的算法基本相同，只是對表尾的判斷作了改變。因此單向循環(huán)鏈表與單鏈表基本上操作相同，只不過表尾的條件將發(fā)生變化。（2）雙向鏈表基本操作實現(xiàn)雙鏈表中有兩個指針域，一個指向其直接后繼結(jié)點，另一個指向其直接前驅(qū)結(jié)點。建立雙鏈表有頭

12、插法和尾插法?！?】頭插法：VoidCreateListF(DLinkList*&L,ElemTypea,intn)/由含有n個元素的數(shù)組a創(chuàng)建帶頭結(jié)點的雙鏈表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個元素的數(shù)組a創(chuàng)建帶頭結(jié)點的雙鏈表LDLinkList*s,*r;intI;L=(DLinkList*)malloc(sizeof(DLinkList);L->prior=L->next=NULL;r=L;/r始終指向尾結(jié)點，開始時指向頭結(jié)點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;在雙鏈表中，大部分基本操作運算與單鏈表相同，除插入與刪除有所區(qū)別。【插入】intListInsert(DLinkList*&L,intI,ElemTypee)intj=0;DLinkList*p=L,*s;/p(指向頭結(jié)點While(j<i-1&&p!=NULL)/查找第i-1個結(jié)點j+;p=p->next;if(p=NULL)/|未找到邏輯位序位i-1的結(jié)點return0;else/|找到邏輯位序為i-1的結(jié)點*ps=(DLinkList*)malloczeof(DLinkList

15、)/創(chuàng)建結(jié)點*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指向頭結(jié)點intj=0;while(j<i-1&&p!=NULL)查找第i-1個結(jié)點j+;p=p->next;if(p=NULL)return0;elseq

16、=p->next;if(q=NULL)return0;e=q->data;p->next=q->next;/從單鏈表中刪除*q結(jié)點if(p->next!=NULL)p->next->prior=p;free(q);/|釋放*p結(jié)點return1;(2)雙向循環(huán)鏈表實現(xiàn)：插入操作(在p所指結(jié)點之前插入q結(jié)點的過程)StatusListInsert_Dl(DLinkList&L,inti,ElemTypex)/在帶頭結(jié)點的向循環(huán)鏈表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;)刪除操作算法(刪