开始的话
从这篇开始, 我会开始重新学习数据结构与算法, 在上学期由于疫情 (也有自己的原因啦) 导致这一门很重要的课我学习得不是非常的好, 于是接下来打算好好的补一补. 我的文章主要会是代码为主, 然后附上讲解, 所以需要一定的C语言基础.
代码测试环境:gcc
吐槽: 我们教材使用了许多的非标准C特性 (GUN C的编译器特性) , 我们老师在教C语言语法的时候也教了许多编译器特性, 但是他也没有说明这是编译器特性 (摔桌!) , 我以为都是标准C. 我照着教材写然后使用标准C来编译运行老是报错, 害我debug了半天, 后来我查阅资料才发现是编译器特性, 坑死我了~.
我会尽量把那些编译器特性的写法改成标准C
好了, 不吐槽了, 今天就先以顺序表开始吧
顺序表的基本概念和特点
存储结构
顺序表就是线性表的顺序表示, 引用书上的话:
"线性表的顺序表示是指用一组连续的存储单元依次存储线性表的数据元素.假设线性表中每个数据元素占用l个存储单元, 第i个元素的地址是LOC (ai) , 那么第i+1个元素的
地址LOC (ai+1) 等于LOC (ai) +l."
说人话就是顺序表元素在内存上是连续存储的, 一个挨着一个的 (不考虑实际物理内存偏移等) , 一个元素的下一个地址就是下一个元素, 有点像我们C语言的数组.
时间复杂度及适用场景
由于顺序表是连续存储的, 所以我们只要知道了顺序表的基地址 (首地址) , 表中的任意一个元素都可以直接读取的, 所以读取任意元素的时间复杂度为O (1) .
顺序表往里在任意位置删除和添加的时间复杂度都为O (n)
以删除为例, 我们删除顺序表中的第i个元素, 那么从i+1到n-1位置上的所有元素都要往前移一个单位, 假设删除这些元素的概率相同, n个元素有有n个可能删除位置, 从这些位置删除要移动n-1,n-2,....1,0个元素,那么平均要移动 (n-1)/2 个元素, 平均算法时间复杂度为O(n), 添加同理.
我们注意到,顺序表在添加/删除最后一个元素的时候的时间复杂度也为O(1).
总结一下,顺序表最主要的优点就是：支持随机访问,最主要的缺点也就是插入删除元素时需要移动元素.
综上所述,顺序表特别适合用在频繁的访问元素, 很少插入或删除元素或者仅频繁在尾部插入删除的场景
代码实现及讲解
常用操作
这里直接用的书上的函数名
- Listinit(Listlp);//初始化,将一个 List变量初始化为空的线性表.
- Listclear(Listlp);//清空,删除线性表中全部元素,逻辑上清空线性表.
- voiddestroy(List* lp);//销毁,不再使用该表前需要进行的操作,注意和清空区别.
- _Boolempty(constList*lp);//判断是否为空表.
- unsignedlength(constList*lp);//求线性表长度.
- Listinsert(List lp,ADTdata,inti);//在线性表第i个元素之前插入元素data.
- List erase(Listlp,inti);//删除线性表第i个元素.
- intremove(List*lp,ADTdata);//删除线性表中所有值等于data的元素.
管理单元
我们定义顺序表中的数据类型为ADT,由于C语言不支持泛型程序设计, 所以我们直接把int当作ADT使用
typedef int ADT;下面是顺序表的管理单元
typedef struct
{
//元素个数
unsigned int size;
//当前已分配空间(单元)
unsigned int capacity;
//指向存储位置的指针
ADT *array;
} SqList;准确的来说,SqList是应该顺序表的管理结构,就像图书管理员一样, 记录着这个图书馆 (顺序表) 存了多少本书(存了多少个元素) (size) ,图书馆的容量有多大 (分配了多少的空间) (capacity) , 以及图书馆在哪个位置 (指向分配空间的指针) (*array). 不过, 一般来说把SqList直接看作一个顺序表也行.
顺序表的初始化
我们直接使用如 SqList sq 这种来定义sq变量直接作为一个顺序表使用是不行的, 因为sq是结构体, 直接定义的话不会初始化里面的数据, 这时里面的数据都是乱的, 不是一个有效的顺序表管理结构. 那么这时候我们就要在定义后首先初始化这个顺序表, 让里面的数据是有意义的.
SqList *init_sq(SqList *p, unsigned a)
{
p->size = 0;
p->capacity = a ? a : 8;
//如果接收的a为0，则初始化为8；
p->array = (ADT *)malloc(p->capacity * sizeof(ADT));
if (!p->array)
{
return NULL;
//如果malloc分配失败了，会返回0，则这个函数也返回NULL
}
return p; //返回接收的那个地址
}这样我们的顺序表(管理结构)就有意义了,参数p表示待初始化 SqList变量的地址, 参数a表示希望为顺序表预分配存储单元的个数, a应该是正整数 (代码中对a为0的情况进行了简单处理). 函数返回初始化后顺序表变量的地址, 含义是
"初始化顺序表操作后得到的结果就是这个被初始化的顺序表".代码中将size初始为0,表示空表;将capacity初始为参数c的值;使用 malloc函数分配能够存放capacity个ADT类型数据元素的堆区内存,首地址保存在array中.如果分配地址失败,则返回地址0(NULL).
顺序表的清空与销毁操作
清空
清空后数据表任然可以用（只是逻辑上清空），开的空间还在，只是将大小(size)清零
SqList *clear_sq(SqList *p)
{
p->size = 0;
return p;
}销毁
销毁就干了两件事, 释放空间, 指针指向空.
int destroy_sq(SqList *p)
{
free(p->array);
p->array=NULL;
return 0;
}顺序表的读写元素操作
虽然在C语言中,永远可以使用“s.array[i]”的形式访问顺序表s中的第i个数据元素。 这里仍然提供了geti_sq和seti_sq两个函数分别用于顺序表元素的安全读写。两个函数在 成功操作后,返回所操作顺序表的地址,含义是“对顺序表进行读或写元素操作后,顺序表还 是那个顺序表”。函数中,首先对表示元素索引号的参数i进行了验证,如果i不在合理范围
之内,函数返回地址0。
读取
读取第i个元素, 并且把读到的元素值写入参数dest指向的空间中:
const SqList *geti_sq(const SqList *p, unsigned i, ADT *dest)
{
//如果超出读取范围则返回空
if (i >= p->size)
{
return NULL;
}
*dest = p->array[i];
return p;
}修改
修改第i个元素，由source覆盖第i个元素:
SqList *seti_sq(SqList *p, unsigned i, ADT source)
{
if (i >= p->size)
{
return NULL;
}
p->array[i] = source;
return p;
}顺序表的空间扩展操作
在我们向顺序表写入元素时,会遇到已分配的空间不足的时候(size==capacity), 这时就需要对顺序表的空间进行扩展了.
//默认大小扩展为原来的2倍
SqList *extend_sq(SqList *p)
{
//定义一个新指针,并指向已经分配了2倍原空间的地址
ADT *np = (ADT *)malloc(p->capacity * 2 * sizeof(ADT));
//把原来的数据复制给新空间
memcpy(np, p->array, sizeof(ADT) * p->size);
//释放原来的空间
free(p->array);
//array指向新地址,并调整capacity的大小
p->array = np;
p->capacity *= 2;
return p;
}顺序表的尾部插入删除操作
对于顺序表来说,在尾部插入和删除元素是非常常见的操作,时间复杂度为O ( 1 ) 所以要单独写一个操作
尾部插入
SqList *push_back_sq(SqList *p, ADT source)
{
if (p->capacity == p->size)
{ //空间不够了，扩展空间
extend_sq(p);
}
p->array[p->size++] = source;
return p;
}尾部删除
SqList *pop_back_sq(SqList *p)
{
if (p->size == 0)
{ //没有元素了，返回NULL
return NULL;
}
p->size--;
return p;
}顺序表任意位置的插入删除操作
任意位置插入
//在第i位插入元素,原来的数据向后挪一位
SqList *insert_sq(SqList *p, unsigned i, ADT source)
{
if (i > p->size)
{ //合理的插入位置应该是有size个,而不是size-1个,因为插在末尾也算插入,例如有size=5,插在array[size]是可以的(算末尾插入)
return NULL;
}
if (p->capacity == p->size)
{ //当空间不够插入时扩展空间
extend_sq(p);
}
memmove(p->array + i + 1, p->array + i, (p->size - i) * sizeof(ADT));
//如果插在末尾则复制个数为0
//注意memmove与memcopy的区别
p->array[i] = source;
p->size++;
return p;
}任意位置删除
//删除第i个元素,后面的元素向前挪
SqList *erase_sq(SqList *p, unsigned i)
{
if (i >= p->size)
{
return NULL;
}
memmove(p->array + i, p->array + i + 1, (p->size - i - 1) * sizeof(ADT));
//就是直接将后面的元素往前挪一位覆盖就实现删除了
p->size--;
return p;
}在顺序表的任意位置插入(删除)元素,会造成操作位置之后的元素向后(向前)移动。 为完成元素移动,这里使用了C语言函数 memmove,而不是 memcpy。函数 memcpy复制 内存数据时,不考虑数据目的地址和源地址重叠的情况。当元素目的地址和源地址重叠时, 向后移动数据,应该从后向前逐一复制元素。向前移动数据,应该从前向后逐一复制元素。
只有如此操作,才能保证数据被覆盖(写)之前被读取
条件删除
在介绍条件删除时,先介绍一下"删除顺序表内比指定元素d小的元素"的函数
unsigned remove_if_sq(SqList *p, ADT d)
{
unsigned count, r, w;
count = r = w = 0;
while (r < p->size)
{
if (p->array[r] < d)//这里是判断
{
count++;
}
else
{
p->array[w++] = p->array[r];
}
r++;
}
p->size -= count;
return count;
}解释一下: 代码中的变量r和w分别跟踪读写位置,当读到元素小于d时,count++,代表删除了一个元素了,否则当读到的元素不小于d时,发生写操作,每写一个元素w便向后移动一个位置,不论写操作是否发生,r都会向后移一位,当r扫描过顺序表的全部元素后,调整变量size,算法终止,返回删除了多少个元素(count). 这样由于小于的d元素没有写入,所以在逻辑上这些元素就不在了.
但是这里有个问题,如果我们的操作不是小于是等于呢?是不是我们还要再写一个"从顺序表中删除等于指定元素d的元素"函数呢?那求根相等, 平方相等呢? 是不是都要写一个函数呢?
大可不必, 实际上, 利用函数指针, 我们只需要写一个判断函数然后返回真假就行了, 具体怎么判断由我们自己在函数内定义即可
下面是改进后的条件删除:
//用函数指针来判断true_or_false,true则删除(可更改为调用一个操作)
//调用方法:remove_if_sq(顺序表,判断函数(自己写))
unsigned remove_if_sq(SqList *p, ADT d, _Bool (*judgment)(ADT, ADT))
{
unsigned count, r, w;
count = r = w = 0;
while (r < p->size)
{
if (judgment(p->array[r], d))
{
count++;
}
else
{
p->array[w++] = p->array[r];
}
r++;
}
p->size -= count;
return count;
}在我们需要调用的时候,只需要写一个判断的函数,例如判断相等的函数:
_Bool jud_equal(ADT a, ADT b)
{
return a == b;
}然后比如我们要删除等于100的函数我们就可以写:remove_if_sq(&sq, 100, jud_equal);了,非常方便.
问:为什么remove_if_sq()要用函数指针而不是直接调用一个函数呢?
答: 因为在编写的时候你也不知道要判断的是什么呀,你就更不知道你要该调用哪个函数来判断了.所以就需要通过函数指针来告诉我们是调用哪一个函数.
代码汇总及测试
测试：
我们写一个打印的代码,帮助我们把这时候顺序表的情况打印出来
int print_sq(SqList *p)
{
printf("顺序表大小:%d,空间大小:%d,元素:", p->size, p->capacity);
for (int i = 0; i < p->size; i++)
{
int x;
geti_sq(p, i, &x);
printf(" %d ", x);
}
printf("\n");
return 0;
}测试代码:
//判断是否相等的函数
_Bool jud_equal(ADT a, ADT b)
{
return a == b;
}
//帮助打印顺序表
int print_sq(SqList *p)
{
printf("顺序表大小:%d,空间大小:%d,元素:", p->size, p->capacity);
for (int i = 0; i < p->size; i++)
{
int x;
geti_sq(p, i, &x);
printf(" %d ", x);
}
printf("\n");
return 0;
}
int main()
{
//定义一个顺序表
SqList sq;
//初始化顺序表
init_sq(&sq, 4);
//在顺序表上尾部放数据，放一次打印一次
for (int i = 0; i <= 10; i++)
{
push_back_sq(&sq, i);
print_sq(&sq);
}
//从顺序表弹出数据，弹一次打印一次
for (int i = 0; i < 6; i++)
{
pop_back_sq(&sq);
print_sq(&sq);
}
//修改第0个元素为100
seti_sq(&sq, 0, 100);
print_sq(&sq);
//在第一个位置插入元素200
insert_sq(&sq, 1, 200);
print_sq(&sq);
//删除第一个元素
erase_sq(&sq, 1);
print_sq(&sq);
//移除所有等于100的元素
remove_if_sq(&sq, 100, jud_equal);
print_sq(&sq);
//清空数据表
clear_sq(&sq);
print_sq(&sq);
//销毁数据表
destroy_sq(&sq);
return 0;
}运行结果:
汇总：
附上包括测试代码及注释在内的所有代码(完整直接运行):
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
typedef int ADT; //定义数据类型为ADT
//顺序表的管理单元，管理这个顺序表有多大，在哪个位置，分配了多少空间
typedef struct
{
unsigned int size; //元素个数
unsigned int capacity; //当前已分配空间(单元)
ADT *array; //指向存储位置的指针
} SqList;
//初始化链表
//顺序表使用前得先初始化顺序表，否侧里面的数据是乱的
//只是这样定义：SqList xxx 是不行的，没初始化
// 假设我们先定义了 SqList sq，那么初始化操作为init_sq(&sq,4)
SqList *init_sq(SqList *p, unsigned a)
{
p->size = 0;
p->capacity = a ? a : 8; //如果接收的a为0，则初始化为8；
p->array = (ADT *)malloc(p->capacity * sizeof(ADT));
if (!p->array)
{
return NULL; //如果malloc分配失败了，会返回0，则这个函数也返回NULL
}
return p; //返回接收的那个地址
}
//清空顺序表
//清空后数据表任然可以用（只是逻辑上清空），开的空间还在，只是将大小(size)清零
SqList *clear_sq(SqList *p)
{
p->size = 0;
return p;
}
//销毁顺序表
//释放内存
int destroy_sq(SqList *p)
{
free(p->array);
p->array=NULL;
return 0;
}
//读取
//读取第i个元素，将值写入dest
const SqList *geti_sq(const SqList *p, unsigned i, ADT *dest)
{
if (i >= p->size)
{
return NULL;
}
*dest = p->array[i];
return p;
}
//修改
//修改第i个元素，由source覆盖第i个元素
SqList *seti_sq(SqList *p, unsigned i, ADT source)
{
if (i >= p->size)
{
return NULL;
}
p->array[i] = source;
return p;
}
//扩展空间
//默认大小扩展为原来的2倍
SqList *extend_sq(SqList *p)
{
ADT *np = (ADT *)malloc(p->capacity * 2 * sizeof(ADT));
memcpy(np, p->array, sizeof(ADT) * p->size);
free(p->array);
p->array = np;
p->capacity *= 2;
return p;
}
//尾部插入
SqList *push_back_sq(SqList *p, ADT source)
{
if (p->capacity == p->size)
{ //空间不够了，扩展空间
extend_sq(p);
}
p->array[p->size++] = source;
return p;
}
//尾部删除
SqList *pop_back_sq(SqList *p)
{
if (p->size == 0)
{ //没有元素了，返回NULL
return NULL;
}
p->size--;
return p;
}
//任意位置插入
//在第i位插入元素,原来的数据向后挪一位
SqList *insert_sq(SqList *p, unsigned i, ADT source)
{
if (i > p->size)
{ //合理的插入位置应该是有size个,而不是size-1个,因为插在末尾也算插入,例如有size=5,插在array[size]是可以的(算末尾插入)
return NULL;
}
if (p->capacity == p->size)
{ //当空间不够插入时扩展空间
extend_sq(p);
}
memmove(p->array + i + 1, p->array + i, (p->size - i) * sizeof(ADT)); //如果插在末尾的复制个数为0//注意memmove与memcopy的区别
p->array[i] = source;
p->size++;
return p;
}
//任意位置删除
//删除第i个元素,后面的元素向前挪
SqList *erase_sq(SqList *p, unsigned i)
{
if (i >= p->size)
{
return NULL;
}
memmove(p->array + i, p->array + i + 1, (p->size - i - 1) * sizeof(ADT)); //就是直接将后面的元素往前挪一位覆盖就实现删除了
p->size--;
return p;
}
//条件删除
//用函数指针来判断true_or_false,true则删除(可更改为调用一个操作)
//调用方法:remove_if_sq(顺序表,判断函数(自己写))
unsigned remove_if_sq(SqList *p, ADT d, _Bool (*judgment)(ADT, ADT))
{
unsigned count, r, w;
count = r = w = 0;
while (r < p->size)
{
if (judgment(p->array[r], d))
{
count++;
}
else
{
p->array[w++] = p->array[r];
}
r++;
}
p->size -= count;
return count;
}
/*
//判断是否相等的函数
_Bool jud_equal(ADT a, ADT b)
{
return a == b;
}
//函数例式:删除顺序表中等于d的部分,调用条件删除 remove_if_sq 和判断相等函数 jud_squal
unsigned remove_sq(SqList*p,ADT d)
{
return remove_if_sq(p,d,jud_equal);
}
*/
/*
顺序表基本功能完毕
-------------------------------------------
下面是测试代码
*/
//判断是否相等的函数
_Bool jud_equal(ADT a, ADT b)
{
return a == b;
}
//测试代码,帮助打印
int print_sq(SqList *p)
{
printf("顺序表大小:%d,空间大小:%d,元素:", p->size, p->capacity);
for (int i = 0; i < p->size; i++)
{
int x;
geti_sq(p, i, &x);
printf(" %d ", x);
}
printf("\n");
return 0;
}
int main()
{
SqList sq; //定义一个顺序表
init_sq(&sq, 4); //初始化顺序表
for (int i = 0; i <= 10; i++) //在顺序表上尾部放数据，放一次打印一次
{
push_back_sq(&sq, i);
print_sq(&sq);
}
for (int i = 0; i < 6; i++) //从顺序表弹出数据，弹一次打印一次
{
pop_back_sq(&sq);
print_sq(&sq);
}
seti_sq(&sq, 0, 100);
print_sq(&sq);
insert_sq(&sq, 1, 200);
print_sq(&sq);
erase_sq(&sq, 1);
print_sq(&sq);
remove_if_sq(&sq, 100, jud_equal);
print_sq(&sq);
clear_sq(&sq);
print_sq(&sq);
destroy_sq(&sq);
return 0;
}