首页 > 其他分享 >顺序表题目

顺序表题目

时间:2022-10-05 23:02:18浏览次数:49  
标签:顺序 题目 val 插入 ran int data

1. 顺序表上的查找

题目描述:定义函数,传入要被查找的顺序表和要查找的值,如果找到返回值的索引,不存在则返回-1,并输出"不存在"即可。

int search(RankList ran,int val){  //传入的形参,因为并不需要改变顺序表中的值,所以不用传入引用
    for(int i=0;i< ran.length;i++){ //一个for循环即可搞定,如果值是在顺序表中,则该函数就会在for循环内返回,就结束了,如果出了循环那就说明传入的值并不在顺序表中,所以输出说明并返回-1即可
        if(ran.data[i] == val){
            return i;
        }
    }
    cout<<"该值不存在顺序表中"<<endl;
    return -1;
}

2. 在递增顺序表中插入一个元素使顺序表仍然递增

题目描述:一非递减有序的顺序表ran1,现插入元素val,写一函数保证ran1仍然非递减有序

​ 1.首先看到这道题第一反应是先找到要插入的位置,使 ran1.data[i] < val < ran1.data[i+1] ,确定val应该插入到索引为i的位置,然后再进行插入操作,这样一来就是两个for循环

​ 2.进行优化,如果是边寻找要插入的位置边进行移动怎么样呢,这样只有一次for循环

int insert_plus(RankList &ran,int val){
	int i=0; 
	if(ran.length == ran.max_size) return -1; //因为是插入所以要判断当前长度是否和最大相等
/*
边移动边寻找插入的位置,因为是插入所以移动一定是向后移动的,所以从后向前进行循环,又已知该顺序表是递增的,所以只要找到符合ran.data[i] < val这个式子就可以停止循环了,此时i就是我们要插入的索引位置

*/
	for(i = ran.length;i>= 0 && ran.data[i-1]>val ;i--){//循环,尤其要注意这里的条件判断,ran.data[i-1] >val,一定不能是ran.data[i] >val,因为在还没有插入的时候ran.data[i]是没有值的,所以就直接跳出循环了
		ran.data[i] = ran.data[i-1];
	}
	
	ran.data[i] = val; //插入找到的索引位置
	ran.length ++;  // 别忘了长度加1
	return 0;
} 

3.两递增顺序表求交集,并输出新的顺序表

题目描述:假设现在用两个递增有序的顺序表L1和L2存储集合A和B,求这两个集合的交集C,得到新的顺序表L3

​ 1.要得到的是交集,也就是两个顺序表中重复的元素,在此为了不再开辟多余的内存空间l3所以复用原表的空间

​ 2.依次比较L1和L2中的相应元素,若相等,该元素副本进入L3;否则,较小元素所在的表下标后移。某个表搜索结束则循环结束,交集元素存在于L3表。

// 求两个递增顺序表的交集 
void merge(RankList &l1,RankList &l2,RankList &l3){
	
	int i=0;
	int j=0;
	int k=0;
	if(l1.length <= l2.length){
		l3.data = l1.data;  //这个是什么意思呢 
	//	cout<<&(l3.data)<<endl;  //这个表示的是l3自己的首地址,是另外一个量,指向了l1的首地址,所以l3可以使用l1的空间 ,避免了空间的开辟 
	//	cout<<&(l1.data)<<endl;  //这个是l1自己的首地址 
	}

	else
		l3.data = l2.data;
		
	while(i<l1.length&&j<l2.length){
		if(l1.data[i]<l2.data[j])  //如果是l1中的元素小,则顺着顺序表向后移动 
			i++;
		else if(l1.data[i]>l2.data[j])
			j++;
		else if(l1.data[i] == l2.data[j]){ // 如果相等则存入到新的顺序表l3中 
			l3.data[k++] = l1.data[i++];
			j++;
		}

	}
	l3.length = k;
	if(l1.length<l2.length)
		clear(l2);
	else
		clear(l1); //使用完后即可清除堆区元素 
	
}

标签:顺序,题目,val,插入,ran,int,data
From: https://www.cnblogs.com/hahakken/p/16756681.html

相关文章

  • 9.29题目大赏
    2022-9-29前两道真的很水,然而我写挂了QAQT1智力大冲浪简单得不能再简单的贪心。先将每个游戏按扣钱为第一关键字降序,时刻为第二关键字升序排列。因为我们希望无法完成......
  • LeetCode - 字符串类型题目
    剑指Offer05.替换空格请实现一个函数,把字符串 s 中的每个空格替换成"%20"。方法:双指针首先统计空格数量count,然后为原字符串数组扩展出2*count的空间,用来存......
  • SQL语句的执行顺序
    原文链接:https://blog.csdn.net/weixin_37646636/article/details/121459732(8)SELECT(9)DISTINCT(11)(1)FROM(3)JOIN(2)ON(4)WHERE(5)GROUPBY(6)WITH{CUBE|......
  • 顺序表10/4
    #include<stdio.h>#include<stdlib.h>#defineMAXSIZE20typedefstructLNODE{charlist[MAXSIZE];intlistlen;//表的当前长度}*List,L;ListnewList();voidshowLis......
  • 题目
    题目1.列举你所了解的计算机存储设备类型?答:随机存储器RAMSRAM、DRAM(SDRAM、RDRAM、CDRAM等)只读存储器ROMMROM、PROM、EPROM、EEPROM2.一般代码存储在计算机的哪个设备中?......
  • 静态初始化块的执行顺序
    如果定义初始化块时使用了static修饰符,则变成了静态初始化块。静态初始化块时类相关的,系统将在类初始化阶段执行静态初始化块,而不是在创建对象时才执行。因此静态初始化块......
  • 排序只要按顺序走就一定没问题
    只要遵循第一个先和第二个比较,第二个在和第三个比较,就不用再第一个和第三个比较了三个都比:#include<iostream>#include<cmath>#include<algorithm>usingnamespac......
  • Atcoder 题目选做
    ABC257G直接考虑\(\rmKMP\)的过程。\(\rmKMP\)可以帮助我们求出\(S\)的\(border\),并找到\(T\)中每一个位置能匹配上的\(S\)的最长前缀。那么我们就可以很......
  • 静态初始化块的执行顺序
    单个类中初始化块、静态初始化块、构造器的执行顺序。无论怎么写,先执行第一个的是静态初始化块,第二个是初始化块,第三个是构造器,如果写了多个的时候从上往下执行,比如写了多......
  • 顺序栈的双端储存
    顺序栈的双端储存1.双端栈在栈的共享技术中最常用的是两个栈的共享技术即双端栈:主要利用了栈“栈底位置不变,而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一......