【数据结构与算法】之顺序表及其实现!

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

目录

​编辑

1. 顺序表的概念及结构

2. 接口的实现

2.1 顺序表的初始化

2.2 检查顺序表容量是否已满

2.3 顺序表的尾插

​编辑

2.4 顺序表的尾删

2.5 顺序表的头插

2.6  顺序表的头删

2.7 顺序表在pos位置插入

2.8  顺序表在pos位置删除

2.9 顺序表的查找

2.10 顺序表的销毁

2.11 顺序表的打印

 3. 我在实现顺序表时的测试代码

4. 完结散花


【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

                                                                                个人主页:秋风起,再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言:悟已往之不谏,知来者犹可追

                                                                                        克心守己,律己则安!

1. 顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元以此存储数据的线性结构,一般情况下用数组存储。在数组上完成数据的增删查改~

1. 静态顺序表:用指定长度数组存储元素~

【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

2. 动态顺序表:用动态开辟的数组存储~

【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

2. 接口的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空 间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间 大小,所以下面我们实现动态顺序表。

我们创建一个Test.h里面包含了所有的接口函数声明和各种头文件的声明~

这样我们一个一个实现,正所谓天下难事必做于细~

#define _CRT_SECURE_NO_WARNINGS
#pragma once//避免头文件的多次包含
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLDataType;//便于类型的改动

//定义一个动态顺序表的结构体变量
typedef struct SeqList
{
	SLDataType* arr;
	size_t num;//记录有效数据的个数
	size_t capacity;//该顺序表的容量大小
}SL;//将该结构体类型重命名为SL

//加入增删查改接口

//1. 顺序表初始化
void SeqListInit(SL* p);

//2. 检查顺序表容量是否已满
void CheckSeqList(SL* p);

//3. 顺序表的尾插
void SeqListPushBack(SL* p, SLDataType x);

//4. 顺序表的尾删
void SeqListPopBack(SL* p);

//5. 顺序表的头插
void SeqListPushFront(SL* p, SLDataType x);

//6. 顺序表的头删
void SeqListPopFront(SL* p);

//7. 顺序表在pos位置插入
void SeqListInsert(SL* p, size_t pos,SLDataType x);

//8. 顺序表在pos位置删除
void SeqListErase(SL* p, size_t pos);

//9. 顺序表的查找
int SeqListFind(SL* p,SLDataType x);//如果该数字存在则返回该数字的下标,否则返回-1

//10 顺序表的销毁
void SeqListDestory(SL* p);

//11. 顺序表的打印
void SeqListPrint(SL* p);

我们将所有函数的实现放在SeqList.c文件中~

2.1 顺序表的初始化

(1) 代码实现
//1. 顺序表初始化
void SeqListInit(SL* p)
{
	assert(p);//判断指针的有效性
	p->arr = NULL;
	p->capacity = 0;
	p->num = 0;
}
(2) 复杂度分析
  • 时间复杂度:由于没有其他未知数的引入,所以所需时间是个常数,也就是O(1)。
  • 空间复杂度:动态开辟N个空间,所以空间复杂度为O(N)。

 注意我们这里一定要传址调用~

2.2 检查顺序表容量是否已满

(1) 代码实现

 注释写的很详细了,这里就不做过多的解释~

//2. 检查顺序表容量是否已满
void CheckSeqList(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == p->capacity)
	{
		 size_t newcapacity=p->capacity == 0 ? p->capacity = 4 : p->capacity * 2;
		//如果原来没有空间,就给上4,有的话就扩大为原来的两倍
		 SLDataType* ptr = (SLDataType*)realloc(p->arr, newcapacity * sizeof(SLDataType));//动态扩容
		 if (ptr == NULL)
		 {
			 perror("realloc fail;");
			 return;
		 }
		 //也可以用assert断言一下
		 p->arr = ptr;//开辟成功将地址传给arr
		 p->capacity = newcapacity;//更新容量
	}
}

2.3 顺序表的尾插

(1) 代码实现
//3. 顺序表的尾插
void SeqListPushBack(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//尾插前先判断有没有容量或容量够不够
	p->arr[p->num] = x;//尾部插入数据
	p->num++;//有效数加一
}

【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

(2) 复杂度分析
  • 时间复杂度:没有变量影响时间,时间复杂度为O(1)。
  • 空间复杂度:以最坏的情况考虑,会进行扩容,空间复杂度为O(N)。

2.4 顺序表的尾删

(1) 代码实现
//4. 顺序表的尾删
void SeqListPopBack(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//断言存在有效数据
	p->num--;//尾删一个数据
}

 【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

(2) 复杂度分析
  • 时间复杂度:没有变量影响时间,时间复杂度为O(1)。
  • 空间复杂度:没有变量影响空间,空间复杂度为O(1)。

2.5 顺序表的头插

(1) 代码实现
//5. 顺序表的头插
void SeqListPushFront(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//先判断容量是否满了
	size_t end = p->num;
	while (end)
	{
		p->arr[end] = p->arr[end - 1];//整体向后移动
		end--;
	}
	p->arr[0] = x;//头插
	p->num++;//有效数据加一
}

 【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

(2) 复杂度分析
  • 时间复杂度:因为从头部插入数据,后续数据需要依次覆盖,所以时间复杂度为O(N)。
  • 空间复杂度:因为可能会进行扩容,按最坏的情况来算,空间复杂度为O(N)。

2.6  顺序表的头删

(1) 代码实现
//6. 顺序表的头删
void SeqListPopFront(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//有数据才删除
	size_t begin = 1;
	while (begin<p->num)
	{
		p->arr[begin - 1] = p->arr[begin];//整体向前移动
		begin++;
	}
	p->num--;// 有效数据减一

}

【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构 整体往前挪,把头覆盖~

(2) 复杂度分析
  • 时间复杂度:因为需要往前覆盖数据,所以时间复杂度自然为O(N)。
  • 空间复杂度:因为并没有开辟其他空间,所以空间复杂度为O(1)。

2.7 顺序表在pos位置插入

(1) 代码实现
//7. 顺序表在pos位置插入
void SeqListInsert(SL* p, size_t pos, SLDataType x)
{
	assert(p);//判断指针的有效性
	assert(pos >= 0 && pos < p->num);//pos必须小于num并且大于等于0
	CheckSeqList(p);//判断容量是否满了
	for (int i = p->num; i >pos-1 ; i--)
	{
		p->arr[i] = p->arr[i - 1];//将pos后面的元素往后挪
	}
	p->arr[pos - 1] = x;//在pos位置加入数据
	p->num++;//有效个数加一
}

 【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

(2) 复杂度分析
  • 时间复杂度:需要依次覆盖,时间复杂度为O(N)。
  • 空间复杂度:可能需要扩容,空间复杂度为O(N)。

2.8  顺序表在pos位置删除

(1) 代码实现
//8. 顺序表在pos位置删除
void SeqListErase(SL* p, size_t pos)
{
	assert(p);//判断指针的有效性
	assert(pos>=0&&pos<p->num );//pos必须小于num并且大于等于0
	assert(p->num > 0);//有数据才能删除
	for (int i = pos; i <p->num; i++)
	{
		p->arr[i-1] = p->arr[i];//将pos后面的元素往后挪
	}
	p->num--;//有效个数减一
}

【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构

(2) 复杂度分析
  • 时间复杂度:需要依次覆盖,时间复杂度为O(N)。
  • 空间复杂度:没有额外的空间消耗,空间复杂度为O(1)。

2.9 顺序表的查找

(1) 代码实现

遍历数组查找~

//9. 顺序表的查找
int SeqListFind(SL* p, SLDataType x)//如果该数字存在则返回该数字的下标,否则返回-1
{
	assert(p);//断言
	for (int i = 0; i < p->num; i++)
	{
		if (p->arr[i] == x)
		{
			return i;//查到返回下标
		}
	}
	return -1;//没有查到
}
(2) 复杂度分析
  • 时间复杂度:以最坏的情况分析,时间复杂度为O(N)。
  • 空间复杂度:并没有格外的空间消耗,空间复杂度为O(1)。

2.10 顺序表的销毁

(1) 代码实现
//10 顺序表的销毁
void SeqListDestory(SL* p)
{
	assert(p);//判断指针的有效性
	free(p->arr );//释放动态内存开辟的空间
	p->arr = NULL;
	p->capacity = 0;//容量置为0
	p->num = 0;//有效个数置为0
}
(2) 复杂度分析
  • 时间复杂度:没有额外的时间消耗,时间复杂度为O(1)。
  • 空间复杂度:没有额外的空间消耗,空间复杂度为O(1)。

2.11 顺序表的打印

(1) 代码实现
//11. 顺序表的打印
void SeqListPrint(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == 0)
	{
		printf("顺序表为空!\n");
		return;
	}
	for (int i = 0; i < p->num; i++)
	{
		printf("%d ", p->arr[i]);//打印数据
	}
	printf("\n");
}
(2) 复杂度分析
  • 时间复杂度:因为会打印顺序表中的所有数据,所以时间复杂度为O(N)。
  • 空间复杂度:打印顺序表并不需要开辟格外的空间,所以空间复杂度为O(1)。

 3. 完整代码

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include"Test.h"


//接口函数的实现

//1. 顺序表初始化
void SeqListInit(SL* p)
{
	assert(p);//判断指针的有效性
	p->arr = NULL;
	p->capacity = 0;
	p->num = 0;
}

//2. 检查顺序表容量是否已满
void CheckSeqList(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == p->capacity)
	{
		 size_t newcapacity=p->capacity == 0 ? p->capacity = 4 : p->capacity * 2;
		//如果原来没有空间,就给上4,有的话就扩大为原来的两倍
		 SLDataType* ptr = (SLDataType*)realloc(p->arr, newcapacity * sizeof(SLDataType));//动态扩容
		 if (ptr == NULL)
		 {
			 perror("realloc fail;");
			 return;
		 }
		 //也可以用assert断言一下
		 p->arr = ptr;//开辟成功将地址传给arr
		 p->capacity = newcapacity;//更新容量
	}
}

//3. 顺序表的尾插
void SeqListPushBack(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//尾插前先判断有没有容量或容量够不够
	p->arr[p->num] = x;//尾部插入数据
	p->num++;//有效数加一
}

//4. 顺序表的尾删
void SeqListPopBack(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//断言存在有效数据
	p->num--;//尾删一个数据
}

//5. 顺序表的头插
void SeqListPushFront(SL* p, SLDataType x)
{
	assert(p);//判断指针的有效性
	CheckSeqList(p);//先判断容量是否满了
	size_t end = p->num;
	while (end)
	{
		p->arr[end] = p->arr[end - 1];//整体向后移动
		end--;
	}
	p->arr[0] = x;//头插
	p->num++;//有效数据加一
}

//6. 顺序表的头删
void SeqListPopFront(SL* p)
{
	assert(p);//判断指针的有效性
	assert(p->num > 0);//有数据才删除
	size_t begin = 1;
	while (begin<p->num)
	{
		p->arr[begin - 1] = p->arr[begin];//整体向前移动
		begin++;
	}
	p->num--;// 有效数据减一

}

//7. 顺序表在pos位置插入
void SeqListInsert(SL* p, size_t pos, SLDataType x)
{
	assert(p);//判断指针的有效性
	assert(pos >= 0 && pos < p->num);//pos必须小于num并且大于等于0
	CheckSeqList(p);//判断容量是否满了
	for (int i = p->num; i >pos-1 ; i--)
	{
		p->arr[i] = p->arr[i - 1];//将pos后面的元素往后挪
	}
	p->arr[pos - 1] = x;//在pos位置加入数据
	p->num++;//有效个数加一
}

//8. 顺序表在pos位置删除
void SeqListErase(SL* p, size_t pos)
{
	assert(p);//判断指针的有效性
	assert(pos>=0&&pos<p->num );//pos必须小于num并且大于等于0
	assert(p->num > 0);//有数据才能删除
	for (int i = pos; i <p->num; i++)
	{
		p->arr[i-1] = p->arr[i];//将pos后面的元素往后挪
	}
	p->num--;//有效个数减一
}

//9. 顺序表的查找
int SeqListFind(SL* p, SLDataType x)//如果该数字存在则返回该数字的下标,否则返回-1
{
	assert(p);//断言
	for (int i = 0; i < p->num; i++)
	{
		if (p->arr[i] == x)
		{
			return i;//查到返回下标
		}
	}
	return -1;//没有查到
}

//10 顺序表的销毁
void SeqListDestory(SL* p)
{
	assert(p);//判断指针的有效性
	free(p->arr );//释放动态内存开辟的空间
	p->arr = NULL;
	p->capacity = 0;//容量置为0
	p->num = 0;//有效个数置为0
}

//11. 顺序表的打印
void SeqListPrint(SL* p)
{
	assert(p);//判断指针的有效性
	if (p->num == 0)
	{
		printf("顺序表为空!\n");
		return;
	}
	for (int i = 0; i < p->num; i++)
	{
		printf("%d ", p->arr[i]);//打印数据
	}
	printf("\n");
}

4. 完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构【数据结构与算法】之顺序表及其实现!,数据结构与算法,数据库,数据结构文章来源地址https://www.toymoban.com/news/detail-860870.html

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

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

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

相关文章

  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 头歌(C语言)-数据结构与算法-栈的实现-第1关:实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义(C) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(65)
  • 数据结构与算法—一维数组、二维数组、矩阵、顺序串、链接串的C++代码实现

    1、一维数组:ArrayOneD.h 数组这种数据结构可以看作线性表的推广。数组一般采用顺序存储的方法表示。 这是一个模板类 ArrayOneD 的实现,用于表示一维数组。它包括了 构造函数、拷贝构造函数、析构函数、重载下标运算符、重载赋值运算符、求数组长度、重新设置数组长度

    2024年02月07日
    浏览(62)
  • 头歌(C语言)-数据结构与算法-队列-第1关:实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务:实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(162)
  • 【数据结构】线性表(一)线性表的定义及其基本操作(顺序表插入、删除、查找、修改)

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(69)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(41)
  • 数据结构与算法之美学习笔记:48 | B+树:MySQL数据库索引是如何实现的?

    本节课程思维导图: 作为一个软件开发工程师,你对数据库肯定再熟悉不过了。作为主流的数据存储系统,它在我们的业务开发中,有着举足轻重的地位。在工作中,为了加速数据库中数据的查找速度,我们常用的处理思路是,对表中数据创建索引。那你是否思考过,数据库

    2024年01月16日
    浏览(82)
  • 青岛大学_王卓老师【数据结构与算法】Week05_13_队列的顺序表示和实现1_学习笔记

    本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享, 另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权,请留言作删文处理。 课程视频链接: 数据结构与算法基础–第05周13–3.5队列的表示和实现2–

    2024年02月17日
    浏览(43)
  • 青岛大学_王卓老师【数据结构与算法】Week05_14_队列的顺序表示和实现2_学习笔记

    本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享, 另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权,请留言作删文处理。 课程视频链接: 数据结构与算法基础–第05周14–3.5队列的表示和实现3–

    2024年02月16日
    浏览(61)
  • 数据结构与算法—顺序表

    目录 一、线性表 二、顺序表概念  三、实现顺序表 1、声明结构体 2、初始化 3、打印数据  4、销毁  5、尾插头插 尾插 判断是否扩容   头插 6、尾删头删 尾删 头删 7、 指定位置插入元素 8、 删除指定位置元素 9、 查找指定元素位置 10、修改指定位置元素 完整版附上: S

    2024年02月08日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包