單鏈表的基本操作

1、實(shí)驗(yàn)題目線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)小組合作姓名班級(jí)學(xué)號(hào)一、實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)（一）1 .掌握線性表的存儲(chǔ)方式、表示方式2 .掌握線性表的基本操作，以及其如何用代碼實(shí)現(xiàn)實(shí)驗(yàn)（二）1 .掌握元素在線性表中的存儲(chǔ)以及表示方法，如何取數(shù)據(jù)元素2 .拓展：將存有偶數(shù)個(gè)元素的線性表中的奇數(shù)項(xiàng)、偶數(shù)項(xiàng)分別抽出，組成一個(gè)新的線性表，并將新的線性表輸出二.實(shí)驗(yàn)環(huán)境DevC+三、實(shí)驗(yàn)內(nèi)容與步驟實(shí)驗(yàn)（一）內(nèi)容：線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱鏈表，有單鏈表和雙鏈表兩類。單鏈表是一種基本的數(shù)據(jù)結(jié)構(gòu)，有兩部分組成：指針域和數(shù)據(jù)域，數(shù)據(jù)域用于存放數(shù)據(jù)，指針域用于指向下一個(gè)結(jié)點(diǎn)的位置。為了操作方便,一般為單鏈表創(chuàng)建一個(gè)頭結(jié)點(diǎn)，指向線性表的的

2、首元素。線性表的最后一個(gè)元素的指針域?yàn)榭眨硎炬湵淼慕Y(jié)束。通順序表一樣，鏈表也有許多基本操作，如：(1)單鏈表的創(chuàng)建(2)單鏈表元素的插入(3)單鏈表元素的刪除(4)單鏈表元素的查找(定位)步驟：1 .引入相關(guān)的頭文件，宏定義2 .創(chuàng)建一個(gè)結(jié)構(gòu)體，用于表示鏈表的結(jié)構(gòu)3 .創(chuàng)建一個(gè)空的單鏈表4 .向單鏈表中添加數(shù)據(jù)5 .查找單鏈表中的元素6 .刪除單鏈表的元素實(shí)驗(yàn)(二)內(nèi)容：已知單鏈表已創(chuàng)建好，表示為L(zhǎng)inkList=a1,b1,a2,b2,.an,bn將單鏈表拆分，使得a1,a2,.an的成一個(gè)單鏈表，剩余的元素構(gòu)成一個(gè)單鏈表，編程實(shí)現(xiàn)。(1)創(chuàng)建單鏈表，添加2n個(gè)元素(2)將鏈表拆分為兩個(gè)子

3、鏈表步驟：7 .引入相關(guān)的頭文件，宏定義8 .創(chuàng)建一個(gè)結(jié)構(gòu)體，用于表示鏈表的結(jié)構(gòu)9 .創(chuàng)建一個(gè)空的單鏈表10 .向單鏈表中添加數(shù)據(jù)11 .調(diào)用拆分鏈表的函數(shù)，用于實(shí)現(xiàn)對(duì)鏈表的拆分工作12 .輸出拆分后的單鏈表四、實(shí)驗(yàn)過程與分析實(shí)驗(yàn)（一）1）引入頭文件，進(jìn)行相關(guān)的定義操作#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLNodeElemTypedata;structLNode*next;LNode,*Link

4、List;2）編寫鏈表的初始化函數(shù)，用于頭結(jié)點(diǎn)的初始化操作voidInitList（LinkListL）L->next=NULL;L->data=0;printf（"帶有頭結(jié)點(diǎn)的單鏈表初始化完畢nn"）;3）單鏈表的遍歷函數(shù)，用于輸出單鏈表的結(jié)點(diǎn)值/遍歷單鏈表voidPrintList（LinkListL）LNode*p;p=L->next;if（p=NULL）printf（"單鏈表為空nn"）;return;printf（"單鏈表的結(jié)點(diǎn)值為："力while(p)printf("%d",p->

5、;data);p=p->next;)printf("nn");)4)結(jié)點(diǎn)的頭插法：用于在頭結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)結(jié)點(diǎn)頭插法StatusInsertHead(LinkListL)/創(chuàng)建結(jié)點(diǎn)LNode*p;ElemTyped;printf("請(qǐng)輸入結(jié)點(diǎn)的值：")；scanf("%d",&d);p=(LNode*)malloc(sizeof(LNode);p->data=d;p->next=L->next;L->next=p;printf("頭插法插入結(jié)點(diǎn)成功nn");returnOK

6、;)5)結(jié)點(diǎn)的尾插法：用于在鏈表的末尾，插入一個(gè)結(jié)點(diǎn)/結(jié)點(diǎn)尾插法StatusInsertTail(LinkListL)LNode*p,*q;ElemTyped;printf("請(qǐng)輸入結(jié)點(diǎn)的值：")；scanf("%d",&d);p=L;q=(LNode*)malloc(sizeof(LNode);q->next=NULL;q->data=d;while(p->next)p=p->next;p->next=q;printf("尾插法創(chuàng)建單鏈表成功nn");returnOK;)6)單鏈表元素的查找：用

7、于獲取某個(gè)位置的元素/獲取單鏈表中的第i個(gè)元素StatusGetElem(LinkListL,intloc)inti=0;LNode*p;p=L->next;while(p)i+;if(i=loc)printf("單鏈表的第d個(gè)元素是：dnn",loc,p->data);break;)p=p->next;)if(!p)printf("該位置超過單鏈表的長(zhǎng)度nn");returnERROR;)returnOK;)7)單鏈表結(jié)點(diǎn)的刪除刪除單鏈表中的第i個(gè)結(jié)點(diǎn)StatusDeleteNode(LinkListL,intloc)inti;LNo

8、de*p,*q;p=L;if(!p->next)printf("單鏈表為空nn");returnERROR;)if(loc<=0)printf("位置必須大于0nn");returnERROR;)for(i=0;i<loc-1;i+)p=p->next;if(!p)/說明單鏈表結(jié)束printf("第個(gè)元素不存在n",loc);returnERROR;)q=p->next;p->next=q->next;free(q);printf("結(jié)點(diǎn)刪除成功n");returnOK;)

9、8)在主函數(shù)中調(diào)用相關(guān)的函數(shù)intmain(void)LinkListL;L=(LNode*)malloc(sizeof(LNode);InitList(L);InsertHead(L);InsertHead(L);PrintList(L);InsertTail(L);InsertTail(L);PrintList(L);GetElem(L,4);DeleteNode(L,1);PrintList(L);DeleteNode(L,0);PrintList(L);return0;)9)編譯鏈接源代碼，后運(yùn)行exe文件：二hrevoOeiktQpClinkliit.exe中有頭皓點(diǎn)跑單施我初始化完

10、畢請(qǐng)輸入結(jié)點(diǎn)的值工10）調(diào)用頭插法的函數(shù)，分別輸入10,20,分別回車:帶有頭結(jié)點(diǎn)的單鏈?zhǔn)匠跏蓟戤呎?qǐng)輸入結(jié)點(diǎn)的俏，10頭插法排入結(jié)點(diǎn)成功請(qǐng)輸入結(jié)點(diǎn)的值：20頭插法插入結(jié)點(diǎn)成功單維融的結(jié)點(diǎn)值為；201011）調(diào)用尾插法的函數(shù)，分別輸入30,40J、NJ。iV'7歲，%星產(chǎn)，lHiiR11nLjAVI帶仃頭結(jié)點(diǎn)的用鏈&初始化完畢請(qǐng)輸入結(jié)點(diǎn)的值：10女后法插A薊點(diǎn)成功請(qǐng)輸人結(jié)點(diǎn)的俏：20女插法插入引點(diǎn)成功單鏈表的結(jié)點(diǎn)值為：2010請(qǐng)輸入結(jié)點(diǎn)的值；30星插法創(chuàng)建單能表成功請(qǐng)輸入結(jié)點(diǎn)的假;40尾插法創(chuàng)建單鏈表成功單鏈友的豺立伯為：2010304012）查找單鏈表的第四個(gè)元素:帶有頭結(jié)點(diǎn)

11、的單銖表初始化完畢請(qǐng)輸入站點(diǎn)的值1W頭插法插入結(jié)點(diǎn)成功請(qǐng)輸入結(jié)點(diǎn)的值：20i:插法插入結(jié)點(diǎn)成功單鏈表的結(jié)點(diǎn)值為：2010請(qǐng)輸入結(jié)點(diǎn)的值；30尾插法創(chuàng)建單鏈表成功請(qǐng)輸入結(jié)點(diǎn)的值；40虐播法創(chuàng)建單鏈表成功單鏈表的結(jié)點(diǎn)值為:20103040單鏈表的第4個(gè)元素是；4013）主函數(shù)中傳入?yún)?shù)，刪除單鏈表的第一個(gè)結(jié)點(diǎn):請(qǐng)輸入結(jié)點(diǎn)的世：1。頭插法插入站點(diǎn)成功請(qǐng)輸入結(jié)點(diǎn)的伯：20實(shí)插注法人結(jié)點(diǎn)成功單鏈表的站點(diǎn)僅為：2010請(qǐng)輸入結(jié)點(diǎn)的值：30尾捕法創(chuàng)建單鏈表成功請(qǐng)輸入結(jié)點(diǎn)的俯；40尾插法創(chuàng)建單鏈表成功單鏈我的結(jié)點(diǎn)值為：20103040單鏈衣的第4個(gè)元素是：40結(jié)點(diǎn)刪除成功單性表的結(jié)點(diǎn)優(yōu)為；10304014）主

12、函數(shù)傳入?yún)?shù)，刪除第0個(gè)未位置的元素，程序報(bào)錯(cuò):C；Usersinechre/oCcsktopClinklist.exe產(chǎn)行頭結(jié)點(diǎn)的單貨去物始化完畢請(qǐng)輸入結(jié)點(diǎn)的伯；10頭插法插入結(jié)點(diǎn)成功請(qǐng)輸入結(jié)點(diǎn)的他；20性播法貓入結(jié)點(diǎn)成功單鏈衣的結(jié)點(diǎn)值為:201C請(qǐng)愉入結(jié)點(diǎn)的俏：30性插法創(chuàng)建單鏈衣成功請(qǐng)摘入結(jié)點(diǎn)的值：40慳插法創(chuàng)建單鏈表成功推戰(zhàn)我的結(jié)點(diǎn)值為：2C103040R鏈去的第4個(gè)元素是：40結(jié)點(diǎn)刪除成功單鏈表的結(jié)點(diǎn)值為：103040位置必須大于015)最后，輸出單鏈表中的元素：CAUserimecirevoDesl(topCinkli&t.帶有頭站點(diǎn)的里錦表初始化完畢有輸入結(jié)點(diǎn)的值二10義

13、播法插入結(jié)點(diǎn)成功請(qǐng)輸入結(jié)點(diǎn)的梢；20頭插法插入站點(diǎn)成功平鏈衣的結(jié)點(diǎn)值為：2010請(qǐng)輸入結(jié)點(diǎn)的值;30尾插法創(chuàng)建單曾表成功請(qǐng)輸入結(jié)點(diǎn)的值，4Q國(guó)摘法創(chuàng)建單藤表成功單依去的結(jié)點(diǎn)值為：20103040“鎮(zhèn)友的第4個(gè)元素足：40結(jié)點(diǎn)刪除成功單靜去的結(jié)點(diǎn)伯為：1U3030住置必須大于0健走的結(jié)山值為：1。3040ProcessexitedAfter5&75secondsvithre實(shí)驗(yàn)(二)1)引入相關(guān)的頭文件，進(jìn)行宏定義#include<stdio.h>#include<stdlib.h>typedefstructNodeintdata;structNode*next;

14、Node,*LinkList;2)初始化函數(shù)，用于對(duì)頭結(jié)點(diǎn)初始化和插入元素(尾插法)voidinit(LinkListL)inti,n;Node*p;L->data=0;L->next=NULL;printf("線性表初始化完成n");printf("請(qǐng)輸入線性表的個(gè)數(shù)(偶數(shù)個(gè))：")；scanf("%d",&n);if(n%2!=0)printf("請(qǐng)輸入偶數(shù)個(gè)數(shù)據(jù)n");return;for(i=0;i<n;i+)p=(Node*)malloc(sizeof(Node);scanf(&

15、quot;%d",&p->data);p->next=L->next;L->next=p;printf("數(shù)據(jù)插入完成n");3)單鏈表的輸出函數(shù)voidprint(LinkListL)Node*p;p=L->next;printf("線性表的元素為：n");while(p)printf("%d”,p->data);p=p->next;)printf("nn");)4)單鏈表的拆分函數(shù)，把單鏈表拆分成兩個(gè):voidcreate(LinkListL)Node*p,*q

16、,*t;/q指向L1,t指向L2LinkListL1,L2;L1=(Node*)malloc(sizeof(Node);L2=(Node*)malloc(sizeof(Node);L1->next=NULL;L2->next=NULL;L1->data=0;L2->data=0;q=L1;t=L2;p=L->next;while(p)q->next=p;p=p->next;q=q->next;q->next=NULL;t->next=p;p=p->next;t=t->next;t->next=NULL;)print(L1);print(L2);p=L;)5)在主函數(shù)中進(jìn)行函數(shù)的調(diào)用intmain(void)LinkListL;L=(Node*)malloc(sizeof(Node);init(L);print(L);create(L);return0;)6)編譯，連接，運(yùn)行源代碼："FC:IJ5ec5mechrevo>Desktopdivicle,exe物生表初始化完成1請(qǐng)輸入線性甚的個(gè)數(shù)（偶數(shù)個(gè)）*7）輸入8,回車，并輸入8個(gè)數(shù)，用空格分隔開，根據(jù)輸出信息,可以看出，鏈表已經(jīng)拆分為兩個(gè)線性衣初始化完成請(qǐng)輸入線性衣的個(gè)數(shù)（偶數(shù)個(gè)）:887654321數(shù)據(jù)插入化成線性衣的元宏為工123