單鏈表實(shí)驗(yàn)報(bào)告

單鏈表實(shí)驗(yàn)報(bào)告.z.計(jì)算機(jī)與信息技術(shù)學(xué)院綜合性、設(shè)計(jì)性實(shí)驗(yàn)報(bào)告專業(yè)：網(wǎng)絡(luò)工程年級(jí)/班級(jí)：大二2016—2017學(xué)年第一學(xué)期課程名稱數(shù)據(jù)構(gòu)造指導(dǎo)教師四**16083240**三工程名稱單鏈表的根本操作實(shí)驗(yàn)類型綜合性/設(shè)計(jì)性實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)地點(diǎn)216機(jī)房實(shí)驗(yàn)?zāi)康摹?〕熟悉順序表的創(chuàng)立、取值、查找、插入、刪除等算法，模塊化程序設(shè)計(jì)方法。實(shí)驗(yàn)儀器或設(shè)備〔1〕硬件設(shè)備：CPU為Pentium4以上的計(jì)算機(jī)，存2G以上〔2〕配置軟件：MicrosoftWindows7與VC++6.0總體設(shè)計(jì)〔設(shè)計(jì)原理、設(shè)計(jì)方案及流程等〕設(shè)計(jì)原理：?jiǎn)捂湵韺儆诰€性表，線性表的存儲(chǔ)構(gòu)造的特點(diǎn)是：用一組任意存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。因此，對(duì)于*個(gè)元素來(lái)說(shuō)，不僅需要存儲(chǔ)其本身的信息，還需要存儲(chǔ)一個(gè)指示其直接后繼的信息。設(shè)計(jì)方案：采用模塊化設(shè)計(jì)的方法，設(shè)計(jì)各個(gè)程序段，最終通過(guò)主函數(shù)實(shí)現(xiàn)各個(gè)程序段的功能。設(shè)計(jì)時(shí)，需要考慮用戶輸入非法數(shù)值，所以要在程序中寫(xiě)入說(shuō)可以處理非法數(shù)值的代碼。設(shè)計(jì)流程：引入所需的頭文件；單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第1頁(yè)。定義狀態(tài)值；單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第1頁(yè)。寫(xiě)入順序表的各種操作的代碼；寫(xiě)入主函數(shù)，分別調(diào)用各個(gè)函數(shù)。在調(diào)用函數(shù)時(shí)，采用if構(gòu)造進(jìn)展判斷輸入值是否非法，從而執(zhí)行相應(yīng)的程序?qū)嶒?yàn)步驟〔包括主要步驟、代碼分析等〕*include<stdio.h>//EOF(=^Z或F6),NULL*include<stdlib.h>//srand(),rand(),e*it(n)*include<malloc.h>//malloc(),alloc(),realloc()等*include<limits.h>//INT_MA*等*include<string.h>*include<ctype.h>*include<math.h>//floor(),ceil(),abs()*include<iostream.h>//cout,cin*include<time.h>//clock(),CLK_TCK,clock_t*defineTRUE1*defineFALSE0*defineOK1*defineERROR0*defineINFEASIBLE-1*defineOVERFLOW-2typedefintStatus;//Status是函數(shù)的類型,//其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等typedefintElemType;typedefstructLNode{ElemTypedata;//結(jié)點(diǎn)的數(shù)據(jù)域structLNode*ne*t;//結(jié)點(diǎn)的指針域}LNode,*LinkList;//LinkList為指向構(gòu)造體LNode的指針類型//初始化單鏈表算法步驟：生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的指針域置空。StatusInitList_L(LinkList&L){L=newLNode;//生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)；L->ne*t=NULL;//頭結(jié)點(diǎn)的指針域置空returnOK;}//單鏈表的取值算法步驟：?jiǎn)捂湵韺?shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第2頁(yè)。用指針P指首元結(jié)點(diǎn)，用j做計(jì)數(shù)器初值賦為1.單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第2頁(yè)。從首元結(jié)點(diǎn)開(kāi)場(chǎng)依次順著鏈域ne*t向下訪問(wèn)，只要指向當(dāng)前結(jié)點(diǎn)的指針p不為空〔NULL〕，并且沒(méi)有到達(dá)序號(hào)為i的結(jié)點(diǎn)，則循環(huán)執(zhí)行以下操作：P指向下一結(jié)點(diǎn)；計(jì)數(shù)器j相應(yīng)加1；3.退出循環(huán)時(shí)，如果指針p為空，或者計(jì)數(shù)器j大于i，說(shuō)明指定的序號(hào)i值不合法〔i大于表長(zhǎng)n或i小于等于0〕，取值失敗返回ERROR，否則取值成功，此時(shí)j=i時(shí)，p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)，用參數(shù)e保存當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域，返回OK。StatusGetElem_L(LinkListL,inti,ElemType&e){ LinkListp; intj; p=L->ne*t; j=1; while(p&&j<i) { p=p->ne*t; ++j; } if(!p||j>i)returnERROR; e=p->data; returnOK;}//單鏈表的按值查找算法步驟：用指針p指首元結(jié)點(diǎn)。從首元結(jié)點(diǎn)開(kāi)場(chǎng)依次順著鏈域ne*t向下查找，只要指向當(dāng)前結(jié)點(diǎn)的指針p不為空，并且p所指結(jié)點(diǎn)的數(shù)據(jù)域不等于給定值e，則循環(huán)執(zhí)行以下操作：p指向下一個(gè)結(jié)點(diǎn)。返回p。假設(shè)查找成功，p此時(shí)即為結(jié)點(diǎn)的地址值，假設(shè)查找失敗，p的值即為NULL。intLocateElem_L(LinkListL,ElemTypee){ LinkListp; intj; p=L->ne*t; j=1; while(p&&p->data!=e) { p=p->ne*t; j++; } if(p)returnj; elsereturn0;}單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第3頁(yè)。//單鏈表的插入單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第3頁(yè)。算法步驟：查找結(jié)點(diǎn)ai-1并由指針p指向該結(jié)點(diǎn)。生成一個(gè)新結(jié)點(diǎn)*s。將新結(jié)點(diǎn)*s的數(shù)據(jù)域置為e。將新結(jié)點(diǎn)*s的指針域指向結(jié)點(diǎn)ai。將結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)*s。StatusListInsert_L(LinkList&L,inti,ElemTypee){ LinkListp=L,s; intj=0; while(p&&(j<i-1)) { p=p->ne*t; ++j; } if(!p||j>i-1) { returnERROR; } s=newLNode; s->data=e; s->ne*t=p->ne*t; p->ne*t=s; returnOK;}//單鏈表的刪除查找結(jié)點(diǎn)ai-1并由指針p指向該結(jié)點(diǎn)。臨時(shí)保存待刪除結(jié)點(diǎn)ai的地址在q中，以備釋放。將結(jié)點(diǎn)*p的指針域指向ai的直接后繼結(jié)點(diǎn)。釋放結(jié)點(diǎn)ai的空間。StatusListDelete_L(LinkList&L,inti){ LinkListp=L,q; intj=0; while((p->ne*t)&&(j<i-1)) { p=p->ne*t; ++j; } if((!p->ne*t)||(j>i-1)) { returnERROR; }單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第4頁(yè)。 q=p->ne*t;單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第4頁(yè)。 p->ne*t=q->ne*t; deleteq; returnOK;}//單鏈表的輸出算法步驟：將指針p指向L的ne*t域。輸出p指針的數(shù)據(jù)。將指針p后移。循環(huán)第2,3步，直到p指針為空〔NULL〕。voidListPrint_L(LinkListL){ LinkListp; p=L->ne*t; do { printf("%5d",p->data); p=p->ne*t; }while(p);}voidmain(){ inti,n,e; LinkListL; if(InitList_L(L));printf("單鏈表創(chuàng)立成功！\n");printf("請(qǐng)輸入您要輸入的數(shù)據(jù)個(gè)數(shù)n:\n");scanf("%d",&n);printf("請(qǐng)輸入您要輸入的數(shù)據(jù)：\n");for(i=1;i<=n;i++) { scanf("%d",&e); ListInsert_L(L,i,e); }printf("當(dāng)前單鏈表的容為：\n");ListPrint_L(L); printf("\n");printf("請(qǐng)輸入您要插入的數(shù)據(jù)e及其位置i，使用空格鍵隔開(kāi):\n");scanf("%d%d",&e,&i); if(ListInsert_L(L,i,e)) {printf("當(dāng)前單鏈表的容為：\n");ListPrint_L(L);單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第5頁(yè)。 }單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第5頁(yè)。 else {printf("i值越界！\n"); } printf("\n");printf("請(qǐng)輸入您要取的數(shù)據(jù)序號(hào)：\n");scanf("%d",&i); if(GetElem_L(L,i,e)) {printf("第%d位數(shù)據(jù)的值為:%d\n",i,e); }else {printf("i值越界！\n"); }printf("請(qǐng)輸入要查找的數(shù)據(jù)值：\n");scanf("%d",&e); if(!LocateElem_L(L,e)) {printf("查無(wú)此值!\n"); }else {printf("數(shù)據(jù)%d在%d號(hào)位置\n",e,LocateElem_L(L,e)); }printf("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)的序號(hào)：\n");scanf("%d",&i); if(ListDelete_L(L,i)) {printf("刪除后單鏈表的容為：\n");ListPrint_L(L); } else {printf("輸入有誤！"); }printf("\n");}結(jié)果分析與總結(jié)圖1單鏈表實(shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第6頁(yè)。結(jié)果分析：?jiǎn)捂湵韺?shí)驗(yàn)報(bào)告全文共7頁(yè)，當(dāng)前為第6頁(yè)。如圖1所示，輸入正確數(shù)據(jù)時(shí)，程序各個(gè)功能執(zhí)行正常。設(shè)置輸入數(shù)據(jù)個(gè)數(shù)為5，可以輸入5個(gè)數(shù)據(jù)，按回車(chē)后，可以顯示我們當(dāng)前單鏈表中的數(shù)據(jù)容。繼續(xù)輸入下一指令：輸入要插入的數(shù)據(jù)及位置，使用空格鍵隔開(kāi)，回車(chē)后，可以看到已經(jīng)成功插入。繼續(xù)輸入所取的數(shù)據(jù)序號(hào)