線性表——最基礎的資料結構

1、什麼是線性表？

​ 在學習線性表之前，我們首先需要了解線性表是什麼

​ 線性表是最基本、最簡單、也是最常用的一種資料結構。線性表（linear list）是資料結構中的一種，一個線性表是n個具有相同特性的資料元素的有限序列。

​ 線性表中資料元素之間的關系是一對一的關系，即除了第一個和最後一個資料元素之外，其它資料元素都是首尾相接的（注意，這句話隻适用大部分線性表，而不是全部。比如，循環連結清單邏輯層次上也是一種線性表（存儲層次上屬于鍊式存儲，但是把最後一個資料元素的尾指針指向了首位結點）

​ 我們說“線性”和“非線性”，隻在邏輯層次上讨論，而不考慮存儲層次，是以雙向連結清單和循環連結清單依舊是線性表。

2、線性表的分類

（圖檔來自網絡，侵删）

3、順式結構

定義：

​ 線性表的順序存儲是指在記憶體中用位址連續的一塊存儲空間依次存放線性表的資料元素，用這種存儲形式存儲的線性表稱為順序表。

其儲存方式如下圖所示：

順序存儲的實作方式：

#include<iostream>
#define MAXSIZE 100        //定義最大儲存空間
#define ElemType int        //定義資料類型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1

using namespace std;

//定義順序表
typedef struct LNode *List;
struct LNode{
    ElemType Data[MAXSIZE];
    int Last;
};           

建立一個空的順序表：

List MakeEmpty(){
    //構造一個空的線性表Ptrl
    List L
    L= new LNode;    //配置設定存放順序表的空間
    L->Last = 0;
    return L;
}           

輸入順序表/初始化順序表

void MakeList(List Ptrl)
{
    int i;
    cin >> n;        //輸入需要的表長
    for(i = 0; i < n; i++){
        cin >> Ptrl->Data[i];    
    }
    L->Last = n;        //設定表長
}           

銷毀/删除順序表：

void DestroyList(List Ptrl)
{
    delete Ptrl；
}           

按資料元素查找：

int Find(List Ptrl, ElemType X)
{
    int i = 0;
    while(i <= Ptrl->Last && Ptrl->Data[i] != X)
        i++;
    if (i > Ptrl->Last)
         return ERROR;
    else
        return i;           

順序表的插入：

bool Insert(List Ptrl, ElementType X, int i)
{
    int j;

    if (Ptrl->Last >= MAXSIZE-1)        //判斷空間是否已滿
    {
        cout << "NO SPACE";
        return OVERFLOW;
    }
    if (i < 1 ||i > Ptrl->Last+2)        //判斷是否非法輸入
    {
        cout << "ILLEGAL INPUT";
        return ERROR;
    }
    for (j = Ptrl->Last; j >= i-1; j--)        //将位置i後面的元素後移一個位置
    {
        Ptrl->Data[j+1] = Ptrl->Data[j];
    }
    Ptrl->Data[i-1] = X;    //插入資料
    Ptrl->Last++;    //順序表長度加1
    return TRUE;
}           

順序表的删除：

bool Delete(List Ptrl, int i)
{
    int j;

    if (i < 1 ||i > Ptrl->Last+1)        //判斷是否非法輸入
    {
        cout << "ILLEGAL INPUT";
        return ERROR;
    }
    for (j = i; j <= Ptrl->Last; j++)        //将位置i後面的元素前移一個位置
    {
        Ptrl->Data[j-1] = Ptrl->Data[j];
    }
    Ptrl->Last--;    //順序表長度減1
    return TRUE;
}           

4、鍊式結構

​ 線性表的鍊式存儲結構的特點是用一組任意的存儲單元存儲線性表的資料元素，這組存儲單元可以是連續的，也可以是不連續的。這就意味着，這些元素可以存在記憶體未被占用的任意位置。

鍊式結構的實作方式：

#include<iostream>
#define MAXSIZE 100        //定義最大儲存空間
#define ElemType int        //定義資料類型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1

using namespace std;

//定義連結清單
typedef struct LNode *List;
struct LNode{
    ElemType Data;
    List *Next;
};           

求一個連結清單的表長：

int length(List Ptrl){
    List P = Ptrl;    int j = 0;
    while(P){
        P = P->Next;    //指向下一個結點
        j++;        //目前P指向的是第j個節點    
        }
    return j;}           

查找第K項：

List FindKth(int K, List Ptrl){
    List P = Ptrl;    int i = 1;    
       while(P != nullptr && i < K){
        P = P->Next;
        i++;
       }
    if(i == K)
        return P;
    else
        return NULL;
}           

按值查找：

List Find(ElemType X, List Ptrl){
    List P = Ptrl;    int i = 1;
    while(P != nullptr && P->Data[i] != K){
        P = P->Next;
        i++;
    }
    if(P)
        return ERROR;
    else
        return P;
}           

連結清單的插入：

List Insert(ElemType X,  int i, List Ptrl){    List P, s;
    if(i == 1){        //新結點在第1位
        s = (List)malloc(sizeof(struct LNode));    //也可以這樣去申請空間
         s = new(LNode);
        s->Data = X;
        s->Next = Ptrl;
        return s;
    }
    P = FindKth(i-1, Ptrl);    //查找第i-1個結點
    if(P == nullptr){    //第i-1個結點不存在，不能插入
        cout << "error";
        return nullptr;
    }
    else{
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = P->Next;        //新結點插在第i-1個結點的後面
        P->Next = s;
        return Ptrl;    
        }
}           

連結清單的删除：

List Delete(int i, List Ptrl){
    List P, s;
    if(i == 1){    //如果删除的是第1個結點
        s = Ptrl;    //s指向第1個結點
        if(Ptrl != nullptr)
            Ptrl = Ptrl->Next;        //從連結清單中删除
        else
            return nullptr;
        delete s;        //釋放被删除結點所申請的空間，防止記憶體洩漏
        return Ptrl;
    }
    P = FindKth(i-1, Ptrl);    //查找第i-1個結點
    if(P == nullptr){
        cout << "error";
        return NULL;
    }
    else if(P->Next == nullptr){
        cout << "not instance";
         return nullptr;
        }
    else{
        s = P->Next;
        P->Next = s->Next;        //删除結點
        delete s;
        return Ptrl;
    }
}           

5、順式結構和鍊式結構的優缺點總結

1、順序存儲結構

優點：可以随機通路，在O(1)内查詢、修改元素，存儲容量高

缺點：在O(n)内插入和删除資料，修改困難，存儲空間需要一次性獲得，表示關系能力弱

2、鍊式存儲結構

優點：空間任意，便于删改，表示關系的能力強，在O(1)内插入、删除元素

缺點：占用空間較多，必須通過指針來通路元素，在O(n)内查找、修改元素