首页 > 资讯 > 后端开发 > 其他教程 >C语言数据结构深入探索顺序表

184

分享到

C语言数据结构深入探索顺序表

2024-04-02 19:04:59 184人浏览安东尼

摘要

目录1.线性表2.顺序表2.1概念及结构2.2 接口实现2.2.1初始化2.2.2 检查容量2.2.3 顺序表打印2.2.4 顺序表尾插2.2.5 顺序表尾删2.2.6 顺序表头插2

2.2.1初始化
2.2.2 检查容量
2.2.3 顺序表打印
2.2.4 顺序表尾插
2.2.5 顺序表尾删
2.2.6 顺序表头插
2.2.7 顺序表头删
2.2.8 顺序表在pos位置插入x
2.2.9 顺序表删除pos位置的值
2.2.10 尾插、尾删、头插、头删的改进
2.2.11 顺序表查找
2.2.12 顺序表销毁

2.3 数组相关面试题

2.4 顺序表的问题及思考

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

2.顺序表

2.1概念及结构

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

顺序表一般可以分为：

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

动态顺序表：使用动态开辟的数组存储

2.2 接口实现

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

#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
	int* a;
	int size;	 //存储数据个数
	int capacity;//存储空间大小
}SeqList;

void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//销毁

void SeqListPrint(SeqList* psl);//打印

void SeqListCheckCapacity(SeqList* psl);//检查容量

int SeqListFind(SeqList* psl, SLDataType x);//查找

//时间复杂度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾删

//时间复杂度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//头插
void SeqListPopFront(SeqList* psl);//头删

//时间复杂度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置删除

2.2.1初始化

就是将元素分别初始化。

//初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

2.2.2 检查容量

初始化时容量为0，想要放数据得增加容量，每次插入数据也得保证容量充足，为了方便，我们先写一个用于检查容量并增容的函数。

//检查容量
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);

	//如果满了，就要扩容
	if (psl->size == psl->capacity)
	{
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一开始capacity=0无法*2增容
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
}

2.2.3 顺序表打印

就是遍历一次把所有元素打印出来，这样可以检查函数写的是否正确，及时订正。

//打印
void SeqListPrint(SeqList* psl)
{
	assert(psl);

	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");

}

2.2.4 顺序表尾插

请添加图片描述

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果满了，就要扩容
	SeqListCheckCapacity(psl);

	psl->a[psl->size] = x;
	psl->size++;
}

2.2.5 顺序表尾删

只需要把size-1这样的话下一个数据就会把尾部数据覆盖掉，达到删除的效果。

//尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);

	if (psl->size > 0)
	{
		psl->size--;
	}
}

2.2.6 顺序表头插

//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);

	//如果满了，就要扩容
	SeqListCheckCapacity(psl);

	//挪动数据,腾出头部位置
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;

}

2.2.7 顺序表头删

将第一个位置覆盖掉，然后用尾删的思路将最后一个数据删除。


//头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);

	//挪动数据覆盖第一个
	if(psl->size>0)
	{
		int begin = 1;
		while (begin < psl->size)
		{
			psl->a[begin - 1] = psl->a[begin];
			begin++;
		}
	}
	psl->size--;
}

2.2.8 顺序表在pos位置插入x

思路跟头插很像,但内含陷阱！

//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);

	//如果满了，就要扩容
	SeqListCheckCapacity(psl);

	温和检测
	//if (pos > psl->size)
	//{
	//	printf("pos越界：%d\n", pos);
	//	return;
	//}
	//暴力检测
	assert(pos <= psl->size);

	//pos=0的时候由于无符号整型判断时的整型提升，会出问题
	//size_t end = psl->size - 1;
	//while (end >= pos)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	end--;
	//}
	//psl->a[pos] = x;
	//psl->size++;

	//这样写才不会有问题
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}

	psl->a[pos] = x;
	psl->size++;
}

2.2.9 顺序表删除pos位置的值

思路跟头删很像

//在pos位置删除
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);

	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		++begin;
	}

	psl->size--;
}

2.2.10 尾插、尾删、头插、头删的改进

有了上面两个通常情况下的增删函数，我们就能改进尾插、尾删、头插、头删。这样能够快速写完顺序表

//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	SeqListInsert(psl, psl->size, x);//在size位置插入数据
}

//尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, psl->size-1);//在size-1位置删除数据
}

//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	SeqListInsert(psl, 0, x);//在0位置插入数据
}

//头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	SeqListErase(psl, 0);//在0位置删除数据
}

2.2.11 顺序表查找

遍历一遍，一个个找

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);

	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

2.2.12 顺序表销毁

最后的最后，一定要养成好习惯，不要忘记销毁之前申请的空间，防止内存泄漏。

//销毁
void SeqListDestroy(SeqList* psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

2.3 数组相关面试题

删除排序数组中的重复项。26. 删除有序数组中的重复项.

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。27. 移除元素.

合并两个有序数组。88. 合并两个有序数组.

2.4 顺序表的问题及思考

问题：

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

思考：如何解决以上问题呢？下期会给出了链表的结构，现在大家可以想想链表会如何解决这些问题。

到此这篇关于C语言数据结构深入探索顺序表的文章就介绍到这了,更多相关C语言顺序表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言数据结构深入探索顺序表

本文链接: https://www.lsjlt.com/news/143905.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

c语言怎么计算字符串长度

2024-03-01

c++排序函数sort怎么使用

2024-03-01

c语言怎么实现字符串与数字相互转换

2024-02-29

c语言swap函数如何调用

2024-02-29

C语言怎么实现对文件夹加密

2024-02-29

c语言数组形参怎么定义

2024-02-29

c++字符串怎么转化为数字

2024-02-29

c++中使用swap函数报错怎么解决

2024-02-29

c++智能指针怎么调用

2024-02-29

c语言数组怎么作为参数传入函数

2024-02-29

热门问答

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布