單鏈表試驗報告

1、計算機(jī)與信息技術(shù)學(xué)院綜合性、設(shè)計性實驗報告專業(yè)：網(wǎng)絡(luò)工程年級/班級：大二2016-2017學(xué)年第一學(xué)期0課程名稱數(shù)據(jù)結(jié)構(gòu)指導(dǎo)教師李四學(xué)號姓名16083240XX 張三項目名稱單鏈表的基本操作實驗類型綜合性/設(shè)計性實驗時間2017.10.3實驗地點216機(jī)房一、實驗?zāi)康?1)熟悉順序表的創(chuàng)建、取值、查找、插入、刪除等算法，模塊化程序設(shè)計方法。CPU為Pentium 4以上的計二、實驗儀器或設(shè)備(1) 硬件設(shè)備：算機(jī)，內(nèi)存2G以上(2) 配置軟件：Microsoft Windows 7 與 VC+6.0總體設(shè)計(設(shè)計原理、設(shè)計方案及流程等)設(shè)計原理：單鏈表屬于線性表，線性表的存儲結(jié)構(gòu)的特點是：用一

2、組任意存儲單元存儲線性 表的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。因此，對于某 個元素來說，不僅需要存儲其本身的信息，還需要存儲一個指示其直接后繼的信 息。設(shè)計方案：采用模塊化設(shè)計的方法，設(shè)計各個程序段，最終通過主函數(shù)實現(xiàn)各個程序段的功 能。設(shè)計時，需要考慮用戶輸入非法數(shù)值，所以要在程序中寫入說可以處理非法 數(shù)值的代碼。設(shè)計流程：1. 引入所需的頭文件；2. 定義狀態(tài)值；3. 寫入順序表的各種操作的代碼；寫入主函數(shù)，分別調(diào)用各個函數(shù)。在調(diào)用函數(shù)時，采用if結(jié)構(gòu)進(jìn)行判斷輸四、入值是否非法，從而執(zhí)行相應(yīng)的程序 實驗步驟(包括主要步驟、代碼分析等)#include<stdio.

3、h> / EOF(=*2或 F6),NULL#in clude<stdlib.h> / srand() ,rand( ),exil (n)#in clude<malloc.h> malloc( ),alloc( )/ealloc()#in clude<!imits.h> / INT_MAX 等#in clude<sth ngh>#in clude<ctypeh>#in clude<math.h> / floor(),ceil( ),abs()#in clude<iostream.h> / cout,ci

4、n#in clude<lime.h> / clock( ),CLK_TCK,clock_t#defi ne TRUE#defi ne FALSE#defi ne OK#defi ne ERROR 0#defi ne INFEASIBLE-1#define OVERFLOW -2 typedef int Status： / Status 其值是函數(shù)結(jié)果狀態(tài)代碼，如 typedef int ElemType; typedef struct LNode <OK等是函數(shù)的類型ElemType data; / struct LNode *next;/ LNode/LinkList： /

5、LinkList /初始化單鏈表結(jié)點的數(shù)據(jù)域結(jié)點的指針域為指向結(jié)構(gòu)體LNode的指針類型算法步驟：1.生成新結(jié)點作為頭結(jié)點，用頭指針L指向頭結(jié)點。2頭結(jié)點的指針域置空。Status lnilList_L(LinkList &L)L=new LNode; L->next=NULL;/生成新結(jié)點作為頭結(jié)點，用頭指針L指向頭結(jié)點;/頭結(jié)點的指針域置空return OK：/單鏈表的取值算法步驟：1. 用指針P指首元結(jié)點，用j做計數(shù)器初值賦為1.2. 從首元結(jié)點開始依次順著鏈域next向下訪問，只要指向當(dāng)前結(jié)點的指針(.NULL.井且沒有到達(dá)序號為i的結(jié)點，則循環(huán)執(zhí)行以下操作：P指向下一結(jié)

6、點；p不為空計數(shù)器j相應(yīng)加1;3.退出循壞時，如果指針p為空，或者計數(shù)器j大于i .說明指定的序號i值不合法(i大于表長 n或i小于等于0),取值失敗返回ERROR否則取值成功，此時pi時，p所指的結(jié)點就是要找的第i 個結(jié)點，用參數(shù)e保存當(dāng)前結(jié)點的數(shù)據(jù)域，返回0K。Status GelElenri_L(LinkList L, int i, ElemType &e) <LinkList p; intj; p=L> next;j=1； while(p&&jvi)p=p>next; +j；if(!p|j>i) return ERROR;e=p->

7、data;return OK：/單鏈表的按值查找算法步驟：1.用指針P指首元結(jié)點。2從首元結(jié)點開始依次順著鏈域next向下查找，只要指向當(dāng)前結(jié)點的指針P不為空，并且P3所指結(jié)點的數(shù)據(jù)域不等于給定值 點a3.返回P。若查找成功.P此時即為結(jié)點的地址值.若查找失敗，P的值即為NULL。 泊 t LocateElem_LLinkList L,ElemT ype e)&則循環(huán)執(zhí)行以下操作：P指向下一個結(jié)LinkList p; int j： p=L> next;j=1:while( P&&p->data!=e)p=p>next; j卄；if(p) return;

8、 else return 0;/單鏈表的插入算法步驟：1.查找結(jié)點a“并由指針P指向該結(jié)點。234生成一個新結(jié)點*S O將新結(jié)點*s的數(shù)據(jù)域置為e將新結(jié)點*s的指針域指向結(jié)點 a.。 將結(jié)點*p的指針域指向新結(jié)點*s 5Status Listlnsert_L(LinkList &L,int i.ElemType e)LinkList p=L,s; intj=O;while(p&&G<i-1)p=p>next; +j；return ERROR：s=new LNode： s->data=e： s>next=p->next： p->next

9、=s;return OK;/單鏈表的刪除1.查找結(jié)點并由指針p指向該結(jié)點。2臨時保存待刪除結(jié)點 a的地址在q中，以備釋放。將結(jié)點y的指針域指向a的直接后繼結(jié)點。釋放結(jié)點a的空間。Status LislDelete_L(Li nkList & LJ nl i)LinkList p=L,q;345intj=O;while(p->next)&&( </)p=p>next; +j；if(!p->nexl)|G>i-1) (return ERROR;q=p->next; p->next=q->next; delete q;retur

10、n OK;/單鏈表的輸出算法步驟：1.將指針P指向L的next域。輸出P指針的數(shù)據(jù)。將指針P后移。循環(huán)第2,3步，直到P指針為空(NULL)。234void ListPrint_L(LinkList L)LinkLisI p; p=L->next： do (phntf("%5d"p->data); p=p->n ext;while(p);void main()int i,n,e; LinkLisI L： if(lnitList_L(L);printfC單鏈表創(chuàng)建成功！ n");printfC請輸入您要輸入的數(shù)據(jù)個數(shù)n:n"); scan

11、fC'%d'&n); printf("請輸入您要輸入的數(shù)據(jù)：n”)；for(i=1;iv=n;i+)(scanf("%d",&e)： Listlnsert_LLj,e);printfC當(dāng)前單鏈表的內(nèi)容為：n");ListP rint_L(L)：printf("n")；printfC請輸入您要插入的數(shù)據(jù)e及其位置i,使用空格鍵隔開 scanf("%d %d：&e,&i);if(Lisllnsert_L(LJ,e)phntfC'當(dāng)前單鏈表的內(nèi)容為：'nJ; List

12、Print_L(L);elseprintfC'i 值越界！ n");printf("n")；printf("請輸入您要取的數(shù)據(jù)序號：n”); scan f(”cr,&);if(GetElem_L(LJ,e)printfC 第4位數(shù)據(jù)的值為：dnT,e);elseprintfC'i 值越界！ n")；printfC請輸入要查找的數(shù)據(jù)值：n”); scanfC'%d&e)： if(!LocateElem_L(L,e)printfC 查無此值！rf);elseprintf(”數(shù)據(jù) (:在 d 號位置 n'

13、;e,LocateElem_L(L,e);phn tf(-請輸入要刪除的數(shù)據(jù)的序號:n")scan fC%d &);if(LislDelete_L(LJ)printfC刪除后單鏈表的內(nèi)容為：rf);ListPri nt_L(L);elsephntfC'輸入有誤！ J;phn tf( Jn ”);五、結(jié)果分析與總結(jié)9Sj?*»眾的胃容為，U 141928754輪MEMM入的（位JLft用Sft93耳:耳衣的內(nèi)»為|13141961287513 H 1961 7S” Any to ewtinu*結(jié)果分析：如圖1所示，輸入正確數(shù)據(jù)時，程序各個功能執(zhí)行正常。設(shè)置輸入數(shù)據(jù)個數(shù)為5,可 以輸入5個數(shù)據(jù)，按回車后，可以顯示我們當(dāng)前單鏈表中的數(shù)據(jù)內(nèi)容。繼續(xù)輸入下 一指令：輸入要插入的數(shù)據(jù)及位置，使用空格鍵隔開，回車后，可以看到已經(jīng)成功 插入。繼續(xù)輸入所取的數(shù)據(jù)序號，可以查找該數(shù)據(jù)的值。輸入要查找的數(shù)據(jù)，可