一维数组应用（C语言）

2023-03-14 18:36 9阅读 0赞

# 一维数组应用（C语言） #

### 目录 ###

*  一维数组应用（C语言）
 *   *  1、去重处理
     *  2、字母使用频率统计
     *  3、集合的合并-----利用有序关系简化问题
     *  4、二分搜索

## 1、去重处理 ##

**问题描述：小明随机生成了n（n < 100000）个0到999之间的整数，可能有重复的整数，请你帮他按从小到大输出这些整数（忽略重复数字）**  
**例如：假设n = 8，小明随机生成的8个数是：1 5 2 4 5 6 5 2**  
**输出结果为：1 2 4 5 6**

**解题方法1：先排序，再去重**

#include<stdio.h>
    #define N 20
    
    /*函数原型*/
    void InputArr(int arry[],int n);
    void SortArr(int arry[],int n);
    void PrnArr(int arry[],int n);
    
    int main(void)
    {
        
        int a[N];
        int n;
    
        printf("Please enter the integers:\n");
        scanf("%d",&n);
    
        InputArr(a,n);      //输入
    
        SortArr(a,n);      //排序
    
        PrnArr(a,n);      //去重后输出
    
        return 0;
    }
    
    void InputArr(int arry[],int n)
    {
        
        int i;
        for(i = 0;i < n ;i++)
        scanf("%d",&arry[i]);
    }
    
    void SortArr(int arry[],int n)
    {
        
        int i,j;
        int temp;
        for(i = 0;i < n - 1;i++)
        {
        
            for(j = i + 1;j < n ;j++)
            if(arry[i] > arry[j])
            {
        
                temp = arry[i];
                arry[i] = arry[j];
                arry[j] = temp;
            }
        }
    }
    
    void PrnArr(int arry[],int n)
    {
        
        int i;
        for(i = 0;i < n;i++)
        {
        
            if(i == 0)      //如果是第一个元素则输出
            printf("%d\n",arry[i]);
    
            else      //若不是第一个元素
                if(arry[i] != arry[i - 1])      //如果当前元素与前面一个元素不相等，则输出当前元素
                printf("%d\n",arry[i]);
        }
    }

**解决方法2：用元素a\[i\] 记录其对应下标i的出现次数**  
**（1）、输入所有整数。用a\[i\]记录编号i出现的次数  
（2）、顺序输出数组a中所有非元素的下标。调用PrintIndex()实现**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70]

#include<stdio.h>
    #define N 1000
    
    int PrintIndex(int arry[]);      //输出arry对应非0的下标原型
    
    int main(void)
    {
        
        int n;
        int number;
        int arry[N] = {
        0};      //把数组arry所有元素初始化为0
    
        printf("Please enter the numbers of integers:\n");
        scanf("%d",&n);
    
        printf("Please enter the integers %d :\n",n);
    
        while(n--)
        {
        
            scanf("%d",&number);      //输入一个整数number
            arry[number]++;      //用arry[number]记录number出现的次数
        }
    
        PrintIndex(arry);      //去重并输出
    
        return 0;
    }
    
    int PrintIndex(int arry[])      //输出arry对应非0的下标
    
    {
        
        int i;
        for(i = 0;i < N ;i++)
        {
        
            if(arry[i] > 0)
            printf("%d ",i);
        }
        printf("\n");
    }

## 2、字母使用频率统计 ##

**描述：对任意输入的一行字符，统计所有英文字母在字符串中出现的频率**

#include<stdio.h>
    
    int main(void)
    {
        
         char ch;
         int a[26] = {
        0};
    
         while((ch = getchar()) != '\n')
         {
        
              if(ch >= 'A' && ch <= 'Z')      //将大写字母转换为小写字母
                   ch = ch + 32;
    
              if(ch >= 'a' && ch <= 'z')      //每出现一次+1
                   a[ch - 'a']++;
         }
    
         for(int i = 0;i < 26;i++)
              printf("count of %c is %d \n",'a' + i,a[i]);
    
         return 0;
    }

## 3、集合的合并-----利用有序关系简化问题 ##

**描述：集合A有m个整型元素，集合B有n个整型元素，请将两个整数集合A和B合并为集合C，并将集合C中的元素按升序输出**

思路分析：
    （1）、分别对A、B两个集合中的元素进行升序
    
    （2）、集合A、B、C分别用三个变量i、j、k
    
    （3）、while(i < m 并且 j < n),重复以下操作：
    若 a[i] < b[j];   c[k] = a[i];   i++;   k++;
    若 b[j] < a[i];   c[k] = b[j];   j++;   k++;
    若 a[i] == b[j];   c[k] = a[i];   i++;   j++;   k++;
    
    （4）、while(i < m),执行
    c[k++] = a[i++];
    
    （5）、while(j < n),执行
    c[k++] = b[b++];

**具体代码实现：**

#include<stdio.h>
    #define N 1000
    
    void InputArr(int arry[],int n);
    void SortArr(int arry[],int n);
    
    int main(void)
    {
        
        int i,j,k;
        int m,n;
        int a[N/2],b[N/2],c[N];
    
        printf("请输入集合A和集合B的元素个数:\n");
        scanf("%d %d",&m,&n);
    
        printf("请输入集合A的元素:\n");
        InputArr(a,m);
    
        printf("请输入集合B的元素:\n");
        InputArr(b,n);
    
        SortArr(a,m);      //对集合A进行排序
        SortArr(b,n);      //对集合B进行排序
    
        i = j = k = 0;
        while (i < m && j < n)
        {
        
            if(a[i] < b[j])
            {
        
                c[k] = a[i];
                i++;
                k++;
            }
            else if(a[i] > b[j])
            {
        
                c[k] = b[j];
                j++;
                k++;
            }
            else
            {
        
                c[k] = a[i];
                i++;
                j++;
                k++;
            }
        }
    
        while (i < m)
        {
        
            c[k] = a[i];
            i++;
            k++;
        }
    
        while (j < n)
        {
        
            c[k] = b[j];
            j++;
            k++;
        }
    
        printf("集合C的元素为:\n");
        for(i = 0;i < k;i++)
        printf("%d ",c[i]);
    
        printf("\n");
        return 0;
    }
    
    void InputArr(int arry[],int n)
    {
        
        int i;
        for(i = 0;i < n;i++)
        scanf("%d",&arry[i]);
    }
    
    void SortArr(int arry[],int n)
    {
        
        int i,j;
        int temp;
        for(i = 0;i < n -1;i++)
        {
        
            for(j = i + 1;j < n;j++)
            if(arry[i] > arry[j])
            {
        
                temp = arry[i];
                arry[i] = arry[j];
                arry[j] = temp;
            }
        }
    }

**运行结果:**  
![在这里插入图片描述][2020052116270171.png]

## 4、二分搜索 ##

**描述：在一个有序的整数序列中搜索给定值X。若找到，返回X所在的位置，否则返回查找失败，标志-1.**  
**二分搜索过程可以描述为以下递归过程：**

if(low > high)
       return -1;      //搜索区域为空
    else
    {
        
       int mid = (low + high) / 2;
       if(x = mid)      //搜索成功
       if(x < mid)      //左边搜索
       if(x > mid)      //右边搜索
    }

**二分搜索实现**

int BSearch(int a[],int x,int low,int high)
    {
        
         if(low > high)
              return -1;
         
         else
         {
        
              int mid = (low + high) / 2;
              if(x == a[mid])
                   return mid;
              
              if(x < mid)
                   return BSearch(a,x,low,mid - 1);
         
              if(x > mid)
                   return BSearch(a,x,mid + 1,high);
         }
    }

**描述：在一个有序的整数序列中搜索给定值X。若找到，返回X所在的位置，否则返回查找失败，标志Not Found!**

#include<stdio.h>
    #define N 100
    
    void InputArr(int a[],int n);      //输入原型
    void SortArr(int a[],int n);      //排序原型
    void BSearch(int a[],int x,int low,int high);      //二分查找原型
    
    int main(void)
    {
        
         int n;
         int a[N];
    
         printf("请输入元素的个数n:\n");
         scanf("%d",&n);
    
         InputArr(a,n);      //输入元素存入数组
    
         SortArr(a,n);      //将数组中的元素进行升序
    
         printf("排序后输出:\n");      //排序后进行输出测试
              int i;
         for(i = 0;i < n;i++)
              printf("%d \n",a[i]);
    
         int x;
         int low;
         int high;
    
         low = a[0];      //确定最小值
         high = a[n-1];      //确定最大值
    
         printf("最大值high,最小值low分别是 :\n");      //测试最大值与最小值
         printf("%d %d \n",a[0],a[n-1]);
    
         printf("请输入要查找的元素:\n");      //输入要查找的元素
         scanf("%d",&x);
    
         BSearch(a,x,low,high);      //二分法进行查找
    
         return 0;
    }
    
    void InputArr(int a[],int n)
    {
        
         int i;
         printf("请依次输入n个元素:\n");
         for(i = 0;i < n;i++)
              scanf("%d",&a[i]);
    }
    
    void SortArr(int a[],int n)
    {
        
         int i;
         int j;
         int temp;
    
         for(i = 0;i < n -1;i++)
         {
        
              for(j = i + 1;j < n;j++)
              {
        
                   if(a[i] > a[j])
                   {
        
                        temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                   }
              }
         }
    }
    
    void BSearch(int a[],int x,int low,int high)
    {
        
         if(low > high)
              printf("Not Found!\n");      //没有找到
    
         else
         {
        
              int mid = (low + high) / 2;
              if(x == a[mid])
                   {
        
                        printf("其下标为:%d\n",mid);      //输出下标
                        return ;
                   }
    
              else if(x < mid)
                   BSearch(a,x,low,mid - 1);
    
              else if(x > mid)
                   BSearch(a,x,mid + 1,high);
         }
    }

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70 1]  
**最后感谢各位的支持，欢迎关注公众号"编程学思",谢谢大家！**  
![在这里插入图片描述][20200521164308498.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70]: /images/20230312/1040d375e6f842a99d283678aac0320d.png
[2020052116270171.png]: /images/20230312/5f54b8eaffc942ca807040321fffc019.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70 1]: /images/20230312/89392ee180504d89bfbc29d5c90b66d3.png
[20200521164308498.png]: /images/20230312/4932134ce0454d408d34659a5caeac5a.png