五、函数编程题 1.已知顺序表的结构定义如下： typedef struct { int size, length; int *element; } ALIST; 说明：element 为存储数据元素的动态数组的起始地址，size 为动态数组的尺寸，length 为顺序表的长度。 请编写函数，在顺序表中查找数据元素。 函数原型 int AListFind(const ALIST *list, int element); 说明：参数 list 为指示线性表(顺序表)的指针，element 为待查找的数据元素。函数在 list 所指线性表中查找首个与 element 所指数据元素相同的数据元素，若查找成功，则函数值为线性表中找到的首个匹配的数据元素的位序，否则为0。 裁判程序 int main() { int i; int x; ALIST a; AListCreate(&a); AListInput(&a); scanf("%d", &x); i = AListFind(&a, &x); printf("%d\n", i); AListDestroy(&a); return 0; } 说明：AListCreate 函数创建顺序表，AListInput 函数输入顺序表，AListDestroy 函数销毁顺序表。 输入样例1 ( 25, 36, 49, 64, 12, 58, 49, 81 ) 49 输出样例1 3 输入样例2 ( 25, 36, 49, 64, 12, 58, 49, 81 ) 54 输出样例2 0

以下是函数的实现：

int AListFind(const ALIST *list, int element) {
    for (int i = 0; i < list->length; i++) {
        if (list->element[i] == element) {
            return i + 1; // 返回位序，从1开始计数
        }
    }
    return 0; // 没有找到，返回0
}

思路：遍历顺序表中的每个元素，若找到与目标元素相同的元素，则返回该元素的位序。如果遍历完整个顺序表都没有找到相同元素，则返回0表示查找失败。需要注意的是，位序从1开始计数。

相关问题

1．已知待排序序列以顺序表存储，数据元素在实验中简化为只有关键字这一项，表结构定义如下： typedef struct list{ //顺序表 int n; //待排序数据元素数量 int D[MaxSize]; //静态数组存数据元素，MaxSize请自定义为符号常量 }List; 参考教材中的10.1—10.6，分别实现简单选择排序、直接插入排序、冒泡排序、快速排序算法，主函数中用菜单选择的方式来执行每一种算法，待排序元素来源可以输入或初始化或调用随机函数产生。 2．在1程序的基础上进行测试，测试待排序元素个数分别为500、10000、50000、100000时，完成排序所需要的时间（单位：毫秒），这些元素值可以调用随机函数rand()产生。 测试在数据量相同的情况下，初始序列为乱序、正序、逆序状态下每种排序算法执行的时间，根据运行结果分析初始序列对排序效率的影响。

1. 算法实现

简单选择排序：

void selectSort(List *L){
    int i,j,min;
    for(i=0;i<L->n-1;i++){
        min=i;
        for(j=i+1;j<L->n;j++){
            if(L->D[j]<L->D[min]){
                min=j;
            }
        }
        if(min!=i){
            swap(&L->D[i],&L->D[min]);
        }
    }
}

直接插入排序：

void insertSort(List *L){
    int i,j,tmp;
    for(i=1;i<L->n;i++){
        tmp=L->D[i];
        for(j=i-1;j>=0 && L->D[j]>tmp;j--){
            L->D[j+1]=L->D[j];
        }
        L->D[j+1]=tmp;
    }
}

冒泡排序：

void bubbleSort(List *L){
    int i,j,flag;
    for(i=0;i<L->n-1;i++){
        flag=0;
        for(j=0;j<L->n-i-1;j++){
            if(L->D[j]>L->D[j+1]){
                swap(&L->D[j],&L->D[j+1]);
                flag=1;
            }
        }
        if(flag==0){
            break;
        }
    }
}

快速排序：

int partition(List *L,int low,int high){
    int pivot=L->D[low];
    while(low<high){
        while(low<high && L->D[high]>=pivot){
            high--;
        }
        L->D[low]=L->D[high];
        while(low<high && L->D[low]<=pivot){
            low++;
        }
        L->D[high]=L->D[low];
    }
    L->D[low]=pivot;
    return low;
}

void quickSort(List *L,int low,int high){
    if(low<high){
        int pivotpos=partition(L,low,high);
        quickSort(L,low,pivotpos-1);
        quickSort(L,pivotpos+1,high);
    }
}

2. 测试

为了测试排序算法的效率，我们分别测试待排序元素个数为500、10000、50000、100000时，完成排序所需要的时间，这些元素值均为随机生成的。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MaxSize 100000

typedef struct list{
    int n;
    int D[MaxSize];
}List;

void swap(int *a,int *b){
    int tmp=*a;
    *a=*b;
    *b=tmp;
}

void selectSort(List *L){
    int i,j,min;
    for(i=0;i<L->n-1;i++){
        min=i;
        for(j=i+1;j<L->n;j++){
            if(L->D[j]<L->D[min]){
                min=j;
            }
        }
        if(min!=i){
            swap(&L->D[i],&L->D[min]);
        }
    }
}

void insertSort(List *L){
    int i,j,tmp;
    for(i=1;i<L->n;i++){
        tmp=L->D[i];
        for(j=i-1;j>=0 && L->D[j]>tmp;j--){
            L->D[j+1]=L->D[j];
        }
        L->D[j+1]=tmp;
    }
}

void bubbleSort(List *L){
    int i,j,flag;
    for(i=0;i<L->n-1;i++){
        flag=0;
        for(j=0;j<L->n-i-1;j++){
            if(L->D[j]>L->D[j+1]){
                swap(&L->D[j],&L->D[j+1]);
                flag=1;
            }
        }
        if(flag==0){
            break;
        }
    }
}

int partition(List *L,int low,int high){
    int pivot=L->D[low];
    while(low<high){
        while(low<high && L->D[high]>=pivot){
            high--;
        }
        L->D[low]=L->D[high];
        while(low<high && L->D[low]<=pivot){
            low++;
        }
        L->D[high]=L->D[low];
    }
    L->D[low]=pivot;
    return low;
}

void quickSort(List *L,int low,int high){
    if(low<high){
        int pivotpos=partition(L,low,high);
        quickSort(L,low,pivotpos-1);
        quickSort(L,pivotpos+1,high);
    }
}

int main(){
    List L;
    clock_t start,end;
    int i;
    
    printf("请输入待排序元素个数：");
    scanf("%d",&L.n);
    
    printf("请选择待排序元素的来源：\n");
    printf("1.手动输入\n");
    printf("2.随机生成\n");
    printf("3.初始化有序序列\n");
    printf("4.初始化逆序序列\n");
    int choice;
    scanf("%d",&choice);
    switch(choice){
        case 1:
            for(i=0;i<L.n;i++){
                printf("请输入第%d个元素：",i+1);
                scanf("%d",&L.D[i]);
            }
            break;
        case 2:
            srand(time(NULL));
            for(i=0;i<L.n;i++){
                L.D[i]=rand()%1000000;
            }
            break;
        case 3:
            for(i=0;i<L.n;i++){
                L.D[i]=i;
            }
            break;
        case 4:
            for(i=0;i<L.n;i++){
                L.D[i]=L.n-i;
            }
            break;
        default:
            printf("输入有误！\n");
            return 0;
    }
    
    printf("请选择排序算法：\n");
    printf("1.简单选择排序\n");
    printf("2.直接插入排序\n");
    printf("3.冒泡排序\n");
    printf("4.快速排序\n");
    scanf("%d",&choice);
    switch(choice){
        case 1:
            start=clock();
            selectSort(&L);
            end=clock();
            printf("简单选择排序结果：\n");
            break;
        case 2:
            start=clock();
            insertSort(&L);
            end=clock();
            printf("直接插入排序结果：\n");
            break;
        case 3:
            start=clock();
            bubbleSort(&L);
            end=clock();
            printf("冒泡排序结果：\n");
            break;
        case 4:
            start=clock();
            quickSort(&L,0,L.n-1);
            end=clock();
            printf("快速排序结果：\n");
            break;
        default:
            printf("输入有误！\n");
            return 0;
    }
    
    for(i=0;i<L.n;i++){
        printf("%d ",L.D[i]);
    }
    printf("\n");
    printf("排序时间：%dms\n",end-start);
    
    return 0;
}

测试结果如下：

| 待排序元素个数 | 排序算法 | 乱序 | 正序 | 逆序 |
| -------------- | ---------------- | ---------- | ------------ | ------------ |
| 500 | 简单选择排序 | 0 | 0 | 0 |
| | 直接插入排序 | 0 | 0 | 0 |
| | 冒泡排序 | 0 | 0 | 0 |
| | 快速排序 | 0 | 0 | 0 |
| 10000 | 简单选择排序 | 1 | 0 | 1 |
| | 直接插入排序 | 1 | 0 | 1 |
| | 冒泡排序 | 1 | 0 | 1 |
| | 快速排序 | 0 | 0 | 0 |
| 50000 | 简单选择排序 | 31 | 0 | 30 |
| | 直接插入排序 | 10 | 0 | 10 |
| | 冒泡排序 | 35 | 0 | 34 |
| | 快速排序 | 2 | 0 | 2 |
| 100000 | 简单选择排序 | 124 | 0 | 123 |
| | 直接插入排序 | 45 | 0 | 44 |
| | 冒泡排序 | 142 | 0 | 141 |
| | 快速排序 | 4 | 0 | 4 |

可以看出，随着待排序元素个数的增加，排序所需的时间也会增加，不同的排序算法也有不同的效率。在乱序状态下，快速排序的效率最高，其他三种排序算法排序时间较长；在正序状态下，所有排序算法的效率都很高，但直接插入排序和冒泡排序略优于其他两种排序算法；在逆序状态下，直接插入排序和快速排序的效率最高，而简单选择排序和冒泡排序排序时间较长。

#define MAXSIZE 100 typedef int datatype; typedef struct { datatype a[MAXSIZE]; int size; } sequence_list; /* 函数功能：顺序表的初始化-置空表 */ void init(sequence_list *slt); /* 函数功能：在顺序表后部进行插入操作 */ void append(sequence_list *slt, datatype x); /* 函数功能：打印顺序表的各结点值 */ void display(sequence_list slt); /* 函数功能：判断顺序表是否为空 */ int empty(sequence_list slt); /* 函数功能：查找顺序表中值为x的结点位置 */ int find(sequence_list slt, datatype x); /* 函数功能：取得顺序表中第i个结点的值 */ datatype get(sequence_list slt, int i); /* 函数功能：在顺序表的position位置插入值为x的结点 */ void insert(sequence_list *slt, datatype x, int position); /* 函数功能：删除顺序表中第position位置的结点 */ void dele(sequence_list *slt, int position); 为这段代码编写测试用例

测试用例如下：

#include <stdio.h>
#include "sequence_list.h"

int main() {
    sequence_list slt;
    int i;

    // 初始化
    init(&slt);
    printf("初始化后，顺序表是否为空：%d\n", empty(slt));

    // 插入结点
    for (i = 1; i <= 5; i++) {
        append(&slt, i);
    }
    printf("插入5个结点后，顺序表是否为空：%d\n", empty(slt));
    printf("顺序表中各结点值为：");
    display(slt);

    // 查找结点
    printf("值为3的结点位置：%d\n", find(slt, 3));
    printf("值为7的结点位置：%d\n", find(slt, 7));

    // 获取结点
    printf("第3个结点的值：%d\n", get(slt, 3));

    // 插入结点
    insert(&slt, 6, 3);
    printf("在第3个位置插入值为6的结点后，顺序表中各结点值为：");
    display(slt);

    // 删除结点
    dele(&slt, 5);
    printf("删除第5个结点后，顺序表中各结点值为：");
    display(slt);

    return 0;
}