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

1、實(shí)現(xiàn)單鏈表的各種基本運(yùn)算一、實(shí)驗(yàn)?zāi)康牧私鈫捂湵肀淼慕Y(jié)構(gòu)特點(diǎn)及有關(guān)概念，掌握單鏈表的各種基本操作算法思想及其實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容編寫(xiě)一個(gè)程序，實(shí)現(xiàn)順序表的各種基本運(yùn)算：1 、初始化單鏈表；2、單鏈表的插入；3、單鏈表的輸出；4、求單鏈表的長(zhǎng)度5、判斷單鏈表是否為空；6、輸出單鏈表的第i位置 的元素；7、在單鏈表中查找一個(gè)給定元素在表中的位置；8、單鏈表的刪除；9、釋放單鏈表三、算法思想與算法描述簡(jiǎn)圖void InitList(LinkList*&L)初始化單鏈表 LLJvoid DestroyList(LinkList*&L)釋放單鏈表 LkJint ListEmpty(Li nk

2、List*L)/判斷單鏈表L是否為空集int Listle ngth(Li nkList*L)/返回單鏈表L的元素個(gè)數(shù)Jvoid DispList(L in kListt*L)/輸出單鏈表Lint GetElem(Li nkList*L,i nt i,char e)/*ElemType e)獲取單鏈表L中的第i個(gè)元素*/Jrint LocateEmpty(L in kList*L,char e)/*ElemType e)在單鏈表L中查找元素e*/JrFint ListInsert(LinkList*&L,inti,char e)/*ElemType e)在單鏈表中第i個(gè)位置上插入元素e

3、*/,intListDelete(Li nkList*&L,i nti,char& e)/*ElemTypeL)在單鏈表L中刪除第i個(gè)元素*/J四、實(shí)驗(yàn)步驟與算法實(shí)現(xiàn)#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);/創(chuàng)建頭結(jié)點(diǎn)L->next=NULL;頭結(jié)點(diǎn)賦值為空void DestroyList(LinkList*&L)銷(xiāo)毀單鏈表(釋放單鏈表 L占用的內(nèi)存空間即逐一釋放全部結(jié)點(diǎn)的空間)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沒(méi)有數(shù)據(jù)結(jié)點(diǎn)，則返回真,否則返回求線性表的長(zhǎng)度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中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)void DispList(LinkList*L)輸出線性表 DispList(L)Li nkList*p=L-> next;while (p!=NULL) 逐一掃描單鏈表L的每個(gè)數(shù)據(jù)結(jié)點(diǎn)，并顯示各結(jié)點(diǎn)的data域 值。pri ntf("%c",p->data);p=p->n ext;prin tf("n");i

6、nt GetELem(LinkList*L,inti,ElemType&e) | 求線性表 L 中指定位置的某個(gè)數(shù)據(jù)元素 GetElem(L,i,&e)int j=0;Lin kList*p=L;while(j<i&&p!=NULL) |在單鏈表L中從頭開(kāi)始找到第i個(gè)結(jié)點(diǎn)，若存在第i 個(gè)數(shù)據(jù)結(jié)點(diǎn),則將其data域值賦給變量e。j+;p=p->n ext;if(p=NULL)return 0;/不存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)elsee=p->data;/ 存在第i個(gè)數(shù)據(jù)結(jié)點(diǎn)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中從頭開(kāi)始找第1個(gè)值域與e相等 的結(jié)點(diǎn)，若存在這樣的結(jié)點(diǎn)，則返回位置，否則返回0。p=p->n ext;n+;if(p=NULL)return (0);elsereturn (n);intListInsert(LinkList*&L,inti,ElemTypee)/| 插入數(shù)據(jù)元素List In sert(&L,i,e)int j=0;Lin kList*p=L,*s

8、;while(j<i-1 &&p!=NULL)先在單鏈表L中找到第i-1個(gè)結(jié)點(diǎn)*p,若存在這樣的結(jié)點(diǎn),將值為e的結(jié)點(diǎn)*s插入到其后。j+;p=p->n ext;if(p=NULL)return 0;/ 未找到位序?yàn)閕-1的結(jié)點(diǎn)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)刪除數(shù)據(jù)元素Li

9、stDelete(&L,i,&e)int j=0;Lin kList*p=L,*q;while(j<i-1 &&p!=NULL)查找第 i-1 個(gè)結(jié)點(diǎn)j+;p=p->n ext;if(p=NULL)/|未找到位序?yàn)閕-1的結(jié)點(diǎn) return 0;else/|找到位序?yàn)閕-1的結(jié)點(diǎn)*pq=p->next;/ql指向要?jiǎng)h除的結(jié)點(diǎn)if(q=NULL)return 0;/ |若不存在第i個(gè)結(jié)點(diǎn),返回e=q->data;p->next=q->next;/ 從單鏈表中刪除*q結(jié)點(diǎn)free(q);/ 釋放 *q 結(jié)點(diǎn)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 長(zhǎng)度=%dn",ListLength(h);printf("(5)單鏈表 h 為%sn",(ListEmpty(h)?"空":"非空");GetELem(h,3,e);printf("(6)單鏈表h的第三個(gè)元素=%cn",e);printf("(7)元素 a 的位置=%dn",LocateElem(h,'a');printf("(

12、8)在第四個(gè)元素的位置上插入9元素n");ListI nsert(h,4,'9');printf("(9)輸出單鏈表 h:");DispList(h);printf("(10)刪除h的第三個(gè)元素n");ListDelete(h,3,e);printf("(11)輸出單鏈表 h:");DispList(h);printf("(12)釋放單鏈表 hn");DestroyList(h);五、實(shí)驗(yàn)測(cè)試及結(jié)果六、思考題1、 單鏈表有帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種形式，則相應(yīng)的操作實(shí) 現(xiàn)有何區(qū)別？答：在帶頭

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

14、鏈表有頭插法和尾插法。【1】頭插法：Void CreateListF(DLinkList *&L,ElemType a,int n)/由含有n個(gè)元素的數(shù)組a創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表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個(gè)元素的數(shù)組a創(chuàng)建帶頭結(jié)點(diǎn)的雙鏈表LDLi nkList *s,*r;i nt I;L=(DLi nkList *)malloc(sizeof(DLi nkList);L->prior=L- >n ext=NULL;r=L;/r始終指向尾結(jié)點(diǎn)，開(kāi)始時(shí)指向頭結(jié)點(diǎn)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;在雙鏈表中，大部分基本操作運(yùn)算與單鏈表相同，除插入與刪除有所區(qū)別。【插入】int ListInsert(DLinkList *&L,int l,ElemType e)int j=0;DLinkList *p=L,*s;/p(指向頭結(jié)點(diǎn)While(j<i-1 &&p!=NULL)/查找第 i-1 個(gè)結(jié)點(diǎn)j+;p=p->n ext;if(p=NULL)/ |未找到邏輯位序位i-1的結(jié)點(diǎn)return

17、0;else /匚找到邏輯位序?yàn)閕-1的結(jié)點(diǎn)*ps=(DLinkList *)malloc(sizeof(DLinkList)/創(chuàng)建結(jié)點(diǎn) *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 指向頭結(jié)點(diǎn)int j=0;w

18、hile (j<i-1 &&p!=NULL) / 查找第 i-1 個(gè)結(jié)點(diǎn)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結(jié)點(diǎn)if (p->n ext!=NULL)p->n ext->prior=p;free(q);/ 釋放 *p 結(jié)點(diǎn)return 1;(2)雙向循環(huán)鏈表實(shí)現(xiàn):插入操作(在p所指結(jié)點(diǎn)之前插入q結(jié)點(diǎn)的過(guò)程)Status Listl nsert_DI(DL in kList & L, i nt i, ElemType x)/在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中第i個(gè)位置之前插入元素x, i的合 法值為K i w表長(zhǎng)+1if (!(p = GetElemP_Dul(L, i) /在L中確定第i個(gè)元素的位置指針preturn ERROR;if (!(q = (DuLNode)malloc(sizeof(DuLNode) return ERROR; q->data = x;q->n ext = p; return OK;p->prio