Maxwell_Leiの小窝

前言数据结构的最后一部分了，排序也是在前面的数据结构的基础上来解决实际问题的。 排序排序算法可以根据数据量的大小分为： 内部排序：数据都在内存中 外部排序：数据太多，无法全部存放在内存中 关于下述的各种排序算法是基于如下的方法结构来实现的： 123456789101112131415161718192021222324252627282930313233343536373839404142#include <stdio.h>#include <stdbool.h>#define _CRT_SECURE_NO_WARNINGS#define ElemType int //存放的数据类型#define MaxSize 10 //最大数组容量//定义了新的List类型typedef struct list { ElemType data[MaxSize]; //数据数组 int num; //数组的实际大小，即实际存放数据数量}List;//遍历输出Listvoid PrintList(List l) { printf("L ...

前言查找表：是一种数据集合（记录），可以理解为你要从哪里查找 查找表可以分为静态查找表和动态查找表 静态查找：只需要执行查找操作 动态查找：除了查找之外还需要增/删除数据元素 顺序查找顺序查找是我们最开始，也是最熟悉的查找方式，就是一个一个查找（遍历）。 常规顺序查找又称“线性查找”，通常用于线性表。其查找模式是线性的。代码示例： 1234567891011121314151617181920#define ElemType int#define MaxSize 10typedef struct sTable{ ElemType a[MaxSize]; int TableLen;}STable;//顺序查找int Serach_Seq(STable s,ElemType data) { for (int i = 0; i < s.TableLen; i++) { if (data == s.a[i]) { printf("下标为:%d", i); return i; } & ...

前言图比较复杂，涉及的算法相对较多。 图的定义图，就是例如下图的东西，图可以分为 有向图：即带有明确的方向指向的图，可以使用 $<a,c>$ 表示从 A 到 C 顶点的路径 无向图：不带有明确的方向指向的图，可以使用 $(a,c)$ 表示从 A 到 C 顶点的路径 图注：有向图 图注：无向图 对于图来说，要求边的两端必须存在“顶点”，否则它不是图。同样的，对于图来说，也不存在空图的概念。 从图的结构来说，又可以分为：简单图和多重图。 简单图 不存在重复边 不存在顶点到自身的边 多重图 允许重复边 允许存在顶点到自身的边 图的基本概念 图的阶：图里面的顶点（或者叫结点）个数 顶点的度 无向图：顶点的边数 有向图：入度 + 出度 出度：从顶点指向外面顶点的边 入度：指向顶点的边 路径：两个顶点之间的顶点序列，例如下图：A 到 B 的路径为：A,C,B 回路：第一个顶点和最后一个顶点相同的路径 简单路径：在路径序列中，顶点不重复出现的路径 简单回路：除了第一个顶点和最后一个顶点外，其余顶点不出现重复的回路 路径长度：路径上边的 ...

前言由于计算机的发展，人们发现对于非数值类型的处理越来越多，进而衍生出来串。 串也就是我们所使用的字符串。 如下所有代码需要做如下引用： 123456#include <stdio.h>#include <stdbool.h>#include <string.h>//如果你使用的是Visual Studio，则还需要添加如下一条引用#define _CRT_SECURE_NO_WARNINGS 关于上述引用的说明，原因参考关于C语言的一些零碎思考 串的定义和基本操作串的定义串，即字符串（String）是由零个或者多个字符组成的有限序列，一般记作S='a1,a2,...an'（$n \geqslant 0 $）。 其中S是串的名称，单引号括起来的字符序列是串的值，其中串字符的个数称为串的长度。当 $n =0$ 的时候称为空串。代码示例： 1S = "Hello,World" 子串：串中任意连续个字符组成的子序列，例如：上面的子串Hello。 串的数据对象限定为：字符集（如中文字符，英文字符）。 串的 ...

前言树的基本概念树的定义树是一种数据结构，它和我们现实生活中的树非常类似，其存在一个根节点，向下分裂，产生分支节点，如此，形成了如下图所示的“树”： 图片来源王道《数据结构》 当然，存在一种特殊的树——空树，也就是结点树为 0 的树。 非空树的特性： 有且仅有一个根节点 没有后继的结点称为“叶子结点”（终端结点） 有后继的结点称为“分支节点”（非终端结点） 结点之间的关系描述 祖先结点：在当前指定结点前驱到根节点路径上的所有结点（即上层） 子孙结点：指定结点下面的所有结点 双亲结点：指定结点的前驱结点 孩子结点：指定结点的直接后继 兄弟结点：指定结点同一层且同一个前驱的结点 堂兄弟结点：指定结点同一层且不是同一个前驱的结点 结点之间的路径：根结点到指定结点（只能从上往下） 路径长度：指的经过了几条边（只能从上往下） 结点，树的属性描述 结点的层次（深度）：从上往下数 结点的高度：从下往上数 树的高度（深度）：总共多少层 结点的度：结点有几个分支 树的度：各结点的度的最大值 树的分类 有序树：逻辑上树中的结点的各子树从左到右是有次序的，不能互换。 无序树：逻辑上树中的结点 ...

前言栈和队列是线性表的另一种变形，它拥有一些各自的特点。 如下所有代码需要做如下引用： 123456#include <stdio.h>#include <stdbool.h>#include <malloc.h>//如果你使用的是Visual Studio，则还需要添加如下一条引用#define _CRT_SECURE_NO_WARNINGS 关于上述引用的说明，原因参考关于C语言的一些零碎思考 栈栈的基本概念栈的定义栈(Stack)本质来说还是一种线性表，栈是只允许在一端进行插入或者删除操作的线性表。 空栈：栈中不存储任何数据 栈顶：栈的最顶端 栈底：栈的最低端 栈的特点：后进先出（Last In First Out，LIFO） 栈的基本操作 操作 说明 InitStack() 初始化栈。创造一个空栈，分配内存空间 DestoryStack() 销毁栈。销毁并释放栈所占的内存空间 Push() 进栈。如果栈未满，则将新元素压入栈顶 Pop() 出栈。如果栈不是空栈，则将栈顶元素弹出栈 GetTop() 读取 ...

前言在使用C的时候难免会碰到一些奇怪的用法或者令人困惑的语法等等，考虑到问题过于琐碎，就写于这个合集中，名为关于C语言的零碎思考 typedef 和 define 的区别这种关键字的使用常见于对于某种类型的替换，例如下面的场景： 123#define ElemType inttypedef int NewType 两者的区别在于：define是一种宏定义，本质上来说就是字符串替换，而typedef是一种类型封装。 例如参考下面的代码，思考各个变量的类型： 12345#define ElemType int*int main(){ ElemType a,b; } 其中变量a的类型为int*，而变量b的类型为int类型，不难理解宏定义只是字符串替换。 12345typedef int* ElemTypeint main(){ ElemType a,b;} 其中**变量a和变量b的类型均为int***，可以理解为typedef将int*封装成了一个新的类型。 typedef 和 struct 的使用关于结构体的相关基础内容我已经在这篇 ...

前言算法是什么？我们如何来评估算法的好坏？有没有一种优美的数学方式来评估算法好坏，而不受客观环境的影响。例如计算机的性能影响？ 学习此部分，需要掌握一定的C语言基础 本部分内容参考程杰老师《大话数据结构》，青岛大学王卓老师的授课等 综合个人所学的总结笔记 本篇写于 时间 ，部分内容可能与现在不符，请自行判断 ——这一招是我从我最爱的游戏里学来的♬ 算法的定义算法是解决特定问题求解步骤的描述，在计算机中表示为指令的有限序列并且每条指令表示一个或者多个操作算法通俗理解就是对于问题的特定解决步骤。 算法的特性 输入输出算法具有零个或者多个输入，至少有一个输出。 有穷性算法在有限的步骤之后，能够自动结束而非无限循环。 确定性算法的每一个步骤都具有确定的含义，不会存在二义性。 可行性算法的每一个步骤都必须是可行的，也就是说每一步，都能执行有限次数完成。 算法设计要求 正确性算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确的反映问题的需求，能够得到问题的正确答案。 可读性算法设计的另一目的是为了便于阅读，理解和交流 健壮性当输入的数据不合法时，算法也可以对其做出相应处 ...

前言有了前面的基础，现在开始正式学习数据结构最常用也是最简单的一种结构——线性表。 学习本文需要掌握一定的 C语言基础。 本部分内容参考程杰老师《大话数据结构》，青岛大学王卓老师的授课，王道考研公开课等 综合个人所学的总结笔记。 线性表的定义线性表，顾名思义，是具有像线一样串联起来的表。串联则意味着存在一个头部，一个尾部，且中间的每个元素都是一个挨着一个，这样的表就可以称为线性表。 线性表(List)：零个或多个数据元素的有限序列。 需要强调的是： 首先它是一个序列，也就是说，元素之间是有顺序的，如果元素存在多个，那么第一个元素无前驱，最后一个元素无后继，其他的元素都有且只有一个前驱和后继。 其次，线性表是有限的。事实上，计算机中处理的对象都是有限，无限的序列，只存于数学中的概念。 如果使用数学语言来进行定义的话，如下： 若将线性表记为（$a_1,·····,a_{i-1},a_i,a_{i+1},···,a_n$），则表中 $a_{i-1}$ 领先于 $a_i$ ，$a_i$ 领先于 $a_{i+1}$，称 $a_{i-1}$ 是 $a_i$ 的直接前驱，$a_{i+1}$ 是 ...

前言在前面介绍了线性表是什么，现在来讲述线性表的两种物理结构的第一种——顺序存储结构。 学习本文需要掌握一定的 C语言基础。 本部分内容参考程杰老师《大话数据结构》，青岛大学王卓老师的授课，王道考研公开课等 综合个人所学的总结笔记。 线性表的顺序存储结构顺序表——用顺序存储的方式实现的线性表 顺序存储定义线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。 线性表的顺序存储示意图如下： 可以通过sizeof(ElemType)函数来获取数据元素的大小 顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。 顺序表上的基本操作的实现静态分配静态分配，顾名思义，它的分配空间在一开始定义的时候就是固定的，代码示例： 123456#define MaxSize 10 //链表默认空间大小typedef struct{ ElemType data[MaxSize]; //静态空间大小 int length; //链表的长度}SqList; //链表结构体 ElemType需要看你具体使用的数据结构的类型 此处 ...