單鏈表的定義及基本操作

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

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

3、。這次試驗出現(xiàn)錯誤最重要的原因就是對課本知識點理解不深刻以及編寫代碼時的粗心。以后要都去練習、實踐，以完善自己的缺乏。六、程序清單(包含注釋)/單鏈表#include<stdio.h>#include<malloc.h>#define OK 1#define ERROR 0typedef char ElemType;typedef int Status;/線性表的單鏈表的存儲結(jié)構(gòu)typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/LinkList為結(jié)構(gòu)體類型的指針，可以直接定義變量，

4、比方LinkList p；/建表頭插法void CreatListF(LinkList &L,ElemType a,int n)/初始化線性表L=(LinkList)malloc(sizeof(LNode);/分配內(nèi)存空間L->next=NULL;/在表中插入元素LinkList S;int i;/頭插法for(i=0;i<n;i+)S=(LinkList)malloc(sizeof(LNode);/生成新結(jié)點S->data=ai;/數(shù)據(jù)域S->next=L->next;L->next=S;/建表尾插法void CreatListR(LinkList

5、 &L,ElemType a,int n)L=(LinkList)malloc(sizeof(LNode);L->next=NULL;LinkList p;p=L;LinkList S;int i;/尾插法for(i=0;i<n;i+)S=(LinkList)malloc(sizeof(LNode);S->data=ai;p->next=S;p=S;p->next=NULL;/初始化線性表void InitList(LinkList &L)L=(LinkList)malloc(sizeof(LNode);L->next=NULL;/獲得鏈表元

6、素Status GetElem(LinkList L,int i,ElemType &e)/L為帶頭結(jié)點的單鏈表的頭指針LinkList p;int j;/初始化，p指向第一個結(jié)點p=L->next;/j為計數(shù)器j=1;/順指針往后查找，直到p指向第i個元素或p為空while(p && j<i)p=p->next;j+;/第i個元素不存在if(!p | j>i)return ERROR;/取第i個元素e=p->data;return OK;/插入Status ListInsert(LinkList &L,int i,ElemType

7、 e)int j=0;LinkList p;p=L;while(p!=NULL && j<i-1)/找第i-1個結(jié)點p=p->next;j+;if(!p | j>i-1)return ERROR;LinkList S;S=(LinkList)malloc(sizeof(LNode);/生成新結(jié)點S->data=e;S->next=p->next;p->next=S;return OK;/刪除Status ListDelete(LinkList &L,int i,ElemType &e)LinkList p;LinkLis

8、t q;int j=0;p=L;while(p->next)!=NULL && j<i-1)/找第i個結(jié)點p=p->next;j+; /!(p->next) ：指向第i個結(jié)點的指針為空第i個元素不存在if(!(p->next) | j>i-1)return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;/求表的長度int ListLength(LinkList L)LinkList p;p=L;int j=0;/線性鏈表最后一個結(jié)點的指針為空wh

9、ile(p->next)!=NULL)j+;p=p->next;return j;/輸出void visit(LinkList L)LinkList p;p=L->next;while(p!=NULL)printf("%c ",p->data);p=p->next;/銷毀:要銷毀的話從頭結(jié)點開始依次free 但要先得到下一個節(jié)點再freevoid DestroyList(LinkList &L)LinkList p;LinkList q;p=L;q=p->next;while(p!=NULL)free(p);p=q;q=p->

10、;next;/free(p);/判空int ListEmpty(LinkList L)/為空表那么執(zhí)行該語句，否那么返回return 0；return (L->next=NULL);/查找int ListSearch(LinkList L,ElemType e)LinkList p;p=L->next;int i=1;while(p!=NULL && p->data!=e)p=p->next;i+;if(p=NULL)return 0;return i;int main()ElemType e;ElemType a6='a','b

11、','c','d','e','f'LinkList L;/鏈表的頭指針printf("頭插法建表：");CreatListF(L,a,6);visit(L);printf("nn");/初始化 InitList(L);printf("初始化后的表：");visit(L);printf("nn");printf("尾插法建表：");CreatListR(L,a,6); visit(L);printf("nn");/初始化后表為空，此時不要調(diào)用GetElem()GetElem(L,3,e);printf("表中第3個元素為：");printf("%cnn",e);/在第5個位置插入字符'k'ListInsert(L,5,'k');printf("在表中第5個位置插入字符'k'后：");visit(L);printf("nn");printf(&