数据结构-顺序表（2）

目录

1. 线性表

2. 顺序表

2.1 动态顺序表

3. 接口实现

前期工作

3.1 初始化、销毁与检查容量

3.1.1 初始化

3.1.2 销毁

3.1.3 检查容量

3.2 尾插

3.3 尾删

3.4 头插

3.5 头删

3.6 插入

3.7 删除

顺序表源码

SeqList.h

SeqList.c

test.c

写在最后：

---

1. 线性表

线性表是n个具有相同特性的数据元素的有限序列，

常见的线性表：顺序表、链表、栈、队列、字符串等等。

2. 顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构。

2.1 动态顺序表

我们一般使用的都是动态的顺序表。

3. 接口实现

前期工作

在VS上建三个工程文件，

test.c用来测试顺序表；

SeqList.c用来实现接口；

SeqList.h用来包头文件，和创建动态顺序表的基本结构；

头文件如下：

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4//选择需要的类型
typedef int SLDatatype;//动态的顺序表
typedef struct SeqList
{SLDatatype* a;int size;	  //有效的数据个数int capacity; //顺序表的空间容量
}SL;//顺序表的增删查改://初始化顺序表
void SeqInit(SL* s);//销毁顺序表
void SeqDestory(SL* s);//打印顺序表
void SeqPrint(SL* s);//检查容量
void CheckCapacity(SL* s);//尾插
void SeqPushBack(SL* s, SLDatatype x);//尾删
void SeqPopBack(SL* s);//头插
void SeqPushFront(SL* s, SLDatatype x);//头删
void SeqPopFront(SL* s);//插入
void SeqInsert(SL* s, int pos, SLDatatype x);//删除
void SeqErase(SL* s, int pos);

3.1 初始化、销毁与检查容量

接口如下：

3.1.1 初始化

//初始化顺序表
void SeqInit(SL* ps)
{//结构体指针不能为空assert(ps);//开辟空间ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY);//检查if (ps->a == NULL){perror("malloc fail");}ps->size = 0;ps->capacity = INIT_CAPACITY;
}

3.1.2 销毁

//销毁顺序表
void SeqDestory(SL* ps)
{//结构体指针不能为空assert(ps);//释放并置空free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

3.1.3 检查容量

//检查容量
void CheckCapacity(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;}
}

3.2 尾插

//尾插
void SeqPushBack(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, ps->size, x);/*单独实现//结构体指针不能为空assert(ps);//检查容量CheckCapacity(ps);//尾插ps->a[ps->size++] = x;*/
}

3.3 尾删

//尾删
void SeqPopBack(SL* ps)
{//代码复用SeqErase(ps, ps->size - 1);/*单独实现//结构体指针不能为空assert(ps);//检查顺序表是否为空assert(ps->size);//尾删ps->size--;*/
}

3.4 头插

//头插
void SeqPushFront(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, 0, 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++;*/
}

3.5 头删

//头删
void SeqPopFront(SL* ps)
{//代码复用SeqErase(ps, 0);/*单独实现//结构体指针不能为空assert(ps);//当顺序表为零时就不能删了assert(ps->size);//将数据往前覆盖int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;*/
}

3.6 插入

//插入
void SeqInsert(SL* ps, int pos, SLDatatype x)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos <= ps->size);//检查容量CheckCapacity(ps);//往后挪动数据int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}//插入数据ps->a[pos] = x;ps->size++;
}

3.7 删除

//删除
void SeqErase(SL* ps, int pos)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos < ps->size);//挪动数据int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

我们发现，

其实顺序表核心的功能就是插入和删除，

只要我们完成这两个接口，

其他的接口的实现都是大同小异。

顺序表源码

SeqList.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define INIT_CAPACITY 4//选择需要的类型
typedef int SLDatatype;//动态的顺序表
typedef struct SeqList
{SLDatatype* a;int size;	  //有效的数据个数int capacity; //顺序表的空间容量
}SL;//顺序表的增删查改://初始化顺序表
void SeqInit(SL* s);//销毁顺序表
void SeqDestory(SL* s);//打印顺序表
void SeqPrint(SL* s);//检查容量
void CheckCapacity(SL* s);//尾插
void SeqPushBack(SL* s, SLDatatype x);//尾删
void SeqPopBack(SL* s);//头插
void SeqPushFront(SL* s, SLDatatype x);//头删
void SeqPopFront(SL* s);//插入
void SeqInsert(SL* s, int pos, SLDatatype x);//删除
void SeqErase(SL* s, int pos);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"//初始化顺序表
void SeqInit(SL* ps)
{//结构体指针不能为空assert(ps);//开辟空间ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * INIT_CAPACITY);//检查if (ps->a == NULL){perror("malloc fail");}ps->size = 0;ps->capacity = INIT_CAPACITY;
}//销毁顺序表
void SeqDestory(SL* ps)
{//结构体指针不能为空assert(ps);//释放并置空free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}//打印
void SeqPrint(SL* ps)
{//结构体指针不能为空assert(ps);//遍历打印for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]); }printf("\n");
}//检查容量
void CheckCapacity(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 SeqPushBack(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, ps->size, x);/*单独实现//结构体指针不能为空assert(ps);//检查容量CheckCapacity(ps);//尾插ps->a[ps->size++] = x;*/
}//尾删
void SeqPopBack(SL* ps)
{//代码复用SeqErase(ps, ps->size - 1);/*单独实现* //结构体指针不能为空assert(ps);//检查顺序表是否为空assert(ps->size);//尾删ps->size--;*/
}//头插
void SeqPushFront(SL* ps, SLDatatype x)
{//代码复用SeqInsert(ps, 0, 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++;*/
}//头删
void SeqPopFront(SL* ps)
{//代码复用SeqErase(ps, 0);/*单独实现//结构体指针不能为空assert(ps);//当顺序表为零时就不能删了assert(ps->size);//将数据往前覆盖int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;*/
}//插入
void SeqInsert(SL* ps, int pos, SLDatatype x)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos <= ps->size);//检查容量CheckCapacity(ps);//往后挪动数据int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}//插入数据ps->a[pos] = x;ps->size++;
}//删除
void SeqErase(SL* ps, int pos)
{//结构体指针不能为空assert(ps);//pos需要在有数据的区间assert(pos >= 0 && pos < ps->size);//挪动数据int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "SeqList.h"//测试接口
void SLTest()
{SL s;SeqInit(&s);SeqPushBack(&s, 1);SeqPushBack(&s, 2);SeqPushBack(&s, 3);SeqPushBack(&s, 4);SeqPushBack(&s, 5);SeqPushBack(&s, 6);SeqPrint(&s);SeqPopBack(&s);SeqPopBack(&s);SeqPrint(&s);SeqPushFront(&s, 10);SeqPushFront(&s, 50);SeqPrint(&s);SeqPopFront(&s);SeqPopFront(&s);SeqPopFront(&s);SeqPrint(&s);SeqDestory(&s);
}int main()
{SLTest();return 0;
}

测试结果无误。

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。