数据结构之旅(顺序表)

前言:  

         Hello,各位小伙伴们我们在过去的60天里学完了C语言基本语法,由于小编在准备数学竞赛,最近没有给大家更新,并且没有及时回复大家的私信,小编在这里和大家说一声对不起!,小编这几天会及时给大家更新初阶数据结构的内容,然后我们来学习今天的内容吧!

一. 顺序表的概念和结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

结构:顺序表的底层结构式数组,对数组的封装，实现了常用的增删改查等接口。

二.顺序表分类

顺序表分为静态顺序表和动态顺序表:

1>静态顺序表:即数组大小是固定的

...
struct Seqlist
{int arr[1000];//定长数组int size;//有效数组个数
}SL;

2>动态顺序表:即数组大小不是固定的

...
struct Seqlist
{int *arr;int size;//有效数据的个数int capacity;//数组的容量
};

相比于静态顺序表,动态顺序表的优点:既不会因为空间内存不够而造成栈溢出,也不会因为数组容量很大而有效数字较少而造成空间的浪费!

三.动态顺序表的实现

动态顺序表的实现我们分为9个模块,初始化,尾插,头插,尾删,头删,顺序表的查找,插入指定位置的数据,删除指定位置的数据,顺序表的销毁!

在写代码之前我们创建3个文件:一个.h文件,两个.c文件其中的.h文件为seqlist.h用来包含顺序表的框架已经一些函数的声明,其中seqlist.c文件用来实现函数的定义test.c用来不断测试代码的正确性

在进行顺序表实现之前我们首先来对代码简化一下,因为后面要多次使用结构体变量,我们使用typedef来重定义一下.

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* arr;int size;int capacity;
}SL;
//初始化
void SLInit(SL* ps);

1>顺序表的初始化

在.h文件中进行函数的声明,在seqlist.c中进行函数的定义

#include"seqlist.h"
void SLInit(SL* ps)
{ps->arr = NULL;ps->capacity = ps->size = 0;
}

同时小编在这里提醒大家一下在进行初始化的时候记得要进行结构体指针传递,否则只会改变形参而不会改变实参在这里小编给大家演示一下传递结构体值变量的时候:而如果传递的结构体的指变量则会同时改变实参和形参!我们在test.c文件中进行调试一下

我们看到此时实参和形参都发生了变化!

2>顺序表的尾插操作

顺序表的尾插操作大致分为两钟情况：空间足够与空间不够的情况

空间足够的情况下：

在空间足够的情况下，在有效数字的后面直接插入数字即可，可以发现有效数字的个数size做为下标的时候可直接进行插入！

空间不够的情况下：

在空间不够的情况下可以下size和capacity的值相等，要想进行数字的插入需要进行扩容操作！我们使用realloc函数来进行扩容。同时在扩容是要等倍扩容，这样会尽量减少空间的浪费！

void SLPushBack(SL* ps, SLDatatype x)
{assert(ps);//空间不够if (ps->capacity == ps->size){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity *sizeof(SLDatatype));if (tmp == NULL){perror("realloc!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->size++] = x;
}

 可以看出时间复杂度为O(1)。

同时我们在test.c文件中进行测试：

 3>顺序表的头插操作

我们在进行顺序表的头插操作时，需要先将原来数组的内容整体向后移动一位，然后再将要插入的数据插入到第一个位置中去。同时我们将判断空间大小是否充足代码包装成一个函数

void CheckCapacity(ps)这样就可以使代码简洁。

代码实现：

void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);void CheckCapacity(ps);//判断是否有足够的空间for (int i = ps->size; i > 0; i++){ps->arr[i] = ps->arr[i - 1];}//向后面整体移动一位ps->arr[0] = x;++ps->size;
}

 可以看出时间复杂度为O(n)。

4>顺序表的尾删操作

进行尾删操作时，将有效数字的个数减一，同时在判断有效数字个数不能为0。

void SLPopBack(SL* ps)
{assert(ps&&ps->size);--ps->size;
}

5>顺序表的头删操作

在进行头删操作时，我们只需要将数组内容整体向前移动一位即可！但在移动时我们要注意要从前向后移动。

void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

 6>顺序表的查找操作

我们遍历整个数组，找到后返回下标，如果没有找到则返回-1，然后在test.c文件中进行测试

int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}return -1;
}

测试：

7>在指定位置插入数据

 在指定位置插入数据，我们需要先将该位置之后的数据向后移动一位同时还要判断是否空间足够，然后在该位置插入数据。

void SLInsert(SL* ps, int pos, SLDatatype x)
{                  assert(ps);assert(pos >= 0 && pos <= ps->size);//取等号的时候就是在进行头插与尾插CheckCapacity(ps);for (int i = ps->size;i>pos;i--){ps->arr[i] = ps->arr[i - 1];}++ps->size;ps->arr[pos] = x;
}

测试：

8>删除指定位置的数据

删除指定位置的数据，即将该位置之后的数据向前移动一位，最后不要忘记将有效数据的个数减一。

void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);for (int i = pos; i <ps->size; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

测试：

8>顺序表的销毁

我们在开辟新的空间的时候使用了malloc函数，在使用完成之后要记得将所开辟的空间还给操作系统。

void SLDestory(SL* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->size = 0;
}

测试：

四.完成顺序表所需要注意的事项(总结)

在整体规划部分，动态顺序表的实现过程中我们创建了3个文件与平常不同的是多出来一个test.c测试文件，因为我们要完成许多函数的功能所以创建这个函数目的在于不断测试，在上面我们在书写代码的过程中不断进行函数的测试，同时我们将所有函数的声明都存在了头文件中，在函数定义的文件中我们只需要包含我们创建的这个头文件即可！

在函数实现部分，我们充分考虑到了函数传参问题，将所有可能的情况包含到了其中，尤其传递的指针为空的情况还有值传递于址传递问题。同时将重复的代码部分另外包装成一个新的函数，减少了代码行数。同时在搞不清逻辑关系的时候我们要记得画图！

ok,今天的内容就到这里啦，我们下期再见！ 欢迎各位小伙伴在评论区留言。