数据结构笔记--线性表

系列文章目录：

• 数据结构—导论
• 数据结构—算法基础
• 数据结构—线性表

线性表

线性表就是一种线性结构，它是由 $n$ 个具有相同类型的数据元素组成的有限序列。

线性表的特点：

• 有序性：线性表中的数据元素存在一对一的线性关系，即除了第一个元素外，每个元素都有唯一的前驱元素；除了最后一个元素外，每个元素都有唯一的后继元素。
• 有限性：线性表中包含的数据元素个数是有限的，即线性表的长度是有限的。

线性表可以采用顺序存储结构或链式存储结构来表示。

顺序表

顺序表是一种线性表的顺序存储结构，它使用一组连续的存储单元来存储线性表中的数据元素。

特点

• 顺序表中的数据元素在内存中是连续存储的，即每个元素都存储在相邻的存储单元中。
• 顺序表中的数据元素可以通过下标直接访问，即可以通过下标快速定位到指定的数据元素。

以上是一个顺序表的示意图。

我们要实现的顺序表应该具有功能：

1. 插入元素（增）
2. 删除元素（删）
3. 修改元素（改）
4. 查找元素（查）

实现代码

我自己写了一个顺序表，代码如下：

#include<iostream>
#include <windows.h>

using namespace std;

const int MAXSIZE = 10000;
typedef long long ElementType;

struct Seqlist
{
    ElementType list[MAXSIZE];
    long long length;

    Seqlist() { length = 0; }

    int Insert(long long i, ElementType x)
    {
        if (i < 0 || i > length)
        {
            cout << "插入位置不合法" << endl;
            return 0;
        }
        if (length >= MAXSIZE)
        {
            cout << "顺序表已满" << endl;
            return 0;
        }
        for (long long j = length; j > i; j--)
            list[j] = list[j - 1];
        list[i] = x;
        length++;
        return 1;
    }

    int Delete(long long i)
    {
        if (i < 0 || i >= length)
        {
            cout << "删除位置不合法" << endl;
            return 0;
        }
        for (long long j = i; j < length - 1; j++)
            list[j] = list[j + 1];
        length--;
        return 1;
    }

    long long Get(long long i)
    {
        if (i < 0 || i >= length)
        {
            cout << "查找位置不合法" << endl;
            return -1;
        }
        return list[i];
    }

    int Modify(long long i, ElementType x)
    {
        if (i < 0 || i >= length)
        {
            cout << "修改位置不合法" << endl;
            return 0;
        }
        list[i] = x;
        return 1;
    }

    bool isEmpty()
    {
        return length == 0;
    }

    void Reverse()
    {
        for (long long i = 0; i < length / 2; i++)
            swap(list[i], list[length - i - 1]);
    }

    Seqlist Find(ElementType x)
    {
        Seqlist indices;
        for (long long i = 0; i < length; i++)
            if (list[i] == x)
                indices.Push_back(i);
        return indices;
    }

    int Push_back(ElementType x) { return Insert(length, x); }
    int Pop_back() { return Delete(length - 1); }
    int Push_top(ElementType x) { return Insert(0, x); }
    int Pop_top() { return Delete(0); }
};

int main()
{
    SetConsoleOutputCP(CP_UTF8);
    Seqlist L;
    L.Push_back(1);
    L.Push_back(1);
    for(long long i=2; i<1213; i++) 
        L.Insert(i,L.Get(i-1)+L.Get(i-2));
    for(auto i=0; i<10; i++) cout << L.Get(i) << " ";
    cout << endl;
    Seqlist F = L.Find(1);
    for(int i=0; i<F.length; i++) cout << "值 " << i << " 对应的索引为" << F.Get(i) << " ";
    system("pause");
}

链表

相对于顺序表，链表的插入和删除操作更加高效，但是访问链表中的元素需要遍历整个链表。

链表是一种线性表的链式存储结构，它使用一组不连续的存储单元来存储线性表中的数据元素。

特点

• 链表中的数据元素不连续存储，而是通过指针链接在一起。
• 链表中的数据元素可以通过指针访问，但是不能通过下标直接访问。

为了表示每个数据元素 $a_i$ 与其后继数据元素 $a_{i+1}$ 之间的逻辑关系，对于数据元素 $a_i$ 来说，除了存储其本身的信息外，还需存储一个指向其后继数据元素的指针。这两部分组成数据元素 $a_i$ 的存储映像，称为结点（Node）。

节点包括两个部分：数据域和指针域。数据域用于存储数据元素的信息，指针域用于存储指向后继节点的指针。

n个节点通过指针链接成一个链表，这种链表称为单链表。此外，每个节点还包含一个指针域，用于指向前驱节点，这种链表称为双向链表。如果链表成环，则称为循环链表。

graph LR
    %% 核心结构
    HEAD((HEAD)) -->|next| Node1
    HEAD -.->|prev| NULL_HEAD[/NULL/]
    
    Node1 -->|prev| HEAD
    Node1 -->|data| DATA1[Data 1]
    Node1 -->|next| Node2
    
    Node2 -->|prev| Node1
    Node2 -->|data| DATA2[Data 2]
    Node2 -->|next| Node3
    
    Node3 -->|prev| Node2
    Node3 -->|data| DATA3[Data 3]
    Node3 -->|next| NULL_TAIL[/NULL/]

    %% 样式定义
    classDef head fill:#1e3a8a,stroke:#bde0fe,color:#fff;
    classDef node fill:#1e90ff,stroke:#bde0fe,color:#fff;
    classDef data fill:#32CD32,stroke:#fff,color:#000;
    classDef null fill:#555,stroke:#fff,color:#fff;
    classDef nextPointer stroke:#FFA500,stroke-width:2px;
    classDef prevPointer stroke:#00FF00,stroke-width:2px,dashed;

    class HEAD head
    class Node1,Node2,Node3 node
    class DATA1,DATA2,DATA3 data
    class NULL_HEAD,NULL_TAIL null
    
    %% 箭头样式
    linkStyle 0,3,6,9 stroke:#FFA500,stroke-width:2px
    linkStyle 1,4,7,10 stroke:#00FF00,stroke-width:2px,dashed

以上就是双向链表的图示。

• 🔵 蓝色圆角矩形：头节点HEAD
• 🔷 蓝色矩形：普通节点
• 🟩 绿色区块：数据域
• ⬛ 灰色菱形：NULL标识

实现代码

这里我先写一个单向链表，代码如下：

#include<iostream>
#include <windows.h>

using namespace std;

const int MAXSIZE = 10000;
typedef long long ElementType;

struct Nodelist
{
    ElementType data;
    struct Nodelist* next;
};

Nodelist* init()
{
    Nodelist* head = new Nodelist;
    head->next = NULL;
    return head;
}

void insertHead(Nodelist* Head, ElementType data)
{
    Nodelist* p = new Nodelist;
    p->data = data;
    //先把p的next指向L的next，再把L的next指向p
    p->next = Head->next;
    Head->next = p;
}

void insertTail(Nodelist* Tail, ElementType data)
{
    Nodelist* p = new Nodelist;
    p->data = data;
    //先把p的next指向NULL
    p->next = NULL;
    //找到链表的最后一个节点
    Nodelist* q = Tail;
    while (q->next != NULL)
        q = q->next;
    //把q的next指向p
    q->next = p;
}

void insertNode(Nodelist* Node, ElementType data, int i)
{
    //这里插入下标从0开始
    if(Node==NULL) {cout << "链表为空" << endl; return; }
    Nodelist* p = new Nodelist;
    Nodelist* q = Node;
    for(int j=0; j<i; j++)
    {

        if(q->next == NULL)
        {
            cout << "插入位置错误" << endl;
            return;
        }
        q = q->next;
    }
    p->data = data;
    p->next = q->next;
    q->next = p;
}

void deleteNode(Nodelist* Node, int i)
{
    Nodelist* p = Node;
    for(int j=0; j<i; j++)
    {
        if(p->next == NULL)
        {
            cout << "删除位置错误" << endl;
            return;
        }
        p = p->next;
    }
    if(p->next == NULL) {cout << "删除位置错误" << endl; return; }
    Nodelist* q = p->next;    // 保存要删除的节点(一定要先保存)
    p->next = p->next->next;  // 连接下下个节点
    delete(q);                // 删除节点
}


int main()
{
    SetConsoleOutputCP(CP_UTF8);
    Nodelist* L = init();
    for(int i=1; i<=5; i++) insertHead(L, i);
    for(int i=1; i<=5; i++) insertTail(L, i);
    // while(L->next != NULL)
    // {
    //     cout << L->next->data << " ";
    //     L = L->next;
    // }
    //注意此方法直接修改L的地址，遍历完后L指向NULL（）最后一个节点
    //正确的遍历方法应该是先创建一个temp指针指向L，再遍历temp
    Nodelist* temp = L;
    while(temp->next != NULL)
    {
        cout << temp->next->data << " ";
        temp = temp->next;
    }
    cout << endl << "-----------------" << endl;
    insertNode(L, 100, 5);
    cout << "在下标5处插入100" << endl;
    temp = L;
    while(temp->next != NULL)
    {
        cout << temp->next->data << " ";
        temp = temp->next;
    }
    cout << endl << "-----------------" << endl;
    deleteNode(L, 5);
    cout << "删除下标5处的节点" << endl;
    temp = L;
    while(temp->next != NULL)
    {
        cout << temp->next->data << " ";
        temp = temp->next;
    }
    system("pause");
}