首先我們讓數組的元素都是由兩個數據域組成,data和cur。也就是說,數組的每一個下標都對應一個data和一個cur。
數據域data用來存放數據元素,也就是通常我們要處理的數據;而游標cur相當於單鏈表中的next指針,
存放該元素的後繼在數組中的下標。我們把這種用數組描述的鏈表叫做靜態鏈表。
數組的第一個元素,即下標為0的元素的cur就存放備用鏈表的第一個結點的下標;而數組的最後一個元素的cur
則存放第一個有數值的元素的下標,相當於單鏈表的頭節點作用,當整個鏈表為空時,則為0,表示無指向。
示例代碼:(改編自《大話數據結構》)
#include<iostream>
using namespace std;
#define MAXSIZE 100
typedef int ElemType;
/* 線性表的靜態鏈表存儲結構 */
typedef struct Node
{
ElemType data;
int cur; //為0時表示無指向
} StaticLinkList[MAXSIZE];
/* 將一維數組array中各分量鏈成一個備用鏈表,array[0].cur為頭指針,"0"表示空指針 */
bool InitList(StaticLinkList array)
{
cout << "InitList..." << endl;
for (int i = 0; i < MAXSIZE - 1; i++)
{
array[i].cur = i + 1;
}
array[MAXSIZE - 1].cur = 0;/* 目前靜態鏈表為空,最後一個元素的cur為0 */
return true;
}
/* 若備用空間鏈表非空,則返回分配的結點下標,否則返回0 */
int Malloc_SLL(StaticLinkList array)
{
int k = array[0].cur;
if (k)
array[0].cur = array[k].cur;/* 下一個分量用來做備用 */
return k;
}
/* 將下標為pos的空閒結點回收到備用鏈表 */
void Free_SLL(StaticLinkList array, int pos)
{
array[pos].cur = array[0].cur; /* 把第一個元素的cur值賦給要刪除的分量cur */
array[0].cur = pos; /* 把要刪除的分量下標賦值給第一個元素的cur */
}
int ListLength(StaticLinkList array)
{
int i = array[MAXSIZE - 1].cur;
int j = 0;
while(i)
{
i = array[i].cur;
++j;
}
return j;
}
/* 在array中第pos個元素之前插入新的數據元素Elem */
bool ListInsert(StaticLinkList array, int pos, ElemType Elem)
{
cout << "Insert List from pos: " << pos << " Item " << Elem << endl;
if (pos < 1 || pos > ListLength(array) + 1)
return false;
int k = MAXSIZE - 1;
int i = Malloc_SLL(array); /* 獲得空閒分量的下標 */
if (i)
{
array[i].data = Elem;
for (int l = 1; l <= pos - 1; l++)
k = array[k].cur;
array[i].cur = array[k].cur;/* 把第pos個元素之前的cur賦值給新元素的cur */
array[k].cur = i;/* 把新元素的下標賦值給第pos個元素之前元素的cur */
return true;
}
return false;
}
/* 刪除在array中第pos個數據元素 */
bool ListDelete(StaticLinkList array, int pos)
{
cout << "Delete List from pos: " << pos << endl;
if (pos < 1 || pos > ListLength(array))
return false;
int k = MAXSIZE - 1;
for (int l = 1; l <= pos - 1; l++)
k = array[k].cur;
int j = array[k].cur;
array[k].cur = array[pos].cur;
Free_SLL(array, j);
return true;
}
bool ListTraverse(StaticLinkList array)
{
cout << "List Traverse : " << endl;
int k = MAXSIZE - 1;
while (array[k].cur != 0)
{
k = array[k].cur;
cout << array[k].data << ' ';
}
cout << endl;
return true;
}
int main(void)
{
StaticLinkList SSL;
InitList(SSL);
for (int i = 1; i < 5; i++)
ListInsert(SSL, i, i);
ListTraverse(SSL);
ListDelete(SSL, 3);
ListTraverse(SSL);
cout << "List Length : " << ListLength(SSL) << endl;
return 0;
}
輸出為:
靜態鏈表在插入和刪除操作時不需要移動元素,只需要修改游標,從而改進了在順序存儲結構中插入和刪除操作需要移動
大量元素的缺點;但並沒有解決連續分配存儲帶來的表長難以確定的問題;並且失去了順序存儲結構隨機存取的特性。