宝安商城网站建设哪家便宜,汕头澄海网站建设,ps软件下载手机版,网站建设的想法和意见目录
前言
已完成内容
归并排序实现
01-开发环境
02-文件布局
03-代码
01-主函数
02-头文件
03-PSeqListFunction.cpp
04-SortFunction.cpp
结语 前言 此专栏包含408考研数据结构全部内容#xff0c;除其中使用到C引用外#xff0c;全为C语言代码。使用C引用主要是…目录
前言
已完成内容
归并排序实现
01-开发环境
02-文件布局
03-代码
01-主函数
02-头文件
03-PSeqListFunction.cpp
04-SortFunction.cpp
结语 前言 此专栏包含408考研数据结构全部内容除其中使用到C引用外全为C语言代码。使用C引用主要是为了简化指针的使用避免二重指针的出现。
已完成内容
[数据结构]01-顺序表C语言实现_Chandni.的博客-CSDN博客
[数据结构]02-单链表C语言实现_Chandni.的博客-CSDN博客
[数据结构]03-栈C语言实现_Chandni.的博客-CSDN博客
[数据结构]04-循环队列数组C语言实现_Chandni.的博客-CSDN博客
[数据结构]05-循环队列链表C语言实现_Chandni.的博客-CSDN博客
[数据结构]06-队列链表带头结点C语言实现_Chandni.的博客-CSDN博客
[数据结构]07-二叉树无头结点C语言实现_Chandni.的博客-CSDN博客
[数据结构]08-顺序查找顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
[数据结构]09-二分查找顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
[数据结构]10-二叉排序树无头结点C语言实现_Chandni.的博客-CSDN博客
[数据结构]11-冒泡排序顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客 [数据结构]12-快速排序顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
[数据结构]13-插入排序顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
[数据结构]14-选择排序顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
[数据结构]15-堆排序顺序表指针实现形式C语言实现_Chandni.的博客-CSDN博客
归并排序实现
01-开发环境 语言C/C14 编译器MinGW64 集成开发环境CLion2022.1.3
02-文件布局 请在CLion集成开发环境中创建C可执行程序否则无法运行原因上面已解释。
03-代码
01-主函数 用于测试归并排序。
// 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
#include ./Head/PSeqSearchData.h
#include ./Source/PSeqListFunction.cpp
#include ./Source/SortCommon.cpp
#include ./Source/SortFunction.cppint main() {// 顺序表初始化PSeqList PSL;PSeqListCreate(PSL, MaxSize);PSeqListPrint(PSL);// 调试内容
// int Array[] {2, 3, 1, 5, 1, 10};memcpy(PSL.data, Array, sizeof(Array));
// PSL.data Array;
// PSL.ListLength 6;// 归并排序// end--表示数组中最后一个元素位置(Length - 1)MergeSort(PSL.data, 0, PSL.ListLength - 1);PSeqListPrint(PSL);return 0;
}02-头文件 用于存储结构体和常量等。
//
// Created by 24955 on 2023-03-02.
// 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)-数组实现形式不可以动态控制顺序表大小
//#ifndef INC_01_SEQUENCESEARCH_PSEQSEARCHDATA_H
#define INC_01_SEQUENCESEARCH_PSEQSEARCHDATA_H
// 头文件
#include stdio.h
#include stdlib.h
#include string.h
#include time.h// 常量
#define MaxSize 10
typedef int ElemType;// 结构体
// 顺序表结构体(以指针形式实现)
typedef struct {ElemType *data;int ListLength;
}PSeqList;
#endif //INC_01_SEQUENCESEARCH_PSEQSEARCHDATA_H03-PSeqListFunction.cpp 用于存储顺序表初始化和打印输出等函数。
//
// Created by 24955 on 2023-03-02.
// 顺序表以指针形式实现(申请堆空间可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
// 不使用哨兵
//
// 顺序表初始化
void PSeqListCreate(PSeqList PSList, int Length) {/** 1. 为顺序表申请堆空间* 2. 根据Length大小设置顺序表长度* 3. 随机数初始化顺序表*/PSList.ListLength Length;PSList.data (ElemType *) malloc((PSList.ListLength) * sizeof(ElemType));srand(time(NULL));for (int i 0; i PSList.ListLength; i) {PSList.data[i] rand() % 100;}
}// 顺序表打印输出
void PSeqListPrint(PSeqList PSList) {/** 1. 0号元素为哨兵因此从1号元素开始打印输出*/for (int i 0; i PSList.ListLength; i) {printf(%3d, PSList.data[i]);}printf(\n);
}
04-SortFunction.cpp 用于存储归并排序函数。
//
// Created by 24955 on 2023-03-06.
// 归并排序时间复杂度O(n*log2n)空间复杂度O(n)
//
void SortTwoOrderedArrays(ElemType *Data, int start, int mid, int end) {/** 1. 具体思想看下方注释*/// 申请缓存数据空间(最大使用空间为MaxSize最小使用空间为2)// 采用static避免重复初始化空间复杂度为O(n)static int TemporaryData[MaxSize];/** 1. i表示左有序数组开始下标mid表示左有序数组结束下标* 2. j表示右有序数组开始下标end表示右有序数组结束下标* 3. pos表示临时数组下标从0开始* 4. 结束条件为左、右数组元素均为空*/for (int i start, j mid 1, pos 0; i mid || j end; pos) {// 若左有序数组为空将右有序数组所剩元素依次加到临时数组后面if (i mid) {TemporaryData[pos] Data[j];} else if (j end) {// 若右有序数组为空将左有序数组所剩元素依次加到临时数组后面TemporaryData[pos] Data[i];} else {// 若两者都不为空比较当前第一个元素大小谁小将其加入临时数组并后移一位if (Data[i] Data[j]) {// 此处是左数组加入并后移一位TemporaryData[pos] Data[i];} else {// 此处是右数组加入并后移一位TemporaryData[pos] Data[j];}}}// 将临时数组中排好序的元素依次写入Data中for (int i start, pos 0; i end; i, pos) {Data[i] TemporaryData[pos];}
}// 归并排序
void MergeSort(ElemType *Data, int start, int end) {/** 1. 首先不断进行二分直到只剩一个元素为止* 2. 随后对两有序数组进行排序* 3. 依次递归下去便可得有序数组*/// 计算二分中间所在位置int mid (start end) / 2;// 递归结束条件为数组中只有一个元素(自身有序)if (end start) {return;} else {// 向前、后各递归排序(一分为二)MergeSort(Data, start, mid);MergeSort(Data, mid 1, end);// 对两有序数组进行排序SortTwoOrderedArrays(Data, start, mid, end);}
}
结语 此博客主要用于408考研数据结构C语言实现记录内有不足可留言可讨论。
