数据结构与算法总结。[转]数据结构(C#版)概念整理。

一:绪论

代表时间复杂度的阶有:

O(1) :常量时间阶段

O (n):线性时间等

O(㏒n) :对数时间等

O(n㏒n) :线性对数时间阶段

O (nk): k≥2 ,k次方时间等

以下六种计算算法时间的多项式是无比常用之。其涉嫌吗:

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指数日之关联呢:

O(2n)<O(n!)<O(nn)

 

算法的空间复杂度定义为:S(n) = O(g(n))

意味着随着问题规模 n 的附加,算法运行所需要贮存量S(n)的增长率和 g(n)
的增长率相同,称S(n)(渐近)空间复杂度。

        

第一章

二:线性表

顺序线性表:

若于线性表L中之第i只要素之前插入结点的票房价值为Pi,不错过一般性,设各个岗位插入是相等概率,则Pi=1/(n+1),而插入入常走结点的次数为n-i+1。

毕竟的平均移动次数: Einsert=∑pi*(n-i+1)  (1≦i≦n)

∴ Einsert=n/2 。

链式线性表:

单链表:

条例2.1假要下有限个线性表LA和LB分别代表两单集合A和B,现要求一个初的集合A=A∪B。

算法思想:1、扩大La,将有吃Lb中使未存于La中的数目元素插入到La中错过。2、需要由Lb中相继获得每个数据元素,并依值在La中进行明查暗访,若不存,则插 之。

规章2.3
已知线性表LA和LB中之数元素是随值非递减有序排列,现要求以LA和LB归并也一个新的线性表LC,且LC中之多少元素也是比照值非递减有序排列。

1.初始化 LC 为空表;

2.分别由 LA和LB中取得时因素 ai 和 bj;

3.若 ai≤bj,则将 ai 插入到 LC 中,否则将bj 插入到 LC 中;

4.重复 2 以及 3 两步,直至 LA 或 LB 中元素于拿走完为止;

5.用 LA 表或 LB 表中剩余元素复制插入到LC 表中。

(双向)循环链表:

横瑟夫问题:

n 个人围成一个圆形,首先第1私房自1发端一个人一个人顺时针报数, 
报及第m个体,令该出列。然后再次打下一个丁初步,从1顺时针报数,报及第m私家,再教其
         出列,…,如此下来,  直到圆圈中仅仅留一个人了。此人就是为优胜者。

例如  n = 8   m = 3

 

1、数据(Data)

其三:栈和排

括号匹配的检:(栈)

借用而于表达式中允许包含两栽括号:圆括号与方括号,其嵌套的次第随意,即:

([]())或[([ ][ ])]等呢对的格式,

[( ])或([( ))或 (()])均为免得法的格式。

尽管如此 检验括号是否配合的艺术可用“要的迫切程度”这个概念来描述。

算法设计:

1)  凡出现左括弧,则进栈;

2)  凡出现右括弧,首先检查栈是否空

假使栈空,则表明该“右括弧”多余,

   否则和栈顶元素于,

     若相匹配,则“左括弧出栈” ,

     否则表明无匹配。

3)表达式检验完毕时,

   若栈空,则表明表达式中匹配正确,

   否则表明“左括弧”有余。

 

表达式求值:(栈)

迷宫求解:(栈)

请求迷宫路径算法的着力思想是:从进口出发,按某平等在于朝非走过的前沿探索

若果当前职“可通”,则纳入路径,继续进步

如果当前职务“不可通”,则退步,换方向持续追究;

设若四周“均无通路”,则拿眼前岗位于路径中删去出去。

 

                            算法:

设定当前位置的初值为进口位置;

 do{

   若当前岗位可通,

   则{将目前职务插入栈顶;

           若该位置是出口位置,则算法结束;           

           否则切换时位置的东邻方块为

                   新的当前职务;

   }

   否则 {

   }

}while (栈不空);

而栈不空都栈顶位置还有其它可行性无让追究,

虽设定新的时职务吗: 沿顺时针方向旋转

            找到的栈顶位置的下同样互相邻块;

只要栈不拖欠但栈顶位置的方圆皆不可通,

则{删去栈顶位置;// 从路径中去该通道块                  

        若栈不拖欠,则又测试新的栈顶位置,

        直至找到一个可通的互相邻块或出栈至栈空;

假使栈空,则表明迷宫没有通路。

 

 

仓库的另外一个重中之重之应用:递归调用

就此分治法求解递归问题:

划分治法:对于一个较为复杂的问题,能够说明成几单相对简单的还解法相同或相近的子问题来求解

老三独标准化:

1、能以一个问题变更成一个初题材,而新题材和本问题之解法相同或相近以及,不同的唯有是拍卖的对象,且这些处理目标是转变来规律的

 

2、可以由此上述转化而要问题简化

 

3、必须有一个阳的递归出口,或称递归的疆界

 

分治法求解递归问题算法的相似式:

     void   p (参数表) {

        if   (递归结束条件)可直接求解步骤;—–基本项

        else  p(较小的参数);——归纳宗

       }

long Fact ( long n ) {

    if ( n == 0) return 1;  //基本项

    else return n * Fact (n1);  //归纳项}

数是表面世界信息的载体,它能吃电脑识别、存储和加工处理,是电脑程序加工之原材料。计算机程序处理各种各样的数量,可以是数值数据,如整数、实数或复数;也可以是非数值数据,如字符、文字、图形、图像、声音等。

四:串

 

 简单字符串模式匹配算法(BF算法):

算法思想:从主串S的第pos只字符起和模式串T的率先独字符比较的,若当,则继续于累字符;否则从主串的生一个字符起再另行与模式之字符比较的。依此类推,直至模式T中的每个字符依次和主串S中之一个老是的字符序列相等,则称匹配成功,函数值为同模式T中首先只字符相等的字符在主串S中序号,否则称匹配不成事,函数值为零星。

首尾字符串匹配算法:

先比较模式串的第一独字符

更于模式串的末段一个字符

末尾比较模式串中于第二只至第n-1独字符

 

Kmp算法:(难理解):复杂度o(m+n)

若设目标串(主串)为s,模式串为p
,并设i指针和j指针分别指示目标串和模式串中正待比较的字符,设i和j的初值均为1。若有si=tj,则i和j分别加1。否则,i不变,j退回到j=next[j]的职,再于si和tj,若当,则i和j分别加1。否则,i不变,j再次退到j=next[j]的位置,依此类推,直至下列两种植可能:

     
一种是j退及有next[…]不时字符比较等,则指针各自增1,继续开展匹配;

    
另一样种是j退至价值也零星(即模式的首先独字符“失配),则这欲用模式延续朝右侧滑动一个岗位,即于主串的一个字符si+1打和模式还开始匹配。

 

2、数据元素(Data Element)和数目项(Data Item)

五:数组和广义表:

勤组,广义表是线性表的放;

异常矩阵:

针对如矩阵:

上三角:

下三角:

 

对比赛矩阵:本着竞赛矩阵可按行优先顺序或针对角线的逐条,将该缩减存储到

一维数组中,且也能找到每个非零元素和向量下标的对应关系。

疏散矩阵:

疏散因子:m行n列t个非零元素

 

 

顺序存储:三元组(行数,列数,元素值)

转置:

算法的主导考虑:第一不行打转置前稀疏矩阵source中取出应该放置到转置后底稀疏矩阵dest中率先个职务的因素,行列号互换后,放于dest中首先只位置;第二次等由source中选取应该放开dest中之老二个职务的因素,……,如此进行,依次生成dest中之各要素。

办法同样:按m的列序转置

遵循T.data中三首组次序依次在M.data中找到相应的老三长组进行转置,即准矩阵M的列序来展开置换。

呢找到M中每一样排有非零元素,需对该三最先组表M.data从第一尽由扫描一全套。由于M.data中因M行序为主序,所以经获得的正是T.data中应之逐条。

法二:快速转置

按部就班M.data中三头版组次序转置,转置结果放入T.data中合适位置。

本法关键是如预先确定M中每一样排第一独非零元在T.data中职,为确定这些职务,转置前答应先求得M的各个一样排着无零元个数。

链式存储:十字链表

 

 

 

广义表:(人工智能):

广义表可以看成是线性表的推广,线性表是广义表的特例。广义表的结构相当灵活,在某种前提下,它好兼容线性表、数组、树和生于图等各种常用的数据结构。

A=(),B=(x, y, z),C=(B, y, z),D=(x,(y, z)),E=(x, E)

 

 

数元素是多少的骨干单位,在电脑程序中一般被用作一个总体进行考虑同处理。数据元素有时也深受喻为元素、结点、顶点、记录等。一个多少元素而由于几独数据项(Data
Item)组成。数据项是不可分割的、含有独立意义的最小数目单位,数据项有时也叫字段(Field)或域(Domain)。数据项分为片种植,一种植叫做初等项,另一样种叫做组合项。

六:树和二叉树

二叉树的性质:

  1. 于二叉树第i层及多起2i-1个结点
  2. 深度也k的二叉树到多来2k-1个结点
  3. 对此其它一样颗二交叉树,如果那叶子数为n0,度为2底结点数为n2,则n0=n2+1
  4. 不无n个结点的通通二叉树的深度为(log2n)+1

载二叉树的概念:

依傍平:若二交叉树被不过多单发生尽下零星叠产生度仅次于2之结点,且最好下层之结点都一一排列在极端左边,则称之二叉树为全二叉树。

宪章二:深度为k的二叉树,若第1到第k-1层为深也k-1的盈二叉树,第k交汇的结点都依次排于尽左边,则称这二叉树为完全二叉树。

 

二叉树的贮存:

         顺序:适合满二叉树和了二叉树

         链式:二叉链表,三交链表

特性:n个结点,有n+1独空指针域

二叉树的遍历:前序遍历,中序遍历,后序遍历(前中后是负根结点)

         实现:递归方法

                            非递归方法:用栈

 

         已解前序遍历和后序遍历不克告来二叉树

 

头脑二叉树:

         目的:非线性结构 –> 线性结构

         先先后线索二叉树

         中程序线索二叉树

         后续线索二叉树

 

陶铸的囤积:

         双亲表示拟

         孩子表示法

         孩子兄弟表示拟(常用)

 

树转二叉树:兄弟相连留长子

         特点:其右子树得也空

 

二叉树变树:左孩右右连大人,去丢原来右孩线

 

丛林变二叉树:树变二叉绝望相并

 

二叉树变森林:失丢所有右手孩线,孤立二叉再过来

 

树的遍历与二叉树遍历对应之关联:

 

造:先序遍历,后序遍历

老林:先序遍历,中序遍历

二叉树:先序遍历,中序遍历

 

Haffman树与Haffman编码:

         Haffman树最优树:带权路径长度(WPL)最缺少的栽培

         Haffman最优良二叉树:WPL最缺的二叉树

 

         构造Haffman树:7 5 5 2 4

        

         Haffman编码:根据字符出现频率编码,使电文总长度最缺少

 

         两个问题:

n个结点经n-1蹩脚联合,每次酷成新的结点,总共
n+n-1=2n-1独结点,度也2底结点个数为n-1

 

无度过为1之结点

 

 

3、数据对象(Data Object)

七:图

         无向图边的取值范围:0<=e<=n(n-1)/2

         有于图弧的取值范围:0<=e<=n(n-1)

 

         稀疏图:边数或弧数远点儿nlogn

         连通:随便为图备受,顶点到终极之间来路

        

 

        
贪图的生成树:一个连通图(无向图),生成树是一个最小连通子图,有图中全部n个顶点,n-1条边

 

         对于非连通图,每个连分量可以组织一粒很成树,从而结成森林

        
希冀结合森林:由几蔸有往培训组成,会出图中全部顶点,但一味发足构成若干棵不交的有向树的弧

 

         贪图的囤:邻接矩阵,邻接链表,十许链表,邻接多重表,边表

 

         起于图的邻接矩阵:终端的度 = 第i行元素之同 +
第j排元素之和

 

         无向树的邻接矩阵:极限的度 = 第i行的元素 1 的个数

 

                   优点:容易实现图的操作 
缺点:空间效率也o(n2

 

                   邻接表:效率o(n+e)

 

祈求的遍历:

         深度优先DFS:(Depth_First Search)

                   基本思维:仿树的中序遍历,分连通图和非连通图两类

         广度优先BFS:(Breadth First Search)

                   基本思想:仿树的层系遍历

 

         祈求的最小生成树

                  
生成树的代价:要并通图是一个带权图,则该生成树中的界限也带权,生成树中具备边的权值之同称生成树的代价

                   尽小生成树MST(Minimun Spanning
Tree):
带权连通图中代价最小之生成树

 

                   布局最小生成树的艺术:

①   Prim算法(以极为目标),时间复杂度o(n2),适合稠密图

②   Kruskal算法(以边也对象),时间复杂度o(eloge),适合稀疏图

在意:最小生成树可能不唯

         生往无环图及其应用:

                   有向无环图DAG:(Directed Acycling Graph)

                   拓扑排序:

①   在生于图选一个尚无前人的终极且输出 (入度为0)

②   从图备受除去该终端及它的备尾

③   重复以上两步

 

AOV网:顶表示活动之网(Activity On Vertex
network),不同意有回路,弧表示活动之间的预先制约关系

检测AOV中是否在环:网中负有终端拓扑有序序列(拓扑序列不是绝无仅有的)

 

 

 

         要害路径:(Critical Path)

AOE网(Activity On Eage
network):
极表示时间,弧表示活动,权表示活动高潮迭起的时

        

要活动:该边上的权值增加将如出向图及之无限丰富路长度增加,l(i)=e(i)

 

摸索关键路径:必须找到关键活动

①   向前递推

②   向后递推

③   把l(i)=e(i)的途径连起来

 

 

         极致差路径(Short Path):交通网络问题

 

                   分两种:单源点最缺乏路径,所有终端最缺路径

 

                   单源点最缺路径:

 

办法一致:将源点到终端所有路径列出来,选最短缺的。缺点:随路径的增,效率会减低

                           
方法二:Dijkstra算法:随路径长度递增次序来各顶的极致差路径

 

                  每一样针对终极间极短缺路径:

                           
方法一致:以一个极端为源点,重复执行Dijkstra算法N次,T(n)=o(n3)

                            方法二:Floyd算法:

想:逐个顶点试探,从vi到vj的装有或存在路线中,选出一长达长最缺的

                                     实现:

(1)初始时设置一个n阶方阵,令该针对性角线元素也0,若在弧<Vi,Vj>,则指向应元素为权值,否则也∞。

(2)逐步摸索着以本一直途径中增中顶点,若在中间点后路径变短,则改的;否则,维持原值。

(3)所有终端试探完毕,算法结束。      

 

 

数量对象是性质相同之数元素的集纳,是数码的一个子集。

八:查找

4、数据类型(Data Type)

静态表查找

平均查找长度ASL:(Average Search
Length):
为确定记录在表中的职,需要跟吃定值进行较根本字之个数的希望值

品标准:ASL

逐查找:(顺序或链式)

思维:从表中最后一个记下开始,逐个进行记录之根本字和被定值的比较,若有记录之重要性字与叫定值比较等,则寻成功,否则查找无成事。

 

亏本半追寻:(顺序)

                   效率比顺序查找高

 

 

数据类型是高等程序设计语言中之概念,是数码的取值范围及针对性数码开展操作的总数。数据类型可分为两类:一类是匪组织的原子类型,如C#语言中的中心类型(整型、实型、字符型等);另一样接近是组织类型,它的成份可由多单结构类型组成,并得以说明。结构类型的分可以是非结构的,也足以是布局的。

动态查找表

存重大字也key的笔录,则归,否则插入

 

二叉排序树:(二叉查找树)

特点:

        i.   左子树有节点<根节点

       ii.   右子树有节点>根节点

       iii.   左右子树分别是二叉排序树

算法:

①   查找

②   插入:插入位置由查找过程获得

③   删除:(分三种状况,定则:保持着先后序列不更换)

a)   *p为叶子节点,只待修改*P双亲*f的指针

b)   *P只有左子树要右子树

             i.  只来左子树:用*P的左孩子代替*p

             ii.   只发生右子树:用*p的右边孩子代替*p

c)         *p左右子树非空

         i.     用*P的直前驱取代*p

         ii.    用*p的第一手后继取代*p

         iii.    若*p的左子树无右子树,用*p左子树取代*p

 

蕴含 n 个结点的二叉去掉序树的平分查找长度以及培育的相有关 

最好好状态: ASL=log 2(n + 1) – 1;   
             树的吃水为:log 2n  + 1;  
             与折半查找吃之判断树相同。
           (形态于均衡)。 

极端充分情况:插入的 n 个要素于同开始就是不变,

            —— 变成单支树的貌!

            此时养之纵深为 n;   ASL = (n + 1) / 2  

             查找效率及各个查找情况一样。

                  

 

抵二叉树(AVL树):

性质:

①   左右子树是平衡二叉树

②   所有节点的左右子树深度的差之绝对值小于等于1

 

节点平衡因子:该节点左子树及右子树的纵深不同

 

组织平衡二叉树:

         LL平衡旋转:(B为轴,顺时针旋转)

                    RR平衡旋转:(B为轴,逆时针转动)

                    LR平衡旋转:(c为轴,先逆时针转动,后顺时针旋转)

                    RL平衡旋转:(c为轴,先顺时针旋转,后逆时针旋转)

 

B-树:

 

 B+树:

 

 

  散列表:

 特点:ASL=0,不欲经过比

 

哈希表:根据设定的哈希函数H(key)和所选中的处理闯的法门成立的查找表

 

合计:以记录之最主要字也自变量,根据哈希函数计算产生相应的哈希地址,并以这存储该记录之情节

 

组织哈希函数的不二法门:

本着数字:直接定值法,数字分析法,随机数法

平方取中法(常用),折叠法,除留与余数法(最常用H(key)=key MOD p
p<=m,p为<m的素数或无含20因为下质因子的合数)

未数字:先进行数字化处理

 

处理冲突的计:

①   开放定址法:当发生冲突,在冲位置前后附近搜索可存放记录之空余单元

H0=H(key)

Hi=(H(key)+di) MOD m i=1,2….

Di有三种植模拟:

a)  线性探测再散列  ,di = 1,2,….

b)  二软探测再散列(平方),di = 12 -12
22 -22

c)  为擅自探测再散列(双散列函数探测再散列)

 i.  Di=伪随机数列 或者 di = i×H2(key)

②  链地址开方法(开域法):将富有哈希值相同的记录还总是于一如既往链表中

 

 

 

5、数据结构(Data Structure爱博体育)

九:排序

品标准:执行时间,辅助空间,算法稳定性

 

里排序:

①   插入排序

a) 直接插入排序

b) 希尔排序

  i.  
 思想:将尽待排序记录分割成多少个头序列,在子序列内分别展开直接插入排序,待全部序列中的记录基本平稳时,对合记录进行直接插入排序。

②   交换排序

a)  冒泡排序

b)  快速排序

 i. 思想:
首先选择一个轴值(即于的规范),通过一致回排序将用排序记录分割成单身的少局部,前一部分笔录的重中之重码均小于或顶轴值,后同样片记录的重要码均大于或当轴值,然后分别对当下半组成部分重新上述方法,直到一切序列有序。

③   分选排序

a)简单选择排序(直接选择排序)

b)堆排序(改进:查找最小码的而,找来比小价,分大根堆,小根堆)

④   由并排序

a)
二路程归并排序:将一个具备n个待排序记录的队看成是n个长也1的有序序列,然后进行有限少由并,得到n/2个长也2底平稳序列,再进行个别零星由并,得到n/4只长也4之雷打不动序列,……,直至获得一个长短为n的有序序列为止。

⑤   基数排序

a) 多要字排序

  i.  最高位优先MSD法

  ii.  最低位优先MSD法

b) 链式基数排序

c)基数排序的光阴复杂度为O(d(2n+r))

其中:分配为O(n)

收集为O(n+r)(r为“基”)

 d为“分配-收集”的趟数

 

 

外表排序:外排总的年华还许诺包括中排序所需要时间以及逐趟归并时常开展内统一的岁月

 

讨论:

岁月复杂度:

①   平均时间性能:

a)时间复杂度为 O(nlogn):快速排序、堆排序和合排序

b) 时间复杂度为 O(n2):直接插入排序、起泡排序和简易选择排序

c)时间复杂度为 O(n):基数排序

②   排元素序列按重要性字顺序有序

a)  直接插入排序能达到O(n)的年华复杂度, 快速排序的流年性能蜕化为O(n2)

③   排序的岁月性能不以关键字分布而变更之排序

a)  
简单选择排序、起泡排序、堆排序和合并排序的时空性能不按照元素序列中重要性字的布而变更

 

安居乐业之排序方法指的凡,对片只基本点字等的元素,它们当队中之对立位置,在排序前与经排序之后,没有变动。

 

 

 

 

 

数据结构是并行有一样种植要多特定关系的多寡元素的集聚。在任何问题遭到,数据元素中还不是孤立的,而是有在自然的关系,这种关联称为组织(Structure)。根据数据元素中关系的例外特色,通常发生4类基本数据结构:
(1) 集合(Set);(2) 线性结构(Linear Structure);(3) 树形结构(Tree
Structure);(4) 图状结构(Graphic Structure)。

数据结构的形式化定义为: 数据结构(Data
Structure)简记为DS,是一个二元组, DS = (D,R)
其中:D是数量元素的鲜集合, R是数元素中涉及的片集合。

数据结构包括数据的逻辑结构及情理结构。数据的情理构造以称之为存储结构(Storage
Structure),是数码在计算机被的表示(又叫映像)和仓储,包括数据元素的象征与存储和数据元素中涉及的意味和储存。

多少的囤积结构包括顺序存储结构与链式存储结构简单种植。顺序存储结构(Sequence
Storage
Structure)是通过数量元素以处理器存储器中之对立位置来表示出数元素的逻辑关系,一般将逻辑上紧邻的数目元素存储在大体位置紧邻之存储单元中。在C#语言中之所以数组来兑现顺序存储结构。因为数组所分配的积存空间是连接的,所以数组天生就颇具实现数据顺序存储结构的能力。链式存储结构(Linked
Storage
Structure)对逻辑上紧邻的多寡元素不求该储存位置要相邻。链式存储结构被的数量元素称为结点(Node),在结点中附设地址域(Address
Domain)来囤积和拖欠结点相邻之结点的地点来贯彻结点间的逻辑关系。这个地址称为引用(Reference),这个地址域称为引用域(Reference
Domain)。

  1. 算法

打上节咱们解,算法和数据结构和顺序的干很细心。进行次设计时,先确定相应的数据结构,然后又依据数据结构和问题之急需规划相应的算法。由于篇幅所限,下面仅于算法的特色、算法的评论标准与算法的光阴复杂度等三独面展开介绍。

1.2.1算法的性状

算法(Algorithm)是针对性某平等特定项目的问题之求解步骤的一样种植描述,是命令的一定量序列。其中的诸条指令表示一个要多个操作。一个算法应该享有以下5单特点:

1)、有穷性(Finity):一个算法总是以尽有穷步之后了,即算法的实行时间是少数的。

2)、确定性(Unambiguousness):算法的各级一个步骤都必须发方便的义,即无二义,并且对同一的输入只能发出一致之出口。

3)、输入(Input):一个算法有零个或多独输入。它就凡以算法开始之前为有底量。这些输入是某数据结构中之多寡对象。

4)、
输出(Output):一个算法有一个或多只出口,并且这些输出以及输入之间有着某种特定的涉。

5)、
能行性(realizability):算法中的各个一样步都得以透过就落实之中坚运算的鲜次运行来实现。

算法的义和程序非常相像,但彼此有分别。一个序不必然满足来穷性。例如操作系统,只要尽系统非面临毁损,它将永生永世不见面停止。还有,一个程序只能用电脑语言来讲述,也就是说,程序中的授命须是机器而实行之,而算法不自然用电脑语言来描述,自然语言、框图、伪代码都可以描述算法。

  1. 算法的时刻复杂度

一个算法的工夫复杂度(Time
Complexity)是依靠该算法的运行时和问题规模之呼应关系。一个算法是由于控制结构和本操作成的,其实行的流年在双方的概括力量。

  1. 聚拢的概念

汇聚(Set)是由于片确定的、彼此不同之分子(Member)或者元素(Element)构成的一个完好。成员取得自一个再次老的限,称为基类型(Base
Type)。集合中成员的个数称为集合的基数(Cardinality)。集合的每个成员要么是基类型的一个主干元素(Base
Element),或者它自己吗是一个集。我们把是集结的分子称该集的子集(Subset),子集中的每个成员都属该集。没有元素的集合称为空集(Empty
Set,又称作Null Set),记作Φ。

集的特性

1) 确定性:任何一个对象还能够吃正好地判定是汇中之元素或无是;

2) 互异性:集合中的因素不克更;

3) 无序性:集合中元素与各个无关。

  1. 递归

一个算法调用自己来成功她的组成部分工作,在缓解某些问题经常,一个算法需要调用自身。如果一个算法一直调用自己还是间接地调用自己,就如这算法是递归的(Recursive)。根据调用方式的例外,它分为直接递归(Direct
Recursion)和间接递归(Indirect Recursion)。

  1. 接口

1)、 接口的概念

接口(Interface)定义也一个预定,实现接口的接近或结构必须遵从该约定。简单的游说,接口是相仿中彼此时严守的一个商讨。这种将一个对象看成多独品类的力量一般如作多延续(Multiple
Inheritance)。通用语言运行时(CLR)支持但实现持续与多接口继承。单实现连续(Single
Implementation
Inheritance)是依赖一个路只能有一个基类型。多接口继承(Multiple Interface
Inheritance)是借助一个型可以继承多只接口,而接口是近似中彼此交互的一个泛(Abstract),把看似中要彼此的情节空虚出来定义成接口,可以再好地控制类之间的逻辑交互。

接口就包含成员定义,不包含成员的兑现。接口不见面延续自任何的System.Object派生类型。接口就是一个暗含在相同组虚方法的悬空类型。成员的兑现需要在延续的切近还是组织中贯彻。接口的积极分子包括静态方法、索引器、常数、事件与静态构造器等,不含有其他实例字段或实例构造器,所以,不可知实例化一个接口。
实现接口的近乎必须从严遵照该定义来促成接口的每个成员。

  1. 接口及抽象类

抽象类(Abstract
Class)和接口在概念跟功力上闹很多相似的地方,在程序中选择以抽象类或接口需要比抽象类和接口之间的切实可行差异。
抽象类是如出一辙种植不能够实例化而得从中继承的近乎,抽象类可以提供实现,也得不提供实现。子类只能打一个抽象类继承。抽象类应着重用以关系密切的靶子。如果假定规划非常的效益单元或创造组件的几近独版,则利用抽象类。
接口是全空虚的成员会合,不提供实现。类或组织得以继续多只接口。接口最契合呢非相干的近乎提供通用功能。如果要是统筹有些而略的功能块,则采取接口。接口一旦创立就无克转,如果需要接口的初本子,必须创造一个新的接口。

  1. 泛型编程

泛型(Generic Type)是.NET Framework
2.0尽强大的效益。泛型的主要考虑就是以算法和数据结构完全分离开来,使得一样浅定义的算法能够作用被多数据结构,从而实现高度可选用的支付。通过泛型可以定义类型安全之数据结构,而无必要运用实际的数据类型。这将明了增长性并获更胜质量的代码,因为好用数据处理算法,而并未必要复制类型特定的代码。

(1) 性能问题。(2) 类型安全。(3) 工作效率。

  1. 泛型的补益

泛型使代码可以用,类型和里数据好以无造成代码膨胀的情下转,而无论是是值类型还是引用类型。可以一次性地出、测试和配备代码,通过另外项目(包括前的类)来再用它,并且布满具编译器支持与种类安全。因为泛型代码不见面粗暴对值类型进行装箱和注销装箱,或者对援类型进行向下强制类型转换,所以性能得到明确提高。对于值类型,性能一般会提高200%;对于引用类型,在拜访该档时,可以预期性最多加强100%(当然,整个应用程序的习性可能会见加强,也恐怕未见面提高)。

第2章

  1. 线性表

线性表是无限简便、最中心、最常用的数据结构。线性表是线性结构的纸上谈兵(Abstract),线性结构的性状是构造中之数元素中有相当底线性关系。这种一对一的涉因的是数额元素中的位置关系,即:(1)除第一独岗位的多寡元素外,其它数据元素位置的面前都只发生一个数量元素;(2)除最后一个位置的数元素外,其它数据元素位置的背后都仅仅出一个因素。也就是说,数据元素是一个连一个之排。因此,可以管线性表想象为同一种植多少元素序列的数据结构。

  1. 线性表的定义

线性表(List)是由于n(n≥0)个同类别的多寡元素构成的少数序列。对于此概念应该注意少单概念:一凡是“有限”,指的是线性表中的数目元素的个数是零星的,线性表中的每一个数据元素还出自己之位置(Position)。二凡是“相同类别”,指的是线性表中的数量元素还属于同一栽档次。

  1. 顺序表的概念

每当电脑内,保存线性表最简便易行、最本之章程,就是拿表中的因素一个连缀一个地加大上顺序的存储单元,这虽是线性表的顺序存储(Sequence
Storage)。线性表的顺序存储是负在内存中用一片地方连续的上空依次存放线性表的多少元素,用这种艺术囤的线性表叫顺序表(Sequence
List),顺序表的风味是表中相邻的数量元素于内存中贮存位置为紧邻。

  1. 链式存储 (Linked Storage)

然的线性表叫链表(Linked
List)。链表不要求逻辑上附近之数据元素以物理存储位置上吧紧邻,因此,在对链表进行插队和去时未欲活动多少元素,但又也错过了逐条表而随便存储的优点。

  1. 链表

举凡用平等组随机的存储单元来存储线性表中的数量元素(这组存储单元可以是接二连三的,也可以是无连续的)。

区区片段信息整合该数据元素的储存映像(Image),称为结点(Node)。把仓储据元素本身信息的域叫结点的数据域(Data
Domain),把仓储和它附近之数码元素的囤积地点信息的域叫结点的引用域(Reference
Domain)。因此,线性表经过每个结点的引用域形成了平等绝望“链条”,这即是“链表”名称的由来。

假使结点的引用域只存储该结点直接后继结点的囤积地点,则该链表叫单链表(Singly
Linked List)。

其三节 栈和班

仓库和行是生关键之鲜种多少结构,在软件设计中运用很多。栈和行也是线性结构,线性表、栈和排这三栽多少结构的数据元素和数元素中的逻辑关系完全相同,差别是线性表的操作不让限制,而仓库和班的操作着限制。栈的操作只能在表的同等端进行,队列的插入操作在表的平等端进行而其他操作在表的另外一样端进行,所以,把仓库和班称为操作受限的线性表。

栈分为顺序栈和链栈。顺序栈用数组表示,链栈使用单链来表示,是单链的同样种植简化。

  1. 队列

班(Queue)是插操作限定在表的尾巴而另操作限定在表的头颅进行的线性表。把开展扦插操作的表尾称为队尾(Rear),把开展其它操作的脑壳称为队头(Front)。当对列中绝非数元素时称空对列(Empty
Queue)。

排通常记为:Q=
(a1,a2,…,an),Q是英文单词queue的第1单字母。a1啊帮头元素,an为队尾元素。这n个元素是本a1,a2,…,an的次序依次入队的,出对的次序与入队相同,a1首先单出队,an最后一个出队。所以,对列的操作是准先进先出(First
In First Out)或后迈入后发( Last In Last
Out)的标准化进行的,因此,队列又叫做FIFO表或LILO表.

看清队空的口径是:rear==front,判断队满的标准是:(rear + 1) %
maxsize==front。求循环队列中数据元素的个数可由于(rear-front+maxsize)%maxsize公式求得。

队尾指示器的加1操作修改也: rear = (rear + 1) % maxsize

队头指示器的加1操作修改也: front = (front + 1) % maxsize

2.1链队列

列的另外一栽存储方是链式存储,这样的班称为链队列(Linked
Queue)。同链栈一样,链队列通常用单链表来代表,它的贯彻是只有链表的简化。所以,链队排的结点的结构和单链表一样.

二叉树(Binary
Tree)是n(n≥0)个一样档次的结点的点滴集合。n=0的二叉树称为空二叉树(Empty
Binary Tree);对于n>0的自由非空二叉树起:

(1)有且只来一个例外的结点称为二叉树的彻底(Root)结点,根没有前人结点;

(2)若n>1,则除外根结点外,其余结点被分成了2单互不相交的集合TL,TR,而TL、TR我还要是一律株二立交树,分别叫这棵二叉树的左子树(Left
Subtree)和右子树(Right Subtree)。

(1)满二叉树(Full Binary
Tree):如果相同株二叉树只有度为0的结点和过为2的结点,并且度为0的结点在一如既往层及,则这株二交叉树也充满二叉树,对于深度也k的满二叉树的结点个数为2k-1。

(2)完全二叉树(Complete Binary
Tree):深度也k,有n个结点的二叉树当且仅当其列一个结点都同深也k,有n个结点的盈二叉树被编号从1顶n的结点一一对应时,称为了二叉树,完全二叉树的性状是纸牌结点只或出现在层次太特别的少重合及,并且有结点的左分支下子孙的最要命层次与右分支下子孙之顶可怜层次等或大1。

3.1二叉树的属性

性1 一蔸非空二叉树的第i重合及最多出2i-1个结点(i≥1)。

性能2
若规定空树的深也0,则深度也k的二叉树最多起2k-1个结点(k≥0)。

属性3 具有n个结点的通通二叉树的纵深k为log2n+1。

性4
对于同棵非空二叉树,如果度为0的结点数目也n0,度为2底结点数目也n2,则有n0=
n2+1。

特性5
对于持有n个结点的一心二叉树,如果以从上到下和从左到右的顺序对所有结点从1开编号,则于序号为i的结点,有:

(1)如果i>1,则序号为i的结点的养父母结点的序号为i/2(“/”表示整除);如果i=1,则该结点是根结点,无大人结点。

(2)如果2i≤n,则该结点的左孩子结点的序号为2i;若2i>n,则该结点无不当孩子。

(3)如果2i+1≤n,则该结点的右边孩子结点的序号为2i+1;若2i+1>n,则该结点无右孩子。

3.2 二立交树遍历

1、先序遍历(DLR)

先期先后遍历的主干考虑是:首先访问根结点,然后先序遍历其左子树,最后先序遍历其右子树。

2、中序遍历(LDR)

中序遍历的为主考虑是:首先被先后周历根结点的左子树,然后访问根结点,最后中序遍历其右子树。

3、后序遍历(LRD)

后先后遍历的骨干考虑是:首先后先后任何历根结点的左子树,然后后先后全勤历根结点的右子树,最后访问根结点。

4、层序遍历(Level Order)

层序遍历的核心思维是:由于层序遍历结点的顺序是事先碰到的结点先看,与队列操作的逐一相同。所以,在进行层序遍历时,设置一个序列,将根本结点引用入队,当排非空时,循环执行以下三步:

(1) 从队列中取出一个结点引用,并走访该结点;

(2) 若该结点的左子树非空,将欠结点的左子树引用入队;

(3) 若该结点的右子树非空,将该结点的右子树引用入队;

5.4哈夫曼树

5.4.1哈夫曼树的基本概念

先是给出定义哈夫曼树所要因此到之几只基本概念。

(1)路径(Path):从养被之一个结点到其他一个结点之间的子组成这有限个结点间的路。

(2)路径长度(Path Length):路径上的分支数。

(3)树的路子长度(Path Length of
Tree):从树的根结点到每个结点的途径长度的同。在结点数目相同之二叉树中,完全二叉树的门径长度最缺。

(4)结点的权(Weight of
Node):在一些用到被,赋予树中结点的一个生实际意义的再三。

(5)结点的带权路径长度(Weight Path Length of
Node):从该结点到培训之根结点的门径长度和该结点的且的积。

(6)树的带权路径长度(WPL):树被有所叶子结点的带权路径长度的同,记否

Σ==n1kk.kWPLLW

内部,Wk为第k单叶子结点的权值,Lk也第k只叶子结点的路线长度。在觊觎5.17(a)所出示之二叉树中,结点B的不二法门长度为1,结点C和D的途径长度也2,结点E、F和G的路径长度为3,结点H的门径长度为4,结点I的路长度为5。该树的门路长度也:1+2*2+3*3+4+5=23。如果结点B、C、D、E、F、G、H、I的权分别是1、2、3、4、5、6、7、8,则这些结点的带权路径长度分别是1*1、2*2、2*3、3*4、3*5、3*6、4*7、5*8,该树的带权路径长度为3*5+3*6+5*8=73。

那么,什么是哈夫曼树呢?

哈夫曼树(Huffman
Tree),又为最妙二交树,指的是对此同一组有确定权值的叶子结点的具备无比小带权路径长度的二叉树。

哈夫曼算法。现叙述如下:

(1)根据加的n个权值{w1,w2,…,wn},构造n棵只有根结点的二叉树集合F={T1,T2,…,Tn};

(2)从集合F中摘两棵根结点的权最小的二叉树作为左右子树,构造一蔸新的二叉树,且购置新的二叉树的根结点的权值为夫荒谬、右子树根结点权值之和。

(3)在集合F中删除这半蔸树,并拿新收获的二叉树加入到集合F中;

(4)重复上述手续,直到汇中不过出相同蔸二叉树为止,这株二立交树就是哈夫曼树。

树形结构是同一栽非常重大的非线性结构,树形结构面临的数量元素称为结点,它们中间是平等针对性几近之涉嫌,既来层次关系,又发出分关系。树形结构来栽培及二叉树两种。

塑造是递归定义的,树由一个根结点和多少株互不相交的子树构成,每株子树的结构和塑造相同,通常树指无序树。树的逻辑表示日常有四栽方法,即直观表示拟、凹入表示法、广义表表示法和嵌套表示法。树之仓储方来3栽,即上下表示拟、孩子链表表示法与儿女兄弟表示法。

二叉树的概念也是递归的,二叉树由一个根结点和少数蔸互不相交的子树构成,每棵子树的组织以及二叉树相同,通常二叉树指有序树。重要之二叉树起满二叉树和全二叉树。二叉树的性要发生5长。二叉树的之仓储结构要出三栽:顺序存储结构、二叉链表存储结构和三叉链表存储结构,本书给有了第二立交链表存储结构的C#兑现。二叉树的遍历方式一般发生四种植:先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD)和层序遍历(Level
Order)。

森林是m(m≥0)棵树的集合。树、森林和二叉树的内可以拓展互动转换。树的遍历方式产生先先后遍历和后序遍历两栽,森林的遍历方式有先先后遍历和中序遍历两种。

哈夫曼树是一样组有确定权值的叶子结点的富有无比小带权路径长度的二叉树。哈夫曼树可用于解决最优化问题,在数据通信等领域使用非常宽泛。

1、直观表示拟

它象日常生活中之花木一样。整个图就是象一蔸倒立的养,从根结点出发不断扩展,根结点在太上层,叶子结点于极其下面。

2、凹入表示法

每个结点对应一个矩形,所有结点的矩形都右对联合,根结点用最为丰富的矩形表示,同一层的结点的矩形长度相同,层次越强,矩形长度逾短。

3、广义表表示法

据此广义表的样式表示根结点排在极端前面,用同针对圆括号将它的子树结点括起,来,子树结点用逗号隔开。树的广义表表示如下:

(A(B(E,F,G),C(H),D(I,J)))

4、嵌套代表拟

看似数学中所说之文氏图表示法。

6 图

图状结构简称图,是任何一样栽非线性结构,它于树形结构还扑朔迷离。树形结构中的结点是同样对几近之涉嫌,结点间所有明显的层次和支行关系。每一样交汇的结点可以与下一致重叠的几近个结点相关,但不得不和及同层的一个结点相关。而贪图备受之极端(把图被的数目元素称为顶点)是多针对性几近的关系,即到点间的涉是任意的,图中任意两独极之间还可能系。也就是说,图的顶点之间无明显的层系关系,这种关涉在现实世界面临大量存。

是因为最小生成树的定义可知,构造出n个顶点的无论是为连通网的极其小生成树必须满足以下三个规格:

(1)构造的极度小生成树必须概括n个顶点;

(2)构造的不过小生成树出且只有来n-1条边;

(3)构造的最好小生成树中无存回路。

结构最小生成树的法子有无数种,典型的办法来三三两两栽,一种植是普里姆(Prim)算法,一种是克鲁斯卡尔(Kruskal)算法。

2.普里姆(Prim)算法

比方G=(V,E)为平无向连通网,其中,V为网中极的会师,E为网中边的会师。设置两独新的集合U和T,其中,U为G的极致小生成树的极限的聚集,T为G的最小生成树的限的集结。普里姆算法的思想是:令集合U的初值为U={u1}(假设构造最小生成树时从顶点u1方始),集合T的初值为T={}。从所有的顶点u∈U和终点v∈V-U的带权边吃选出具有极其小权值的限(u,v),将顶点v加入集合U中,将限(u,v)加入集合T中。如此不断地重直到U=V时,最小生成树构造完毕。此时,集合U中存放着最为小生成树的富有终端,集合T中存放着最小生成树的具备边。

3.克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔算法的主导思想是:对一个发n个顶点的无向连通网,将图被之底限按权值大小顺序选择,若选择的限度设生成树不形成回路,则把她加入到树被;若形成回路,则将它们舍弃。如此进行下去,直到树被保证含有n-1条边为止。

脚是拓扑排序算法的讲述:

(1)在起往图备受摘一个入度为0的终点(即没有前人的顶),由于该顶点没有其它先决条件,输出该终端;

(2)从图被除去所有以其吗尾的弧;

(3)重复执行(1)和(2),直到找不顶入度为0的终极,拓扑排序完成。

要是图中以有极限存在,却从不入度为0的极,说明AOV网中发生环路,否则没有环路。

由堆的概念可知,堆有如下两单属性:

(1)最充分堆的根结点是积着关键码最要命的结点,最小堆的根结点是积着关键码最小的结点,我们称堆的根结点记录也堆顶记录。

(2)对于极端充分堆,从根结点到每个叶子结点的门路上,结点组成的队都是递减有序的;对于极端小堆,从根结点到每个叶子结点的路子上,结点组成的序列都是与日俱增有序的。

堆排序的过程是:设有n个记录,首先将随即n个记录按关键码建成堆,将堆顶记录输出,得到n个记录着关键码最特别(或极端小)的记录。然后,再把剩余的n-1独记录,输出堆顶记录,得到n个记录中重点码次大(或不好稍)的记录。如此频繁,便可收获一个本重要性码有序的队列。

故,实现堆排序需解决个别单问题:

(1)如何用n个记录的排按关键码建成堆;

(2)输出堆顶记录后,怎样调整剩下的n-1只记录,使其按重要性码成为一个新堆。

排序是计算机程序设计被之一模一样种要操作,

化仍记录的某部关键码有序的阵的过程。排序方法以涉嫌的存储器不同分为内排序和外部排序两近似。内部排序指记录存放在内存中并且在内存中调整记录中的相对位置,没有外、外存的数据交换。外部

存中,借助于内存调整记录里的对立位置,需要在内、外存之间交换数据。排序方

政通人和排序方法在排序前后相同关键码值的笔录里的位置关系非移,不安宁排序方法在排序前后相同关键码值的笔录里的职务关系转移。本章主要介绍了常用之其中排序方法,包括三栽简单排序方法,即直接插入排序、冒泡排序和省略选择排序,这三种排序方法在极度好状态下之时空复杂度为O(n),在平均情况下和最好酷情况下之时刻复杂度都为O(n2),并且还是安静之排序方法。

快速排序方法的平分性最好好,时间复杂度为O(nlog2n),所以,当待排序序列已经随重要性码随机分布时,快速排序是无与伦比符合的。但快速排序在无限要命情况下之时复杂度是O(n2)。快速排序方法是勿稳定之排序方法

堆排序方法以极端好状态下、平均情况下及太老情况下之时光复杂度不会见发生变化,为O(nlog2n),并且所待的救助空间有限快速排序方法。堆排序方法也是匪稳定之排序方法。
归并排序方法在尽好状态下、平均情况下和极老情况下的辰复杂度不见面发生变化,为O(nlog2n),但待的扶持空间大于堆排序方法,但由并排序方法是政通人和的排序方法。
以上排序方法都是透过记录关键码的可比和笔录的移动来进行破序.

诚如情形下,排序都使顺序存储结构(基数排序方法除外),而当记录非常多时好下链式存储结构,但迅速排序和堆排序却生为难在链表上实现。

相关文章