實驗1_鏈表的操作實驗_第1頁
實驗1_鏈表的操作實驗_第2頁
實驗1_鏈表的操作實驗_第3頁
實驗1_鏈表的操作實驗_第4頁
實驗1_鏈表的操作實驗_第5頁
已閱讀5頁,還剩5頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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; /*

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論