算法实现
未读 逆序对(分治法)
逆序对的含义
什么是逆序对?
例如上面这个表格第一行是数组序号,第二行是数组元素
当序号小的数组元素值大于序号大的数组元素值的时候称这两个数为逆序对
例如:
(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的子串 ...
关于KMP算法的实现,如果转载请标明出处
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118#include <stdio.h>#include <stdlib.h>#include <string.h>#define OK 1#define ERROR 0#define status int typedef struct sstring{ char ch[50]; int length;}Sstring, *Lstring;status InitString(Lstring& ...
数据结构
1.数据
数值型
1 2 3
非数值型
文字,图像, 图形
2.数据元素和数据项
数据元素
组成数据的基本单位就是数据元素
例如
学号
姓名
性别
出生日期
政治面貌
0001
张三
男
20020514
团员
0002
李四
男
20030604
团员
0003
王五
男
20040507
团员
每一行就是一个数据元素,或者称为记录,节点或顶点
数据项
组成数据元素的不可分割的最小单位
例如上面的表中每一列就是一个数据项
数据 >数据元素>数据项
学生表>个人纪录>学号,姓名·····
3.数据对象
是性质相同的数据元素的集合,是数据的一个子集
例如整数的数据对象是集合N={1,2,3··}
4.数据对象与数据元素
数据元素 ------ 组成数据的基本单位
与数据的关系: 是集合的个体
数据对象 ----- 性质相同的数据元素 的集合
与数据的关系是:集合的子集
5.数据结构
数据结构
数据元素不是孤立存在的,他们 ...