文章目录
- 前言
- 1.什么是顺序表？
- 1.1线性表
- 2.编写你的顺序表！
- 2.0 赛前准备
- 2.1 初始化
- 2.2 容量检查
- 2.3 打印顺序表
- 2.4 尾插和尾删
- 2.5 头插和头删
- 2.6 插入和删除
- 2.7 查找和更改
- 3.菜单
- 一些err
- 总结
前言
顺序表是我们学习数据结构第一阶段的必经之路
什么是顺序表，且听我慢慢道来
本篇博客用到的知识点：
- 动态内存管理
- 自定义类型-结构体
- 所用编译器：VS2019
1.什么是顺序表？
1.1线性表
线性表是数据结构的一种，它是n个具有相同特性的数据元素的有限序列。 常见的线性表：顺序表、链表、栈、队列、字符串……
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理内存上存储时，通常以数组和链式结构的形式存储。
本篇博客所讲述的顺序表，就是以数组结构存储的线性表
2.编写你的顺序表！
为了保证写完之后不要进入贤者debug状态，建议每编写一个模块，就在test.c的main函数中进行测试，保证当前编写的模块正确后再进行下一步！
不然问题多了，改起来很头疼的！
2.0 赛前准备
和我们日常所用的数组不同，顺序表的这个结构，主要的组成部分是一个结构体（本篇博客中的线性表以int为例）
struct SeqList
{
int* a;
int size; // 存储数据个数
int capacity; // 存储空间大小
};为了方便使用，我们可以使用typedef对符号进行重定义
typedef int SLDataType;
//和普通的整型区分开，以此命名的数据和顺序表直接相关
//动态顺序表
typedef struct SeqList
{
SLDataType* a;
int size; // 存储数据个数
int capacity; // 存储空间大小
}SeqList;
//SeqList可以替代struct SeqList2.1 初始化
本次编写顺序表代码，我们采用“多文件编程”方式，将函数的实现，函数的声明与主函数分开，分别放入两个源文件和一个头文件
先在main函数中定义一个顺序表的结构体，编写SQLinst函数进行初始化
SeqList s;//创建结构体变量
SQLinst(&s);//初始化在.h文件中，我们写入函数声明和库函数的引用。
注意需要在另外两个.c文件中以"Seqlist.h"方式引用自定义头文件
#include"Seqlist.h"
初始化方式如下，我们先给a用calloc函数开辟3个SLDataType(int)类型的空间
- CAPA：由define定义的符号，方便后续修改初始容量
void SQLinst(SeqList* sql)
{
assert(sql);
sql->a = (SLDataType*)calloc(CAPA,sizeof(SLDataType));
sql->capacity = CAPA;
sql->size = 0;
return;
}2.2 容量检查
既然我们的函数是由calloc开辟的动态内存空间，就需要在顺序表内空间不够用的时候，检查容量，判断是否需要扩容
void CheckCapacity(SeqList* sql)
{
assert(sql);
if (sql->size < sql->capacity)
return;
else
{
size_t newcapacity = 2 * (sql->capacity);
SLDataType* tmp = (SLDataType*)realloc(sql->a,newcapacity*sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc failed\n");
exit(0);
}
else
{
sql->a = tmp;
sql->capacity = newcapacity;
}
}
return;
}使用realloc函数的时候需要注意，它可能扩容失败，所以我们不能直接让sql->a来接收realloc函数的返回值（扩容失败返回NULL，相当于前功尽弃）
而是需要用一个中间变量tmp来接收开辟后的地址，确认realloc成功后再赋值给a。同时，也需要将sql->capacity更改成新的容量
2.3 打印顺序表
void SQLprint(SeqList* sql)
{
assert(sql);
for (int i = 0; i < (sql->size); i++)
{
printf("%d ", sql->a[i]);
}
printf("\n");
return;
}2.4 尾插和尾删
和平时使用数组不同的是，线性表中把在表尾插入数据称作尾插、删除数据叫做尾删，对应的是pushback和popback
如果你看过之前我的那篇函数调用参数压栈的博客，应该还记得，汇编代码中入栈和出栈也是push和pop
void SQLpushback(SeqList* sql, size_t x);//尾插
void SQLpopback(SeqList* sql);//尾删实现方式很是简单，和我们日常在数组尾部插入元素相同
需要注意的是，这里我们插入的数据是size_t（unsigned int)类型，也就是说，这个顺序表中并没有负数
void SQLpushback(SeqList* sql, size_t x)
{
assert(sql);
CheckCapacity(sql);//使用时检查容量
sql->a[sql->size] = x;
sql->size++;
return;
}
void SQLpopback(SeqList* sql)
{
assert(sql);
//sql->a[sql->size] = 0;
//这里可以把最后一个数改为0，也可以不改
sql->size--;
return;
}2.5 头插和头删
和尾部修改数据不同，在头部修改数据，必须要把已有数据整体往后移动
void SQLpushfront(SeqList* sql, size_t x)
{
assert(sql);
CheckCapacity(sql);
int i = sql->size;
while (i >= 0)
{
sql->a[i] = sql->a[i - 1];
i--;
}
sql->a[0] = x;//整体后移 之后修改第一个数
sql->size++;
return;
}
void SQLpopfront(SeqList* sql)
{
assert(sql);
int i = 0;
while (i < (int)sql->size)
{
sql->a[i] = sql->a[i + 1];
i++;//直接整体前移即可
}
sql->size--;
return;
}2.6 插入和删除
除了头尾的操作，我们还需要编写在顺序表中间的插入和删除操作
- 插入：需要将插入位置之后的数据整体后移
- 删除：删除位置之后的数据整体前移
- pos：插入位置的下标
void SQLinsert(SeqList* sql, size_t pos, size_t x)
{
assert(sql);
if (pos >= (int)sql->size)
{//温和的判断，assert太过暴力，在OJ里容易出错
printf("input err\n");
return;
}
CheckCapacity(sql);
int i = sql->size;
while (i > (int)pos)
{
sql->a[i] = sql->a[i - 1];
i--;
}
sql->a[pos]=x;
sql->size++;
return;
}
void SQLerase(SeqList* sql, size_t pos)
{
assert(sql);
if (pos >= (int)sql->size)
{//温和的判断，assert太过暴力，在OJ里容易出错
printf("input err\n");
return;
}
int i = pos;
while (i < (int)sql->size-1)
{
sql->a[i] = sql->a[i + 1];
i++;
}
sql->size--;
return;
}2.7 查找和更改
当我们需要查找的时候，必须从头开始遍历整个数组，来找到待查找元素
int SQLfind(SeqList* sql, size_t x)
{
assert(sql);
for (int i = 0; i < sql->size; i++)
{
if (sql->a[i] == x)
{
return i;//返回下标
}
}
printf("find err\n");
return -1;
}而修改函数则是在查找的基础上，更改掉目标元素
void SQLmodify(SeqList* sql, size_t pos, size_t x)
{
assert(sql);
sql->a[pos] = x;
return;
}如果用户不知道自己想修改的元素的下标，可以通过find函数查找，再调用修改函数
3.菜单
一个小建议是，不要在一开始编写函数的时候就写出菜单！
因为这样非常不方便debug，你需要按菜单上的函数调用再进行下一步操作
话说是不是应该在前面就告诉大家？
标签：return,int,SeqList,printf,C语言,详解,sql,灵活运用,size From： https://blog.51cto.com/musnow/11898946