6-1 查找最大值并返回其下标

1.题目

本题利用函数查找数组中的最大值。

函数接口定义：
int findMax(int arr[], int n);
该函数中arr用于接收数组，n为所接收的数组的长度，函数返回值为数组中最大值的下标。

2.思路

设置初始max值，之后遍历数组，遇到更大的数则不断更新最大值即可。由于要求返回的是最大值下标，可以用下标表示最大值。

3.代码

int findMax(int arr[], int n){
    int max_index=0;//初始设置最大值为第一个元素
    for(int i=1;i<n;i++){//遍历数组更新最大元素
        if(arr[max_index]<arr[i]){
            max_index=i;
        }
    }
    return max_index;
}

6-17 实验7_9_简单排序

1.题目

设计函数 void bubbleSort(int a[],int n);，实现对整型数组的排序。

输入第一行为一个整数n(0<n<=1000),代表待排序元素的个数。第二行是n个整数，每个整数都不会超过int型的存储范围，为待排序元素。

输出只有一行，为输入的n个待排序元素按从小到大排序后的结果。（建议采用起泡排序算法）

建议设计一个辅助函数:

函数功能：依次输出数组中各个元素，数与数之间用空格分开，最后一个数后没有空格而是换行符

参数说明：数组名，数组内元素个数

void outputData(int data[],int elementCount) ;

注：此题大家可以练习各种排序算法。

函数接口定义：
函数原型如下：
void bubbleSort(int a[],int n);
辅助函数原型：
void outputData(int data[],int elementCount) ;
其中 a 和 n 都是用户传入的参数。 n 是大于0且小于等于1000的整数，代表待排序元素的个数； a 是待排序数组。

辅助函数原型：
其中 data 和 elementCount 都是用户传入的参数。 elementCount 是大于0且小于等于1000的整数，代表元素的个数； data 是待输出的数组。

2.思路

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.代码

void bubbleSort(int a[],int n){
    for(int i=0;i<n;i++){
        for(int j=1;j<n-i;j++){//注意比较范围
            if(a[j-1]>a[j]){//比较相邻两个元素
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
}
void outputData(int data[],int elementCount){
    for(int i=0;i<elementCount-1;i++){
        printf("%d ",data[i]);
    }
    printf("%d\n",data[elementCount-1]);//最后一个元素
}

6-18 实验7_10_发子弹

1.题目

在某次实弹射击训练中，班长让战士们围成一圈发子弹。首先，班长给每个人发若干发子弹，然后按如下方法将每个战士手中的子弹进行调整：所有的战士检查自己手中的子弹数，如果子弹数为奇数，则向班长再要一颗。然后每个战士再同时将自己手中的子弹分一半给下一个战士（最后一个战士将手中的子弹分一半给第1个战士)。这种调整会一直进行下去，直到所有战士手中的子弹数相等为止。现请你写一个函数模拟这个调整的过程。

函数接口定义：
void distribute(int * bullets , int size , int number ) ;
其中 bullets 、 size 和 number 都是用户传入的参数。 bullets 为指向一个int 型数组的指针，该数组中依次存储着每个战士手中的子弹数，每次调整后该数组仍然依次存储着每个战士手中的子弹数 ; size 是战士的总数； number为调整的次数。函数没有返回值。

2.思路

m控制的是调整次数，因此不需要调整到子弹数相同，而是由m的值控制调整的次数。这是第一层循环。
第二层循环需要遍历数组，对于每个元素，为奇数则加一，模拟“要一颗子弹”的过程，而“同时”传递子弹则可以设计一个数组add，用来存储每个士兵交给下一个士兵的子弹数，同时更改自己的子弹数目。

当然，这种方式易于理解但是并不是最优的，实际上只定义一个add变量，初始值为最后一个士兵给第一个士兵的子弹数，之后随着遍历更改add变量即可，可以自己试验一下这种优化思路。

3.代码

void distribute(int * bullets , int size , int number ){
    int add[size];//定义子弹转移的数量
    for(int m=0;m<number;m++){
        for(int i=0;i<size;i++){
            if(bullets[i]%2!=0){//奇数子弹
                bullets[i]++;
            }
            if(i<size-1){//不是最后一个战士
                bullets[i]/=2;
                add[i+1]=bullets[i];
            }
            else{//最后一个战士
                bullets[i]/=2;
                add[0]=bullets[i];
            }
        }
        for(int i=0;i<size;i++){//同时交换子弹
            bullets[i]+=add[i];
        }
    }
}

6-19 实验7_12_插入排序

1.题目

设计函数 void InsertSort(int a[],int n); 该函数使用插入排序算法，将数组a的前n个元素按照升序的方式排序。

插入排序算法描述如下：

初始序列：49 38 65 97 76 13 27 49

将元素(38) 插入合适位置： [38 49] 65 97 76 13 27 49

将元素(65) 插入合适位置： [38 49 65] 97 76 13 27 49

将元素(97) 插入合适位置： [38 49 65 97] 76 13 27 49

将元素(76) 插入合适位置： [38 49 65 76 97] 13 27 49

将元素(13) 插入合适位置： [13 38 49 65 76 97] 27 49

将元素(27) 插入合适位置： [13 27 38 49 65 76 97] 49

将元素(49) 插入合适位置： [13 27 38 49 49 65 76 97]

输入与输出要求：
首先输入一个整数n（1<=n<=1000），代表待排序元素的个数。然后输入n个整数，每个整数不会超过int型的存储范围。

输出为n-1行，依次为1到n-1趟排序后数组内各个元素。每行输出的顺序为a[0]至a[n-1]，数与数之间用空格分开，注意第n个数后没有空格而是换行符。

函数接口定义：
函数原型如下：
void InsertSort(int a[],int n);
其中 a 和 n 都是用户传入的参数。 a 为待排序数组； n 需排序的元素的个数。函数没有返回值。

2.思路

插入排序的基本思路：前x个元素是已经排序好的数组，对于第x+1个元素，需要在前x个元素中查找它应该处于的位置，插入之后前x+1个元素是排好序的数组，直到x=n；
注意插入的时候还需要考虑后续数组的移动

3.代码

void InsertSort(int a[],int n){
    int sort_len=1;//已经排序的数组的长度,初始假设元素0是长度为1的排序数组
    for(sort_len=1;sort_len<n;sort_len++){
        int break_index=sort_len;//记录待插入位置
        for(int i=0;i<sort_len&&break_index==sort_len;i++){
            if(a[i]>a[sort_len]){//第一次出现降序，则是待插入的位置。
                break_index=i;
            }
        }
        int insert_element=a[sort_len];//对待插入元素进行备份，防止后面被覆盖
        for(int j=sort_len;j>break_index;j--){//数组后半段元素移动,从后往前覆盖
            a[j]=a[j-1];
        }
        a[break_index]=insert_element;//元素插入
        //每次需要输出当前数组元素
        for(int i=0;i<n-1;i++){
            printf("%d ",a[i]);
        }
        printf("%d\n",a[n-1]);
    }
}

6-20 实验7_11_循环移位

1.题目

设计函数void shift(int *array , int num , int size ) ;，实现将整型数组内元素循环向左移若干位置。循环向左移位含义如下：

比如，原始数组a[0],a[1]...a[9]内元素依次为：1 2 3 4 5 6 7 8 9 10，循环向左移1位后，则a[0],a[1]...a[9]内元素依次为：2 3 4 5 6 7 8 9 10 1，循环向左移2位后，则a[0],a[1]...a[9]内元素依次为：3 4 5 6 7 8 9 10 1 2。依次类推。

补充说明：本题测试用例中并没有num >= size的情况，大家也可以想一想，如果有这种情况，算法应该如何实现，与没有时是否一样。

函数接口定义：
void shift(int *array , int num , int size ) ;
其中 array 、 num和 size 都是用户传入的参数。 array 为指向原始数组的指针； num 为向左移的位数；size 为数组的大小。函数没有返回值。

2.思路

• 循环移位最简单的思路，开辟temp[num]数组，记录array前num位数组，然后将array中的元素向左移动，之后再用temp数组填补array数组因为移动而产生的空缺。
• 循环移位有一种简洁的思路——三次数组反转：以num为分界点，将数组分为两部分a和b，数组a和b分别反转，之后将数组整体再次反转。

数组反转的过程存在一定的操作重复性，可定义一个reverse函数简化代码。

• 三次反转解决移位问题是一个经典的算法思路。
• 如果num>size,可取num%size的结果作为分割数组的界限值。

3.代码

void reverse(int *array,int start,int end){
//数组反转思路：和回文字符串判断类似，首尾元素交换，向中间会合
    while(start<end){
        int temp=array[start];
        array[start]=array[end];
        array[end]=temp;
        start++;
        end--;
    }
}
void shift(int *array , int num , int size ){
    reverse(array,0,num-1);//前半段反转
    reverse(array,num,size-1);//后半段反转
    reverse(array,0,size-1);//整体反转
}

6-21 实验7_13_选择排序

1.题目

设计函数 void SelectSort(int a[],int n); 使用选择排序算法对数组a的前n个元素按照升序的方式排序。

选择排序算法描述如下：
从a[0]到a[n-1]这段元素中找最小元素a[min]，a[0]和a[min]交换；接着，从a[1]到a[n -1]这段元素中找最小元素a[min]，a[1]和a[min]交换；依次类推，直到从a[n－2]到a[n -1]这段元素中找最小元素a[min]，a[n－2]和a[min]交换。

输入：首先输入一个整数n(1<n<=1000)，代表待排序元素的个数。然后是n个整数，每个整数不会超过int型的存储范围

输出为n-1行，依次为1到n-1趟排序后数组内各个元素。每行输出的顺序为a[0]至a[n-1]，数与数之间用空格分开，注意第n个数后没有空格而是换行符。

建议设计两个辅助函数:

函数功能：找数组中的最小值元素，并返回其下标

参数说明：数组名，查找起始位置下标，查找终止位置下标

int findMin(int data[], int startLoc, int endLoc) ;

函数功能：依次输出数组中各个元素，数与数之间用空格分开，最后一个数后没有空格而是换行符

参数说明：数组名，数组内元素个数

void outputData(int data[],int elementCount) ;

函数接口定义：

//选择排序（升序） 
//参数说明：数组，数组中已有元素个数 
void selectSort(int data[],int elementCount) ;

//函数功能：找数组中的最小值元素，并返回其下标 
//参数说明：数组名，查找起始位置下标，查找终止位置下标
int findMin(int data[], int startLoc, int endLoc) ; 

//输出数组中所有元素 
//参数说明：数组，数组中已有元素个数 
void outputData(int data[],int elementCount) ;

2.思路

选择排序和插入排序类似，前x个元素已经排序，每次交换第x+1个元素和后续元素中的最小值。

3.代码

void selectSort(int data[],int elementCount){//升序
    int min_index;
    for(int sort_len=0;sort_len<elementCount-1;sort_len++){//注意下标范围，最后一次只剩下一个元素没有排序的时候，排序已经完成
        //查找最小元素下标
        min_index=findMin(data,sort_len,elementCount);
        //交换元素
        int temp=data[min_index];
        data[min_index]=data[sort_len];
        data[sort_len]=temp;
        //输出每次排序调整结果
        outputData(data,elementCount);
    }
    
}

//函数功能：找数组中的最小值元素，并返回其下标 
//参数说明：数组名，查找起始位置下标，查找终止位置下标
int findMin(int data[], int startLoc, int endLoc){//和第一题类似
    int min_index=startLoc;
    for(int i=startLoc+1;i<endLoc;i++){//遍历数组
        if(data[i]<data[min_index]){//有更小的数组
            min_index=i;//更新最小值下标
        }
    }
    return min_index;
}

void outputData(int data[],int elementCount){//数组输出，注意格式，和第二题类似
    for(int i=0;i<elementCount-1;i++){
        printf("%d ",data[i]);
    }
    printf("%d\n",data[elementCount-1]);
}

6-22 实验7_14_二分查找

1.题目

设计函数 int BinarySearch(int a[],int n,int key);

利用二分查找算法，在升序排列的数组a的前n个元素中查找值为key的数组元素的下标。如果数组a中存在整数key，则返回下标；否则返回－1。假设数组a中的元素互不相同。

输入与输出要求：

首先输入两个整数n，m，分别代表数组a中元素的个数与需要查找的整数的个数，n（0<n<=2000000）与m(0<m<=100000)。然后分别输入n个整数和m个整数，分别代表存放在数组中的数以及要查找的数。

输出m个整数，分别为要查找的数在数组a中的下标，如果数组a中不存在某个数，则输出-1。数与数之间用空格分开，注意第n个数后没有空格而是换行符。

函数接口定义：

int BinarySearch(int a[],int n,int key) ;

其中 a 、 n和 key 都是用户传入的参数。 a被查找的数组； n 是数组长度； key 是要查找的元素。如果找到，则返回该元素在数组中的下标，否则返回-1。

2.思路

二分查找首先需要数组有序，然后每次都比较中间元素a[mid]和key的大小关系：

• a[mid]==key,查找结束；
• a[mid] > key,说明key只可能存在于前半段数组中，继续查找；
• a[mid] < key,说明key只可能存在于后半段数组中，继续查找

直到查找到key（成功）或者数组大小小于等于0（失败）

3.代码

int BinarySearch(int a[],int n,int key){
    int start=0,end=n-1;//数组的首尾，之后会不断变化
    int mid;//中间下标
    int index=-1;//用来表示查找是否成功
    while(start<=end&&index==-1){//继续查找
        mid=(end+start)/2;
        if(a[mid]==key){//查找成功
            index=mid;
        }
        if(a[mid]>key){//继续查找前半段a[start,mid-1]
            end=mid-1;
        }
        if(a[mid]<key){//继续查找后半段a[mid+1,end]
            start=mid+1;
        }
    }
    return index;//失败返回-1，成功返回对应下标
}