資料結構-----C------線性表

新人第一次寫博客，如有不對的地方，請各位大佬指正！

線性表

線性表有兩種儲存結構，一種是順序儲存結構，一種是鏈式儲存結構，

線性表的順序儲存結構由陣列和表長所構成的結構體組成，定義的代碼如下

#define MaxSize 20

typedef struct

{

int data[MaxSize];

int length;

}SqList;

這里typedef的作用是給struct SqList 起別名，方便后續創建結構體變數

線性表定義了之后，需要讀取元素，讀取元素的代碼如下：

typedef int status;

status GetElem(SqList L,int i,int *e)

{

if(L.length==0||i<1||i>L.length) //當線性表為空表或者i輸入的范圍有誤時，回傳0

return 0;

*e=L->data[i-1]; //第i個元素對應陣列的下標就是i-1，故將該值賦給*e

return 1;
}

進行了線性表的讀取元素操作后，還需要進行線性表的插入和洗掉

線性表的順序儲存結構的插入的代碼如下：

Status ListInsert(SqList L,int i,int e)

{

int k;

if(L.length==MaxSize||i<1||i>L.length) //表滿或者i不在范圍內時回傳0

return 0;

if(i<=L.length) //插入元素不在表尾

{

for(k=L.length-1;k>=i-1;k--)

L.data[k+1]=L.data[k]; //將i-1之后的元素全部向后移一位

}

L.data[i-1]=e;

return 1;

}

線性表的順序儲存結構的洗掉代碼如下：

status ListDelete(SqList L,int i,int *e)

{

int k;

if(L.length=MaxSize||i<1;i>L.length) //判斷資料是否合理

return 0;

*e=L.data[i-1];

if(i<=L.length) //如果不在表尾

{
for(k=i;k<=L.length-1;k++)

L.data[k-1]=L.data[k]; //第i個之后的元素向前移動一位
}

L.length--; //表長減1

return 1;

}

線性表的鏈式儲存結構

線性表的鏈式儲存結構又叫鏈表，鏈表由多個結點鏈接而成，每個結點又有由指標域和資料域組成，鏈表的定義代碼如下：

//先創建結點

typedef struct Node

{

int data; //資料域

struct Node* next; //指標域

}Node;

//定義鏈表

typedef struct Node* LinkList;

由于鏈表的每個結點只有一個指標域，所以又叫作單鏈表，對于線性表來說，總得有個頭有個尾，鏈表也不例外，我們把鏈表中的第一個結點的儲存位置叫作頭指標，除最后一個結點外每一個結點的指標都指向下一個結點，而最后一個結點的指標指向空，

單鏈表的讀取代碼如下：

Status GetElem(LinkList L,int i,int *e)

{

int j=1;

if(i<1||i>MaxSize) //當輸入的資料不合理時，回傳0

return 0;

p=L->next; //讓p指向鏈表的第一個結點

while(j<i&&p)

{

p=p->next; //讓p指向下一個結點

j++;

}

if(!p||j>i) //第i個結點不存在

return 0;

*e=p->data; //將要讀取元素的資料賦值給*e

reuturn 1;
}

單鏈表的插入和洗掉代碼如下：

Status ListInsert(LinkList *L,int i,int e)

{

LinkList p,s; //創建兩個結點 p，s

int j=1;

p=*L; //讓p指向鏈表的頭結點

while(p&&j<i)

{

p=p->next; //使得p指向下一個結點

j++;

}

if(!p||j>i) //未讀取到該節點

return 0;

s=(LinkList)malloc(sizeof(Node));

s->data=e;

s->next=p->next;

p->next=s;

return 1;
}

Status ListDelete(LinkList *L,int i,int *e)

{
LinkList p,q; //創建兩個結點

p=*L; //讓p指向鏈表的頭部

int j=1; //創建計數器

while(j<i&&p->next)

{

p=p->next; //讓p指向下一個結點

j++;
}

if(!p||j>i) //未找到該結點

return 0;

*e=p->data; //將要洗掉的資料賦值給*e

q=p->next;

p->next=q->next;

free(q); //釋放q

return 1;

}

單鏈表的整表創建的代碼如下：

//頭插法 將每一個新的結點插入頭結點的后一個位置，這使得每一個新插入的結點會是鏈表的第一個結點

Status CreatLinkListHead(LinkList *L,int n)

{

LinkList p;

int j;

*L=(LinkList)malloc(sizeof(Node)); //創建頭結點

(*L)->next=NULL; //頭結點置空

srand(time(0)); //初始化亂數種子

{

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

{

p=(LinkList)malloc(sizeof(Node));

p->data=rand()%100+1;

p->next=(*L)->next;

(*L)->next=p;

}

return 1;

}

//尾插法 將每一個新的結點插入鏈表的尾部，使得每一個新的節點成為鏈表的最后一個結點

Status CreatLinkListTail(LinkList *L,int n)

{

LinkList p,r; //創建p，q兩個結點

srand(time(0)); //初始化亂數種子

*L=(LinkList)malloc(sizeof(Node)); //創建頭結點

r=*L; //使得r成為鏈表的頭結點

int j; //創建計數器

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

{

p=(LinkList)malloc(sizeof(Node)); //創建一個新節點p

p->data=rand()%100+1; //給p賦值

r->next=p; //使得p成為r的下一個結點

r=p; //使得p成為鏈表的最后一個結點

}

r->next=NULL; //表示該鏈表結束

return 1;

}
//單鏈表的整表洗掉

Status ListDelete(LinkList *L)

{

LinkList p,q; //創建兩個結點p，q

p=(*L)->next; //使得p指向鏈表的第一個結點

while(p)

{

q=p->next; //將下一個結點的值賦給q

free(q); //釋放q

p=q; //把p的值賦給p

}

(*L)->next=NULL; //將頭結點置空

return 1;
}

靜態鏈表

靜態鏈表=資料+游標，靜態鏈表是指用陣列描述的鏈表，陣列的元素都是由兩個資料域組成，一個叫data，一個叫cur，資料域data用來存放資料元素，也就是通常要處理的資料，而cur相當于單鏈表中的next指標，存放該元素的后繼在陣列中的下標，我們把cur叫作游標，

靜態鏈表的陣列的第一個元素的cur用來存放備用鏈表第一個結點的下標，備用鏈表是指未被使用的陣列元素，靜態鏈表的陣列的最后一個元素的cur用來存放第一個插入元素的下標，相當于頭結點，

靜態鏈表的定義代碼如下：

typedef struct

{

int data; //資料

int cur; //游標

}Component,StaticLinkList[MaxSize];

//靜態鏈表的初始化

Status InitList(StaticLinkList L)

{

int i;

for(i=0;i<MaxSize-1;i++)

{

L[i].cur=i+1;//每個元素的游標等于下標加1
}

L[MaxSize-1]=0; //目前靜態鏈表為空，最后一個元素的cur為0

return 1;
}

//靜態鏈表的插入操作，因為靜態鏈表自身沒有記憶體申請的函式，故該函式需要自己定義，該函式的作用是若備用空間鏈表非空，則回傳分配的結點下標，否則回傳0

Status Malloc_SSL(StaticLinkList Space)

{

int i=Space[0].cur; //當前陣列第一個元素的cur存的值就是要回傳的第一個備用空閑的下標

if(Space[0].cur)

Space[0].cur=Space[i].cur; //由于要拿出一個分量來使用了，

return i; //所以我們就得把它的下一個分量用來做備用
}

//靜態鏈表的長度計算

Status ListLength(StaticLinkList Space)

{

int j;

int i=Space[MaxSize-1].cur; //從頭結點開始

while(i)

{

i=Space[i].cur;

j++; //每讀取一次游標，j就加1

}

return j;

}

//靜態鏈表的插入

Status ListInsert(StaticLinkList L,int i,int e)

{

int j,k,l;

k=MaxSize-1; //鏈表的最后一個元素的下標

if(i<1||i>ListLength(L)) //輸入資料不符合范圍 ListLength為鏈表的長度計算函式

return 0;

j=Malloc_SSL(L); //向備用空間鏈表申請記憶體

if(j)

{

L[j]=e; //賦值

for(l=1;l<=i-1;l++)

k=L[k].cur; //找到i之前的元素的位置

L[j].cur=L[k].cur; //游標更替

L[k].cur=j;

return 1;

}

return 0;
}

//靜態鏈表的洗掉，因為靜態鏈表是由陣列鏈接而成的，故沒有記憶體釋放的函式，需要自己定義，該函式用來釋放結點，代碼如下：

void Free_SSL(StaticLinkList L，int k)

{

Space[k].cur=Space[0].cur; //把第一個元素cur值賦給要洗掉的分量cur

Space[0].cur=k; //把要洗掉的分量下標賦值給第一個元素的cur
}

//靜態鏈表的洗掉

Status ListDelete(StaticLinkList L,int i)

{

int j,k;

k=MaxSize-1;

if(i<1||i>ListLength(L)) //輸出的資料不合理的時候回傳0

return 0;

for(k=1;k<=i-1k++)

k=L[k].cur; //找到i之前被洗掉元素的下標

L[k].cur=L[j].cur;

Free_SSL(L,j); //

return 1;

}

回圈鏈表

將單鏈表中終端結點的指標端由空指標改為指向頭結點，就使整個單鏈表形成一個環，這種頭尾相接的單鏈表成為單回圈鏈表，簡稱回圈鏈表

回圈鏈表的函式大多與單鏈表一致，只是多了個尾指標，當要將兩個回圈鏈表合并成一個表時，有了尾指標就非常簡單了

/* rearA為A的尾結點 rearB為B的尾結點

p=rearA->next //p保存鏈表A的頭結點

rearA->next=rearB->next->next; //使得A鏈表的尾結點指向B鏈表的第一個結點

q=rearB->next //q保存鏈表B的頭結點

rearB->next=p;

free(q);

*/

雙向鏈表

雙向鏈表是在單鏈表的每個結點中，再設定一個指向其前驅結點的指標域，所以在雙向鏈表中的結點都有兩個指標域，一個指向直接后繼，另一個指向直接前驅

//雙向鏈表的定義

typedef struct DullNode

{

int data; //資料域

struct DullNode *next; //后繼指標

struct DullNode *prior; //前驅指標
}DullNode,*DuLinkList;

//雙向鏈表的插入操作的部分代碼如下

// p s p->next

s->prior=p; //把p的值賦給s的前驅

s->next=p->next; //把p->next的值賦給s的后繼

p->next->prior=s; //把s的值賦給p->next的前驅

p->next=s; //把s賦給p的后繼

//雙向鏈表的洗掉操作

// p->prior p p->next

p->prior->next=p->next; 把p->next的值賦給p->prior的后繼

p->next->prior=p->prior; 把p->prior的值賦給p->next的前驅

free(p);