【数据结构】手撕顺序表

一，概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储；

在数组上完成数据的增删查改。

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

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

 

二，接口实现

静态顺序表只适用于确定知道需要存多少数据的场景；

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用；

所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表；

        1，顺序表的创建（动态）

//动态顺序表
typedef int SLDataType;typedef struct SqList
{SLDataType* a;int size;		//存储有效数据个数int capacity;	//容量空间大小
}SL;

这里我们将数据类型暂时定为int类型，typedef为SLDataType，便于我们后续对顺序表数据类型的修改；

定义属性表为SL*的指针a，有效数据个数size，现有容量capacity;

        2，接口函数

// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos);

        3，初始化 

	//定义SL s1;//初始化SLInit(&s1);

// 顺序表初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->a== NULL){perror("malloc");exit(-1);}ps->size = 0;ps->capacity = 4;
}

首先要进行断言ps不能为空，如果ps为空则下面对ps解引用就会报错；

刚开始先给 a 申请4个SLDataType大小的空间，这个自己可以任意修改，然后对size和capacity进行赋值；

        4，销毁

// 顺序表销毁
void SLDestroy(SL*ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}

然后就是销毁顺序表，直接用 free 释放掉 a 即可，再置为空指针，再重置 size 和 capacity ；

        5，判断是否增容

// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){ps->a = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (ps->a == NULL){perror("realloc");exit(-1);}ps->capacity = ps->capacity * 2;}
}

像后面如果进行尾插，头插的话就需要检查空间是否需要增容了，也很好判断，当size等于capacity时就需要增容了，我们这里是选择直接扩容一倍；

然后再更新一下capacity的值就行了；

        6，尾插

//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查空间SLChenkCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

首先判断是否需要增容，此时size的值就是末尾的数的下标加一；

直接对其下标进行赋值，再让size加一；

        7，尾删

//顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔的检查//if (ps->size == 0)//	return;//暴力检查assert(ps->size > 0);ps->size--;
}

这里有两种检查方式，推荐暴力检查法，要删除值，size的值必须大于0；

然后直接令size减一即可，访问不到即为删除；

          8，头插

//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLChenkCapacity(ps);int end = ps->size-1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--; }ps->a[0] = x;ps->size++;
}

还是先判断是否需要增容，然后先将整体的值往后推一位；

给头赋值，令size加一；

           9，头删

//顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int i = 0;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}

要删除数据首先数据不能为空，要进行断言一下；

然后将整体往前推一位，再令size减一；

        10，打印

//顺序表打印
void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}

size是数据个数，其减一就是末尾数据的下标，然后进行遍历打印即可；

        11，查找

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

直接遍历数组进行查找然后返回下标，没有则返回-1；

         12，指定位置进行插入

// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{assert(ps);assert(pos>=0 && pos <= ps->size);SLChenkCapacity(ps);int end = ps->size - 1;while (end >=pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

首先判断pos要大于等于0且小于等于size，是否需要增容；

然后从pos数组的值往后推一位，再对其位置重新赋值，再令size++；

         13，指定位置进行删除

// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = pos;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}

首先还是要判断pos的值，大于等于0小于size，因为数组下标为size是没有值的，所以pos不能等于size；

然后在pos处往前推一位，令size--；

三，源码

        1，头文件

SqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//动态顺序表
typedef int SLDataType;typedef struct SqList
{SLDataType* a;int size;		//存储有效数据个数int capacity;	//容量空间大小
}SL;// 顺序表初始化
void SLInit(SL* ps);
// 顺序表销毁
void SLDestroy(SL* ps);
// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps);
//顺序表尾插
void SLPushBack(SL* ps,SLDataType x);
//顺序表尾删
void SLPopBack(SL* ps);
//顺序表头插
void SLPushFront(SL* ps, SLDataType x);
//顺序表头删
void SLPopFront(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
// 顺序表查找
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x);
// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos);

         2，执行文件

SqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SqList.h"// 顺序表初始化
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->a== NULL){perror("malloc");exit(-1);}ps->size = 0;ps->capacity = 4;
}// 顺序表销毁
void SLDestroy(SL*ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}// 检查空间，如果满了，进行增容
void SLChenkCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){ps->a = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));if (ps->a == NULL){perror("realloc");exit(-1);}ps->capacity = ps->capacity * 2;}
}//顺序表尾插
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//检查空间SLChenkCapacity(ps);ps->a[ps->size] = x;ps->size++;
}//顺序表尾删
void SLPopBack(SL* ps)
{assert(ps);//温柔的检查//if (ps->size == 0)//	return;//暴力检查assert(ps->size > 0);ps->size--;
}//顺序表头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLChenkCapacity(ps);int end = ps->size-1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--; }ps->a[0] = x;ps->size++;
}//顺序表头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int i = 0;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}//顺序表打印
void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");
}// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}// 顺序表在pos位置插入x
void SLInsert(SL*ps, int pos, SLDataType x)
{assert(ps);assert(pos>=0 && pos <= ps->size);SLChenkCapacity(ps);int end = ps->size - 1;while (end >=pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}// 顺序表在pos位置删除x
void SLErase(SL*ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = pos;while (i < ps->size - 1){ps->a[i] = ps->a[i + 1];i++;}ps->size--;
}

如有不足之处欢迎来补充交流！

完结。。。

---