线性表

本文最后更新于 2024年9月15日 晚上

总结

线性表总结

线性表的定义和基本操作

线性表的定义

    线性表是具有==相同数据类型==的 n (n>=0) 个数据元素的有限序列（数据之间具有前后驱关系），其中 n 为表长，当 n = 0 时线性表是一个空表。若用 L 命名线性表，则其一般表示为

L = (a₁, a₂, ⋯, aᵢ, aᵢ₊₁, ⋯, aₙ)

    式中，a₁ 是唯一的“第一个”数据元素，又称表头元素；aₙ 是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

特点：

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

线性表基本操作

  1. 初始化表。构造一个空的线性表。
  2. 求表长。返回线性表工的长度，即1中数据元素的个数。
  3. 按值查找操作。在表工中查找具有给定关键字值的元素。
  4. 按位査找操作。获取表工中第i个位置的元素的值。
  5. 插入操作。在表工中的第i个位置上插入指定元素 e。
  6. 删除操作。删除表,中第i个位置的元素,并用e返回删除元素的值。
  7. 输出操作。按前后顺序输出线性表工的所有元素值。
  8. 判空操作。若为空表，则返回true，否则返回 false。
  9. 销毁操作。销毁线性表，并释放线性表工所占用的内存空间。

代码实现功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>

class LinearList {
private:
    std::vector<int> list;

public:
    // 1. 初始化表。构造一个空的线性表。
    LinearList() {}

    // 2. 求表长。返回线性表的长度，即数据元素的个数。
    int length() const {
        return list.size();
    }

    // 3. 按值查找操作。在表中查找具有给定关键字值的元素。
    int findByValue(int value) const {
        for (int i = 0; i < list.size(); ++i) {
            if (list[i] == value) {
                return i;
            }
        }
        return -1; // 未找到返回 -1
    }

    // 4. 按位查找操作。获取表中第 i 个位置的元素的值。
    int findByIndex(int index) const {
        if (index < 0 || index >= list.size()) {
            throw std::out_of_range("Index out of range");
        }
        return list[index];
    }

    // 5. 插入操作。在表中的第 i 个位置上插入指定元素 e。
    void insert(int index, int value) {
        if (index < 0 || index > list.size()) {
            throw std::out_of_range("Index out of range");
        }
        list.insert(list.begin() + index, value);
    }

    // 6. 删除操作。删除表中第 i 个位置的元素，并返回删除元素的值。
    int remove(int index) {
        if (index < 0 || index >= list.size()) {
            throw std::out_of_range("Index out of range");
        }
        int value = list[index];
        list.erase(list.begin() + index);
        return value;
    }

    // 7. 输出操作。按前后顺序输出线性表的所有元素值。
    void print() const {
        for (int value : list) {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }

    // 8. 判空操作。若为空表，则返回 true，否则返回 false。
    bool isEmpty() const {
        return list.empty();
    }

    // 9. 销毁操作。销毁线性表，并释放线性表所占用的内存空间。
    void clear() {
        list.clear();
    }
};

int main() {
    LinearList list;

    // 初始化表
    std::cout << "初始化表" << std::endl;

    // 插入操作
    list.insert(0, 10);
    list.insert(1, 20);
    list.insert(2, 30);
    list.insert(1, 15);

    // 输出操作
    std::cout << "表的内容: ";
    list.print();

    // 求表长
    std::cout << "表长: " << list.length() << std::endl;

    // 按值查找操作
    int index = list.findByValue(20);
    std::cout << "值 20 的索引: " << index << std::endl;

    // 按位查找操作
    int value = list.findByIndex(2);
    std::cout << "索引 2 的值: " << value << std::endl;

    // 删除操作
    int removedValue = list.remove(1);
    std::cout << "删除的值: " << removedValue << std::endl;

    // 输出操作
    std::cout << "表的内容: ";
    list.print();

    // 判空操作
    std::cout << "表是否为空: " << (list.isEmpty() ? "是" : "否") << std::endl;

    // 销毁操作
    list.clear();
    std::cout << "表已销毁" << std::endl;

    // 判空操作
    std::cout << "表是否为空: " << (list.isEmpty() ? "是" : "否") << std::endl;

    return 0;
}

线性表的顺序表示

顺序表的定义

    线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置,第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素q在顺序表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。
    每个数据元素的存储位置都和顺序表的起始位置相差一个和该数据元素的位序成正比的常数，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

内存分配

    一维数组可以是静态分配的，也可以是动态分配的。对数组进行静态分配时，因为数组的大小和空间事先已经固定，所以一旦空间占满，再加入新数据就会产生溢出，进而导致程序崩溃。
    而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的，而不需要为线性表一次性地划分所有空间。

顺序表的优点：

  1. 可进行随机访问,即可通过首地址和元素序号可以在 O(1)时间内找到指定的元素:

  2. 存储密度高，每个结点只存储数据元素。
    顺序表的缺点：

  3. 元素的插入和删除需要移动大量的元素，插入操作平均需要移动 n/2 个元素，删除操作平均需要移动(n-1)/2个元素;

  4. 顺序存储分配需要一段连续的存储空间，不够灵活。

顺序表代码实现

静态分配的顺序表储存结构实现

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
    DataType data[MAXSIZE];
    int last;
} Seqlist;

void initseqlist(Seqlist *L)
{
    L->last = 0;
}

动态分配的顺序表储存结构实现

1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
    DataType *data;//指示动态分配数组的指针
    int last,size;
} Seqlist;

void initseqlist(Seqlist *L)
{
    L->data = new DataType[MAXSIZE];
    L->last = 0;
}

库文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <iostream>
using namespace std;
#define MAXSIZE 100
typedef int DataType;
typedef struct
{
    DataType *data;//指示动态分配数组的指针
    int last,size;
} Seqlist;

void initseqlist(Seqlist *L)
{
    L->data = new DataType[MAXSIZE];
    L->last = 0;
}

void input(Seqlist *L)
{
    DataType x;
    initseqlist(L);
    cout << "请输入顺序表中的元素，以0结束" << endl;
    cin >> x;
    while (x)
    {
        L->data[L->last++] = x;
        cin >> x;
    }
}

bool insert(Seqlist *L)
{
    int pos;
    DataType x;
    cout << "请输入插入位置和插入元素：" << endl;
    cin >> pos >> x;
    if (pos < 0 || pos > L->last)
    {
        cout << "插入位置不合法" << endl;
        return false;
    }

    if (L->last >= MAXSIZE)
    {
        cout << "顺序表已满，无法插入" << endl;
        return false;
    }

    for (int i = L->last; i >= pos; i--)
    {
        L->data[i] = L->data[i - 1];
    }

    L->data[pos - 1] = x;

    L->last++;

    return true;
}

bool deletel(Seqlist *L)
{
    int pos;
    DataType x;
    cout << "请输入删除数据的位置：" << endl;
    cin >> pos;
    if (pos < 0 || pos > L->last)
    {
        cout << "删除位置不合法" << endl;
        return false;
    }

    if (L->last <= 0)
    {
        cout << "顺序表为空，无法删除" << endl;
        return false;
    }

    for (int i = pos - 1; i <= L->last - 1; i++)
    {
        L->data[i] = L->data[i + 1];
    }

    L->last--;

    return true;
}

bool lookfor(Seqlist *L)
{
    int pos;
    DataType x;
    cout << "1. 查找元素第一次出现的位置" << endl;
    cout << "2. 查找某一位置上的元素" << endl;
    cout << "请输入你的选择：" << endl;
    int choice;
    cin >> choice;
    if (choice)
        if (choice == 1)
        {
            cout << "请输入想要查询的元素" << endl;
            cin >> x;
            for (int i = 0; i < L->last; i++)
            {
                if (L->data[i] == x)
                {
                    cout << "元素" << x << "第一次出现的位置是：" << i + 1 << endl;
                    return true;
                }
            }
            cout << "元素" << x << "不存在" << endl;
            return false;
        }
        else if (choice == 2)
        {
            cout << "请输入想要查询的位置" << endl;
            cin >> pos;
            if (pos < 0 || pos > L->last)
            {
                cout << "查询位置不合法" << endl;
                return false;
            }
            cout << "位置" << pos << "上的元素是：" << L->data[pos - 1] << endl;
            return true;
        }
    return true;
}

void sprit(Seqlist *L1, Seqlist *L2, Seqlist *L3)
{
    initseqlist(L2);
    initseqlist(L3);

    for (int i = 0; i < L1->last; i++)
    {
        if (L1->data[i] % 2 == 1)
        {
            L2->data[L2->last++] = L1->data[i];
        }
        else
        {
            L3->data[L3->last++] = L1->data[i];
        }
    }
}

void print(Seqlist *L)
{
    int i;
    if (L->last == 0)
        cout << "顺序表为空" << endl;
    else
        for (i = 0; i < L->last; i++)
        {
            cout << L->data[i] << " ";
            if ((i + 1) % 10 == 0)
                cout << endl;
        }
    cout << endl;
}

void inputfromfile(Seqlist *L, char *f)
{
    initseqlist(L);
    FILE *fp = fopen(f, "r");
    if (fp)
    {
        while (!feof(fp))
        {
            fscanf(fp, "%d", &L->data[L->last++]);
        }
        fclose(fp);
    }
}

测试函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include "seqlist.h"

int main()
{
    Seqlist L1, L2, L3;
    input(&L1);
    print(&L1);
    if (insert(&L1))
    {
        cout<<"插入成功"<<endl;
    }
    else{
        cout<<"插入失败"<<endl;
    }
    print(&L1);
    if (deletel(&L1))
    {
        cout<<"删除成功"<<endl;
    }
    else{
        cout<<"删除失败"<<endl;
    }
    print(&L1);
    if (lookfor(&L1))
    {
        cout<<"查找成功"<<endl;
    }
    else{
        cout<<"查找失败"<<endl;
    }
    sprit(&L1, &L2, &L3);
    cout << "原序列为：" << endl;
    print(&L1);
    cout << "奇数序列为：" << endl;
    print(&L2);
    cout << "偶数序列为：" << endl;
    print(&L3);
    return 0;
}

线性表的链式表示

单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息之外，还需要存放一个指向其后继的指针。

data next
数据域 指针域

    通常用头指针$head$来标识一个单链表，指出链表的起始地址，头指针为NULL是表示一个空表。
    头结点，在单链表第一个数据结点之前附加的一个结点，可不设任何信息，也可记录表长，带头结点时，头指针指向头结点；不带头结点时，头指针指向第一个数据结点。尾结点的指针域为NULL（用^表示）

单向链表结构

为什么要引入头结点：

  1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理;
  2. 无论链表是否为空,其头指针都是指向头结点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就得到了统一。

单向链表基本操作实现

双链表

    双链表结点中有两个指针 prior和next，分别指向其直接前驱和直接后继，如图2.9所示。表头结点的prior域和尾结点的next域都是 NULL。

双链表示意图

  1. 插入
  2. 删除

循环链表

单向循环链表：

    循环单链表和单链表的区别在于，表中最后一个结点的指针不是 NULL，而改为指向头结点,从而整个链表形成一个环。
    在循环单链表中，表尾结点*r的 next 域指向工,故表中没有指针域为 NULL 的结点,因此,循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针上。

循环单链表示意图

循环双链表：

    由循环单链表的定义不难推出循环双链表。不同的是，在循环双链表中，头结点的prior指针还要指向表尾结点，当某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其头结点的prior 域和next域都等于$L$。

循环双链表示意图

静态链表

    静态链表是用数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next,与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对地址(数组下标)，又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。

顺序表和链表比较

  1. 顺序表可以顺序存取，也可以随机存取，链表只能从表头开始依次顺序存取。例如在第i个位置上执行存取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次。
  2. 采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
  3. 对于按值查找，顺序表无序时，两者的时间复杂度均为 0(n);顺表有序时，可采用折半查找,此时的时间复杂度为 O(logn)。对于按序号査找,顺序表支持随机访问,时间复杂度仅为 O(1),而链表的平均时间复杂度为 O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。
  4. 顺序存储在静态存储分配情形下容易出现溢出和浪费的情况，动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败;链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效，但由于链表的每个结点都带有指针域，因此存储密度不够大。
note > 408 > 数据结构与算法
#数据结构
线性表
http://2819461143wp.github.io/线性表/
作者
cwdp.sky
发布于
2024年9月11日
许可协议