当前位置：首页 > news >正文

数据结构第二章：线性表之顺序表

news 2025/7/21 9:14:59

一.线性表的认识

n个具有相同特性的数据元素的有序序列。常见的线性表有：顺序表、链表、栈、队列、字符串······线性表在逻辑上是线性结构的，也就是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

数组形式的图像：

链式结构形式的图像：

二.顺序表的实现

1.顺序表的概念和结构

顺序表是用一段物理地址连续的存储单元，依次存储数据元素的线性结构，一般情况下采用数组的方式进行存储，在数组上完成数据的增删查改。

顺序表一般分为静态顺序表和动态顺序表，静态顺序表使用定长的数组存储；动态顺序表使用动态开辟的数组进行存储。

静态顺序表使用固定大小的数组存储数据，存储空间在编译时就已经确定，大小不可改变；容量固定，一旦数据量超过预设大小，会出现溢出；如果预设容量远大于实际容量，会造成内存浪费，若容量不足，则无法扩容。

动态顺序表存储空间在程序运行时，通过动态内存分配获得，大小可以根据需求调节；容量可动态增长，当数据量接近当前容量时，会重新分配更大的内存空间（一般为原内存的二倍），并将原有数据复制过去，避免溢出；优点是内存利用率高，缺点是扩容时的复制操作会产生额外时间开销。

综上所述，我们将实现利大于弊的动态顺序表

2.顺序表实现

在C语言中，实现一个工程程序，需要三个文件：头文件、源文件、测试文件。下来我们将一一实现。

(1)seqlist.h文件

首先顺序表的作用就是在数组上完成数据的增删查改工作，所以我们要先写出对头文件的函数声明。

在顺序表的实现过程中，我们需要有以下功能：顺序表的初始化、顺序表数据的打印、检查顺序表容量、顺序表数据头插、尾插、尾删、头删、任意位置数据的插入、删除、释放空间、查找数据、修改数据。

因为函数声明需要参数，下来我们着重讨论参数问题。函数调用参数形式分为两种：传值调用、传址调用。两种不同的调用形式不同之处在于：传址调用可以改变实际参数的数据，这恰恰能达到我们的需求，所以在函数声明的接口头文件的形式参数应该是结构体指针。

代码实践：

typedef int SQDateType;		//将int名称换成SQDateType方便后续更改typedef struct seqlist//上述typedef....{  }SL;相当于：typedef struct seqlist   SL;//解释：将struct seqlist简化成SL方便代码的书写{SQDateType * a;	//定义一个类型为SQDateType的指针变量，指向malloc扩容的数组int size;			//定义一个整型变量，记录存储了多少个数据：有效数据的个数int capacity;		//定义一个整型变量，记录内存容量大小
}SL;					//所有的SL相当于struct seqlist//SL* ps：定义结构体指针变量psvoid seqlistInit(SL* ps);		//初始化数据void seqlistPrint(SL* ps);		//打印数据void seqlistCheckCapacity(ps);	//检查容量void seqlistPushBack(SL* ps, SQDateType x);		//尾插数据void seqlistPushFront(SL* ps, SQDateType x);	//头插数据void seqlistPopBack(SL* ps);		//尾删数据void seqlistPopFront(SL* ps);		//头删数据void seqlistInsert(SL* ps, int pos, SQDateType x);		//任意位置插入数据void seqlistErase(SL* ps, int pos);			//任意位置删除数据void seqlistDestory(SL* ps);			//释放空间int seqlistFind(SL* ps, SQDateType x);		//查找数据void seqlistModity(SL* ps, int pos, SQDateType x);		//修改数据

上述代码的解释：上述是顺序表的头文件的函数接口，主要阐述了顺序表的全部功能。首先将int改名为SQDateType，方便后续更改顺序表数据的数据类型。接下来定义了动态顺序表的结构体，结构体成员有:SQDateType指针指向将要扩容的数组a；size为顺序表的有效数据的个数；capacity为顺序表的容量，方便后续判断剩余容量的多少，从而决定是否扩容。

(2)seqlist.c文件

下来我们将会逐一实现头文件中的函数接口：

<1>初始化数据

//初始化数据
void seqlistInit(SL* ps)
{ps->a = NULL;		//将最开始的空间置为0（或者malloc申请一些空间）ps->size = 0;ps->capacity = 0;}

初始化顺序表的数据，我可以将a的数据先置为空，后期再malloc扩容。当然数据的有效大小和顺序表的容量都先置为空。因为初始化只是先赋一个值，最后用的时候根据实际情况更改即可。

<2>打印数据

//打印数据
void seqlistPrint(SL* ps)
{if (ps->size <= 0){printf("顺序表无数据");exit(-1);}else for (int i = 0; i < ps->size; i++){printf("%d", ps->a[i]);}printf("\n");
}

打印顺序表的数据是为了展现顺序表内部的情况，方便后期数据的管理。当结构体成员size等于0时，说明顺序表内没有存储数据，所以便打印：“顺序表无数据”，并返回-1。当结构体成员变量size不为0时，利用for循环打印size个顺序表的有效数据内容。

<3>检查容量

//检查容量，不足则扩容
void seqlistCheckCapacity(SL*ps)
{if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SL* tmp = (SL *)realloc(ps->a, newcapacity * sizeof(SL));if (tmp == NULL){printf("扩容失败\n");return -1;}else{ps->a = tmp;ps->capacity = newcapacity;}}
}

随时检查容量的大小可以在容量不足时及时扩容，防止因为容量不足导致数据的丢失。
当有效数据的个数等于容量的大小时，这时候就没有了多余的空间，我们就需要扩容。先定义一个整型变量newcapacity用于存储新的容量大小。当旧的容量为0时，将新的容量赋值为4，当旧的容量不为0时，将新的容量赋值为二倍的旧容量的大小。
下来进行数组a容量的扩容：先定义一个结构体指针变量，用于存储经过扩容得到的空间，利用realloc扩容函数进行空间的扩容。当tmp为空时，表示扩容失败，打印错误信息；当不为空时，表示扩容成功。将tmp的地址赋值给数组a，这时候扩容的目的就达成了。接下来更新顺序表的容量大小。

<4>尾插数据

//尾插数据
void seqlistPushBack(SL* ps, SQDateType x)
{seqlistCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}

顺序表尾插数据首先应该检查容量的大小，防止尾插的数据没有空间存储，然后将需要插入的数据放入结构体成员变量a数组的尾部，最后更新一下顺序表有效数据的个数。

<5>头插数据

//头插数据
void seqlistPushFront(SL* ps, SQDateType x)
{seqlistCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

顺序表头插数据需要检查容量的大小，防止新插入的数据没有空间存储。然后将结构体成员变量a数组所有的数据后移一个空间，将需要插入的元素插入在结构体成员变量a数组的头部位置。最后不要忘记更新顺序表有效数据的个数。

<6>尾删数据

//尾删数据
void seqlistPopBack(SL* ps)
{assert(ps->size > 0);ps->size--;}

尾删数据比较简单，可以直接顺序表的有效个数减去1即可，这样便最简程度达到了尾删数据的目的。但是需要注意的是：尾删数据之前需要保证顺序表内部有数据，所以用assert断言函数，判断顺序表的有效数据的个数。如果小于0，则打印错误信息。

<7>头删数据

//头删数据
void seqlistPopFront(SL* ps)
{assert(ps->size > 0);int start=1;while (start<ps->size){ps->a[start-1] = ps->a[start];start++;}ps->size--;
}

顺序表的头删数据也要先判断顺序表的有效数据个数，当无数据储存时，打印错误信息；有数据储存时，再进行下面的头删数据的代码。头删数据可以直接将除了第一个元素之外的其他元素前移一个单位，这样就可以达到头删数据的目的。最后不要忘记更新顺序表有效数据的个数。

<8>任意位置插入数据

//任意位置插入数据
void seqlistInsert(SL* ps, int pos, SQDateType x)
{assert(ps->size > pos);seqlistCheckCapacity(ps);int end=ps->size-1;while (end>=pos){ps->a[end+1]= ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

顺序表的任意位置插入数据，需要assert判断插入的位置不能大于有效数据个数，并且需要判断容量的大小，这里调用检查容量的函数，当容量不足时，进行适当的扩容。任意位置插入数据，首先需要将该位置后面的元素后移一个单位，再将数据插入该位置，最后不要忘记更新顺序表有效数据的个数。

<9>任意位置删除数据

//任意位置删除数据
void seqlistErase(SL* ps, int pos)
{assert(pos < ps->size);int start = pos + 1;while (start< ps->size){ps->a[start - 1] = ps->a[start];start++;}ps->size--;
}

顺序表任意位置删除数据，需要先判断删除的数据是否在顺序表有效元素里，如果不在，则打印错误信息；如果在就进行任意位置删除数据。将该位置后的元素整体前移一个单位就可以达到该位置删除数据的效果，最后不要忘记更新顺序表有效数据的个数。

<10>释放空间

//释放空间
void seqlistDestory(SL* ps)
{free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

<11>查找数据

//查找数据
int seqlistFind(SL* ps, SQDateType x)
{for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}

<12>修改数据

//修改数据
void seqlistModity(SL* ps, int pos, SQDateType x)
{assert(pos < ps->size);ps->a[pos] = x;
}

三.练习题

1.题目一

题目描述：给一个数组nums和一个值val，原地移除所有等于val数值的元素，并返回移除后的数组长度。

注意：不可以使用额外的数组空间，必须用0（1）额外空间，并原地修改输入数组。

示例：nums：[0，1，2，2，3，0，4，2] val=2

思路一：逐个判断每个元素是否等于val，如果等于val就将其后的元素前移一个单位，覆盖等于val的元素，以达到删除该元素的目的。

第一步：nums：[0，1，2，3，0，4，2]
第二步：nums：[0，1，3，0，4，2]
第三步：nums：[0，1，3，0，4]
最后一步：遍历该数组，并返回新数组的元素个数。

但是上述思路代码的时间复杂度为O（N^2），我们进行优化一下：

思路二：以空间换取时间，创建一个新数组，将不等于val的元素，赋值在新数组中，最后将新元素的数组个数进行返回。

但是上述思路的时间复杂度和空间复杂度均为O（N），空间复杂度不符合题意，所以将此思路舍去。

思路三：利用双指针进行空间的省略，下来进行画图分析：

像上述图片那样，当src位置上的元素不是val时，就将src赋值给dst，然后src++，dst++；当src位置上的元素是val时，src++。最后dst的下标就是数据的个数。且dst所指位置的前面就是最后的元素。

代码实践：

int removeElement(int * nums, int numsize ,int val)
{int src =0;        //定义双变量的位置int dst =0;while(src <numsize)    //当src大于数组元素个数时，循环终止{if(num[src]!=val)    //如果src不等于val，则将src赋值给dst，并两者均自增nums[dst++]=nums[src++];elsesrc++;        //当src等于val时，src++即可}return dst;    //完成上述操作后，返回数组的元素个数
}