数据结构-顺序表各项功能的实现

这篇具有很好参考价值的文章主要介绍了数据结构-顺序表各项功能的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

线性表是n个具有相同属性的有限数列,常见的线性表有:=顺序表,链表,栈,队列,字符串…
线性表在逻辑上是线性结构,也就是说连成一条直线,但是在物理结构上不一定连续,线性表在物理上存储是,通常以数组和链式结构的形式进行存储。
本章,我们将通过顺序表的实现来研究顺序表


一、"SeqList.h"部分

一个大的工程,永远不可能只有一个源文件,所以我们要善于将一个工程分成几个部分来完结,该头文件则是包含了库函数的引用头文件及函数的定义,包括了几个顺序表的功能,这里我们将其一一列出
需要注意的部分博主已经注释

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;//指向动态开辟数组
	int size;//存储有效数据个数
	int capacity;//空间大小
}SeqList;

// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);//初始化
void SeqListDestroy(SeqList* ps);//消除

void SLCheckCapacity(SeqList* ps);//扩容空间
void SeqListPrint(SeqList* ps);//打印
void SeqListPushBack(SeqList* ps, SLDateType x);//尾插
void SeqListPopBack(SeqList* ps);//尾删
void SeqListPushFront(SeqList* ps, SLDateType x);//头插
void SeqListPopFront(SeqList* ps);//头删


// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除low位置的值
void SeqListErase(SeqList* ps, int low);

下面我们就要围绕着头文件进行程序的编写

二、"SeqList.c"部分

1.初始化

既然是动态规划内存,那便少不了malloc,relloc之类动态内存函数的使用,这里,我们使用malloc进行动态开辟数组空间
代码如下:

void SeqListInit(SeqList* ps)
{
	ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

初始化比较简单,这里我们就讲到这

2.销毁

我们开辟空间后,不在使用时,要及时销毁,对于释放内存空间,且与malloc经常一起出没的,那便是free函数释放内存后,别忘了讲指针置空

void SeqListDestroy(SeqList* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

3.扩容及打印

有时候我们在添加数时可能会发生空间满了的情况,所以这时候我们就要扩容,但扩容用哪个动态内存函数好呢,答案肯定是realloc,因为它能更灵活的对内存大小进行调整
注:realloc开辟的内存空间千万不能用free释放,因为realloc自己带有释放功能,盲目使用可能会造成意想不到的后果

void SLCheckCapacity(SeqList* ps)//扩容
{
	//满了就要去扩容
	if (ps->size == ps->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

打印就比较简单了,基本上写代码就能用,这里我们之间上代码

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

4.尾插及尾删

尾插,顾名思义就是在数组结尾处插入一个数字,这里我们的有效数字个数size就得加1,并防止ps->size>=ps->capacity即可

void SeqListPushBack(SeqList* ps, SLDateType x)//尾插
{
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

尾删也就是讲最后一位数字删去,这里我们要防止出现数组没数据的情况即(ps->size=0).
这里我们可以采用断言函数来控制size的范围

void SeqListPopBack(SeqList* ps)//尾删
{
	//暴力删除
	assert(ps->size > 0);
	ps->size--;

5.头插及头删

这两个也类似与上面的尾插和尾删,同样得注意ps->size=ps->capacity及ps->size=0的情况,这里与数组的首尾增添相似,这里就不细讲了,直接上代码

void SeqListPushFront(SeqList* ps, SLDateType x)//头插
{
	SLCheckCapacity(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(SeqList* ps)//头删
{
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
		ps->a[i] = ps->a[i + 1];
	ps->size--;
}

6.顺序表查找

顺序表的查找原理与数组查找大致一致,读者可以根据数组查找来复刻出顺序表查找的方式,上代码

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

7.顺序表在pos位插入x

这里插入问题首先还是要考虑ps->size=ps->capacity的情况,如何插入一个数字与数组同样是大相径庭,故这里就不细讲

void SeqListInsert(SeqList* ps, int pos, SLDateType x)// 顺序表在pos位置插入x
{
	SLCheckCapacity(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++;
	SeqListPrint(ps);
}

8.顺序表删除low位置的数

提到删除,第一时间想到会不会出现ps->size=0的情况,然后同样利用数组知识,写出代码

void SeqListErase(SeqList* ps, int low)// 顺序表删除low位置的值
{
	assert(low>=0&&low<ps->size);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (i != low - 1)
			printf("%d ", ps->a[i]);
	}
}

顺序表的核心部分到此结束了,下面我们来进行模拟实现


三、"text.c"部分

这里我们对照函数部分写出对应的实现方法,来确定函数是否有误,这里我们直接放代码

#include "SeqList.h"



void TestSeqList1()//尾插尾删
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushBack(&sl, 3);
	SeqListPushBack(&sl, 4);

	SeqListPopBack(&sl);
	SeqListPrint(&sl);

	SeqListDestroy(&sl);
}

void TestSeqlist2()//头插头删
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushFront(&sl, 1);
	SeqListPushFront(&sl, 2);
	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);

	SeqListPopFront(&sl);
	SeqListPrint(&sl);

	SeqListDestroy(&sl);
}

void TestSeqlist3()//查找数
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);
	SeqListPrint(&sl);

	int ret = SeqListFind(&sl, 2);
	if (ret == 1)
	{
		printf("找到了,下标为:%d\n", ret);
	}
	else
		printf("该数字不在该顺序表里\n");
	//SeqListPrint(&sl);

	SeqListDestroy(&sl);
}

void TestSeqlist4()//顺序表在pos位置插入x,在low删除数字
{
	SeqList sl;
	SeqListInit(&sl);
	SeqListPushBack(&sl, 1);
	SeqListPushBack(&sl, 2);
	SeqListPushFront(&sl, 3);
	SeqListPushFront(&sl, 4);
	printf("插入前:\n");
	SeqListPrint(&sl);

	printf("插入后:\n");
	SeqListInsert(&sl, 3, 5);

	printf("删除low位置数字后:\n");
	SeqListErase(&sl, 2);

	SeqListDestroy(&sl);
}

int main()
{
	printf("尾插尾删用例\n");
	TestSeqList1();
	printf("头插头删用例\n");
	TestSeqlist2();
	printf("顺序表查找数据用例\n");
	TestSeqlist3();
	printf("顺序表在pos位置插入x,删除low位置的数用例\n");
	TestSeqlist4();
	return 0;
}

博主使用的用例结果如下图所示:
数据结构-顺序表各项功能的实现,数据结构,代理模式

结语

关于顺序表的内容即实现到这里就结束了,希望可以帮到各位文章来源地址https://www.toymoban.com/news/detail-621394.html

到了这里,关于数据结构-顺序表各项功能的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】实现顺序表

    顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下 采用数组存储 。 顺序表与通讯录类似,可以完成 增删查改 等功能。在此基础上,还可以实现 头插、头删、尾插、尾删以及某位置的插入和删除 1.创建多文件 用多文件的好处在通讯录一文

    2024年02月12日
    浏览(70)
  • 数据结构-二叉树·堆(顺序结构的实现)

    🎉个人名片: 🐼作者简介:一名乐于分享在学习道路上收获的大二在校生 🐻‍❄个人主页🎉:GOTXX 🐼个人WeChat : ILXOXVJE 🐼本文由GOTXX原创,首发CSDN🎉🎉🎉 🕊系列专栏:零基础学习C语言----- 数据结构的学习之路 🐓每日一句:如果没有特别幸运,那就请特别努力!🎉

    2024年02月05日
    浏览(47)
  • 【数据结构】顺序队列模拟实现

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 一、队列的基本概念

    2024年02月10日
    浏览(40)
  • 【数据结构】二叉树的顺序结构及实现

    目录 1. 二叉树的顺序结构 2. 堆的概念及结构 3. 堆的实现 3.1 堆向下调整算法 3.2 堆的创建 3.3 建堆时间复杂度 3.4 堆的插入 3.5 堆的删除 3.6 堆的代码实现 4. 堆的应用 4.1 堆排序 4.2 TOP-K问题 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉

    2024年02月08日
    浏览(42)
  • 【数据结构】结构实现:顺序存储模式实现堆的相关操作

    🚩 纸上得来终觉浅, 绝知此事要躬行。 🌟主页:June-Frost 🚀专栏:数据结构 🔥该文章着重讲解了使用顺序结构实现堆的插入和删除等操作。  二叉树的顺序存储是指将二叉树中的所有节点按照一定的顺序(一层一层)存储到一个数组中。  我们可以通过数组下标来表示

    2024年02月08日
    浏览(49)
  • 数据结构队列例题一顺序实现

    仅供个人复习使用

    2024年02月06日
    浏览(45)
  • 【数据结构】--顺序表的实现

    什么是顺序表?顺序表(SeqList)是线性表中的一类。而线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、字符串、栈、队列... 注意:线性表在逻辑上是线性结构,也就是说是一条连续的直线。但在

    2024年04月17日
    浏览(47)
  • 数据结构: 线性表(顺序表实现)

    线性表(linear list)是 n 个具有相同特性的数据元素的有序序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表: 顺序表,链表,栈,队列,字符串… 顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删

    2024年02月14日
    浏览(50)
  • 【(数据结构)- 顺序表的实现】

    先来看两张图片 数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据? 常见的数值1、2、3、4…、教务系统里保存的用户信息(姓名、性别、年龄、学历等等)、网页里肉眼可以看到的信息(文字、图片、视频等等),这些都是数据 什么是结构? 当我们想要使用大

    2024年02月07日
    浏览(51)
  • 数据结构:顺序表(C实现)

    个人主页 水月梦镜花 个人专栏 C语言 ,数据结构 顺序表是用一段物理结构连续的存储单元依次存储数据元素的线性结构,一般采用数组存储。 顺序表一般分为两种: 静态顺序表:使用定长数组实现 动态顺数表:使用动态开辟的数组实现 本篇文章,顺序表是使用动态开辟的

    2024年02月15日
    浏览(26)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包