單向連結串列

單向連結串列是連結串列的一種，其特點是連結串列的連結方向是單向的，對連結串列的訪問要透過從頭部開始，依序往下讀取。資料結構.一個單向連結串列的節點被分成兩個部分。第一個部分儲存或者顯示關於節點的資訊，第二個部分儲存下一個節點的地址。單向連結串列只可向一個方向遍歷。動態單連結串列.單向連結串列的資料結構可以分為兩部分：資料域和指標域，資料域儲存資料，指標域指向下一個儲存節點的地址。儲存結構./* c2-2.h 線性表的單鏈表儲存結構 */typedef struct LNodeElemType data;struct LNode *next;}LNode,*LinkList;基本操作./* bo2-2.c 帶有頭結點的單鏈表(儲存結構由c2-2.h定義)的基本操作(12個),包括演算法2.8,2.9,2.10 */void InitList(LinkList *L)*L=(LinkList)malloc(sizeof(struct LNode)); /* 產生頭結點，並使L指向此頭結點 */if(!*L) /* 儲存分配失敗 */exit(OVERFLOW);(*L)-&gt;next=NULL; /* 指標域為空 */void DestroyList(LinkList *L)LinkList q;while(*L)q=(*L)-&gt;next;free(*L);*L=q;void ClearList(LinkList L) /* 不改變L */LinkList p,q;p=L-&gt;next; /* p指向第一個結點 */while(p) /* 沒到表尾 */q=p-&gt;next;free(p);p=q;L-&gt;next=NULL; /* 頭結點指標域為空 */Status ListEmpty(LinkList L)if(L-&gt;next) /* 非空 */return FALSE;elsereturn TRUE;int ListLength(LinkList L)int i=0;LinkList p=L-&gt;next; /* p指向第一個結點 */while(p) /* 沒到表尾 */i++;p=p-&gt;next;return i;Status GetElem(LinkList L,int i,ElemType *e) /* 演算法2.8 */int j=1; /* j為計數器 */LinkList p=L-&gt;next; /* p指向第一個結點 */while(p&amp;&amp;jnext;printf("\n");靜態單鏈表.// 線性表的靜態單鏈表儲存結構typedef struct {ElemType data; //此處的ElemType可以自由代換int cur;} component, SLinkList[MAX_SIZE];// 一個數組只生成一個靜態連結串列的基本操作(11個)void InitList(SLinkList L) {// 構造一個空的連結串列L，表頭為L的最後一個單元L[MAX_SIZE-1]，其餘單元鏈成// 一個備用連結串列，表頭為L的第一個單元L[0]，“0”表示空指標int i;L[MAX_SIZE - 1].cur = 0; // L的最後一個單元為空連結串列的表頭for (i = 0; i &lt; MAX_SIZE - 2; i++) // 將其餘單元連結成以L[0]為表頭的備用連結串列L[i].cur = i + 1;L[MAX_SIZE - 2].cur = 0;void ClearList(SLinkList L) {// 初始條件：線性表L已存在。操作結果：將L重置為空表int i, j, k;i = L[MAX_SIZE - 1].cur; // 連結串列第一個結點的位置L[MAX_SIZE - 1].cur = 0; // 連結串列空k = L[0].cur; // 備用連結串列第一個結點的位置L[0].cur = i; // 把連結串列的結點連到備用連結串列的表頭while (i) { // 沒到連結串列尾j = i;i = L[i].cur; // 指向下一個元素L[j].cur = k; // 備用連結串列的第一個結點接到連結串列的尾部Status ListEmpty(SLinkList L) {// 若L是空表，返回TRUE；否則返回FALSEif (L[MAX_SIZE - 1].cur == 0) // 若為空表return TRUE;elsereturn FALSE;int ListLength(SLinkList L) {// 返回L中資料元素個數int j = 0, i = L[MAX_SIZE - 1].cur; // i指向第一個元素while (i) { // 沒到靜態連結串列尾i = L[i].cur; // 指向下一個元素j++;return j;Status GetElem(SLinkList L, int i, ElemType *e) {// 用e返回L中第i個元素的值int l, k = MAX_SIZE - 1; // k指向表頭序號if (i  ListLength(L))return ERROR;for (l = 1; l &lt;= i; l++) // 移動到第i個元素處k = L[k].cur;*e = L[k].data;return OK;int LocateElem(SLinkList L, ElemType e) { // 演算法2.13(有改動)// 在靜態單鏈線性表L中查詢第1個值為e的元素。若找到，則返回它在L中的// 位序，否則返回0。(與其它LocateElem()的定義不同)int i = L[MAX_SIZE - 1].cur; // i指示表中第一個結點while (i &amp;&amp; L[i].data != e) // 在表中順鏈查詢(e不能是字串)i = L[i].cur;return i;Status PriorElem(SLinkList L, ElemType cur_e, ElemType *pre_e) {// 初始條件：線性表L已存在// 操作結果：若cur_e是L的資料元素，且不是第一個，則用pre_e返回它的前驅，// 否則操作失敗，pre_e無定義int j, i = L[MAX_SIZE - 1].cur; // i指示連結串列第一個結點的位置do { // 向後移動結點j = i;i = L[i].cur;} while (i &amp;&amp; cur_e != L[i].data);if (i) { // 找到該元素*pre_e = L[j].data;return OK;return ERROR;Status NextElem(SLinkList L, ElemType cur_e, ElemType *next_e) {// 初始條件：線性表L已存在// 操作結果：若cur_e是L的資料元素，且不是最後一個，則用next_e返回它的後繼// 否則操作失敗，next_e無定義int j, i = LocateElem(L, cur_e); // 在L中查詢第一個值為cur_e的元素的位置if (i) { // L中存在元素cur_ej = L[i].cur; // cur_e的後繼的位置if (j) { // cur_e有後繼*next_e = L[j].data;return OK; // cur_e元素有後繼return ERROR; // L不存在cur_e元素，cur_e元素無後繼Status ListInsert(SLinkList L, int i, ElemType e) {// 在L中第i個元素之前插入新的資料元素eint l, j, k = MAX_SIZE - 1; // k指向表頭if (i  ListLength(L) + 1)return ERROR;j = Malloc(L); // 申請新單元if (j) { // 申請成功L[j].data = e; // 賦值給新單元for (l = 1; l &lt; i; l++) // 移動i-1個元素k = L[k].cur;L[j].cur = L[k].cur;L[k].cur = j;return OK;return ERROR;Status ListDelete(SLinkList L, int i, ElemType *e) {// 刪除在L中第i個數據元素e，並返回其值int j, k = MAX_SIZE - 1; // k指向表頭if (i  ListLength(L))return ERROR;for (j = 1; j &lt; i; j++) // 移動i-1個元素k = L[k].cur;j = L[k].cur;L[k].cur = L[j].cur;*e = L[j].data;Free(L, j);return OK;void ListTraverse(SLinkList L, void(*vi)(ElemType)) {// 初始條件：線性表L已存在。操作結果：依次對L的每個資料元素呼叫函式vi()int i = L[MAX_SIZE - 1].cur; // 指向第一個元素while (i) { // 沒到靜態連結串列尾vi(L[i].data); // 呼叫vi()i = L[i].cur; // 指向下一個元素printf("\n");