线性表(Linear List)

在使用数组是，你是都有插入一个数据，或者删改一个数据的烦恼？那么来试试线性表吧

拥有的功能

  • 初始化线性表：将一个线性表进行初始化，得到一个全新的线性表
  • 获取指定位置上的元素：直接获取线性表指定位置i上的元素
  • 获取元素的位置：获取某个元素在线性表上的位置i
  • 插入元素：在指定位置i上插入一个元素
  • 删除元素：删除指定位置i上的元素
  • 获取长度：返回线性表的长度

那么怎么实现这些功能呢？

我们一般有两种解决方式：

  1. 顺序存储实现（顺序表）
  2. 链式存储实现（链表）

顺序表

前面我们说到，既然数组无法实现这样的高级表结构，那么我就基于数组，对其进行强化，也就是说，我们存放数据还是使用数组，但是我们可以为其编写一些额外的操作来强化为线性表，像这样底层依然采用顺序存储实现的线性表，我们称为顺序表。

image-20220724150015044

可以先定义一个新的类或结构体类型，将一些需要用到的数据保存在一起，这里我们以int类型的线性表为例：

定义与初始化

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>

using namespace std;

const int MAX_SIZE = 100; // 最大容量

class SeqList {
private:
    int data[MAX_SIZE]; // 存储数据
    int length; // 当前长度
}

进行初始化操作：

1
2
3
4
5
6
public:
// 构造函数
    SeqList() 
    {
        length = 0;
    }

但是我们发现一个问题，这样的话我们的顺序表长度不就是固定为100的了吗？而前面我们线性表要求的是长度是动态增长的，那么这个时候怎么办呢？我们可以直接使用一个指针来指向底层数组的内存区域，当装不下的时候，我们可以创建一个新的更大的内存空间来存放数据，这样就可以实现扩容了，所以我们来修改一下：

1
2
3
4
5
6
7
class SeqList 
{
private:
    int* data; // 存储数据的指针
    int capacity; // 当前容量
    int length; // 当前长度
}

接着修改一下构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public:
    // 构造函数
    SeqList() 
    {
        capacity = 10;
        data = new int[capacity];//使用动态增长的话记得进行释放
        length = 0;
    }

    // 析构函数
    ~SeqList() 
    //释放空间
    {
        delete[] data;
    }

插入元素

考虑因素：

  1. 指定位置插入（后续内容要向后移动）
  2. 动态空间申请
  3. 判断插入位置是否合法（越界啊）（bool）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool insert(int index, int value) 
    {
        if (index < 0 || index > length) 
        {
            return false; // 超出范围
        }
    if (length == capacity) {
            // 重新分配更大的内存空间//直到内存不足才会停止扩容
            capacity *= 2;
            int *new_data = new int[capacity];
            for (int i = 0; i < length; i++) {
                new_data[i] = data[i];
            }
            delete[] data;
            data = new_data;
        }
        for (int i = length; i > index; i--)
        {
            data[i] = data[i - 1]; // 数据后移
        }
        data[index] = value; // 插入数据
        length++; // 长度加1
        return true;
    }

打印函数

1
2
3
4
5
6
7
8
9
10
11
12
13
void print() 
{
        cout << "顺序表: [";
        for (int i = 0; i < length; i++) 
        {
            cout << data[i];
            if (i != length - 1) 
            {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }

好，写到这里让我们来小小的测试一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() 
{
    SeqList list;

    list.insert(0, 123);
    list.print();
    list.insert(1, 456);
    list.print();
    list.insert(0, 789);
    list.print();

    return 0;

}

imgList01

删除元素

1
2
3
4
5
6
7
8
9
bool remove(int index) {
    if (index < 0 || index >= length) {
        return false; // 超出范围
    }
    for (int i = index; i < length - 1; i++) {
        data[i] = data[i + 1]; // 数据前移
    }
    length--; // 长度减1
    return true;

获取数据以及获取线性表长度

1
2
3
4
5
6
7
8
9
10
11
12
// 获取数据
int get(int index) const {
    if (index < 0 || index >= length) {
        return -1; // 超出范围
    }
    return data[index];
}

// 获取长度
int size() const {
    return length;
}

完整代码

好，那么有关线性表的实现就完成了，完整代码如下

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
#include <iostream>

using namespace std;

class SeqList {
private:
    int* data; // 存储数据的指针
    int capacity; // 当前容量
    int length; // 当前长度

public:
    // 构造函数
    SeqList() {
        capacity = 10;
        data = new int[capacity];
        length = 0;
    }

    // 析构函数
    ~SeqList() {
        delete[] data;
    }

    // 插入数据
    bool insert(int index, int value) 
    {
        if (index < 0 || index > length) 
        {
            return false; // 超出范围
        }
        if (length == capacity) {
            // 重新分配更大的内存空间
            capacity *= 2;
            int* new_data = new int[capacity];
            for (int i = 0; i < length; i++) {
                new_data[i] = data[i];
            }
            delete[] data;
            data = new_data;
        }
        for (int i = length; i > index; i--)
        {
            data[i] = data[i - 1]; // 数据后移
        }
        data[index] = value; // 插入数据
        length++; // 长度加1
        return true;
    }

    // 删除数据
    bool remove(int index) {
        if (index < 0 || index >= length) {
            return false; // 超出范围
        }
        for (int i = index; i < length - 1; i++) {
            data[i] = data[i + 1]; // 数据前移
        }
        length--; // 长度减1
        return true;
    }

    // 获取数据
    int get(int index) const {
        if (index < 0 || index >= length) {
            return -1; // 超出范围
        }
        return data[index];
    }

    // 获取长度
    int size() const {
        return length;
    }

    // 打印顺序表
    void print()
    {
        cout << "顺序表: [";
        for (int i = 0; i < length; i++) 
        {
            cout << data[i];
            if (i != length - 1) 
            {
                cout << ", ";
            }
        }
        cout << "]" << endl;
    }
};

int main() {
    SeqList list;

    list.insert(0, 123);
    list.print();
    list.insert(1, 456);
    list.print();
    list.insert(0, 789);
    list.print();
    for (int i = 0; i <= 100; i++)
    {
        list.insert(i, i);
    }
    list.print();
    return 0;

}

imgList02

一些问题

1.请问顺序实现的线性表，插入、删除、获取元素操作的时间复杂度为？

  • 插入：因为要将后续所有元素都向后移动，所以平均时间复杂度为O(N)
  • 删除：同上，因为要将所有元素向前移动，所以平均时间复杂度为O(N)
  • 获取元素：因为可以利用数组特性直接通过下标访问到对应元素，所以时间复杂度为O(1)

2.顺序表是一种（ ）的存储结构？

A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取

首先顺序表底层是基于数组实现的，那么它肯定是支持随机访问的，因为我们可以直接使用下标想访问哪一个就访问哪一个，所以选择A，不要看到名字叫做顺序表就选择顺序存取，因为它并不需要按照顺序来进行存取，链表才是。这里也没有建立索引去访问元素，也更不可能是散列存取了，散列存取我们会在后面的哈希表中进行介绍

链表

线性表的另外一种实现方式是链表，那么什么是链表呢？

链表不同于顺序表，顺序表底层采用数组作为存储容器，需要分配一块连续且完整的内存空间进行使用，而链表则不需要，它通过一个指针来连接各个分散的结点，形成了一个链状的结构，每个结点存放一个元素，以及一个指向下一个结点的指针，通过这样一个一个相连，最后形成了链表。它不需要申请连续的空间，只需要按照顺序连接即可，虽然物理上可能不相邻，但是在逻辑上依然是每个元素相邻存放的，这样的结构叫做链表（单链表）。

说人话，就是，申请时就是一堆散点，之后通过链状，连接到一起。而不需要像顺序表一样，申请一大块的连续空间。

链表还分为带头节点的链表和不带头结点的链表。一般设计链表都会采用带头结点的结构，因为操作更加方便。在写算法题的时候，会选择使用，不带头结点的链表。

PS:不带头节点的单链表对于第一个结点的操作与其他结点的操作不一样，需要特殊处理，这增加的程序的复杂性和出现bug的机会，因此带头节点会更方便

带头链表（单链表）

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
struct Node //使用结构体保证链表数据的封装性和安全性
{
	int data;
	Node* next;
};
class LinkedList
{
public:
	LinkedList()//链表初始化
	{
		head == NULL;
	}
private:
	Node* head;

};
int main()
{
	return 0;
}

打印列表

1
2
3
4
5
6
7
8
9
void printList() 
{
	ListNode* node = head->next;//头结点，是没有值的，因此从它的下一个节点开始输出
	while (node != NULL) {
		cout << node->data << " ";
		node = node->next;
	}
	cout << endl;
}

插入元素

我们可以先修改新插入的结点的后继结点（也就是下一个结点）指向，指向原本在这个位置的结点：

接着我们可以将前驱结点（也就是上一个结点）的后继结点指向修改为我们新插入的结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool insert(int data, int index)
	{
		if (index < 1) return false;//插入位置小于1，直接报错
		ListNode* node = head;//通过--index，从头节点依次向后进行寻找前驱节点
		while (--index)
		{
			node = node->next;//总是指向下一个结点
			if (node == NULL)//超出范围	
			{
				return false;
			}
		}
		ListNode* new_node = new ListNode;
		if (new_node == NULL) return false;
		new_node->data = data;
		new_node->next = node->next;
		node->next = new_node;
		return true;
	}

我们来简单测试一下

1
2
3
4
5
6
7
8
9
int main()
{
	LinkedList list;
	list.insert(1, 1);
	list.insert(2, 2);
	list.insert(3, 1);
	list.printList();
	return 0;
}

imgList03

删除元素

那么我们如何实现删除操作呢？实际上也会更简单一些，我们可以直接将待删除节点的前驱结点指向修改为待删除节点的下一个：

所以我们只需要释放掉待删除结点占用的内存空间就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool remove(int index)
	{
		if (index < 1) return false;//插入位置小于1，直接报错
		ListNode* node = head;//通过--index，从头节点依次向后进行寻找前驱节点
		while (--index)
		{
			node = node->next;//总是指向下一个结点
			if (node == NULL)//删除的位置超出范围	//?
			{
				return false;
			}
		}
		if (node->next == NULL) return false;//如果有5个数，但是想要删除第六个，就需要特殊考虑
		
		//删除元素
		ListNode* temp = node->next;
		node->next = node->next->next;//跨越到下一个的下一个，把删除的元素跳过去
		delete temp;
		return true;
	}

我们来测试一下

1
2
3
4
5
6
7
8
9
10
11
int main()
{
	LinkedList list;
	list.insert(1, 1);
	list.insert(2, 2);
	list.insert(3, 1);
	list.printList();
	list.remove(2);
	list.printList();
	return 0;
}

imgList04

获取对应位置上的元素

1
2
3
4
5
6
7
8
9
10
11
int* getlist(int index)//用指针的形式进行返回
	{
		ListNode* node = head;
		if (index < 1) return 0;
		do
		{
			head = head->next;
			if (head == NULL) return 0;
		} while (--index);
		return &head->data;
	}

再来测试一下

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
	LinkedList list;
	list.insert(1, 1);
	list.insert(2, 2);
	list.insert(3, 1);
	list.printList();
	list.remove(2);
	list.printList();
	cout << *list.getlist(2) << endl;
	return 0;
}

imgList05

获取元素的对应位置（不重复）

1
2
3
4
5
6
7
8
9
10
11
12
int findList(int data)
	{
		ListNode* node = head->next;//先走到第一个节点
		int i = 1;//计数器
		while (node != NULL)
		{
			if (node->data == data) return i;//如果找到，就返回i;
			i++;
			node = node->next;
		}
		return -1;
	}

获取列表长度

1
2
3
4
5
6
7
8
9
10
11
int size()
	{
		ListNode* node = head->next;
		int i = 0;
		while (node)
		{
			i++;
			node = node->next;
		}
		return i;
	}

最后再来测试一下

1
2
3
4
5
6
7
8
9
10
11
int main()
{
	LinkedList list;
	list.insert(1, 1);
	list.insert(2, 2);
	list.insert(3, 1);
	list.printList();
	cout << list.findList(2) << endl;
	cout<<list.size()<<endl;
	return 0;
}

imgList06

全部代码

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
#include <iostream>
using namespace std;
struct ListNode //使用结构体保证链表数据的封装性和安全性
{
	int data;
	ListNode* next;
};
class LinkedList
{
public:
	LinkedList()//链表初始化
	{
		head = new ListNode;
		head->next = NULL;
	}
	~LinkedList() //释放内存
	{
		ListNode* node = head;
		while (node != NULL) 
		{
			ListNode* temp = node;
			node = node->next;
			delete temp;
		}
	}
	bool insert(int data, int index)
	{
		if (index < 1) return false;//插入位置小于1，直接报错
		ListNode* node = head;//通过--index，从头节点依次向后进行寻找前驱节点
		while (--index)
		{
			node = node->next;//总是指向下一个结点
			if (node == NULL)//超出范围	
			{
				return false;
			}
		}
		ListNode* new_node = new ListNode;
		if (new_node == NULL) return false;
		new_node->data = data;
		new_node->next = node->next;
		node->next = new_node;
		return true;
	}
	bool remove(int index)
	{
		if (index < 1) return false;//插入位置小于1，直接报错
		ListNode* node = head;//通过--index，从头节点依次向后进行寻找前驱节点
		while (--index)
		{
			node = node->next;//总是指向下一个结点
			if (node == NULL)//删除的位置超出范围	//?
			{
				return false;
			}
		}
		if (node->next == NULL) return false;//如果有5个数，但是想要删除第六个，就需要特殊考虑
		
		//删除元素
		ListNode* temp = node->next;
		node->next = node->next->next;//跨越到下一个的下一个，把删除的元素跳过去
		delete temp;
		return true;
	}
	int* getlist(int index)//用指针的形式进行返回
	{
		ListNode* node = head;
		if (index < 1) return 0;
		do
		{
			node = node->next;
			if (node == NULL) return 0;
		} while (--index);
		return &node->data;
	}
	int findList(int data)
	{
		ListNode* node = head->next;//先走到第一个节点
		int i = 1;//计数器
		while (node != NULL)
		{
			if (node->data == data) return i;//如果找到，就返回i;
			i++;
			node = node->next;
		}
		return -1;
	}
	int size()
	{
		ListNode* node = head->next;
		int i = 0;
		while (node)
		{
			i++;
			node = node->next;
		}
		return i;
	}
	void printList() 
	{
		ListNode* node = head->next;//头结点，是没有值的，因此从它的下一个节点开始输出
		while (node != NULL) {
			cout << node->data << " ";
			node = node->next;
		}
		cout << endl;
	}
private:
	ListNode* head;

};
int main()
{
	LinkedList list;
	list.insert(1, 1);
	list.insert(2, 2);
	list.insert(3, 1);
	list.printList();
	cout << list.findList(2) << endl;
	cout<<list.size()<<endl;
	list.remove(2);
	list.printList();
	cout << *list.getlist(1) << endl;

	return 0;
}

一些问题

1.请问链式实现的线性表，插入、删除、获取元素操作的时间复杂度为？

  • 插入：因为要寻找对应位置的前驱结点，所以平均时间复杂度为O(n)，但是不需要做任何的移动操作，效率肯定是比顺序表要高的。
  • 删除：同上，所以平均时间复杂度为O(n)
  • 获取元素：由于必须要挨个向后寻找，才能找到对应的结点，所以时间复杂度为O(n)，不支持随机访问，只能顺序访问，比顺序表慢。

2.什么情况下使用顺序表，什么情况下使用链表呢？

  • 通过分析顺序表和链表的特性我们不难发现，链表在随机访问元素时，需要通过遍历来完成，而顺序表则利用数组的特性直接访问得到，所以，当我们读取数据多于插入或是删除数据的情况下时，使用顺序表会更好。
  • 而顺序表在插入元素时就显得有些鸡肋了，因为需要移动后续元素，整个移动操作会浪费时间，而链表则不需要，只需要修改结点 指向即可完成插入，所以在频繁出现插入或删除的情况下，使用链表会更好。

3.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行（ ）操作与链表的长度有关？

A．删除单链表中的第一个元素
B．删除单链表中的最后一个元素
C．在单链表第一个元素前插入一个新元素
D．在单链表最后一个元素后插入一个新元素

注意题干，现在有指向链表头尾的两个指针，那么A、C肯定是可以直接通过头结点找到的，无论链表长度如何都不影响，D也可以直接通过尾指针进行拼接，只有B需要尾指针的前驱结点，此时只能从头开始遍历得到，所以选择B

4.在一个单链表HL中（HL为头结点指针），若要向表头插入一个由指针p指向的结点，则执行？

A． HL＝p; p->next＝HL;
B． p->next＝HL; HL＝p;
C． p->next＝HL; p＝HL;
D． p->next＝HL->next; HL->next＝p;

既然要在表头插入一个数据，也就是说要在第一个位置插入，那么根据我们之前讲解的链表的插入，只需要将头结点指向新的结点，再让新的结点指向原本的第一个结点即可，所以选择D

5.链表不具备的特点是？

A．可随机访问任一结点 B．插入删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与其长度成正比

我们前面说了，链表由于是链式存储结构，无法直接访问到对应下标的元素，所以我们只能通过遍历去找到对应位置的元素，故选择A

双向链表

当我们学完单链表的时候会发现，我们想要操作某一个结点时，比如删除，插入等，都需要找到前驱节点，才能进行。

那么有没有一种方法可以让节点不仅保存指向后续节点的指针，也能保存前驱节点的指针呢？

答案是有，它就是双链表

定义与初始化

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
#include <iostream>
using namespace std;
class Node
{
	int data;
	Node* prev;
	Node* next;
	Node(int value)
	{
		data = value;
		prev = nullptr;//将指针都设定为空
		next = nullptr;
	}
};
class DoubleLinkedList
{
private:
	Node* head;
	Node* tail;
public:
	DoubleLinkedList()
	{
		head = nullptr;//将指针都设定为空
		tail = nullptr;
	}
};

添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool add(int value)
	{
		Node* newNode = new Node(value);

		if (head == nullptr) 
		{
			head = newNode;
			tail = newNode;
		}
		else 
		{
			tail->next = newNode;
			newNode->prev = tail;
			tail = newNode;
		}
	}

插入函数

接着是双向链表的插入操作，这就比单链表要麻烦一些了，我们先来分析一下：

首先我们需要考虑后继结点，当新的结点插入之后，新的结点的后继结点就是原本在此位置上的结点，所以我们可以先将待插入结点的后继指针指向此位置上的结点：

由于是双向链表，所以我们需要将原本在此位置上的结点的前驱指针指向新的结点：

接着我们来处理一下前驱结点，首先将前驱结点的后继指针修改为新的结点：

最后我们将新的结点的前驱指针指向前驱结点即可：

这样，我们就完成了双向链表中结点的插入操作，按照这个思路，我们来设计一下函数吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool insert(int value, int index)
{
	if (index <= 0) return false;
	if (head == nullptr) return false;
	Node* newNode = new Node(value);
	Node* current = head;
	int currentIndex = 1;
	while (current != nullptr && currentIndex < index)
	{
		current = current->next;
		currentIndex++;
	}
	if (current == nullptr) return false;
	newNode->prev = current->prev;
	newNode->next = current;
	current->prev->next = newNode;
	current->prev = newNode;
}

打印列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void printForward()//正向输出
{
	Node* current = head;
	while (current != nullptr)
	{
		cout << current->data << "->";
		current = current->next;
	}
	cout << endl;
}
void printReverse()//逆向输出
{
	Node* current = tail;
	while (current != nullptr)
	{
		cout << current->data << "<-";
		current = current->prev;
	}
	cout << endl;
}

删除元素

我们只需将前驱结点和后继结点的指向修改即可：

接着直接删除对应的结点即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool remove(int index)
{
	if (index < 1) return false;
	Node* current = head;
	int currentIndex = 1;
	while (current != nullptr && currentIndex < index)
	{
		current = current->next;
		currentIndex++;
	}
	if (current == nullptr) return false;
	if (current->next != nullptr)
	{
		current->next->prev = current->prev;
	}
	if (current->prev != nullptr)
	{
		current->prev->next = current->next;
	}
	delete current;
	return true;
}

好，基本的内容我们都已经实现了，那我们来测试一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
	DoubleLinkedList List;
	for (int i = 1; i <= 5; i++)
	{
		List.add(i);
	}
	List.printForward();
	List.printReverse();
	List.remove(3);
	List.printForward();
	return 0;
}

imgList07

全部代码

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
#include <iostream>
using namespace std;
class Node
{
public:
	int data;
	Node* prev;
	Node* next;
	Node(int value)
	{
		data = value;
		prev = nullptr;
		next = nullptr;
	}
};
class DoubleLinkedList
{
private:
	Node* head;
	Node* tail;
public:
	DoubleLinkedList()
	{
		head = nullptr;
		tail = nullptr;
	}
	void add(int value)
	{
		Node* newNode = new Node(value);

		if (head == nullptr) 
		{
			head = newNode;
			tail = newNode;
		}
		else 
		{
			tail->next = newNode;
			newNode->prev = tail;
			tail = newNode;
		}
	}
	bool insert(int value, int index)
	{
		if (index < 1) return false;
		if (head == nullptr) return false;
		Node* newNode = new Node(value);
		Node* current = head;
		int currentIndex = 1;
		while (current != nullptr && currentIndex < index)
		{
			current = current->next;
			currentIndex++;
		}
		if (current == nullptr) return false;
		newNode->prev = current->prev;
		newNode->next = current;
		current->prev->next = newNode;
		current->prev = newNode;
	}
	bool remove(int index)
	{
		if (index < 1) return false;
		Node* current = head;
		int currentIndex = 1;
		while (current != nullptr && currentIndex < index)
		{
			current = current->next;
			currentIndex++;
		}
		if (current == nullptr) return false;
		if (current->next != nullptr)
		{
			current->next->prev = current->prev;
		}
		if (current->prev != nullptr)
		{
			current->prev->next = current->next;
		}
		delete current;
		return true;
	}
	void printForward()
	{
		Node* current = head;
		while (current != nullptr)
		{
			cout << current->data << "->";
			current = current->next;
		}
		cout << endl;
	}
	void printReverse()
	{
		Node* current = tail;
		while (current != nullptr)
		{
			cout << current->data << "->";
			current = current->prev;
		}
		cout << endl;
	}
};
int main()
{
	DoubleLinkedList List;
	for (int i = 1; i <= 5; i++)
	{
		List.add(i);
	}
	List.printForward();
	List.printReverse();
	List.remove(3);
	List.printForward();
	return 0;
}

循环链表

循环链表，这种链表实际上和前面我们讲的链表是一样的，但是它的最后一个结点，是与头结点相连的，双向链表和单向链表都可以做成这样的环形结构，我们这里以单链表为例：

这种类型的链表实际上与普通链表的唯一区别就在于最后是否连接到头结点，因此循环链表支持从任意一个结点出发都可以到达任何的结点，而普通的链表则只能从头结点出发才能到达任意结点，同样也是为了更灵活而设计的。

练习题

  1. 与单链表相比，双链表的优点之一是？

    A．插入、删除操作更简单
    B．可以进行随机访问
    C．可以省略表头指针或表尾指针
    D．顺序访问相邻结点更灵活

    首先插入删除操作并没有更简单，反而更复杂了，随机访问肯定也是不行的，省略表头表尾指针实际上单链表也可以，所以D

  2. 非空的循环单链表head的尾结点（由p所指向）满足？

    A．p->next == NULL B．p == NULL
    C．p->next ==head D．p == head

    前面我们说了，循环链表实际上唯一区别就是尾部的下一个结点会指向头部，所以这里选择C

  3. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用什么存储方式最节省运算时间？

    A．单链表 B．给出表头指针的单循环链表 C．双链表 D．带头结点的双循环链表

    题干说明了常用的是在尾结点插入或删除尾结点，那么此时不仅需要快速找到最后一个结点，也需要快速找到最后一个结点的前驱结点，所以肯定是使用双向链表，为了快速找到尾结点，使用循环双向链表从头结点直接向前就能找到，所以选择D

  4. 如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用？

    A．只有表头指针没有表尾指针的循环单链表
    B．只有表尾指针没有表头指针的循环单链表
    C．非循环双链表
    D．循环双链表

    首先这里需要操作两个内容，一个是删除第一个元素，另一个是在最后插入新元素，所以A的话只有表头指针虽然循环但是还是得往后遍历才行，而B正好符合，因为循环链表的尾指针可以快速到达头结点，C不可能，D的话，循环双链表也可以，但是没有单链表节省空间，故B是最优解

特殊的线性表

栈(Stack)

基本介绍

栈是一种特殊的线性表，它只能在在表尾进行插入和删除操作，就像下面这样：

也就是说，我们只能在一端进行插入和删除，当我们依次插入1、2、3、4这四个元素后，连续进行四次删除操作，删除的顺序刚好相反：4、3、2、1，我们一般将其竖着看：

底部称为栈底，顶部称为栈顶，所有的操作只能在栈顶进行，也就是说，被压在下方的元素，只能等待其上方的元素出栈之后才能取出，就像我们往箱子里里面放的书一样，因为只有一个口取出里面的物品，所以被压在下面的书只能等上面的书被拿出来之后才能取出，这就是栈的思想，它是一种先进后出的数据结构（FILO，First In, Last Out）

实现栈也是非常简单的，可以基于我们前面的顺序表或是链表，这里我们先使用顺序表来实现一下，这里我们需要实现两个新的操作：

  • pop：出栈操作，从栈顶取出一个元素。
  • push：入栈操作，向栈中压入一个新的元素。

首先还是按照我们的顺序表进行编写：

定义与初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Stack
{
private:
	T* elements;
	int capacity;//栈的容量
	int topIndex;//当前占点元素下标
public:
	Stack(int size)//栈的初始化
	{
		capacity = size;
		elements = new T[capacity];
		topIndex = -1;//当前顶部指向-1，代表没有元素。
	}
	~Stack()
	{
		delete[] elements;
	}
};

入栈操作

1
2
3
4
5
6
7
8
void push(const T& item)//入栈操作
	{
		if (topIndex == capacity - 1)
		{
			throw out_of_range("满了满了，别塞了");
		}
		elements[++topIndex] = item;
	}

但是我想让他没有容量限制，那怎么办呢？很简单，加个扩容功能就好了。

扩容功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void push(const T& item)//入栈操作
	{
		if (topIndex == capacity - 1)
		{
			//throw out_of_range("满了满了，别塞了");
            expendCapacity();
		}
		elements[++topIndex] = item;
	}
void expendCapacity()//扩容操作
	{
		int newCapacity = capacity * 2;
		T* newElements = new T[newCapacity];
		for (int i = 0; i <= topIndex; i++)
		{
			newElements[i] = elements[i];
		}
		delete[] elements[i];
		elements = newElements;
		capacity = newCapacity;
	}

出栈操作

1
2
3
4
5
6
7
8
9
T pop()//因为出栈，只能从最上方删除，所以不用任何参数 
   {
	if (topIndex == -1) 
	{
		throw out_of_range("Stack is empty");//出栈之前，判断下顶层的位置在哪
	}

	return elements[topIndex--];//直接删除顶层数值即可
}

全部代码与测试

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
#include <iostream>
using namespace std;
template <class T>
class Stack
{
private:
	T* elements;
	int capacity;//栈的容量
	int topIndex;//当前占点元素下标
public:
	Stack(int size)//栈的初始化
	{
		capacity = size;
		elements = new T[capacity];
		topIndex = -1;//当前顶部指向-1，代表没有元素。
	}
	~Stack()
	{
		delete[] elements;
	}
	void push(const T& item)//入栈操作
	{
		if (topIndex == capacity - 1)
		{
			//throw out_of_range("满了满了，别塞了");
			cout << "阿巴阿巴，你别急，我扩容一下" << endl;
			expendCapacity();
		}
		elements[++topIndex] = item;
	}
	void expendCapacity()
	{
		int newCapacity = capacity * 2;
		T* newElements = new T[newCapacity];
		for (int i = 0; i <= topIndex; i++)
		{
			newElements[i] = elements[i];
		}
		delete[] elements;
		elements = newElements;
		capacity = newCapacity;
	}
	T pop() {
		if (topIndex == -1) 
		{
			throw out_of_range("Stack is empty");//出栈之前，判断下顶层的位置在哪
		}

		return elements[topIndex--];//直接删除顶层数值即可
	}
	void print()
	{
		if (topIndex == -1)
		{
			cout << "空的，啥也没有" << endl;
		}
		for (int i = 0; i <= topIndex; i++)
		{
			cout << elements[i] << "|";
		}
		cout << endl;
	}
};
int main()
{
	Stack<int> stack(4);
	stack.print();
	for (int i = 1; i <= 4; i++)
	{
		stack.push(i);
	}
	stack.print();
	stack.push(5);
	stack.print();
	cout << stack.pop() << endl;
	stack.print();
	return 0;
}

测试结果

imgList08

栈的利用率可能会很低，这个时候我们可以将一个固定长度的数组共享给两个栈来使用：

数组的两头分别作为两个栈的栈底，当两个栈的栈顶指针相遇时（栈顶指针下标之差绝对值为1时），表示栈已满。通过这种方式，我们就可以将数组占用的空间更充分地使用，这样的栈我们称为共享栈。

练习题

  1. 若进栈序列为1，2，3，4，则不可能得到的出栈序列是？

    A. 3，2，1，4 B. 3，2，4，1
    C. 4，2，3，1 D. 2，3，4，1

    注意进栈并不一定会一次性全部进栈，可能会出现边进边出的情况，所以出栈的顺序可能有很多种情况，首先来看A，第一个出栈的是3，那么按照顺序，说明前面一定入栈了2、1，在出栈时4还没有入栈，然后是2、1最后是4，没有问题。接着是B，跟前面的A一样，不过这次是先出站3、2，而1留在栈中，接着4入栈，然后再让4、1出栈，也是正确的。然后是C，首先是4出栈，那么说明前三个一定都入栈了，而此时却紧接着的一定是3，而这里是2，错误。所以选择C

  2. 假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么栈大小至少为？

    A.2
    B.3
    C.4
    D.5

    首先我们分析一下，第一个出栈的元素为3，那么也就是说前面的1、2都在栈内，所以大小至少为3，然后是5，那么说明此时栈内为1、2、4，算是出栈的5，那么至少需要的大小就是4了，所以选择C

队列(Queue)

基本介绍

前面我们学习了栈，栈中元素只能栈顶出入，它是一种特殊的线性表，同样的，队列（Queue）也是一种特殊的线性表。

就像我们在超市、食堂需要排队一样，我们总是排成一列，先到的人就排在前面，后来的人就排在后面，越前面的人越先完成任务，这就是队列，队列有队头和队尾：

秉承先来后到的原则，队列中的元素只能从队尾进入，只能从队首出去，也就是说，入队顺序为1、2、3、4，那么出队顺序也一定是1、2、3、4，所以队列是一种先进先出（FIFO，First In, First Out）的数据结构。

想要实现队列也是很简单的，也可以通过两种线性表来实现，我们先来看看使用顺序表如何实现队列，假设一开始的时候队列中有0个元素，队首和队尾一般都初始都是-1这个位置：

此时有新的元素入队了，队尾向后移动一格（+1），然后在所指向位置插入新的元素：

之后都是同样的方式进行插入，队尾会一直向后移动：

现在我们想要执行出队操作了，那么需要将队首向后移动一格，然后删除队首指向的元素：

看起来设计的还挺不错的，不过这样有一个问题，这个队列是一次性的，如果队列经过反复出队入队操作，那么最后指针会直接指向数组的最后，如果我们延长数组的话，也不是一个办法，不可能无限制的延伸下去吧？所以一般我们采用循环队列的形式，来实现重复使用一个数组（不过就没办法扩容了，大小是固定的）

我们可以在移动队首队尾指针时，考虑循环的问题，也就是说如果到达了数组尽头，那么就直接从数组的前面重新开始计算，这样就相当于逻辑上都循环了，队首和队尾指针在一开始的时候都指向同一个位置，每入队一个新的元素，依然是先让队尾后移一位，在所指向位置插入元素，出队同理。

不过这样还是有问题，既然是循环的，那么怎么判断队列是否已满呢？

由于队首指针和队尾指针重合时表示队列为空，所以我们只能舍弃一个存储单元，当队尾距离队首一个单元的时候，表示队列已满。

定义与初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
class Queue
{
private:
	int* array;
	int capacity;
	int rear, front;
public:
	Queue() :capacity(10), rear(0), front(0)
		//默认为 容量为10，队首与队尾在0起点
	{
		array = new int[capacity];
	}
	~Queue()
	{
		delete[] array;
	}
};

入队操作

1
2
3
4
5
6
7
8
bool offerQueue(int element) //先位移，再插入
{
	if ((rear + 1) % capacity == front)   // 先判断队列是否已满，如果队尾下一个就是队首，那么说明已满
		return false;
	rear = (rear + 1) % capacity;   // 队尾先向前移动一位，注意取余计算才能实现循环
	array[rear] = element;   // 在新的位置插入元素
	return true;
}

出队操作

1
2
3
4
5
6
7
8
9
bool isEmpty()//判断是否为空
{
	return rear == front;
}
int poolQueue()//出队操作
{
	front = (front + 1) % capacity;
	return array[front];
}

打印操作

1
2
3
4
5
6
7
8
9
10
void print() {
	cout << "<<< ";
	int i = front;   // 遍历队列需要从队首开始
	while (i != rear)
	{
		i = (i + 1) % capacity;   // 先向后循环移动
		cout << array[i] << " ";  // 然后打印当前位置上的元素
	}
	cout << "<<<" << endl;
}

全部代码并测试

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
#include <iostream>
using namespace std;
class Queue
{
private:
	int* array;
	int capacity;
	int rear, front;
public:
	Queue() :capacity(10), rear(0), front(0)
		//默认为 容量为10，队首与队尾在0起点
	{
		array = new int[capacity];
	}
	~Queue()
	{
		delete[] array;
	}
	bool offerQueue(int element) //先位移，再插入
	{
		if ((rear + 1) % capacity == front)   // 先判断队列是否已满，如果队尾下一个就是队首，那么说明已满
			return false;
		rear = (rear + 1) % capacity;   // 队尾先向前移动一位，注意取余计算才能实现循环
		array[rear] = element;   // 在新的位置插入元素
		return true;
	}
	bool isEmpty()//判断是否为空
	{
		return rear == front;
	}
	int poolQueue()//出队操作
	{
		front = (front + 1) % capacity;
		return array[front];
	}
	
	void print() {
		cout << "<<< ";
		int i = front;   // 遍历队列需要从队首开始
		while (i != rear)
		{
			i = (i + 1) % capacity;   // 先向后循环移动
			cout << array[i] << " ";  // 然后打印当前位置上的元素
		}
		cout << "<<<" << endl;
	}
};
int main()
{
	Queue queue;
	queue.print();
	for (int i = 0; i < 5; i++)
	{
		queue.offerQueue(i);
	}
	queue.print();
	while (!queue.isEmpty())
	{
		cout<<queue.poolQueue()<<" ";
	}
	cout << endl;
	return 0;
}

imgList09

链表实现队列

刚才使用顺序表来实现的队列，接下来试试链表来实现，好处是可以忽略容量的限制。

这里就直接展示全部代码了

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
#include <iostream>
using namespace std;
class LNode {
public:
    int element;
    LNode* next;
};
class LinkedQueue
{
private:
    LNode* front;
    LNode* rear;
public:
    LinkedQueue()
    {
        front = new LNode();
        rear = front;
    }
    ~LinkedQueue()
    {
        LNode* current = front;
        while (current != nullptr)
        {
            LNode* temp = current;
            current = current->next;
            delete temp;
        }
    }
    void offerQueue(int element) 
    {
        LNode* node = new LNode();
        node->element = element;
        node->next = nullptr;
        rear->next = node;
        rear = node;
    }
    bool isEmpty() 
    {
        return front == rear;
    }
    int pollQueue() 
    {
        int e = front->next->element;
        LNode* node = front->next;
        front->next = front->next->next;
        if (rear == node)
            rear = front;
        delete node;
        return e;
    }
    void printQueue() 
    {
        cout << "<<< ";
        LNode* node = front->next;
        while (node != nullptr) {
            cout << node->element << " ";
            node = node->next;
        }
        cout << "<<<" << endl;
    }
};
int main() {
    LinkedQueue queue;
    for (int i = 0; i < 5; ++i) {
        queue.offerQueue(i * 100);
    }
    queue.printQueue();
    while (!queue.isEmpty()) {
        cout << queue.pollQueue() << " ";
    }
    cout << endl;

    return 0;
}

imgList10

队列练习题：

  1. 使用链表方式存储的队列，在进行出队操作时需要？

    A. 仅修改头结点指向 B. 仅修改尾指针 C. 头结点指向、尾指针都要修改 D. 头结点指向、尾指针可能都要修改

    首先出队肯定是要动头结点指向的，但是不一定需要动尾指针，因为只有当尾指针指向的是待出队的元素时才需要，因为执行后队列就为空了，所以需要将队尾指针移回头结点处，选择D

  2. 引起循环队列队头位置发生变化的操作是？

    A. 出队

    B. 入队

    C. 获取队头元素

    D. 获取队尾元素

    这个题还是很简单的，因为只有出队操作才会使得队头位置后移，所以选择A