單鏈表的定義及基本操作

文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.單鏈表的定義及基本操作一、實(shí)驗(yàn)?zāi)康?、意義1）理解線性表中帶頭結(jié)點(diǎn)單鏈表的定義和邏輯圖表示方法。2）熟練掌握單鏈表的插入，刪除和查詢算法的設(shè)計(jì)與實(shí)現(xiàn)。3）根據(jù)具體問(wèn)題的需要，設(shè)計(jì)出合理的表示數(shù)據(jù)的鏈表結(jié)構(gòu)，并設(shè)計(jì)相關(guān)算法。二、實(shí)驗(yàn)內(nèi)容及要求說(shuō)明1：本次實(shí)驗(yàn)中的鏈表結(jié)構(gòu)均為帶頭結(jié)點(diǎn)的單鏈表。說(shuō)明2:學(xué)生在上機(jī)實(shí)驗(yàn)時(shí)，需要自己設(shè)計(jì)出所涉及到的函數(shù)，同時(shí)設(shè)計(jì)多組輸入數(shù)據(jù)并編寫主程序分別調(diào)用這些函數(shù)，調(diào)試程序并對(duì)相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗(yàn)證輸出的結(jié)果，加深對(duì)有關(guān)算法的理解。具體要求：建立單鏈表，完成鏈表（帶表頭結(jié)點(diǎn)）的基本操作：建立鏈表、插入、刪除、查找、輸出；其它基本操作還有銷毀鏈表、將鏈表置為空表、求鏈表的長(zhǎng)度、獲取某位置結(jié)點(diǎn)的內(nèi)容、搜索結(jié)點(diǎn)。三、實(shí)驗(yàn)所涉及的知識(shí)點(diǎn)數(shù)據(jù)結(jié)構(gòu)、C語(yǔ)言語(yǔ)法函數(shù)、結(jié)構(gòu)體類型指針、單鏈表（建表、初始化鏈表、求表長(zhǎng)、插入、刪除、查詢算法）等。四、實(shí)驗(yàn)結(jié)果及分析（所輸入的數(shù)據(jù)及相應(yīng)的運(yùn)行結(jié)果，運(yùn)行結(jié)果要有提示信息，運(yùn)行結(jié)果采用截圖方式給出。）五、總結(jié)與體會(huì)（調(diào)試程序的心得與體會(huì)，若實(shí)驗(yàn)課上未完成調(diào)試，要認(rèn)真找出錯(cuò)誤并分析原因等。）調(diào)試程序時(shí)，出現(xiàn)了許多錯(cuò)誤。如：結(jié)構(gòu)體類型指針出錯(cuò)，忽略了釋放存儲(chǔ)空間，對(duì)頭插法建表、尾插法建表不熟悉等。另外還有一些語(yǔ)法上的錯(cuò)誤。由于對(duì)所學(xué)知識(shí)點(diǎn)概念模糊，試驗(yàn)課上未能完成此次上機(jī)作業(yè)。后來(lái)經(jīng)過(guò)查閱教材，瀏覽網(wǎng)頁(yè)等方式，才完成試驗(yàn)。這次試驗(yàn)出現(xiàn)錯(cuò)誤最重要的原因就是對(duì)課本知識(shí)點(diǎn)理解不深刻以及編寫代碼時(shí)的粗心。以后要都去練習(xí)、實(shí)踐，以完善自己的不足。1文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.六、程序清單(包含注釋)//單鏈表#include<stdio.h>#include<malloc.h>#defineOK1#defineERROR0typedefcharElemType;typedefintStatus;//線性表的單鏈表的存儲(chǔ)結(jié)構(gòu)typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;//LinkList 為結(jié)構(gòu)體類型的指針，可以直接定義變量，比如 LinkListp；//建表（頭插法）voidCreatListF(LinkList&L,ElemTypea[],intn){//初始化線性表L=(LinkList)malloc(sizeof(LNode));// 分配內(nèi)存空間L->next=NULL;//在表中插入元素LinkListS;inti;//頭插法for(i=0;i<n;i++){S=(LinkList)malloc(sizeof(LNode));// 生成新結(jié)點(diǎn)S->data=a[i];//數(shù)據(jù)域S->next=L->next;L->next=S;2文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.}}//建表（尾插法）voidCreatListR(LinkList&L,ElemTypea[],intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;LinkListp;p=L;LinkListS;inti;//尾插法for(i=0;i<n;i++){S=(LinkList)malloc(sizeof(LNode));S->data=a[i];p->next=S;p=S;}p->next=NULL;}//初始化線性表voidInitList(LinkList&L){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;}//獲得鏈表元素StatusGetElem(LinkListL,inti,ElemType&e){3文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針LinkListp;intj;//初始化，p指向第一個(gè)結(jié)點(diǎn)p=L->next;//j為計(jì)數(shù)器j=1;//順指針往后查找，直到 p指向第i個(gè)元素或 p為空while(p&&j<i){p=p->next;j++;}//第i個(gè)元素不存在if(!p||j>i)returnERROR;//取第i個(gè)元素e=p->data;returnOK;}//插入StatusListInsert(LinkList&L,inti,ElemTypee){intj=0;LinkListp;p=L;while(p!=NULL&&j<i-1)// 找第i-1個(gè)結(jié)點(diǎn){p=p->next;j++;}4文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.if(!p||j>i-1)returnERROR;LinkListS;S=(LinkList)malloc(sizeof(LNode));// 生成新結(jié)點(diǎn)S->data=e;S->next=p->next;p->next=S;returnOK;}//刪除StatusListDelete(LinkList&L,inti,ElemType&e){LinkListp;LinkListq;intj=0;p=L;while((p->next)!=NULL&&j<i-1)// 找第i個(gè)結(jié)點(diǎn){p=p->next;j++;}//!(p->next) ：指向第i個(gè)結(jié)點(diǎn)的指針為空（第 i個(gè)元素不存在）if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}5文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.//求表的長(zhǎng)度intListLength(LinkListL){LinkListp;p=L;intj=0;//線性鏈表最后一個(gè)結(jié)點(diǎn)的指針為空while((p->next)!=NULL){j++;p=p->next;}returnj;}//輸出voidvisit(LinkListL){LinkListp;p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}}//銷毀:要銷毀的話從頭結(jié)點(diǎn)開(kāi)始依次 free但要先得到下一個(gè)節(jié)點(diǎn)再 freevoidDestroyList(LinkList&L){LinkListp;LinkListq;p=L;6文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.q=p->next;while(p!=NULL){free(p);p=q;q=p->next;}free(p);}判空intListEmpty(LinkListL){//為空表則執(zhí)行該語(yǔ)句，否則返回 return0；return(L->next==NULL);}//查找intListSearch(LinkListL,ElemTypee){LinkListp;p=L->next;inti=1;while(p!=NULL&&p->data!=e){p=p->next;i++;}if(p==NULL)return0;returni;}intmain()7文檔收集于互聯(lián)網(wǎng)，已整理， word版本可編輯.文檔來(lái)源為:從網(wǎng)絡(luò)收集整理 .word版本可編輯.歡迎下載支持.{ElemTypee;ElemTypea[6]={'a','b','c','d','e','f'};LinkListL;//鏈表的頭指針printf("頭插法建表： ");CreatListF(L,a,6);visit(L);printf("\n\n");//初始化InitList(L);printf("初始化后的表： ");visit(L);printf("\n\n");printf("尾插法建表： ");CreatListR(L,a,6);visit(L);printf("\n\n");//初始化后表為空，此時(shí)不要調(diào)用 GetElem()GetElem(L,3,e);printf("表中第3個(gè)元素為：");printf("%c\n\n",e);//在第5個(gè)位置插入字符 'k'ListInsert(L,5,'k');printf("在表中第 5個(gè)位置插入字符 'k'后：");visit(L);printf("\n\n");printf("表的長(zhǎng)度為:%d\n\n",ListLength(L));intz;z=ListSearch(L,'d');