数据结构——顺序表

发布于：2025-08-14 ⋅ 阅读:(26) ⋅ 点赞:(0)

目录

1 数据结构的相关概念

数据结构指计算机内部存储数据，将数据组织起来的方式
数据结构主要包括逻辑结构和物理结构
逻辑结构
指元素与元素之间的逻辑关系
物理结构
指元素在内存中的存储方式

2 线性表的概念

线性表是一种可以容纳 n 个元素的数据结构，一般来说，线性表在逻辑结构上一定是连续的，但是在物理结构上不一定是连续的
常见的线性表有：顺序表，链表，栈，队列等
比方说，下面的数组，它也可以称为是线性表，因为它的逻辑结构是连续的（各个元素在逻辑上相邻，排成了一条线），而对于数组来讲，它的物理结构也是连续的（元素的存储空间连续）

在这里插入图片描述

3 顺序表的概念

顺序表是一种逻辑结构连续，物理结构也连续的数据结构，它由数组来实现，分为动态顺序表和静态顺序表两种
看到这里，可能会有相应的疑问，顺序表由数组来实现，为什么不直接使用数组呢？
因为数组本身提供的操作太少，只有根据下标访问元素，存放元素等操作，而顺序表则是将数组需要的大部分操作都封装了起来，方便使用

3.1 静态顺序表

静态顺序表指使用静态数组来实现的顺序表，它的结构体声明如下：

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType a[N]; //数组
	int size; //有效数据个数	
}SL;

定义 SLDataType 是为了方便类型的更改，因为顺序表肯定要能存储各式各样的数据
定义 N 则是为了方便更改数组的大小
静态顺序表的缺点是，由于不知道数组该给多大的空间，所以空间给小了会不够用，空间给大了则会浪费空间

3.2 动态顺序表

动态顺序表指使用动态开辟的空间来存放数据的顺序表，结构体声明如下：

//动态顺序表
#define int SLDataType
typedef struct SeqList
{
	SLDataType* arr; //动态空间
	int size; //顺序表有效元素个数
	int capacity; //顺序表总大小
}SL;

动态顺序表规避了静态顺序表的缺点，开始时给出较小的空间，在用户需要使用更大的空间时，进行扩容即可

4 动态顺序表的相关操作

4.1 动态顺序表的初始化

//初始化顺序表
void SLInit(SL* ps)
{
	ps->arr = NULL; //初始未开辟空间
	ps->size = 0; //初始有效元素为0
	ps->capacity = 0; //初始容量为0
}

在这里，因为要更改顺序表内部结构的值，所以使用传址调用

4.2 动态顺序表的扩容

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity) //说明当前顺序表已满，需要扩容
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //防止顺序表大小为0的情况

		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL) //防止开辟新空间失败
			assert(tmp);

		ps->arr = tmp;
		ps->capacity = newCapacity; //设置新大小
	}
}

动态顺序表在扩容时，分为两个情况
空间为 0 的情况：在这个情况下，有效元素个数 size 为 0，顺序表大小 capacity 也为 0，动态开辟 4 个空间供用户使用
空间满了的情况：在这个情况下，有效元素个数 size 就等于顺序表大小 capacity，扩充两倍的容量供用户使用
在这里插入图片描述

4.3 动态顺序表的尾插操作

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps); //防止空指针访问

	SLCheckCapacity(ps); //检查是否需要扩容

	ps->arr[ps->size++] = x; //存放数据
}

尾插指在顺序表的尾部放入元素
动态顺序表在进行尾插时，主要考虑两个情况
空间足够时：直接在 size 指向的位置插入即可
在这里插入图片描述

空间不够时：要先进行扩容，再向 size 指向的位置插入元素
在这里插入图片描述

4.4 动态顺序表的头插操作

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[0] = x;
	ps->size++;

}

头插指在顺序表的起始位置插入元素
动态顺序表在进行头插时，要考虑两个情况
空间足够时
将顺序表的元素整体向后移动一位，再将 x 插入到头部即可
在这里插入图片描述
空间不够时
对原顺序表的空间进行扩容，再将元素整体向后移动，最后把 x 插入到头部即可
在这里插入图片描述

4.5 动态顺序表的尾删操作

void SLPopBack(SL* ps)
{
	assert(ps); //防止使用空指针
	assert(ps->size); //防止对空顺序表进行删除操作
	ps->size--;
}

在尾删时，只需要让有效数据的数量减一，进行逻辑上的删除即可

4.6 动态顺序表的头删操作

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0;i < ps->size - 1;++i)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

在执行头删操作时，需要将后方的数据全部向前移动一位，通过数据覆盖的方式来达到删除的效果
在这里插入图片描述

4.7 顺序表指定位置插入元素

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++;

}

要在指定位置插入元素，就需要分空间足够和不够的两种情况
空间足够时： 将pos指向的位置及之后的元素整体向后移动，最后将 x 插入至 pos 指向的位置即可
空间不够时：先进行扩容，将pos指向的位置及之后的元素整体向后移动，最后将 x 插入至 pos 指向的位置即可
大体流程如图：
在这里插入图片描述

4.8 顺序表指定位置删除元素

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	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--; //有效元素个数-1
}

要在指定位置删除元素，就需要将 pos 位置后的元素全部向前移动一位，通过覆盖的方式来删除元素
在这里插入图片描述

4.9 顺序表元素的查找

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(ps->size);

	for (int i = 0;i < ps->size;++i)
	{
		if (ps->arr[i] == x)
			return i;
	}

	return -1;

}

在顺序表中查找元素，只需要遍历顺序表，比对每个元素的值，最终查找成功返回对应元素的下标即可，查找失败返回 -1，返回 -1 是因为它是不存在的下标，也可以返回 -2，-3 等

4.10 打印顺序表的值

//输出
void SLPrint(SL s)
{
	for (int i = 0;i < s.size;++i)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

与打印数组的值类似，遍历顺序表，打印每个值即可

4.11 销毁顺序表

//删除顺序表
void SLDestory(SL* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

5 整体实现

seqList.h

//函数声明，头文件，结构体
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


//动态顺序表
#define SLDataType int
typedef struct SeqList
{
	SLDataType* arr;
	int size; //顺序表有效元素个数
	int capacity; //顺序表总大小
}SL;

//初始化顺序表
void SLInit(SL* ps);

//删除顺序表
void SLDestory(SL* ps);

//尾插
void SLPushBack(SL* ps, SLDataType x);

//头插
void SLPushFront(SL* ps, SLDataType x);

//输出
void SLPrint(SL s);

//尾删
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);

seqList.c

//函数具体的实现
#include "seqList.h"
//初始化顺序表
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//删除顺序表
void SLDestory(SL* ps)
{
	if (ps->arr != NULL)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//扩容
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity) //说明当前顺序表已满，需要扩容
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //防止顺序表大小为0的情况

		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL) //防止开辟新空间失败
			assert(tmp);

		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); //防止空指针访问

	SLCheckCapacity(ps); //检查是否需要扩容

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

	ps->arr[0] = x;
	ps->size++;

}

//输出
void SLPrint(SL s)
{
	for (int i = 0;i < s.size;++i)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

//尾删
void SLPopBack(SL* ps)
{
	assert(ps); //防止使用空指针
	assert(ps->size); //防止对空顺序表进行删除操作
	ps->size--;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(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);

	//将pos后方的元素整体向后移动一位
	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(ps->size);
	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--; //有效元素个数-1
}

//查找元素
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(ps->size);

	for (int i = 0;i < ps->size;++i)
	{
		if (ps->arr[i] == x)
			return i;
	}

	return -1;

}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布