靜態鍊表

靜態鍊表

對於線性鍊表，也可用一維數組來進行描述。這種描述方法便於在沒有指針類型的高級程式設計語言中使用鍊表結構。

基本介紹

  • 中文名：靜態鍊表
  • 外文名：Static list
  • 拼音：jing tai lian biao
  • 相關概念：線性鍊表
  • 描述方式：用一維數組
  • 相關領域：數學，制表
定義,優點,示例,示例一,示例二,示例三,

定義

用數組描述的鍊表，即稱為靜態鍊表。
在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;
while (head<>-1)and(j<place-1) do
begin
inc(j);
head:=list[head].next;
end;
if (head=-1)or(j>place-1) then
begin
writeln('Input Error!');
exit;
end;
x:=get_node(av);
if x=-1 then
begin
writeln('List has been full!');
exit;
end;
list[x].num:=num;
list[x].next:=list[j].next;
list[j].next:=x;
end;
procedure del(var av:integer;head,place:integer);
var j,k:integer;
begin
j:=0;
while (list[head].next<>-1)and(j<place-1) do
begin
inc(j);
head:=list[head].next;
end;
if (list[head].next=-1)or(j>place-1) then
begin
writeln('Input Error!');
exit;
end;
k:=list[head].next;
list[head].next:=list[list[head].next].next;
disp_node(av,k);
end;
begin
init(av);
head:=get_node(av);
list[head].next:=-1;
readln(ch);
while ch<>'E' do
begin
case ch of
'I':begin
readln(num,place);
insert(head,num,place,av);
end;
'D':begin
readln(place);
del(av,head,place);
end;
'P':print(head);
else writeln('Input Error!');
end;
readln(ch);
end;
end.
typedefstruct_node{intdata;intinext;}node,list[DEF_SIZE];

相關詞條

熱門詞條

聯絡我們