活动选择问题 无权值 问题背景 有一个会场，需要安排几场活动 公司年会：10:00 - 19:00 婚礼宴请：11:00- 14:00 生日聚会：12:00 - 17:00 学术研究：14:00 - 16:00 问 如果安排这个会场能让活动尽可能的多的进行？ 有下面这几个活动和占比时间 选择出租的时间不能有冲突 问题研究，策略选择 ​ 这时候我们采用贪心策略： 策略一：最短活动优先 策略二：最早开始的活动优先 ​ 策略三：最早结束活动优先 选择最早结束的活动，可以给后面的活动留出更大的弓箭 证明该策略是正确的（替换法） ​ 我们可以通过替换的规则让 某个最优解替换为 贪心所得的最优解，在替换的时候，如果活动相同的话，直接替换即可，如果不相同的话，因为贪心所得的是这个活动的最先完成 的活动，所有会给后面的活动留出的活动空间更大不会影响后面活动的替换 代码实现 输入：活动集合S={a1, a2, a3 … an}，每个活动ai的起始时间si 结束时间 fi 输出：不冲突的最大子集S‘ 先把活动结束时间由小到大排个序 先给数组S赋值 a1（因为这里a ...

逆序对（分治法） 逆序对的含义 什么是逆序对？ 例如上面这个表格第一行是数组序号，第二行是数组元素 当序号小的数组元素值大于序号大的数组元素值的时候称这两个数为逆序对 例如： （4,3）（4,5）就是逆序对 枚举法 我们通过两层for循环来遍历这个数组，挨个寻找到所有的逆序对 分治法 我们把数组分为两个部分对每个部分分别求解，使用二分法，对每个部分分别求出最大子序列，然后再求出合并之后的最大子序列，最后让这三部分相加。 最后让这三个相加得出最后的逆序对个数 求解S3的方法： 使用枚举法，遍历前面的和后面的分别比较求解 但是最后的时间复杂度还是O(n2n^2n2) 所以直接求解S3的分而治之和蛮力枚举并未提高算法运行时间 原因：我们每次在寻找A[i] 里面那个元素比A[j]的小的时候，都要遍历一遍A[i] ，这样时间比较多 改进方法：我们可以通过讲数组A[i] 和A[j]分别进行排序，然后使用二分查找进行查找对应元素，这样算法效率就能提高不少 排序之后使用二分法求解 分别对数组A[1…m]和A[m + 1…n]进行排序 对于每个A[j] e A[m+ 1…n] ...

树的定义 树与线性表不同的地方是：线性表有唯一 的直接前趋，和唯一的直接后继，但是树有唯一的直接前趋，不唯一的直接后继 树是n（n≥0）个结点的有限集。 若n == 0, 称为**空树** 若 n > 0，则它满足以下两个条件： 有且仅有一个特定的称为根的节点 其余节点可分为m（m≥0）个互不相交的有限集T1， T2, T3·····其中每一个集合本身有是一颗树，并成为根的子树 树的基本术语 根节点：非空树中无前趋结点的结点 节点的度：结点拥有的子树数 树的度：树内各节点的度的最大值 当度=0时的结点：终端节点 当度≠0时的结点：称为分支结点，非终端结点，根节点以外的分支结点称为内部结点 结点的子树的跟称为该节点的孩子，该节点称为孩子的双亲 拥有同一个双亲的一类结点，称为兄弟结点 双亲在同一层的结点，称为堂兄弟结点 结点的祖先：从根节点到该节点所经分支上的所有结点 树的深度：树中结点的最大层次 有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子） 无序树：树中结点的各子树无次序。 森林：是m(m≥0)颗互 ...

第一部分 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125#include <stdio.h>#include <stdlib.h>typedef struct BiTree{ char data; struct BiTree *lchild; struct BiTree *rchild;}BiTree, *BiNode;BiNode CreatBiTree(BiNode T){ char ch; scanf("%c ...

以下是顺序表的代码的实现 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124#include <stdio.h>#include<stdlib.h>#include<string.h>#define MAX 20typedef struct Sqtable{ int a[20]; int length;}Sq;void read_Sq(Sq *L){ int n = 0; int *p = L->a; FILE *f ...

线性表 定义 线性表是具有相同特征的数据元素的一个有限序列 a1,a2,a3·····,ai-1,ai,ai+1,······,an 上面元素称为数据元素 a1 称为线性起点 an是线形终点，n为元素总个数，即表长 ai-1是ai的直接前趋， ai+1是ai的直接后续 当n=0时，称为空表 线性表： 由n（n>=0）个数据元素（节点）a1,a2,a3,a4····an组成的有限序列 其中数据元素的个数n定义为表的长度 当n= 0时称为空表 当非空的线性表（n>0）记作：（a1,a2····an） 这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同情况下可以不同 逻辑特征 在非空线性表，有且仅有一个开始节点a1，他没有直接前趋，而仅有一个直接后续a2 有且仅有一个终端节点an,他没有直接后续，而且仅有一个直接前趋an-1 其余的内部节点ai(2<=i<=n-1)都有且仅有一个直接前趋ai-1和一个直接后续ai+1 案例 一元多项式的计算 当表达式为p0 + p1x^1 + p2x^2 + p3 ...

栈代码的实现 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920 ...

栈和队列 定义： 栈和队列是两种常用的，重要的数据结构 栈和队列是限定插入和删除只能在表的“端点“进行的线性表 其中栈，规定再插入的时候只能插入在表尾，删除的时候也只能删除最后一个 ”后进先出“ 是栈的结构特点 数值转换 表达式求值 括号匹配的检验 八皇后的问题 行编辑的程序 函数调用 迷宫求解 函数调用 迷宫求解 递归调用的实现 其中队列，规定插入的时候 只能在表尾插入，删除的时候只能在表头删除。 ”先进先出“是队列的结构特点，使得队列可以解决类似排队问题的有用工具 脱机打印输出：按申请的先后顺序依次输出 多用户系统中，多个用户排成队，分时的循环使用CPU和主存 按用户优先级拍成多个队，每个优先级一个队列 实时控制系统中，信号按接受的先后顺序依次处理 网络电文传输，按照到达的时间先后顺序依次进行 栈的结构和特点 栈是一个特殊的线性表，是限定仅在一段（通常是表尾）进行插入和删除操作的线性表 又称为后进先出（Last In First Out）的线性表，简称LIFO结构 栈的相关概念 栈是仅在表尾进行插入，删除操作的线性表。表尾（即an端）称为栈顶Top ...

串 串：内容受限制的线性表（里面内容只能是字符串） S = "a1a2a3·····an"(n≥0) 串名：S； 串值：“a1a2a3·····an”; 串长：n; 空串：n = 0；空集 子串：一个串中任意个连续字符组成的**子序列（含空串）**称为该串的子串 例如，“abcde”的字串有： “”， “a”,"ab", "abc","abcd","abcde" 真子串是指不包含自身的所有子串 主串：包含子串的串相应的称为主串 字符位置：字符在序列中的序号为该字符在串中的位置 字串位置：子串第一个字符再主串中的位置 空格串：有一个或多个空格组成的串，与空串不同 例：字符串a,b,c,d a = "BEI"; b = "JING"; c = "BEIJING"; d = "BEI JING" 它们的长度是：3，4，7，8 c的子串：a b d的子串 ...