發(fā)現(xiàn)更多計算機知識，歡迎訪問Cr不是鉻的個人網(wǎng)站

1.1線性表的定義

線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列
對應的邏輯結構圖形：

file

從線性表的定義中可以看出它的特性：

（1）有窮性：一個線性表中的元素個數(shù)是有限的

（2）一致性：一個線性表中所有元素的性質相同，即數(shù)據(jù)類型相同

（3）序列性：各個元素的相對位置是線性的

1.2線性表的抽象數(shù)據(jù)類型描述

（如下圖所示）

file

那為什么要引進這個數(shù)據(jù)結構呢送巡？那就不得不談談它的作用了。

線性表的作用體現(xiàn)在兩個方面：

a. 當一個線性表實現(xiàn)后善茎，程序員加油直接使用它來存放數(shù)據(jù)缭召，即作為存放數(shù)據(jù)的容器

b.使用線性表的基本運算來完成更復雜的運算

2.1線性表的順序存儲結構——順序表

線性表的順序存儲結構簡稱為順序表

file

（如圖為線性表到順序表的映射）

需要注意的是順序表采用數(shù)組進行實現(xiàn)滋捶，但是不是任意數(shù)組可以作為一個順序表撞鹉，二者運算是不同的

下圖為順序表的存儲示意圖

file

2.2順序表的基本運算實現(xiàn)

（1）結構體SqList定義

//數(shù)據(jù)元素
typedef int ElemType;
//結構體
typedef struct
{
    ElemType data[MaxSize];
    //數(shù)據(jù)長度
    int length;
}SqList;

（2）建立順序表

//建立順序表
void CreateList(SqList*& L, ElemType a[], int n)
{
    int i = 0, k = 0;
    //記得一定要分配內存空間 
    L = (SqList*)malloc(sizeof(SqList));
    while (i < n)
    {
        //將a[i]存儲到L中
        L->data[k] = a[i];
        k++; i++;
    }
    L->length = k;
}

（3）初始化線性表

void InitList(SqList*& L)
{
    L = (SqList*)malloc(sizeof(SqList));
    L->length = 0; //置空線性表的長度為0
}

(4)銷毀線性表

void DestroyList(SqList*& L)
{
    free(L);//釋放L所指的順序表空間
}

(5)判斷是否為空

bool ListEmpty(SqList* L)
{
    return(L->length == 0);
}

(6)求線性表長度

int ListLength(SqList* L)
{
    return (L->length);
}

（7）求表中某個值

bool GetElem(SqList* L, int i, ElemType& e)
{
    if (i<1 || i > L->length)
        return false;
    e = L->data[i - 1];
    return true;    //成功找到元素返回true
}

（8）按照元素值查找

int LocateElem(SqList* L,ElemType e)
{
    int i = 0;
    while (i < L->length && L->data[i] != e)
        i++;
    if (i >= L->length)
        return 0;
    else
        return i + 1;       //返回邏輯序號
}

（9）輸出線性表

void DisplayList(SqList* L)
{
    for (int i = 0; i < L->length; i++)
        printf("%d", L->data[i]);
    printf("\n");
}

(10)完整代碼

#include<iostream>
using namespace std;
const int MaxSize = 1005;
typedef int ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int length;
}SqList;

//建立順序表
void CreateList(SqList*& L, ElemType a[], int n)
{
    int i = 0, k = 0;
    //記得一定要分配內存空間 
    L = (SqList*)malloc(sizeof(SqList));
    while (i < n)
    {
        L->data[k] = a[i];
        k++; i++;
    }
    L->length = k;
}
//初始化線性表
void InitList(SqList*& L)
{
    L = (SqList*)malloc(sizeof(SqList));
    L->length = 0; //置空線性表的長度為0
}
void DestroyList(SqList*& L)
{
    free(L);//釋放L所指的順序表空間
}
bool ListEmpty(SqList* L)
{
    return(L->length == 0);
}

int ListLength(SqList* L)
{
    return (L->length);
}
void DisplayList(SqList* L)
{
    for (int i = 0; i < L->length; i++)
        printf("%d", L->data[i]);
    printf("\n");
}
bool GetElem(SqList* L, int i, ElemType& e)
{
    if (i<1 || i > L->length)
        return false;
    e = L->data[i - 1];
    return true;    //成功找到元素返回true
}
int LocateElem(SqList* L,ElemType e)
{
    int i = 0;
    while (i < L->length && L->data[i] != e)
        i++;
    if (i >= L->length)
        return 0;
    else
        return i + 1;       //返回邏輯序號
}
bool ListInsert(SqList*& L, int i, ElemType e)
{
    int j;
    if (i < 1 || i >L->length + 1 || L->length == MaxSize)
        return false;
    i--;
    for (j = L->length; j > i; j--)
        L->data[j] = L->data[j - 1];
    L->data[i] = e;
    L->length++;
    return true;
}
bool ListDelete(SqList*& L, int i, ElemType& e)
{
    int j;
    //特判是否符合 
    if (i < 1 || i>L->length)
        return false;
    i--;
    for (int j = i; j < L->length - 1; j++)
        L->data[j] = L->data[j + 1];
    L->length--;
    return true;
}
void delnodel(SqList*& L, ElemType x)
{
    int k = 0;
    for (int i = 0; i < L->length; i++)
        if (L->data[i] != x)
        {
            L->data[k] = L->data[i];
            k++;
        }
    L->length = k;
}

}
int main() {
    SqList* L;
    int a[10] = { 7,5,7,7,9,1,6,2,4,8 };
    CreateList(L, a, 10);

    DisplayList(L);
}

2.3線性表的鏈式存儲結構——鏈表

線性表的鏈式存儲就是鏈表疟丙，每個鏈表存儲點不僅包括數(shù)據(jù)域，還有指針域孔祸。

鏈表示意圖如下：

file

2.4 單鏈表算法實現(xiàn)

（1）數(shù)據(jù)結構聲明

typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;      //存放元素值
    struct LinkNode* next;  //指向后繼結點

}LinkNode;

建立單鏈表有兩種方法：頭插法和尾插法

(2)頭插法

//建立單鏈表
void CreatListF(LinkNode*& L, ElemType a[], int n)
{
    LinkNode* s;
    //創(chuàng)建頭結點 
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL; //頭結點指針域置NULL
    for (int i = 0; i < n; i++)
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));//重新分配空間
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
}

(3)尾插法

void CreatListR(LinkNode*& L, ElemType a[], int n)
{
    LinkNode* s, * r;
    //創(chuàng)建頭結點
    L = (LinkNode*)malloc(sizeof(LinkNode));
    r = L;                      //r始終指向尾結點隆敢，初始時指向頭結點
    for (int i = 0; i < n; i++)
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));//重新分配空間
        s->data = a[i];
        r->next = s;
        r = s;
    }
    //尾結點的nextt域置為NULL
    r->next = NULL;         
}

(4)初始化

void InitList(LinkNode*& L)
{
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = NULL;
}

(5)銷毀表

void DestroyList(LinkNode*& L)
{
    LinkNode* pre = L, * p = L->next;   //pre指向p的前驅結點
    while (p != NULL)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);      //循環(huán)結束時p為NULL发皿，pre指向尾結點
}

(6)輸出表

void DispList(LinkNode* L)
{
    LinkNode* p = L->next;//指向頭結點
    while (p!=NULL)
    {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

重點４藁邸！穴墅！

（7）鏈表的插入

bool ListInsert(LinkNode*& L, int i, ElemType e)
{
    int j = 0;
    LinkNode* p = L, * s;
    if (i <= 0)return false;//首結點的次序是一
    while (j < i - 1 && p != NULL)//找到第i-1個結點
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        s = (LinkNode*)malloc(sizeof(LinkNode));
        //典中典
        s->data = e;
        s->next = p->next;
        p->next = s;
        return true;
    }
}

(8)刪除某個元素

bool ListDelete(LinkNode*& L, int i, ElemType& e)
{
    int j = 0;
    LinkNode* p = L, * q;
    if (i <= 0)return false;//頭結點是不計入其中的
    while (j < i - 1 && p != NULL)
    {
        j++;
        p = p->next;
    }       
    if (p == NULL)
        return false;
    else {
        q = p->next;
        if (q == NULL)
            return false;
        e = q->data;
        p->next = q->next;
        free(q);
        return true;
    }
}

最后介紹一下雙鏈表

2.5雙鏈表

(1)建立雙鏈表

typedef int ElemType;
// 定義DlinkNode結構體
struct DlinkNode {
    int data;           // 數(shù)據(jù)域
    DlinkNode* prior;   // 前驅指針
    DlinkNode* next;    // 后繼指針
};

同樣的惶室，雙鏈表的建立也有頭插法和尾插法

（2）頭插法

// 定義CreateListF函數(shù)
void CreateListF(DlinkNode*& L, ElemType a[], int n)
{
    DlinkNode* s;
    L = (DlinkNode*)malloc(sizeof(DlinkNode)); // 創(chuàng)建頭結點
    L->prior = L->next = NULL; // 先后指針域置NULL
    for (int i = 0; i < n; i++) // 循環(huán)創(chuàng)建數(shù)據(jù)結點
    {
        s = (DlinkNode*)malloc(sizeof(DlinkNode)); // 創(chuàng)建數(shù)據(jù)結點s
        s->data = a[i];
        s->next = L->next; // 將S插到頭結點之后
        if (L->next != NULL)
            L->next->prior = s;
        L->next = s;
        s->prior = L;
    }
}

(3)尾插法

void CreateListR(DlinkNode*& L, ElemType a[], int n)
{
    DlinkNode* s,*r;
    L = (DlinkNode*)malloc(sizeof(DlinkNode)); // 創(chuàng)建頭結點
    r = L;          //r始終指向尾結點温自，開始時指向頭結點
    for (int i = 0; i < n; i++) // 循環(huán)創(chuàng)建數(shù)據(jù)結點
    {
        s = (DlinkNode*)malloc(sizeof(DlinkNode)); // 創(chuàng)建數(shù)據(jù)結點s
        s->data = a[i];
        r->next = s; s->prior = r;      //將s結點插入到r結點之后
        r = s;                          //r指向尾結點
    }
    r->next = NULL;
}

2.6總結

線性表是一種基礎且重要的數(shù)據(jù)結構,常見的線性表有三種實現(xiàn)方式:順序表、單鏈表和雙鏈表皇钞。

本文對這三種線性表的實現(xiàn)方式及特點做一個簡要總結:

一悼泌、順序表順序表是將邏輯順序上相鄰的數(shù)據(jù)元素存儲在物理位置上也相鄰的存儲單元中,通常使用數(shù)組來實現(xiàn)。- 特點:定位直接,通過下標操作即可快速訪問任一位置的節(jié)點;實現(xiàn)簡單夹界。

缺點:插入刪除需要移動大量元素,效率低;存儲空間固定,擴容不靈活馆里。

二、單鏈表單鏈表通過鏈式存儲結構實現(xiàn),每個節(jié)點除存儲數(shù)據(jù)外,還儲存下一個節(jié)點的地址信息可柿。

-特點:存儲靈活,可動態(tài)擴展,插入刪除簡單,效率高鸠踪。-

缺點:訪問任一節(jié)點需要從頭結點遍歷,無法直接定位

三琴儿、雙鏈表雙鏈表相比單鏈表,每個節(jié)點增加一個指向前驅節(jié)點的指針,實現(xiàn)雙向鏈表负间。-

特點:可雙向遍歷鏈表,操作更靈活淀歇。-

缺點:每個節(jié)點存儲空間略大于單鏈表娇掏。

**綜上,三種線性表各有特點,使用需根據(jù)具體場景需求選擇合適的數(shù)據(jù)結構蕴轨。順序表操作簡單,鏈表存儲靈活,雙鏈表可以雙向訪問限府。開發(fā)時需要權衡效率與實現(xiàn)難度,選擇最優(yōu)實現(xiàn)读拆。**

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布祠肥！