文章目录
前言
顺序表是一种数据结构，在介绍顺序表之前我们需要知道什么是数据结构，在生活中不借助排队的方式来管理客呼，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等 情况。同理，程序中如果不对数据进行管理，可能会导致数据丢失、操作数据困难、野指针等情况。 通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的方式任意对数据进行增删改查等操作。
一、什么是数据结构
数据结构是由“数据”和“结构”两词组合而来。
什么是数据？常见的数值1、2、3、4.....、教务系统里保存的用户信息（姓名、性别、年龄、学历等 等）、网页里肉眼可以看到的信息（文字、图片、视频等等），这些都是数据。
什么是结构？当我们想要使用⼤量使用同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性非常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的方式。
概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。
最基础的数据结构：数组。
有了数组为什么还要学习其他数据结构？
假设有10个空间，已经使用了5个，向数组中插入数据步骤： 求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据（注意：这里是否要判断数组是否满了，满了还能继续插入吗）.....
假设数据量非常庞大，频繁的获取数组有效数据个数会影响程序执行效率。
结论：最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。
二、顺序表
1.顺序表的概念和结构
1.1线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的⼀类数据结构的集合 如何理解逻辑结构和物理结构？
2.顺序表的分类
顺序表和数组的区别：
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口。
顺序表的分类：
2.1.静态顺序表
静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费
2.2.动态顺序表
静态不方便我们就换成另一个可以随时改变的动态顺序表，因为数组再内存中是连续存放的，我们可以使用动态内存管理来开辟几块连续的空间，我们只需要指向这块空间的指针即可。
由于动态顺序表我们未知申请了多少空间，所以需要记录申请空间容量。 
上图就是动态的顺序表，数组在内存中是连续存放的，使用我们同过指针操作就可以访问连续的空间。动态顺序表中的指针a就可以使用malloc开辟一块连续的空间。
我们需要多少就可以开辟多少，不够可以扩充。因此叫做动态顺序表。
3.顺序表的接口
顺序表中我们要实现增删查改。增就是插入数据，但是要注意从何插入数据，删除也要注意删除何处的数据。下面我们给出要实现的接口。
//SList.h #include <stdio.h> #include <stdlib.h> //静态顺序表 typedef int SLDataType; //#define N 7 //typedef struct SeqList { // SLDataType a[N]; //定长数组 // int size; //有效数据个数 //}SL;//动态顺序表 typedef struct SeqList {SLDataType* a; //指针int size; //有效数据个数int capacity; //容量 }SL;//打印 void SLPrint(SL* ps); //初始化 void SLInit(SL* ps); //销毁 void SLDestory(SL* ps);//头插和尾插 void SLPushFront(SL* ps, SLDataType x); void SLPushBack(SL* ps, SLDataType x);//头删和尾删 void SLPopFront(SL* ps); void SLPopBack(SL* ps);//指定位置之前和之后插入 void SLPushInsertFront(SL* ps, int pos, SLDataType x); void SLPushInsertBack(SL* ps, int pos, SLDataType x);//删除指定位置 void SLErase(SL* ps, int pos);//查找 int SLFind(SL* ps, SLDataType x);//修改 void SLChange(SL* ps, int pos, SLDataType x);
4.顺序表的实现
4.1 初始化顺序表
初始条件可以由用户自己决定,这里初始化为空:
//SList.c中#include "SList.h"//初始化顺序表
void SLInit(SL* ps)
{if (ps == NULL) { return;}
//使用assert(ps)可以直接终止程序，需要头文件<assert.h>ps->a = NULL;ps->size = 0;ps->capacity = 0;
}//void SLInit(SL s);是传值传参，不会修改主函数中的s 写一步测试一步是避免和排除错误的最好前提:
注意不能将s1直接传过去，否则不能初始化成功。需要取得s1的地址。
4.2 顺序表的插入
顺序表的插入分为头插入和尾插入:
尾插入:
尾插仅仅需要注意空间是否足够：
1.空间capacity足够：直接插入到size位置:
2.空间capacity不足够:先扩容，在插入到size位置。
C语言中没有对一个数组直接进行扩容，而是重新开辟一块空间先扩容，再将旧空间的数据拷贝到新空间，然后在进行插入操作。
而realloc可以完美解决原空间的拷贝。
所以在插入之前我们得先检查空间是否足够，不足够需要进行扩容再插入：
//SList.c中//采用声明和定义分离#include "SList.h"//扩容
void Change_Capacity(SL* ps)
{//如果有原数据，先拷贝转移,如果没有则直接进行扩容//reclloc实际上已经具备转移资源的功能,所以我们不需要而外进行判断//注意初始时，capacity为0int newcapacity = ps->capacity == 0 ? 4 : 2* ps->capacity;//注意是否申请失败SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));if (tmp == NULL){perror("realloc fail！");exit(1);}ps->a = tmp;ps->capacity = newcapacity;
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{//不能传空指针if (ps == NULL) return;//空间是否足够//不足够if (ps->capacity == ps->size){//扩容Change_Capacity(ps);}//足够,直接进行插入ps->a[ps->size++] = x;}为了方便查看将打印也写出来：
void SLPrint(SL* ps)
{if (ps == NULL) return;for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}测试:
void test02()
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);SLPushBack(&s1, 6);SLPrint(&s1);
}
头插入:
//头插
void SLPushFront(SL* ps,SLDataType x)
{if (ps == NULL) return;//头插也需要考虑空间是否足够if (ps->size == ps->capacity){Change_Capacity(ps);}//将数据后移一位，从最后移，避免数据被覆盖//注意移动时count - 1是否超出数组范围int count = ps->size;while (count > 0){ps->a[count] = ps->a[count - 1];count--;}//空出首位ps->a[0] = x;ps->size++;
}测试：
void test03()
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushFront(&s1, 5);SLPushFront(&s1, 6);SLPrint(&s1);
}
4.3 头删尾删
顺序表的删除就不需要考虑空间是否足够了，而是考虑有效数据个数。
尾删很简单，直接将 ps->size--,当然不能为负数。
头删则需要将后面的数据往前移:
从前往后移可以避免数据被覆盖。
//头删和尾删
void SLPopFront(SL* ps)
{if (ps == NULL)return;if (ps->size == 0) return;int count = 0;//注意 count+ 1的位置while (count < ps->size - 1){ps->a[count] = ps->a[count + 1];count++;}ps->size--;
}
void SLPopBack(SL* ps)
{if (ps == NULL) return;if (ps->size > 0)ps->size--;elsereturn;
}
测试:
void test04() //尾删
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);SLPushBack(&s1, 6);SLPrint(&s1);SLPopBack(&s1);SLPopBack(&s1);SLPopBack(&s1);SLPrint(&s1);SLPopBack(&s1);SLPopBack(&s1);SLPopBack(&s1);SLPrint(&s1);
}void test05() //头删
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPushBack(&s1, 5);SLPushBack(&s1, 6);SLPrint(&s1);SLPopFront(&s1);SLPopFront(&s1);SLPopFront(&s1);SLPrint(&s1);SLPopFront(&s1);SLPopFront(&s1);SLPopFront(&s1);SLPrint(&s1);
}4.4 指定位置插入
指定位置之前:
将pos位置的数据以及之后的数据往后移，同样从最后开始移动，以免覆盖数据。（注意位置遵从下标从0开始ps->a[0]表示第一个）
代码：
//指定位置之前和之后插入
void SLPushInsertFront(SL* ps, int pos, SLDataType x)
{if (ps == NULL) return;if (pos >= ps->size && pos < 0) return;if (ps->size == ps->capacity){Change_Capacity(ps);}//将该位置数据以及后面的数据往后移int count = ps->size;while (count > pos){ps->a[count] = ps->a[count - 1];count--;}ps->a[pos] = x;ps->size++;
}测试:
void test06()
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPrint(&s1);SLPushInsertFront(&s1, 1, 7);SLPrint(&s1);}指定位置之后插入：
void SLPushInsertBack(SL* ps, int pos, SLDataType x)
{if (ps == NULL) return;if (pos >= ps->size && pos < 0) return;if (ps->size == ps->capacity){Change_Capacity(ps);}//将该位置之后的数据往后移int count = ps->size;while (count > pos + 1){ps->a[count] = ps->a[count - 1];count--;}ps->a[pos+1] = x;ps->size++;
}4.4 删除指定位置
//删除指定位置
void SLErase(SL* ps, int pos)
{if (ps == NULL) return;if (pos >= ps->size && pos < 0) return;//将pos位置之后的数据往前移int count = pos;while (count < ps->size - 1){ps->a[count] = ps->a[count + 1];count++;}ps->size--;
}
void test08()
{SL s1;SLInit(&s1);SLPushBack(&s1, 1);SLPushBack(&s1, 2);SLPushBack(&s1, 3);SLPushBack(&s1, 4);SLPrint(&s1);SLErase(&s1, 0);SLPrint(&s1);}4.5 查找
//查找
int SLFind(SL* ps, SLDataType x)
{if (ps == NULL) {exit(1);}//暴力，二分...for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){printf("值为%d，下标为%d\n", x, i);return i;}}printf("无该值\n");
}可使用不同的查找方法.
4.6 销毁
//销毁顺序表
void SLDestory(SL* ps)
{if (ps == NULL) return;//如果存在空间，释放空间if (ps->a) free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}