数据结构(初阶)第二节:顺序表

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

数据结构(初阶)第一节:数据结构概论-CSDN博客

从本文正式进入对数据结构的讲解,开始前友友们要有C语言的基础,熟练掌握动态内存管理结构体指针等章节,方便后续的学习。

目录

顺序表(Sequence List)

顺序表的分类

静态顺序表

动态顺序表

顺序表的功能

初始化

扩容        

头插        

尾插 

头删 

尾删

销毁

打印顺序表

指定下标插入

指定下标删除

查找

示例


顺序表(Sequence List)

线性表的概念线性表(linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构,常⻅的线性表:顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的, 线性表在物理上存储时,通常以数组和链式结构的形式存储。

        线性表是对存储具有某种共同点的数据集合的统称,顺序表和数组就是线性表的一种。顺序表的底层逻辑是利用数组实现的,但是相较于数组,顺序表的功能更齐全、丰富,顺序表新增了增、删、查、改等功能。

顺序表的分类

        根据定义格式的不同,顺序表又可分为静态顺序表动态顺序表

静态顺序表

#include <stdio.h>

struct SeqList//定义顺序表
{
	int arr[10];//定长数组
	int size;//顺序表中有序的元素个数
};

静态顺序表的缺陷:空间给少了不够⽤,给多了造成空间浪费静态顺序表的定义方式已经基本被淘汰,现在大多采用动态顺序表的定义方式。

动态顺序表

        动态顺序表不同于静态顺序表,它很好的解决了空间浪费的问题,动态顺序在定义时不直接指明内存空间的大小(在初始化时有一定的空间),而是根据需求通过动态内存分配的方式开辟内存,等到存储空间不够时再扩容。

#include <stdio.h>

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* a;//动态数组
	int size;//有效元素个数
	int capacity;//已经开辟的空间大小
}SL;

在一开始定义时,使用typedef关键字对数据类型和结构体重命名,方便后续修改,比如说将存储int的数组改为存储char的数组,只需要将typedef int SLDateType中的int改为char即可,可以提高开发效率。

顺序表的功能

初始化

        在初始化时,我们选择malloc函数为数组分配内存,初始的内存空间一般定义为4个字节的大小。

注意:在对初始化函数传参时一定要传地址值,也就是参数一定是指针变量,不能直接将非指针变量传递过去,因为形参和实参不在同一块内存空间中,直接传参的话会导致初始化失败,程序报错。

void SLinit(SL* ps)
{
	ps->a = malloc((sizeof(SLDateType)) * 4);//初始内存4个字节
	if (ps->a == NULL)//分配内存失败
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	ps->size = 0;
}

扩容        

        在对顺序表进行扩容时应该首先判断该情况下是否需要扩容,即ps->capacity == ps->size,判断之后使用realloc函数进行扩容,每次扩容应为上一次的两倍。

void SLcheckCapcity(SL* ps)
{
	if (ps->capacity == ps->size)//判断是否需要扩容
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);//一般每次扩容到上一次的2倍
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}

头插        

        在顺序表的头部插入一个元素,其余元素按顺序向后移动。

void SLpopFront(SL* ps, SLDateType x)
{
	assert(ps);
	SLcheckCapcity(ps);
	for (int i = ps->size; i >= 1; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;
}

尾插 

        顺序表尾部插入元素,在尾部插入时就一定要进行数组扩容。通过调用SLpopBack函数在尾部插入元素,ps->size最开始指向0索引,每次插入元素时size总在最后一个有效元素的下一位。

void SLpopBack(SL* ps, SLDateType x)
{
	assert(ps);
	SLcheckCapcity(ps);
	ps->a[ps->size++] = x;
}

头删 

     从顺序表头部删除元素,将元素按顺序前移,覆盖要删除的元素。

void SLpushFront(SL* ps)
{
	assert(ps && ps->size);//当顺序表为空时不用删除元素
	for (int i = 1; i < ps->size; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

尾删

void SLpushBack(SL* ps)
{
	assert(ps && ps->size);
	ps->size--;
}

销毁

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

打印顺序表

void SLprint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->a[i]);
	printf("\n");
}

指定下标插入

void SLinsert(SL* p1, int pos, SLDataType x)
{
	//要注意p1->size指向的是最后一个有效数据的下一位
	//pos是指定的插入位置的下标(如果为0则是头插,如果为ps->size-1则为尾插)
	//x是待插入的数据
	assert(p1 && pos >= 0 && pos < p1->size);
	SLcheckCapcity(p1);
	for (int i = p1->size; i > pos; i--)
	{
		p1->a[i] = p1->a[i - 1];
	}
	p1->a[pos] = x;
	p1->size++;
}

指定下标删除

void SLerase(SL* p1, int pos)
{
	assert(p1 && pos >= 0 && pos < p1->size);
	for (int i = pos; i < p1->size - 1; i++)
	{
		p1->a[i] = p1->a[i + 1];
	}
	p1->size--;
}

查找

int SLfind(SL* p1, SLDataType x)
{
	assert(p1);
	for (int i = 0; i < p1->size; i++)
	{
		if (p1->a[i] == x)
		{
			return i;//找到后返回下标
		}
	}
	return -1;//没有找到返回-1
}

示例

int main()
{
	SL p;
	SLinit(&p);

	printf("这是尾插:");//尾插1 2 3 4 5
	SLpopBack(&p, 1);
	SLpopBack(&p, 2);
	SLpopBack(&p, 3);
	SLpopBack(&p, 4);
	SLpopBack(&p, 5);
	SLprint(&p);

	printf("这是头插:");//头插6 7 8
	SLpopFront(&p, 8);
	SLpopFront(&p, 7);
	SLpopFront(&p, 6);
	SLprint(&p);

	printf("这是头删:");//头删6 7 8
	SLpushFront(&p);
	SLpushFront(&p);
	SLpushFront(&p);
	SLprint(&p);

	printf("这是尾删:");//尾删3 4 5
	SLpushBack(&p);
	SLpushBack(&p);
	SLpushBack(&p);
	SLprint(&p);

	SLdestory(&p);

	return 0;
}

 运行结果:

数据结构(初阶)第二节:顺序表,数据结构与算法,c语言,数据结构文章来源地址https://www.toymoban.com/news/detail-848359.html

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

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

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

相关文章

  • 数据结构初阶--二叉树的顺序结构之堆

    目录 一.堆的概念及结构 1.1.堆的概念 1.2.堆的存储结构 二.堆的功能实现 2.1.堆的定义 2.2.堆的初始化 2.3.堆的销毁 2.4.堆的打印 2.5.堆的插入 向上调整算法 堆的插入 2.6.堆的删除 向下调整算法 堆的删除 2.7.堆的取堆顶元素 2.8.堆的判空 2.9.堆的求堆的大小 三.堆的创建 3.1.向上调

    2024年02月14日
    浏览(44)
  • 数据结构(初阶):顺序表实战通讯录

    数据结构(初阶)第一节:数据结构概论-CSDN博客 数据结构(初阶)第二节:顺序表-CSDN博客         本文将以C语言和顺序表实现通讯录基础管理,实现功能包括增、删、改、查等,在实现相关功能时需要用到在第二节中顺序表的相关内容,需要友友们掌握顺序表的相关

    2024年04月16日
    浏览(36)
  • 初阶数据结构:顺序表相关题目练习

    在对顺序表这一数据结构进行了学习与自实现后,我明白了顺序表的是使用了 物理地址上连续的数组模型 实现的,而 插入删除 的操作都会涉及到其中 数据的挪动与边界问题 。接下来,就结合算法时空间复杂的要求来对这一相关问题通过几道题目进行巩固练习。 题目要求:

    2024年01月20日
    浏览(49)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(241)
  • 【数据结构初阶】二、 线性表里的顺序表

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

    2024年02月09日
    浏览(36)
  • 【数据结构】第二站:顺序表

    目录 一、线性表 二、顺序表 1.顺序表的概念以及结构 2.顺序表的接口实现 3.顺序表完整代码 三、顺序表的经典题目 1.移除元素 2.删除有序数组中的重复项 3.合并两个有序数组 在了解顺序表前,我们得先了解线性表的概念 线性表(linear list)是n个具有相同特性的数据元素的

    2023年04月09日
    浏览(94)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

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

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

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

    2024年02月03日
    浏览(45)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(66)
  • 『初阶数据结构 • C语言』⑧ - 动态顺序表详解(附完整源码)

    本章内容 写在前面 1.静态与动态是指什么? 2.动态顺序表结构的定义 3.动态顺序表的函数接口实现 4.动态顺序表的问题及思考 5.关于顺序表的OJ题 6.OJ答案及解析 1.移除元素 2.删除有序数组中的重复项 ​3.合并两个有序数组 7.动态顺序表完整源码 1.SeqList.h 2.SeqList.c     上一章

    2024年02月16日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包