一文彻底搞清楚数据结构之顺序表

承渊政道

发布于 2025-12-18 17:12:52

2110

🔥承渊政道：个人主页 ❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》 ✨逆境不吐心中苦,顺境不忘来时路! 🎬 博主简介:

前言：想拥有好的算法能力是建立在好的算法结构基础上,数据结构是算法能力的基础.本篇文章是来介绍一下数据逻辑结构中的线性结构中的线性表包含的顺序表,下面跟着小编的节奏🎵一起学习吧！

1.线性表

线性表:是n个具有相同特性的数据元素的有限序列,数据元素之间是一一对应的关系.线性表中的数据元素个数是有限的,其个数n称为线性表的长度,n=0时为空表.线性表是⼀种在实际中⼴泛使⽤的数据结构,常⻅的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构,也就说是连续的⼀条直线.但是在物理结构上并不⼀定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 相同特性:1️⃣逻辑结构:一定是线性的.2️⃣物理结构:不一定是线性的. 下面这是一张关于数据结构体系的详细图,里面包含的内容在后续中我都会一一介绍.

2.顺序表

2.1概念和结构

概念:线性表的存储顺序是指,在内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素.采用顺序存储结构的线性表称为顺序表.

顺序表的结构:1️⃣逻辑结构:线性的.2️⃣物理结构:线性的. 顺序表和数组的区别？顺序表的底层结构是数组,对数组的封装,实现了常⽤的增删改查等接⼝.

2.2分类

2.2.1静态顺序表

概念:使⽤定⻓数组存储元素.

静态顺序表缺陷:空间给少了不够⽤,给多了造成空间浪费.

2.2.2动态顺序表

动态顺序表:能在一定程度上降低空间浪费.

2.3动态顺序表的实现(初始化、头尾的增删、指定位置的增删、顺序表的销毁)

//初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//判断容器容量是否足够，不够就需要扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		//增容
		//realloc第二个参数，单位是字节,所以需要newCapacity * sizeof(SLDataType)来计算总字节数。
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//空间足够的情况下
	ps->arr[ps->size++] = x;
}//尾插的时间复杂度是O(1)

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	//简单的处理方式
	//if (ps == NULL)
	//{
	//	return;
	//}
	assert(ps != NULL);
	//判断空间是否足够
	SLCheckCapacity(ps);
	//将顺序表中所有数据向后挪动一位
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	++ps->size;
}//头插的时间复杂度是O(N)

//尾删
void SLPopBack(SL* ps)
{
	//ps：限制参数不能直接给NULL
	//ps->size：顺序表为空
	assert(ps && ps->size);
	--ps->size;
}//尾删的时间复杂度是O(1)

//头删
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}//头删的时间复杂度是0(N)

//指定位置之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	SLCheckCapacity(ps);
	//pos及之后的数据整体向后挪动一位
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
}//在指定位置之前插入数据的时间复杂度是O(N)

思考一下,在指定位置之后如何插入元素？

// 在指定位置pos之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    SLCheckCapacity(ps);
    // 将pos+1及之后的数据整体向后挪动一位
    for (int i = ps->size; i > pos + 1; i--)
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos + 1] = x;
    ++ps->size;
}//在指定位置pos之后插入数据的时间复杂度是O(N)

// 删除POS位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//pos之后的数据整体向前挪动一位
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}//删除POS位置的数据的时间复杂度是O(N)

//查找
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}//查找的时间复杂度是O(N)
//SLFind函数的作用是在顺序表(SL)中查找指定元素x,返回其所在位置的下标;若未找到,则返回-1.通过for循环遍历顺序表中的所有元素(从下标0到ps->size-1).若找到元素x(ps->arr[i] == x),则立即返回该元素的下标i.若循环结束后仍未找到元素x,则返回-1表示查找失败.

//销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}//SLDestroy函数的作用是销毁顺序表(SL)释放其动态分配的内存,并将相关属性重置,避免内存泄漏.assert(ps)确保传入的顺序表指针ps不为空.若ps->arr不为空(即存在动态分配的内存),调用free函数释放该内存.将ps->arr设为 NULL(避免野指针),并将ps->size(元素个数)和ps->capacity(容量)都重置为0,完成顺序表的销毁.

2.4动态顺序表的完整代码实现

SeqList.c

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

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	++ps->size;
}
void SLPopBack(SL* ps)
{
	assert(ps && ps->size);
	--ps->size;
}
void SLPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
void SLPopFront(SL* ps)
{
	assert(ps && ps->size);
	for (int i = 0; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
  SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	++ps->size;
}
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	--ps->size;
}
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SLDestroy(SL* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;      
	int capacity;  
}SL;
void SLPrint(SL* ps);//打印
void SLInit(SL* ps);//初始化
void SLDestroy(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);// 删除POS位置的数据
int SLFind(SL* ps, SLDataType x);//查找

test.c

#include"SeqList.h"

void test01()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);
	SLPushBack(&sl, 5);
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);//4 3 2 1
	SLPushFront(NULL, 1);
	SLPopBack(&sl);
	SLPrint(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);
	SLPopBack(&sl);
	SLPrint(&sl);
	SLPopBack(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLPopFront(&sl);
	SLPrint(&sl);
	SLInsert(&sl, 4, 100);
	SLPrint(&sl);
  SLErase(&sl, 3);
	SLPrint(&sl);
	int find = SLFind(&sl, 22222);
	if (find != -1)
	{
		printf("\n");
	}
	else {
		printf("\n");
	}
	SLDestroy(&sl);
}
int main()
{
	test01();
	return 0;
}

2.5顺序表的算法题

移除元素

//思路1
int removeElement(int* nums, int numsSize, int val) {
    int k = numsSize; 
    int i = 0;
    while (i < k) {
        if (nums[i] == val) {
            for (int j = i; j < k - 1; j++) {
                nums[j] = nums[j + 1];
            }
            k--; 
        } else {
            i++; 
        }
    }
    return k;
}

//思路2
int removeElement(int* nums, int numsSize, int val) {
    int* tmp = (int*)malloc(numsSize * sizeof(int));
    if (tmp == NULL) {
        return -1;
    }
    int k = 0; 
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != val) {
            tmp[k] = nums[i];
            k++;
        }
    }
    for (int i = 0; i < k; i++) {
        nums[i] = tmp[i];
    }
    free(tmp);
    tmp = NULL; 
    return k;
}

//思路3(本人提倡用这种方法-->双指针法)
int removeElement(int* nums, int numsSize, int val) {
    int dst=0; int src=0;
    while(src<numsSize)
    {
        if(nums[src]!=val)
        {
            nums[dst]=nums[src];
            dst++;
        }
        src++;
    }
    return dst;
}

删除有序数组中的重复项

int removeDuplicates(int* nums, int numsSize) {
    int dst=0,src=dst+1;
    while(src<numsSize)
    {
        if(nums[src]!=nums[dst]&& ++dst!=src)
        {
            nums[dst]=nums[src];
        }
        src++;
    }
    return dst+1;
}

合并两个有序数组

//思路1
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 1. 合并数组：将nums2的元素放入nums1的尾部
    for (int i = 0; i < n; i++) {
        nums1[m + i] = nums2[i];
    }
    // 2. 冒泡排序：对合并后的nums1进行排序
    int total = m + n;  // 合并后的总长度
    for (int i = 0; i < total; i++) {
        // 每轮将最大的元素"冒泡"到末尾，内层循环范围逐渐缩小
        for (int j = 0; j < total - i - 1; j++) {
            if (nums1[j] > nums1[j + 1]) {
                // 交换相邻元素
                int temp = nums1[j];
                nums1[j] = nums1[j + 1];
                nums1[j + 1] = temp;
            }
        }
    }
}

//思路2
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 创建临时数组，大小为m + n（与nums1总容量一致）
    int* tmp = (int*)malloc((m + n) * sizeof(int));
    int i = 0; // 指向nums1中有效元素的指针
    int j = 0; // 指向nums2中元素的指针
    int k = 0; // 指向临时数组的指针
    // 同时遍历两个数组，比较元素大小并放入临时数组
    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            tmp[k++] = nums1[i++];
        } else {
            tmp[k++] = nums2[j++];
        }
    }
   // 将nums1中剩余元素放入临时数组
    while (i < m) {
        tmp[k++] = nums1[i++];
    }
    // 将nums2中剩余元素放入临时数组
    while (j < n) {
        tmp[k++] = nums2[j++];
    }
    // 将临时数组的结果复制回nums1
    for (int p = 0; p < m + n; p++) {
        nums1[p] = tmp[p];
    }
    free(tmp);
}

//思路3
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1=m-1;
    int l2=n-1;
    int l3=m+n-1;
    while(l1>=0&&l2>=0)
    {
        if(nums1[l1]>nums2[l2])
        {
            nums1[l3--]=nums1[l1--];
        }
        else{
            nums1[l3--]=nums2[l2--];
        }
    }
    while(l2>=0)
    {
        nums1[l3--]=nums2[l2--];
    }
}

2.6顺序表问题与思考

1️⃣中间/头部的插⼊删除,时间复杂度为O(N). 2️⃣增容需要申请新空间,拷⻉数据,释放旧空间.会有不⼩的消耗. 3️⃣增容⼀般是呈2倍的增⻓,势必会有⼀定的空间浪费.例如当前容量为100,满了以后增容到200,我们再继续插⼊了5个数据,后⾯没有数据插⼊了,那么就浪费了95个数据空间. 思考:如何解决以上问题呢? 头部的的插入删除的时间复杂度能变为:O(1)吗？能不能不需增容呢？能不能不浪费空间呢？

敬请期待下一篇文章内容:数据结构之链表！