初阶数据结构:顺序表相关题目练习

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

一,引子

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

二, 练习题目

1. 移除指定元素

题目要求:
初阶数据结构:顺序表相关题目练习,数据结构,算法
题目信息:

  1. 数组nums
  2. 数组长度numsSize
  3. 移除元素值val

题目链接:
题目:移除元素

方法1(空间换时间):

思路(时间复杂度 O(n) 空间复杂度 O(n)):开辟一块相同大小的空间,将原数组中不等于val的值拷贝进新空间内。遍历完成后,将新空间中的数据再拷贝回原数组中。

过程演示:
初阶数据结构:顺序表相关题目练习,数据结构,算法

int removeElement1(int* nums, int numsSize, int val)
{
	//开辟新空间
	int* arr = (int*)malloc(numsSize * sizeof(int));
	int i = 0;
	int j = 0;
	
	//将不等于val的值复制至新空间内
	for (i = 0; i < numsSize; i++)
	{
		if (nums[i] != val)
		{
			arr[j] = nums[i];
			j++;
		}
	}
	
	//将数据拷贝会原数组
	memcpy(nums, arr, (j * sizeof(int)));
	
	//释放申请的新空间
	free(arr);

	return j;
}

方法2(挪动覆盖元素):

思路(时间复杂度 O(n^2) 空间复杂度 O(1)):遍历数组,若数组元素等于val,将数组后面元素整体前移覆盖,若不等于下标加1。

过程演示:
初阶数据结构:顺序表相关题目练习,数据结构,算法

int removeElement2(int* nums, int numsSize, int val)
{
	//原地挪动覆盖
	//时间复杂度O(n^2),空间复杂度O(1)
	int len = numsSize;
	int i = 0;
	while (i < len)
	{
		if (nums[i] == val)
		{
			int j = i;
			while (j < len - 1)
			{
				nums[j] = nums[j + 1];
				j++;
			}
			len--;
		}
		else
		{
			i++;
		}
	}

	return len;
}

2. 删除有序数组中的重复项

题目要求:
初阶数据结构:顺序表相关题目练习,数据结构,算法
题目信息:

  1. 数组nums
  2. 数组长度numsSize
  3. 数组为非严格递增序列(不递减)

题目链接:
题目:删除重复项

方法1(空间换时间):

思路(时间复杂度 O(n) 空间复杂度 O(n)):开辟等大小空间,将每个元素拷贝一份到新空间中,最后全部拷贝回去。

int removeDuplicates1(int* nums, int numsSize)
{
	//额外空间拷贝
	int* arr = (int*)malloc(numsSize * sizeof(int));

	int i = 0;
	int j = 0;
	
	while (i < numsSize)
	{
		if (i + 1 >= numsSize || nums[i] != nums[i + 1])
		{
			arr[j] = nums[i];
			j++;
		}
		i++;
	}

	memcpy(nums, arr, j * sizeof(int));

	free(arr);

	return j;
}

方法2(挪移覆盖):

思路(时间复杂度 O(n^2) 空间复杂度 O(1)):将重复出现的元素使用数组后续元素挪移覆盖。

int removeDuplicates2(int* nums, int numsSize)
{
	//非严格递增排列
	//暴力求解挪移
	//O(n^2)
	int i = 0;
	int len = numsSize;
	while (i < len - 1)
	{
		if (nums[i] == nums[i + 1])
		{
			int j = i;
			while (j < len - 1)
			{
				nums[j] = nums[j + 1];
				j++;
			}
			len--;
		}
		else
		{
			i++;
		}
	}

	return len;
}

3. 合并两个有序数组

题目要求:
初阶数据结构:顺序表相关题目练习,数据结构,算法
题目信息:

  1. 两个数组:nums1,nums2
  2. 两数组中分别的元素个数:m,n
  3. 两数组容量:numsSize1,numsSize2
  4. 两数列都为非严格递增序列
  5. 最后合并数据存放在数组nums1

题目链接:
题目:合并两个有序数组

方法1(从前向后比较,需要额外空间):

注:从前向后往nums1数组中拷贝数据会对原数据产生覆盖,所以需要开辟新空间。

void merge1(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int* cp_num = (int*)malloc((m + n) * sizeof(int));
	int* long_num = nums1;
	if (nums1Size < nums2Size)
	{
		long_num = nums2;
	}

	int i = 0;
	int j = 0;
	int x = 0;
	while (i < m || j < n)
	{
		//nums2为空数组
		if (j == n || (i < m && nums1[i] <= nums2[j]))
		{
			cp_num[x] = nums1[i];
			i++;
		}
		else
		{
			cp_num[x] = nums2[j];
			j++;
		}
		x++;
	}
	
	memcpy(long_num, cp_num, (m + n) * sizeof(int));

}

方法2(从后向前比较):

从后比较,自后向前拷贝数据,不会产生数据的覆盖,直接拷贝到nums1中。

void merge2(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	//非递减顺序
	//1. 比大小,将较小的元素放入大数组中(从前往后)
	//2. 将较大的元素放入大数组中(从后往前)

	int* long_num = nums1;
	if (nums1Size < nums2Size)
	{
		long_num = nums2;
	}

	int end1 = m - 1;
	int end2 = n - 1;
	int insert = m + n - 1;
	while (end1 >= 0 || end2 >= 0)
	{
		//特殊情况,有一个数组插入完成
		//nums1插入完,nums2插入完
		if ((end2 < 0) || (end1 >= 0 && nums1[end1] >= nums2[end2]))
		{
			long_num[insert] = nums1[end1];
			end1--;
		}
		else
		{
			long_num[insert] = nums2[end2];
			end2--;
		}
		insert--;
	}
}

方法2(改):

注:(优化)当nums2中的元素插入完成,nums1没有插入完成无,需再进行插入操作,数组中数据本就有序。文章来源地址https://www.toymoban.com/news/detail-807530.html

void merge3(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int end1 = m - 1;
	int end2 = n - 1;
	int end = m + n - 1;

	//固定为nums1存放合并后的数组
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] >= nums2[end2])
		{
			nums1[end--] = nums1[end1--];
		}
		else
		{
			nums1[end--] = nums2[end2--];
		}
	}

	//nums1中的元素未遍历完,nums1的剩余元素本就有序,无需再插入
	while (end2 >= 0)
	{
		nums1[end--] = nums2[end2--];
	}
}

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

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

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

相关文章

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

    今天要讲的堆,不是操作系统虚拟进程地址空间中(malloc,realloc等开空间的位置)的那个堆,而是数据结构中的堆,它们虽然名字相同,却是截然不同的两个概念。堆的底层其实是 完全二叉树 ,如果你问我,完全二叉树是什么。好吧,那我先从树开始讲起,开始我们今天的

    2024年03月14日
    浏览(55)
  • 数据结构初阶--二叉树的顺序结构之堆

    目录 一.堆的概念及结构 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日
    浏览(42)
  • 数据结构(初阶):顺序表实战通讯录

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

    2024年04月16日
    浏览(34)
  • 【数据结构初阶】顺序表和链表(1)

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

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

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

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

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

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

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

    2024年02月03日
    浏览(44)
  • 数据结构初阶之二叉树性质练习与代码练习

    个人主页:点我进入主页 专栏分类:C语言初阶      C语言程序设计————KTV       C语言小游戏     C语言进阶 C语言刷题       数据结构初阶    Linux 欢迎大家点赞,评论,收藏。 一起努力,共赴大厂。 目录 1.前言 2.性质练习 3.代码练习  3.1单值二叉树 3.2检查两颗树

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

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

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

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

    2024年02月16日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包