靜态連結清單:使用數組這一資料類型申請到一個有限存儲空間
靜态連結清單的組成:資料+遊标
遊标:用來存放下一個結點在數組中的位置
因為建立數組的時候元素的位置随機配置設定,是以需要用遊标來記錄位置資訊——是以靜态連結清單的結點既有自己的資料部分還有用來存儲下一個結點位置的遊标。
①當靜态連結清單為 空 的時候:最後一個元素的cur為0。L[999].cur=0
②當靜态連結清單為 非空的時候:最後一個元素的cur是用來存放第一個元素的下标,通常為1。L[999].cur=1
//靜态連結清單的插入
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000
//因為靜态連結清單有兩個一個資料data一個遊标
struct JingTai
{
int data;
int cur;
};
int Malloc(struct JingTai *L);
int Length(struct JingTai *L);
void InitList(struct JingTai *L);
bool ListInsert(struct JingTai *L,int i,int e);
void TraveList(struct JingTai *L);
int main()
{
struct JingTai L[MAXSIZE];
int i,e;
InitList(L);
ListInsert(L,i,e);
ListInsert(L,i,e);
ListInsert(L,i,e);
ListInsert(L,i,e);
TraveList(L);
system("pause");
return 0;
}
void InitList(struct JingTai *L)
{
/*兩部分一個是靜态連結清單一個是備用連結清單*/
L[MAXSIZE-1].cur=0;
L[MAXSIZE-2].cur=0;
int i =1;
L[0].cur=1;
while(i<MAXSIZE-2)
{
L[i].cur=i+1;
i++;
}
}
bool ListInsert(struct JingTai *L,int i,int e)//需要操作的連結清單,插入的位置,插入的元素值。
{
printf("請輸入插入元素的位置:\n");
scanf("%d",&i);
printf("請輸入元素的值\n");
scanf("%d",&e);
//判斷插入的位置i 是否超過靜态連結清單的大小
if(i<1||i>Length(L)+1)
{
printf("輸入的位置有誤\n");
return false;
}
int q;//使用一個數q用來記錄備用連結清單的下标
int k;//K是最後一個下标,因為最後一個下标的遊标為1,即L[999]=1,有了後面的循環 k=k[1].cur ->k=2; k=k[2].cur ->k=3.....
int j;
k=MAXSIZE-1;
for(j=1;j<i;j++)
{
k=L[k].cur;//完成的是遊标的轉移,比如說, L[1].cur=2,那麼k就等于3,k=L[3].cur,就又完成了一次轉移
}
q=Malloc(L);//配置設定區域的下标
L[q].data =e;//配置設定完空間後将資料e填進來
L[q].cur = L[k].cur;
L[k].cur=q;
return 0;
}
//用一個函數來判斷靜态連結清單L的長度
int Length(struct JingTai *L)
{
//計算表長就一個一個的數
int i=MAXSIZE-1;
int j=0;
while(L[i].cur)//這個遊标的意思
{
i=L[i].cur;//擷取遊标
j++;
}
return j;
}
//配置設定區域 (因為是要找連結清單裡面的備用連結清單是以參數是連結清單 )
int Malloc(struct JingTai *L)
{
int i;
i=L[0].cur;//傳回的是配置設定的區域下标 ,備用連結清單的下标
//備用連結清單被用了之後,新的備用連結清單的遊标就指向原來的備用連結清單的遊标所指的下标->新遊标=原來遊标
L[0].cur =L[i].cur;
return i;
}
void TraveList(struct JingTai *L)
{
int i=MAXSIZE-1;
int j=0;
while(i)
{
if(j!=0)
{
printf("%d ",L[i].data);
}
i=L[i].cur;//不停地傳遞下去
j++;
}
}