數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)

單鏈表的定義和操作

實(shí)驗(yàn)報(bào)告單鏈表的定義和操作實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱單鏈表的定義和操作實(shí)驗(yàn)?zāi)康氖煜語(yǔ)言的上機(jī)環(huán)境。掌握C語(yǔ)言的基本結(jié)構(gòu)；7定*單需車走的結(jié)占舉型?3：熟悉對(duì)單鏈表禹賃體函菽定義和一些基本操作；4.通過(guò)對(duì)單鏈表的定義掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)。實(shí)驗(yàn)內(nèi)容編制一個(gè)演示單鏈表插入、刪除、查找等操作的程序。問(wèn)題描述用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)，實(shí)現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結(jié)構(gòu)類型以及對(duì)單鏈表操作的具體的函數(shù)定義（包括：初始化單鏈表、清空單鏈表、檢查單鏈表是否為空、遍歷單鏈表、求單鏈表的長(zhǎng)度、從單鏈表表中查找元素、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置、向單鏈表中插入元素、從單鏈表中刪除元素、用尾插法建立單鏈表）。問(wèn)題分析該實(shí)驗(yàn)是基于C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)知識(shí)基礎(chǔ)的對(duì)單鏈表的基本操作的檢驗(yàn)，無(wú)需設(shè)計(jì)復(fù)雜的算法，程序語(yǔ)句也相對(duì)簡(jiǎn)單。因此，我直接按要求定義了對(duì)單鏈表操作的具體函數(shù)，并于主函數(shù)中實(shí)現(xiàn)對(duì)應(yīng)的功能調(diào)用，其中，功能選擇靠switch語(yǔ)句實(shí)現(xiàn)。實(shí)驗(yàn)步驟需求分析本演示程序用VC++編寫，完成單鏈表的生成，任意位置的插入、刪除，以及確定某一元素在單鏈表中的位置等操作。輸入的形式和輸入值的范圍：插入元素時(shí)需要輸入插入的位置和元素的值；刪除元素時(shí)輸入刪除元素的位置；查找操作時(shí)需要輸入元素的值。在所有輸入中,元素的值都是整數(shù)。輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內(nèi)容。其中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。程序所能達(dá)到的功能：完成單鏈表的生成(通過(guò)插入操作)、插入、刪除、查找等操作。測(cè)試數(shù)據(jù)：插入操作中依次輸入0,1,2,3,4,5,6,789生成一個(gè)單鏈表概要設(shè)計(jì)1)為了實(shí)現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：ADTLinkList{數(shù)據(jù)對(duì)象：D={ai|aiIntegerSet,i=0,l,2,…,n,n$0}數(shù)據(jù)關(guān)系：R={<ai,ai+l>|aizai+lGD}基本操作：VoidListinsertfLinkListIJnti,DataTypex)初始條件：?jiǎn)捂湵鞩己存在操作結(jié)果：將元素x插入到單鏈表I的i位置VoidListDelfLinkListI^DataTypex)初始條件：?jiǎn)捂湵鞩己存在操作結(jié)果：將單鏈表L中值為x的元素刪除intListGetfLinkListLQataTypex)初始條件：?jiǎn)捂湵鞩依存在操作結(jié)果：?jiǎn)捂湵鞩中查找是否元素x,若存在，返回元素在表中的位置2)本程序包含7個(gè)函數(shù)：①主函數(shù)main()②清空單鏈表函數(shù)LinkedListClear()③檢查單鏈表是否為空函數(shù)LinkedListEmptyf)④遍歷單鏈表函數(shù)LinkedListT「averse()⑤求單鏈表的長(zhǎng)度函數(shù)LinkedListLength()@從單鏈表表中查找元素函數(shù)LinkedListGet()@查找與給定元素的位置函數(shù)LinkedListLocateO?插入元素函數(shù)LinkedListlnsert()?刪除元素函數(shù)LinkedListDelf)⑩用尾插法建立單鏈表函數(shù)LinkedListCreat()函數(shù)說(shuō)明#include<stdio.h>#include<malloc.h>#include<stdlib.h>#defineFALSE0〃邏輯值#defineTRUE1〃邏輯值typedefintDataType;structNode 〃鏈表的結(jié)點(diǎn)類型{DataTypedata;structNode*next;};typedefstructNode*PNode; 〃指向結(jié)點(diǎn)指針typedefstructNode*LinkList;//指向鏈表指針〃創(chuàng)建空單鏈表：帶頭結(jié)點(diǎn)的空鏈表LinkListLinkListlnit()LinkListp;p=(LinkList)malloc(sizeof(structNode));//為表頭結(jié)點(diǎn)申請(qǐng)空間if(p==NULL){printf(HOutofspace!\nn);returnNULL;}else{p->next=NULL;}returnp;}〃清空單鏈表voidLinkListClear(LinkListI){PNodep=lzq=p->next;while(p){free(p);P=Q；if(q)q=p->next;}l->next=NULL;}〃判斷是否為空鏈表intLinkListEmpty(LinkListI){returnl->next==NULL;}〃遍歷單鏈表中所有元素voidLinkListTraverse(LinkListI){LinkListp=l;while(p->next){printf("%d,,/p->next->data);p=p->next;}printfC'Xn");}〃求單鏈表的長(zhǎng)度intLinkListLength(LinkListI)intlen=O;LinkListp=l;while(p->next)len++;p=p->next;}returnlen;}〃查找第i位元素DataTypeLinkListGet(LinkListIJnti){PNodep=l;intj=0;while(j<=i){訐(p==NULL)returnNULL;else{p=p->next;j++;}}returnp->data;}〃求X元素的存儲(chǔ)位置intLinkListLocate(LinkListLDataTypex){PNodep;inti=l;if(l==NULL)return0;p=l->next;while(p!=NULL&&p->next->data!=x){p=p->next;i++；}returni;}〃在第i+1個(gè)元素前插入值為x的元素voidLinkListlnsert(LinkListIJnti,DataTypex)PNodep,q;intj=0;P=l；while(p!=NULL&&j<i){p=p->next;j++;}if(j!=i){printf(HThevalueofi=%disnotreasonable.\n”)；}q=(PNode)malloc(sizeoffstructNode));if(q!=NULL){q->data=x;q->next=p->next;p->next=q;}}〃單鏈表單個(gè)結(jié)點(diǎn)的刪除voidLinkListDel(LinkListLDataTypex){PNodep,q;P=l；while(p->next!=NULL&&p?>next?>data!=x)〃查找x的前驅(qū)p=p->next;if(p->next==NULL)//沒(méi)找到x{printf("Notexist!\nH)；}else{q=p->next;p->next=p->next?>next;//delfree(q);}}〃用尾插法建立單鏈表LinkListLinkListCreat(intn){inti;PNodereacs;LinkListfirst;

first=(LinkList)malloc(sizeof(structNode));rear=first;printf(HPleaseinput%delementstocreatetheLinkList:篤n);for(i=0;i<n;i++){s=(LinkList)malloc(sizeof(structNode));scanf(,,%d,,,&s->data);rear->next二s;rear=s;}rear->next=NULL;returnfirst;}intmain(intargc,char*argv[])單鏈表的定義和操作TOC\o"1-5"\h\zprintf("*********************************************\n"printff"* *\n"單鏈表的定義和操作printff"* 單鏈表的定義和操作 *\n"printff"* *\n"printf^'*********************************************\n"printf^'*********************************************\n"printff"*功能選擇與實(shí)現(xiàn)printf("*printff"*1?用頭插法建立十元素單鏈表*\n”)；printff"*2.清空單鏈表*\n”)；printff'*3.判斷是否為空鏈表*\n”)；printff'*4.遍歷單鏈表中所有元素*\n”)；printff'*5.求單鏈表的長(zhǎng)度*\n”)；printff'*6.查找第i位元素*\n")；printff'*7.求x元素的存儲(chǔ)位置*\n")；printff'*8.在第i+l個(gè)元素前插入xprintff'*9.單鏈表單個(gè)結(jié)點(diǎn)的刪除*\n”)；printff'*10.用尾插法建立單鏈表*\n”)；printf("*printf^'*********************************************\n")?intabi’x,n』lag=l;LinkListp=LinkListlnit();LinkListq=LinkListlnit();〃創(chuàng)建指向鏈表的頭結(jié)點(diǎn)intlenJud;DataTypedata;while(flag)printf(H\n請(qǐng)輸入功能號(hào)n:\tH);scanf(吆(T&n);switch(n){casel:printf(HPleaseinputtennumbers:"”)；for(i=0;i<10;i++){scanf「％cT&a);LinkListlnsert(p,O,a);//在第一個(gè)元素前插入新結(jié)點(diǎn)}break;case2:LinkListClear(p); 〃清空單鏈表break;case3:jud=LinkListEmpty(p);if(jud) 〃檢查單鏈表是否為空printf("TheLinkListisempty!\n")；elseprintf("TheLinkListisnotempty!\nH)；break;case4:LinkListTraverse(p); 〃遍歷單鏈表中所有元素break;case5:len二LinkListLength(p);printf("ThelengthoftheLinkListis%d!\n"Jen);//求單鏈表的長(zhǎng)度break;case6:printf("請(qǐng)輸入i:\t")；scanf(,,%d,l,&i);data=LinkListGet(pJ);printf("The%dthelementoftheLinkListis%d!\rT丄data);//查找單鏈表中的第i位元素break;case7:printf("請(qǐng)輸入x:\t")；scanf(,,%d,l,&x);b=LinkListLocate(p,x);printf("The%disintheplaceoftheLinkList,%d!\n%b);〃查找單鏈表中的xbreak;case8:printf("請(qǐng)輸入元素a和位置i:\t")；scanf(H%d%d"/&a/&i);LinkListlnsert(p,i,a);〃在第i個(gè)元素前插入新結(jié)點(diǎn)break;case9:printf("請(qǐng)輸入x:\t")；scanf(,,%d,,,&x);LinkListDel(p,x); 〃刪除值為x的第一個(gè)元素break;case10:q=LinkListCreat(5); 〃用尾插法建立長(zhǎng)度為5的單鏈表printf(H遍歷當(dāng)前單鏈表的元素為：”)；LinkListTraverse(q); 〃遍歷單鏈表中所有元素}printff'是否繼續(xù)操作，是為1,否為0:\t”)；scanff”％d”,&flag);}return0;}程序流程圖

調(diào)試報(bào)告1.在執(zhí)行清空單鏈表的函數(shù)后，再執(zhí)行判斷空鏈表的函數(shù)時(shí)，輸出"TheLinkList

isnotempty!-,與預(yù)期實(shí)驗(yàn)結(jié)果不符，而編譯和組建時(shí)均為發(fā)出錯(cuò)誤和警告信號(hào)。后經(jīng)過(guò)單步運(yùn)行調(diào)試后，發(fā)現(xiàn)是清空單鏈表的函數(shù)出了問(wèn)題(while(q)循環(huán)語(yǔ)句出了問(wèn)題)，應(yīng)該把循環(huán)控制語(yǔ)句q改為p,修改完畢后現(xiàn)己得到正確結(jié)果"TheLinkListisempty!"。程序設(shè)計(jì)初期因沒(méi)有優(yōu)先考慮到用戶體驗(yàn)，造就了流水線的鏈表功能調(diào)用。經(jīng)老師提醒和建議，我乂在整理實(shí)驗(yàn)報(bào)告之前，在原來(lái)的程序基礎(chǔ)上添加了switch語(yǔ)句和while循環(huán)語(yǔ)句，以實(shí)現(xiàn)隨時(shí)調(diào)用。使用說(shuō)明■J"c:\Users\Administrator\Desktop\^^n1§^^finished\Debug\linklist.exe"單鏈表的定義和操作功能選擇與實(shí)現(xiàn)插：WW鏈懸i+表插頭六匚斷找X/第鏈尾-S闢嚟借1234567890表鏈素元V+空中長(zhǎng)霄零立建表為表的辟W建站單法功能選擇與實(shí)現(xiàn)插：WW鏈懸i+表插頭六匚斷找X/第鏈尾-S闢嚟借1234567890表鏈素元V+空中長(zhǎng)霄零立建表為表的辟W建站單法操作界而請(qǐng)輸入功能號(hào)n：1Pleaseinputtennunbers:0123456789TOC\o"1-5"\h\z是否繼續(xù)榻作，是為1,否為0： 1用頭插法建立十元素單鏈表請(qǐng)輸入功能號(hào)n：49876543210是否繼續(xù)操作，是為1,否為0： 1遍歷單鏈表中的所有元素請(qǐng)輸入功能號(hào)叭5ThelengthoftheLinkListis10?是否繼續(xù)爆作，是為1,否為「 1求單鏈表的長(zhǎng)度憧攢△功能號(hào)叭6i青端入讓 3The3thelementoftheLinkListis6?昱否繼續(xù)操作，是為1,否為0： 1查找第3位元素

求第一個(gè)元素值為5的位置在第5個(gè)元素前插入元素3幘輸入功能號(hào)n：求第一個(gè)元素值為5的位置在第5個(gè)元素前插入元素3幘輸入功能號(hào)n：498763543210區(qū)否繼續(xù)操作，是為「否為0: 1遍歷當(dāng)前單鏈表ThelengthoftheLinkListis11?昱否繼續(xù)爆作，是為1,否為「 1求當(dāng)前單鏈表的長(zhǎng)度廚f△功能號(hào)牡9情輸入x： 6[1否繼續(xù)操作，是知，否為0