2020-2021学年信息学奥赛资料 第十二课 一维数组插入、查找（适用于高中）课件（21张PPT）

第十一课 一组数组插入、查找

目 标
01、学会一维数组的元素插入和删除操作。
02、 学会一维数组的元素查找操作。
一维数组的插入
插入一个元素，需要先找到插入的位置(假设下标为 x)，将这个元素及其之后的所有元素依次往后移一位(注意要从后往前进行操作)，再将给定的元素插入(覆盖)到位置 x，如图 5.3-1 所示。
一维数组的删除
删除某一个元素，也需要先找到删除的位置(假设下标为 x)，将下标为 x+1 及其之后的所有元素依次向前移一位，覆盖原来位置上的元素，如图 5.3-2 所示。
例1、插队问题
【问题描述】
有 n 个人（每个人有一个唯一的编号，用 1~n 之间的整数表示）在一个水龙头前排队准备接水，现在第 n 个人有特殊情况，经过协商，大家允许他插队到第 x 个位置。输出第 n 个人插队后的排队情况。
【输入格式】
第一行 1 个正整数 n，表示有 n 个人，2第二行包含 n 个正整数，之间用一个空格隔开，表示排在队伍中的第 1~ 第 n 个人的编号。
第三行包含 1 个正整数 x，表示第 n 个人插队的位置，1≤x【输出格式】
一行包含 n 个正整数，之间用一个空格隔开，表示第 n 个人插队后的排队情况。
【输入样例】
7
7 2 3 4 5 6 1
3
【输出样例】
7 2 1 3 4 5 6
【问题分析】
n个人的排队情况可以用数组 q 表示，q[i]表示排在第 i 个位置上的人。定义数组时多定义一个位置，然后重复执行：q[i+1] = q[i]，其中，i 从 n ~ x。最后再执行 q[x] = q[n+1]，输出 q[1] ~ q[n]。
国内外研究状况
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar.
#include
using namespace std;
int main(){
int n,i,x,q[102];
scanf( “ %d ” ,&n);
for(i = 1; i <= n; i++) scanf( “ %d ” ,&q[i]);
scanf( “ %d ” ,&x);
for(i = n; i >= x; i--) q[i+1] = q[i];
q[x] = q[n+1];
for(i = 1; i < n; i++) printf( “ %d “ ,q[i]);
printf( “ %d\n ” ,q[n]);
return 0;
}
国内外研究状况
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar.
例2、队伍调整
【问题描述】
有 n 个人（每个人有一个唯一的编号，用 1~n 之间的整数表示）在一个水龙头前排队准备接水，现在第 x 个人有特殊情况离开了队伍，求第 x 个人离开队伍后的排队情况。
【输入格式】
第一行 1 个正整数 n，表示有 n 个人，2第二行包含n个正整数，之间用一个空格隔开，表示排在队伍中的第1个到第n个人的编号。
第三行包含 1 个正整数 x，表示第 x 个人离开队伍，1≤x≤n。
【输出格式】
一行包含 n-1 个正整数，之间用一个空格隔开，表示第 x 个人离开队伍后的排队情况。
国内外研究状况
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec luctus nibh sit amet sem vulputate venenatis bibendum orci pulvinar.
【输入样例】
7
7 2 3 4 5 6 1
3
【输出样例】
7 2 4 5 6 1
#include
using namespace std;
int main(){
int n,i,x,q[102];
scanf( “ %d ” ,&n);
for(i = 1; i <= n; i++) scanf( “ %d ” ,&q[i]);
scanf( “ %d ” ,&x);
for(i = x; i < n; i++) q[i] = q[i+1];
n--;
for(i = 1; i < n; i++) printf( “ %d “ ,q[i]);
printf( “ %d\n ” ,q[n]);
return 0;
}
一维数组的查找统计
一维数组的查找操作，就是在一维数组中查找有没有某个元素，它的值等于指定的值 x。查找操作的结果可能是一个没找到、找到一个或者找到很多个。常见的查找算法有“顺序”查找和“二分”查找。
顺序查找就是按照从前往后的顺序，将数组中的元素依次与要查找的数 x 进行比较。
二分查找又称“折半”查找，其优点是比较次数少、查找速度快。但是要求数据是递增或递减排序的。
二分查找
int left = 0，right = n - 1;
int find = n;//find标记找到的位置，初始化为n，表示没找到
while(left <= right){
int mid = (left + right) / 2;
if(a[mid] == x){//找到了，就标记位置，并退出循环
find = mid;
break;
}
if(x < a[mid]) right = mid - 1;//x只能在左半部分
if(a[mid] < x) left = mid + 1; //x只能在右半部分
}
if(find != n) printf("%d\n",find);
else printf("not find\n");
例1、抽奖1
【问题描述】
公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人依次公布 n 个不同的获奖号码，小谢看着自己抽奖券上的号码 num，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中的是第几个号码；如果没有中奖，请输出 0。
【输入格式】
第一行一个正整数 n，表示有 n 个获奖号码，2第二行包含 n 个正整数，之间用一个空格隔开，表示依次公布的 n 个获奖号码。
第三行一个正整数 num，表示小谢抽奖券上的号码。
1≤获奖号码，num<10000。
【输出格式】
一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为 0。
【输入样例】
7
17 2 3 4 9555 6 1
3
【输出样例】
3
参考代码：
#include
using namespace std;
int main(){
int n,i,num,f,g[101];
scanf( “ %d ” ,&n);
for(i = 1; i <= n; i++) scanf( “ %d ” ,&g[i]);
scanf( “ %d ” ,&num);
f = 0;
for(i = 1; i <= n; i++)
if(g[i] == num){f = i; break;}
printf( “ %d\n ” ,f);
return 0;
}
例2、抽奖2
【问题描述】
公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人从小到大依次公布 n 个不同的获奖号码，小谢看着自己抽奖券上的号码 win，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中奖的是第几个号码；如果没有中奖，请输出 0。
【输入格式】
第一行一个正整数 n，表示有 n 个获奖号码，2第二行包含 n 个正整数，之间用一个空格隔开，表示依次公布的 n 个获奖号码。
第三行一个正整数 win，表示小谢抽奖券上的号码。
1≤获奖号码，win<10000。
【输出格式】
一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为 0。
【输入样例】
7
1 2 3 4 6 17 9555
3
【输出样例】
3
参考代码:
#include
using namespace std;
int main(){
int n,i,win,f,left,right,mid,g[101];
scanf( “ %d ” ,&n);
for(i = 1; i <= n; i++) scanf( “ %d ” ,&g[i]);
scanf( “ %d ” ,&win);
f = 0; left = 1; right = n;
while(left <= right){
mid = (left + right) / 2;
if(g[mid] == win){f = mid; break;}
if(win < g[mid]) right = mid - 1;
if(g[mid] < win) left = mid + 1;
}
printf( “ %d\n ” ,f);
return 0;
}
例3、比身高
【问题描述】
有 N 个人排成一排，假设他们的身高均为正整数，请找出其中符合以下条件的人：排在他前面且比他高的人数与排在他后面且比他高的人数相等。
【输入格式】
第一行为一个正整数 N，1下面 N 行，每行一个正整数，表示从前往后每个人的身高，假设每个人的身高≤10000。
【输出格式】
一行一个整数，表示满足这个条件的人数。
【输入样例】
4
1
2
1
3
【输出样例】
2
【样例说明】
第 3、第 4 个人满足条件。
参考代码：
#include
using namespace std;
int h[1001],n,i,j,ans,t1,t2;
int main(){
scanf( “ %d ” ,&n);
for(i = 1; i <= n; i++) scanf( “ %d ” ,&h[i]);
for(i = 1; i <= n; i++){
t1 = t2 = 0;
for(j = 1; j < i; j++)
if(h[j] > h[i]) t1++;// 排在他前面且比他高的人数
for(j = i + 1; j <= n; j++)
if(h[j] > h[i]) t2++;// 排在他后面且比他高的人数
if(t1 == t2) ans++;
}
printf( “ %d\n ” ,ans);
return 0;
}