鏈表

  與順序表相同，鏈表也是一種線性表，它的數據邏輯組織形式是一維的。而與順序表不同的是，鏈表的物理存儲結構是用一組地址任意的存儲單元存儲數據的。也就是說，它不像鏈表一樣占據一段連續的記憶體空間，而是將存儲單元分散在記憶體的任意地址上。在鏈表結構中，每一個數據元素記錄都存放在鏈表的一個結點中（node）,而每一個結點之間由指針將其連接一起，這樣就形成一條如同“鏈”的結構。

  在C語言中，鏈表的每一個結點可以是一個結構體元素，當然也可以是其他的構造類型元素。在鏈表的每一個結點中，都必須有一個專門存放指針（地址）的域，用這個指針域來存放後繼結點的地址，這樣就達到連接後繼結點的目的。一條鏈表通常有有一個表頭，用來存放第一個結點的地址。此外，一條鏈表的最後一個結點的指針域要置空，表示該結點為鏈表的結尾，因為它沒有後繼結點。

                                        上圖是鏈表的結構示意圖

  一個鏈表結點可用C語言描述如下：

typedef struct node{
ElemType data;
struct node* next;
}LNode,*LinkList;

創建一個鏈表如下：

LinkList CreatLinkList(int n){
/*建立一個長度為n的鏈表*/
LinkList p,r,list=NULL;
ElemType e;
int i;
for(i=1;i<=n;i++){
Get(e);//輸入獲取數據
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=NULL;
if(!list)
   list=p;
else
  r->next=p;
 r=p;
}
return list;
}

上述的代碼思路是:調用函數 CreatLinlList(n);的時候，當i=1的時候，list是為null，此時將p的值賦值給表頭（list），同時將p的值給此時的r,第二次i=2的時候list不為null,而此時p的值是一個新的結點，這是就要用到r了，r是上一個p的值，將r->next=p,表示將新的p值接上上一個值，此時重新將r值更新為這次的p值，之後迴圈。

  向鏈表中插入結點（下麵介紹的是在指針q指向的結點後面插入結點）：

（1）先創建一個新的結點，並將指針p指向該結點

（2）將q指向的結點的next域的值(q->next)賦值給p->next;

（3）在將q->next=p;

上圖就是插入的過程.

代碼如下:

void insertList(LinkList *list,LinkList q,ElemType e){
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
if(!*list){
*list=p;//向空鏈表插入元素
p->next=NULL;
}
else{
p->next=q->next;
q->next=p;
}
}

刪除鏈表元素代碼如下:

void delLink(LinkList *list,LinkList q){
LinkList r;
if(q==*list){
*list=q->next;
free(q);
}
else{
for(r=*list;r->next!=q;r=r->next);//遍歷鏈表找到q的前驅結點
if(r->next!=NULL){
r->next=q->next;
free(q);
}
}
}

 銷毀一個鏈表代碼如下：

void destroyLinkList(LinkList *list){
LinkList p,q;
p=*list;
while(p){
q=p->next;
free(p);
p=q;
}
*list=NULL;
}

 案例分析：

#include "stdio.h"
#include <stdlib.h>
typedef int ElemType;
typedef struct node{
ElemType data;
struct node* next;
}LNode,*LinkList;
LinkList CreatLinkList(int n){
/*建立一個長度為n的鏈表*/
LinkList p,r,list=NULL;
ElemType e;
int i;
for(i=1;i<=n;i++){
scanf("%d",&e);//輸入獲取數據
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=NULL;
if(!list)
   list=p;
else
  r->next=p;
 r=p;
}
return list;
}
void insertList(LinkList *list,LinkList q,ElemType e){
LinkList p;
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
if(!*list){
*list=p;//向空鏈表插入元素
p->next=NULL;
}
else{
p->next=q->next;
q->next=p;
}
}
void delLink(LinkList *list,LinkList q){
LinkList r;
if(q==*list){
*list=q->next;
free(q);
}
else{
for(r=*list;r->next!=q;r=r->next);//遍歷鏈表找到q的前驅結點
if(r->next!=NULL){
r->next=q->next;
free(q);
}
}
}
void destroyLinkList(LinkList *list){
LinkList p,q;
p=*list;
while(p){
q=p->next;
free(p);
p=q;
}
*list=NULL;
}
void main()
{
    int e,i;
    LinkList l,q;
    q=l=CreatLinkList(1);
    scanf("%d",&e);
    while(e){
    insertList(&l,q,e);
    q=q->next;
    scanf("%d",&e);
    }
    q=l;
    printf("The content of the linklist:\n");
    while(q)
    {
        printf("%d ",q->data);
        q=q->next;
    }
    q=l;
    printf("\nDelete the fifth element\n");
    for(i=0;i<4;i++)
    {
        if(q==NULL){
        printf("the length of the linklist is smaller than 5!\n");
        getchar();
        return;
        }
        q=q->next;
    }
    delLink(&l,q);
    q=l;
    while(q)
    {    
        printf("%d ",q->data);
        q=q->next;
    }
    destroyLinkList(&l);
    getchar();


}