【C进阶】顺序表详解

文章目录

• 线性表的概念
• 顺序表
• • 顺序表的概念
  • 声明--接口
  • • 启动
    • • 初始化
      • 扩容
      • 尾插
      • 打印
      • 销毁
      • 尾删
      • 头插
      • 头删
      • 指定位置插入数据
      • • 删除指定位置数据
        • 查找
        • • 修改
          • ���结

            ---

            线性表的概念

            线性表是一种常见的抽象数据类型：线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

            线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

            线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

            顺序表：逻辑结构是线性的，物理结构是连续的

            顺序表

            顺序表的概念

            顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

            顺序表是一种线性表数据结构。顺序表和数组的区别：顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

            顺序表分类：

            1. 静态顺序表：使⽤定⻓数组存储元素【缺陷：空间给少了不够⽤，给多了造成空间浪费】
            2. 动态顺序表：使用动态开辟的数组存储

            声明–接口

            静态顺序表：给定的数组长度，若不够，会导致后续的数据保存失败，导致数据丢失，给多了，会导致空间大量浪费。

            因此推荐使用动态顺序表，动态顺序表的长度可以动态增长,不需要预先指定表长。常见的动态顺序表实现包括:向量(Vector)、数组列表(ArrayList)等。它们内部使用动态数组实现自动扩容机制。

            本文实现动态顺序表。

            接口函数是指定义在接口(interface)中的函数。

            接口是一种抽象类型,它定义了一组函数原型而不提供具体实现。接口函数就是这组函数原型。

            我们将创建在seqList.h文件，因此我们在每一个文件要使用直接包含该头文件就可以使用了。

            接口如下：

            //初始化和销毁void SLInit(SL* ps);void SLDestroy(SL* ps);void SLPrint(SL* ps);//保持接口一致性// 扩容void SLCheckCapacity(SL * ps);//顺序表的头部/尾部插入void SLPushBack(SL* ps, SLDataType x);void SLPushFront(SL* ps, SLDataType x);//顺序表的头部/尾部删除void SLPopBack(SL* ps);void SLPopFront(SL* ps);//指定位置之前插入数据//删除指定位置数据void SLInsert(SL* ps, int pos, SLDataType x);void SLErase(SL* ps, int pos);//查找/修改int SLFind(SL* ps, SLDataType x);void SLModify(SL* ps, int pos, SLDatatype x) 

            启动

            （不，是创建文件）为了让代码具有可读性，方便后期维护，我们将文件分成三个文件进行，创建三个文件：头文件：“SeqList.h”用来存放头文件接口函数，源文件"SeqList.c"用来实现接口函数，具体实现步骤，"test.c"检查错误，测试函数功能如图：

            SeqList.h

            # define _CRT_SECURE_NO_WARNINGS 1#include #include #include //静态顺序表//#define N 100//struct SeqList//{//SLDataType a[N];//int size;//};//动态顺序表typedef int SLDataType;typedef struct SeqList{SLDataType* arr;//存储数据的底层结构int capacity;   //记录顺序表的空间大小int size;       //记录顺序表当前有效的数据个数}SL;

            int 【N】和int*arr这样写不方便后面代码修改数据类型，当文件想要把数据类型int，修改为char，但是一个一个改，不方便，一键替换，会有替换不必要的风险，因此我们用typedef重新把int取名为SLDataType，因此要修改，直接修改int即可。

            为了代码可读性，偷点小懒，我们可以把struct SeqList使用typedef再取名为SL，写SL比struct SeqList，更加方便，快捷。

            初始化

            Ok，“Seqlist.h"接口搞定了，来具体实现接口函数"SeqList.c”，老样子，把接口函数的文件包含起来1. 将顺序表的数组指针初始化为NULL 2.将顺序表的当前长度size和容量capacity初始化为0：

            #include "SeqList.h"//初始化函数void SLInit(SL* ps){ps->arr=NULL;ps->size = ps->capacity = 0;}

            扩容

            当我们插入数据，若空间不够，将要扩容操作：使用realloc函数。

            //扩容void SLCheckCapacity(SL* ps){if (ps->size == ps->capacity) //如果当前长度等于容量,需要扩容{//如果原容量为0,则新容量为4 //否则新容量为原容量的2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));//使用realloc重新分配内存空间if (NULL == tmp)//realloc失败,输出错误信息并退出{perror("realloc");exit(1);}/扩容成功,更新数组指针和容量ps->arr = tmp;ps->capacity = newCapacity;}}

            尾插

            尾插的注意情况：

            顺序表没有空间capacity为0，插不了，或者创建的空间capacity满了，或者空间足够，直接插。

            void SLPushBack(SL* ps, SLDataType x){//断言--简单粗暴的解决方式//assert(ps !=NULL);assert(ps);//if判断--温柔的解决方式if(NULL == ps){return;}//空间不够，扩容SLCheckCapacity(ps);//空间足够，直接插入ps->arr[ps->size++] = x;//ps->size++;}

            打印

            打印函数，实现一个功能，我们可以实时进行输入数据验证，进行对函数的检查，我们把他封装在一个函数里，需要时，只需调用即可。

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

            销毁

            到这里，顺序表的初始化，创建了尾插数据，打印检查，如果这样就完成了可不行，因为我们顺序表是动态内存分配的，还在内存的堆上有realloc分配的空间，不销毁会有内存泄漏的风险。

            //销毁void SLDestroy(SL* ps) {assert(ps);// 断言ps指针非空,防止传入NULL指针导致问题if (ps->arr) / 检查顺序表是否分配过内存{free(ps->arr);// 如果分配过内存,使用free释放内存}ps->arr = NULL;/ 释放完内存后,将arr指针设置为NULLps->size = ps->capacity = 0;/ 重置size和capacity为0,表示顺序表结构被销毁}

            尾删

            尾部删除，你可能想到把最后那个元素标志为-1然后通过设置标识值来"删除",本身不修改元素内存,这样也可以，但是这样会篡改数据，如果原来是-1，怎么办？这样的代码如下：

            //尾部删除void SLPopBack(SL* ps){assert(ps);assert(ps->size);//顺序表不为空ps->arr[ps->size - 1] = -1;ps->size--;}

            其实只要把最后一个元素数量减掉，最后一个数据去掉，size--，并不影响我们查找等功能。代码如下：

            //尾部删除void SLPopBack(SL* ps){assert(ps);// 断言ps指针非空assert(ps->size);// 断言顺序表不为空//顺序表不为空,可以进行删除操作ps->size--;//顺序表长度减1}

            头插

            顺序表的头插操作主要步骤如下:

                     | 1 | 2 | 3 | 4 |         size = 4

            1. 检查顺序表是否为空,通过size判断

            2. 先把插入位置设为0,表示插入到头部

            3. 从尾到头依次移动元素,为新的元素腾出空间

                     |   | 1 | 2 | 3 | 4 |      size = 4

               for(int i=ps->size; i>0; i--)   {       ps->arr[i] = ps->arr[i-1];   }

            1. 将新元素插入到0位置

                     | 0 | 1 | 2 | 3 | 4 |    size = 5

               ps->arr[0] = x;

            1. 顺序表长度size加1

            它保证了元素的有序性,但移动元素的开销较大。时间复杂度为O(n)。

            //头插void SLPushFront(SL* ps, SLDataType x){assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧的数据往后挪动一位for (int i = ps->size;i>0;i--){ps->arr[i] = ps->arr[i - 1];//ps->arr[1]=ps->arr[0]}ps->arr[0] = x;ps->size++;}

            头删

            方式和头插差不多，只需依次向前挪动数据，然后数据减一，size–就好了。

            //头删void SLPopFront(SL* ps){assert(ps);assert(ps->size);//不为空执行挪动操作for (int i = 0; isize-1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;}

            注意：为了防止头删除删到顺序表为空了，还删会出现越界，因此需要对顺序表的有效个数进行断言。

            指定位置插入数据

            顺序表指定位置插入数据的主要思路是:

            1. 检查顺序表ps和插入位置pos是否合法

            2. 从尾到头遍历元素,当索引大于等于插入位置pos时,后移一个位置

               for(int i=ps->size-1; i>=pos; i--)   {       ps->arr[i+1] = ps->arr[i];   }

            1. 将新元素插入到pos位置

               ps->arr[pos] = x; 

            1. 顺序表长度size加1

            具体步骤:

            假设现有顺序表:{1,2,3,4},插入元素0到位置1:

                     |1|2|3|4|       size=4

            1. pos设为1

            2. 从尾到头遍历,i>=pos时后移元素

                     | |1|2|3|4|    size=4  

            3. 在pos=1位置插入0

                     |0|1|2|3|4|    size=5

            通过从尾到头遍历元素,每次将元素后移一个位置,为插入元素腾出指定位置pos,然后插入新元素,实现了顺序表指定位置插入。

            时间复杂度为O(n),需要移动指定位置之后的所有元素。

            //指定位置插入数据void SLInsert(SL* ps, int pos, SLDataType x){assert(ps);assert(pos >= 0 && pos size);SLCheckCapacity(ps);for(int i=ps->size-1; i>=pos; i--)   {       ps->arr[i+1] = ps->arr[i];   }ps->arr[pos] = x;ps->size++;}

            删除指定位置数据

            顺序表删除指定位置数据的主要步骤是:

            1. 检查顺序表ps和位置pos是否合法

            2. 从删除位置开始,将后面的元素前移一个位置

               for(int i=pos; isize-1; i++)   {         ps->arr[i] = ps->arr[i+1];   }

            1. 顺序表长度size减1

            具体操作如下:

            假设顺序表为:{1,2,3,4},删除位置2的元素:

                     |1|2|3|4|       size=4

            1. 确定删除位置pos=2

            2. 从pos开始,将后面元素前移一个位置

                     |1|3|4| |    size=4

            3. pos减1

                     |1|3|4| |    size=3

            代码：

            void SLErase(SL* ps, int pos){assert(ps);assert(pos >= 0 && pos size);//pos以后的数据往前挪动一位for (int i=pos;isize-1;i++){ps->arr[i] = ps->arr[i + 1];//ps->arr[i-2]=ps->arr[i-1];}ps->size--;}

            查找

            遍历元素，找到相同元素的数据返回即可，找不到返回-1

            int SLFind(SL* ps, SLDataType x){assert(ps);for (int i = 0; i size; i++){if (ps->arr[i] == x) {return i;}}return -1;}

            修改

            //修改void SLModify(SL* ps, int pos, SLDatatype x)  {assert(ps);assert(pos >= 0 && pos size);ps->a[pos] = x;}

            总结

            感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞