c++ 一维数组(包括排序与例题)

一、一维数组的知识

####  扩:setw(输出的宽度)  C++ 中的格式化函数，用于指定输出流的宽度。不能用于输入流 
#### 一维数组：一组相同类型的变量
  ## 格式：类型标识符 数组名[常量表达式];     eg: int a[5];
               -- 类型标识符(基本数据类型/结构体等构造类型) 
  ## 引用数组格式：数组名[下标]   
     eg: h[5]、h[i*2+1]等。
     注意1：下标只能为整型常量或整型表达式 √√√
           -- 整型表达式而不是整形变量  √√√
     注意二：下标值必须在数组定义的下标范围内    
     注意三：不能一次引用整个数组，只能逐个引用数组的单个元素。
     注意四：单输出数组名，返回数组的首地址 
  ## sizeof会返回数据类型的(字节)大小  int = 4字节 =（4*8）32位  1字节 = 1字符 = 1/2汉字 √√√ 
    eg:int a[3]={1,2,3};
       int b=12;
       cout << sizeof(a) << endl;
       cout << sizeof(b) << endl;
  ## system("pause")     -- 暂停程序的执行(暂停命令行窗口)  目的:为了查看程序的结果/错误信息 
  ## 数组在计算机内存单元中是连续存储的 
  ## 数组的插入思路：从最后开始往后移动直到插入后的位置逐步加一，然后开始插入x   √√√ 
  ## 数组的删除思路：从删除的位置之后开始往前i减一(直接进行覆盖，不用再删除)   √√√ 
  ## 数组的查找x:
     # 查找操作的结果：可能是一个没找到、找到一个或者找到很多个
     # 常见的查找：顺序查找和二分查找 
     # 顺序查找：按照从前往后的顺序，将数组中的元素依次与要查找的数x进行比较。
     # 二分查找(折半查找)：√√√ 
        要求：数据是递增或递减排序的。数据是有序的。
        left  right  mid=(left+right)/2  循环：mid跟查找x比较，找到输出位置；
        若没找到，若在左面，right=mid-1，若在右面，left=mid+1 
        优点：比较次数少、查找速度快。
  ## 数组的排序问题：通过数组中的元素比较和交换来实现的，关键是数组下标的分析   √√√ 
   # 选择排序：从小到大：假设一个最小的，依次每个与最小的进行比较(获取最小的) 放在第一个位置(依次放到第二个位置.... )
   # 冒泡排序：从小到大：每一轮依次两两进行比较，大的交换到后面(依次第二后，第三后...) 
   # 插入排序: 
     思想：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排序的。
        每一趟都是把后一段的第一个数“插入”到前一段的某一个位置，保证前一段仍然是有序的。
        开始时，第 1 个数作为前一段肯定是有序的；第一趟，把第 2 个数插入进去，保证前 2个数有序；
        第二趟，把第 3 个数插入进去，保证前 3 个数有；……第 n-1 趟，把第 n 个数插入进去，保证 n 个数都有序。                          
二、数组的整体赋值
整体赋值(统一赋值)：给数组按字节整体赋值，按元素整体赋值： 
## fill(d,d+5,8);   //给d数组的前5个元素赋值为8 
## memset(c,0,5);   //给数组前5个字节都赋值为 0 
## memset(b,1,sizeof(b));   //将b数组所有元素均赋值，按照sizeof(int) = 4字节 = 每一字节按8位计算2^0+2^8+2^16+2^24  
## 示例： 
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int a[10],b[10],c[10],d[10],i;
    memset(a,0,sizeof(a));   // 将a数组所有元素均赋值为0
    for(i = 0; i < 9; i++) cout << a[i] <<  " " ;
    cout << a[9] << endl; 
    memset(b,1,sizeof(b));// 将 b 数组所有元素均赋值
    //二进制数 2^0+2^8+2^16+2^24=16843009
    for(i = 0; i < 9; i++) cout << b[i] <<  "  " ;
    cout << b[9] << endl; 
    memset(c,0,5);
    //将 c 数组前 5 个字节都赋值为 0，所以只能确定 c[0]
    //等于0，其他元素值不确定
    for(i = 0; i < 9; i++) cout << c[i] <<  "  " ;
    cout << c[9] << endl;
    fill(d,d+5,8);
    //将 d 数组前 5 个元素都赋值为 8，其他元素值不确定
    for(i = 0; i < 9; i++) cout << d[i] <<  "  " ;
    cout << d[9] << endl;
    return 0;
}
三、下楼梯问题
【问题描述】
一个楼梯有 n 级，小苏同学从下往上走，一步可以跨一级，也可以跨两级。问：他走到第 n 级楼梯有多少种走法？
【输入格式】
一行一个整数 n，0<n≤30。
【输出格式】
一行 n 个整数，之间用一个空格隔开，表示走到第 1 级、第 2 级、……第 n 级分别有多少种走法。
【输入样例】
2
【输出样例】
1 2
#### 【问题分析】
假设 f (i) 表示走到第 i 级楼梯的走法，则走到第 i (i>2)级楼梯有两种可能：一种是从第 i-1级楼梯走过来；另一种是从第 i-2 级楼梯走过来。
根据加法原理，f (i) = f (i-1) + f (i-2)，边界条件为：f (1) = 1，f (2) = 2。
具体实现时，定义一维数组 f，用赋值语句从前往后对数组的每一个元素逐个赋值。本质上，f (i) 构成了斐波那契数列 
#### 解法： 
#include<cstdio>
using namespace std;
int main(){
    int n,i,f[31];
    scanf( " %d " ,&n);
    f[1] = 1; f[2] = 2;
    for(i = 3; i <= n; i++) f[i] = f[i-1] + f[i-2];
    for(i = 1; i < n; i++) printf( " %d  ",f[i]);
    printf( " %d\n " ,f[n]);
    return 0;
}
四、幸运数问题： 
【问题描述】
判断一个正整数 n 是否能被一个“幸运数”整除。幸运数是指一个只包含 4 或 7 的正整数，如 7、47、477 等都是幸运数，17、42 则不是幸运数。
【输入格式】
一行一个正整数 n，1≤n≤1000。
【输出格式】
一行一个字符串，如果能被幸运数整除输出“YES”；否则，输出“NO”。
【输入样例】
47
【输出样例】
YES
#### 【问题分析】
分析发现，1~1000 范围内的幸运数只有 14 个。于是，将这 14 个幸运数直接存储到一个数组 lucky 中，再穷举判断其中有没有一个数能整除 n。
#### 代码：
//p5-2-3
#include<cstdio>
using namespace std;
int main(){
    int n,lucky[14] = {4,7,44,47,74,77,444,447,474,477,744,747,
                                   774,777};// 在数组定义时给数组赋值
  scanf( "  %d "  , &n);
    bool flag = false;
    for(int i = 0; i < 14; i++)
           if(n % lucky[i] == 0) flag = true;
    if(flag) printf( "  YES\n "  );
    else printf( "  NO\n "  );
    return 0;
}
五、插队问题(数组的插入x)： 
(数组的插入)思路：从最后开始往后移动，直到插入后的位置，然后开始插入 
【问题描述】
有 n 个人（每个人有一个唯一的编号，用 1~n 之间的整数表示）在一个水龙头前排队准备接水，
现在第 n 个人有特殊情况，经过协商，大家允许他插队到第 x 个位置。输出第 n 个人插队后的排队情况。
【输入格式】
第一行 1 个正整数 n，表示有 n 个人，2<n≤100。
第二行包含 n 个正整数，之间用一个空格隔开，表示排在队伍中的第 1~ 第 n 个人的编号。
第三行包含 1 个正整数 x，表示第 n 个人插队的位置，1≤x<n。
【输出格式】
一行包含 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]。
#### 代码：
#include<cstdio>
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;
}

六、队伍调整：有一个人离开队伍(数组的删除x) 

【问题描述】
有 n 个人（每个人有一个唯一的编号，用 1~n 之间的整数表示）在一个水龙头前排队准备接水，现在第 x 个人有特殊情况离开了队伍，求第 x 个人离开队伍后的排队情况。
【输入格式】
第一行 1 个正整数 n，表示有 n 个人，2<n≤100。
第二行包含n个正整数，之间用一个空格隔开，表示排在队伍中的第1个到第n个人的编号。
第三行包含 1 个正整数 x，表示第 x 个人离开队伍，1≤x≤n。
【输出格式】
一行包含 n-1 个正整数，之间用一个空格隔开，表示第 x 个人离开队伍后的排队情况。
【输入样例】
7
7 2 3 4 5 6 1
3
【输出样例】
7 2 4 5 6 1
#### 代码： 
#include<cstdio>
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;
}

七、数组的二分查找(前提数据是有序的)： 

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");

八、选择排序(从小到大)： 
选择排序的基本思想是：每一趟从待排序的数据中，通过“打擂台”比较选出最小元素，放在这些数据的最前面。
这样，第一趟把 n 个数中（第 1 个到第 n 个）最小的放在第一个位置，
第二趟把剩余的 n-1 个数中（第 2 个到第 n 个）最小的放在第二个位置，
第三趟把剩余的 n-2 个数中（第 3 个到第 n 个）最小的放在第三个位，……
第 n-1 趟把剩下的 2 个数中（第 n-1 个到第 n 个）最小的放在第 n-1 个位置，
剩下的最后一个数（第 n 个）一定最大，自然落在了第 n个位置。
#### 选择排序代码：(从小到大)
#include<iostream>
using namespace std;
int main(){
    int n,i,j,k,temp,h[101];    
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 1; i <= n; i++){
         k = i;    // 定义k为最小的位置 
         for(j = i+1; j <= n; j++)
             if(h[j] < h[k]) k = j;// 在 i~n 之间的最小元素
         temp = h[i];
         h[i] = h[k];   // 把最小的放到第一个位置i ，依次第二个位置... 
         h[k] = temp;// 将 i~n 之间的最小元素放到第 i 个位置
    }
    for(i = 1; i < n; i++) cout << h[i] <<  " " ;
    cout << h[n] << endl;
    return 0;
}

九、冒泡排序(从小到大)： 
冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果“逆序”就交换。
这样，一趟排序结束后，最大的元素就放在了第 n 个位置了。
第二趟把剩余的前 n-1 个数中最大的交换到第 n-1 个位置，
第三趟把剩余的前 n-2 个数中最大的交换到第 n-2 个位置，……
经过 n-1 趟，排序结束。 
#### 冒泡排序代码：(从小到大)
#include<iostream>
using namespace std;
int main(){
    int n,i,j,temp,h[101];
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 1; i < n; i++)
         for(j = 1; j <= n-i; j++)
                if(h[j] > h[j+1]){
                           temp = h[j];
                           h[j] = h[j+1];
                           h[j+1] = temp;
                }
    for(i = 1; i < n; i++) cout << h[i] <<  " " ;
    cout << h[n] << endl;
    return 0;
}

十、对于冒泡排序，我们还可以做些算法“优化”。
如果一趟排序下来，都没有任何“逆序”数对，即没有发生“交换”操作，
则说明已经排好序了。此时，就可以立刻退出循环。
#### 优化后的冒泡排序： 
#include<iostream>
using namespace std;
int main(){
    int n,i,j,temp,h[101];
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 1; i < n; i++){
                         bool flag = true;
                        for(j = 1; j <= n-i; j++)
                                     if(h[j] > h[j+1]){
                                           temp = h[j];
                                           h[j] = h[j+1];
                                           h[j+1] = temp;
                                           flag = false;
                                     }
                         if(flag) break;
    }
    for(i = 1; i < n; i++) cout << h[i] <<  " " ;
    cout << h[n] << endl;
    return 0;
}

十一、插入排序(从小到大):
插入排序的基本思想是：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排序的。
每一趟都是把后一段的第一个数“插入”到前一段的某一个位置，保证前一段仍然是有序的。
开始时，第 1 个数作为前一段肯定是有序的；第一趟，把第 2 个数插入进去，保证前 2个数有序；
第二趟，把第 3 个数插入进去，保证前 3 个数有；……
第 n-1 趟，把第 n 个数插入进去，保证 n 个数都有序。
#### 插入排序的代码(从小到大)： 
#include<iostream>
using namespace std;
int main(){
    int n,i,j,k,temp,h[101];
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 2; i <= n; i++){
           temp = h[i];
           k = 1;
           while(h[k] <= temp && k < i) k++;
           for(j = i-1; j >= k; j--) h[j+1] = h[j];
           h[k] = temp;
    }
    for(i = 1; i < n; i++) cout << h[i] <<  " " ;
    cout << h[n] << endl;
    return 0;
}