大話數據結構之二（線性表） - liyunhua－IT工程師數位筆記本

文章出處

線性表的抽象數據類型

什么是線性表。線性表其實就是零個或多個數據元素的有限序列。

在較復雜的線性表中，一個數據元素可以由若干個數據項組成

線性表的抽象數據類型如下：

線性表的順序存儲結構

事實上我們可以用c語言的一維數組來實現順序存儲結構，源碼如下：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存儲空間初始分配量 */

typedef int Status;          /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef int ElemType;        /* ElemType類型根據實際情況而定，這里假設為int */


Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}

typedef struct
{
    ElemType data[MAXSIZE];        /* 數組，存儲數據元素 */
    int length;                                /* 線性表當前長度 */
}SqList;

/* 初始化順序線性表 */
Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}

/* 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */
Status ListEmpty(SqList L)
{ 
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

/* 初始條件：順序線性表L已存在。操作結果：將L重置為空表 */
Status ClearList(SqList *L)
{ 
    L->length=0;
    return OK;
}

/* 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數 */
int ListLength(SqList L)
{
    return L.length;
}

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e返回L中第i個數據元素的值,注意i是指位置，第1個位置的數組是從0開始 */
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
            return ERROR;
    *e=L.data[i-1];//只要i的數值在數組下標范圍內就把數組第i-1下標的值返回

    return OK;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結果：返回L中第1個與e滿足關系的數據元素的位序。 */
/* 若這樣的數據元素不存在，則返回值為0 */
int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)//如果是空表
            return 0;
    for(i=0;i<L.length;i++)
    {
            if (L.data[i]==e)//找到
                    break;
    }
    if(i>=L.length)//判斷是否越界
            return 0;

    return i+1;//返回所在索引位置
}


/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{ 
    int k;
    if (L->length==MAXSIZE)  /* 順序線性表已經滿 */
        return ERROR;
    if (i<1 || i>L->length+1)/* 當i比第一位置小或者比最后一位置后一位置還要大時 */
        return ERROR;

    if (i<=L->length)        /* 若插入數據位置不在表尾 */
    {
        for(k=L->length-1;k>=i-1;k--)  /* 將要插入位置之后的數據元素向后移動一位 */
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;          /* 將新元素插入 */
    L->length++;

    return OK;
}

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1 */
Status ListDelete(SqList *L,int i,ElemType *e) 
{ 
    int k;
    if (L->length==0)               /* 線性表為空 */
        return ERROR;
    if (i<1 || i>L->length)         /* 刪除位置不正確 */
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)                /* 如果刪除不是最后位置 */
    {
        for(k=i;k<L->length;k++)/* 將刪除位置后繼元素前移 */
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結果：依次對L的每個數據元素輸出 */
Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
            visit(L.data[i]);
    printf("\n");
    return OK;
}
/* 將所有的在線性表Lb中但不在La中的數據元素插入到La中 */
void unionL(SqList *La,SqList Lb)
{
    int La_len,Lb_len,i;
    ElemType e;//聲明與La和Lb相同的數據元素e
    La_len=ListLength(*La);//獲得線性表的長度
    Lb_len=ListLength(Lb);
    for (i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);//取得Lb中第i個數據元素賦給e
        if (!LocateElem(*La,e))//La中不存在和e相同數據元素
            ListInsert(La,++La_len,e);//插入
    }
}

void main()
{
        
    SqList L;
    SqList Lb;
    
    ElemType e;
    Status i;
    int j,k;
    i=InitList(&L);
    printf("初始化L后：L.length=%d\n",L.length);
    for(j=1;j<=5;j++)
            i=ListInsert(&L,1,j);
    printf("在L的表頭依次插入1～5后：L.data=");
    ListTraverse(L); 

    printf("L.length=%d \n",L.length);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    i=ClearList(&L);
    printf("清空L后：L.length=%d\n",L.length);
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    for(j=1;j<=10;j++)
            ListInsert(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L); 

    printf("L.length=%d \n",L.length);

    ListInsert(&L,1,0);
    printf("在L的表頭插入0后：L.data=");
    ListTraverse(L); 
    printf("L.length=%d \n",L.length);

    GetElem(L,5,&e);
    printf("第5個元素的值為：%d\n",e);
    for(j=3;j<=4;j++)
    {
            k=LocateElem(L,j);
            if(k)
                    printf("第%d個元素的值為%d\n",k,j);
            else
                    printf("沒有值為%d的元素\n",j);
    }
    

    k=ListLength(L); /* k為表長 */
    for(j=k+1;j>=k;j--)
    {
            i=ListDelete(&L,j,&e); /* 刪除第j個數據 */
            if(i==ERROR)
                    printf("刪除第%d個數據失敗\n",j);
            else
                    printf("刪除第%d個的元素值為：%d\n",j,e);
    }
    printf("依次輸出L的元素：");
    ListTraverse(L); 

    j=5;
    ListDelete(&L,j,&e); /* 刪除第5個數據 */
    printf("刪除第%d個的元素值為：%d\n",j,e);

    printf("依次輸出L的元素：");
    ListTraverse(L); 

    //構造一個有10個數的Lb
    i=InitList(&Lb);
    for(j=6;j<=15;j++)
            i=ListInsert(&Lb,1,j);

    unionL(&L,Lb);

    printf("依次輸出合并了Lb的L的元素：");
    ListTraverse(L); 

    scanf('&a');//這句話是為了讓屏幕暫停
}

View Code

這里強調一下：

插入操作的思路

刪除操作的思路

線性表順序存儲結構的優缺點：

線性表鏈式存儲結構

先來看看什么叫鏈式存儲？

單鏈表就是每個結點只包含一個指針域，那如果包含兩個就叫雙鏈表了。

鏈表中第一個結點的存儲位置叫做頭指針，有時候我們為了更加方便的對鏈表進行操作，會在單鏈表的第一個結點前附設一個結點，稱為頭結點。頭結點的數據域可以不存儲任何信息也可以存儲如線性表的長度等附加信息，頭結點的指針域指向第一個結點的指針。

頭指針和頭結點的異同

單鏈表的存儲結果示意圖

帶有頭結點的單鏈表

空鏈表

線性表的鏈式存儲結構源碼

鏈式存儲結構單鏈表讀取在最壞情況下的時間復雜度為O(n) （做讀取的時候只能一直“指針后移”的方式進行比較）

單鏈表的插入操作核心代碼只有兩句：

    s->next = p->next;      /* 將p的后繼結點賦值給s的后繼  */
    p->next = s;          /* 將s賦值給p的后繼 */

這兩句話事實上就做了如下圖所示的事情

單鏈表的刪除操作核心代碼：

    q = p->next;
    p->next = q->next;            /* 將q的后繼賦值給p的后繼 */

事實上這兩句代碼只做了如下圖所示的一件事：將它的前繼結點的指針繞過，指向它的后繼結點。如下圖所示

單鏈表的整表創建有兩種方式:

頭插法
尾插法

頭插法示意圖：

尾插法核心代碼如下：

        r->next=p;                        /* 將表尾終端結點的指針指向新結點 */
        r = p;                            /* 將當前的新結點定義為表尾終端結點 */

尾插法的核心思想就是L是整個鏈表，r是始終指向尾結點的變量，r會隨著循環不斷變化而L則隨著循環增長為一個多結點的鏈表，在循環中始終中將表尾終端結點的指針指向新結點，然后再生成的新的結點賦值給r，這樣就能保證r始終為最尾終端結點

示意圖如下

整個的源碼如下所示：

#include "stdio.h"    
#include "string.h"
#include "ctype.h"      
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存儲空間初始分配量 */

typedef int Status;/* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據實際情況而定，這里假設為int */


Status visit(ElemType c)
{
    printf("%d ",c);
    return OK;
}

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定義LinkList */

/* 初始化順序線性表 */
Status InitList(LinkList *L) 
{ 
    *L=(LinkList)malloc(sizeof(Node)); /* 產生頭結點,并使L指向此頭結點 */
    if(!(*L)) /* 存儲分配失敗 */
            return ERROR;
    (*L)->next=NULL; /* 指針域為空 */

    return OK;
}

/* 初始條件：順序線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */
Status ListEmpty(LinkList L)
{ 
    if(L->next)
            return FALSE;
    else
            return TRUE;
}

/* 初始條件：順序線性表L已存在。操作結果：將L重置為空表 */
Status ClearList(LinkList *L)
{ 
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一個結點 */
    while(p)                /*  沒到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 頭結點指針域為空 */
    return OK;
}

/* 初始條件：順序線性表L已存在。操作結果：返回L中數據元素個數 */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一個結點 */
    while(p)                        
    {
        i++;
        p=p->next;
    }
    return i;
}

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：用e返回L中第i個數據元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
    //從頭開始找，直到第i個元素為止
    int j;
    LinkList p;        /* 聲明一結點p指向鏈表的第一個結點*/
    p = L->next;        /* 讓p指向鏈表L的第一個結點 */
    j = 1;        /*  j為計數器 從1開始*/
    while (p && j<i)  /* p不為空或者計數器j還沒有等于i時，循環繼續 */
    {   
        p = p->next;  /* 讓p指向下一個結點 */
        ++j;/* j累加 */
    }
    if ( !p || j>i ) 
        return ERROR;  /*  第i個元素不存在 */
    *e = p->data;   /*  取第i個元素的數據 */
    return OK;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結果：返回L中第1個與e滿足關系的數據元素的位序。 */
/* 若這樣的數據元素不存在，則返回值為0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到這樣的數據元素 */
                return i;
        p=p->next;
    }

    return 0;
}


/* 初始條件：順序線性表L已存在,1≤i≤ListLength(L)， */
/* 操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{ 
    int j;
    LinkList p,s;
    p = *L;  //p指向鏈表的第一個結點 
    j = 1;//j從1開始
    while (p && j < i)     /* 尋找第i個結點 */
    {
        p = p->next;
        ++j;
    } 
    if (!p || j > i) 
        return ERROR;   /* 第i個元素不存在 */
    s = (LinkList)malloc(sizeof(Node));  /*  生成新結點(C語言標準函數) */
    s->data = e;  
    s->next = p->next;      /* 將p的后繼結點賦值給s的后繼  */
    p->next = s;          /* 將s賦值給p的后繼 */
    return OK;
}

/* 初始條件：順序線性表L已存在，1≤i≤ListLength(L) */
/* 操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1 */
Status ListDelete(LinkList *L,int i,ElemType *e) 
{ 
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while (p->next && j < i)    /* 遍歷尋找第i個元素 */
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i) 
        return ERROR;           /* 第i個元素不存在 */
    q = p->next;
    p->next = q->next;            /* 將q的后繼賦值給p的后繼 */
    *e = q->data;               /* 將q結點中的數據給e */
    free(q);                    /* 讓系統回收此結點，釋放內存 */
    return OK;
}

/* 初始條件：順序線性表L已存在 */
/* 操作結果：依次對L的每個數據元素輸出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

/*  隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（頭插法） */
void CreateListHead(LinkList *L, int n) 
{
    LinkList p;//聲明結點
    int i;//計數器變量
    srand(time(0));                         /* 初始化隨機數種子 */
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;                      /*  先建立一個帶頭結點的單鏈表 */
    for (i=0; i<n; i++) 
    {
        p = (LinkList)malloc(sizeof(Node)); /*  生成新結點 */
        p->data = rand()%100+1;             /*  隨機生成100以內的數字 */
        p->next = (*L)->next;    
        (*L)->next = p;                        /*  插入到表頭 */
    }
}

/*  隨機產生n個元素的值，建立帶表頭結點的單鏈線性表L（尾插法） */
void CreateListTail(LinkList *L, int n) 
{
    LinkList p,r;
    int i;
    srand(time(0));                      /* 初始化隨機數種子 */
    *L = (LinkList)malloc(sizeof(Node)); /* L為整個線性表 */
    r=*L;                                /* r為指向尾部的結點 */
    for (i=0; i<n; i++) 
    {
        p = (Node *)malloc(sizeof(Node)); /*  生成新結點 */
        p->data = rand()%100+1;           /*  隨機生成100以內的數字 */
        r->next=p;                        /* 將表尾終端結點的指針指向新結點 */
        r = p;                            /* 將當前的新結點定義為表尾終端結點 */
    }
    r->next = NULL;                       /* 表示當前鏈表結束 */
}

void main()
{        
    LinkList L;
    ElemType e;
    Status i;
    int j,k;
    i=InitList(&L);
    printf("初始化L后：ListLength(L)=%d\n",ListLength(L));
    for(j=1;j<=5;j++)
            i=ListInsert(&L,1,j);
    printf("在L的表頭依次插入1～5后：L.data=");
    ListTraverse(L); 

    printf("ListLength(L)=%d \n",ListLength(L));
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    i=ClearList(&L);
    printf("清空L后：ListLength(L)=%d\n",ListLength(L));
    i=ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",i);

    for(j=1;j<=10;j++)
            ListInsert(&L,j,j);
    printf("在L的表尾依次插入1～10后：L.data=");
    ListTraverse(L); 

    printf("ListLength(L)=%d \n",ListLength(L));

    ListInsert(&L,1,0);
    printf("在L的表頭插入0后：L.data=");
    ListTraverse(L); 
    printf("ListLength(L)=%d \n",ListLength(L));

    GetElem(L,5,&e);
    printf("第5個元素的值為：%d\n",e);
    for(j=3;j<=4;j++)
    {
            k=LocateElem(L,j);
            if(k)
                    printf("第%d個元素的值為%d\n",k,j);
            else
                    printf("沒有值為%d的元素\n",j);
    }
    

    k=ListLength(L); /* k為表長 */
    for(j=k+1;j>=k;j--)
    {
            i=ListDelete(&L,j,&e); /* 刪除第j個數據 */
            if(i==ERROR)
                    printf("刪除第%d個數據失敗\n",j);
            else
                    printf("刪除第%d個的元素值為：%d\n",j,e);
    }
    printf("依次輸出L的元素：");
    ListTraverse(L); 

    j=5;
    ListDelete(&L,j,&e); /* 刪除第5個數據 */
    printf("刪除第%d個的元素值為：%d\n",j,e);

    printf("依次輸出L的元素：");
    ListTraverse(L); 

    i=ClearList(&L);
    printf("\n清空L后：ListLength(L)=%d\n",ListLength(L));
    CreateListHead(&L,20);
    printf("整體創建L的元素(頭插法)：");
    ListTraverse(L); 
    
    i=ClearList(&L);
    printf("\n刪除L后：ListLength(L)=%d\n",ListLength(L));
    CreateListTail(&L,20);
    printf("整體創建L的元素(尾插法)：");
    ListTraverse(L); 


   scanf("&a");
}

View Code

單鏈表結構與順序存儲結構優缺點

靜態鏈表

用數組描述的鏈表就叫靜態鏈表（靜態鏈表讓我覺得人類的智慧真是太無窮了）

我們都知道c語言是有指針的，但是早期的高級編程語言是沒有指針的，但是鏈表結構在沒有指針的情況下應該怎么弄呢，這時候就想到了一種方案“靜態鏈表”。我們來看一下如果我們已經將數據存入靜態鏈表中，比如分別存儲甲乙丁...如下圖所示

靜態鏈表插入

假設我們需要在乙丁之間插入一個值為丙的元素，事實上只要做三步操作

將丙放到備用鏈表第一個位置
修改丙的cur為乙的cur游標
修改乙的cur游標為丙所在的索引
修改下標為0的cur的位置為新的備用鏈表第一個結點的下標

靜態鏈表刪除：

1、將下標為999（也就是最后一個元素）的cur修改為要刪除的元素的下標

2、將要刪除的元素的cur為下標為0的cur（也就是說現在要刪除的元素才是備用鏈表的第一個結點，原先備用鏈表的第一個結點成為將要刪除元素的后繼結點了）

3、將要刪除的分量下標賦值給第一個元素的cur

如上所述思想，假設甲要被刪除的話，則示意圖如下所示：

靜態鏈表的實現源碼如下所示：

#include "string.h"
#include "ctype.h"      

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 1000 /* 存儲空間初始分配量 */

typedef int Status;           /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef char ElemType;        /* ElemType類型根據實際情況而定，這里假設為char */


Status visit(ElemType c)
{
    printf("%c ",c);
    return OK;
}

/* 線性表的靜態鏈表存儲結構 */
typedef struct 
{
    ElemType data;
    int cur;  /* 游標(Cursor) ，為0時表示無指向 */
} Component,StaticLinkList[MAXSIZE];


/* 將一維數組space中各分量鏈成一個備用鏈表，space[0].cur為頭指針，"0"表示空指針 */
Status InitList(StaticLinkList space) 
{
    int i;
    for (i=0; i<MAXSIZE-1; i++)  
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0; /* 目前靜態鏈表為空，最后一個元素的cur為0 */
    return OK;
}


/* 若備用空間鏈表非空，則返回分配的結點下標，否則返回0 */
int Malloc_SSL(StaticLinkList space) 
{ 
    int i = space[0].cur;                   /* 當前數組第一個元素的cur存的值 */
                                            /* 就是要返回的第一個備用空閑的下標 */
    if (space[0]. cur)         
        space[0]. cur = space[i].cur;       /* 由于要拿出一個分量來使用了， */
                                            /* 所以我們就得把它的下一個 */
                                            /* 分量用來做備用 */
    return i;
}


/*  將下標為k的空閑結點回收到備用鏈表 */
void Free_SSL(StaticLinkList space, int k) 
{  
    space[k].cur = space[0].cur;    /* 把第一個元素的cur值賦給要刪除的分量cur */
    space[0].cur = k;               /* 把要刪除的分量下標賦值給第一個元素的cur */
}

/* 初始條件：靜態鏈表L已存在。操作結果：返回L中數據元素個數 */
int ListLength(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}

/*  在L中第i個元素之前插入新的數據元素e   */
Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;   /* 注意k首先是最后一個元素的下標 */
    if (i < 1 || i > ListLength(L) + 1)   
        return ERROR;   
    j = Malloc_SSL(L);   /* 獲得空閑分量的下標 */
    if (j)   
    {   
        L[j].data = e;   /* 將數據賦值給此分量的data */
        for(l = 1; l <= i - 1; l++)   /* 找到第i個元素之前的位置 */
           k = L[k].cur;           
        L[j].cur = L[k].cur;    /* 把第i個元素之前的cur賦值給新元素的cur */
        L[k].cur = j;           /* 把新元素的下標賦值給第i個元素之前元素的ur */
        return OK;   
    }   
    return ERROR;   
}

/*  刪除在L中第i個數據元素   */
Status ListDelete(StaticLinkList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return ERROR;   
    k = MAXSIZE - 1;   
    for (j = 1; j <= i - 1; j++)   
        k = L[k].cur;   
    j = L[k].cur;   
    L[k].cur = L[j].cur;   
    Free_SSL(L, j);   
    return OK;   
} 

Status ListTraverse(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
            visit(L[i].data);
            i=L[i].cur;
            j++;
    }
    return j;
    printf("\n");
    return OK;
}


int main()
{
    StaticLinkList L;
    Status i;
    i=InitList(L);
    printf("初始化L后：L.length=%d\n",ListLength(L));

    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');

    printf("\n在L的表頭依次插入FEDBA后：\nL.data=");
    ListTraverse(L); 

    i=ListInsert(L,3,'C');
    printf("\n在L的“B”與“D”之間插入“C”后：\nL.data=");
    ListTraverse(L); 

    i=ListDelete(L,1);
    printf("\n在L的刪除“A”后：\nL.data=");
    ListTraverse(L); 

    printf("\n");

    return 0;
}