2. 【数据结构】顺序表专题

一、课前准备

1. 目标

• C语言语法基础到数据结构与算法，前面已经掌握并具备了扎实的C语言基础，为什么要学习数据结构课程？⸺ 通讯录项目

2. 需要的储备知识

• 简单了解，通讯录具备增加、删除、修改、查找联系⼈等操作。要想实现通讯录项目有两个技术关键:
• C语言语法基础
• 数据结构之顺序表/链表

3. 数据结构相关概念

• 什么是数据结构？

数据结构是由“数据”和“结构”两词组合而来。

• 什么是数据？
  常见的数值1、2、3、4…、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页肉眼可以看到的信息（文字、图片、视频等等），这些都是数据.

• 什么是结构？
  当我们想要使用大量使用同一类型的数据时，通过手动定义大量的独立的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将大量的数据组织在一起，结构也可以理解为组织数据的方式。
  想要找到草原上名叫“咩咩”的羊很难，但是从羊圈里找到1号羊就很简单，羊圈这样的结构有效将羊群组织起来。

• 概念：数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

总结：

1）能够存储数据（如顺序表、链表等结构）
2）存储的数据能够⽅便查找

---

• 通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的方式任意对数据进行增删改查等操作。

最基础的数据结构：数组

【思考】有了数组，为什么还要学习其他的数据结构？
假定数组有10个空间，已经使用了5个，向数组中插⼊数据步骤：

• 求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这里是否要判断数组是否满了，满了还能继续插⼊吗）…
  假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。

结论：最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现

二、开始顺序表

1. 顺序表的概念及结构

线性表的概念：

• 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
• 案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合如何理解逻辑结构和物理结构？

2. 顺序表分类

• 顺序表和数组的区别

  • 顺序表的底层结构是数组,所以顺序表在逻辑结构上是线性的,在物理结构上也是线性的
  • 数组分为定长数组和动态数组

• 顺序表分类

  • 静态顺序表
  • 动态顺序表

• 概念:使用定长数组存储元素

• 静态顺序表

• 静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

• 动态顺序表

3. 动态顺序表的实现

在我们实现顺序表的时候，首先定义出结构体，还有数据类型的定义

头文件：SeqList.h

• 其中size是记录多少个有效数据，为什么要定义这个capacity呢？因为是动态的顺序表，今天100的空间，明天200的空间，所以就是capacity空间有多大，空间容量~~

• 我们可以看到我们当前的顺序表只能存储的是整形的数据，假如我把顺序表实现好了，我给其他人使用的时候，那我这里是整形，那能不能是char类型，double型…，我这里为什么一定要定义int类型？

• 那么我们这里就要使用typedef来定义类型~~

• 那我们也给这个结构体也重命名一个名字~~

#pragma once
//头文件
#include<stdio.h>

//数据类型的定义
typedef int SLDataType;

//结构体的定义
typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
}SL;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

初始化顺序表

函数的声明:SeqList.h

//初始化顺序表
void SLInit(SL s);
1
2

函数的实现:SeqList.c

//初始化顺序表
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
1
2
3
4
5
6
7

• 这里需要指针来初始化~~
• 可以看到已经初始化成功了~~

有初始化顺序表就有销毁顺序表，接下来我们就来看看销毁顺序表是怎么完成的~~

顺序表的销毁

函数的声明:SeqList.h

//销毁顺序表
void SLDestroy(SL* ps);
1
2

函数的实现:SeqList.c

• 我们首先要判断这个顺序表为有没有开辟空间，如果没有开辟空间就不需要释放，开辟了再free
• 将顺序表连续的空间的首地址指向空，有效数据个数和容量均置为0。
• 这里的ps有没有可能传过来的是NULL所以我们就需要断言~~

void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
1
2
3
4
5
6
7

---

这个时候就要实现顺序表的主体功能了~~

检查容量

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//空间不够，需要扩容
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc fail!");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

顺序表的尾插

• 尾插有两种情况
• 第一种是空间足够可以直接插入
• 第二种就是空间不够，需要先检查扩容，再插入

• 所以我们的做法是：

1. 判断顺序表是否有足够的空间，如果有，直接插入
2. 空间不够，需要扩容，扩容怎么扩？需要申请多少个空间？
   • 增容：一般以2倍或者1.5倍进行扩容~~

函数的声明:SeqList.h

//尾插
void SLPushBack(SL* ps, SLDataType x);
1
2

函数的实现:SeqList.c

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//直接插入数据
	ps->a[ps->size++] = x;
}
1
2
3
4
5
6
7
8

顺序表的头插

• 头插也是需要顺序表的空间检查~~
• 那么也是需要检查容量的，和上面代码一样了，我们就将上面的代码分装成一个函数，直接调用就可以了

函数的声明:SeqList.h

void SLPushFront(SL* ps, SLDataType x);
1

函数的实现:SeqList.c

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断空间是否足够，不够则扩容
	SLCheckCapacity(ps);
	//空间足够，历史数据后移一位
	// 挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 这个时候我们可以看到，已经头插进去了~~

顺序表的尾删

• 首先这里还要判断顺序表的有效数据是否为空
• 这里我们再分装一个函数来判断是否为空

函数的声明:SeqList.h

bool SLIsEmpty(SL* ps);
1

函数的声明:SeqList.h

bool SLIsEmpty(SL* ps)
{
	assert(ps);
	return ps->size == 0;
}
1
2
3
4
5

---

• 尾删没有其他操作直接有效数据减减就可以了~~

函数的声明:SeqList.h

void SLPopBack(SL* ps);
1

函数的实现:SeqList.c

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	ps->size--;
}
1
2
3
4
5
6
7

---

打印顺序表

函数的声明:SeqList.h

void SeqListPrint(SeqList* ps);
1

函数的实现:SeqList.c

• assert函数断言传过来的指针是否为空，若为空就直接结束程序 。

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

顺序表的头删

• 需不需要先把第一个位置的数据置为默认值呢？
  • 不需要，只需将后面的数据向左挪动一位，直接覆盖就可以了~~

函数的声明:SeqList.h

void SLPopFront(SL* ps);
1

函数的实现:SeqList.c

//顺序表的头删
//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps)); 
	//让后面的数据往前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 可以看到头删已经成功了

在顺序表的指定位置插入数据

• 情况一：检查容量，容量足够，直接插入
• 情况二：检查容量，容量不够，需要扩容，扩容完毕，直接插入

函数的声明:SeqList.h

void SLInsert(SL* ps, int pos, SLDataType x);
1

• 这里需要注意，pos要检查范围，不能不能负数和超出有效数据的范围~~

函数的实现:SeqList.c

//在顺序表pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//需要限制范围
	assert(pos >= 0 && pos <= ps->size);
	//检查容量
	SLCheckCapacity(ps);
	
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos - 1] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 可以看到已经插入了~~

• 有了指定位置之前插入数据之后，就可以在头插尾插口中直接调用该函数即可~~

---

在顺序表的指定位置删除数据

函数的声明:SeqList.h

void SLErase(SL* ps, int pos);
1

• 一样，需要先检查顺序表有没有有效数据，照样限制范围~~

函数的实现:SeqList.c

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	assert(pos >= 0 && pos <= ps->size);
	for (int i = pos - 1; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11

顺序表的查找

• 这里很简单直接遍历查找就可以了~~

函数的声明:SeqList.h

bool SLFind(SL* ps, SLDataType x);
1

函数的实现:SeqList.c

bool SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x) 
			return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11

---

源码~~

SepList.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//类型重命名
typedef int SLDataType;

//结构体的定义
typedef struct SeqList
{
	SLDataType* a;
	int size;//记录多少个有效数据
	int capacity;//空间容量
}SL;


//初始化顺序表
void SLInit(SL* ps);

//销毁顺序表
void SLDestroy(SL* ps);

//尾插
void SLPushBack(SL* ps, SLDataType x);

//头插
void SLPushFront(SL* ps, SLDataType x);

//尾删
void SLPopBack(SL* ps);

//头删
void SLPopFront(SL* ps);

//打印顺序表
void SLPrint(SL* ps);

//判断是否为空
bool SLIsEmpty(SL* ps);

//在任意位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x);

//在任意位置之前删除
void SLErase(SL* ps, int pos);

//查找顺序表
bool SLFind(SL* ps, SLDataType x);
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

SepList.c

#include"SepList.h"

//初始化顺序表
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

//销毁顺序表
void SLDestroy(SL* ps)
{
	if(ps->a)
		free(ps->a);
	ps->capacity = ps->size = 0;
}

//检查容量
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//空间不够，需要扩容
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc fail!");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断空间够不够？
	SLCheckCapacity(ps);
	//直接插入数据
	ps->a[ps->size++] = x;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断空间是否足够，不够则扩容
	SLCheckCapacity(ps);
	//空间足够，历史数据后移一位
	// 挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	//让后面的数据往前挪动一位
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

//打印顺序表
void SLPrint(SL* ps)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//判断空间是否为空
bool SLIsEmpty(SL* ps)
{
	assert(ps);
	return ps->size == 0;
}


//在任意位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//需要限制范围
	assert(pos >= 0 && pos <= ps->size);
	//检查容量
	SLCheckCapacity(ps);
	
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos - 1] = x;
	ps->size++;
}

//在任意位置之前删除
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(!SLIsEmpty(ps));
	assert(pos >= 0 && pos <= ps->size);
	for (int i = pos - 1; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

//查找顺序表
bool SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x) 
			return true;
	}
	return false;
}
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