顺序表(一)(数据结构)

一. 线性表

二. 顺序表的实现

2.1 概念与结构

上面讲了线性表的概念，那什么是顺序表呢？顺序表其实就是线性表的一种，是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况采用数组存储。所以问题这就来了，顺序表在逻辑结构上线性的，那在物理结构上是线性的还是非线性的？这里就要看看顺序表的底层逻辑，上面也说了顺序表是物理地址连续存储单元，所以在物理结构上也是线性的。

2.2.1 静态顺序表

概念：使用定长数组存储元素。

#define N 7
typedef int SLDataType;
typedef struct SepList 
{SLDataType  a[N];  //定长数组int size;          //有效数据个数
}SL;

上面的代码就是一个静态顺序表，在这个顺序表中我们使用tyoedef重新定义int类型，其作用就是在我们需要替换int类型的时候我们可以按我们的需求进行替换，不用逐个来换，使用Ctrl+h一键替换，使用#define对N进行定义，size记录真正的有效个数，也就是说我们使用静态顺序表的时候是已经提前知道了数组的元素个数。静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

2.2.2 动态顺序表

静态顺序表在空间的大小上是固定的，还不够灵活，这个时候就需要动态顺序表这个更有优势的，可以动态申请空间。

typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size;      //有效数据个数int capacity;  //空间容量
}SL;

2.2 动态顺序表的实现

上面只是一个动态顺序表结构体，但如果要真正实现一个动态顺序表，我们所需要考虑的东西就多了，我们为了让代码清晰可见，在VS中创建一个头文件SeqList.h，用来定义顺序表的结构和声明要提供的操作，再创建一个SeqList.c文件，用来实现各种操作，一个test.c文件，用来测试函数。

在创建顺序表的时候我们要进行多次测试，比如当我们写好初始化的时候就可以进行一次测试，在测试函数test.c中的初始化SLInit中传入的是s的地址，使用的是传址调用，因为如果是传值调用，那么形参pa的值是不影响实参s的值，这一点我们要注意。

尾部 / 头部插入数据：

 

 上面的是对顺序表的尾插和头插，以及它们打印出来的结果，在 尾插和头插的时候我们第一要关注的是空间是否足够，第二就是我们的数组不能是空指针。在我们空间不够的时候我们使用realloc来申请空间，原因是就是realloc可以返回新空间的起始地址，然后就是在申请空间的时候推荐2倍申请，这样的话空间就不会过于浪费。

尾部 / 头部删除数据：

对于删除数据来说，有尾删和头删，大家可能对于尾删来说有点疑问，那么为什么直接pa->size--就可以呢？比如现在有一个数组包含数据1  2  3  4 ，那么现在我要删除4这个数据，我们知道size是指向有效数据的下一个位置，也就是4的后面一个位置，那么现在我让size--就会让size指向4的位置，当我们打印的时候这个位置的数据就不是有效的数据了，而且在尾部插入数据的时候在空间充足的时候我们是直接将新的数据元素之直接插在size的位置上，然后再让size++。对于头删的话我们就用将所有元素整体向前移动一位即可。

任意位置插入 / 删除数据：

在指定位置删除或者插入数据的时候，我们一定要注意不是是空指针。 

完整代码：

SeqList.h:

//顺序表，（动态顺序表）
//一般我们会有头文件和.c文件用来实现各种操作
//定义动态顺序表结构
#include <stdio.h>
#include <stdlib.h>//申请空间//如果后期要改变int的类型，为了方便，我们进行重命名
typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* arr;int capacity;  //空间大小int size;  //有效数据个数
}SL;//初始化
void SLInit(SL* pa);
//销毁
void SLDestory(SL* pa);
//打印数据
void SLPrintf(SL* pa);
//插入数据
void SLPushBack(SL* pa,SLDatatype x);   //尾部插入
void SLPopBack(SL* pa);                 //尾部删除
void SLPushFront(SL* pa, SLDatatype x); //头部插入
void SLPopFront(SL* pa);                //头部删除
void SLInsert(SL* pa, SLDatatype x, int pos);//任意位置之前插入数据
void SLErase(SL* pa, int pos);//删除指定位置的数据

SeqList.c:

//顺序表（动态顺序表）
//一般我们会有头文件和.c文件用来实现各种操作
#include "SeqList.h"
//初始化
void SLInit(SL* pa)
{pa->arr = NULL;pa->size = pa->capacity = 0;
}
//销毁
void SLDestory(SL* pa)
{if (pa != NULL){free(pa->arr);}pa->arr = NULL;pa->size = pa->capacity = 0;
}//判断空间是否足够
void SLCheckcapacity(SL* pa)
{if (pa->size == pa->capacity){//增容 0*2=0，若capacity为0，给个默认值，否则*2倍int newcapacity = pa->capacity == 0 ? 4 : 2 * pa->capacity;SLDatatype* tmp = realloc(pa->arr, newcapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}pa->arr = tmp;pa->capacity = newcapacity;}
}
//插入数据
void SLPushBack(SL* pa, SLDatatype x)//尾插数据
{//判断pa是否为空指针if (pa == NULL){return;}//判读空间是否足够SLCheckcapacity(pa);pa->arr[pa->size] = x;pa->size++;
}
void SLPushFront(SL* pa, SLDatatype x)//头插数据
{//判断pa是否为空指针if (pa == NULL){return;}//判读空间是否足够SLCheckcapacity(pa);//数据整体向后移动一位for (int i = pa->size; i >= 0; i--){pa->arr[i] = pa->arr[i- 1];}pa->arr[0] = x;pa->size++;
}
//删除数据
#include <assert.h>
void SLPopBack(SL* pa)//尾删
{assert(pa);assert(pa->size);pa->size--;
}
void SLPopFront(SL* pa)//头删
{assert(pa);assert(pa->size);//数据整体向前挪动一位for (int i = 0;i<pa->size-1; i++){pa->arr[i] = pa->arr[i + 1];}pa->size--;
}//任意位置之前插入数据
void SLInsert(SL* pa, SLDatatype x, int pos)
{assert(pa);assert(pos >= 0 && pos <= pa->size);//空间检查SLCheckcapacity(pa);//pos及之后的数据整体向后移动一位for (int i = pa->size; i > pos; i--){pa->arr[i] = pa->arr[i - 1];}pa->arr[pos] = x;pa->size++;
}
//删除指定位置的数据
void SLErase(SL* pa, int pos)
{assert(pa);assert(pos >= 0 && pos < pa->size);//pos之后的数据整体向前移动一位for (int i=pos;i<pa->size-1;i++){pa->arr[i] = pa->arr[i + 1];}pa->size--;
}//打印数据
void SLPrintf(SL* pa)
{for (int i = 0; i < pa->size; i++){printf("%d ", pa->arr[i]);}printf("\n");
}

test.c：

//测试
#include "SeqList.h"
void SLtest01()
{SL s;SLInit(&s);//初始化SLPushBack(&s, 1);//尾插数据SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPopBack(&s);SLPrintf(&s);//SLPushFront(&s, 1);//头插数据//SLPushFront(&s, 2);//SLPushFront(&s, 3);//SLPushFront(&s, 4);SLPrintf(&s);SLDestory(&s);
}int main()
{SLtest01();return 0;
}