数据结构入门(C语言)顺序表的增删查改

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


数据结构入门(C语言)顺序表的增删查改

前言

本章会用C语言来描述数据结构中的顺序表,实现简单的增删查改操作,其中头文件包含在新建的头文件SeqList.h内,顺序表的实现在新建的Seqlist.c内,主函数Text.c将会实现菜单,方便我们进行功能的选择。

1. 顺序表的概念

数据结构入门(C语言)顺序表的增删查改

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

顺序表分为静态和动态两个版本,一般我们都是使用动态的版本进行操作
因为静态的版本使用定长数组存储元素,而动态的版本使用动态开辟的数组存储
数据结构入门(C语言)顺序表的增删查改

2. 动态顺序表

数据结构入门(C语言)顺序表的增删查改

2.1 顺序表的初始化与销毁

我们知道,一个顺序表有这么几个组成部分:起始地址,存储的数据个数,以及容量。 在进行初始化时,我们应该将起始地址置为空(NULL),个数和容量置为0。
//初始化
void SLInit(SL* ps1)
{
	ps1->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (ps1->a == NULL)
	{
		perror("malloc fail");//顺序表为空就报错,说明申请空间失败
		return;
	}
	ps1->capacity = 4;//我们设定初始空间为4个SLDatatype(这里是int)大小
	ps1->size = 0;
}

注意要释放掉内存

void SLDestory(SL* ps1)
{
	free(ps1->a);//释放
	ps1->a = NULL;//将顺序表置为空
	ps1->size = 0;//有效数字置0
	ps1->capacity = 0;//容量置0
}

2.2 顺序表的尾插

尾插,顾名思义,就是在顺序表的尾部插入数据,在实现尾插功能的同时,我们要写一个检查顺序表容量的函数,插入的时候我们要检查空间是否足够,不够则要进行扩容,足够则插入。

void SLPushBack(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);//检查容量
	ps1->a[ps1->size] = x;//尾插数据
	size++
	//ps1->a[ps1->size++] = x;
	
}

容量检查

void SLCheckCapacity(SL* ps1)
{
	if (ps1->size == ps1->capacity)//有效数据大小如果和容量相等说明需要扩容了
	{
		SLDatatype* tmp = (SLDatatype*)realloc(ps1->a, sizeof(SLDatatype) * ps1->capacity * 2);
		//如果空间不够了,就扩容到原来的二倍
		if (tmp == NULL)
		{
			perror("realloc fail");//如果tmp为空说明扩容空间失败
			return;
		}
		ps1->a = tmp;//检查确保tmp不为空再赋给a
		ps1->capacity *= 2;//容量变为原来的二倍
	}

}

2.3 顺序表的尾删

实现尾删功能我们需要注意的时,说是删,但是我们可不能真删了,并不是把数据置为\n或是\0,只需要把有效数据-1就行了。
注意:不可以对要删除数的空间进行释放,因为动态开辟出的空间有一个特点:一起开辟,一起释放,在这里不可以实现。

void SLPopBack(SL* ps1)
{   //尾删数据
	assert(ps1);//暴力检查一下
	//size不能一直-1
	if(ps1->size>0)
	{
	    p->size--;
	}
}

2.4 顺序表的头插

除了需要把顺序表中【0,size-1】的元素依次向后移动一位,再插入数值
我们要从后往前向后移,因为从前往后的话数据会被覆盖
数据结构入门(C语言)顺序表的增删查改

void SLPushFront(SL* ps1, SLDatatype x)
{
	SLCheckCapacity(ps1);//检查容量
	for (int i = ps1->size - 1; i >= 0; i--)//头插需要将顺序表中【0,size-1】的元素依次向后移动一位
	{
		ps1->a[i + 1] = ps1->a[i];
	}
	ps1->a[0] = x;   //头插数据
	ps1->size++;     //有效数据+1
}

2.5 顺序表的头删

头删很简单,与头插相反,头插是将从最后一个数开始向后覆盖,而头删是从第二个元素开始从前往后覆盖前一个元素。

void SLPopFront(SL* ps1)
{
	assert(ps1->a > 0);//暴力检查
	for (int i = 0; i < ps1->size - 1; i++)
	{
		ps1->a[i] = ps1->a[i + 1];
	}
}

2.6 固定位置的插入

思路和头插没区别,只要找到要插入的位置,将它后面位置的元素全部向后移一位,然后插入,就OK了,需要注意的是pos(插入的位置)也要进行断言

void SLInsert(SL* ps1, int pos, SLDatatype x)
{
	assert(ps1);//断言检查空指针
	assert(pos>=0 && pos <= ps1->size);//断言检查pos是否合规

	SLCheckCapacity(ps1);//检查容量
	int end = ps1->size - 1;
	while (pos <= end)
	{
		ps1->a[end + 1] = ps1->a[end];
		--end;
	}
	ps1->a[pos] = x;
	ps1->size++;
	

}

2.7 固定位置的删除

同理,从要删除的位置开始,从前往后将后一位的值赋给前一位,太简单了

void SLEarse(SL* ps1, int pos)
{
	assert(ps1);
	assert(pos >= 0 && pos <= ps1->size);

	SLCheckCapacity(ps1);
	int start = pos+1;
	while (start < ps1->size)
	{
		ps1->a[start - 1] = ps1->a[start];
		++start;
	}
	ps1->size--;
}

2.8 查找和打印

过于简单,直接上代码

int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
void SLPrint(SL* ps1)
{
	for (int i = 0; i < ps1->size; i++)
	{
		printf("%d ",ps1->a[i]);
	}
	printf("\n");
}

2.9 修改元素

void SLModify(SL* ps1, int pos, SLDatatype x)
{
	assert(ps1);
	assert(0 <= pos && pos < ps1->size);

	ps1->a[pos] = x;

}

主函数部分(菜单)

void menu()
{
	printf("***************************************\n");
	printf("1、尾插数据  2、尾删数据\n");
	printf("3、头插数据  4、头删数据\n");
	printf("5、打印数据  -1、退出\n");
	printf("***************************************\n");
}
int main()
{
	int option = 0;
	SL s;
	SLInit(&s);
	while (option != -1)
	{
		menu();
		printf("请输入你的操作:>");
		scanf("%d", &option);
		if (option == 1)
		{
			/*printf("请输入要尾插的数据,以-1结束:");
			int x = 0;
			scanf("%d", &x);
			while (x != -1)
			{
				SLPushBack(&s, x);
				scanf("%d", &x);
			}*/

			int n = 0;
			printf("请输入要尾插的数据个数,再依次输入要插入的数据:");
			scanf("%d", &n);

			int x = 0;
			while (n > 0)
			{
				scanf("%d", &x);
				SLPushBack(&s, x);
				n--;
			}
		}
		else if (option == 5)
		{
			SLPrint(&s);
		}
		else if (option == -1)
		{
			break;
		}
		else
		{
			printf("无此选项,请重新输入\n");
		}
	}

	SLDestroy(&s);

	return 0;
}

结语

就这样,顺序表从定义到结束,增删查改的功能也全部实现了,学到这里,我们就大致掌握了顺序表,同时我们也要思考一些问题:
1.中间/头部的插入,时间复杂度为O(N)
2.增容需要申请新空间,拷贝数据,释放旧空间,这个过程会有损耗
3.增容一般是以两倍的方式增长,所以必定会造成浪费,比如我们当前容量为100,已经满了,我们扩容到200,但是只新插入了5个数据,这就浪费了95个数据空间
如何处理呢?

数据结构入门(C语言)顺序表的增删查改文章来源地址https://www.toymoban.com/news/detail-436298.html

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

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

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

相关文章

  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(62)
  • 数据结构从入门到实战——顺序表的应用

    目录 一、基于动态顺序表实现通讯录 二、代码实现 2.1 通讯录的初始化 2.2 通讯录的销毁  2.3 通讯录的展示 2.4 通讯录添加联系人信息 2.5 通讯录删除联系人信息 2.6 通讯录修改联系人信息  2.7 通讯录的查找联系人信息 2.8 将通讯录中联系人信息保存到文件中  2.9 从文件中

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

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

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

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

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

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

    2024年02月07日
    浏览(48)
  • [C语言][数据结构][动态内存空间的开辟]顺序表的实现!

    目录 零.必备知识 a.顺序表的底层是数组. b.数组在内存中是连续存放的. c.动态内存空间的开辟(malloc,calloc,realloc). 一.顺序表的定义与实现          1.1 顺序表的定义          1.2 顺序表的初始化          1.3 顺序表的销毁          1.4 顺序表容量的检查与调整

    2024年04月09日
    浏览(88)
  • 数据结构-顺序表的基本实现(C语言,简单易懂,含全部代码)

    今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻

    2023年04月08日
    浏览(41)
  • 数据结构(C语言实现)——顺序表的介绍及基本操作的实现

    今天我们来学习数据结构中的线性表,本文主要介绍一种常见的线性表——顺序表。 本文着重介绍顺序表的概念以及顺序表各种基本操作的实现过程(C语言实现),以后会更新更多的数据结构,觉得有用的朋友可以三连关注一波,一起学习。 线性表(linear list)是n个具有相

    2023年04月13日
    浏览(52)
  • 【数据结构】顺序表的实现及基本操作完整代码(C语言实现)

    顺序表:逻辑上相邻的数据元素,其物理次序也是相邻的 这里之所以要把int分别创建新名字为SqlElemType和Status,是因为实际应用时数据的类型不一定是int型,这样设置方便修改元素类型,提高代码适用性。 LocateElem的时间复杂度为O(n) InsertSq的时间复杂度为O(n) DeleteSq的时间

    2024年04月12日
    浏览(50)
  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(69)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包