實驗1_鏈表的操作實驗

1、實驗B01: 鏈表的操作實驗一、實驗名稱和性質(zhì)所屬課程數(shù)據(jù)結(jié)構(gòu)實驗名稱鏈表的操作實驗學(xué)時2實驗性質(zhì)驗證 綜合 設(shè)計必做/選做必做 選做二、實驗?zāi)康?掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的表示和實現(xiàn)方法。2掌握鏈表基本操作的算法實現(xiàn)。三、實驗內(nèi)容1建立單鏈表，并在單鏈表上實現(xiàn)插入、刪除和查找操作（驗證性內(nèi)容）。2建立雙向鏈表，并在雙向鏈表上實現(xiàn)插入、刪除和查找操作（設(shè)計性內(nèi)容）。3計算已知一個單鏈表中數(shù)據(jù)域值為一個指定值x的結(jié)點個數(shù)（應(yīng)用性設(shè)計內(nèi)容）。四、實驗的軟硬件環(huán)境要求硬件環(huán)境要求：PC機（單機）使用的軟件名稱、版本號以及模塊：Windows環(huán)境下的TurboC2.0以上或VC+ 等。五、知識準(zhǔn)備前期

2、要求熟練掌握了C語言的編程規(guī)則、方法和單鏈表和雙向鏈表的基本操作算法。六、驗證性實驗1實驗要求編程實現(xiàn)如下功能：（1）根據(jù)輸入的一系列整數(shù)，以0標(biāo)志結(jié)束，用頭插法建立單鏈表，并輸出單鏈表中各元素值，觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。（2）在單鏈表的第i個元素之前插入一個值為x的元素，并輸出插入后的單鏈表中各元素值。（3）刪除單鏈表中第i個元素，并輸出刪除后的單鏈表中各元素值。（4）在單鏈表中查找第i個元素，如果查找成功，則顯示該元素的值，否則顯示該元素不存在。2. 實驗相關(guān)原理：線性表的鏈?zhǔn)絻Y(jié)構(gòu)是用一組任意的存儲單元依次存放線性表中的元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。為反映

3、出各元素在線性表中的前后邏輯關(guān)系，對每個數(shù)據(jù)元素來說，除了存儲其本身數(shù)據(jù)值之外，還需增加一個或多個指針域，每個指針域的值稱為指針，又稱作鏈，它用來指示它在線性表中的前驅(qū)或后繼的存儲地址。這兩個部分的的一起組成一個數(shù)據(jù)元素的存儲映像，稱為結(jié)點，若干個結(jié)點鏈接成鏈表。如果一個結(jié)點中只含一個指針的鏈表，則稱單鏈表。單鏈表的存儲結(jié)構(gòu)描述如下：typedef struct Lnode Elemtype data;/*數(shù)據(jù)域*/ struct Lnode *next;/*指針域*/LNODE,*Linklist; /*其中LNODE為結(jié)點類型名，Linklist為指向結(jié)點的指針類型名*/【核心算法提示】1

4、 鏈表建立操作的基本步驟：鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此建立鏈表的過程是一個結(jié)點“逐個插入” 的過程。先建立一個只含頭結(jié)點的空單鏈表，然后依次生成新結(jié)點，再不斷地將其插入到鏈表的頭部或尾部，分別稱其為“頭插法”和“尾插法”。2 鏈表查找操作的基本步驟：因鏈表是一種"順序存取"的結(jié)構(gòu)，則要在帶頭結(jié)點的鏈表中查找到第 i個 元素，必須從頭結(jié)點開始沿著后繼指針依次"點數(shù)"，直到點到第 i 個結(jié)點為止,如果查找成功，則用e返回第i個元素值。頭結(jié)點可看成是第0個結(jié)點。3 鏈表插入操作的基本步驟：先確定要插入的位置，如果插入位置合法，則再生成新的結(jié)點

5、，最后通過修改鏈將新結(jié)點插入到指定的位置上。4 鏈表刪除操作的基本步驟：先確定要刪除的結(jié)點位置，如果位置合法，則再通過修改鏈?zhǔn)贡粍h結(jié)點從鏈表中“卸下”，最后釋放被刪結(jié)點的空間。 【核心算法描述】void creat1(Linklist &L) /*輸入一系列整數(shù)，以0標(biāo)志結(jié)束，將這些整數(shù)作為data域并用頭插法建立一個帶頭結(jié)點的單鏈表的函數(shù)*/ L=(Linklist)malloc(sizeof(LNODE);/*生成頭結(jié)點*/ L->next=NULL;/*頭結(jié)點的指針域初始為空*/ scanf("%d",&node);while(node!=0)

6、p=(Linklist)malloc(sizeof(LNODE);/*為一個新結(jié)點的分配空間*/ p->data=node; /*為新結(jié)點數(shù)據(jù)域賦值*/ p->next=L->next;/*新結(jié)點指針域指向開始結(jié)點*/ L->next=p; /*頭結(jié)點指針域指向新結(jié)點，即新結(jié)點成為開始結(jié)點*/scanf("%d",&node); void creat2(Linklist &L) /*輸入一系列整數(shù)，以0標(biāo)志結(jié)束，將這些整數(shù)作為data域并用尾插法建立一個帶頭結(jié)點的單鏈表的函數(shù)*/ L=(Linklist)malloc(sizeof(L

7、NODE);/*為頭結(jié)點分配空間*/ L->next=NULL; /*頭結(jié)點的指針域初始為空*/ r=L; /*尾指針初始指向頭結(jié)點*/scanf("%d",&node);while(node!=0) p=(Linklist)malloc(sizeof(LNODE);/*為一個新結(jié)點分配空間*/ p->data=node; /*新結(jié)點數(shù)據(jù)域賦值*/ p->next=NULL; /*新結(jié)點指針域為空*/ r->next=p;/*尾結(jié)點指針域指向新結(jié)點*/ r=p; /*尾指針指向新結(jié)點，即新結(jié)點成為尾結(jié)點*/scanf("%d&quo

8、t;,&node); status list_search(Linklist L, int i;Elemtype &e) /*在帶頭結(jié)點的單鏈表L中查找第i個元素，如果查找成功則用e返回其值*/ p=L->next; /*使指針p指向第1個元素結(jié)點*/j=1; /*計數(shù)器賦初值為1*/while (p&& j<i) /*順著后繼指針查找第i個元素結(jié)點*/ p=p->next; j+;if (!p&& j>i) return ERROR; /*如果i值不合法，即i值小于1或大于表長，則出錯*/e=p->data; /*

9、如果第i個元素存在，則將該元素值賦給e*/return OK; status list_insert(Linklist &L,int i;Elemtype x) /*在帶頭結(jié)點的單鏈表L中第i個位置之前插入新元素x*/ p=L; j=0; while(p!=NULL&&j<i-1) /*尋找插入位置，并使p指向插入位置的前驅(qū)結(jié)點，即L中的第i-1個位置*/ p=p->next; +j; if(p=NULL|j>i-1) return ERROR; /*若位置不正確,即i小于1或大于表的長度加1，則出錯*/ s=(Linklist)malloc(size

10、of(LNODE); /*分配一個新結(jié)點的空間*/ s->data=x; /*為新結(jié)點數(shù)據(jù)域賦值*/ /*下面兩條語句就是完成修改鏈，將新結(jié)點s插入到p結(jié)點之后*/ s->next=p->next; /*新結(jié)點指針域指向p的后繼結(jié)點*/ p->next=s; /*新結(jié)點成為p的后繼結(jié)點*/ return OK;status list_delete(Linklist &L,int i,Elemtype &x)/*在帶頭結(jié)點的單鏈表L中，刪除第i個元素結(jié)點,并用x返回其值*/ p=L;j=0; while(p->next!=NULL&&

11、j<i-1) /*尋找被刪結(jié)點，并使p指向被刪結(jié)點的前驅(qū)*/ p=p->next; +j; if (p->next=NULL|j>i-1) return ERROR; /*若位置不正確，即i小于1或大于表長，則出錯*/ q=p->next; /* q指向p的后繼結(jié)點*/ p->next=q->next; /*q的后繼結(jié)點成為p的后繼結(jié)點*/ x=q->data; /*用x返回第i個位置的元素*/free(q); /*釋放q所指的被刪結(jié)點的空間*/return OK;3源程序代碼參考#include <stdio.h>#include

12、<malloc.h>typedef struct Lnode int data; struct Lnode *next; LNODE,*Linklist;Linklist creat(Linklist L) /*單鏈表建立函數(shù) */int node; Linklist p; L=(Linklist)malloc(sizeof(LNODE); L->next=NULL; printf("nplease input the node(end with 0):n "); /*請求輸入線性表中各個元素，以0結(jié)束*/ scanf("%d",&am

13、p;node); while(node!=0) p=(Linklist)malloc(sizeof(LNODE); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf("%d",&node); return L;Linklist insert(Linklist L,int i,int x) /*單鏈表插入函數(shù)*/ int j;Linklist p,s; p=L; j=0; while (p!=NULL&&j<i-1) p=p->next;

14、+j; if (p=NULL|j>i-1) printf("n ERROR position!n"); else s=(Linklist)malloc(sizeof(LNODE); s->data=x; s->next=p->next; p->next=s; return L;Linklist delete(Linklist L,int i) /*單鏈表刪除函數(shù)*/ int j,x; Linklist p,q; p=L; j=0; while(p->next!=NULL&&j<i-1) p=p->next; +

15、j; if(p->next=NULL|j>i-1) printf("n ERROE position!n"); else q=p->next; p->next=q->next; x=q->data; printf("the delete data is:%dn",x); free(q); return L;int search(Linklist L, int i) /*單鏈上的查找函數(shù)*/ Linklist p; int j; p=L->next; j=1; while (p&& j<i)

16、p=p->next; j+; if (!p&& j>i) return 0; /*如果i值不合法，即i值小于1或大于表長，則函數(shù)返回0值*/ else return(p->data); /*否則函數(shù)返回第i個元素的值*/void display(Linklist L) /*單鏈表元素輸出函數(shù)*/ Linklist p; p=L->next; while(p!=NULL) printf("%4d",p->data); p=p->next; printf("n");main()/*主函數(shù)*/ Linklis

17、t L=NULL; int i,x; L=creat(L);/*調(diào)用單鏈表建立函數(shù)*/ printf("the Linklist is:n"); display(L); /*調(diào)用單鏈表元素輸出(遍歷)函數(shù)*/ printf("please input the position you want to insert:");/*請求輸入插入操作位置*/ scanf("%d",&i); printf("please input the node you want to insert:");/*請求輸入需要插入的元

18、素*/ scanf("%d",&x); L=insert(L,i,x);/*調(diào)用單鏈表插入函數(shù)*/ printf("the Linklist after inserted is:n"); display(L);/*調(diào)用單鏈表元素輸出(遍歷)函數(shù)*/ printf("please input the node position you want to delete:"); /*請求輸入刪除操作位置*/ scanf("%d",&i); L=delete(L,i); /*調(diào)用單鏈表刪除函數(shù)*/ print

19、f("the Linklist after deleted is:n"); display(L); /*調(diào)用單鏈表元素輸出(遍歷)函數(shù)*/ printf("please input the position you want to search:"); /*請求輸入待查找元素的位置*/ scanf("%d",&i); x=search(L,i); /*調(diào)用單鏈表查找函數(shù)*/ if (x) /*如果查找成功，則顯示第i個元素的值，否則顯示第i個元素不存在*/ printf(" the %dth elem is %dn&

20、quot;,i,x); else printf(" the %dth elem is not exsitn");4運行結(jié)果參考如圖2-1所示： 圖2-1: 驗證性實驗運行結(jié)果七、設(shè)計性實驗1. 編程實現(xiàn)在雙向循環(huán)鏈表上的插入、刪除和查找操作1 實驗要求（1）輸入鏈表的長度和各元素的值，用尾插法建立雙向循環(huán)鏈表，并輸出鏈表中各元素值，觀察輸入的內(nèi)容與輸出的內(nèi)容是否一致。（2）在雙向循環(huán)鏈表的第i個元素之前插入一個值為x的元素，并輸出插入后的鏈表中各元素值。（3）刪除雙向循環(huán)鏈表中第i個元素，并輸出刪除后的鏈表中各元素值。（4）在雙向循環(huán)鏈表中查找值為x元素，如果查找成功，則顯

21、示該元素在鏈表中的位置，否則顯示該元素不存在。 核心算法提示 雙向循環(huán)鏈表采用的存儲結(jié)構(gòu)描述如下： typedef struct DULNODE Elemtype data; /*數(shù)據(jù)域*/ struct DULNODE *prior; /*指向前驅(qū)結(jié)點的指針域*/ struct DULNODE *next;/*指向后繼結(jié)點的指針域*/ DULNODE,*DuLinklist; typedef int Elemtype;不論是建立雙向循環(huán)鏈表還是在雙向循環(huán)鏈表中進行插入、刪除和查找操作，其操作方法和步驟都跟單鏈表類似。只不過要注意兩點：（1）凡是在操作中遇到有修改鏈的地方，都要進行前驅(qū)和后繼兩

22、個指針的修改。（2）單鏈表操作算法中的判斷條件：p= =NULL 或p!=NULL ,在循環(huán)鏈表的操作算法中則需改為：p!= L,其中L為鏈表的頭指針。 核心算法描述void DuList_creat (DuLinklist &L,int n) /*輸入n個整數(shù)（其中n為表長），將這些整數(shù)作為data域并用尾插法建立一個帶頭結(jié)點的雙向循環(huán)鏈表的函數(shù)*/ L=( DuLinklist)malloc(sizeof(DULNODE);/*為頭結(jié)點分配空間*/ L->next=L->prior=L;/*使頭結(jié)點的后繼指針和前驅(qū)指針都指向自身，形成空的雙向循環(huán)鏈表*/ r=L; /*

23、尾指針初始指向頭結(jié)點*/for (i=0;i<n;i+) p=(DuLinklist)malloc(sizeof(DULNODE);/*為一個新結(jié)點分配空間*/ scanf("%d",&p->data); /*從鍵盤輸入值，并保存在新結(jié)點數(shù)據(jù)域中*/ p->next=r->next; /*新結(jié)點后繼指針指向尾結(jié)點r的后繼結(jié)點*/ p->prior=r; /*新結(jié)點的前驅(qū)指針指向尾結(jié)點r*/ r->next=p; /*尾結(jié)點的后繼指針指向新結(jié)點*/ r=p; /*尾指針指向新結(jié)點，即新結(jié)點成為尾結(jié)點*/L->prior=r;

24、/*使尾結(jié)點成為頭結(jié)點的前驅(qū)結(jié)點*/status DuList_search(DuLinklist L, int i;Elemtype &e) /*在帶頭結(jié)點的雙向循環(huán)鏈表L中查找第i個元素，如果查找成功則用e返回其值*/ p=L->next; /*使指針p指向第1個元素結(jié)點*/j=1; /*計數(shù)器賦初值為1*/ while (p!=L && j<i) /*順著后繼指針查找第i個元素結(jié)點*/ p=p->next; j+;if (j!=i) return ERROR; /*如果i值不合法，即i值小于1或大于表長，則出錯*/e=p->data; /*如果第i個元素存在，則將該元素值賦給e*/return OK; status DuList_insert(DuLinklist &L,int i;Elemtype x) /*在帶頭結(jié)點的雙向循環(huán)鏈表L中第i個位置之前插入新元素x*/ p=L->next; j=1;while(p!=L &&j<i) /*尋找插入位置，并使p指向插入位置的結(jié)點，即L中的第i個結(jié)點*/ p=p->next; +j; if(j!=i) return ERROR; /*