1. Toy模板网首页
  2. > Toy博客

数据结构：顺序表的奥秘

8月前 作者：GOTXX 分类：Toy博客 阅读(53) 违法举报

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

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

🎉个人名片：

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

🎉文章简介：

🎉本篇文章对   用C语言实现顺序表 学习的相关知识进行分享！🎉

如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉

目录

一.顺序表的概念及存储结构

1.1储存结构

二.顺序表的实现

一.功能函数的实现

1.初始化函数

2.顺序表的销毁

3.顺序表的打印

4.扩容函数

5.尾插函数

6.尾删函数

7.头插函数

8.头删函数

9.插入函数

10.删除函数

11.查找函数

12.修改函数

三.总代码

四.顺序表的性能分析

一.顺序表的概念及存储结构

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

顺序表可以分为静态顺序表和动态顺序表。

1.1储存结构

静态顺序表：使用定长数组存储元素；

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

动态顺序表：数组的大小是根据存储的数据个数，如果满了就动态开辟出来的，相对而言不会造成空间的浪费；

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

二.顺序表的实现

静态顺序表 只适用于确定知道需要存多少数据的场景；

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。例如：如果数组的大小定为200，却只储存了几十个数据，和动态的顺序表相比，空间浪费更大；所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

一.功能函数的实现（含图解）

1.初始化函数

功能：对结构体内成员进行初始化操作；

代码实现：

void InitList(SL* s)
{
	assert(s);        //断言，防止传入空指针

	s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);  
	if (s->a == NULL)   //这里最开始开辟四个存储数据类型的大小
	{
		perror("malloc fail");
		exit(-1);
	}
	s->size = 0;            //存储的有效数据个数为0
	s->capacity = 4;       //空间置成4
}

2.顺序表的销毁

功能：对动态开辟的空间进行销毁，空间释放

代码实现：

void DestoryList(SL* s)
{
	assert(s);

	free(s->a);       //释放动态开辟的空间
	s->a = NULL;      //置空
	s->capacity = s->size = 0;
}

3.顺序表的打印

代码实现：

void SListPrintf(SL* s)
{
	assert(s);

	if (s->size < 0)     //如果没有数据，则直接返回
	{
		return;
	}
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);       //遍历依次打印
	}
	printf("\n");        //打印完换行
}

4.扩容函数

功能：检查是否需要扩容

代码实现：

void CheckCapacity(SL* s)
{
	assert(s);

	if (s->capacity == s->size)    //相等则说明空间已经满了
	{
		SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity);  //二倍扩容
		if (tmp == NULL)    
		{
			perror("realloc fail");
			exit(-1);
		}

		s->a = tmp;
		s->capacity *= 2;

	}
}

5.尾插函数

功能：在顺序表最后插入一个数据

代码实现：

void PushBack(SL* s, SLDateType n)
{
	assert(s);

	CheckCapacity(s);  //检查空间是否满
	s->a[s->size] = n;    //直接插入到数组最后
	s->size++;       //有效数据个数++
}

6.尾删函数

功能: 删除顺序表的最后一个数据

代码实现：

void PopBack(SL* s)
{
	assert(s);
	assert(s->size > 0);     //当数组中有效数据个数为0时，不能再删除

	s->size--;         //数据个数--

}

7.头插函数

功能：在顺序表最前面插入一个数据

代码实现：

void PushFront(SL* s, SLDateType n)
{
	assert(s);
	CheckCapacity(s);    //检查扩容

	int end = s->size;    
	while (end>0) 
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}
	s->a[0] = n;         
	s->size++;
}

图解：

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

性能分析：头插一个数据，首先需要将全部数据一次往后挪一个位置，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

8.头删函数

功能：删除表中第一个元素

代码实现：

void Popfront(SL* s)
{
	assert(s);
	assert(s->size > 0);   //size为0时，不能再删除

	for (int i = 0; i < s->size; i++)
	{
		s->a[i] = s->a[i+1];      //向前挪动数据
	}

	s->size--;
}

图解：

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

性能分析：头删一个数据，首先需要将全部数据一次往前挪一个位置，将第一个元素覆盖掉，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

9.插入函数

功能：在某个位置插入一个数据

代码实现：


void SListInsert(SL* s, int pos, SLDateType n)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);    //判断pos合法

	int end = s->size;
	int begin = pos;
	while (begin < end)
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}
	s->a[pos] = n;       //修改数据
	s->size++;
}

图解：

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

性能分析：中间插入一个数据和头插差不多，首先需要将该位置后面的全部数据依次往后挪一个位置，将该位置空出来，再将该数据插入，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

10.删除函数

功能：删除数组中任何位置的数据

代码实现：

void SListErase(SL* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);    //pos范围合法判断

	int cur = pos;
	while (cur < s->size)
	{
		s->a[cur] = s->a[cur+1];    //挪动位置
		cur++;
	}
	s->size--;

}

图解：

数据结构：顺序表的奥秘,数据结构的学习之路,前端,c++,开发语言,C语言

性能分析：删除一个数据与头删差不多，首先需要待删数据位置后面全部数据依次往前挪一个位置，将待删元素覆盖掉，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

11.查找函数

功能：查找顺序表中某个数据，返回下标

代码实现：

int SListFind(SL* s,SLDateType n)
{
	assert(s);

	for (int i = 0; i < s->size; i++)    //遍历寻找
	{
		if (s->a[i] == n)     //找到了返回下标
		{ 
			return i;
		}
	}

	printf("顺序表中无该数据\n");   
	exit(-1);

}

性能分析：将数组中的数据遍历一遍；时间复杂度：O(N)

空间复杂度：O(1)

12.修改函数

功能：修改数组中某个数据

代码实现：

void SListModify(SL* s, int pos,SLDateType n)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	s->a[pos] = n;     //直接通过下标访问修改
}

三.总代码

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


typedef int SLDateType;

struct SeqList
{
	SLDateType* a;      //指向一个数组的指针
	int size;           //记录数据个数
	int capacity;       //记录容量，如果与数据个数相等就扩容
};

typedef struct SeqList SL;


void InitList(SL* s);

void SListPrintf(SL* s);

void PushBack(SL* s, SLDateType n);
void PushFront(SL* s, SLDateType n);
void PopBack(SL* s);
void Popfront(SL* s);

int SListFind(SL* s,SLDateType n);

void SListModify(SL* s, int pos, SLDateType n);
void SListErase(SL* s, int pos);
void SListInsert(SL* s, int pos, SLDateType n);


void DestoryList(SL* s);

#include"SeqList.h"



void InitList(SL* s)
{
	assert(s);        //断言，防止传入空指针

	s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);  
	if (s->a == NULL)   //这里最开始开辟四个存储数据类型的大小
	{
		perror("malloc fail");
		exit(-1);
	}
	s->size = 0;            //存储的有效数据个数为0
	s->capacity = 4;       //空间置成4
}

void SListPrintf(SL* s)
{
	assert(s);

	if (s->size < 0)     //如果没有数据，则直接返回
	{
		return;
	}
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);       //遍历依次打印
	}
	printf("\n");        //打印完换行
}


void CheckCapacity(SL* s)
{
	assert(s);

	if (s->capacity == s->size)    //相等则说明空间已经满了
	{
		SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity);  //二倍扩容
		if (tmp == NULL)    
		{
			perror("realloc fail");
			exit(-1);
		}

		s->a = tmp;
		s->capacity *= 2;

	}
}

void PushBack(SL* s, SLDateType n)
{
	assert(s);

	CheckCapacity(s);  //检查空间是否满
	s->a[s->size] = n;    //直接插入到数组最后
	s->size++;       //有效数据个数++
}

void PushFront(SL* s, SLDateType n)
{
	assert(s);
	CheckCapacity(s);    //检查扩容

	int end = s->size;    
	while (end>0) 
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}
	s->a[0] = n;         
	s->size++;
}

void PopBack(SL* s)
{
	assert(s);
	assert(s->size > 0);     //当数组中有效数据个数为0时，不能再删除

	s->size--;         //数据个数--

}


void Popfront(SL* s)
{
	assert(s);
	assert(s->size > 0);   //size为0时，不能再删除

	for (int i = 0; i < s->size; i++)
	{
		s->a[i] = s->a[i+1];      //向前挪动数据
	}

	s->size--;
}


int SListFind(SL* s,SLDateType n)
{
	assert(s);

	for (int i = 0; i < s->size; i++)    //遍历寻找
	{
		if (s->a[i] == n)     //找到了返回下标
		{ 
			return i;
		}
	}
	printf("顺序表中无该数据\n");   
	exit(-1);
}

void SListModify(SL* s, int pos,SLDateType n)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	s->a[pos] = n;     //直接通过下标访问修改
}


void SListErase(SL* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);    //pos范围合法判断

	int cur = pos;
	while (cur < s->size)
	{
		s->a[cur] = s->a[cur+1];    //挪动位置
		cur++;
	}
	s->size--;

}

void SListInsert(SL* s, int pos, SLDateType n)
{

	assert(s);
	assert(pos >= 0 && pos <= s->size);    //判断pos合法

	int end = s->size;
	int begin = pos;
	while (begin < end)
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}

	s->a[pos] = n;       //修改数据
	s->size++;
}


void DestoryList(SL* s)
{
	assert(s);

	free(s->a);       //释放动态开辟的空间
	s->a = NULL;      //置空
	s->capacity = s->size = 0;
}

四.顺序表的性能分析

问题：


1. 中间/头部的插入删除，时间复杂度为O(N);
2. 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗;
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间;

思考：如何解决以上问题呢？

下一章链表结构就可以解决这个问题；文章来源地址https://www.toymoban.com/news/detail-838269.html

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

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】顺序表的定义

    【数据结构】顺序表的定义

    🎈个人主页：豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏：数据结构 🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！ 在数据结构的世界里，顺序表是一种常见且基础的线性数据结构。它以其简洁、直观的特性，广

    2024年04月08日
    浏览(51)
  • 【（数据结构）- 顺序表的实现】

    【（数据结构）- 顺序表的实现】

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

    2024年02月07日
    浏览(48)
  • 数据结构--顺序表的查找

    数据结构--顺序表的查找

    目标： GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。 代码实现 时间复杂度 O(1) 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性 目标： LocateElem(Le):按值查找操作。在表L中查找具有给

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

    【数据结构】--顺序表的实现

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

    2024年04月17日
    浏览(44)
  • 【数据结构】顺序表的定义和运算

    【数据结构】顺序表的定义和运算

    目录 1.初始化 2.插入 3.删除 4.查找 5.修改 6.长度 7.遍历 8.完整代码 🌈嗨！我是Filotimo__🌈。很高兴与大家相识，希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创，首发于CSDN📚。 📣如需转载，请事先与我联系以获得授权⚠️。 🎁欢迎大家给我点赞👍、收藏⭐️

    2024年02月05日
    浏览(35)
  • 【数据结构】顺序表的定义和操作

    【数据结构】顺序表的定义和操作

    目录 1.初始化 2.插入 3.删除 4.查找 5.修改 6.长度 7.遍历 8.完整代码 🌈嗨！我是Filotimo__🌈。很高兴与大家相识，希望我的博客能对你有所帮助。 💡本文由Filotimo__✍️原创，首发于CSDN📚。 📣如需转载，请事先与我联系以获得授权⚠️。 🎁欢迎大家给我点赞👍、收藏⭐️

    2024年02月03日
    浏览(48)
  • 【数据结构】顺序表的实现——静态分配

    【数据结构】顺序表的实现——静态分配

    🎈个人主页：豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏：数据结构 🤝希望本文对您有所裨益，如有不足之处，欢迎在评论区提出指正，让我们共同学习、交流进步！ 在数据结构的领域中，顺序表是一种基础且重要的线性表实现方式。它采用一段地址连续的存储

    2024年04月26日
    浏览(39)
  • 数据结构(六)——线性表的顺序实现

    数据结构(六)——线性表的顺序实现

    🏠个人主页：尘觉主页 🧑个人简介：大家好，我是尘觉，希望我的文章可以帮助到大家，您的满意是我的动力😉 在csdn获奖荣誉: 🏆csdn城市之星2名 ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ ⁣⁣⁣⁣ 💓csdn2023年后端赛道第第七 ⁣⁣⁣⁣ ⁣⁣⁣⁣

    2024年01月25日
    浏览(62)

  • 数据结构1：动态顺序表的实现

    2024年04月13日
    浏览(49)

  • 数据结构与算法 --顺序表的创建

    1. 顺序表（Sequence List）是一种线性表的实现方式，通过连续的内存空间存储元素，按照顺序排列。 顺序表的特点包括： 元素在内存中的存储是连续的，通过数组实现。 元素之间的逻辑顺序与物理顺序一致。 可以根据元素的索引直接访问和修改元素。 需要预先分配足够的内

    2024年03月26日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包