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

初阶数据结构之顺序表的实现

article 2024/11/1 22:52:26

1 线性表

什么是线性表呢？

线性表是n个具有相同特性的数据元素的有限序列。
常见的线性表：顺序表，链表，栈，队列，字符串。

线性表在逻辑上是线性结构，在物理结构上不一定是线性的。线性表在物理存储时，通常是以数组或链式结构形式存储。

线性表大致分为两种：顺序表和链表。基于这两种最基本的结构才能够实现更复杂的数据结构。今天我们着重来了解顺序表的实现。

2 顺序表

概念：线性表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，因此一般情况下采用数组存储。

在这里插入图片描述

顺序表既然是用数组实现的，那么顺序表和数组有什么区别呢？举个例子大家就明白了。这就好比玉米羹，通过厨师一番操作，给玉米羹加上了料汁，饰品，摆盘等，摇身一变就变成宫廷玉液羹。而在这里，顺序表的底层结构采用数组，对数组进行封装，实现了常用的增删改查等接口，就成为了顺序表。

2.1 顺序表的选择

那么新的问题又来了，我们到底该采用静态顺序表还是动态顺序表？

在这里插入图片描述

可以清楚的看到，静态顺序表能够存储的数据个数是有限的。如果数组满了，就无法对新的数据进行存储。可能会有人说，那简单啊，把数组的容量给大一点不就好了。那如果只是多存储了一个数据呢？那岂不是会有很多空间被浪费掉。

静态顺序表的缺陷：空间给少了不够用，给大了空间浪费。

在这里插入图片描述

动态顺序表可根据数据个数对空间大小进行调整。那么到底该如何调整呢？当数组空间满了的时候，我们到底扩几倍呢？如果倍数太大，有可能会造成空间浪费，倍数太小，空间不够用。我们一般扩两倍，因为这样不仅实现了增容，而且有利于减少空间的浪费。

2.2 顺序表的实现

2.1.1 顺序表的定义

typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int capacity;//顺序表的容量
	int size;//实际存储数据的个数
}SL;

typedef int SLDataType 对int进行类型重命名，如果需要存储
char类型数据，只需要修改这里的int就可以了。十分的方便，
代码也不容易出现错误。

2.1.2 顺序表的接口

//初始化
void SeqListInit(SL* ps);

//打印顺序表
void DisplaySeqList(SL* ps);

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

//尾删
void SeqListPopBack(SL* ps);

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

//头删
void SeqListPopFront(SL* ps);

//顺序表查找
int SeqListFind(SL* ps, SLDataType x);

//从指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x);

//从指定位置删除数据
void SeqListErase(SL* ps, int pos);

//从指定位置修改数据
void SeqListModify(SL* ps, int pos, SLDataType x);

//销毁空间
void SeqListDestroy(SL* ps);

2.1.3 顺序表的初始化

//初始化
void SeqListInit(SL* ps)
{
	assert(ps != NULL);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

assert(ps!=NULL);断言ps不能为空指针，否则将导致野指针的出现，
同时会对有问题的文件和行号进行报错。

2.1.4 顺序表的打印

//打印顺序表
void DisplaySeqList(SL* ps)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		printf("%d ", ps->a[i]);
		i++;
	}
	printf("\n");
}

ps->size是顺序表的有效数据的个数。数组下标从0开始，对i进行初
始化为0，使用下标引用操作符[]对顺序表进行访问，循环打印。

2.1.5 检查顺序表的容量

//检查容量
void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//初始化时顺序表的容量是0，没有空间，因此无法存储数
		//据，使用三目操作符给顺序表一个初始的容量,同时当顺
		//序表容量满的时候，进行增容
		SLDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->capacity = newcapacity;
		//开辟newcapacity*sizeof(SLDataType)个字节空间
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		//如果开辟失败，则退出程序
		if (NULL == tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		//开辟成功，将新空间的地址交给ps->a进行维护
		ps->a = tmp;
	}
}

在这里插入图片描述

检查顺序表的容量，当容量满了的时候就进行增容。

2.1.6 顺序表尾插

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	//检查顺序表的容量，满了就增容
	SeqListCheckCapacity(ps);
	//插入数据
	ps->a[ps->size] = x;
	//记录顺序表有效数据的个数
	ps->size++;
}

在这里插入图片描述

2.1.7 顺序表尾删

//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//顺序表不能为空，为空意味着顺序表中没有数据，不需要删除
	assert(ps->size > 0);
	ps->size--;
}

这里需要注意的是assert(ps->size>0)(断言顺序表不能为空)，如果没
有这段代码，顺序表会无限制的删除，极易造成越界。

在这里插入图片描述

2.1.8 顺序表头插

//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	//end记录数组最后一个元素的下标
	int end = ps->size - 1;
	//将数组元素整体向后移
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//插入数据
	ps->a[0] = x;
	//更新数组有效数据的个数
	ps->size++;
}

在这里插入图片描述
每次插入数据之前都要先判断顺序表容量是否足够。

2.1.9 顺序表头删

//头删
void SeqListPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//开始挪动数据的起始位置
	int start = 1;
	//将数组元素整体向前移
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	//每删除一次数据，顺序表有效数据个数-1
	ps->size--;
}

在这里插入图片描述

assert(ps->size>0)说明顺序表中有数据才可以删除，否则不需要删除

2.1.10 顺序表查找

//顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}

对数组进行遍历，如果与查找的数字相等，则返回下标，否则继续查找。循环结束之后还未找到，说明顺序表中没有该数据，返回-1。

2.1.11 从指定位置之前插入数据

//从指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断pos的有效性
	assert(pos >= 0 && pos < ps->size);
	//检查顺序表的容量
	SeqListCheckCapacity(ps);
	//记录数组最后一个元素的下标
	int end = ps->size - 1;
	//挪动数据
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//插入数据
	ps->a[pos] = x;
	//更新顺序表有效数据的个数
	ps->size++;
}

在这里插入图片描述

插入数据之前先判断顺序表的容量和pos位置的有效性，再将元素往后移，为pos位置腾出空位，最后插入元素，更新ps->size。

2.1.12 从指定位置删除数据

//从指定位置删除数据
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//顺序表为空的情况
	assert(ps->size > 0);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表至少有一个数据
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}

在这里插入图片描述

删除数据之后，一定不能忘记ps->size--

2.1.13 从指定位置修改顺序表

//从指定位置修改顺序表
void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表为空的情况
	assert(ps->size > 0);
	ps->a[pos] = x;
}

使用下标引用操作符[]去访问数组，直接修改就可以了。

2.1.14 销毁顺序表

//销毁空间
void SeqListDestroy(SL* ps)
{
	assert(ps);
	//ps->a有可能是NULL
	if(ps->a!=NULL)
	{
		free(ps->a);
		ps->a = NULL;
	}
	ps->capacity = 0;
	ps->size = 0;
}

数组是动态开辟出来的空间，程序结束之后要还给操作系统。否则会
造成内存泄漏。因为计算机内存空间也是有限的，如果不还给操作系
统，内存就会越来越少。

3 完整代码的实现

seqlist.h头文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLDataType;
//动态顺序表
typedef struct SeqList
{
	SLDataType* a;
	int capacity;//顺序表的容量
	int size;//实际存储数据的个数
}SL;


//初始化
void SeqListInit(SL* ps);

//打印顺序表
void DisplaySeqList(SL* ps);

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

//尾删
void SeqListPopBack(SL* ps);

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

//头删
void SeqListPopFront(SL* ps);

//顺序表查找
int SeqListFind(SL* ps, SLDataType x);

//从指定位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x);

//从指定位置删除数据
void SeqListErase(SL* ps, int pos);

//从指定位置修改顺序表
void SeqListModify(SL* ps, int pos, SLDataType x);

//销毁空间
void SeqListDestroy(SL* ps);

seqlist.c源文件

#define _CRT_SECURE_NO_WARNINGS
#include"seqlist.h"


//初始化
void SeqListInit(SL* ps)
{
	assert(ps != NULL);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

//打印顺序表
void DisplaySeqList(SL* ps)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		printf("%d ", ps->a[i]);
		i++;
	}
	printf("\n");
}

//检查容量
void SeqListCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		ps->capacity = newcapacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (NULL == tmp)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
	}
}

//销毁空间
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

//尾删
void SeqListPopBack(SL* ps)
{
	assert(ps);
	//顺序表为空的情况
	assert(ps->size > 0);
	ps->size--;
}

//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

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

//顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	while (i < ps->size)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
		i++;
	}
	return -1;
}
//从指定位置之前插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SeqListCheckCapacity(ps);
	assert(pos >= 0 && pos < ps->size);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

//从指定位置删除数据
void SeqListErase(SL* ps, int pos)
{
	assert(ps);
	//顺序表为空的情况
	assert(ps->size > 0);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表至少有一个数据
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}

//从指定位置修改顺序表
void SeqListModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//判断pos位置的有效性
	assert(pos >= 0 && pos < ps->size);
	//顺序表为空的情况
	assert(ps->size > 0);
	ps->a[pos] = x;
}

test.c测试文件

#define _CRT_SECURE_NO_WARNINGS
#include"seqlist.h"

void TestSeqList1()
{
	SL s1;

	SeqListInit(&s1);

	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListPushBack(&s1, 5);

	DisplaySeqList(&s1);

	//SeqListDestroy(&s1);

	SeqListPopBack(&s1);
	SeqListPopBack(&s1);
	SeqListPopBack(&s1);

	DisplaySeqList(&s1);

	SeqListPushFront(&s1, 10);
	SeqListPushFront(&s1, 20);
	SeqListPushFront(&s1, 30);
	SeqListPushFront(&s1, 40);

	DisplaySeqList(&s1);

	SeqListPopFront(&s1);
	SeqListPopFront(&s1);

	DisplaySeqList(&s1);

	SeqListInsert(&s1, 3, 50);
	SeqListInsert(&s1, 2, 60);
	SeqListInsert(&s1, 5, 70);

	DisplaySeqList(&s1);

	int ret = SeqListFind(&s1, 10);
	if (ret >= 0)
	{
		printf("找到了,下标是%d\n", ret);
	}

	SeqListErase(&s1, 0);
	SeqListErase(&s1, 0);

	DisplaySeqList(&s1);

	SeqListModify(&s1, 3, 80);

	DisplaySeqList(&s1);

	SeqListDestroy(&s1);

}
int main()
{
	TestSeqList1();
	return 0;
}

总结：今天的顺序表到这里就结束了。觉得还ok的伙伴点点关注，收藏和点赞吧。


http://www.kler.cn/a/375010.html

相关文章：

  • 『 Linux 』网络传输层 - TCP(二)
  • 如何保护网站安全
  • HT8787B 可任意限幅、内置自适应升压的2x9.0W立体声音频功放
  • 学Linux的第五天
  • 【新闻转载】RansomHub勒索威胁曝光：OMA机场运营面临3TB数据泄露危机
  • 【第一个qt项目的实现和介绍以及程序分析】【正点原子】嵌入式Qt5 C++开发视频
  • tkinter 走进现代化【一】 - 登录页
  • 从 classList 到 DOMTokenList: 简化类名管理的工具
  • git入门教程11：git安全性
  • 2024年【制冷与空调设备安装修理】考试总结及制冷与空调设备安装修理作业模拟考试
  • 【SSH访问Termux】
  • 时间序列算法---ARIMA
  • 推荐一款功能强大的媒体播放管理：Zoom Player MAX
  • BERT的中文问答系统26
  • 20241101编译Rockchip原厂的RK3566平台的Buildroot【使用荣品的DTS】
  • 91.【C语言】数据结构之单向链表的头删和尾删
  • MySQL 日志之 binlog 格式 → 关于 MySQL 默认隔离级别的探讨
  • 如何实现图片懒加载，原生 + React 实现方式
  • 数据库管理系统的ACID都各自是什么？
  • 遗传算法：AI 借鉴生物进化的优化方法
  • HTML练习题 :新闻列表 包含盒子模型,内边距,外边距,鼠标悬停
  • 数据结构模拟题［二］
  • scrapy爬取名人名言
  • 安卓基础001
  • .NET Core WebApi第4讲：控制器、路由
  • LeetCode每日一题3165---不包含相邻元素的子序列的最大和