複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/靜態鏈表/10222248
複製
複製成功

靜態鏈表

鎖定
對於線性鏈表，也可用一維數組來進行描述。這種描述方法便於在沒有指針類型的高級程序設計語言中使用鏈表結構。
中文名
靜態鏈表
外文名
Static list
拼    音
jìng tài liàn biǎo
相關概念
線性鏈表
描述方式
用一維數組
相關領域
數學，製表

目錄

  1. 1 定義
  2. 2 優點
  3. 3 示例
  4. ▪ 示例一
  5. ▪ 示例二
  6. ▪ 示例三

靜態鏈表定義

用數組描述的鏈表，即稱為靜態鏈表。
在C語言中，靜態鏈表的表現形式即為結構體數組，結構體變量包括數據域data和遊標CUR。

靜態鏈表優點

這種存儲結構，仍需要預先分配一個較大的空間，但在作為線性表的插入和刪除操作時不需移動元素，僅需修改指針，故仍具有鏈式存儲結構的主要優點。
假如有如上的靜態鏈表S中存儲着線性表（a，b，c，d，f，g，h，i），Maxsize=11，要在第四個元素後插入元素e，方法是：先在當前表尾加入一個元素e，即：S[9].data = e;然後修改第四個元素的遊標域，將e插入到鏈表中，即：S[9].cursor = S[4].cursor; S[4].cursor = 9;，接着，若要刪除第7個元素h，則先順着遊標鏈通過計數找到第7個元素存儲位置6，刪除的具體做法是令S[6].cursor = S[7].cursor。

靜態鏈表示例

靜態鏈表示例一

#include<stdio.h>
#include"definition.h"
void Init(component *L)//初始化靜態鏈表
{ 
    unsigned short i;
    for(i=0; i<MAXSIZE-1; i++)
        L[i].cur=i+1;
    L[MAXSIZE-1].cur=0;
}
component* Insert(component *L)//插入數據到
鏈表
{ 
    component *T, *
temp1, *temp2;
    unsigned short i;
    ElemType ch;
    if( i=Malloc(L) ){
        T=temp1=&L;
        T->cur=0;
    } else
        return 0;
    
while( (ch=getchar()) != '\n' ){
        if( i=Malloc(L) ){
            temp2=&L;
            temp2->data=ch;
            temp2->cur=0;
            temp1->cur=i;
            
temp1=temp2;
        } else
            return 0;
    }
    return T;
}

靜態鏈表示例二

short Malloc(component *L)//分配空間
{ 
    unsigned short i;
    i=L[0].cur;
    if(L[0].cur){
        L[0].cur=L.cur;
        return i;//成功返回空間位置
    }
    return 0;//失敗返回0
}
void Free(component *L, short i) //回收空間
{ 
    L.cur=L[0].cur;
    L[0].cur=i;
}
void Disp(component *T, component *L)//顯示靜態鏈表數據
{ 
    
while(T->cur){
        T=&L[T->cur];

printf("%c", T->data);
} printf("\n");
}
void Purge(component *T, component *L) //刪除重複數據
{ component *
tmp, *temp;
for(T=&L[T->cur]; T->data; T=&L[T->cur]){//若T->data中沒數據，則退出循環
for(temp=T, tmp=&L[T->cur]; tmp->data;){//若tmp->data中沒數據，則退出循環
if(T->data==tmp->data){
temp->cur=tmp->cur;
Free(L, (short)(tmp-L));//回收空間

tmp=&L[temp->cur];
} else{
tmp=&L[tmp->cur];
temp=&L[temp->cur];
} }
} }
void Union(component *A, component *B, component *L)//(A-B)交(B-A)
{ component *T, *ta, *tb=B;
short flag;//用於判斷是否進行了刪除操作
B=&L;

while(B->data){//循環判斷，直到B表中所有數據都和A表比較過後才結束

靜態鏈表示例三

ta=T=A;
flag=1;//1代表沒有進行刪除
while(T->cur){//循環判斷，直到A表中所有數據都和B->data比較過後才結束
T=&L[T->cur];
if(T->data==B->data){//如果相等，則刪除
ta->cur=T->cur;
Free(L, (short)(T-L));
T=&L[ta->cur];
tb->cur=B->cur;
Free(L, (short)(B-L));
B=&L[tb->cur];
flag=0;//1代表進行了刪除
break;
} else//不相等則把指針移動到一個數據
ta=&L[ta->cur];
} if(flag){//如果沒有進行刪除操作，則連接兩個結點
T->cur=tb->cur;
tb->cur=B->cur;
B->cur=0;
B=&L[tb->cur];
} }
}
鏈表大家都知道吧，我就不廢話了．．．所謂的靜態鏈表就是在那些不能用指針的語言裏用數組建立鏈表並用一個下標來維護．．．給個程序吧．．．
program static_link_list(input,output);
const maxl=10;
type elem=record
num,next:integer;
end;
tlist=array[0..maxl]of elem;
var list:tlist;
num,place,head,av:integer;
ch:char;
function get_node(var av:integer):integer;
begin
get_node:=av;
if av<>-1 then av:=list[av].next;
end;
procedure disp_node(var av:integer;k:integer);
begin
list[k].next:=av;
av:=k;
end;
procedure init(var av:integer);
var i:integer;
begin
for i:=0 to maxl-1 do
list.next:=i+1;
list[maxl].next:=-1;
av:=0;
end;
procedure print(head:integer);
begin
head:=list[head].next;
while head<>-1 do
begin
write(list[head].num,' ');
head:=list[head].next;
end;
writeln;
end;
procedure insert(head,num,place:integer;var av:integer);
var j,x:integer;
begin
j:=0;