二.线性表之顺序表

前言

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储：

一.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

#define N 7
typedef int SlDataType;
typedef struct Seqlist
{SlDataType array[N];  //定长数组size_t size;   //有效数据个数
}Seqlist;

2. 动态顺序表：使用动态开辟的数组存储。

二.顺序表的接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，下面我们来实现动态顺序表：

1.顺序表的动态存储

typedef int SLDataType;  //可以是int，double，结构体，按照要求来
#define INIT_CAPACITY 4  //初始化大小为4typedef struct Seqlist
{SLDataType* a;   //指向存放数据的每一个内存空间int size;        //有效数据个数int capacity;    //空间容量
}SL;

顺序表的长度是不固定的，可增容的，所以要用指针指向每一块信息空间。

2.顺序表的初始化

void SLInit(SL* pc)
{assert(pc);//1.强制转化类型 2.分配的是字节：sizeof(SLDataType) * INIT_CAPACITYpc->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);  //刚开始分配4个if (pc->a == NULL){perror("malloc");return;}pc->size = 0;pc->capacity = INIT_CAPACITY;
}

采用动态分配内存的方式，进行初始化

3.顺序表尾插

void SLPushBack(SL* pc, SLDataType x)
{assert(pc);//检查是否扩容if (pc->size == pc->capacity){SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);if (tmp == NULL){printf("realloc");return;}pc->a = tmp;pc->capacity *= 2;}//pc->size记录的是当前表中数据的下一位，直接赋值给该位赋值即可pc->a[pc->size++] = x;  
}

注意：

1. realloc函数是按照字节调整大小，所以一定要记得用sizeof 计算类型的字节大小。
2. pc->a[pc->size++] = x的具体含义如下：
   

改进：上面尾插数据时我们需要检查是否扩容，不如就把扩容函数单独封装，后面再需要检查扩容的时候直接调用该函数即可：

#封装：扩容函数

void SLCheckCapacity(SL* pc)
{assert(pc);//检查是否扩容if (pc->size == pc->capacity){//有可能异地扩容，再新定义一个指针SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);if (tmp == NULL){printf("relloc");return;}pc->a = tmp;pc->capacity *= 2;}
}

这样尾插函数就可以简化为：

void SLPushBack(SL* pc, SLDataType x)
{//assert(pc);检查是否扩容//if (pc->size == pc->capacity)//{//	//有可能异地扩容，再新定义一个指针//	SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);//	if (tmp == NULL)//	{//		printf("relloc");//		return;//	}//	pc->a = tmp;  //	pc->capacity *= 2;//}SLCheckCapacity(pc);pc->a[pc->size++] = x;
}

4.顺序表尾删

void SLPopBakc(SL* pc)
{//暴力的检查//assert(pc->size > 0);//温柔的检查if (pc->size == 0)return;pc->size--;
}

注意：

1. 当size删到0的时候，我们就没法再删除元素了，否则会出问题，所以在删除元素的时候需要特判一下size的大小，可以用断言assert，也可以用if语句。
2. **pc->size- -；**的意思是顺序表中元素数量减一，也就是删掉了尾部元素。

5.顺序表头插

//头插
void SLPushFront(SL* pc，SLDataType x)
{assert(pc);SLCheckCapacity(pc);int end = pc->size - 1;  while (end >= 0){//从最后一位开始，整体把数据后移一位pc->a[end + 1] = pc->a[end];--end;}pc->a[0] = x;pc->size++;
}

为了给开头腾出位置，需要将数据整体先向后移动一位：

从最后一位开始移动，防止数据被覆盖

6.顺序表头删

//头删
void SLPopFront(SL* pc)
{assert(pc);assert(pc->size > 0); //保证有数据int begin = 1;while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];}pc -> size--;
}

删除头部数据前先判断表中是否有数据，表里没东西固然不能硬删。删头元素时是把头元素后面的数据全部往前挪一位，整体覆盖前一个数据，相当于删除了头部元素：

从第二个开始往前挪，防止提前被覆盖。

7.顺序表查找

//查找
int SLFind(SL* pc, SLDataType x)
{assert(pc);for (int i = 0; i < pc->size; i++){if (pc->a[i] == x){return i;}}return -1;
}

直接遍历一遍查找即可

8.顺序表在pos位置插入x

//任意位置插入
void SLInsert(SL* pc, int pos, SLDataType x)
{assert(pc);assert(pos >= 0 && pos <= pc->size);SLCheckCapacity(pc);int end = pc->size - 1;while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;
}

与头插法想法类似，把pos后面的数据整体向后挪动一位，给pos腾出位置来，放入新的值x：

改进：当pos=0的时候其实就是头插，当pos=pc->size的时候就是尾插
所以我们可以只用一个在任意位置插入的SLInsert函数实现所有位置的数据插入：
①尾插：

void SLPushBack(SL* pc, SLDataType x)
{//assert(pc);检查是否扩容//if (pc->size == pc->capacity)//{//	//有可能异地扩容，再新定义一个指针//	SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);//	if (tmp == NULL)//	{//		printf("relloc");//		return;//	}//	pc->a = tmp;  //	pc->capacity *= 2;//}/*SLCheckCapacity(pc);pc->a[pc->size++] = x;*/SLInsert(pc, pc->size, x);
}

②头插

void SLPushFront(SL* pc, SLDataType x)
{//assert(pc);//SLCheckCapacity(pc);//int end = pc->size - 1;  //while (end >= 0)//{//	//从最后一位开始，整体把数据后移一位//	pc->a[end + 1] = pc->a[end];//	--end;//}//pc->a[0] = x;//pc->size++;SLInsert(pc, 0, x);
}

这又能进一步使代码变得简洁

9.顺序表删除pos位置的值

//任意位置删除
void SLErase(SL* pc, int pos)
{assert(pc);assert(pc >= 0 && pos < pc->size);  //size指向当前数据的下一位，还没有存放数据，所以没东西可删，要注意与任意位置插入的代码区分int begin = pos + 1;while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;
}

与头删法类似，采用从pos后往前覆盖的思想，把pos存的数据覆盖住：

改进：当pos=0时就是头删，当pos=pc->size-1时就是尾删，这样我们可以只用该函数实现任意位置的删除
①尾删：

void SLPopBakc(SL* pc)
{//assert(pc);暴力的检查//assert(pc->size > 0);//温柔的检查//if (pc->size == 0)//	return;//pc->size--;SLErase(pc, pc->size - 1);
}

②头删

//头删
void SLPopFront(SL* pc)
{//assert(pc);//assert(pc->size > 0); //保证有数据//int begin = 1;//while (begin < pc->size)//{//	pc->a[begin - 1] = pc->a[begin];//}//pc -> size--;SLErase(pc, 0);
}

使代码更简洁。

10.顺序表销毁

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

由于空间都是动态分配的，所以销毁的时候直接free掉，free后的指针记得置空。

11.顺序表打印

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

三.源

1.Seqlist.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//typedef int SLDataType;
//#define N 100000
//
 静态顺序表 -- 开少了不够用 开多了浪费
//struct SeqList
//{
//	SLDataType a[N];
//	int size;
//};typedef int SLDataType;
#define INIT_CAPACITY 4// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDataType* a;int size;     // 有效数据个数int capacity; // 空间容量
}SL;// 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

2.Seqlist.c

#include"SeqList.h"
//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType)* INIT_CAPACITY);if (ps->a == NULL){perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}
//销毁数据
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
//打印数据
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}
//检查扩容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{//assert(ps); 扩容//SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;//ps->a[ps->size++] = x;SLInsert(ps, ps->size, x);
}
//尾删
void SLPopBack(SL* ps)
{//assert(ps); 暴力检查//assert(ps->size > 0); 温柔的检查if (ps->size == 0)//	//return;ps->a[ps->size - 1] = 0;//ps->size--;SLErase(ps, ps->size-1);
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{/*assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;*/SLInsert(ps, 0, x);
}
//头删
void SLPopFront(SL* ps)
{//assert(ps);//assert(ps->size > 0);//int begin = 1;//while (begin < ps->size)//{//	ps->a[begin - 1] = ps->a[begin];//	++begin;//}//ps->size--;SLErase(ps, 0);
}
//任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}
//任意位置删除
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];++begin;}ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{assert(ps);for(int i = 0; i < ps->size; ++i){if (ps->a[i] == x){return i;}}return -1;
}

四.顺序表的问题及思考

1. 中间或头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

要解决上述问题，就要用到链表的知识了，我们下一篇再见！！

---

码文不易，还请多多支持哦！！