1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1.1 順序存儲結(jié)構(gòu)不足的解決辦法

線性表的順序存儲結(jié)構(gòu)最大的缺點是插入和刪除時需要移動大量數(shù)據(jù)，這顯然就需要消耗時間。本節(jié)討論的鏈?zhǔn)酱鎯Y(jié)構(gòu)可以很好滴解決這個問題。
線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這些存儲單元可以使連續(xù)的，也可以是不連續(xù)的。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置。 以前的順序結(jié)構(gòu)中，每個數(shù)據(jù)元素只需要存數(shù)據(jù)元素的信息就可以了?，F(xiàn)在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存數(shù)據(jù)元素信息外，還要存儲它的后繼元素的存儲地址。 因此，為了表示每一個數(shù)據(jù)元素a(i)與其直接后繼數(shù)據(jù)元素a(i+1)之間的邏輯關(guān)系。對數(shù)據(jù)a(1)來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈。這兩部分信息組成元素a(i)的存儲映像，稱為結(jié)點。如果每個結(jié)點只包含一個指針域，叫做單鏈表。單鏈表正是通過每個節(jié)點的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序連接在一起，如圖所示：
對于線性表來說，總要有頭有尾，鏈表也不例外。我們把鏈表中第一個結(jié)點的存儲位置叫做頭指針，那么整個鏈表的存取就必須是從頭指針開始進(jìn)行了。之后的每一個結(jié)點，其實就是上一個的后繼指針指向的位置。最后有意義的是討論最后一個結(jié)點的指針指向問題，暫時規(guī)定，線性鏈表的最后一個結(jié)點指針為“空”（NULL）
有時，我們?yōu)榱烁臃奖愕貙︽湵磉M(jìn)行操作，會在單鏈表的第一個結(jié)點前附設(shè)一個結(jié)點，稱為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針，如圖所示：

2.單鏈表操作

2.1 單鏈表的讀取

在線性表的順序存儲結(jié)構(gòu)中，我么要計算任意一個元素的存儲位置時容易的。但是在單鏈表中，由于第i個元素到底在哪？沒辦法一開始就知道，必須從頭開始找。 獲得鏈表第i個數(shù)據(jù)的算法思路： (1)聲明一個結(jié)點p指向鏈表第一個結(jié)點，初始化j從1開始； (2)當(dāng)j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一結(jié)點，j累加1； (3)若到鏈表末尾p為空，則說明第i個元素不存在； (4)否則查找成功，返回結(jié)點p的數(shù)據(jù)。 代碼實現(xiàn)如下： Status GetElem( LinkList* L, int i, ElemType* e) {int j;LinkList p; //聲明一節(jié)點pp = L->next; //讓p指向鏈表L的第一個節(jié)點j = 1;while ( p && j<i) //p不為空 或者計數(shù)器j還沒有等于i時，循環(huán)繼續(xù){p = p->next; //讓p指向下一個結(jié)點++j;}if (!p || j>1i)return ERROR;*e = p->data;return OK; } 說白了，就是從頭開始找，知道第i個元素為止。由于這個算法的時間復(fù)雜度取決于i的位置，當(dāng)i=1時，則不需要遍歷，第一個就取出數(shù)據(jù)了，而當(dāng)i = n時，則遍歷n-1次就可以了，因此最壞情況的時間復(fù)雜度是O(n)。 由于單鏈表的結(jié)構(gòu)中沒有定義表長，所以不能事先知道要循環(huán)多少次，因此也就不方便使用for來控制循環(huán)。其主要核心思想就是“工作指針后移”。

2.2 單鏈表的元素插入

單鏈表的元素插入用不著驚到其他結(jié)點，只需要讓s->next和p->next的指針做一點改變即可。

s->next = p->next； p->next =s;

單鏈表第i個數(shù)據(jù)插入節(jié)點的算法思路： (1)聲明一結(jié)點p指向鏈表第一個結(jié)點，初始化j從1開始； (2)當(dāng)j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一結(jié)點，j累加1； (3)若到鏈表末尾p為空，則說明第i個元素不存在； (4)否則查找成功，在系統(tǒng)中生成一個空節(jié)點s; (5)將數(shù)據(jù)元素e賦值給s->data; (6)單鏈表的插入標(biāo)準(zhǔn)語句s->next=p->next；p->next = s; (7)返回成功。 實現(xiàn)代碼算法如下： Status ListInsert ( LinkList *L, int i, ElemType e) {int j;LinkList p,s;p = *L;'j = 1;while( p && j<i){p = p->next;++j;}if ( !p || j>1)return ERROR;s = (LinkList)malloc(sizeof(Node));s->data = e;s->next = p->next;p->next = s;return OK; }

2.3 單鏈表的元素刪除

設(shè)存儲元素a(i)的結(jié)點為q，要實現(xiàn)將節(jié)點q刪除單鏈表操作，其實就是將他的前幾結(jié)點的指針繞過，指向它的后繼結(jié)點即可，如圖所示：
這里需要做的只有一步，p->next = p->next->next,用q來取代p->next,刪除語句可以寫成： q=p->next; p->next = q->next;單鏈表第i個數(shù)據(jù)刪除節(jié)點的算法思路： (1)聲明一個結(jié)點p指向鏈表第一個結(jié)點，初始化j從1開始； (2)當(dāng)j小于i時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一個結(jié)點，j累加1； (3)若到鏈表末尾p為空，則說明第i個元素不存在； (4)否則查找成功，將預(yù)刪除的結(jié)點p->next賦值給q; (5)單鏈表的刪除標(biāo)準(zhǔn)語句p->next=q->next； (6)將q結(jié)點中的數(shù)據(jù)賦值給e，作為返回； (7)釋放q結(jié)點； (8)返回成功。
實現(xiàn)代碼算法如下： Status ListDelete( LinkList* L, int i, ElemType* e) {int j;LinkList p,q;p = *L;j = 1;while( p->next || j<i ){p = p->next;++j;}if ( !(p->next) || j>i)return ERROR;q=p->next;p->next=q->next;*e = q->data;free(q);return OK; }

總結(jié)

以上是生活随笔為你收集整理的大话数据结构：线性表(2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。