西安电脑网站建设,有哪些好的网站,网站项目怎么做,自己网站做问卷调查目录
前言
已完成内容
快速排序实现
01-开发环境
02-文件布局
03-代码
01-主函数
02-头文件
03-PSeqListFunction.cpp
04-SortCommon.cpp
05-SortFunction.cpp
结语 前言 此专栏包含408考研数据结构全部内容#xff0c;除其中使用到C引用外#xff0c;全为C语言代…目录
前言
已完成内容
快速排序实现
01-开发环境
02-文件布局
03-代码
01-主函数
02-头文件
03-PSeqListFunction.cpp
04-SortCommon.cpp
05-SortFunction.cpp
结语 前言 此专栏包含408考研数据结构全部内容除其中使用到C引用外全为C语言代码。使用C引用主要是为了简化指针的使用避免二重指针的出现。 快速排序本文主要采用了两种编写思想1交换思想 2覆盖思想(挖坑法)。其中交换思想中又包含两种1直接对数组指针进行操作移动指针所在位置实现分治。2对数组下表进行操作、记录实现分治。 两种思想各有特色读者可根据自身情况选择相对而言挖坑法更易理解。 交换思想两种操作方式宜各有特色个人觉得指针方式更易理解。最初书写代码时便是采用了交换思想--指针操作方式。每个人情况不同可根据自身情况选择。
已完成内容
[数据结构]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博客
快速排序实现
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, 10);PSeqListPrint(PSL);// 调试内容
// int Array[] {2, 3, 1, 5, 1, 10};memcpy(PSL.data, Array, sizeof(Array));
// PSL.data Array;
// PSL.ListLength 6;// 快速排序--数组指针操作
// QuickSortPointer(PSL.data, PSL.ListLength);
// PSeqListPrint(PSL);// 快速排序--数组操作// 初始化头标签和尾标签
// int start 1, end PSL.ListLength - 1;
// QuickSort(PSL.data, start, end);
// PSeqListPrint(PSL);// 快速排序--挖坑法QuickSortHole(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// 常量
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-SortCommon.cpp 用于存储排序公用函数--交换函数、分割函数。
//
// Created by 24955 on 2023-03-06.
//
// 交换两值元素
void Swap(ElemType ElemOne, ElemType ElemTwo) {/** 1. 交换两元素值*/ElemType TemporaryData;TemporaryData ElemOne;ElemOne ElemTwo;ElemTwo TemporaryData;
}// 分割函数--交换
int Partition(ElemType *Data, int start, int end) {/** 1. PartitionIndex标记分割元素所在位置* 2. PartitionData标记分割元素值* 3. 主要思想为交换*/// 开始标签指向分割元素前一个位置因此需要-1// 可根据自身情况修改(为满足两函数都可调用做了一定折中处理)// QuickSortPointer函数中可根据自身理解设置start值ElemType PartitionIndex start - 1;ElemType PartitionData Data[PartitionIndex];// 当end start时完成一次分割(大于分隔值的在右边小于分隔值的在左边)while (start end) {// 设当前数组第0个元素为分割元素/* 1. 头标签代表元素值大于等于分隔值时* 2. 判断尾标签代表元素与分隔值大小关系*/if (Data[start] PartitionData) {if (Data[end] PartitionData) {// 尾标签代表元素值大于等于分隔值时移动尾标签-1end--;} else {// 尾标签代表元素值小于分隔值时交换并将头标签1尾标签-1Swap(Data[start], Data[end--]);}} else {// 头标签代表元素值小于分隔值时移动头标签1start;}}// 将分割元素与尾标签所指元素交换即可将分割元素位于中间位置(排好分割元素)Swap(Data[end], Data[PartitionIndex]);// 返回交换后分割元素所在位置return end;
}// 分割函数--挖坑法(覆盖)
int PartitionHole(ElemType *Data, int start, int end) {/** 1. 挖坑法主要思想为覆盖*/// 用一个变量记录分割元素值ElemType PartitionData Data[start];while (start end) {// 从后向前寻找第一个小于分割元素值的位置while (start end Data[end] PartitionData) {end--;}// 覆盖Data[start] Data[end];// 从前向后寻找第一个大于分割元素值的位置while (start end Data[start] PartitionData) {start;}// 覆盖Data[end] Data[start];}// start所在位置几位中间位置(排序后实际所在位置)Data[start] PartitionData;return start;
}05-SortFunction.cpp 用于存储快速排序函数。
//
// Created by 24955 on 2023-03-06.
// 快排最好、平均时间复杂度O(nlog2n)最坏时间复杂度O(n^2)(本身有序)
// 快排空间复杂度O(log2n)
//
// 快速排序--数组指针操作
void QuickSortPointer(ElemType *Data, int Length) {/** 1. 传递数组指针和长度进行递归排序* 2. 此方式不便于理解当方便使用*/// 初始化头标签和尾标签int start 1, end Length - 1;// 备份Data数组--用于结尾交换和参数传递使用(内部更改了Data数组值)ElemType *TemporaryData Data;// 数组为1个或0个元素时自身有序因此结束递归if (Length 1) {end Partition(Data, start, end);// 可用以下代码替换该处函数调用{
// // 当end start时完成一次分割(大于分隔值的在右边小于分隔值的在左边)
// while (start end) {
// // 设当前数组第0个元素为分割元素
// /* 1. 头标签代表元素值大于等于分隔值时
// * 2. 判断尾标签代表元素与分隔值大小关系*/
// if (Data[start] Data[0]) {
// if (Data[end] Data[0]) {
// // 尾标签代表元素值大于等于分隔值时移动尾标签-1
// end--;
// } else {
// // 尾标签代表元素值小于分隔值时交换并将头标签1尾标签-1
// Swap(Data[start], Data[end--]);
// }
// } else {
// // 头标签代表元素值小于分隔值时移动头标签1
// start;
// }
// }
// // 将分割元素与尾标签所指元素交换即可将分割元素位于中间位置(排好分割元素)
// Swap(Data[end], Data[0]);}// 分而治之分别将分割元素之前的元素和之后的元素重新进行快排// 直到只有一个元素时结束递归QuickSortPointer(TemporaryData, end);QuickSortPointer(TemporaryData end 1, Length - end - 1);}
}// 快速排序--数组操作
void QuickSort(ElemType *Data, int start, int end) {/** 1. 递归结束条件为start end*/if (start end) {int PartitionIndex Partition(Data, start, end);// 设置尾标签为PartitionIndex - 1QuickSort(Data, start, PartitionIndex - 1);// 头标签位于分割元素之前因此需要2指向新的头标签(1指向分割元素)QuickSort(Data, PartitionIndex 2, end);}
}// 快速排序--挖坑法
void QuickSortHole(ElemType *Data, int start, int end) {/** 1. 递归结束条件为start end*/if (start end) {int PartitionIndex PartitionHole(Data, start, end);QuickSortHole(Data, start, PartitionIndex - 1);QuickSortHole(Data, PartitionIndex 1, end);}
}
结语 此博客主要用于408考研数据结构C语言实现记录内有不足可留言可讨论。
