【数据结构】动态顺序表的接口实现（附图解和源码）

动态顺序表的接口实现（附图解和源码）

---

---

前言

本文主要介绍动态顺序表中增删查改等接口实现，结尾附总源码！

---

一、定义结构体

代码如下（示例）：

#define N 1000
typedef int SLDataType;//int->SLDataTypetypedef struct SeqList
{SLDataType* a;int size;      //表示数组中存储了多少个元素int capacity; //表示最大容积
}SeqList;

---

二、每一个接口的实现原理（附图解）

注意：接口函数的命名风格是跟着STL走的。
这里的11个接口，我都会一 一为大家讲解（图解+源码）

1.初始化顺序表

初始化的时候把a数组为NULL，储存元素个数和最大容量都设为0

代码如下（示例）：

void SeqListInit(SeqList* ps)
{ps->a = NULL;ps->size = 0；ps->capacity = 0;
}

---

2.增容顺序表

当我们的size和capacity相等的时候（数组已经满了），要进行增容！具体看下图！

代码如下（示例）：

void SeqLisrCheckCapacity(SeqList* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}

---

3.尾插数据

代码如下（示例）：

void SeqListPushBack(SeqList* ps, SLDataType x)
{SeqLisrCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

---

4.删除顺序表信息（尾删）

大家可能会好奇，为什么这里只有尾删法，一会我会给大家介绍指定位置删除的方法~

代码如下（示例）：

void SeqListPopBack(SeqList* ps)
{if (ps->size > 0){//ps->a[ps->size - 1] = 0;ps->size--;}elseprintf("容量不足，无法执行过多的删除行为！");
}

---

5.打印顺序表信息

打印信息和打印一个一维数组的打印方法一样，这里不做过多的介绍！

代码如下（示例）：

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

6.销毁顺序表

所谓销毁指的就是对realloc开辟的空间通过free进行释放！

代码如下（示例）：

void SeqListDestroy(SeqList* ps)
{free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}

---

7.头插数据

头插和尾插得原来差不多，尾插一定要保证end>=0，这样才不会导致越界访问~

代码如下（示例）：

void SeqListPushFront(SeqList* ps, SLDataType x)
{SeqLisrCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

---

8.删除顺序表信息（头删）

代码如下（示例）：

void SeqListPopFront(SeqList* ps)
{int left = 0;if (ps->size > 0){while (left != ps->size - 1){ps->a[left] = ps->a[left + 1];left++;}ps->size--;}else{printf("没有可删除的内容！");}
}

---

9.查找顺序表中元素

这里采用一维数组的遍历方式进行查找并返回下标~

代码如下（示例）：

int SeqListFind(SeqList* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}

---

10.指定pos下标位置插入元素

这里有两个注意的点：1.要保证pos下标不越界。2.要考虑增容问题

代码如下（示例）：

void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{assert(pos <= ps->size && pos >= 0);SeqLisrCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

---

11.删除pos位置的数据（头删+尾删+任意位置删除）

这里的任意位置删除可以把头删和尾删替换掉，这种删除是很全面的~
注意：这里的pos不可以越界（不可以等于size）

代码如下（示例）：

void SeqListErase(SeqList* ps, int pos)
{assert(pos < ps->size&& pos >= 0);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

---

三、源代码整理

这里分为三个文件，分别是test.c(头文件包含和测试)、SepList.c(函数的实现)、SepList.h(头文件声明)

test.c 源码如下：

#include "SepList.h"
void TestSeqList1()
{SeqList s1;SeqListInit(&s1);SeqListPushBack(&s1, 1);SeqListPushBack(&s1, 2);SeqListPushBack(&s1, 3);SeqListPushBack(&s1, 4);SeqListPushBack(&s1, 5);SeqListPrint(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPopBack(&s1);SeqListPrint(&s1);SeqListDestroy(&s1);
}
void TestSeqList2()
{SeqList s1;SeqListInit(&s1);SeqListPushBack(&s1, 1);SeqListPushBack(&s1, 2);SeqListPushBack(&s1, 3);SeqListPushBack(&s1, 4);SeqListPushBack(&s1, 5);SeqListPrint(&s1);SeqListPushFront(&s1, 30);SeqListPushFront(&s1, 40);SeqListPushFront(&s1, 50);SeqListPushFront(&s1, 60);SeqListPrint(&s1);int ret = SeqListFind(&s1, 30);//if (ret >= 0)//	printf("找到了下标是%d\n", ret);//else//	printf("%d\n", ret);SeqListInsert(&s1, 3, 35);SeqListPrint(&s1);SeqListErase(&s1, 0);SeqListPrint(&s1);
}
int main()
{//TestSeqList1();TestSeqList2();return 0;
}

SepList.h 源码如下：

#pragma once
#include <stdio.h>
#include <stdlib.h> 
#include <assert.h>#define N 1000
typedef int SLDataType;//int->SLDataTypetypedef struct SeqList
{SLDataType* a;int size;      //表示数组中存储了多少个元素int capacity; //表示最大容积
}SeqList;//接口函数 -- 命名风格是跟着STL走的。
void SeqListInit(SeqList* ps);//初始化顺序表
void SeqListPushBack(SeqList* ps, SLDataType x);//添加顺序表信息
void SeqListDestroy(SeqList* ps);//销毁顺序表
void SeqLisrCheckCapacity(SeqList* ps);//增容顺序表
void SeqListPrint(SeqList* ps);//打印顺序表信息
void SeqListPopBack(SeqList* ps);//删除顺序表信息
void SeqListPushFront(SeqList* ps, SLDataType x);//头插数据
void SeqListPopFront(SeqList* ps);//删除头插信息
int SeqListFind(SeqList* ps, SLDataType x);//找到了返回x位置下标，没有找到返回-1
void SeqListInsert(SeqList* ps, int pos, SLDataType x);//指定pos下标位置插入
void SeqListErase(SeqList* ps, int pos);//删除pos位置的数据

SepList.c 如下（示例）：

#include "SepList.h"void SeqListInit(SeqList* ps)
{ps->a = NULL;ps->size = ps->capacity = 0;
}void SeqListDestroy(SeqList* ps)
{free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}void SeqListPrint(SeqList* ps)
{for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}void SeqListPopBack(SeqList* ps)
{if (ps->size > 0){//ps->a[ps->size - 1] = 0;ps->size--;}elseprintf("容量不足，无法执行过多的删除行为！");
}void SeqLisrCheckCapacity(SeqList* ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}
}void SeqListPushBack(SeqList* ps, SLDataType x)
{SeqLisrCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}void SeqListPushFront(SeqList* ps, SLDataType x)
{SeqLisrCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}void SeqListPopFront(SeqList* ps)
{int left = 0;if (ps->size > 0){while (left != ps->size - 1){ps->a[left] = ps->a[left + 1];left++;}ps->size--;}else{printf("没有可删除的内容！");}
}int SeqListFind(SeqList* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{assert(pos <= ps->size && pos >= 0);SeqLisrCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}void SeqListErase(SeqList* ps, int pos)
{assert(pos < ps->size&& pos >= 0);int begin = pos + 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

---

总结

以上就是今天要讲的内容，本文介绍了动态顺序表的11种接口实现原理和源码图解！
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！
在这里和大家声明一下，本人并不是大学生，而是一个编程爱好者！！！