靜態單鏈表 :

線性表的靜態單鏈表存儲結構 :

#define MAXSIZE 100;

?

typedef struct{

?

? ElemType data;

? int cur;

?

}component,SLinkList[MAXSIZE];

?

分析 :

這種描述方法便于在不設 ” 指針 ” 類型的高級程序設計語言中 , 使用的鏈表結構 . 數組的零分量可看成頭節點 . 這種結構仍然需要預先分配一個較大的空間 . 但在插入和刪除的時候 , 不需要移動元素 . 僅需要修改指針 . 所以仍然具有鏈式存儲結構的主要優點 .

?

基本操作 :

(1) ?? 在靜態單鏈表中 , 查找第一個值為 e 的元素 .

int LocateElem_L(SLinkList S, ElemType e)

{

?

?? i = S[0].cur;

?? while(i && S[i].data != e) i=S[i].cur;

?? return i;

?

}

分析 :

如果找不到相應的元素 , 返回值為 0.

(2) ???? 將一維數組 space 中的各個分量 , 鏈成一個備用的鏈表 .

space[0].cur 為頭指針 .

?

void InitSpace(SLinkList &space){

?

?

?? for(i =0;i<MAXSIZE-1;++i)

????? space[i].cur = i+1;

?? space[MAXSIZE-1].cur =0;

?

}

?

(3) ?? 如果備用空間的鏈表非空 , 則返回分配的節點下標 ,

否則 , 返回 0;

?

int Malloc_SL(SLinkList &space){

?

?? i=space[0].cur;

?? if(space[0].cur)

????? space[0].cur =space[i].cur;

?? return i;

}

(4) 將下標為 k 的空閑節點回收到備用鏈表 .

void Free_SL(SLinkList &space,int k)

{

space[k].cur =space[0].cur;

space[0].cur = k;

}

(4) ?? 計算集合運算 (A-B ) ∪ (B-A)

假設由終端輸入集合元素 , 先建立表示集合 A 的靜態鏈表 S, 然后在輸入集合 B 的元素的同時查找 S 表 , 如果存在相同的元素 , 則從 S 表中刪除 , 否則將其插入到 S 表中 .

具體代碼如下 :

void difference(SLinkList &space , int &s)

{

?

????? InitSpace_SL(space);

????? s = Malloc_SL(space);

????? r=s;

????? scanf(m,n);

????? for(j=1;j<=m;++j)

{???? i =Malloc_SL(space);

?????????? scanf(space[i].data);

?????????? space[r].cur =i;

?????????? r=i;

????? }? space[r].cur=0;

for (j=1;j<=n;++j){

??? scanf(b);

??? p=s;k=space[s].cur;

??? while(k!=space[r].cur && space[k].data !=b)

??? { p=k;k=space[k].cur;}

if (k==space[r].cur)

{

??? ?? i = Malloc_SL(space);

??? ?? space[i].data = b;

??? ?? space[i].cur = space[r].cur;

??? ?? space[r].cur = i;

??? ?? r=i;

??? }

??? else{

????? space[p].cur =space[k].cur;

????? Free_SL(space,k);

????? if(r==k)

????? r=p;

??? }

}

}