C语言实现数据结构：查找与排序_使用数据结构查找与排序知识设计并实现一个升级版的图书信息管理系统。要求定义一

第四次上机实验报告

1.作业题目：

设计并实现一个管理系统（学生管理、图书管理、产品管理等等），系统中需包含1000条以上的记录，系统至少包含以下功能：

(1) 自动生成记录信息（或者从文件中读取）；

(2) 逐条显示所有记录信息；

(3) 利用时间复杂度O(n2)的排序算法（例如直接插入排序或者折半插入排序）按照关键字进行排序；

(4) 利用时间复杂度O(nlogn)的排序算法（例如快速排序）按照关键字进行排序；

(5) 程序中统计（3）和（4）的算法在数据正序、逆序、乱序情况下的比较次数与移动次数并输出，在报告中对比较次数与移动次数进行分析。

程序运行结果截图，需测试各种情况。写出测试过程中遇到的主要问题及所采用的解决措施。

2. 运行结果截图:

 

3.排序移动次数和比较次数分析

Ⅰ.直接插入排序

①.乱序：

移动次数：1517940

比较次数：751710

②.逆序

移动次数：1498500

比较次数：499500

③.正序

移动次数：0

比较次数：0

Ⅱ.冒泡排序

①.乱序：

移动次数：758970

比较次数：498720

②.逆序

移动次数：1498500

比较次数：499500

③.正序

移动次数：0

比较次数：999

Ⅲ.快速排序

①.乱序：

移动次数：4862

比较次数：10487

②.逆序

移动次数：1998

比较次数：49500

③.正序

移动次数：1998

比较次数：49500

4.得出的结论：

直接插入排序：

正序移动次数为0，比较次数为0；

逆序移动次数为3*0.5*n*(n-1)，比较次数为0.5*n*(n-1);

乱序介于它们之间。

冒泡排序：

正序移动次数为0，比较次数为n-1；

逆序移动次数为3*0.5*n*(n-1)，比较次数为0.5*n*(n-1);

乱序介于它们之间。

快速排序：

正序移动次数为2*(n-1)，比较次数为0.5*n*(n-1)；

逆序移动次数为2*(n-1)，比较次数为0.5*n*(n-1);

乱序均比它们大。

5.附录

列出程序文件清单，及文件功能。

头文件：

sort.h:存放宏定义、全局变量定义和函数声明

源文件：

main.cpp:存放主函数

sort.cpp:存放其他分函数

代码注释要求：

1. 对关键的算法实现代码有必要的注释
2. 函数说明格式：

*****************************************************

函数名：

函数功能：

输入参数：

       类型，参数名，含义

输出参数：

文件提交要求：

将两道题目各自的完整工程（包含该工程下所有目录和文件）和此文档一起打包，以组内学生姓名作为文件名，上传提交。例如Stu1_Stu2.zip

代码:

sort.h

#pragma once
#define ARRAY_LEN 1000        //    数组长度
#define MIN 1                 //    数组的最小值
#define MAX 1000              //    数组的最大值
 
int Comparisons_num;          //    比较次数
int Mobile_num;               //    移动次数
 
void Create_data(double* a, int n, int min, int max);                            //    建立伪随机分数
void Copy_array(double* tar, double* arr, int len);                              //    复制数组
void Swap_element(double* a, double* b);                                         //    交换元素
 
void Insert_sort(double* arr, int len);                                          //    直接插入排序 
void Bubble_sort(double* arr, int len);                                          //    冒泡排序
int Division(double* a, int left, int right);                                    //    分隔过程（快速排序）
void Quick_sort(double* arr, int left, int right, int count);                    //    快速排序（left和count初始值为0，right初始值为数组长度 - 1）    
 
void Print_sort_negative(double* arr, int len);                                  //    逆序输出
void Print_sort_positive(double* arr, int len);                                  //    输出
void Print_mob_com();                                                            //    显示移动次数和比较次数

sort.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <conio.h>
#include <string.h>
 
extern int Comparisons_num;       //    比较次数
extern int Mobile_num;            //    移动次数
 
//　　建立伪随机数组
void Create_data(double* a, int n, int min, int max)
{
    int flag;                    //　　避免取重复取值
    srand(time(NULL));
 
    if (n > max - min + 1)
        ;
    for (int i = 0, j = 0; i < n; i++)
    {
        do
        {
            a[i] = (max - min + 1) * rand() / (RAND_MAX + 1) + 1;
            flag = 0;
            for (j = 0; j < i; j++)
            {
                if (a[i] == a[j])
                    flag = 1;
            }
        } while (flag);
    }
}
 
//　　复制数组
void Copy_array(double* tar, double* arr, int len)
{
    int i;
 
    for (i = 0; i < len; i++)
        tar[i] = arr[i];
}
 
//　　交换元素
void Swap_element(double* a, double* b)
{
    double tmp = *a;
 
    *a = *b;
    *b = tmp;
 
    Mobile_num += 3;    //　　一次关键字交换计为3次移动
}
 
 
//    直接插入排序
void Insert_sort(double* arr, int len)
{
    int i, j;
    int tmp;            //    待排序的元素
 
    for (i = 0; i < len; i++)
    {
        tmp = arr[i];
        for (j = i - 1; j >= 0 && tmp < arr[j]; j--)
        {
            Swap_element(arr + j, arr + j + 1);
            Comparisons_num++;
        }
        arr[j + 1] = tmp;
    }
}
 
 
//    冒泡排序
void Bubble_sort(double* arr, int len)
{
    int i, j;
    int flag = 1;            //    标记循环过程是否进行过交换，如果为1则进行了交换    
 
    for (i = 0; i < len && flag; i++)
    {
        flag = 0;
        for (j = 1; j < len - i; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                Swap_element(arr + j, arr + j - 1);
                flag = 1;
            }
            Comparisons_num++;
        }
    }
}
 
 
//　　分隔（快速排序）
int Division(double* a, int left, int right)
{
    double base = a[left];
    while (left < right)
    {
        while (left < right && base < a[right])
        {
            right--;
            Comparisons_num++;
        }
 
        a[left] = a[right];
        Mobile_num++;
 
        while (left < right && a[left] < base)
        {
            left++;
            Comparisons_num++;
        }
 
        a[right] = a[left];
        Mobile_num++;
    }
 
    a[left] = base;
    return left;
}
 
//　　快速排序    
//　　left 和 count初始值为0  right 初始值为数组长度 - 1
void Quick_sort(double* arr, int left, int right, int count)
{
    int i;
    int count_temp = count + 1;
 
    if (left < right)
    {
        i = Division(arr, left, right);
        Quick_sort(arr, left, i - 1, count_temp);
        Quick_sort(arr, i + 1, right, count_temp);
    }
}
 
 
//    输出
void Print_sort_positive(double* arr, int len)
{
    int i;
 
    for (i = 0; i < len; i++)
    {
        printf("%5.1f ", arr[i]/10);
    }
    putchar('\n');
}
 
//    逆序输出
void Print_sort_negative(double* arr, int len)
{
    int i;
 
    for (i = 0; i < len; i++)
    {
        printf("%5.1f ", arr[len - i - 1]/10);
    }
    putchar('\n');
}
 
//    显示移动次数和比较次数
void Print_mob_com()
{
    printf("移动次数：%d\n", Mobile_num);
    printf("比较次数：%d\n\n", Comparisons_num);
    //    初始化
    Mobile_num = Comparisons_num = 0;
}

main.cpp

#include "Sort.h"
#include <stdio.h>
 
int main(void)
{
    double arr[ARRAY_LEN];
    double rightarr[ARRAY_LEN];
    double leftarr[ARRAY_LEN];
    double target_arr[ARRAY_LEN];
    double target_rightarr[ARRAY_LEN];
    double target_leftarr[ARRAY_LEN];
 
    Create_data(arr, ARRAY_LEN, MIN, MAX);
 
    Copy_array(target_arr, arr, ARRAY_LEN);
    Bubble_sort(target_arr, ARRAY_LEN);
    Copy_array(rightarr, target_arr, ARRAY_LEN);
    for (int i = 0; i < ARRAY_LEN; i++) {
        leftarr[i] = rightarr[ARRAY_LEN-i-1];
    }
 
    printf("以下为随机生成的1000个学生的分数数据: \n（分数从0.1到100.0分各不相同)\n");
    Print_sort_positive(arr, ARRAY_LEN);
 
    printf("\n*****************************************************************************\n");
 
    printf("\n直接插入排序: \n");
 
    printf("\n乱序: \n");
    Copy_array(target_arr, arr, ARRAY_LEN);
    Print_sort_positive(target_arr, ARRAY_LEN);
    Insert_sort(target_arr, ARRAY_LEN);
    printf("直接插入排序:\n");
    Print_mob_com();
 
    printf("\n逆序: \n");
    Copy_array(target_leftarr, leftarr, ARRAY_LEN);
    Print_sort_positive(target_leftarr, ARRAY_LEN);
    Insert_sort(target_leftarr, ARRAY_LEN);
    printf("直接插入排序:\n");
    Print_mob_com();
 
    printf("\n正序: \n");
    Copy_array(target_rightarr, rightarr, ARRAY_LEN);
    Print_sort_positive(target_rightarr, ARRAY_LEN);
    Insert_sort(target_rightarr, ARRAY_LEN);
    printf("直接插入排序:\n");
    Print_mob_com();
 
 
 
    printf("\n*****************************************************************************\n");
 
    printf("\n冒泡排序: \n");
 
    printf("\n乱序: \n");
    Copy_array(target_arr, arr, ARRAY_LEN);
    Print_sort_positive(target_arr, ARRAY_LEN);
    Bubble_sort(target_arr, ARRAY_LEN);
    printf("冒泡排序:\n");
    Print_mob_com();
 
    printf("\n逆序: \n");
    Copy_array(target_leftarr, leftarr, ARRAY_LEN);
    Print_sort_positive(target_leftarr, ARRAY_LEN);
    Bubble_sort(target_leftarr, ARRAY_LEN);
    printf("冒泡排序:\n");
    Print_mob_com();
 
    printf("\n正序: \n");
    Copy_array(target_rightarr, rightarr, ARRAY_LEN);
    Print_sort_positive(target_rightarr, ARRAY_LEN);
    Bubble_sort(target_rightarr, ARRAY_LEN);
    printf("冒泡排序:\n");
    Print_mob_com();
 
 
 
 
    printf("\n*****************************************************************************\n");
 
 
 
    printf("\n快速排序: \n");
 
    printf("\n乱序: \n");
    Copy_array(target_arr, arr, ARRAY_LEN);
    Print_sort_positive(target_arr, ARRAY_LEN);
    Quick_sort(target_arr, 0, ARRAY_LEN - 1, 0);
    printf("快速排序:\n");
    Print_mob_com();
 
    printf("\n逆序: \n");
    Copy_array(target_leftarr, leftarr, ARRAY_LEN);
    Print_sort_positive(target_leftarr, ARRAY_LEN);
    Quick_sort(target_leftarr, 0, ARRAY_LEN - 1, 0);
    printf("快速排序:\n");
    Print_mob_com();
 
    printf("\n正序: \n");
    Copy_array(target_rightarr, rightarr, ARRAY_LEN);
    Print_sort_positive(target_rightarr, ARRAY_LEN);
    Quick_sort(target_rightarr, 0, ARRAY_LEN - 1, 0);
    printf("快速排序:\n");
    Print_mob_com();
 
    return 0;
}

查找算法与排序算法总结：