第五次上机实验

女爷i 2022-01-05 11:34 187阅读 0赞

1、补足程序，附上程序代码与运行截图

// 练习：使用二分查找，在一组有序元素中查找数据项
    //  形参是数组，实参是数组名 
    #include  <stdio.h>
    const int N=5;
    int binarySearch(int x[], int n, int item);
    int main() {
        int a[N]={
        1,3,9,16,21};
        int i,index, key;
        
        printf("数组a中的数据:\n");
        for(i=0;i<N;i++)
           printf("%d ",a[i]);
        printf("\n");
        
        printf("输入待查找的数据项: ");
        scanf("%d", &key);
        
        // 调用函数binarySearch()在数组a中查找指定数据项item,并返回查找结果给index 
        // 补足代码① 
        // ××× 
        index=binarySearch(a,N,key);
        
        if(index>=0) 
            printf("%d在数组中，下标为%d\n", key, index);
        else
            printf("%d不在数组中\n", key); 
       
       return 0;
    }
    
    
    //函数功能描述：
    //使用二分查找算法在数组x中查找特定值item，数组x大小为n 
    // 如果找到，返回其下标 
    // 如果没找到，返回-1 
    int binarySearch(int x[], int n, int item) {
        int low, high, mid;
        
        low = 0;
        high = n-1;
        
        while(low <= high) {
            mid = (low+high)/2;
            
            if (item == x[mid])
                return mid;
            else if(item<x[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
        
        return -1;
    }

![1617995-20190522203920459-1703899415.png][]![1617995-20190522203748787-2081961404.png][]；

补足程序（2），附上程序代码与运行截图：

// 练习：使用二分查找，在一组有序元素中查找数据项
    //  形参是指针变量，实参是数组名
    #include  <stdio.h>
    const int N=5;
    int binarySearch(int *x, int n, int item);
    int main() {
        int a[N]={
        1,3,9,16,21};
        int i,index, key;
        
        printf("数组a中的数据:\n");
        for(i=0;i<N;i++)
           printf("%d ",a[i]);
        printf("\n");
        
        printf("输入待查找的数据项: ");
        scanf("%d", &key);
        
        // 调用函数binarySearch()在数组a中查找指定数据项item,并返回查找结果
        // 补足代码①
        // ××× 
        index=binarySearch(a,N,key);
        if(index>=0) 
            printf("%d在数组中，下标为%d\n", key, index);
        else
            printf("%d不在数组中\n", key); 
       
       return 0;
    }
    
    //函数功能描述：
    //使用二分查找算法在x指向的数据项开始的n个数据中，查找item
    // 如果找到，返回其位置
    // 如果没找到，返回-1 
    int binarySearch(int *x, int n, int item) {
        int low, high, mid;
        
        low = 0;
        high = n-1;
        
        while(low <= high) {
            mid = (low+high)/2;
            
            if (item == *(x+mid))
                return mid;
            else if(item<*(x+mid))
                high = mid - 1;
            else
                low = mid + 1;
        }
        
        return -1;
    }

![1617995-20190522204145720-1241397350.png][]![1617995-20190522204151720-1036474555.png][]。

2、选择法排序。附上程序代码与运行截图：

// 练习：使用选择法对字符串按字典序排序
    #include <stdio.h>
    #include <string.h>
    void selectSort(char str[][20], int n ); // 函数声明，形参str是二维数组名 
    int main() {
        char name[][20] = {
        "John", "Alex", "Joseph", "Candy", "Geoge"};
        int i;
        
        printf("输出初始名单:\n");
        for(i=0; i<5; i++)
            printf("%s\n", name[i]);
            
        selectSort(name, 5);  // 调用选择法对name数组中的字符串排序
        
        printf("按字典序输出名单:\n");
        for(i=0; i<5; i++)
            printf("%s\n", name[i]);
         
        return 0;
    } 
    
    // 函数定义
    // 函数功能描述：使用选择法对二维数组str中的n个字符串按字典序排序 
    void selectSort(char str[][20], int n) {
        // 补足代码
        // ×××
        int i,j=0,k,m;
        char  t[20];
        for(i=0;i<n-1;i++)                    //从第一个元素开始按顺序依次比较，共要比较四次
    {
            for(k=1;(j+k)<n;k++)            //第j行元素需要与j+1,j+2……行直到最后一行元素比较，比如第一行元素j=0，假设它最小的话，它需要与元素j=1,2,3,4比较，k便是1,2,3,4.
    {
              if(strcmp(str[j],str[j+k])>0)//如果前一行元素比后第k行大，根据要求，它不满足最小的要求
    {
                  j=j+k;                    //由上面知道，str[j+k]比str[j]小，我们选择它，str[j]不需要再往下比了，于是将j+k的值赋给j，作为新的需要被比较的元素str[j]
                  m=j;                      //用m记录目前最小元素的下标j
                  k=0;                      //由于是从j+1,j+2……这样一次去比较的，且if结束后，k++会执行，为了下一次新str[j]一次向下比较即与str[j+1],str[j+2]……比较，将0赋值给k
                 }
                 else m=j;                  //这也是记录目前最小元素的下标，目的是防止后面出现某一元素一直不符合if条件（即它最小），本层循环后，进行原数组赋值变动时，m还是上一个for循环遗留的结果，导致原数组赋值出错
              }
              strcpy(t,str[m]);             //将选出的最小元素赋值给中间变量
              strcpy(str[m],str[i]);        //将原数组的第i+1行元素赋值给第m+1行元素，这里便是交换，比如第一个找出的最小元素，他与原数组第一行元素对换，以此类推
              strcpy(str[i],t);            //将中间变量赋值给第i+1行元素，完成原数组元素互换

//至此我们对于原数组只进行了两个元素的交换，即所找到的最小元素与由上至下，例如第一个最小元素与原数组第一行元素的互换
            j=i+1;                          //由于，比如i此时等于0，即第一行元素已经是最小值，接下来只需要从第一行开始重复上述步骤，找出第二个最小值，故j=i+1，即从str[1]开始向下比较
      }
    }

![1617995-20190522204336672-218023852.png][]。

实验总结与体会：

①实验内容1中，对于数组名与指针变量，在实参写法上，两者保持一致；在形参写法上，前者为a\[ \]，对数组的初始化，后者为\*x，指向数组的第一个元素；函数实现中，前者元素采用a\[i\]形式，后者采用\*（x+i）形式。我个人觉得两者好像没什么区别，因为间接访问\*（x+i）就等效于a\[i\]，两者都表示数组的第（i+1）个元素。

在实验内容1中，需要注意（1）数组的调用形式；（2）需要有接受子函数返回值的变量；

②实验内容2中，我一开始时纠结于如何“选择最值”，看了pdf中的网页链接的动图与代码演示后才依葫芦画瓢写了出来。需要注意（1）明确每一步目的是什么（2）如何选出与存放最值（3）二维数组中每行首元素的表示方式（4）数组元素中的比较函数strcmp与赋值函数strcpy的**具体**含义。

③实验内容三中，我个人觉得需要注意的（1）while(       )什么时候运行，什么时候不运行；（2）数组作为实参的写法（3）对于下标i的控制

第三道练习的条件表达式while(p<=head)，我觉得功能是s\[head\]是第一个不为\*的元素，故这一项元素以及前面所有元素都要保留。

最后的s\[i\]='\\0'我觉得可能是因为原数组是由每一项都是' '元素构成的，所以最后需要一个字符终止符。

附上评论地址：

https://www.cnblogs.com/MR-XN/p/10932596.html；

https://www.cnblogs.com/rosalyn/p/10928406.html；

https://www.cnblogs.com/plutocharon/p/10934443.html。

转载于:https://www.cnblogs.com/yuan82/p/10908930.html

[1617995-20190522203920459-1703899415.png]: https://img2018.cnblogs.com/blog/1617995/201905/1617995-20190522203920459-1703899415.png
[1617995-20190522203748787-2081961404.png]: /images/20211229/7b7f6d6b504c4906b2685cdd503f8e44.png
[1617995-20190522204145720-1241397350.png]: https://img2018.cnblogs.com/blog/1617995/201905/1617995-20190522204145720-1241397350.png
[1617995-20190522204151720-1036474555.png]: /images/20211229/ee574e1b68674ec1a9b9ae21c72ae049.png
[1617995-20190522204336672-218023852.png]: /images/20211229/bbb71d3625f04747ae0017551edda57c.png