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