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

1、實現(xiàn)單鏈表的各種基本運算一、實驗目的了解單鏈表表的結(jié)構(gòu)特點及有關概念，掌握單鏈表的各種基本操作算法思想及其實現(xiàn)。二、實驗內(nèi)容編寫一個程序，實現(xiàn)順序表的各種基本運算：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的元素個數(shù)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四、實驗步驟與算法實現(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é)點L->next=NULL;頭結(jié)點賦值為空void DestroyList(LinkList*&L)銷毀單鏈表(釋放單鏈表 L占用的內(nèi)存空間即逐一釋放全部結(jié)點的空間)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沒有數(shù)據(jù)結(jié)點，則返回真,否則返回求線性表的長度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é)點的個數(shù)void DispList(LinkList*L)輸出線性表 DispList(L)Li nkList*p=L-> next;while (p!=NULL) 逐一掃描單鏈表L的每個數(shù)據(jù)結(jié)點，并顯示各結(jié)點的data域 值。pri ntf("%c",p->data);p=p->n ext;prin tf("n");i

6、nt GetELem(LinkList*L,inti,ElemType&e) | 求線性表 L 中指定位置的某個數(shù)據(jù)元素 GetElem(L,i,&e)int j=0;Lin kList*p=L;while(j<i&&p!=NULL) |在單鏈表L中從頭開始找到第i個結(jié)點，若存在第i 個數(shù)據(jù)結(jié)點,則將其data域值賦給變量e。j+;p=p->n ext;if(p=NULL)return 0;/不存在第i個數(shù)據(jù)結(jié)點elsee=p->data;/ 存在第i個數(shù)據(jù)結(jié)點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相等 的結(jié)點，若存在這樣的結(jié)點，則返回位置，否則返回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個結(jié)點*p,若存在這樣的結(jié)點,將值為e的結(jié)點*s插入到其后。j+;p=p->n ext;if(p=NULL)return 0;/ 未找到位序為i-1的結(jié)點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 個結(jié)點j+;p=p->n ext;if(p=NULL)/|未找到位序為i-1的結(jié)點 return 0;else/|找到位序為i-1的結(jié)點*pq=p->next;/ql指向要刪除的結(jié)點if(q=NULL)return 0;/ |若不存在第i個結(jié)點,返回e=q->data;p->next=q->next;/ 從單鏈表中刪除*q結(jié)點free(q);/ 釋放 *q 結(jié)點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);五、實驗測試及結(jié)果六、思考題1、 單鏈表有帶頭結(jié)點和不帶頭結(jié)點兩種形式，則相應的操作實 現(xiàn)有何區(qū)別？答：在帶頭

13、節(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é)點。建立雙

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

17、0;else /匚找到邏輯位序為i-1的結(jié)點*ps=(DLinkList *)malloc(sizeof(DLinkList)/創(chuàng)建結(jié)點 *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é)點int j=0;w

18、hile (j<i-1 &&p!=NULL) / 查找第 i-1 個結(jié)點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é)點if (p->n ext!=NULL)p->n ext->prior=p;free(q);/ 釋放 *p 結(jié)點return 1;(2)雙向循環(huán)鏈表實現(xiàn):插入操作(在p所指結(jié)點之前插入q結(jié)點的過程)Status Listl nsert_DI(DL in kList & L, i nt i, ElemType x)/在帶頭結(jié)點的雙向循環(huán)鏈表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