數(shù)據(jù)結(jié)構(gòu)單鏈表

1、實驗一 單鏈表一、實驗?zāi)康?、掌握用 Vc+上機(jī)調(diào)試程序的基本方法；2、掌握單鏈表的建立、插入、刪除以及相關(guān)操作。二、 實驗內(nèi)容1、單鏈表的插入算法；2、單鏈表的刪除算法；3、兩個有序單鏈表合并成一個有序單鏈表的算法。三、實驗要求1、學(xué)生用 C+/C完成算法設(shè)計和程序設(shè)計并上機(jī)調(diào)試通過；2、撰寫實驗報告，提供實驗測試數(shù)據(jù)和實驗結(jié)果；3、分析算法，要求給出具體的算法分析結(jié)果，包括時間復(fù)雜度和空間復(fù)雜度， 并簡要給出算法設(shè)計小結(jié)和心得。四、實驗準(zhǔn)備1、復(fù)習(xí)C 語言中指針的用法，特別是結(jié)構(gòu)體的指針的用法；2、了解單鏈表的概念，單鏈表的定義方法；3、掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)基本操作：查找、插入、

2、刪除的算法； 在實現(xiàn)這些算法的時候，要注意判斷輸入數(shù)據(jù)的合法性，除此之外還要注意以 下內(nèi)容：在實現(xiàn)查找的時候，首先要判斷該單鏈表是否為空，其次要判斷查找后的結(jié)果 (查到時輸出查到的數(shù)據(jù)，未查到時給出錯誤提示 )。在實現(xiàn)插入的時候，由于是鏈?zhǔn)酱鎯?，它可以隨機(jī)產(chǎn)生和回收存儲空間，所以 它不要判斷線性表是否為滿， 但仍需判斷要插入的位置是否合法， 其次要注意插 入的時候語句的順序不可顛倒，否則出錯。在實現(xiàn)刪除的時候，首先要判斷線性表是否為空，為空則不能刪除；其次在刪 除后要回收空間。五、實驗步驟1、編程實現(xiàn)建立一個單鏈表，并在此表中插入一個元素和刪除一個元素5(1) 通過鍵盤讀取元素建立單鏈表；(2

3、) 指定一個位置，在此位置之前插入一個新元素；(3) 指定一個位置，刪除此位置元素。2、兩個有序單鏈表合并成一個有序單鏈表的算法。(1) 通過鍵盤讀取元素建立 2 個有序單鏈表；(2) 將二兩個有序單鏈表合并成一個有序單鏈表；(3) 輸出合并后的單鏈表。六、實驗參考代碼1、編程實現(xiàn)建立一個單鏈表，并在此表中插入一個元素和刪除一個元素 #include #include #define OK 1#define ERROR 0typedef int ElemType;typedef int Status; typedef struct Lnode ElemType data; struct Lno

4、de *next; Lnode,*LinkList;/ 以下是建立單鏈表 void CreatList_L(LinkList &head) LinkList tail, p;int n,i;p=(Lnode *)malloc(sizeof(Lnode); head=tail=p;head-next=NULL; printf(Please input length to creat a list:n); scanf(%d, &n);printf(Please input a group of values of the list:n); for(i=1;idata);p-next=NULL; t

5、ail-next=p; tail=p; printf(A list has been created successfully!n);/ 以下是輸出單鏈表 void OutputList_L(LinkList L) LinkList p = L-next;if(p=NULL) printf(n No listn);return; printf(The list is:n); while (p ) printf(%4d,p-data); p = p-next; printf(n);/ 在第 i個元素之前插入一個元素Status ListInsert_L(LinkList L, int i, El

6、emType e) LinkList p,s;p=L; int j=0; while(p&jnext; +j; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode); s-data=e;s-next=p-next; p-next=s; return OK;/ 刪除第 i 個元素Status ListDelete_L(LinkList L, int i, ElemType &e) LinkList p,q; p=L; int j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1) return ER

7、ROR; q=p-next;p-next=q-next; e=q-data;free(q);return OK;void main() LinkList L; int choice,i; ElemType e; choice=1;printf(We should create a list first!); CreatList_L(L);OutputList_L(L); while(choice!=0) printf(n menu n); printf( 1 insert a elem ); printf( 2 delete a elem ); printf( 3 output a list)

8、; printf( 4 exit );n);printf(n printf(please choice ( 1, 2, 3, 4);scanf(%d,&choice); if(choice=0) break;else if(choice=1) printf(Please input a pos and a value what you want to insert: n); scanf(%d%d, &i,&e);if(ListInsert_L(L,i,e) printf(The inserting action has been done!n);OutputList_L(L);else pri

9、ntf(The inserting pos is error! please do again!n);else if (choice=2)printf(Please input a pos what you want to delete:n); scanf(%d, &i);if(ListDelete_L(L,i,e)printf(The deleting action has been done, the deleted value is %dn,e);OutputList_L(L);else printf(The pos what you want to delete is error! p

10、lease do again!n);else if (choice=3)OutputList_L(L); else if(choice!=0)printf(choice errorn);2、兩個有序單鏈表合并成一個有序單鏈表的算法。實現(xiàn)提示：程序需要 3 個指針： pa,pb,pc，其中 pa，pb 分別指向 La表、 Lb 表的首結(jié)點，用 pa 遍歷 La 表， pb 遍歷 Lb 表， pc指向合并后的新表的最后一個結(jié)點(即尾結(jié)點)，pc的初值指向 La表的頭8結(jié)點。合并的思想是：先建立好兩個鏈表 La表和 Lb 表，然后依次掃描 La 和 Lb 中的元素，比較當(dāng) 前元素的值，將較小者鏈到

11、*pc 之后，如此重復(fù)直到 La 或 Lb 結(jié)束為止，再將另一個鏈表余 下的內(nèi)容鏈到 pc所指的結(jié)點之后。#include #include typedef int ElemType;typedef struct Lnode ElemType data;struct Lnode *next;Lnode,*LinkList;/ 以下是建立單鏈表void CreatList_L(LinkList &head) LinkList tail, p;int n,i;p=(Lnode *)malloc(sizeof(Lnode);head=tail=p; head-next=NULL;printf(Ple

12、ase input length to creat a list:n); scanf(%d, &n);printf(Please input a group of values of the list:n);for(i=1;idata); p-next=NULL;tail-next=p;tail=p;printf(A list has been created successfully!n);/ 以下是輸出單鏈表void OutputList_L(LinkList L)LinkList p = L-next;if(p=NULL)printf(n No listn);return; printf

13、(The list is:n);while (p ) printf(%4d,p-data);p = p-next;printf(n);/ 以下將 La 和 Lb 表合并為 Lc 表void MergeList(LinkList &Lc, LinkList &La, LinkList &Lb) LinkList pa, pb, pc;pa=La-next; pb=Lb-next;Lc=pc=La;while (pa&pb)if (pa-datadata) pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=papa:pb;free(Lb);/ 以下是主程序void main() LinkList La,Lb,Lc;printf(We should create two incremental and orderly lists first!n); printf(please creat a incremental and orderly li