單鏈表實驗報告

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

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

3、e<stdio.h> / EOF(=Z或 F6),NULL#include<stdlib.h> / srand( ) ,rand( ),exit(n)#include<malloc.h> / malloc( ),alloc( ),realloc( )等#include<limits.h> / INT_MAX等#include<string.h>#include<ctype.h>#include<math.h> / floor(),ceil( ),abs( )#include<iostream.h>

4、/ cout,cin#include<time.h> / clock( ),CLK_TCK,clock_t#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;/ Status是函數(shù)的類型 ,/ 其值是函數(shù)結果狀態(tài)代碼，如OK等typedefintElemType;typedef struct LNodeElemType data;/結點的數(shù)據(jù)域struct LNode *next; /結點的指針域LNode,*LinkList;/Li

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

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

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

8、t;j+;if(p) return j;else return 0;/ 單鏈表的插入算法步驟：1. 查找結點 ai-1 并由指針 p 指向該結點。2. 生成一個新結點 *s 。3. 將新結點 *s 的數(shù)據(jù)域置為 e。4. 將新結點 *s 的指針域指向結點 ai 。5.將結點 *p 的指針域指向新結點*s 。Status ListInsert_L(LinkList &L,int i,ElemType e)LinkList p=L,s;int j=0;while(p&&(j<i-1)p=p->next;+j;if(!p|j>i-1)return ERROR

9、;s=new LNode;s->data=e;s->next=p->next;p->next=s;return OK;/ 單鏈表的刪除1. 查找結點 ai-1 并由指針 p 指向該結點。2. 臨時保存待刪除結點 ai 的地址在 q 中，以備釋放。3. 將結點 *p 的指針域指向 ai 的直接后繼結點。4. 釋放結點 ai 的空間。Status ListDelete_L(LinkList &L,int i)LinkList p=L,q;int j=0;while(p->next)&&(j<i-1)p=p->next;+j;if(!

10、p->next)|(j>i-1)return ERROR;q=p->next;p->next=q->next;delete q;return OK;/ 單鏈表的輸出算法步驟：1. 將指針 p 指向 L 的 next 域。2. 輸出 p 指針的數(shù)據(jù)。3. 將指針 p 后移。4. 循環(huán)第 2,3 步，直到 p 指針為空（ NULL）。void ListPrint_L(LinkList L)LinkList p;p=L->next;doprintf("%5d",p->data);p=p->next;while(p);void mai

11、n()int i,n,e;LinkList L;if(InitList_L(L);printf("單鏈表創(chuàng)建成功！n");printf("請輸入您要輸入的數(shù)據(jù)個數(shù)n:n");scanf("%d",&n);printf("請輸入您要輸入的數(shù)據(jù)：n");for(i=1;i<=n;i+)scanf("%d",&e);ListInsert_L(L,i,e);printf("當前單鏈表的內(nèi)容為：n");ListPrint_L(L);printf("n&q

12、uot;);printf("請輸入您要插入的數(shù)據(jù)e 及其位置i ，使用空格鍵隔開:n");scanf("%d %d",&e,&i);if(ListInsert_L(L,i,e)printf("當前單鏈表的內(nèi)容為：n");ListPrint_L(L);elseprintf("i值越界！ n");printf("n");printf("請輸入您要取的數(shù)據(jù)序號：n");scanf("%d",&i);if(GetElem_L(L,i,e)p

13、rintf("第 %d位數(shù)據(jù)的值為 :%dn",i,e);elseprintf("i值越界！ n");printf("請輸入要查找的數(shù)據(jù)值：n");scanf("%d",&e);if(!LocateElem_L(L,e)printf("查無此值 !n");elseprintf("數(shù)據(jù) %d在 %d號位置 n",e,LocateElem_L(L,e);printf("請輸入要刪除的數(shù)據(jù)的序號：n");scanf("%d",&i);if(ListDelete_L(L,i)printf("刪除后單鏈表的內(nèi)容為：n");ListPrint_L(L);elseprintf("輸入有誤！ ");printf("n");五、結果分析與總結圖 1結果分析：如圖 1 所示，輸入正確數(shù)據(jù)時，程序各個功能執(zhí)行正常。 設置輸入數(shù)據(jù)個數(shù)為 5，可以輸入 5 個數(shù)據(jù)，按回車后，可以顯示我們當前單鏈表中的數(shù)據(jù)內(nèi)容。 繼續(xù)輸入下一指令：輸入要插入的數(shù)據(jù)及位置，使用空格