数据结构与算法总结。[转]数据结构(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),但需要的拉空间大于堆排序方法,但由并排序方法是政通人和的排序方法。
以上排序方法都是经记录关键码的较和笔录之位移来展开排序.

貌似情形下,排序都利用顺序存储结构(基数排序方法除外),而当记录非常多时可运用链式存储结构,但高速排序和堆排序却坏不便在链表上实现。

相关文章