线性表List

线性表分类

定义

​ List：零个或多个数据元素的有限序列。

​ 线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

线性表定义

​ 在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件

顺序表

基本概念

  • 概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。

  • 特点：逻辑上相邻的数据元素，物理次序也是相邻的。

​ 只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。

代码实现

  • 头文件、链表结构体声明

1
2
3
4
5
6
7
8
9
10
#include<String>
#include<iostream>
using namespace std; //一定要有这个，否则用不了cout
typedef int elemtype;

typedef struct{
	elemtype* elem;
	int size;
	int length;
}sqList;

  • 需要实现的函数列表（增删查改）

1
2
3
4
5
6
7
8
9
10
bool InitList(sqList& L, int size);//初始化顺序表
int get_ListLength(const sqList &L);//获取表长度
int Locate(const sqList &L ,const elemtype &e);//按值查找
bool Getdata(const sqList& L, int i, elemtype &e);//获取第i个数据
bool InsList(sqList& L, int i,const elemtype e );//在第i个元素前插入一个元素
bool DelList(sqList& L, int i, elemtype& e);//删除第i个元素
void DestroyList(sqList& L);//销毁顺序表
void ClearList(sqList& L);//清空顺序表
bool emptyList(const sqList& L);//判断顺序表是否为空
void display(const sqList& L);//遍历顺序表，并输出

  • 函数具体细节

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
bool InitList(sqList& L, int size){	//初始化顺序表
	if (size <= 0) size = 10;
	L.elem = new elemtype[size];
	if (L.length == NULL) return false;
	L.size = size;
	L.length = 0;
	return true;
}

int get_ListLength(const sqList& L) {//获取表长度
	if (L.length == NULL){
		return false;
	}
	else {
		return L.length;
	}
}

int Locate(const sqList& L, const elemtype& e) {//按值查找
	for (int i = 0; i <= L.length -1; i++){
		if (L.elem[i] == e){
			return i + 1;
		}
	}
	return -1;
}

bool Getdata(const sqList& L, int i,  elemtype& e) {//获取第i个数据
	if (i>=1 && i<L.length){
		e = L.elem[i - 1];
		return true;
	}
	return false;
}

bool InsList(sqList& L, int i, const elemtype e) {//在第i个元素前插入一个元素

	if (i<1 || i>L.length + 1) return false;
	if (L.size == L.length){
		elemtype *temp = new elemtype[2 * L.size];
		if (temp == NULL) return false;
		for (int b = 0; b < L.length; b++){
			temp[b] = L.elem[b];
		}
		delete[] L.elem;
		L.elem = temp;
		L.size = L.size * 2;
	}
	for ( int a = L.length -1; a >=i-1 ; a--){
		L.elem[a + 1] = L.elem[a];
	}
	L.elem[i-1] = e;
	L.length++;
	return true;
}

bool DelList(sqList& L, int i, elemtype& e) {//删除第i个元素
	int a;
	e = L.elem[i - 1];
	if (i<1 || i>L.length) return false;

	for (a = i-1; a < L.length -1; a++) {
		L.elem[a] = L.elem[a+1];
	}
	L.length--;
	return true;
}

void DestroyList(sqList& L) {//销毁顺序表
	delete[] L.elem;
	L.elem = NULL;
	L.length = 0;
	L.size = 0;
}

void ClearList(sqList& L) {//清空顺序表
	L.length = 0;
}

bool emptyList(const sqList& L) {//判断顺序表是否为空
	if (L.length == 0){
		return true;
	}
	else{
		return false;
	}
}

void display(const sqList& L) {//遍历顺序表，并输出
	for (int i = 0; i <= L.length -1; i++){
		cout << L.elem[i]<<" ";
	}
}

​ 其中，InsList函数实现链表动态大小。若存入的数据的位置大于链表的size，则自动扩容2倍。

  • 主函数

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
int main(){
	sqList L;
	int x;
	InitList(L,2);
	cout << "顺序表初始长度是：" << get_ListLength(L) << endl;
	for (int i = 1; i <= 5; i++)
	{
		InsList(L, i, i + 1);
	}
	cout << "顺序表长度是：" << get_ListLength(L) << endl;
	cout << "顺序表大小是：" << L.size << endl;
	display(L);
	cout << endl;
	bool re = DelList(L, 2,x);
	if (re == true) {
		display(L);
		cout << "删除的元素是：" << x;
	}
	else{
		cout << "false";
	}
	Getdata(L,3,x);
	cout << endl;
	cout << "find的元素是：" << x << endl;
	int y = Locate(L,6);
	cout << "locate的元素是：" << y << endl;
}

  • 运行结果

顺序链表实验截图

顺序表优缺点

优点

  1. 支持随机访问，可以通过下标来直接访问。
  2. 可以排序。

缺点

  1. 中间/头部的插入删除，时间复杂度为O(N)
  2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。

链表

链表定义

​ 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表定义

​ 图中：2.3.4.5都是结构体，称之为结点Node，与顺序表不同的是，链表中的每个结点不是只单纯的存一个数据。而是一个结构体，结构体成员包括一个所存的数据，和下一个结点的地址。另外，顺序表中的地址是连续的，而链表中结点的地址是随机分配的。

​ 图中的phead指针中存放的是第一个结点的地址，那么根据指着地址我们就可以找到这个结构体，又因为这个结构体中存放了下一个结构体的地址，所以又可以找到第二个结构体，循环往复就可以找到所有的结点，直到存放空地址的结构体。因此结点由数据域和指针域构成。

notes：图中的箭头实际上是不存在的，这里只是为了能够方便理解。

注意：

  1. 从图中可以看出，链式结构在逻辑上是连续的，但在物理上不一定连续。
  2. 现实中的结点一般都是从堆上申请出来的。
  3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

链表分类

1. 单向或者双向

有head头指针，链表结尾指向NULL（尾结点）

链表单向或双向

2.带头或不带头

链表带头或不带头

3.循环或非循环

有head头指针，链表结尾指向第一个node的地址（尾结点）

循环或非循环

常用链表

常见链表

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

单向链表代码实现

​ 代码实现单向链表的创建、删除、查找。增加、修改操作与删除操作大同小异。

头文件

1
2
3
4
5
6
7
8
#include<String>
#include<iostream>

using namespace std;
typedef struct Node{
	int data;//数据域
	Node* next;//结构体指针
}Node;

实现函数列表

1
2
3
4
Node* creatnode(int n); //创建链表
int display(Node * head,int x);//遍历打印链表,查找元素个数
Node* findnode(Node *head,int x);//查找指针位置
bool delnode(Node* head , int n);//删除第n个结点

函数具体细节

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
Node* creatnode(int n) {//创建链表
	Node* s = NULL; // 指向结点
	Node* head = NULL;
	Node* tail = NULL;
	int x;
	for (int i = 0; i < n; i++){
		s = new Node;	//记得要申请内存，若不用内存要及时删除
		if (s ==NULL){
			return head;
		}
		else{
		cin >> x;
		s->data = x;
		s->next = s;
		if (i==0){
			head = s;
			tail = s;
		}
		else{
			tail->next = s;
			tail = s;
		}
		}
	}
	if (tail != NULL){
		tail->next = NULL;
	}
	return head;
}

int display(Node* head, int x) {//遍历打印链表,查找元素个数
	int count = 0;
	Node* p;
	p = head;
	while (p != NULL){
		cout << p->data << " ";
		if (x == p->data) {
			count++;
		}
		p = p->next;
	}
	return x;
}

Node* findnode(Node* head, int x) {//查找指针位置
	Node* p = head;
	while (p != NULL){
		if (x == p->data){
			return p;
		}
		p = p->next;
	}
	return NULL;
}

bool delnode(Node* head , int n) {//删除第n个结点
	Node* p = head;
	Node* before = NULL;
	for (int i = 0; i <= n-2; i++){//n-1是要删除的结点，n-2的时候就指向该结点了
		if (p == NULL){
			return false;
		}
		p = p->next;
		if (i==n-3){
			before = p;
		}
	}
	Node* temp = p->next;
	if (before != NULL)	{
		before->next = temp;
	}
	delete[] p;
	return true;
}

链表遍历图例

链表遍历

链表创建图例

链表创建过程解释图

视频讲解

bilibili

测试主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
int main() {
	int n;
	cin >> n;
	Node *head = creatnode(n);
	int x = display(head,2);
	Node* find = findnode(head , 3);
	cout << endl << "查找2的个数有：" << x << endl;
	cout << "元素3所在的位置是：" << find << endl;
	delnode(head, 3);
	cout << "删除第三个元素后：" << endl;
	display(head, 2);
	return 0;
}

实验结果

1

顺序表和链表区别

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续
随机访问 支持O(1） 不支持：O(N)
任意位置插入或者删除元素 可能需要搬移元素，效率低O(N) 只需修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率 高 低

参考：

嵌入式常见的数据结构_嵌入式数据结构-CSDN博客

数据结构：栈和队列(Stack & Queue)【详解】-CSDN博客

【数据结构】链表(单链表实现+详解+原码)-CSDN博客

数据结构–链表入门超详细解析(简单易懂纯原篇)_链表教学-CSDN博客

数据结构–链表入门超详细解析(简单易懂纯原篇)_链表教学-CSDN博客