【数据结构初阶】顺序表的概念及动态顺序表的实现

摘要：本文从线性表的定义出发，介绍顺序表的概念与结构，对比静态顺序表与动态顺序表的区别，并完整实现一个基于 C 语言的动态顺序表，涵盖初始化、销毁、打印、扩容、头尾插删、指定位置插删及查找等核心接口，最后通过测试代码验证各功能的正确性。

1. 线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构——连续的一条直线；但是在物理结构上并不一定是连续的。线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

2.1 概念与结构

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

顺序表和数组的区别：顺序表的底层结构是数组，是对数组的封装，实现了常用的增删改查等接口。

2.2 分类

2.2.1 静态顺序表

使用定长数组存储元素：

// 静态顺序表typedefintSLDataType;#defineN6typedefstructSeqList{SLDataType a[N];// 定长数组intsize;// 有效数据个数}SL;

缺陷：空间给少了不够用，给多了造成空间浪费。

2.2.2 动态顺序表

按需申请空间——容量不够时扩容，是实际使用的方式。

3. 动态顺序表的实现

3.1 首先创建文件

3.2 头文件 SeqList.h 声明

// SeqList.h#pragmaonce//避免重复包含#define_CRT_SECURE_NO_WARNINGS//防止VS报错#include<stdio.h>#include<stdlib.h>#include<assert.h>//定义数据类型typedefintSLDataType;// 动态顺序表 -- 按需申请typedefstructSeqList{SLDataType*arr;//创建指针变量intsize;// 有效数据个数intcapacity;// 空间容量}SL;// 初始化和销毁voidSLInit(SL*ps);voidSLDestroy(SL*ps);//打印voidSLPrint(SL*ps);// 扩容voidSLCheckCapacity(SL*ps);// 头部插入删除 / 尾部插入删除voidSLPushBack(SL*ps,SLDataType x);//尾部插入数据xvoidSLPopBack(SL*ps);//尾部删除数据voidSLPushFront(SL*ps,SLDataType x);//头部插入数据xvoidSLPopFront(SL*ps);//头部删除数据// 指定位置插入 / 删除数据voidSLInsert(SL*ps,intpos,SLDataType x);//在指定位置pos插入数据xvoidSLErase(SL*ps,intpos);//在指定位置pos删除数据// 查找intSLFind(SL*ps,SLDataType x);//查找数据x

3.3 SeqList.c 文件内实现函数

3.3.1 包含头文件

// SeqList.c#include"SeqList.h"

3.3.2 初始化函数的实现

//初始化voidSLInit(SL*ps){//断言assert(ps!=NULL);//初始化数组ps->arr=NULL;ps->size=ps->capacity=0;}

3.3.3 销毁函数的实现

// 销毁voidSLDestroy(SL*ps){//断言assert(ps!=NULL);//销毁值free(ps->arr);//置空ps->arr=NULL;ps->size=ps->capacity=0;}

3.3.4 打印函数的实现

// 打印voidSLPrint(SL*ps){assert(ps!=NULL);for(inti=0;i<ps->size;i++)printf("%d ",ps->arr[i]);printf("\n");}

3.3.5 扩容函数的实现

// 扩容voidSLCheckCapacity(SL*ps){assert(ps!=NULL);if(ps->size==ps->capacity){//如果原容量为零，直接初始化为4；//不为零，则初始化为原容量的2倍intnewCapacity=ps->capacity==0?4:2*ps->capacity;SLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataType));//检验是否成功扩容if(tmp==NULL){perror("realloc failed:");exit(1);}ps->arr=tmp;//更新指针ps->capacity=newCapacity;//更新容量信息}}

3.3.6 头插函数的实现

// 头插voidSLPushFront(SL*ps,SLDataType x){//断言assert(ps!=NULL);//检查空间是否足够SLCheckCapacity(ps);//空间足够,所有数据向后移动for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;//插入新数据ps->size++;//有效数据个数增加}

3.3.7 尾插函数的实现

// 尾插voidSLPushBack(SL*ps,SLDataType x){//断言assert(ps!=NULL);//检查空间是否足够SLCheckCapacity(ps);//空间足够，直接插入ps->arr[ps->size++]=x;//后置++，插入数据后更新有效数据个数}

3.3.8 头删函数的实现

// 头删voidSLPopFront(SL*ps){//断言assert(ps!=NULL);assert(ps->size!=0);//直接将所有元素前移，覆盖第一个元素for(inti=0;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}ps->size--;//更新有效数据个数}

3.3.9 尾删函数的实现

// 尾删voidSLPopBack(SL*ps){//断言assert(ps!=NULL);assert(ps->size!=0);//直接减少有效数据个数ps->size--;}

3.3.10 指定位置插入数据

// 指定位置之前插入voidSLInsert(SL*ps,intpos,SLDataType x){//断言assert(ps!=NULL);assert(ps->size>=pos&&pos>=0);//检查空间是否足够SLCheckCapacity(ps);//将指定位置后数据后移for(inti=ps->size;i>pos;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[pos]=x;//插入数据直接覆盖指定位置数据ps->size++;//更新有效数据个数}

3.3.11 指定位置删除数据

// 指定位置删除数据voidSLErase(SL*ps,intpos){//断言assert(ps!=NULL);assert(ps->size>pos&&pos>=0);//直接将指定位置后数据前移，覆盖指定位置数据for(inti=pos;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}ps->size--;//更新有效数据个数}

3.3.12 查找指定数据

// 查找intSLFind(SL*ps,SLDataType x){//断言assert(ps!=NULL);for(inti=0;i<ps->size;i++){if(ps->arr[i]==x)returni;//查找成功则返回下标}return-1;}

3.4 test.c文件进行测试

intmain(){SL s;SLInit(&s);SLPushBack(&s,1);SLPushBack(&s,2);SLPushBack(&s,3);SLPushFront(&s,0);SLPrint(&s);// 0 1 2 3SLInsert(&s,4,4);// 末尾插入SLPrint(&s);// 0 1 2 3 4SLInsert(&s,0,-1);// 头部插入SLPrint(&s);// -1 0 1 2 3 4SLErase(&s,0);SLPrint(&s);// 0 1 2 3 4printf("find 3 = %d\n",SLFind(&s,3));// 3// 触发扩容for(inti=5;i<20;i++)SLPushBack(&s,i);SLPrint(&s);SLDestroy(&s);return0;}