顺序表 --- C语言实现

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

 文章来源地址https://www.toymoban.com/news/detail-556143.html

目录

1.线性表

2.顺序表

2.1 概念和结构

2.2 接口实现

2.3 数组相关面试题

2.4 顺序表的问题及思考


1.线性表

什么是线性表 :

线性表(linear list)是n个具有相同特性数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...,本篇文章介绍一下顺序表

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表 --- C语言实现,c语言,开发语言,数据结构,顺序表

2.顺序表

2.1 概念和结构

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

顺序表一般可以分为:

  1. 静态顺序表,使用定长数组存储元素。
  2. 动态顺序表:使用动态开辟的数组存储。

 1.静态顺序表的定义

#define N 7 //顺序表的大小
typedef int SLDataType;

typedef struct SeqList
{
    SLDataType array[N];    //定长数组,顺序表只能存储N个元素
    int size;               //有效元素个数
}SeqList;

2.动态顺序表的定义

typedef int SLDatatype;

typedef struct SeqList
{
	SLDatatype* a; //指向动态开辟的数组,空间不够可以扩容
	int size;      //有效数据个数
	int capacity;  //容量空间大小
}SeqList;

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。

所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。

头文件 :

typedef int SLDatatype;

typedef struct SeqList
{
	SLDatatype* a;
	int size;
	int capacity;
}SeqList;

//初始化
void SeqListInit(SeqList* ps);
//释放
void SeqListDestroy(SeqList* ps);
//打印
void SeListPrint(SeqList* ps);
//头插法
void SLPushfront(SeqList* ps, SLDatatype x);
//尾插法
void SLPushback(SeqList* ps, SLDatatype x);
//头删
void SLPopfront(SeqList* ps);
//尾删
void SLPopback(SeqList* ps);
//顺序表查找
int SeqListFind(SeqList* ps, SLDatatype x);
//在顺序表pos位置插入x
void SeqListInsert(SeqList* ps,int pos, SLDatatype x);
//删除顺序表pos位置的值
void SeqListErase(SeqList* ps,int pos);
//修改顺序表pos位置的值
void SeqListMidefy(SeqList* ps, int pos, SLDatatype x);

 函数的实现:

//初始化
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (ps->a == 0)
	{
		perror("malloc fail");
		return;
	}
	ps->size = 0;
	ps->capacity = 4;
}
//释放
void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	ps->size = 0;
	ps->capacity = 0;
	free(ps->a);
	ps->a = NULL;
}
//打印
void SeListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//检查容量
int CheckCapacity(SeqList* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDatatype* ptr = (SLDatatype*)realloc(ps->a, sizeof(SLDatatype) * ps->capacity * 2);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return 0;
		}
		else
		{
			ps->a = ptr;
			ps->capacity *= 2;
		}
	}
	return 1;
}

//头插法
void SLPushfront(SeqList* ps, SLDatatype x)
{
	assert(ps);
	if (CheckCapacity(ps) == 0)
	{
		return;
	}

	int end = ps->size;
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
	
}
//尾插法
void SLPushback(SeqList* ps, SLDatatype x)
{
	assert(ps);
	if (CheckCapacity(ps) == 0)
	{
		return;
	}
	ps->a[ps->size] = x;
	ps->size++;
}
//头删
void SLPopfront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}
//尾删
void SLPopback(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	ps->size--;
}
//顺序表查找
int SeqListFind(SeqList* ps, SLDatatype x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//在顺序表pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	if (CheckCapacity(ps) == 0)
	{
		return;
	}
	int end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
//删除顺序表pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//已经包含 ps->size > 0
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}
//修改顺序表pos位置的值
void SeqListMidefy(SeqList* ps, int pos, SLDatatype x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//已经包含 ps->size > 0
	ps->a[pos] = x;
}

2.3 数组相关面试题

  1. 原地移除数组中所有的元素val,要求时间复杂度为O(N),空间复杂度为O(1)。OJ链接
  2. 删除排序数组中的重复项。OJ链接
  3. 合并两个有序数组。ОJ链接

2.4 顺序表的问题及思考

问题:

1.中间/头部的插入删除,时间复杂度为O(N)

2.增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。

3.增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

思考:如何解决以上问题呢?可以通过看下一篇文章链表来解决。

本篇结束:

顺序表 --- C语言实现,c语言,开发语言,数据结构,顺序表

 

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

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

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

相关文章

  • 【C语言数据结构】模拟·顺序表·总项目实现

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

    2024年02月15日
    浏览(42)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(44)
  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(54)
  • 【数据结构】详谈队列的顺序存储及C语言实现

    大家好,很高兴又和大家见面啦!!! 在上一篇内容中,我们在介绍完队列的基本概念、重要术语以及基本操作后,又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。 队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义

    2024年01月21日
    浏览(74)
  • 【数据结构】顺序表基本操作的实现(C语言)

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🐌 个人主页:蜗牛牛啊 🔥 系列专栏:🛹数据结构、🛴C++ 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与

    2024年02月16日
    浏览(55)
  • 【数据结构】链表OJ题(顺序表)(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年02月05日
    浏览(46)
  • 数据结构初阶之顺序表(C语言实现)

    顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。 顺序表,它分为两类: 动态顺序表 和 静态顺序表 ,这两个表的区别就是 前者的空间不固定 ,是 支持扩容 的,后者的 空间是固定

    2024年02月03日
    浏览(45)
  • 【数据结构】C语言实现顺序栈(附完整运行代码)

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 在本次项目中我们的目标是 实现一个 顺序栈 : 该 顺序栈 使用 动态内存分配空间 ,可以用来 存储任意数量的同类型数据 . 顺序栈 结构体 需要包含 三个要素 : 存放数据的数组arr,栈顶元素下标top

    2024年04月29日
    浏览(39)
  • 数据结构之顺序表的实现(C语言版)

         Hello, 大家好,我是一代,今天给大家带来有关顺序表的有关知识      所属专栏:数据结构      创作不易,望得到各位佬们的互三呦 1.首先在讲顺序表之前我们先来了解什么是数据结构 数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据?常见的数值1、

    2024年04月25日
    浏览(47)
  • C语言数据结构-----顺序表(多功能动态顺序表的代码实现)

    本篇讲述了顺序表的相关知识,以及动态顺序表的代码实现。 顺序表和链表一般情况下都会叫他们线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性

    2024年02月07日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包