1、單鏈表的定義及基本操作一、實驗目的、意義（1）理解線性表中帶頭結點單鏈表的定義和邏輯圖表示方法。（2）熟練掌握單鏈表的插入，刪除和查詢算法的設計與實現(xiàn)。（3）根據具體問題的需要，設計出合理的表示數據的鏈表結構，并設計相關算法二、實驗容及要求說明1：本次實驗中的鏈表結構均為帶頭結點的單鏈表。說明2:學生在上機實驗時，需要自己設計出所涉及到的函數，同時設計多組輸 入數據并編寫主程序分別調用這些函數，調試程序并對相應的輸出作出分析；修 改輸入數據，預期輸出并驗證輸出的結果，加深對有關算法的理解。具體要求：建立單鏈表，完成鏈表（帶表頭結點）的基本操作：建立鏈表、插入、刪除、 查找、輸出；其它基本操作還

2、有銷毀鏈表、將鏈表置為空表、求鏈表的長度、獲 取某位置結點的容、搜索結點。三、實驗所涉及的知識點數據結構、C語言語法函數、結構體類型指針、單鏈表（建表、初始化鏈表、求表長、插入、刪除、查詢算法）等。四、實驗結果及分析（所輸入的數據及相應的運行結果，運行結果要有提示信息，運行結果采用截圖 方式給出。）五、總結與體會（調試程序的心得與體會，若實驗課上未完成調試，要認真找出錯誤并分析原因 等。調試程序時，出現(xiàn)了許多錯誤。如：結構體類型指針出錯，忽略了釋 放存儲空間，對頭插法建表、尾插法建表不熟悉等。另外還有一些語 法上的錯誤。由于對所學知識點概念模糊，試驗課上未能完成此次上 機作業(yè)。后來經過查閱教材

3、，瀏覽網頁等方式，才完成試驗。這次試 驗出現(xiàn)錯誤最重要的原因就是對課本知識點理解不深刻以及編寫代碼 時的粗心。以后要都去練習、實踐，以完善自己的不足。六、程序清單（包含注釋）/單鏈表#in clude<stdio.h>#in clude<malloc.h> #defi ne OK 1#defi ne ERROR 0typedef char ElemType;typedef int Status;/線性表的單鏈表的存儲結構typedef struct LNodeElemType data;struct LNode *n ext;LNode,*Li nkList;/Li n

4、kList為結構體類型的指針，可以直接定義變量，比如Lin kList p ;/建表(頭插法)void CreatListF(Li nkList & L,ElemType a,i nt n)/初始化線性表L=(Li nkList)malloc(sizeof(LNode);分配存空間L-> next=NULL;/在表中插入元素Lin kList S;int i;/頭插法for(i=0;i< n;i+)S=(L in kList)malloc(sizeof(LNode);/生成新結點S->data=ai;數據域S->n ext=L->n ext;L->n

5、 ext=S;/建表(尾插法)void CreatListR(L in kList & L,ElemType a,i nt n).下載可編輯.L=(L in kList)malloc(sizeof(LNode);L-> next=NULL;Lin kList p;p=L;Lin kList S;int i;/尾插法for(i=0;i< n;i+)S=(L in kList)malloc(sizeof(LNode);S->data=ai;p_>n ext=S;P=S;p-> next=NULL;/初始化線性表void In itList(L in kList

6、 &L)L=(L in kList)malloc(sizeof(LNode);L-> next=NULL;/獲得鏈表元素Status GetElem(L in kList L,i nt i,ElemType &e)/L為帶頭結點的單鏈表的頭指針Lin kList p;int j;/初始化，p指向第一個結點p=L->n ext;/j為計數器.下載可編輯.j=1;順指針往后查找，直到p指向第i個元素或p為空while(p && j<i)p=p->n ext;j+；/第i個元素不存在if(!p II j>i)return ERROR;/取

7、第i個元素e=p_>data;return OK;II插入Status List In sert(L in kList &L,i nt i,ElemType e)int j=0;Lin kList p;p=L;個結點生成新結點while(p!=NULL && j<i-1)II 找第 i-1p=p->n ext;j+;if(!p II j>i-1)return ERROR;Lin kList S;S=(Li nkList)malloc(sizeof(LNode);S->data=e;S->n ext=p->n ext;.下載可編輯

8、.p->n ext=S;return OK;/刪除Status ListDelete(LinkList &L,int i,ElemType &e)Lin kList p;Lin kList q;int j=0;p=L;while(p->next)!=NULL && j<i-1)找第 i 個結點p=p->n ext;j+;個元素不存在）/!(p->next):指向第i個結點的指針為空(第iif(!(p-> next) | j>i-1)return ERROR;q=p->n ext;p_>n ext=q _>

9、;n ext;e=q_>data;free(q);return OK;/求表的長度int ListLe ngth(L in kList L)Lin kList p;p=L;int j=0;/線性鏈表最后一個結點的指針為空.下載可編輯.while(p-> next)!=NULL)j+；p=p->n ext;return j;/輸出void visit(L in kList L)Lin kList p;p=L->n ext;while(p!=NULL)prin tf("%c ”,p->data);p=p->n ext;free/銷毀：要銷毀的話從頭結點

10、開始依次free但要先得到下一個節(jié)點再void DestroyList(LinkList &L)Lin kList p;Lin kList q;p=L;q=p->n ext;while(p!=NULL)free(p);p=q;q=p->n ext;/ free(p);/判空int ListEmpty(L in kList L)return 0/為空表則執(zhí)行該語句，否則返回return (L-> next=NULL);/查找int ListSearch(L in kList L,ElemType e)Lin kList p;p=L->n ext;int i=1;w

11、hile(p!=NULL && p->data!=e)p=p->n ext;i+;if(p=NULL)return 0;return i;int mai n()ElemType e;ElemType a 6='a','b','c','d','e','f;Lin kList L;鏈表的頭指針printf("頭插法建表：");CreatListF(L,a,6);.下載可編輯.visit(L);prin tf("nn");/初始化Ini tLis

12、t(L);printf(”初始化后的表：”)；visit(L);prin tf("nn");printf("尾插法建表：");CreatListR(L,a,6);visit(L);prin tf("nn");/初始化后表為空，此時不要調用GetElem()GetElem(L,3,e);printf(" 表中第3個元素為：”)；prin tf("%c nn",e);/在第5個位置插入字符'k'ListI nsert(L,5,'k');printf(”在表中第5個位置插入字符'k'后：”);visit(L);prin tf("nn");p