@
目录前言
讲完算法效率,就正式开始我们的数据结构了,而今天博主讲解的内容是顺序表
顺序表
何为顺序表?即一个数组,在逻辑结构和物理结构上,它都是连续的,这里有个概念:逻辑与物理结构.
- 逻辑结构: 人为所想出来的,实际并不存在.
- 物理结构: 实际存在,可以观察得到的
怎么理解这两个概念呢?举个例子,假设有 甲乙丙丁戊 五个人.
-
如果挨着顺序站成一排,五个人依次报数,会报1 2 3 4 5.
- 逻辑上来讲,他们五个人是连续的,因为依次报数1 2 3 4 5
- 物理上来讲,他们五个人
是连续的,因为顺序是 甲乙丙丁戊
-
如果五个人随机站成一排,五个人同样依次报数,会报1 2 3 4 5
- 逻辑上来讲,他们五个人是连续的,因为依次报数1 2 3 4 5
- 物理上来讲,他们五个人
不是连续的,因为顺序不是 甲乙丙丁戊,可能丙丁甲乙戊,可能......
顺序表即如此,物理与逻辑结构都连续.
- 物理结构是他的存储地址,地址连续
- 逻辑结构是我们逻辑认为他的数据是连接在一起的
而顺序表有两种: 分别是静态版与动态版,我们着重讲解的就是动态版,因为静态版其实就完完全全是个普通数组,讲解意义不大.
何为动态版顺序表? 即数组是动态的,容量不受限制,支持数据插入,删除,修改等一系列操作,下面我们开始实现.
项目详细分配.
博主使用的是vs2019就以vs2019为例子搭建顺序表工程.
- 创建一个
SeqList.h顺序表头文件 - 创建一个
SeqList.c顺序表方法文件 - 创建一个
test.c测试文件
解释:
SeqList.h头文件用来创建顺序表,和一些函数方法的声明SeqList.c文件用来实现顺序表函数的定义test.c文件用来测试每次实现一个函数后是否成功
下面我们开始实现各细节
定义顺序表
我们以整型顺序表为例:
struct SeqList
{
int* data; //动态数组.
int size; //数组实际已存储数量
int capacity; //数组真实容量
};
到此为止,顺序表就定义完毕.
但是有一个小问题需要修改,那就是我们在以后如果不再需要整型,就需要去改int,但是不要忘记,以后大家都是要接触各种项目的,在一个项目里面我们用到结构体次数非常多,如果去修改结构体里面的int,那么在后面的程序就会挨个修改int.
有没有很好的办法解决呢? 有,那就是typedef.
修改如下:
typedef int SQDataType;
typedef struct SeqList
{
SQDataType* data;
int size;
int capacity;
}SLT; //给结构体改个短名
这样的话,以后如果不需要int型,我们就可以直接修改typedef定义的int,非常便捷
定义好后,我们该将这段程序放在哪里呢? 没错,上面已经讲解了,我们将它放在
SeqList.h头文件中.
顺序表之初始化方法实现
顺序表定义完成,我们就需要对他初始化.即实现一个初始化函数,前面博主讲解三子棋等游戏项目也做过类似事情
void SeqListInit(SLT ps)
{
ps.a = NULL;
ps.size = ps.capacity = 0;
}
程序定义完毕后,怎样放?
SeqList.h中放程序初始化声明:void SeqListInit(SLT ps);SeqList.c中放上面的函数定义.
进行测试是否成功:
#include "SeqList.h"
int main()
{
SLT plist = { 0 };
SeqListInit(plist);
return 0;
}
我们调试发现,plist根本没有达到我们的要求,那是怎么回事呢?大家细细思考一下~
- 其实这是博主之前在c语言篇中讲解的
函数参数传递问题,这里就涉及到了.因为实参与形参是同类型的 - 就相当于函数内的
ps只是plist的一份临时拷贝,而一个拷贝量的改变会影响plist吗?答案显然,不会 - 那怎么办呢? 这就是我们的指针知识,所以我们需要传递
plist的地址.
修改版本如下:
void SeqListInit(SLT* ps)
{
assert(ps); //一定要断言,因为ps不能是空指针,记得在头文件引<assert.h>
ps->a = NULL;
ps->size = ps->capacity = 0;
}
再测试:
#include "SeqList.h"
int main()
{
SLT plist = { 0 };
SeqListInit(&plist);
return 0;
}
成功!!!!!!!!!!!!
顺序表之打印方法
在SeqList.h文件声明
void SeqListPrint(SLT* ps);
在SeqList.c文件定义
void SeqListPrint(SLT* ps)
{
for(int i = 0;i<ps->size;i++)
{
printf("%d-->",ps->data[i]);
}
printf("\n");
}
顺序表之尾插方法实现
顾名思义,尾插,即在最后面插入.那我们想想怎么实现呢?
-
如果只传递
plist可以插进去吗? 不会! 还是老话,临时拷贝量的改变与实参plist无关,所以需要传递地址 -
还需要传递 需要插入的数据
-
还需要检查顺序表是否还有容量
在SeqList.h文件声明
void SeqListPushBack(SLT* ps,SQDataType elem);
在SeqList.c文件定义
void SeqListPushBack(SLT* ps,SQDataType elem)
{
assert(ps); //ps不可以是空指针
SeqListCheckCapacity(ps);//检查是否需要增容,后续会实现
ps->data[ps->size] = elem; //插进
ps->size++;//实际容量加1
}
顺序表之检查容量方法实现
在SeqList.h文件声明
void SeqListCheckCapacity(ps);
怎么定义这个函数呢? 我们先看他的功能:
- 首先检查是否容量已经装满了
- 满的条件是
ps->size == ps->capacity- 如果满足上述条件,并且
ps->capacity不等于0,说明满了,就增加容量,增加方式是2倍增加- 如果满足上述条件,并且
ps->capacity等于0,说明还是空容量,就增加4个空间
在SeqList.c文件定义
void SeqListCheckCapacity(ps)
{
if(ps->size == ps->capacity)
{
int newcapacity = (ps->capacity) == 0 ? 4:(ps->capacity)*2;
SQDataType* p = (SQDataType*)realloc(ps->data,sizeof(SLT)*newcapacity);
//上面两步是如果capacity为0就给他4个空间
//如果容量不为0,说明空间满了,需要增容,而我们进行2倍增容.
if(p==NULL)
{
perror("错误原因:");
return;
}
ps->data = p;
ps->capacity = newcapacity;
}
}
测试尾插是否成功:
成功!!!!!!
顺序表之头插方法实现
在SeqList.h文件声明
void SeqListPushFront(SLT* ps,SQDataType elem);
头插,即在最前面的地方进行插入,那怎么进行实现呢?
先检查容量,看是否足够
然后挪动数据,给第一个位置空出来
然后在空出来的位置,插进去
在SeqList.c文件定义
void SeqListPushFront(SLT* ps,SQDataType elem)
{
assert(ps);
SeqListCheckCapacity(ps);
for(int i= ps->size;i>0;i--)
{
ps->data[i] = ps->data[i-1];
}
ps->data[0] = elem;
ps->size++;
}
测试头插是否成功:
顺序表之尾删方法实现
在SeqList.h文件声明
void SeqListPopBack(SLT* ps);
尾删,即删除最后一个.
但是怎么算删除呢? 把最后一个置为0吗?恩,肯定不可以.因为如果最后一个本就是0呢
那怎么办??
其实我们就让size减去1就行了.为什么?因为他即使还存在,但是size已经少去1了,即实际存储中已经没有最后一个了,我们看不见他了. 这也是为啥我们的电脑数据可以恢复,因为并没有真正的删除.
在SeqList.c文件定义
void SeqListPopBack(SLT* ps)
{
assert(ps->size > 0); //必须保证有数据可以删除
ps->size--;
}
测试尾删是否成功:
可以看到,当成功录入4个数据后,也成功删除了4个数据,因为最后一个1删除后,打印了一个空行.刚好符合我们定义的打印函数
在删除第五次时候,就报出了错误: size <= 0
所以测试成功!!!!!
顺序表之头删方法实现
在SeqList.h文件声明
void SeqListPopFront(SLT* ps);
头删之前,我们想想尾删是怎么操作的.
嗯,没错,他直接size减1
那么头删呢? 需要把第一个置为什么吗?? 嗯,不需要,直接挨个把数据向前挪进行覆盖,然后size减一
在SeqList.c文件定义
void SeqListPopFront(SLT* ps)
{
assert(ps->size > 0);
for(int i= 0;i<ps->size-1;i++)
{
ps->data[i] = ps->data[i+1];
}
ps->size--;
}
测试头删是否成功:
成功!!!
顺序表之查找元素操作
要求:
- 给一个元素,查找是否在顺序表内,如果在,返回下标.
- 如果不在,返回小于0的数字
在SeqList.h文件声明
int SeqListFind(SLT* ps,SQDataType elem);
在SeqList.c文件定义
int SeqListFind(SLT* ps,SQDataType elem)
{
assert(ps->size > 0);
assert(ps);
for(int i= 0;i<ps->size;i++)
{
if(ps->data[i] == elem)
return i;
}
return -1;
}
测试SeqListFind是否成功:
成功!!!!!
顺序表之任意位置插入
要求:
- 输入指定下标, 想要插入的元素,就在此下标位置插入
- 实现方法: 输入的下标位置及其后,所有数据都往后面挪.
- 然后插入数据,size加1
在SeqList.h文件声明
void SeqListInsert(SLT* ps,size_t index,SQDataType elem);
解释:
size_t是无符号整型
在SeqList.c文件定义
void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
assert(ps);
assert(ps->size >= index); //索引位置必须小于等于size
SeqListCheckCapacity(ps); //看看容量是否足够
for(int i = ps->size;i>index;i--)
{
ps->a[i] = ps->a[i-1];
}
ps->a[index] = elem;
ps->size++;
}
另一种实现版本:
void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
assert(ps);
for(int i = ps->size-1;i>=index;i--)
{
ps->a[i+1] = ps->a[i];
}
ps->size++;
}
**大家想想,这种写法会有什么问题??? **
没错,当这种写法,顺序表为空时候,就会陷入死循环,因为 index是size_t类型,i就会发生整型提升
测试是否成功
成功!!
顺序表之任意位置擦除
怎么操作? 我们想想头删
- 头删就是直接覆盖,然后size-1
在SeqList.h文件声明
void SeqListErease(SLT* ps,size_t index);
在SeqList.c文件定义
void SeqListErease(SLT* ps,size_t index)
{
assert(ps->size > 0);//必须有元素可以删除
for(int i = index;i< ps->size-1;i++)
{
ps->data[i] = ps->data[i+1];
}
ps->size--;
}
测试是否成功:
成功!!
线性表之查看有多少元素
在SeqList.h文件声明
size_t SeqListSize(SLT* ps) ;
在SeqList.c文件定义
size_t SeqListSize(SLT* ps)
{
assert(ps);
return ps->size;
}
测试是否成功:
成功!!!
线性表之修改任意位置
在SeqList.h文件声明
void SeqListAt(SLT* ps, size_t index, SQDataType elem);
在SeqList.c文件定义
void SeqListAt(SLT* ps, size_t index, SQDataType elem)
{
assert(ps);
assert(index < ps->size);
ps->a[index] = elem;
}
测试:
线性表之销毁空间
在SeqList.h文件声明
void SeqListDestroy(SLT* ps);
在SeqList.c文件定义
void SeqListDestroy(SLT* ps)
{
assert(ps);
if(ps->data != NULL)
{
free(ps->data);
ps->data = NULL;
}
ps->size = ps->capacity = 0;
}
测试是否成功:
成功!!!
综合
SeqList.h文件内容
#pragma once
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
typedef int SQDataType;
typedef struct SeqList
{
SQDataType* a;
int size;
int capacity;
}SLT;
//开始增删查改
//初始化操作与销毁空间操作
void SeqListInit(SLT* ps);
void SeqListDestroy(SLT* ps);
void SeqListPrint(SLT* ps);
void SeqListCheckCapacity(SLT* ps); // 增容检查
//增加和删除操作
void SeqListPushBack(SLT* ps,SQDataType elem);
void SeqListPushFront(SLT* ps,SQDataType elem);
void SeqListPopBack(SLT* ps);
void SeqListPopFront(SLT* ps);
//查找操作
int SeqListFind(SLT* ps,SQDataType elem);
//其他部位插入操作
void SeqListInsert(SLT* ps,size_t index,SQDataType elem);
//其他部位删除操作
void SeqListErease(SLT* ps, size_t index);
size_t SeqListSize(SLT* ps);
void SeqListAt(SLT* ps,size_t index,SQDataType elem);
SeqList.c文件内容
#include "SeqList.h"
void SeqListInit(SLT* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SeqListDestroy(SLT* ps)
{
assert(ps);
if (ps->a != NULL)
{
free(ps->a);
ps->a = NULL;
}
ps->size = ps->capacity = 0;
}
void SeqListCheckCapacity(SLT* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //为什么有这一步 ?? 防止给了0
SQDataType* p = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SLT));
if (!p)
{
perror("增容失败原因");
return;
}
ps->a = p;
ps->capacity = newcapacity;
}
}
void SeqListPrint(SLT* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d-->",ps->a[i]);
}
printf("\n");
}
/********************************************** 增加与删除操作 **************************************/
void SeqListPushBack(SLT* ps, SQDataType elem)//尾插
{
//assert(ps);
//SeqListCheckCapacity(ps);
//ps->a[ps->size] = elem;
//ps->size++;
SeqListInsert(ps,ps->size,elem);
}
void SeqListPushFront(SLT* ps, SQDataType elem)//头插
{
//assert(ps);
//SeqListCheckCapacity(ps);
//for (int i = ps->size; i > 0; i--)
//{
// ps->a[i] = ps->a[i - 1];
//}
//ps->a[0] = elem;
//ps->size++;
SeqListInsert(ps, 0, elem);
}
void SeqListPopBack(SLT* ps)//尾删
{
assert(ps->size > 0); //因为如果没有数据,就无法删除了
/*ps->size--;*/
SeqListErease(ps,ps->size-1);
}
void SeqListPopFront(SLT* ps)
{
assert(ps->size > 0); //因为如果没有数据,就无法删除了
//for (int i = 0; i < ps->size-1; i++)
//{
// ps->a[i] = ps->a[i + 1];
//}
//ps->size--;
SeqListErease(ps,0);
}
/*********************************************************************************************************/
int SeqListFind(SLT* ps, SQDataType elem)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
if (ps->a[i] == elem)
return i;
return -1;
}
void SeqListInsert(SLT* ps,size_t index,SQDataType elem)
{
assert(ps);
assert(index <= ps->size);//必须有等号,因为如果插末尾,
SeqListCheckCapacity(ps);
for (int i = ps->size; i > index; i--)
{
ps->a[i] = ps->a[i - 1]; //注意这里哦,这种写法是最好的.比如下面的循环就会出问题
}
/*
for(int i = ps->size-1;i>=index;i--) 这种写法,如果size等于0或者index等于0时,会发现死循环.因为是无符号的
{ 即避免 "有符号" 因为 提升导致变成无符号而异常的大
ps->a[i+1] = ps->a[i];
}
*/
ps->a[index] = elem;
ps->size++;
}
void SeqListErease(SLT* ps,size_t index)
{
assert(ps);
assert(index < ps->size);
for (int i = index; i < ps->size - 1; i++)
{
ps->a[i] = ps->a[i + 1];
}
ps->size--;
}
size_t SeqListSize(SLT* ps) //访问结构体成员最好用函数去访问. 为什么???想想
{
assert(ps);
return ps->size;
}
void SeqListAt(SLT* ps, size_t index, SQDataType elem)
{
assert(ps);
assert(index < ps->size);
ps->a[index] = elem;
}