当前位置：首页 > news >正文

[数据结构]：13-插入排序（顺序表指针实现形式）（C语言实现）

news 2025/7/7 4:01:57

前言

已完成内容

插入排序实现

01-开发环境

02-文件布局

03-代码

01-主函数

02-头文件

03-PSeqListFunction.cpp

04-SortCommon.cpp

05-SortFunction.cpp

结语

前言

此专栏包含408考研数据结构全部内容，除其中使用到C++引用外，全为C语言代码。使用C++引用主要是为了简化指针的使用，避免二重指针的出现。

插入排序本文主要采用了两种编写思想：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博客

[数据结构]：12-快速排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

插入排序实现

01-开发环境

语言：C/C++14

编译器：MinGW64

集成开发环境：CLion2022.1.3

02-文件布局

请在CLion集成开发环境中创建C++可执行程序，否则无法运行，原因上面已解释。

03-代码

01-主函数

用于测试插入排序。

// 顺序表以指针形式实现(申请堆空间，可动态控制顺序表大小)--数组实现形式不可以动态控制顺序表大小
#include "./Head/PSeqSearchData.h"
#include "./Source/PSeqListFunction.cpp"
#include "./Source/SortCommon.cpp"
#include "./Source/SortFunction.cpp"int 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;// 插入排序--交换思想
//    InsertSortExchange(PSL.data, PSL.ListLength);
//    PSeqListPrint(PSL);// 插入排序--覆盖实现(挖坑法)InsertSortHole(PSL.data, PSL.ListLength);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_H

03-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;
}

05-SortFunction.cpp

用于存储插入排序函数。

//
// Created by 24955 on 2023-03-07.
// 插入排序时间复杂度O(n^2)，空间复杂度O(1)
//
// 插入排序--交换思想
void InsertSortExchange(ElemType *Data, int Length) {/** 1. 外层循环控制要插入的元素* 2. 内层循环控制交换次数*/// 外层循环控制要插入的元素for (int i = 0; i < Length; i++) {// 内层循环控制交换次数for (int j = i; j > 0; j--) {// 若前一个元素大于当前元素则发生交换// 否则跳出循环if (Data[j - 1] > Data[j]) {Swap(Data[j], Data[j - 1]);} else {// 因为当前元素之前的所有元素已有序，找到第一个比自身小的元素// 之后的所有元素均小于自身，故可跳出循环break;}}}
}// 插入排序--覆盖思想(挖坑法)
void InsertSortHole(ElemType *Data, int Length) {/** 1. 外层循环控制要插入的元素* 2. 内层循环控制交换次数*/// 外层循环控制要插入的元素for (int i = 0; i < Length; i++) {// 临时变量储存待插入值ElemType TemporaryData = Data[i];int j;for (j = i; j > 0; j--) {if (Data[j - 1] > TemporaryData) {Data[j] = Data[j - 1];} else {break;}}// 由于上述为j = i;(j起始位置为待插入值所在位置)// 因此需循环结束后j才到待覆盖位置，故插入值的覆盖应在内层循环之外Data[j] = TemporaryData;}
}