靜態(tài)單鏈表 :

線性表的靜態(tài)單鏈表存儲(chǔ)結(jié)構(gòu) :

#define MAXSIZE 100;

?

typedef struct{

?

? ElemType data;

? int cur;

?

}component,SLinkList[MAXSIZE];

?

分析 :

這種描述方法便于在不設(shè) ” 指針 ” 類型的高級(jí)程序設(shè)計(jì)語言中 , 使用的鏈表結(jié)構(gòu) . 數(shù)組的零分量可看成頭節(jié)點(diǎn) . 這種結(jié)構(gòu)仍然需要預(yù)先分配一個(gè)較大的空間 . 但在插入和刪除的時(shí)候 , 不需要移動(dòng)元素 . 僅需要修改指針 . 所以仍然具有鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要優(yōu)點(diǎn) .

?

基本操作 :

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

int LocateElem_L(SLinkList S, ElemType e)

{

?

?? i = S[0].cur;

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

?? return i;

?

}

分析 :

如果找不到相應(yīng)的元素 , 返回值為 0.

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

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) ?? 如果備用空間的鏈表非空 , 則返回分配的節(jié)點(diǎn)下標(biāo) ,

否則 , 返回 0;

?

int Malloc_SL(SLinkList &space){

?

?? i=space[0].cur;

?? if(space[0].cur)

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

?? return i;

}

(4) 將下標(biāo)為 k 的空閑節(jié)點(diǎn)回收到備用鏈表 .

void Free_SL(SLinkList &space,int k)

{

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

space[0].cur = k;

}

(4) ?? 計(jì)算集合運(yùn)算 (A-B ) ∪ (B-A)

假設(shè)由終端輸入集合元素 , 先建立表示集合 A 的靜態(tài)鏈表 S, 然后在輸入集合 B 的元素的同時(shí)查找 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;

??? }

}

}