C/C++ 第五讲 一维数组

5.1 数组的定义

问题：给定N个学生成绩，求高于平均分者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//简单变量逐一处理(N=5)
int k=0;
float ave,sum=0,s1,s2,s3,s4,s5;
cin>>s1>>s2>>s3>>s4>>s5;
sum=s1+s2+s3+s4+s5;
ave=sum/N;
if(s1>ave)
    k++
.....//效率太低
//引入新数据类型批量处理（N=5)
int k=0;
float s[N], ave, sum=0;
for (i=0;i<N;i++)
{
    sum+=s[i];
}
ave=sum/N;
for(i=0;i<N;i++)
    if(s[i]>ave)
        k++;
//数组：对一组数据的重复操作进行批量处理

数组的概念、特点

  • 是同类型同性质的一组元素顺序存放构成的数据集合；
  • 所有数据共用同一名字，通过下标区分；
  • 循环控制下标来批量处理数据。

数组的定义

1
数据类型 数组名[整型常量表达式]
  • 数组名代表数组在内存中的首地址，由系统自动分配；
  • 整型常量表达式代表数组长度，此处不可用变量说明长度；
  • 下标范围0~长度-1
1
2
3
4
5
6
7
8
9
10
11
//正确例：
#define N 5
float s[N];
//或者：
const int n=5;
float s[n];

//错误例：
int n=5, s[n];//长度不允许用变量
double d[];//长度不允许为空
float b[3.4]//长度不允许非整形

数组的存储

元素的访问

数组名[下标]

  • 数组元素相当于同类型的普通变量，可参与该类型变量允许的一切操作
  • 对于数值型数组，只能操作数组元素，不能操作数组名

5.2 一维数组的初始化

问题：将十进制整数n转换成r(2~16)进制

例：

转换方法：

  1. n%r得到最低位存放进a[0];
  2. n=n/r，再进行n%r，得到倒数第二位a[1];
  3. 以此类推，直到n=0.

输出方法：

  • 从数组最末元素向前输出。
  • 制作对照表，将10-15转换为A~F。16进制所需数字的字母放在长度16的字符数组中

数组初始化

  • 定义的同时允许对数组的部分或全部元素赋初值；
  • 初值应被组织在{}内
    • 字符数组表示的字符串例外
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//全部元素赋初值:
int a[5]={0,2,4,6,8}
//可省略数组长度
int a[]={0,2,4,6,8}
//相当于：
a[0]=0; a[1]=2; a[2]=4; a[3]=6; a[4]=8;

//部分元素赋初值
//未赋值元素默认为0
int a[10]={1,3,5,7,9}
//a[5]~a[9]皆为0

//常见错误：
int a[10];
a={1,3,5,7,9}//数组名不能被赋值
int a[10];
a[10]={...}//a[10]不是合法元素，也不能被赋集合值
int c[3]={1,2,3,4}//初值个数超过数组长度

数制转换：（10进制–>r进制）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "iostream"
using namespace std;
int main()
{
    int i=0,r,n,a[10];
    char b[16]={'0','1','2',...,'A','B','C','D','E','F'}
    cin>>n>>r;
    do 
    {
        a[i]=n%r;
        n=n/r;
        i++;
    }while(n!=0);
    for(--i;i>=0;--i)
    {
        n=a[i];
        cout<<b[n];
    }
    system("pause");
    return 0;
}

5.3 常用算法-选择法排序

例：N个成绩从大到小排序

选择法排序：

  1. N个数中选出MAX与第一个数交换位置；
  2. N-1数中选出MAX与第二个数交换位置；
  3. 以此类推，重复N-1遍。
  • rand()函数
    • 随机数范围：0~32767
    • 原型在头文件stdlib.h
    • 范围随机数：rand()%(a+1)+b (b~b+a)
  1. 求最高分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define N 10
#include "iostream"
using namespace std;
int main()
{
    int a[N],i ,max;
    for (i=0;i<N;i++)
    {
        a[i]=rand()%101;
        cout<<a[i]<<' ';
    }
    max=a[0];
    for(i=1;i<N;i++)
        if (a[i]>max)
            max=a[i];
    cout<<"max="<<max<<endl;
    system("pause");
    return 0;
}
  1. 求最高分位置
1
2
3
4
imax=0;
for(j=1;j<N;j++)
    if (a[j]>a[imax])
        imax=j;
  1. 最高分放在首位
1
2
3
int t=a[0];
a[0]=a[imax];
a[imax]=t;
  1. 次高分，次次高分……循环。（N-1遍）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
imax=1;
for(j=2;j<N;j++)
    if (a[j]>a[imax])
        imax=j;
int t=a[1];
a[1]=a[imax];
a[imax]=t;
//循环重复:

for(i=0;i<N-1;i++)
{
    imax=i;  //注意i需变
    for(j=i+1;j<N;j++)
        if (a[j]>a[imax])
            imax=j;
    if (i!=imax)
    {
        int t=a[i]; 
        a[i]=a[imax];
        a[imax]=t;
    }
}

5.4 冒泡法排序

例：对含N个元素的数组用冒泡法由小到大排序。

思想：

  1. 自a[0]始，两两相邻元素进行N-1次比较，若前>后则交换这对元素。一次遍历后最大的元素存在a[N-1]中；
1
2
3
4
5
6
7
for(i=0;i<N-1;i++)
    if (a[i]>a[i+1])
    {
        t=a[i];
        a[i+1]=a[i];
        a[i]=t;
    }
  1. 对a[0]~a[N-2]的N-1个数进行此操作，次大数存入a[N-2]；
1
2
3
4
5
6
7
8
for (j=0;j<N;j++)
    for(i=0;i<N-1-j;i++)
        if (a[i]>a[i+1])
        {
            t=a[i];
            a[i+1]=a[i];
            a[i]=t;
        }
  1. 以此类推N-1次。

完整程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define N 10
#include "iostream"
using namespace std;
int main()
{
    int a[N],i ,j,t;
    for (i=0,i<N;i++)
    {
        a[i]=rand()%101;
        cout<<a[i]<<' ';
    }
    for (i=0;i<N-1;i++)
    for(j=0;j<N-1-i;j++)
        if (a[j]>a[j+1])
        {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
        }
    cout<<"\n after sort: \n";
    for(i=0;i<N;i++)
        cout<<a[i]<<' '; 
    system("pause");
    return 0;
}

5.5 常用算法-插入与删除

插入

例：在递增数组a内插入数x，使插入后数组仍保持有序。

  1. 查找x应插入的位置k；
  2. 下标k的元素到最后的元素依次后移；
  3. x插入位置k。
  • 移动：从最后元素移起
1
2
for(i=n-1;i>=k;i--)
    a[i+1]=[i];

完整程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define N 10
#include "iostream"
using namespace std;
int main()
{
    int a[N],i,k,x,n;
    cout<<"递增输入数组中现有元素个数：";
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    cout<<"输入待插入数据：";
    cin>>x;
    //输入完成，开始处理：
    //找位置：
    for(i=0;i<n;i++)
        if (x<a[i])
            break;
    k=i;
    //移动，挪出位置
    for(i=n-1;i>=k;i--)
        a[i+1]=[i];
    //插入新数据
    a[k]=x;
    //输出新数组
    for(i=0;i<n+1;i++)
        cout<<a[i]<<' ';
    system("pause");
    return 0;
}

删除

例：查找数据x是否是数组a中元素，若是，删除第一次出现的该元素；否则提示“没找到”。

思想：

  1. 查找待删除元素的位置k；
  2. 若找到，下标k+1的元素到最后的元素依次后移；
  3. x插入位置k。
  • 移动：前移（覆盖）
1
2
for(i=k;i<n-1;i++)
    a[i]=a[i+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(i=0;i<n;i++)
if(x==a[i])
    break;
k=i;
if(i==n)//注意这里是n
    cout<<"未找到\n";
else
{
    //前移删除后的数据
    for(i=k;i<n-1;i++)
        a[i]=a[i+1];
    for(i=0;i<n-1;i++)
        cout<<a[i]<<' ';
}

5.6 常用算法-二分法查找

数据量大，顺序查找效率低

例：在长度为N按递增顺序排列的数组a中用二分法查找数key，找到、输出其位置；否则输出“没找到”。

思想：

  1. low和high是查找区间的起终点下标，则初始状态：low=0, high=N-1;

  2. 求待查区间中间元素的下标mid=(low+high)/2，然后比较a[mid]和x决定后续查找范围；

  3. 当x==a[mid]，查找完毕

    当x>a[mid]，修改low=mid+1

    当x<a[mid]，修改high=mid-1

  4. 重复2、3；若low>high则null

注：

  • 二分法只适用于有序数组；
  • 终止循环查找的两种情况：
    • x==a[mid]
    • low>high
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
low=0;
high=N-1;
while(low<=high)
{
    mid=(low+high)/2
        if (x==a[mid])
            break;
        else if(x>a[mid])
            low=mid+1;
        else
            high=mid-1;
}
if(low>high)
    cout<<"没找到"<<endl;
else
    cout<<mid<<endl;

例题

  1. N个学生，围成一圈，1-5报数，报到5的同学出圈。问最后剩下的一名同学起初序号为几？

a[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[N],k=0,i;  //i:序号；k:报数次数
int s=0;  //报的数
for(i=0;i<N;i++)
    a[i]=1;
while(k!=N-1)
{
    for(i=0;i<N;i++)
    {
        s=s+a[i];
        if(s==5)
        {
            s=0;
            k++;
            a[i]=0;
        }
    }
}
cout<<i<<endl;
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

Comments