🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
目录
👉线性表👈
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
👉顺序表👈
概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，不能跳跃存储，一般情况下采用数组存储。在数组上完成数据的增删查改。
分类
顺序表一般可以分为：静态顺序表和动态顺序表。
静态顺序表：使用定长数组存储元素。
对于静态顺序表，应该如何定义呢？见下方代码：
//顺序表的静态存储#defineN10typedefint SLDataType;typedefstructSeqList{
SLDataType a[N];//定长数组int size;//存储数据的个数}SL;
在上方的代码里，采用了
#define
的方式来定义数组的大小并以
typedef int SLDataType
来重命名数组的类型，这么做的目的是方便修改。当另一种情景，数组的长度要要更长或者更短或者数组元素的类型不为
int
，只需要修改
N
的值和
SLDataType
就行了。
我们很容易就可以知道，静态顺序表的缺点：当
N
过小时，无法存储足够多的数据；但
N
过大时，又会造成浪费内存空间的问题。
为了解决静态顺序表的问题，所以就有了动态顺序表。
动态顺序表：使用动态开辟的数组存储
那对于动态顺序表，又该如何去定义呢？见下方代码：
//顺序表的动态存储typedefint SLDataType;typedefstructSeqList{
SLDataType* a;//指向动态开辟的数组int size;//有效数据个数int capacity;//容量空间的大小}SL;
接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致
N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
我们要实现的函数接口有：顺序表初始化、销毁顺序表、打印顺序表、尾插数据、尾删数据、头插数据、头删数据、查找数据、在
pos
位置插入数据、删除
pos
位置的数据以及修改
pos
位置的数据。
我们很容易就知道，当
pos = 0
或者
pos = ps->size
时，在
pos
位置插入数据的函数接口就是头插或者尾插数据的函数接口；当
pos = 0
或者
pos = ps->size -1
时，删除
pos
位置的数据就是头删或者尾删数据的函数接口。
因为需要实现的函数接口很多，写在同一个文件内代码的行数会过长也不利于查看，所以我们将采取模块化的方式来实现动态顺序表。第一个模块是
SeqList.h
头文件，该头文件里面是头文件的包含、类型的重命名、结构体的声明以及函数接口的声明。第二个模块是
SeqList.c
源文件，该源文件里面是函数接口的实现。第三个模块是
test.c
源文件，该源文件里面是测试函数的功能。我们采取
void SeqListTest()
的方式来测试函数的功能，这样方便我们知道该函数接口功能是否是我们所想要的。如果没有达到我们想要的，那也比较容易定位错误、修改
BUG
。
👉SeqList.h👈
#pragmaonce //防止重复包含头文件//#ifndef __SEQLIST_H__//#define __SEQLIST_H__//#endif#include<stdio.h>#include<stdlib.h>#include<assert.h>//顺序表的动态存储typedefint SLDataType;typedefstructSeqList{
SLDataType* a;//指向动态开辟的数组int size;//有效数据个数int capacity;//容量空间的大小}SL;//接口函数的声明//顺序表初始化voidSeqListInit(SL* ps);//销毁顺序表voidSeqListDestory(SL* ps);//打印顺序表voidSeqListPrint(SL* ps);//尾插voidSeqListPushBack(SL* ps, SLDataType x);//尾删voidSeqListPopBack(SL* ps);//头插voidSeqListPushFront(SL* ps, SLDataType x);//头删voidSeqListPopFront(SL* ps);//查找intSeqListFind(SL* ps, SLDataType x);//在pos位置插入xvoidSeqListInsert(SL* ps,size_t pos, SLDataType x);//删除pos位置的值voidSeqListErase(SL* ps,size_t pos);//修改pos位置的值voidSeqListModify(SL* ps,size_t pos, SLDataType x);
为了避免头文件的重复引用，我们可以将需要的头文件放在
SeqList.h
头文件中，并在该文件的最前面加上
#pragma once
或者
#ifndef__SEQLIST_H__#define__SEQLIST_H__#endif
为什么上面的函数接口的参数都是结构体指针呢？因为大多数的函数接口的功能是要修改结构体的数据的，所以只能传结构体指针。如果传结构体的话，形参只是实参的一份临时拷贝，对于形参的修改不会影响实参。而少数的函数接口的参数可以是结构体，比如打印顺序表的函数接口。如果传递一个结构体对象的时候，结构体过大，参数压栈的的系统开销比较大，所以会导致性能的下降。所以，结构体传参的时候，我们应该传结构体指针。
还有需要注意的是，当我们需要对结构体的指针进行解引用操作时，我们首先需要对该指针进行断言或者判空处理，本人强烈推荐断言
assert(ps)
。这样可以帮助我们快速找出错误。
👉SeqList.c👈
SeqList.c
源文件是函数接口的实现，是顺序标准最为重要的一部分。因为函数接口比较多，所以我们写完一个函数接口，就测试一下这个接口的功能是否达到我们的预期。千万不要将全部函数接口实现完，再来测试函数接口的功能。如果出现了错误，我们将会很难找出错误在哪里，大大增加了自己的工作量。
在写函数接口时也要写好相关的注释，为了日后的快速复习。所以一定要写好相关的注释！！！那么现在就看一下函数接口的实现。
#include"SeqList.h"//初始化顺序表voidSeqListInit(SL* ps){assert(ps);
ps->a =NULL;
ps->size = ps->capacity =0;}//销毁顺序表voidSeqListDestory(SL* ps){assert(ps);free(ps->a);//释放动态开辟的空间
ps->a =NULL;
ps->size = ps->capacity =0;}//打印顺序表//传结构体指针voidSeqListPrint(SL* ps){assert(ps);for(int i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");//换行}//传结构体//void SeqListPrint(SL s)//{// // for (int i = 0; i < s.size; i++)// {// printf("%d ",(s.a)[i]);// }// printf("\n");//换行//}//检查容量voidCheckCapacity(SL* ps){assert(ps);if(ps->size == ps->capacity){//ps->capacity = 0时，先给4个空间//ps->capacity != 0时，扩大到原来的两倍int newcapacity = ps->capacity ==0?4: ps->capacity *2;
SLDataType* tmp =(SLDataType*)realloc(ps->a, newcapacity *sizeof(SLDataType));if(tmp ==NULL){perror("realloc fail");exit(-1);//直接结束程序}
ps->a = tmp;
ps->capacity = newcapacity;}}//尾插voidSeqListPushBack(SL* ps, SLDataType x){assert(ps);CheckCapacity(ps);//ps->a[ps->size] = x;//ps->size++;SeqListInsert(ps, ps->size, x);}//尾删voidSeqListPopBack(SL* ps){assert(ps);//温柔的检查//if (ps->size == 0)//{// return;//}//暴力的检查assert(ps->size >0);//检查是否有数据可删//ps->size--;SeqListErase(ps, ps->size -1);}//头插voidSeqListPushFront(SL* ps, SLDataType x){assert(ps);CheckCapacity(ps);//挪动数据//int end = ps->size - 1;//while (end >= 0)//{// ps->a[end + 1] = ps->a[end];// end--;//}//ps->a[0] = x;//ps->size++;SeqListInsert(ps,0, x);}//头删voidSeqListPopFront(SL* ps){assert(ps);assert(ps->size >0);//检查是否有数据可删//int begin = 0;//while (begin < ps->size - 1)//{// ps->a[begin] = ps->a[begin + 1];// begin++;//}//ps->size--;//int begin = 1;//while (begin < ps->size)//{// ps->a[begin - 1] = ps->a[begin];// begin++;//}//--ps->size;SeqListErase(ps,0);}//查找intSeqListFind(SL* ps, SLDataType x){assert(ps);for(int i =0; i < ps->size; i++){if(ps->a[i]== x){return i;//找到了}}return-1;//没找到}//在pos位置插入xvoidSeqListInsert(SL* ps,size_t pos, SLDataType x){assert(ps);assert(pos <= ps->size);CheckCapacity(ps);//挪动数据//int end = ps->size - 1;//while (end >= (int)pos)//{// ps->a[end + 1] = ps->a[end];// end--;//}//ps->a[pos] = x;//ps->size++;size_t end = ps->size;while(end > pos){
ps->a[end]= ps->a[end -1];
end--;}
ps->a[pos]= x;++ps->size;}//删除pos位置的值voidSeqListErase(SL* ps,size_t pos){assert(ps);assert(pos < ps->size);//size_t begin = pos;//while (begin < ps->size - 1)//{// ps->a[begin] = ps->a[begin + 1];// ++begin;//}//ps->size--;size_t begin = pos +1;while(begin < ps->size){
ps->a[begin -1]= ps->a[begin];
begin++;}
ps->size--;}//修改pos位置的数据voidSeqListModify(SL* ps,size_t pos, SLDataType x){assert(ps);assert(pos < ps->size);
ps->a[pos]= x;}
初始化顺序表
1.结构体中的指针
ps->a指向
NULL2.有效数据的个数
ps->size初始化为 0
3.数组的容量ps->capacity初始化为 0
4.注意，初始化还有另一种方式：ps->size初识化为 0、
ps->capacity初始化为
n，
ps->指向一块能存储
n个数据的空间
//初始化顺序表voidSeqListInit(SL* ps){assert(ps);
ps->a =NULL;
ps->size = ps->capacity =0;}
销毁顺序表
1.释放申请的空间
free(ps->a)2.有效数据的个数
ps->size置为 0
3.数据的容量ps->capacity置为 0
//销毁顺序表voidSeqListDestory(SL* ps){assert(ps);free(ps->a);//释放动态开辟的空间
ps->a =NULL;
ps->size = ps->capacity =0;}
打印顺序表
写一个
for或者
while循环打印就好了，打印完数据需要换行。推荐函数接口的参数设为结构体指针。
//打印顺序表voidSeqListPrint(SL* ps){assert(ps);for(int i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");//换行}
检查容量
ps->size == ps->capacity时，ps->capacity == 0；当newcapacity = 4时，ps->capacity != 0newcapacity = ps->capacity * 22.先用
tmp指针
realloc的空间。如果
tmp为
NULL，输出错误并直接结束程序。如果
tmp不为
NULL，
ps->a = tmp和
ps->capacity = newcapacity
扩容和缩容的说明
当进行插入数据时，数组的空间不足，我们需要进行扩容操作。在这里，我们选择了比较合适的扩容倍数 2，因为扩容 2 倍比较适中，并不会扩容过大也不会过小。使用
realloc
函数扩容有两种情况：第一种是原地扩容，返回原来的地址；第二种是异地扩容，先将数组的数据拷贝到新空间，释放原来的空间，最后返回新空间的起始地址。
对于
realloc
函数还需要注意两个点：第一，当
realloc
函数的第一个参数为
NULL
时，此时的
realloc
函数相当于
malloc
函数；第二，如果申请空间失败，将返回一个空指针，并且参数
ptr
所指向的内存块不会被释放(它仍然有效，且其内容不变)。
当进行删除数据时，我们是否需要进行缩容操作呢？答案是不用。如果进行缩容操作的话，将会影响性能。因为使用
realloc
函数调整空间的大小是需要消耗时间的。缩容是有可能会异地缩容的，这样缩容的话，就要将之前的数据拷贝到新空间，再将旧空间释放掉。同时删除数据并缩容之后，也有可能再插入数据，这时候又要
realloc
调整空间大小，所以缩容是非常没有必要的。不缩容也是一种以空间换取时间的操作，以空间换取时间是非常必要的，因为现在的计算机不再那么的缺少空间了。
//检查容量voidCheckCapacity(SL* ps){assert(ps);if(ps->size == ps->capacity){//ps->capacity = 0时，先给4个空间//ps->capacity != 0时，扩大到原来的两倍int newcapacity = ps->capacity ==0?4: ps->capacity *2;
SLDataType* tmp =(SLDataType*)realloc(ps->a, newcapacity *sizeof(SLDataType));if(tmp ==NULL){perror("realloc fail");exit(-1);//直接结束程序}
ps->a = tmp;
ps->capacity = newcapacity;}}
尾插数据
1.检查容量
2.插入数据ps->a[ps->size] = x和
ps->size++，也可以调用在
pos位置插入数据的函数
SeqListInsert(ps, ps->size, x)
//尾插voidSeqListPushBack(SL* ps, SLDataType x){assert(ps);CheckCapacity(ps);//检查容量//ps->a[ps->size] = x;//ps->size++;SeqListInsert(ps, ps->size, x);}
尾删数据
1.检查是否有数据可删，推荐暴力的检查
2.尾删数据，ps->size--或者调用函数
SeqListErase(ps, ps->size - 1)即可，不需要缩容
//尾删voidSeqListPopBack(SL* ps){//assert(ps);//温柔的检查//if (ps->size == 0)//{// return;//}//暴力的检查//assert(ps->size > 0);//检查是否有数据可删//ps->size--;SeqListErase(ps, ps->size -1);}
头插数据
1.检查容量
2.挪动数据、插入数据、有效数据个数加一ps->size++或者直接调用函数
SeqListInsert(ps, 0, x)
//头插voidSeqListPushFront(SL* ps, SLDataType x){assert(ps);CheckCapacity(ps);//挪动数据//int end = ps->size - 1;//while (end >= 0)//{// ps->a[end + 1] = ps->a[end];// end--;//}//ps->a[0] = x;//ps->size++;SeqListInsert(ps,0, x);}
头删数据
1.检查是否有数据可删
2.挪动数据覆盖，有效数据个数减一或者直接调用函数SeqListErase(ps, 0)
//头删voidSeqListPopFront(SL* ps){//assert(ps);//assert(ps->size > 0);//检查是否有数据可删//int begin = 0;//while (begin < ps->size - 1)//{// ps->a[begin] = ps->a[begin + 1];// begin++;//}//ps->size--;//int begin = 1;//while (begin < ps->size)//{// ps->a[begin - 1] = ps->a[begin];// begin++;//}//--ps->size;SeqListErase(ps,0);}
查找数据
利用
for循环或者
while循环查找
x，如果找到了就返回下标
i，没找到就返回 -1。
//查找intSeqListFind(SL* ps, SLDataType x){assert(ps);for(int i =0; i < ps->size; i++){if(ps->a[i]== x){return i;//找到了}}return-1;//没找到}
**在
pos
位置插入数据**
1.检查
pos是否合法
2.检查容量
3.挪动数据，插入数据，有效数据个数加一（有两种方式，个人推荐第二种）
如果某个操作符的各个操作数属于不同的类型，那么除非其中一个操作数的转换为另一个操作数的类型，否则操作就无法进行。下面的层次体系称为寻常算术转换。
longdoubledoublefloatunsignedlongint//当这些类型的数据进行比较时，处于下面的类型要向处于上面的乐行转换longintunsignedintint
//在pos位置插入xvoidSeqListInsert(SL* ps,size_t pos, SLDataType x){assert(ps);assert(pos <= ps->size);//检查参数pos是否合法CheckCapacity(ps);//挪动数据//int与size_t比较时，int的数据会隐式转换成size_t//int end = ps->size - 1;//while (end >= (int)pos)//{// ps->a[end + 1] = ps->a[end];// end--;//}//ps->a[pos] = x;//ps->size++;size_t end = ps->size;while(end > pos){
ps->a[end]= ps->a[end -1];
end--;}
ps->a[pos]= x;++ps->size;}
**删除
pos
位置的数据**
1.检查
pos是否合法
2.挪动数据覆盖，有效数据个数减一
//删除pos位置的值voidSeqListErase(SL* ps,size_t pos){assert(ps);assert(pos < ps->size);//检查pos是否合法//size_t begin = pos;//while (begin < ps->size - 1)//{// ps->a[begin] = ps->a[begin + 1];// ++begin;//}//ps->size--;size_t begin = pos +1;while(begin < ps->size){
ps->a[begin -1]= ps->a[begin];
begin++;}
ps->size--;}
**修改
pos
位置的数据**
1.检查
pos是否合法
2.直接修改pos位置的数据
//修改pos位置的数据voidSeqListModify(SL* ps,size_t pos, SLDataType x){assert(ps);assert(pos < ps->size);//检查pos是否合法
ps->a[pos]= x;}
👉test.c👈
test.c
源文件里主要是测试函数接口的功能，我们应该写完一个函数接口，就举一些例子来测试一下，方便看函数的功能是否达到我们的预期。如果没有，也方便我们找出错误。
将全部函数接口实现完并测试完后，可以写一个菜单来玩一玩。其实写菜单并不是很重要，也不会很难，重要的是掌握模块化的思想和掌握各个函数接口的实现。在这里，博主也给大家写了个菜单参考一下。大家可以根据这个菜单，来验证函数接口实现是否正确。
#include"SeqList.h"//测试尾插、头插、打印顺序表voidSeqListTest1(){
SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPushFront(&sl,1);SeqListPushFront(&sl,2);SeqListPushFront(&sl,3);SeqListPushFront(&sl,4);SeqListPushFront(&sl,5);SeqListPrint(&sl);SeqListDestory(&sl);}//测试尾删、头删voidSeqListTest2(){
SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPrint(&sl);//1 2 3 4 5SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);//1 2 3SeqListPushFront(&sl,1);SeqListPushFront(&sl,2);SeqListPushFront(&sl,3);SeqListPushFront(&sl,4);SeqListPushFront(&sl,5);SeqListPrint(&sl);//5 4 3 2 1 1 2 3SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);//3 2 1 1 2 3SeqListDestory(&sl);}//测试pos位置插入voidSeqListTest3(){
SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPrint(&sl);//1 2 3 4SeqListInsert(&sl,4,40);SeqListPrint(&sl);//1 2 3 4 40SeqListInsert(&sl,0,10);SeqListPrint(&sl);//10 1 2 3 4 40int x =3;int pos =SeqListFind(&sl, x);if(pos !=-1){SeqListInsert(&sl, pos,30);SeqListPrint(&sl);//10 1 2 30 3 4 40}SeqListDestory(&sl);}//测试pos位置删除voidSeqListTest4(){
SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPrint(&sl);//1 2 3 4SeqListErase(&sl,3);SeqListPrint(&sl);//1 2 3SeqListErase(&sl,0);SeqListPrint(&sl);//2 3int x =3;int pos =SeqListFind(&sl, x);if(pos !=-1){SeqListErase(&sl, pos);SeqListPrint(&sl);//2}SeqListDestory(&sl);}//测试pos位置修改voidSeqListTest5(){
SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPrint(&sl);//1 2 3 4int x =3;int pos =SeqListFind(&sl, x);if(pos !=-1){SeqListModify(&sl, pos,30);SeqListPrint(&sl);//1 2 30 4}SeqListDestory(&sl);}//菜单voidmenu(){printf("****************************\n");printf("***1.尾插数据 2.尾删数据***\n");printf("***3.头插数据 4.头删数据***\n");printf("***5.查找数据 6.插入数据***\n");printf("***7.删除数据 8.修改数据***\n");printf("***9.打印数据 0.退出 ***\n");printf("****************************\n\n");}voidTest(){
SL sl;SeqListInit(&sl);int input =0;int x =0;int pos =0;do{menu();printf("请选择:>");scanf("%d",&input);switch(input){case1:printf("请输入你要尾插的数据，以-1结束\n");scanf("%d",&x);while(x !=-1){SeqListPushBack(&sl, x);scanf("%d",&x);}break;case2:SeqListPopBack(&sl);break;case3:printf("请输入你要头插的数据，以-1结束\n");scanf("%d",&x);while(x !=-1){SeqListPushFront(&sl, x);scanf("%d",&x);}break;case4:SeqListPopFront(&sl);break;case5:printf("请输入你要查找的数据:>");scanf("%d",&x);
pos =SeqListFind(&sl, x);if(pos ==-1){printf("顺序表中没有%d该数据\n", x);}else{printf("你要查找的数据的下标是%d\n", pos);}break;case6:printf("请输入要插入的数据:>");scanf("%d",&x);printf("请输入一个位置:>");scanf("%d",&pos);SeqListInsert(&sl, pos, x);break;case7:printf("请输入一个位置:>");scanf("%d",&pos);SeqListErase(&sl, pos);break;case8:printf("请输入要修改的数据:>");scanf("%d",&x);printf("请输入一个位置:>");scanf("%d",&pos);SeqListModify(&sl, pos, x);break;case9:SeqListPrint(&sl);break;case0:break;default:printf("选择错误，请重新选择:>\n");break;}}while(input);SeqListDestory(&sl);}intmain(){//SeqListTest1();//SeqListTest2();//SeqListTest3();//SeqListTest4();//SeqListTest5();Test();}
👉总结👈
其实顺序表主要就是C语言的综合的应用，其实也并没有那么地难，重点是要学会函数接口是怎么实现的。以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！💖💝❣️
版权归原作者 阿亮joy. 所有， 如有侵权，请联系我们删除。