【数据结构】线性表之顺序表详解

🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非研究生的编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

顺序表

前言

数据的逻辑结构分为线性结构和非线性结构，线性结构中的线性表根据存储结构又分为顺序表和链表。这篇博客主要讲的是顺序表的定义和基本操作，以及它是如何实现的。

一、线性表的定义和基本操作

1. 线性表的定义

线性表是具有相同数据类型的

n (n>=0)

个数据元素的有限序列，其中

n

为表长，当

n=0

时线性表是一个空表。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

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

2. 线性表的特点

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表示一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

3. 线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下：

void ListInit(List* s);

初始化表。构造一个空的线性表。

void CheckCapacity(List* s);

检查空间，若表空间已满，进行扩容

void ListPushBack(List* s, SLDataType x)

线性表尾插

void ListPopBack(List* s);

线性表尾删

void ListPushFront(List* s, SLDataType x);

线性表头插

void ListPopFront(List* s);

线性表头删

int ListFind(List* s, SLDataType x);

线性表查找,返回查找元素的位置

void ListInsert(List* s, size_t pos, SLDataType x);

线性表在pos位置插入x

void ListErase(List* s, size_t pos);

线性表删除pos位置的值

void ListDestory(List* s);

线性表销毁

void ListPrint(List* s);

线性表打印

二、线性表的顺序表示（顺序表）

1. 顺序表的定义

线性表的顺序存储称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。线性表的顺序存储结构是一种随机存取的存储结构。一般情况通过数组来描述顺序表结构。

顺序表一般可分为：

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

#defineMaxsize50//定义顺序表的最大长度typedefint SLDataType;typedefstructSeqList{
    SLDataType data[Maxsize];//定长数组
    size_t size;//有效数据个数}SeqList;

在静态分配时，由于数组的大小和空间事先已经固定，一旦空间站满，再加入新的数据就会产生溢出，进而导致程序崩溃。

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

typedefint SLDataType;typedefstructSeqList{
  SLDataType* array;// 指向动态开辟数组的指针
  size_t size ;// 有效数据个数
  size_t capicity ;// 容量空间的大小}SeqList;

2. 顺序表的特点

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间 O(1) 内找到指定的元素。
顺序表的存储密度高，每个节点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

3. 顺序表的动态实现

typedefint SLDataType;// 顺序表的动态存储typedefstructSeqList{
    SLDataType* array;// 指向动态开辟的数组
    size_t size;// 有效数据个数
    size_t capacity;// 容量空间的大小}SeqList;

3.1 顺序表初始化

voidSeqListInit(SeqList* s){
    s->array =(SLDateType*)malloc(sizeof(SLDateType)*5);//将顺序表中的数组元素个数初始化为5个if(s->array ==NULL){return;}
    s->capacity =5;
    s->size =0;}

3.2 顺序表检查空间

voidCheckCapacity(SeqList* s){assert(s);//当数组有效元素个数与数组容量相等时进行扩容，每次扩容后的元素个数为原来的2倍if(s->capacity == s->size){
        SLDateType* array =(SLDateType*)realloc(s->a,sizeof(SLDateType)*(s->capacity*2));if(array==NULL){return;}
        s->array = array;
        s->capacity *=2;}}

3.3 顺序表打印

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

3.4 顺序表尾插

voidSeqListPushBack(SeqList* s, SLDataType x){assert(s);CheckCapacity(s);
    s->array[s->size]= x;
    s->size++;}

3.5 顺序表头插

voidSeqListPushFront(SeqList* s, SLDataType x){CheckCapacity(s);for(SLDataType i = s->size -1; i >=0; i--){
        s->array[i +1]= s->array[i];}
    s->array[0]= x;
    s->size++;}

3.6 顺序表尾删

voidSeqListPopBack(SeqList* s){
    s->size--;//对于尾删，只需要将数组元素个数减一就行，第一，在打印时不会再访问到该元素，第二，在插入时会将这个元素覆盖}

3.7 顺序表头删

voidSeqListPopFront(SeqList* s){for(size_t i =1; i < s->size; i++){
        s->array[i-1]= s->array[i];}
    s->size--;}

3.8 顺序表任意位置插入

voidSeqListInsert(SeqList* s, size_t pos, SLDataType x){assert(s);CheckCapacity(s);for(size_t i = s->size -1; i >= pos; i--){
        s->array[i +1]= s->array[i];}
    s->array[pos]= x;
    s->size++;}

3.9 顺序表任意位置删除

voidSeqListErase(SeqList* s, size_t pos){assert(s);for(size_t i = pos; i < s->size; i++){
        s->array[i]= s->array[i +1];}
    s->size--;}

3.10 顺序表查找

intSeqListFind(SeqList* s, SLDataType x){for(size_t i =0; i < s->size; i++){if(s->array[i]== x){//找到return i +1;}}//没找到return-1;}

3.11 顺序表销毁

voidSeqListDestory(SeqList* s){free(s->array);//顺序表的数组是动态申请的，所以需要通过 free 函数进行释放
    s->array =NULL;
    s->size =0;
    s->capacity =0;}

三、源代码及运行结果展示

1. SeqList.h

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLDataType;// 顺序表的动态存储typedefstructSeqList{
    SLDataType* array;// 指向动态开辟的数组
    size_t size;// 有效数据个数
    size_t capacity;// 容量空间的大小}SeqList;// 基本增删查改接口// 顺序表初始化voidSeqListInit(SeqList* s, size_t capacity);// 顺序表销毁voidSeqListDestory(SeqList* s);// 顺序表打印voidSeqListPrint(SeqList* s);// 检查空间，如果满了，进行增容voidCheckCapacity(SeqList* s);// 顺序表尾插voidSeqListPushBack(SeqList* s, SLDataType x);// 顺序表尾删voidSeqListPopBack(SeqList* s);// 顺序表头插voidSeqListPushFront(SeqList* s, SLDataType x);// 顺序表头删voidSeqListPopFront(SeqList* s);// 顺序表查找intSeqListFind(SeqList* s, SLDataType x);// 顺序表在pos位置插入xvoidSeqListInsert(SeqList* s, size_t pos, SLDataType x);// 顺序表删除pos位置的值voidSeqListErase(SeqList* s, size_t pos);

2. SeqList.c

#include"Seqlist.h"// 对数据的管理:增删查改 voidSeqListInit(SeqList* s){
    s->array =(SLDateType*)malloc(sizeof(SLDateType)*5);if(s->array ==NULL){return;}
    s->capacity =5;
    s->size =0;}voidSeqListDestroy(SeqList* s){assert(s);free(s->array);
    s->array =NULL;
    s->capacity =0;
    s->size =0;}voidCheckCapacity(SeqList* s){assert(s);//当数组有效元素个数与数组容量相等时进行扩容，每次扩容后的元素个数为原来的2倍if(s->capacity == s->size){
        SLDateType* array =(SLDateType*)realloc(s->a,sizeof(SLDateType)*(s->capacity*2));if(array==NULL){return;}
        s->array = array;
        s->capacity *=2;}}//顺序表打印voidSeqListPrint(SeqList* s){assert(s);for(int i =0; i <(s->size); i++){printf("%d ", s->a[i]);}printf("\n");}//顺序表尾插voidSeqListPushBack(SeqList* s, SLDataType x){assert(s);CheckCapacity(s);
    s->array[s->size]= x;
    s->size++;}//顺序表头插voidSeqListPushFront(SeqList* s, SLDataType x){CheckCapacity(s);for(SLDataType i = s->size -1; i >=0; i--){
        s->array[i +1]= s->array[i];}
    s->array[0]= x;
    s->size++;}//顺序表尾删voidSeqListPopBack(SeqList* s){
    s->size--;//对于尾删，只需要将数组元素个数减一就行，第一，在打印时不会再访问到该元素，第二，在插入时会将这个元素覆盖}voidSeqListPopFront(SeqList* s){for(size_t i =1; i < s->size; i++){
        s->array[i-1]= s->array[i];}
    s->size--;}// 顺序表查找intSeqListFind(SeqList* s, SLDataType x){for(size_t i =0; i < s->size; i++){if(s->array[i]== x){//找到return i +1;}}//没找到return-1;}// 顺序表在pos位置插入xvoidSeqListInsert(SeqList* s, size_t pos, SLDataType x){assert(s);CheckCapacity(s);for(size_t i = s->size -1; i >= pos; i--){
        s->array[i +1]= s->array[i];}
    s->array[pos]= x;
    s->size++;}// 顺序表删除pos位置的值voidSeqListErase(SeqList* s, size_t pos){assert(s);for(size_t i = pos; i < s->size; i++){
        s->array[i]= s->array[i +1];}
    s->size--;}voidSeqListTest(){
    SeqList s;SeqListInit(&s);SeqListPushBack(&s,1);SeqListPushBack(&s,2);SeqListPushBack(&s,3);SeqListPushBack(&s,4);SeqListPushBack(&s,5);SeqListPrint(&s);SeqListPushFront(&s,0);SeqListPrint(&s);SeqListPopFront(&s);SeqListPrint(&s);SeqListPopBack(&s);SeqListPrint(&s);SeqListInsert(&s,1,6);SeqListPrint(&s);SeqListErase(&s,1);SeqListPrint(&s);}

3. test.c

#include"seqlist.h"intmain(){SeqListTest();return0;}

结果展示:

总结

对于顺序表来说，它有着自己的特点：可在时间 O(1) 内查找元素，存储密度高。
但是，顺序表的插入删除，时间复杂度为O(N)；
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗；
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
对于上述的问题，我们可通过链表进行解决，下篇博客将会对链表进行详细讲解。