一篇博客读懂顺序表 —— Sequence-List

目录

一、顺序表的初始定义

1.1新建头文件和源文件

1.2 SeqList.h 中的准备工作

二、顺序表的初始化与销毁

三、首尾插入元素

四、首尾删除元素

五、中间插入元素

六、中间删除元素

 七、查找指定元素下标

八、源代码

---

一、顺序表的初始定义

1.1新建头文件和源文件

当我们要实现通讯录时，我们会自定义一个 contact.h 文件来存储我们的各种声明，自定义一个 contact.c 文件来存储实现声明的函数，同时还会存在一个 test.c 来测试我们代码的可行性。

在这里我们学习顺序表时，也要使用这种方式，来分割我们的代码使程序更加简洁耐看：

在 SeqList.h 中，我们要声明我们需要的头文件、重新定义的类型、我们需要的函数...... 

1.2 SeqList.h 中的准备工作

为了方便我们修改顺序表中的数据类型，我们把我们顺序表中的类型(int为例)重定义为SLDataType，这样如果我们以后想修改数据类型的话，可以直接来此处将 int 改为 double......

typedef int SLDataType;

 其次，我们定义的顺序表其实是一个结构体，其包含了一个表头(一个指针)，实际保存的数据以及表的容量，这里我们并把结构体名称重定义为简称，方便后续的使用。

typedef struct SeqList
{int* p;//表头int size;//实际存储的数据数量int capacity;//此时表中的容量
}SL;

我们的顺序表要具有哪些特点呢？

1.动态存储，可以动态开辟使用空间

2.各种位置的增删查改，分为头、尾、中间。 

二、顺序表的初始化与销毁

初始化和销毁：

首先用断言来保证传入的指针不为空，其次我们需要用 SLInit 函数来将结构体中的数据一一赋初值，其次在销毁数据时，也要保证 free 函数的对象为非空指针，接着将数据重新初始化。

void SLInit(SL* psl) //初始化顺序表
{assert(psl != NULL);psl->p = NULL;psl->size = 0;psl->capacity = 0;
}
void SLDestroy(SL* psl) //销毁顺序表
{assert(psl != NULL);if (psl->p != NULL){free(psl->p);psl->size = 0;psl->capacity = 0;}
}

因为我们的顺序表是动态开辟空间，所以写一个检查实时容量的函数是必备的，在此处我们使用二倍扩容的方法来开辟内存空间，但是在初始化时我们把我们的 capacity 赋值为 0，在进行二倍扩容时还是 0，这时就可以用三目运算符完美规避这个问题。

检查并扩充容量：

并且我们用新的临时变量来保存扩容后的空间，在没有问题后再把值返回给原本的变量。

void SLCheckCapacity(SL* psl)
{assert(psl != NULL);if (psl->size == psl->capacity){//因为初始化时capacity为0，所以我们按照二倍扩容后也是0，这里运用三目运算符就能很好的解决SLDataType NewCapacity = (psl->capacity == 0) ? 4 : psl->capacity * 2;//动态开辟的空间是给顺序表的，注意不要把改行上下两个数据颠倒//sizeof() 不要忘！！SLDataType* tmp = (SLDataType*)realloc(psl->p, sizeof(SL) * NewCapacity);if (tmp == NULL){perror("SLCheckCapacity -> realloc");return;}psl->capacity = NewCapacity;psl->p = tmp;}
}

三、首尾插入元素

打印顺序表：

 为了更好的测试我们的代码，我们可以先写一个打印函数来打印我们的顺序表。

void SLPrint(SL* psl)
{assert(psl != NULL);int i = 0;for (; i < psl->size; i++){printf("%d ", psl->p[i]);}printf("\n");
}

尾部插入元素：

void SLPushBack(SL* psl, SLDataType x)
{assert(psl != NULL);SLCheckCapacity(psl);//检查是否需要扩容psl->p[psl->size] = x;psl->size++;
}

首部插入元素：

首部插入元素就比尾部插入元素复杂一点啦，我们需要让前面的元素覆盖后面的元素，下图我们模拟顺序表中有 8 个元素(size == 8)，来看一下我们的代码应该如何写：

我们让 i 从后面开始向前走，才能保证有用的元素不会被覆盖，同时我们根据首尾元素的覆盖下标推理出 i 的取值范围。

//第一种取值
void SLPushFront(SL* psl, SLDataType x)
{assert(psl != NULL);SLCheckCapacity(psl);int i = psl->size;for (; i > 0; i--){psl->p[i] = psl->p[i - 1];}psl->p[0] = x;psl->size++;
}//第二种取值
void SLPushFront(SL* ps, SLDateType x)//ʱ临Ӷ O(n) ;  n O(n^2)
{assert(ps != NULL);SLCheckCapacity(ps);int i = ps->size - 1;for (; i >= 0; i--){ps->p[i + 1] = ps->p[i];}ps->p[0] = x;ps->size++;
}

四、首尾删除元素

尾部删除元素：

这里我们采用 size-- 的方法，让我们直接无法访问到最后一个元素，下一次增添时又会被新的元素覆盖以实现删除的操作，同时断言我们的实际元素个数必须多余 0

void SLPopBack(SL* psl)
{assert(psl != NULL);assert(psl->size > 0);psl->size--;
}

首部删除元素： 

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

五、中间插入元素

void SLInsert(SL* psl, int num, SLDataType x)
{assert(psl != NULL);assert(num >= 0 && num <= psl->size);SLCheckCapacity(psl);int i = psl->size - 1;for (; i >= num; i--){psl->p[i + 1] = psl->p[i];}psl->p[num] = x;psl->size++;
}

六、中间删除元素

void SLErase(SL* psl, int num)
{assert(psl != NULL);assert(num >= 0 && num < psl->size);SLCheckCapacity(psl);int i = num;for (; i < psl->size - 1; i++){psl->p[i] = psl->p[i + 1];}psl->size--;
}

 七、查找指定元素下标

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

八、源代码

欢迎光临我的Gitee - Gitee.comhttps://gitee.com/bright-and-sparkling-at-night/studying/commit/dd1f9978f81f9decce01805623b4708b7671f3e0