顺序表算法练习

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

一.顺序表基础算法

1.说明

博主这里是算法练习,帅气的读者来这里默认已经知道了它,这里主要是针对408考研真题中关于线性表的算法题进行编写。第一部分是根据课本编写线性表的基本函数,剩下四个部分是针对考研真题的算法练习。

2.C语言代码

这里使用C语言实现课本要求的基本算法,一=以一个学生成绩单为例:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MaxSize 50                //这里只是演示,我们假设这里最多存五十个学生信息

//定义学生结构
typedef struct {
	char name[20];              //姓名
	char tel[15];               //电话
	char id[10];               //学号,这个是主键
	int  grade;               //分数
} Elemtype;

//声明使用顺序表
typedef struct {
	/*这里给数据分配内存,可以有静态和动态两种方式,这里采用动态分配*/
	Elemtype  *data;            //存放线性表中的元素是Elemtype所指代的学生结构体
	int length;                 //存放线性表的长度
} SqList;						//给这个顺序表起个名字,接下来给这个结构体定义方法

//初始化线性表
void InitList(SqList &L){
	/*动态分配内存的初始化*/
	L.data = (Elemtype*)malloc(MaxSize * sizeof(Elemtype));  //为顺序表分配空间
	L.length = 0;                                            //初始化长度为0
}

//求表长函数
int Length(SqList &L){
	return L.length;
}

//求某个数据元素值
bool GetElem(SqList &L, int i, Elemtype &e) {
	if (i < 1 || i > L.length)
		return false;         //参数i错误时,返回false
	e = L.data[i - 1];      //取元素值
	return true;
}

//输出线性表
void DispList(SqList &L) {
	if (L.length == 0)
		printf("线性表为空");
	//扫描顺序表,输出各元素
	for (int i = 0; i < L.length; i++) {
		printf("%s   %s   %s     %d", L.data[i].name, L.data[i].tel, L.data[i].id, L.data[i].grade);
		printf("\n");
	}
	printf("\n");
}

//插入数据元素
bool ListInsert(SqList &L, int i, Elemtype e) {
	/*在顺序表L的第i个位置上插入新元素e*/
	int j;
	//参数i不正确时,返回false
	if (i < 1 || i > L.length + 1 || L.length == MaxSize)
		return false;
	i--;                //将顺序表逻辑序号转化为物理序号
	//参数i正确时,将data[i]及后面的元素后移一个位置
	for (j = L.length; j > i; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i] = e;      //插入元素e
	L.length++;         //顺序表长度加1
	return true;
	/*平均时间复杂度为O(n)*/
}

//删除数据元素
bool ListDelate (SqList &L, int i, Elemtype &e) {
	/*删除顺序表中的第i个元素,其值为e*/
	int j;
	if (i < 1 || i > L.length)
		return false;
	i--;              //将顺序表逻辑序号转化为物理序号
	e = L.data[i];
	//参数正确时,将data[i]之后的元素前移一个位置
	for (j = i; j < L.length - 1; j++)
		L.data[j] = L.data[j + 1];
	L.length--;     //顺序表的长度减1
	return true;
	/*平均时间复杂度为O(n)*/
}

//元素查找
int LocateElem(SqList &L, Elemtype e) {
	/*顺序查找第一个值域与e相等的元素逻辑序号(根据e找i)*/
	int i = 0;
	//while循环查找e,这里的依据是姓名
	while (i < L.length && strcmp(L.data[i].name, e.name) != 0)
		i++;
	if (i >= L.length)
		return 0;                      //未找到返回0
	else
		printf("%s    %s    %s     %d", L.data[i].name, L.data[i].tel, L.data[i].id, L.data[i].grade);
	return i + 1;                 //找到后返回其逻辑序号
	/*时间复杂度为O(n)*/
}




3.说明

由于只是算法练习,所以不写完整代码,博主已用线性表完成相关完整项目,可以点击这里查看

二.2010算法真题

1.题目

设将n (n> 1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置,即将R中的数据由(Xo, X,Xn- 1)变换为(Xp, Xp+1,……,Xn-1,X0,X1……,Xp-1).要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。

2.分析

可将问题视为把数组ab转换成数组ba (a代表数组的前p个元素,b代表数组中余下的n-p个元素,先将a逆置得到a -1b,再将a -1b逆置得到(a -1b-1),最后将整个a 'b I逆置得到(a -1b-1)-1=ba。

此算法原理来源于考研线性代数矩阵的转换公式,(a -1b-1)-1=ba。以abcdefgh为例:

  • Reverse (0,p-1)得到cbade fgh;
  • Reverse(p,n-1)得到cbahgfed;
  • Reverse(0,n-1)得到de fghabc;

3.算法代码

//取逆函数
void Reverse(int nums[],int from,int to){
    int i,temp;
    for(i=0;i<((to-from)/2+1);i++){
        temp=nums[to];
        nums[to]=nums[from];
        nums[from]=nums[to];
    }
}
//逻辑函数
void Converse(int nums[],int n,int p){
    Reverse(R,0,p-1);
    Reverse(R,p,n-1);
    Reverse(R,0,n-1);
}

4.说明

最简单的算法题了,必须要会。

考研算法题,不一定看到要时间复杂度和空间复杂度最优就不会,按照平时的练习,能解决问题就行,其余都对只会扣1到2分,哪怕算法不是最优。

所以,如果你想不到这种算法,可以提前申请n个位置,然后把b整体搬迁,能解决问题就行。

三.2011算法真题

1.题目

一个长度为L (L≥1)的升序序列s,处在第[L/2]个位置的数称为s的中位数。例如,若序列Si=(11,13, 15, 17,19),则S;的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2, 4,6,8, 20),则S和S2的中.位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。

2.分析

算法的基本设计思想如下:
分别求两个升序序列A、B的中位数,设为a和b,求序列A、B的中位数过程如下:
①若a=b,则a或b即为所求中位数,算法结束。
②若a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求两次舍弃的长度相等。
③若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等。
在保留的两个升序序列中,重复过程①、②、③,直到两个序列中均只含.一个元素时为止,较小者即为所求的中位数。

3.算法代码

int M_Search(int A[], int B[], int n) {
	int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
	//分别表示序列A和B的首位数、末位数和中位数
	while (s1 != d1 || s2 != d2) {
		m1 = (s1 + d1) / 2;
		m2 = (s2 + d2) / 2;
		if (A[m1] == B[m2])
			return A[m1];			//满足条件①
		if (A[m1] < B[m2]) {			//满足条件②
			if ((s1 + d1) % 2 == 0) { //若元素 个数为奇数
				s1 = m1 ;			//舍弃A中间点以前
				d2 = m2;
			}//舍弃B中间点以后
			else {                 //元素个数为偶数
				s1 = m1 + 1 ;
				//舍弃A中间点及中
				d2 = m2;
				// 舍弃B中间点以后
			}
		} else {
			//满足条件③
			if ((s2 + d2) / 2 == 0) { //若元素 个数为奇数
				d1 = m1;
				//舍弃A中间点以后
				s2 = m2;
				//舍弃B中间点以前
			} else {
				// 元素个数为偶数
				d1 = m1;
				//舍弃A中间点以后
				s2 = m2 + 1;
				//舍弃B中间点及中
			}
			return A[s1] < B[s2] ? A[s1] : B[s2] ;
		}
	}
}

4.补充

答案确实是最标准的算法,但是我们很难想到,最简单想到的就是使用归并排序后再求中位数,考试也可以这么干.

四.2013算法真题

1.题目

[2013统考真题]已知一个整数序列A=(a,a1,.,an-1),其中0≤a;<n (0≤i<n)。若存在ap1=ap2=.=apm=x且m>n/2 (0≤pk<n, 1≤k≤m),则称x为A的主元素。例如A=(0,5,5,3,5,7,5,5), 则5为主元素;又如A=(0,5,5,3,5,1,5,7),则A中没有主元素。假设A中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A的主元素。若存在主元素,则输出该元素;否则输出-1。要求:

  • 1)给出算法的基本设计思想。
  • 2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
  • 3)说明你所设计算法的时间复杂度和空间复杂度。

2.思路

算法的基本设计思想:算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num。然后重新计数,确认Num是否是主元素。
算法可分为以下两步:

  • ①选取候选的主元素。依次扫描所给数组中的每个整数,将第一个遇到的整数Num保存到c中,记录Num的出现次数为1;若遇到的下一个整数仍等于Num,则计数加1,否则计数减1;当计数减到0时,将遇到的下一个整数保存到c中,计数重新记为1,开始新一轮计数,即从当前位置开始重复上述过程,直到扫描完全部数组元素。
  • ②判断c中元素是否是真正的主元素。再次扫描该数组,统计c中元素出现的次数,若大于n/2,则为主元素;否则,序列中不存在主元素。

3.算法代码

int Majority(int A[], int n) {
	int i, c, count = 1;
	//c用来保存候选主元素,count用来计数
	c = A[0] ;
	//设置A[0]为候选主元素
	for (i = 1; i < n; i++)
		//查找候选主元素
		if (A[i] == c)
			count++;
	//对A中的候选主元素计数
		else if (count > 0)
			//处理不是候选主元素的情况
			count-- ;
		else {
			//更换候选主元素,重新计数
			c = A[i];
			count = 1 ;
			if (count > 0)
				for (i = count = 0; i < n; i++) //统计 候选主元素的实际出现次数
					if (A[i] == c)
						count++ ;
			if (count > n / 2) return c;
			// 确认候选主元素
			else return -1 ;
			// 不存在主元素
		}
}

4.补充

我们想不出来这种算法,另一种思路,由于它给定了每个值的范围[0,n]之间,我们可以遍历整个数组等到每个元素的计数器组成新的数组,再遍历这个数组是否有>n/2的存在。

五.2018算法真题

1.题目

给定一个含n (n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3, 2,3}中未出现的最小正整数是1;数组{1,2, 3}中未出现的最小正整数是4。要求:
1)给出算法的基本设计思想。
2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
3)说明你所设计算法的时间复杂度和空间复杂度。

2.思路

要求在时间上尽可能高效,因此采用空间换时间的办法。分配一个用于标记的数组B[n],用来记录A中是否出现了1~n 中的正整数,B[0]对应正整数1,B[n-1]对应正整数n,初始化B中全部为0。由于A中含有n个整数,因此可能返回的值是1~n+1,当A中n个数恰好为1~n时返回n+1。当数组A中出现了大于或等于0或大于n的值时,会导致1~n中出现空余位置,返回结果必然在1~n中,因此对于A中出现了大于或等于0或大于n的值,可以不采取任何操作。

3.算法代码

int findMissMin(int A[], int n) {
	int i, *B;
	B = (int *)malloc(sizeof (int) * n) ; //分配空间
	memset(B, 0, sizeof (int)*n) ;
	for (i = 0; i < n; i++)
		if (A[i] > 0 && A[i] <= n)
			//若A[i]的值介于1~n,则标记数组B
			B[A[i] - 1] = 1;
	for (i = 0; i < n; i++)
		//扫描数组B,找到目标值
		if (B[i] == 0) break;
	return i + 1;
}

4.补充

上一道题的次优解法思路,典型的空间换时间.

六.2020算法真题

1.题目

[2020统考真题]定义三元组(a, b,c) (a, b, c均为整数)的距离D= |a-b|+ |b-c|+|c-a|。给定3个非空整数集合S、S2和S3,按升序分别存储在3个数组中。请设计一个尽可能高效的算法,计算并输出所有可能的三元组(a, b,c)(a∈S,b∈S2, c∈S;)中的最小距离。例如Si={-1,0,9}, S2={-25,-10, 10,11},S3= {2,9, 17,30,41},则最小距离为2,相应的三元组为(9, 10,9)。要求:

  • 1)给出算法的基本设计思想。
  • 2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
  • 3)说明你所设计算法的时间复杂度和空间复杂度。

2.思路

由D的表达式可知,事实上决定D大小的关键是a和c之间的距离,于是问题就可以简化为每次固定c找一个a,使得L3=|c- a|最小。
1)算法的基本设计思想

  • ①使用Dmin记录所有已处理的三元组的最小距离,初值为一个足够大的整数。
  • ②集合S、S2和S3 分别保存在数组A、B、C中。数组的下标变量i=j=k=0,当i<|S|j<|S2|且k< |Ss|时(|S|表示集合S中的元素个数),循环执行下面的a) ~c)。
    • a)计算(A[i], B[], C[k])的距离D; (计算 D)
    • b)若D<Dmin,则Dmin=D; (更新D)
    • c)将A[]、B[小]、C[k]中的最小值的下标+1; (对照分析:最小值为a,最大值为c,这里
      C不变而更新a,试图寻找更小的距离D)
  • ③输出Dmin, 结束。

3.算法代码

顺序表算法练习文章来源地址https://www.toymoban.com/news/detail-475882.html

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

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

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

相关文章

  • 顺序表基本操作算法——基础代码(C语言)

     创建一个顺序表(数据元素个数为5), 输出顺序表中的所有数据元素 查找第3个位置上的元素 查找元素15是否在顺序表中,如果在,请输出该元素在顺序表中的位置 在顺序表中的第1个位置插入数据0 删除刚刚插入的元素 输出顺序表中的所有数据元素 运行结果如下  

    2024年02月06日
    浏览(49)
  • [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板(持续更新)

    [蓝桥杯Python]算法练习、算法基础、算法训练、算法模板( 持续更新..... ) 目录 一、算法基础 1.Huffuman树 2.Sine之舞 3.数列排序 4.数列排序 5.特殊回文数 6.回文数 7.特殊的数字 8.杨辉三角形 9.高精度加法 10.Fibonacci数列 11.报时助手 12.回形取数 13.矩阵乘法 二、算法提高 1.印章

    2023年04月08日
    浏览(49)
  • java基础入门-12-【API(算法,lambda表达式,练习)】

    ​ 数据结构是数据存储的方式,算法是数据计算的方式。 ​ 也叫做顺序查找 ​ 说明:顺序查找适合于存储结构为数组或者链表。 基本思想 基本思想 :顺序查找也称为线形查找,属于无序查找算法。从数据结构线的一端开始,顺序扫描,依次将遍历到的结点与要查找的值

    2024年02月05日
    浏览(56)
  • 第一百零五天学习记录:数据结构与算法基础:顺序表(王卓教学视频)

    注:笔记截图均来自王卓数据结构教学视频 线性表是具有相同特性的数据元素的一个有限序列 同一线性表中的元素必定具有相同特性,数据元素间的关系是线性关系。 稀疏多项式的运算 顺序存储结构存在的问题 1、存储空间分配不灵活 2、运算的空间复杂度高 引出链式存储

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

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

    2024年01月20日
    浏览(50)
  • 顺序表和链表的练习题

    该题目需要先对顺序表进行遍历至元素x正确插入位置,再对顺序表完成插入操作。因此涉及到for循环与if语句的使用 该题目需要对顺序表制定元素删除,并且还需要返回值。所以定义的函数接口不能为void类型,使用for循环对p后继顺序表元素进行遍历前移,且考虑可能出现删

    2024年04月22日
    浏览(48)
  • 【数据结构】顺序表详解(附leetcode练习题)

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺

    2023年04月27日
    浏览(49)
  • 多级缓存测试练习案例导入说明

    为了演示多级缓存,我们先导入一个商品管理的案例,其中包含商品的CRUD功能。我们将来会给查询商品添加多级缓存。 后期做数据同步需要用到MySQL的主从功能,所以需要大家在虚拟机中,利用Docker来运行一个MySQL容器。 为了方便后期配置MySQL,我们先准备两个目录,用于挂

    2024年02月09日
    浏览(26)
  • 超维空间S2无人机使用说明书——55、代码详解:基础PID算法控制无人机的跟随代码详解

    PID,即比例 Proportion、积分 Integral 和微分 Derivative 三个单词的缩写;比例积分微分控制,简称PID控制。 简单讲,根据给定值和实际输出值构成控制偏差,将偏差按比例、积分和微分通过线性组合构成控制量,对被控对象进行控制。 常规 PID 控制器作为一种线性控制器。 步骤

    2024年01月21日
    浏览(64)
  • 趣说数据结构(练习2) —— 顺序表/链表力扣刷题(中等难度)

    力扣原题:https://leetcode.cn/problems/reverse-linked-list-ii/ 题目描述 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left = right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1 输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] 示例 2 输入:h

    2024年02月01日
    浏览(56)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包