c语言提高学习笔记——03-c提高10day_数据结构

在学习c语言提高-数据结构总结了笔记，并分享出来。有问题请及时联系博主：​​Alliswell_WP​​，转载请注明出处。

03-c提高10day_数据结构

目录：
一、队列(Queue)
1、队列基本概念
2、队列的链式存储
练习1：队列的链式存储
二、树和二叉树
1、树的基本概念
2、二叉树基本概念
3、二叉树的遍历
练习1：二叉树递归遍历（先序遍历）
练习2：二叉树的高度和叶子节点数目
练习3：二叉树的拷贝和释放
练习4：二叉树的非递归遍历
三、插入排序
练习1：插入排序

一、队列(Queue)

1、队列基本概念

队列是一种特殊的受限制的线性表。

队列（queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（Firs- In First Out)的线性表，简称FIFO，允许插入的一端为队尾，允许删除的一端为队头，队列不允许在中间部位进行操作！假设队列是q=(a1，a2...…,an)，那么al就是队头元素，而an是队尾元素，这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。如下图：

不支持遍历，不支持随机存取。

2、队列的链式存储

练习1：队列的链式存储

队列的链式存储.c

1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 struct Person
 7 {
 8     struct QueueNode node;
 9     char name[64];
10     int age;
11 };
12 
13 void test()
14 {
15     //初始化队列
16     LinkQueue queue = Init_LinkQueue();
17     
18     //创建数据
19     struct Person p1 = { NULL, "aaa", 10};
20     struct Person p2 = { NULL, "bbb", 20};
21     struct Person p3 = { NULL, "ccc", 30};
22     struct Person p4 = { NULL, "ddd", 40};
23     struct Person p5 = { NULL, "eee", 50};
24     struct Person p6 = { NULL, "fff", 60};
25     
26     //插入队列
27     Push_LinkQueue(queue, &p1);
28     Push_LinkQueue(queue, &p2);
29     Push_LinkQueue(queue, &p3);
30     Push_LinkQueue(queue, &p4);
31     Push_LinkQueue(queue, &p5);
32     Push_LinkQueue(queue, &p6);
33     
34     struct Person* pBack = (struct Person*)Back_LinkQueue(queue);
35     printf("队尾元素：%s %d\n", pBack->name, pBack->age);
36     
37     while(Size_LinkQueue(queue) > 0)
38     {
39         //获得队头元素
40         struct Person* person = (struct Person*)Front_LinkQueue(queue);
41         //打印队头元素
42         printf("Name:%s Age:%d\n", person->name, person->age);
43         //弹出队头元素
44         Pop_LinkQueue(queue);
45     }
46     
47     //销毁队列
48     Destroy_LinkQueue(queue);
49     
50 }
51 
52 int main(){
53 
54     test();
55     
56     system("pause");
57     return EXIT_SUCCESS;
58 }

LinkQueue.h

1 #pragma once
 2 
 3 #include<stdlib.h>
 4 
 5 //链表结点的数据类型
 6 struct QueueNode
 7 {
 8     struct QueueNode* next;
 9 };
10 
11 //链表数据类型
12 struct LQueue
13 {
14     struct QueueNode header;//头结点
15     int size;
16     struct Queue* rear;//尾指针，始终指向链表的最后一个结点
17 };
18 
19 typedef void* LinkQueue;
20 
21 #ifdef __cpluscplus
22 extern "C"{
23 #endif
24 
25 
26 
27     //初始化
28     LinkQueue Init_LinkQueue();
29     //入队
30     void Push_LinkQueue(LinkQueue queue, void* data);
31     //出队
32     void Pop_LinkQueue(LinkQueue queue);
33     //获得队头元素
34     void* Front_LinkQueue(LinkQueue queue);
35     //获得队尾元素
36     void* Back_LinkQueue(LinkQueue queue);
37     //大小
38     int Size_LinkQueue(LinkQueue queue);
39     //销毁队列
40     void Destroy_LinkQueue(LinkQueue queue);
41 
42 #ifdef __cpluscplus
43 }
44 #endif

LinkQueue.c

1 #include"LinkQueue"
  2 
  3 //初始化
  4 LinkQueue Init_LinkQueue()
  5 {
  6     struct LQueue* queue = malloc(sizeof(struct LQueue));
  7     if(NULL == queue)
  8     {
  9         return NULL;
 10     }
 11     
 12     queue->header.next = NULL;
 13     queue->size = 0;
 14     queue->rear = &(queue->header);
 15     
 16     return queue;
 17 }
 18 //入队
 19 void Push_LinkQueue(LinkQueue queue, void* data)
 20 {
 21     if(NULL == queue)
 22     {
 23         return;
 24     }
 25     if(NULL == data)
 26     {
 27         return;
 28     }    
 29     struct LQueue* q = (struct LQueue*)queue;
 30     struct QueueNode* n = (struct QueueNode*)data;
 31     
 32     q->rear->next = n;
 33     n->next = NULL;
 34     //更新尾指针
 35     q->rear = n;
 36     
 37     q->size++;
 38 }
 39 //出队
 40 void Pop_LinkQueue(LinkQueue queue)
 41 {
 42     if(NULL == queue)
 43     {
 44         return;
 45     }
 46     
 47     struct LQueue* q = (struct LQueue*)queue;
 48     
 49     if(q->size == 0)
 50     {
 51         return;
 52     }
 53     
 54     if(q->size == 1)
 55     {
 56         q->header.next = NULL;
 57         q->rear = &(q->header);
 58         q->size--;
 59         
 60         return;
 61     }
 62     
 63     
 64     struct QueueNode* pFirstNode = q->header.next;
 65     
 66     q->header.next = pFirstNode->next;
 67     
 68     q->size--;
 69     
 70 }
 71 //获得队头元素
 72 void* Front_LinkQueue(LinkQueue queue)
 73 {
 74     if(NULL == queue)
 75     {
 76         return NULL;
 77     }
 78 
 79     struct LQueue* q = (struct LQueue*)queue;
 80     
 81     return q->header.next;
 82 }
 83 //获得队尾元素
 84 void* Back_LinkQueue(LinkQueue queue)
 85 {
 86     if(NULL == queue)
 87     {
 88         return NULL;
 89     }
 90 
 91     struct LQueue* q = (struct LQueue*)queue;
 92     
 93     return q->rear;    
 94 }
 95 //大小
 96 int Size_LinkQueue(LinkQueue queue)
 97 {
 98     if(NULL == queue)
 99     {
100         return -1;
101     }
102 
103     struct LQueue* q = (struct LQueue*)queue;
104     
105     return q->size;        
106 }
107 //销毁队列
108 void Destroy_LinkQueue(LinkQueue queue)
109 {
110     if(NULL == queue)
111     {
112         return;
113     }
114     free(queue);
115     queue = NULL;
116 }

二、树和二叉树

1、树的基本概念

>树的定义：
由一个或多个（n20)结点组成的有限集合T，有且仅有一个结点称为根(root），当n>1时，其余的结点分为m（m≥0）个互不相交的有限集合T1，T2….Tm。每个集合本身又是一颗树，被称作这个根的子树。

>树的结构特点
■非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）
■树的定义具有递归性，树中还有树。
■树可以为空，即节点个数为0。

>若干术语
■根→即根结点（没有前驱）
■叶子→即终端结点（没有后继）
■森林→指m棵不相交的树的集合（例如删除A后的子树个数）
■有序树→结点各子树从左至右有序，不能互换（左为第一）
■无序树→结点各子树可互换位置。
■双亲→即上层的那个结点（直接前驱）parent
■孩子→即下层结点的子树(直接后继）child
■兄弟→同一双亲下的同层结点（孩子之间互称兄弟）sibling
■堂兄弟→即双亲位于同一层的结点（但并非同一双亲）cousin
■祖先→即从根到该结点所经分支的所有结点
■子孙→即该结点下层子树中的任一结点

■结点→即树的数据元素
■结的度→结点挂接的子树数（有几个直接后继就是几度）
■结点的层次→从根到该结点的层数（根结点算第一层）
■终端结点→即度为0的结点，即叶子
■分支结点→除树根以外的结点（也称为内部结点）
■树的度→所有结点度中的最大值（Max（各结点的度]）
■树的深度（或高度）→指所有结点中最大的层数（Max（各结点的层次））

2、二叉树基本概念

>定义：
n(n>=0)个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成，

>逻辑结构：
一对二（1：2）

>基本特征：
■每个结点最多只有两棵子树（不存在度大于2的结点）；
■左子树和右子树次序不能顺倒（有序树）。

>二叉树性质
■性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>0）
■性质2：深度为k的二叉树至多有2^(k) - 1 个结点（k>0）
■性质3：对于任何一棵二又树，若度为2的结点数有n2个，则叶子数（n0）必定为n2+1（即n0=n2+1）

3、二叉树的遍历

>遍历用途
它是树结构插入、删除、修改、查找和排序运算的前提，是二又树一切运算的基础和核心。

>遍历方法
牢记一种约定，对每个结点的查看都是“先左后右”。
限定先左后右，树的遍历有三种实现方案：

DLR       　　　　　　 LDR     　　　　   LRD

先（根）序遍历    中（根）序遍历   后（根）序遍历

■DLR-先序遍历，即先根再左再右
■LDR-中序遍历，即先左再根再右
■LRD-后序遍历，即先左再右再根

注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。
从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

练习1：二叉树递归遍历（先序遍历）

1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 
 7 struct BiNode
 8 {
 9     char ch;
10     struct BiNode* lchild;
11     struct BiNode* rchild;
12 };
13 
14 //二叉树递归遍历（先序遍历）
15 void recursion(struct BiNode* root)
16 {
17     if(NULL == root)
18     {
19         return;
20     }
21     
22     printf("%c ", root->ch);
23     //递归遍历左子树
24     recursion(root->lchild);
25     //递归遍历右子树
26     recursion(root->rchild);
27 }
28 
29 void test()
30 {
31     struct BiNode nodeA = { 'A', NULL, NULL};
32     struct BiNode nodeB = { 'B', NULL, NULL};
33     struct BiNode nodeC = { 'C', NULL, NULL};
34     struct BiNode nodeD = { 'D', NULL, NULL};
35     struct BiNode nodeE = { 'E', NULL, NULL};
36     struct BiNode nodeF = { 'F', NULL, NULL};
37     struct BiNode nodeG = { 'G', NULL, NULL};
38     struct BiNode nodeH = { 'H', NULL, NULL};
39     
40     nodeA.lchild = &nodeB;
41     nodeA.rchild = &nodeF;
42     
43     nodeB.rchild = &nodeF;
44     
45     nodeC.lchild = &nodeD;
46     nodeC.rchild = &nodeE;
47     
48     nodeF.rchild = &nodeG;
49     
50     nodeG.lchild = &nodeH;
51     
52     recursion(&nodeA);
53 }
54 
55 int main(){
56 
57     test();
58     
59     system("pause");
60     return EXIT_SUCCESS;
61 }

练习2：二叉树的高度和叶子节点数目

1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 
 7 struct BiNode
 8 {
 9     char ch;
10     struct BiNode* lchild;
11     struct BiNode* rchild;
12 };
13 
14 //int num = 0;全局变量比较浪费空间
15 //求二叉树的叶子结点数目（先序遍历）
16 void cuculateLeafNum(struct BiNode* root, int* p)
17 {
18     if(NULL == root)
19     {
20         return;
21     }
22     
23     if(root->lchild && root->rchild == NULL)
24     {
25         (*p)++;
26     }
27     cuculateLeafNum(root->lchild, p);
28     cuculateLeafNum(root->rchild, p);
29 }
30 
31 int getTreeHeight(struct BiNode* root)
32 {
33     if(NULL == root)
34     {
35         return 0;
36     }    
37     
38     //求树的左子树高度
39     int lheight = getTreeHeight(root->lchild);
40     //求树的右子树高度
41     int rheight = getTreeHeight(root->lchild);
42     
43     int height = lheight > rheight ? lheight + 1 : rheight + 1;
44     
45     return height;
46 }
47 
48 void test()
49 {
50     struct BiNode nodeA = { 'A', NULL, NULL};
51     struct BiNode nodeB = { 'B', NULL, NULL};
52     struct BiNode nodeC = { 'C', NULL, NULL};
53     struct BiNode nodeD = { 'D', NULL, NULL};
54     struct BiNode nodeE = { 'E', NULL, NULL};
55     struct BiNode nodeF = { 'F', NULL, NULL};
56     struct BiNode nodeG = { 'G', NULL, NULL};
57     struct BiNode nodeH = { 'H', NULL, NULL};
58     
59     nodeA.lchild = &nodeB;
60     nodeA.rchild = &nodeF;
61     
62     nodeB.rchild = &nodeF;
63     
64     nodeC.lchild = &nodeD;
65     nodeC.rchild = &nodeE;
66     
67     nodeF.rchild = &nodeG;
68     
69     nodeG.lchild = &nodeH;
70     
71     //1.求二叉树的叶子结点数目
72     int num = 0;
73     cuculateLeafNum(&nodeA, &num);
74     printf("叶子结点数目：%d\n", num);
75     
76     //2.求二叉树的高度
77     int height = getTreeHeight(&nodeA);
78     printf("树的高度：%d\n", height);
79 }
80 
81 int main(){
82 
83     test();
84     
85     system("pause");
86     return EXIT_SUCCESS;
87 }

练习3：二叉树的拷贝和释放

1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<stdlib.h>
  5 
  6 
  7 struct BiNode
  8 {
  9     char ch;
 10     struct BiNode* lchild;
 11     struct BiNode* rchild;
 12 };
 13 
 14 //int num = 0;全局变量比较浪费空间
 15 //求二叉树的叶子结点数目（先序遍历）
 16 void cuculateLeafNum(struct BiNode* root, int* p)
 17 {
 18     if(NULL == root)
 19     {
 20         return;
 21     }
 22     
 23     if(root->lchild && root->rchild == NULL)
 24     {
 25         (*p)++;
 26     }
 27     cuculateLeafNum(root->lchild, p);
 28     cuculateLeafNum(root->rchild, p);
 29 }
 30 
 31 int getTreeHeight(struct BiNode* root)
 32 {
 33     if(NULL == root)
 34     {
 35         return 0;
 36     }    
 37     
 38     //求树的左子树高度
 39     int lheight = getTreeHeight(root->lchild);
 40     //求树的右子树高度
 41     int rheight = getTreeHeight(root->lchild);
 42     
 43     int height = lheight > rheight ? lheight + 1 : rheight + 1;
 44     
 45     return height;
 46 }
 47 //拷贝
 48 struct BiNode* copyBiTree(struct BiNode* root)
 49 {
 50     if(NULL == root)
 51     {
 52         return NULL;
 53     }
 54     
 55     //先拷贝左子树
 56     struct BiNode* lchild = copyBiTree(root->lchild);
 57     //拷贝右子树
 58     struct BiNode* rchild = copyBiTree(root->rchild);
 59     
 60     struct BiNode* newnode = malloc(sizeof(struct BiNode));
 61     newnode->lchild = lchild;
 62     newnode->rchild = rchild;
 63     newnode->ch = root->ch;
 64     
 65     return newnode;
 66 }
 67 
 68 //释放（后序遍历）
 69 void freeSpace(struct BiNode* root)
 70 {
 71     if(NULL == root)
 72     {
 73         return;
 74     }    
 75     
 76     //释放左子树内存
 77     freeSpace(root->lchild);
 78     //释放右子树
 79     freeSpace(root->rchild);
 80     
 81     printf("%c 被释放！\n", root->ch);
 82     free(root);
 83 }
 84 
 85 void showBiTree(struct BiNode* root)
 86 {
 87     if(NULL == root)
 88     {
 89         return;
 90     }
 91 
 92     printf("%c ", root->ch);
 93     showBiTree(root->lchild);
 94     showBiTree(root->rchild);
 95 }
 96 
 97 void test()
 98 {
 99     struct BiNode nodeA = { 'A', NULL, NULL};
100     struct BiNode nodeB = { 'B', NULL, NULL};
101     struct BiNode nodeC = { 'C', NULL, NULL};
102     struct BiNode nodeD = { 'D', NULL, NULL};
103     struct BiNode nodeE = { 'E', NULL, NULL};
104     struct BiNode nodeF = { 'F', NULL, NULL};
105     struct BiNode nodeG = { 'G', NULL, NULL};
106     struct BiNode nodeH = { 'H', NULL, NULL};
107     
108     nodeA.lchild = &nodeB;
109     nodeA.rchild = &nodeF;
110     
111     nodeB.rchild = &nodeF;
112     
113     nodeC.lchild = &nodeD;
114     nodeC.rchild = &nodeE;
115     
116     nodeF.rchild = &nodeG;
117     
118     nodeG.lchild = &nodeH;
119     
120     //1.求二叉树的叶子结点数目
121     int num = 0;
122     cuculateLeafNum(&nodeA, &num);
123     printf("叶子结点数目：%d\n", num);
124     
125     //2.求二叉树的高度
126     int height = getTreeHeight(&nodeA);
127     printf("树的高度：%d\n", height);
128     
129     //3.拷贝二叉树
130     struct BiNode* root = copyBiTree(&nodeA);
131     showBiTree(root);
132     printf("\n");
133     showBiTree(&nodeA);
134     
135     //释放（自己开辟的内存）
136     freeSpace(root);
137 }
138 
139 int main(){
140 
141     test();
142     
143     system("pause");
144     return EXIT_SUCCESS;
145 }

练习4：二叉树的非递归遍历

思路：需要用到栈

模型分析图如下：

代码如下：

二叉树的非递归遍历.c

1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<stdlib.h>
  5 #include<stdbool.h>
  6 #include"SeqStack.h"
  7 
  8 struct BiNode
  9 {
 10     char ch;
 11     struct BiNode* lchild;
 12     struct BiNode* rchild;
 13 };
 14 
 15 
 16 
 17 struct Info
 18 {
 19     struct BiNode* node;
 20     bool flag;
 21 };
 22 
 23 struct Info* createInfo(struct BiNode* node, bool flag)
 24 {
 25     struct Info* info = malloc(sizeof(struct Info));
 26     info->flag = flag;
 27     info->node = node;
 28     
 29     return info;
 30 }
 31 
 32 //非递归遍历
 33 void nonRecursion(struct BiNode* root)
 34 {
 35     //初始化栈
 36     SeqStack stack = Init_SeqStack();
 37     //先把根结点压入栈中
 38     Push_SeqStack(stack, createInfo(root, false));
 39     
 40     while(Size_SeqStack(stack) > 0)
 41     {
 42         //获得栈顶元素
 43         struct Info* info = (struct Info*)Top_SeqStack(stack);
 44         //弹出栈顶元素
 45         Pop_SeqStack(stack);
 46         
 47         if(info->flag)
 48         {
 49             printf("%c ", info->node->ch);
 50             free(info);
 51             continue;
 52         }
 53         
 54         //将右子树压入栈中
 55         if(info->node->rchild != NULL)
 56         {
 57             Push_SeqStack(stack, createInfo(info->node->rchild, false));
 58         }
 59         //将左子树压入栈中
 60         if(info->node->lchild != NULL)
 61         {
 62             Push_SeqStack(stack, createInfo(info->node->lchild, false));
 63         }
 64         
 65         //将根结点入栈
 66         info->flag = true;
 67         Push_SeqStack(stack, info);
 68     }
 69     
 70     //销毁栈
 71     Destroy_SeqStack(stack);
 72 }
 73 
 74 void test()
 75 {
 76     struct BiNode nodeA = { 'A', NULL, NULL};
 77     struct BiNode nodeB = { 'B', NULL, NULL};
 78     struct BiNode nodeC = { 'C', NULL, NULL};
 79     struct BiNode nodeD = { 'D', NULL, NULL};
 80     struct BiNode nodeE = { 'E', NULL, NULL};
 81     struct BiNode nodeF = { 'F', NULL, NULL};
 82     struct BiNode nodeG = { 'G', NULL, NULL};
 83     struct BiNode nodeH = { 'H', NULL, NULL};
 84     
 85     nodeA.lchild = &nodeB;
 86     nodeA.rchild = &nodeF;
 87     
 88     nodeB.rchild = &nodeF;
 89     
 90     nodeC.lchild = &nodeD;
 91     nodeC.rchild = &nodeE;
 92     
 93     nodeF.rchild = &nodeG;
 94     
 95     nodeG.lchild = &nodeH;
 96     
 97     nonRecursion(&nodeA);
 98 }
 99 
100 int main(){
101 
102     test();
103     
104     system("pause");
105     return EXIT_SUCCESS;
106 }

SeqStack.c和SeqStack.h和栈的顺序存储相同

SeqStack.h

1 #pragma once
 2 
 3 #include<stdlib.h>
 4 #include<string.h>//memset
 5 
 6 #ifdef __cplusplus
 7 extern "C"{
 8 #endif    
 9 
10 
11 #define MAX 1024
12 
13     //顺序栈数据结构
14     struct SStack
15     {
16         void* data[MAX];//存放数据的数组
17         int size;//栈中元素的个数
18     }
19     
20     //数组高下标的位置当做栈顶，因为不需要移动数组中的元素在插入和删除中
21     
22     //初始化
23     SeqStack Init_SeqStack();
24     //入栈
25     void Push_SeqStack(SeqStack stack, void* data);
26     //出栈
27     void Pop_SeqStack(SeqStack stack);
28     //获得栈顶元素
29     void* Top_SeqStack(SeqStack stack);
30     //获得栈的大小
31     int Size_SeqStack(SeqStack stack);
32     //销毁栈
33     void Destroy_SeqStack(SeqStack stack);
34 
35 #ifdef __cplusplus
36 }
37 #endif

SeqStack.c

1 #include"SeqStack.h"
 2 
 3 //初始化
 4 SeqStack Init_SeqStack()
 5 {
 6     struct SStack* stack = malloc(sizeof(struct SStack));
 7     if(NULL == stack)
 8     {
 9         return NULL;
10     }
11     
12     memset(stack, 0, sizeof(struct SStack));
13     stack->size = 0;
14     
15     return stack;
16 }
17 //入栈
18 void Push_SeqStack(SeqStack stack, void* data)
19 {
20     if(NULL == stack)
21     {
22         return;
23     }
24     if(NULL == data)
25     {
26         return;
27     }    
28     
29     struct SStack* s = (struct SStack*)stack;
30     
31     s->data[s->size] = data;
32     s->size++;
33 }
34 //出栈
35 void Pop_SeqStack(SeqStack stack)
36 {
37     if(NULL == stack)
38     {
39         return;
40     }
41     struct SStack* s = (struct SStack*)stack;
42     
43     if(s->size == 0)
44     {
45         return;
46     }
47     
48     s->data[s->size-1] = NULL;//此句可有可无，有数据会把这块内存覆盖
49     s->size--;
50 }
51 //获得栈顶元素
52 void* Top_SeqStack(SeqStack stack)
53 {
54     if(NULL == stack)
55     {
56         return NULL;
57     }
58 
59     struct SStack* s = (struct SStack*)stack;
60     
61     if(s->size == 0)
62     {
63         return NULL;
64     }
65     
66     return s->data[s->size-1];
67 }
68 //获得栈的大小
69 int Size_SeqStack(SeqStack stack)
70 {
71     if(NULL == stack)
72     {
73         return -1;
74     }
75 
76     struct SStack* s = (struct SStack*)stack;
77     return s->size;
78 }
79 //销毁栈
80 void Destroy_SeqStack(SeqStack stack)
81 {
82     if(NULL == stack)
83     {
84         return;
85     }
86     free(stack);
87         
88 }

三、插入排序

练习1：插入排序

分析如下：

代码如下：

1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 
 6 //打印
 7 void printArray(int arr[], int len)
 8 {
 9     for(int i = 0; i < len; ++i)
10     {
11         printf("%d ", arr[i]);
12     }
13     printf("\n");
14 }
15 
16 //插入排序
17 void InsertSort(int arr[], int len)
18 {
19     for(int i = 1; i < len; ++i)
20     {
21         if(arr[i] < arr[i - 1])
22         {
23             int temp = arr[i];
24             int j = i - 1
25             for(; j >= 0; temp < arr[j]; j--)
26             {
27                 arr[j + 1] = arr[j];
28             }
29             
30             arr[j + 1] = temp;
31         }
32     }
33     
34 }
35 
36 void test()
37 {
38     int arr[] = {5, 3, 9, 2, 1, 3};
39     int len = sizeof(arr) / sizeof(int);
40     printArray(arr, len);
41     InsertSort(arr, len);
42     printArray(arr, len);
43 }
44 
45 int main(){
46 
47     test();
48     
49     system("pause");
50     return EXIT_SUCCESS;
51 }

在学习c语言提高-数据结构总结了笔记，并分享出来。有问题请及时联系博主：​​Alliswell_WP​​，转载请注明出处。