主页：114514的代码大冒险

qq:2188956112（欢迎小伙伴呀hi✿(。◕ᴗ◕。)✿ ）

Gitee：庄嘉豪 (zhuang-jiahaoxxx) - Gitee.com

前言

数据结构是一种计算机科学技术领域广泛使用的专业术语，在很多书籍以及博客中，对数据结构的解释为数据在计算机的存储方式，很容易让人误以为数据结构只是一种数据的物理存储方式，其实不然，数据结构可以理解为：数据 + 结构。数据是描述客观事物的符号，为程序操控，存储在计算机上，结构包括数据的逻辑结构和存储结构。

因此足以见得数据结构在计算机领域的重要作用。

---

 

一、顺序表是什么？

区别于链表，顺序表支持随机访问，从而支持二分查找，冒泡排序等需按下标进行访问的算法

顺序表其实就是数组，本文将主要介绍顺序表的增删查改操作

二、项目功能的逐一实现（基本）

1. 准备工作

我们按照三子棋和通讯录的标准工程旧历，创立三个文件 SeqList.c(实现各种功能接口（函数）)  SeqList.h（存放此次需要的头文件以及函数声明） test.c（调用函数，测试功能是否正常）。

 另外还要介绍一下顺序表的组成：

 

2.打印（SeqListPrint）和初始化（SeqListInit）

SeqList.h：

 SeqList.h：

void SeqListPrint(SL* ps)
{for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}

void SeqListInit(SL* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;}

test.c：

因为会涉及多次测试，所以我们将测试函数分成多个：

 

 

 为什么使用这么长的命名?
因为这和c++的stl库相关联，方便日后学习c++。

1.头插（对顺序表首部进行内容的增加）

代码：

void SeqListPushFront(SL* ps, SLDataType x)
{SeqListCheckCapacity(ps);//扩容函数，在插入内容之前进行容量的检查//避免出现访问错误int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}

思想：将最后一个元素后移，然后倒数第二个数移到倒数第一个数，以此类推，全部移动之后，

将要添加的值放在头一个位置上：
 

2.头删（对顺序表首部进行内容的删除）

代码：

void SeqListPopFront(SL* ps)
{assert(ps->size > 0);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}

思想：就是将第二个位置上的数字放在第一个位置上，第三个位置上的数字放在第二个位置上，以此类推  全部移动之后，再将记录数据个数的size进行-1操作；

3.尾插（对顺序表尾部进行内容的增加）

代码：

void SeqListPushBack(SL* ps, SLDataType x)
{SeqListCheckCapacity(ps);//检查顺序表容量，容量不足进行扩容ps->a[ps->size] = x;ps->size++;
}

思想：在已有数据的末尾位置放置一个新数据。

4.尾删（对顺序表尾部进行内容的删除）

代码：

void SeqlistPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;}

注意：
一定在进行删除之前，检查数据现存个数，避免出现非法访问，

这里如果你不检查，可能当时编译器不会报错，但是，在释放内存时，就会出现问题

5.内容扩增：

代码：

void SeqListCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}}

为什么进行内容扩增？

 扩容为什么一次扩容增加为之前的二倍？

因为一次扩容扩多了，空间浪费；扩少了，需多次进行扩容操作。

二倍则是一个比较友好的扩容选择。

注意：这里的扩容，有可能要扩大的容量本身为0；而0*2 = 0,所以我们选择进行一个判断

如果为0，我们就将容量扩大到4；如果不为零，我们就按照扩为二倍处理

6.销毁顺序表（动态内存的释放）

代码：

void SeqListDestory(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

三，补充功能（调整）

1.随机插入（对指定位置增加内容）

代码：

void SeqListInsert(SL* ps, int pos, SLDataType x)
{// 温柔的处理方式/*if (pos > ps->size || pos < 0){printf("pos invalid\n");return;}*///比较粗暴的方式assert(pos >= 0 && ps->size);SeqListCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

思想：

以插入位置2举例：

 

注意：

这里要对插入位置pos进行检查（检查方法分为if语句与assert语句），避免非法访问

---

于是便有了对头插，尾插的改动：
 

SeqListInsert(ps, ps->size, x);//尾插

 

SeqListInsert(ps, 0, x);//尾插

2.随机删除（对指定内容进行删除）

删除之前，要找到目标数据的下标：
 

int SeqListFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

然后就是正题：

void SeqListErase(SL* ps, int pos)
{assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}

---

于是便有了对头删，尾删的改动

SeqListErase(ps, 0);//头删

SeqListErase(ps, ps->size - 1);//尾删

总结

这就是本次全部内容了，顺序表是在数据结构中打的第一枪，虽然在整个数据结构的学习中并不算难，但是依然要认真起来，加油O(∩_∩)O哈哈~