写在前面
顺序表是数据结构里面最简单的一个知识,不过它能够充分体现出数据结构的思想,今天让我们正式进入拉开数据结构的帷幕.让我们一起来学习吧.
线性表
在谈正式内容之前,我们先来看看什么是线性表。
线性表（linear list）是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表：顺序表、链表、栈、队列、字符串...
这里我想重点谈谈线性表,首先线性表是一个序列,不是那个升序降序的序列,就是一组数.对于存在多个数据,第一个元素找不到前驱,最后一个元素找不到后驱,其余的都有一个前驱和一个后驱.再说一下,里面的元素是相同数据类型的,不能存在不同的数据类型.说人话线性表就是我们可以拿一个绳子把所有相同的数据给串起来.
顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改.它的本质就是一个数组.我们会疑惑我们既然有数组,为何还会出现顺序表呢?实际上在C99之前,我们的编译器不支持变常数组,在对数据的存储方面有一定的不便之处,比如说我们要是空间开大了就浪费,小了不够用这就出现了顺序表.今天顺序表的博客是很简单的,就是关于数组元素的增删查改.没有很么可以值德思考的地方,细心一点就可以了.顺序表又分为：
- 静态顺序表：使用定长数组存储
- 动态顺序表：使用动态开辟的数组存储.
静态顺序表
我们平常是不用静态数组的,这里我们为了知识的完整性,顺便为下面的动态顺序表做铺垫.这里我们想的是既然是顺序表,这里我们给一个结构体,里面成员包含一个数组,既然有数组了,这里是不是应该有一个变量存储数组里面有效元素的个数.这就构成了一一个简单的顺序表.
#define NUM 100
struct StaticSeqList
{
int array[NUM];
size_t size;
};
静态顺序表都很大的缺点,一般它得大小在运行得时候已经确定了,也就是说在运行前我们需要估算该给这个数组多大得空间,但是有的项目数据是一直产生得,我们空间随着时间要的越来越大,如果我们要是一开始就给了很大得空间,这里就占据了,其他程序就不能使用,很不好.所以一般我们不太提倡使用静态顺序表,除非是在它适当的地方.
动态顺序表
我们这里开始我们今天的大菜,既然静态的有很大的缺点,那么我们在C语言学过动态开辟内存,这里我们就可以使用这个知识点.我们先来用一下.
struct SeqList
{
int* array;
size_t size; // 记录元素的有效个数
size_t capacity; // 记录数组的大小
};
上面就是我们动态顺序表的框架,我们可以根据自己数据扩大来动态的增长我们的空间,空间不够了就扩容.但是我们上面的顺序表还存在两个小问题,这里我们先来解决第一个.这里我们存储的是int类型的数据,如果我们要是存储char或者其他的类型,这个就不太适用了,所以这里我们需要这么做.
typedef int SLDateType;
struct SeqList
{
SLDateType * array;
size_t size;
size_t capacity;
};
还有另外一个,在C语言中struct SeqList 才是我们的数据类型,这里每一次带上struct感觉都有点麻烦,这里我们也修改下.
typedef int SLDateType;
typedef struct SeqList
{
SLDateType * array;
size_t size;
size_t capacity;
} SeqList;
常见接口
我们知道了顺序表是什么,这里就来简单的实现一下它的用法,顺序表的操作莫过于增删改查,这里函数的实现是非常简单的,我们需要细心一点,前面如果看过我写的通讯录博客,这里理解的会更容易点.
SeqListInit()
由于我们的数据结构是由C语言写的,我们首先要做的就是给我们的顺序表进行初始化,这里存在一个问题,我们对于初始化函数参数如何传递?我们先来看一下下面的代码.
void SeqListInit(SeqList ps)
{
ps.array = NULL;
ps.capacity = 0;
ps.size = 0;
}
这里我们需要先测一下自己写的函数对还是不对,大家在学习数据结构的时候一定要写一个函数测一下功能,不要把所有的函数都实现了,最后测,这样你会发现修改错误比你写代码的时间还要长.这里VS2019检测很严格,不允许使用未初始化的变量我们在Linux环境下测试,大家看不懂没有关系,只需看看结果就行了.
#include "SeqList.h"
void TestInit()
{
SeqList s;
SeqListInit(s);
printf("hello 数据结构");
}
int main()
{
TestInit();
return 0;
}
我们发现s1里面的成员都没有被修改,这里的原因就和我们前面说的一样,函数传参会拷贝一个形参,改变形参是不会影响实参的.
void f(int b)
{
b = 20;
}
int main()
{
int a = 0;
f(a);
printf("%d", a);
return 0;
}
所以这里我们使用的是指针传参,注意一点就可以了.
void SeqListInit(SeqList* ps)
{
// 首先检测 是否为空
assert(ps);
//这里有两个模式,一个是初始化的时候开辟点空间
//一个不开,这里我们选择不开
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
我们在测试一下.
void TestInit()
{
SeqList s ;
SeqListInit(&s);
printf("hello 数据结构");
}
int main()
{
TestInit();
return 0;
}
SeqListPushBack()
我们来是实现一下尾插这个函数,这里还是比较简单的,不过我们在进行数据插入之前需要判断一下这个顺序表的空间是不是够,不够的话我们就要增容.大家看一下下面的代码,要是不太明白realloc可以去查看一下手册,很简单.
再谈一下下面得扩容机制,这里我们选择得是2倍扩,我们是可以选择4倍,5倍...但是这里我们需要认识到一点,如果我们原数组有100个有效元素,我们只是为了插入1个元素,你给我扩大了5倍,这里不就是浪费了吗?当然我们2倍扩容在上面的情况也是有点浪费,可以换成1.3倍,这里看实际情况,无论我们如何选择,尽量往浪费少的地方想就可以了.这个时候有人又会想,既然我们成倍数的扩容都会造成浪费,我们这里插入一个扩一个空间不行吗?那么请问我们调用realloc函数扩容会不会降低效率 ,这里都是需要我们考虑的.
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
// 检测扩容
if (ps->size == ps->capacity)
{
size_t newSize = 2 * ps->capacity; // 我们先择得是 2 倍 扩
SLDateType* ret = realloc(ps->array, sizeof(SLDateType) * newSize);
assert(ret);
ps->capacity = newSize;
ps->array = ret;
}
// 到这一步 空间够了
ps->array[ps->size++] = x;
}
在测试这个代码之前,我们先吧打印函数简单的写一下,等下用来辅助验证我们上面写的函数对不对.注意这里我们打印函数传指针的原因和初始化函数是不一样的,这里是为了拷贝的时候消耗少一点,毕竟指针不是4字节就是8字节,结构体有点大.
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (size_t i = 0; i < ps->size; i++)
{
printf("%d ", *(ps->array + i));
}
printf("\n");
}
好了,万事俱备,这个时候我们就需要来测试一下尾插函数究竟对不对了.
void TestPuskBack()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPrint(&s);
}
int main()
{
TestPuskBack();
return 0;
}
我们一看很不错,这里我们得到结果是正确的,那么真的是正确的吗?我们调试一下,这里有些东西我们被编译器给骗了.要知道我们初始化的时候容量给的是0,第一次插入数据肯定要扩容,这里就是我们出现问题的地方,0乘任何数都是0,我们怎么扩容结果还是0,这里就申请不出空间.
有的人可能异疑惑,我们没有申请出空间,那么这里也就是我们越界访问了,使用了野指针,请问程序为何还运行成功了?这里我们要提出一个结论,编译器对于数组越界的检测是随机的,也就是有的时候可以检测出来,有的时候不能.我们看一下下面的结果.
int main()
{
int arr[10] = { 0 };
arr[10] = 1;
printf("%d", arr[10]);
return 0;
}
那么下面的越界呢?你就会发现这里就检测不出来,所以我们需要一再小心,这里每一步都是坑.
int main()
{
int arr[10] = { 0 };
arr[11] = 1;
printf("%d", arr[11]);
return 0;
}
这里我们修改一下就可以了在第一次的时候给它开4个元素的空间,注意是一定要开4个,是你觉得开几个好就开几个.
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
// 检测扩容
if (ps->size == ps->capacity)
{
size_t newSize = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDateType* ret = realloc(ps->array, sizeof(SLDateType) * newSize);
assert(ret);
ps->capacity = newSize;
ps->array = ret;
}
// 到这一步 空间够了
ps->array[ps->size++] = x;
}
SeqListPopBack()
谈完了尾插这里就说一下尾删吧.个是非常简单的.我们这样想,所谓的尾删不就是不要最后一个元素吗,而不要最后一个元素不就是让用户看不到它吗,看不到它不就是让size减掉1吗,至于最后一个有效空间的数据存储的是啥我们一点都不关心.这里需要注意一下原本的顺序表没有元素的情况.
void SeqListPopBack(SeqList* ps)
{
assert(ps);
if(ps->size == 0)
return;
ps->size--;
}
我们这里测试一下,倒是挺简单的.
void TestPopBack()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPrint(&s);
SeqListPopBack(&s);
printf("===============\n");
SeqListPrint(&s);
}
int main()
{
TestPopBack();
return 0;
}
SeqListPushFront()
尾部的相关操作我们已经写完了,这里开始头部的相关操作.先来谈头部的插入,我们插入数据之前首先要做的就是看看自己空间是不是够,这里就涉及到扩容操作.那么我们是不是还要写扩容的判断呢?这里要是写了就是代码冗余了,所以这里我们应该把扩容操作封成一个函数,需要的时候调用就可以了.
void SeqListCheckCapacity(SeqList* ps)
{
assert(ps);
if (ps->capacity == ps->size)
{
// z注意这个判断很重要
size_t newSize = ps->capacity == 0 ? 4 : 2 * ps->capacity;
// 开辟空间 使用 realloc
// 这个函数 会开辟拷贝
int* ret = (int*)realloc(ps->array, sizeof(SLDateType) * newSize);
assert(ret);
ps->array = ret;
ps->capacity = newSize;
}
}
那么前面我们写的尾插函数就要发生点改变了,不用自己再判断是不是要扩容了.
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
// 检测扩容
SeqListCheckCapacity(ps);
// 到这一步 空间够了
ps->array[ps->size++] = x;
}
好了,现在我们就可以实现头插函数具体实现了.我们先来整理一下思路,头插就是我们把已有的元素整体往后移动一个,把下标为0的位置给空出来,最后把新元素插入进去就可以了.那么我们看一下代码吧.
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
// 扩容
SeqListCheckCapacity(ps);
size_t pos = ps->size-1;
while (pos >= 0)
{
ps->array[pos + 1] = ps->array[pos];
--pos;
}
ps->array[0] = x;
ps->size++;
}
注意上面的代码存在很大的问题,我们来测试下.
void TestPushFront()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPrint(&s);
SeqListPushFront(&s, 0);
SeqListPrint(&s);
}
int main()
{
TestPushFront();
return 0;
}
下面我来简单的分析一下,我们这里想一想当这个顺序表里面没有元素的时候,pos等于-1,不满足循环条件,这里不进入循环,按理说这里应该是对的,那么为何会报错呢?这里大家忘记了变量的类型,这里我们用的是size_t,也就是无符号整数,一直是大于等于0的,不可能出现-1,所以这里while循环一直运行,直到程序崩溃.至于为何要使用size_t的类型呢?这里留到insert函数和大家解释.
void TestPushFront()
{
SeqList s;
SeqListInit(&s);
SeqListPushFront(&s, 0);
SeqListPrint(&s);
}
int main()
{
TestPushFront();
return 0;
}
既然这个方法不太行,我们有什么解决方法吗?这里有两个,一个就是强制类型转化,这个代码放在下面了.另外一个方法就比较容易了,我们把pos指向size,直接取前一个数据,这样pos就不会到0了.
// pos 指向size
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
// 扩容
SeqListCheckCapacity(ps);
size_t pos = ps->size;
while(pos > 0)
{
ps->array[pos] = ps->array[pos-1];
--pos;
}
ps->array[pos] = x;
ps->size++;
}
// 强制类型转换
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
// 扩容
SeqListCheckCapacity(ps);
size_t pos = ps->size-1;
while ((int)pos >= 0)
{
ps->array[pos + 1] = ps->array[pos];
--pos;
}
ps->array[0] = x;
ps->size++;
}
这里我们就可以简单的验证一下了,不用怀疑,这里是正确的.
void TestPushFront()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPrint(&s);
SeqListPushFront(&s, 0);
SeqListPrint(&s);
}
int main()
{
TestPushFront();
return 0;
}
SeqListPopFront()
这个倒是挺简单的,也没有太多的坑,注意一点判断顺序表是不是为空就可以了.
void SeqListPopFront(SeqList* ps)
{
assert(ps);
if (ps->size == 0)
return;
for (size_t i = 1; i < ps->size; i++)
{
ps->array[i - 1] = ps->array[i];
}
ps->size--;
}
我们这里要重点谈一下如何测试代码,一般而言,对于删除函数,.我喜欢删除尾部,中间,头部各一个,这样一般就可以覆盖大部分情况了,不过这里是头删,从头删到尾就可以;了.
void TestPopFront()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
for (int i = 0; i < 4; i++)
{
SeqListPopFront(&s);
SeqListPrint(&s);
}
}
int main()
{
TestPopFront();
return 0;
}
SeqListInsert()
这个需要我们简单的分析一下,我们在pos位置插入数据,这里就要把pos和pos之后的数据往后移动,新数据插入pos位置.听着是不是很熟悉,我们的头擦就是如此,所以头擦需要注意的,insert都需要注意,除此之外我们还需要注意另外的一件事时,我们需要判断pos的合法性.顺序表的数据是连续的,因此我们呢不能所以插入数据.
这里我们就可以解释我们为何传参要使用size_t类型的了.由于无符号整数不会小于零,这就造成我们只需要判断一种情况就可以了,不过最关键的原因是在我们后续的C\++有一个STL,里面保存者我们常见的数据结构,其中vector就是我们的顺序表,我们来看一下它们的函数接口也是size_t,这里我们选择和他一样.
说了这么多,我们来实现一个这个函数,注意点细节就可以了,不太难.
void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)
{
assert(ps);
//判断pos的合法性
assert(pos <= ps->size); // 等于箱单于尾插
SeqListCheckCapacity(ps);
size_t end = ps->size;
while (end > pos)
{
ps->array[end] = ps->array[end - 1];
end--;
}
ps->array[pos] = x;
ps->size++;
}
来都来了,这里不验证一下吗,我们这里验证头部尾部中间三大部分,
void TestInsert()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPrint(&s);
printf("---------------\n");
SeqListInsert(&s, 3, 4); // 尾插
SeqListPrint(&s);
SeqListInsert(&s, 0, 0); // 头插
SeqListPrint(&s);
SeqListInsert(&s, 2, -1);// 中间插入
SeqListPrint(&s);
}
int main()
{
TestInsert();
//TestPopFront();
//TestPopBack();
return 0;
}
这里我们实现好了,那么前面我们写的尾插和头插就可以直接复用这个函数了,不用自己实现了.
void SeqListPushBack(SeqList* ps, SLDateType x)
{
SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
SeqListInsert(ps, 0, x);
}
SeqListErase()
这里和前面我们的头删一样都是很简单的,我们只需要注意下细节就可以了.
void SeqListErase(SeqList* ps, size_t pos)
{
assert(ps);
assert(pos < ps->size); // 这里不等 是因为数组下标越界
if (ps->size == 0)
return;
for (size_t i = pos + 1; i < ps->size; i++)
{
ps->array[i-1] = ps->array[i];
}
ps->size--;
}
是不是正确我们来测一下代码,这里简单的验证一下.
void TestInsert()
{
SeqList s;
SeqListInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPrint(&s);
SeqListErase(&s, 0);
SeqListPrint(&s);
SeqListErase(&s, 1);
SeqListPrint(&s);
SeqListErase(&s, 1);
SeqListPrint(&s);
}
int main()
{
TestInsert();;
return 0;
}
到这里和上面一样,我们头删和尾删都可以复用这个代码了.
void SeqListPopFront(SeqList* ps)
{
SeqListErase(ps, 0);
}
void SeqListPopBack(SeqList* ps)
{
SeqListErase(ps, ps->size-1);
}
SeqListDestroy()
上面我的的测试程序都有一个问题,我们不用这个顺序表的时候,需要释放掉申请的空间,否则会造成内存泄漏问题.
void SeqListDestroy(SeqList* ps)标签：ps,顺序,SeqList,pos,我们,array,不会,表吧,size From： https://blog.51cto.com/byte/5780593
{
assert(ps);
ps->capacity = 0;
ps->size = 0;
// 释放 NULL 也不会报错
// 不过最好判断一下
if(ps->array)
free(ps->array);
ps->array = NULL;
}