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

單鏈表的定義和操作

實驗報告單鏈表的定義和操作實驗報告實驗名稱單鏈表的定義和操作實驗?zāi)康氖煜語言的上機環(huán)境。掌握C語言的基本結(jié)構(gòu)；7定*單需車走的結(jié)占舉型?3：熟悉對單鏈表禹賃體函菽定義和一些基本操作；4.通過對單鏈表的定義掌握線性表的鏈式存儲結(jié)構(gòu)的特點。實驗內(nèi)容編制一個演示單鏈表插入、刪除、查找等操作的程序。問題描述用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識，實現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結(jié)構(gòu)類型以及對單鏈表操作的具體的函數(shù)定義（包括：初始化單鏈表、清空單鏈表、檢查單鏈表是否為空、遍歷單鏈表、求單鏈表的長度、從單鏈表表中查找元素、從單鏈表表中查找與給定元素值相同的元素在鏈表中的位置、向單鏈表中插入元素、從單鏈表中刪除元素、用尾插法建立單鏈表）。問題分析該實驗是基于C語言和數(shù)據(jù)結(jié)構(gòu)知識基礎(chǔ)的對單鏈表的基本操作的檢驗，無需設(shè)計復(fù)雜的算法，程序語句也相對簡單。因此，我直接按要求定義了對單鏈表操作的具體函數(shù)，并于主函數(shù)中實現(xiàn)對應(yīng)的功能調(diào)用，其中，功能選擇靠switch語句實現(xiàn)。實驗步驟需求分析本演示程序用VC++編寫，完成單鏈表的生成，任意位置的插入、刪除，以及確定某一元素在單鏈表中的位置等操作。輸入的形式和輸入值的范圍：插入元素時需要輸入插入的位置和元素的值；刪除元素時輸入刪除元素的位置；查找操作時需要輸入元素的值。在所有輸入中,元素的值都是整數(shù)。輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內(nèi)容。其中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。程序所能達到的功能：完成單鏈表的生成(通過插入操作)、插入、刪除、查找等操作。測試數(shù)據(jù)：插入操作中依次輸入0,1,2,3,4,5,6,789生成一個單鏈表概要設(shè)計1)為了實現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：ADTLinkList{數(shù)據(jù)對象：D={ai|aiIntegerSet,i=0,l,2,…,n,n$0}數(shù)據(jù)關(guān)系：R={<ai,ai+l>|aizai+lGD}基本操作：VoidListinsertfLinkListIJnti,DataTypex)初始條件：單鏈表I己存在操作結(jié)果：將元素x插入到單鏈表I的i位置VoidListDelfLinkListI^DataTypex)初始條件：單鏈表I己存在操作結(jié)果：將單鏈表L中值為x的元素刪除intListGetfLinkListLQataTypex)初始條件：單鏈表I依存在操作結(jié)果：單鏈表I中查找是否元素x,若存在，返回元素在表中的位置2)本程序包含7個函數(shù)：①主函數(shù)main()②清空單鏈表函數(shù)LinkedListClear()③檢查單鏈表是否為空函數(shù)LinkedListEmptyf)④遍歷單鏈表函數(shù)LinkedListT「averse()⑤求單鏈表的長度函數(shù)LinkedListLength()@從單鏈表表中查找元素函數(shù)LinkedListGet()@查找與給定元素的位置函數(shù)LinkedListLocateO?插入元素函數(shù)LinkedListlnsert()?刪除元素函數(shù)LinkedListDelf)⑩用尾插法建立單鏈表函數(shù)LinkedListCreat()函數(shù)說明#include<stdio.h>#include<malloc.h>#include<stdlib.h>#defineFALSE0〃邏輯值#defineTRUE1〃邏輯值typedefintDataType;structNode 〃鏈表的結(jié)點類型{DataTypedata;structNode*next;};typedefstructNode*PNode; 〃指向結(jié)點指針typedefstructNode*LinkList;//指向鏈表指針〃創(chuàng)建空單鏈表：帶頭結(jié)點的空鏈表LinkListLinkListlnit()LinkListp;p=(LinkList)malloc(sizeof(structNode));//為表頭結(jié)點申請空間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");}〃求單鏈表的長度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元素的存儲位置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個元素前插入值為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;}}〃單鏈表單個結(jié)點的刪除voidLinkListDel(LinkListLDataTypex){PNodep,q;P=l；while(p->next!=NULL&&p?>next?>data!=x)〃查找x的前驅(qū)p=p->next;if(p->next==NULL)//沒找到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"*功能選擇與實現(xiàn)printf("*printff"*1?用頭插法建立十元素單鏈表*\n”)；printff"*2.清空單鏈表*\n”)；printff'*3.判斷是否為空鏈表*\n”)；printff'*4.遍歷單鏈表中所有元素*\n”)；printff'*5.求單鏈表的長度*\n”)；printff'*6.查找第i位元素*\n")；printff'*7.求x元素的存儲位置*\n")；printff'*8.在第i+l個元素前插入xprintff'*9.單鏈表單個結(jié)點的刪除*\n”)；printff'*10.用尾插法建立單鏈表*\n”)；printf("*printf^'*********************************************\n")?intabi’x,n』lag=l;LinkListp=LinkListlnit();LinkListq=LinkListlnit();〃創(chuàng)建指向鏈表的頭結(jié)點intlenJud;DataTypedata;while(flag)printf(H\n請輸入功能號n:\tH);scanf(吆(T&n);switch(n){casel:printf(HPleaseinputtennumbers:"”)；for(i=0;i<10;i++){scanf「％cT&a);LinkListlnsert(p,O,a);//在第一個元素前插入新結(jié)點}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);//求單鏈表的長度break;case6:printf("請輸入i:\t")；scanf(,,%d,l,&i);data=LinkListGet(pJ);printf("The%dthelementoftheLinkListis%d!\rT丄data);//查找單鏈表中的第i位元素break;case7:printf("請輸入x:\t")；scanf(,,%d,l,&x);b=LinkListLocate(p,x);printf("The%disintheplaceoftheLinkList,%d!\n%b);〃查找單鏈表中的xbreak;case8:printf("請輸入元素a和位置i:\t")；scanf(H%d%d"/&a/&i);LinkListlnsert(p,i,a);〃在第i個元素前插入新結(jié)點break;case9:printf("請輸入x:\t")；scanf(,,%d,,,&x);LinkListDel(p,x); 〃刪除值為x的第一個元素break;case10:q=LinkListCreat(5); 〃用尾插法建立長度為5的單鏈表printf(H遍歷當前單鏈表的元素為：”)；LinkListTraverse(q); 〃遍歷單鏈表中所有元素}printff'是否繼續(xù)操作，是為1,否為0:\t”)；scanff”％d”,&flag);}return0;}程序流程圖

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

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

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