数据结构与算法总结。[转]数据结构(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),但得之帮扶空间大于堆排序方法,但由并排序方法是稳定之排序方法。
以上排序方法还是经记录关键码的于和记录之走来拓展割除序.

相似情况下,排序都使用顺序存储结构(基数排序方法除外),而当记录非常多时得利用链式存储结构,但很快排序和堆排序却挺麻烦在链表上贯彻。

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注