数据结构知识点整理

1、数据 是信息的 体，是描述客 事物的数、字符、以及所有能 入到 算机中，被 算机程序 和 理的符号（数 、字符等）的集合。数据元素（数据成 ）是数据的基本 位。在不同的条件下，数据元素又可称 元素、 点、 点、 等数据 象 具有相同性 的数据元素（数据成 ）的集合数据 构 由某一数据 象及 象中所有数据成 之 的关系 成。 data_structure = d, r其中，据 象， r 是 象中所有数据成 之 的关系的有限集合。数据 型 是指一种 型，以及定 在 个 集合上的一 操作的 称。判断一个算法的 劣主要 准：正确性、可使用性、可 性、效率、健壮性、 性。算法效率的衡量方法：后期 ，事前

2、估 算法分析 是算法的 分析 称数据 构 包括“ 构”和“物理 构”两个方面( 次 ): 构是 数据成 之 的 关系的描述，它可以用一个数据成 的集合和定 在此集合上的若干关系来表示物理 构是 构在 算机中的表示和 ，故又称“存 构”d 是某一数 性表的定 ： n（ 3 0 ）个表 的有限序列l = （ a1,a2, ,an） ai 是表 ， n 是表 度。第一个表 是表 ，最后一个是表尾。 性表的特点 ：表中元素的数据 型相同； 性表中， 点和 点 的关系是一 一的，有序表和无序表 性表的存 方式。一， 序存 方式，二， 表存 方式。 序表的存 表示有2 种方式 ：静 方式和 方式。 序表的

3、定 是 ：把 性表中的所有表 按照其 序依次存 到从 算机存 中指定存 位置开始的一 的存 空 中。 序表的特点 ：用地址 的一 存 空 序存放各表 ，各表 的 序与物理 序一致， 各个表 可以 序 ，也可以随机 。 表 是一种最 的 表表示，也叫 性 表 ，用她来表示 性表 ，用指 表示 点 的 关系。特点：是 度可以很方便地 行 充。 存 方式（ 序表）特点：存 利用率高，存取速度快缺点：插入、 除等操作 需要移 大量数据： 式存 方式（ 表）特点 ：适 表的 增 和 除。缺点：需要 外的指 存 空 表的 定 ：多个 表达一个概念( 表 ) 。分 ： 表 点 ( listnode ) 类

4、， 表 ( list ) 。循 表的概念 ：是另一种形式的表示 性表的 表，它的 点 构与 表相同，与 表不同的是 表中表尾 点的 link 域中不是 null，而是存放了一个指向 表开始 点的指 ， ，只要知道表中任何一个 点的地址，就能遍 表中其他任何一 点。双向 表的概念 ：在双向 表的没 点中 有两个 接指 作 它的数据成 ：1link 指示它的前 点，rlink 指示它的后 点，因此，双向 表的每个 点至少有3 个域： 1link( 前 指 ) dada（数据） rlink （后 指 ） 。栈：定 只允 在表的末端 行插入和 除的 性表。特点是：后 先出。 的定 ：若一个 象部分地包

5、含它自己，或用它自己 自己定 , 称 个 象是 的；若一个 程直接地或 接地 用自己 , 称 个 程是 的 程。以下三种情况常常用到 方法一。定 是 的二。数据 构是 的三 的解法是 的。 列 ： 列是只允 在一端 除，在另一端插入的 序表允 除的一端叫做 ，允 插入的一端叫做 尾。特性：先 先出。 先 列 ：是不同于先 先出 列的另一种 列。每次从 列中取出的是具有最高 先 的元素。多 数 是一 数 的推广。多 数 是一 数 的推广。多 数 的特点是每一个数据元素可以有多个直接前 和多个直接后 。数 元素的下 一般具有固定的下界和上界，因此它比其他复 的非 性 构 。字符串 是 n ( 3

6、0 )个字符的有限序列， 作 s :“c1c2c3cn”其中，s 是串名字 c1c2c3cn”是串 ci是串中字符 n 是串的 度， n = 0称 空串。广 表 是 n ( 0 )个表元素 成的有限序列， 作ls ( a1, a2, a3, ,an) ， ls 是表名， ai 是表元素，可以是表（称 子表） ，可以是数据元素（称 原子） 。 n 表的 度。 n = 0的广 表 空表。n 0 ，表的第一个表元素称 广 表 的表 （ head），除此之外，其它表元素 成的表称 广 表的表尾（tail有根 ：一棵有根 t， 称 ，它是n ( n 0)个 点的有限集合。当n = 0 ， t 称 空 ；

7、否 ， t 是非空 ， 作 t= 空集 n=0r,t1,t2 .tn,n0r 是一个特定的称 根(root)的 点，它只有直接后 ，但没有直接前 ；根以外的其他 点划分 m( m 3 0)个互不相交的有限集合 t1, t2, , tm，每个集合又是一棵 ，并且称之 根的子 。每棵子 的根 点有且 有一个直接前 ，但可以有 0 个或多个直接后 二叉 的定 : 一棵二叉 是 点的一个有限集合， 集合或者 空，或者是由一个根 点加上两棵分 称 左子 和右子 的、互不相交的二叉 成。完全二叉 : 若 二叉 的深度 k， 共有 k 。除第 k 外，其它各 (1 k-1) 的 点数都达到最大个数，第 k

8、从右向左 缺若干 点， 就是完全二叉 二叉 的遍 就是按某种次序 中的 点，要求每个 点 一次且 一次。 根 点 作v 遍 根的左子 作 l 遍 根的右子 作r 。 可能的遍 次序有： 前序 vlr 像 vrl；中序 lvr 像 rvl；后序 lrv 镜像 rlv前序遍 二叉 算法的框架是：若二叉 空， 空操作；否 根 点(v) ；前序遍 左子 (l) ；前序遍 右子 (r) 。遍 果 - +a *b -c d /e f 的后根次序遍 : 当 非空 依次后根遍 根的各棵子 根 点： 后根遍 efbcgda； 二叉 中序遍 efbcgda； 的后根遍 果与其 二叉 。表示的中序遍 果相同： 的后

9、根遍 可以借助 二叉 的中序遍 算法 最小堆和最大堆： 如果有一个关 集合k=k0,k1 ，k2，k3， .,kn-1 ，把它的所有元素按完全二叉 的 序存 方式存放在一个一 数 中。并 足ki k2i+1 且 ki k2i+2( 或者 ki k2i+1且 kik2i+2 )i=0,1, . （ n-2 ） /2 ， 称 个集合 最小堆或最大堆。堆是最高效的一种数据 构，每次出 列的是 先 最高的元素。用堆 其存 表示，能 高效运作。堆的建立 ：有 2 种方式建立最小的堆，一种方式是通 第一个构造函数建立一个空堆，其大小通 存 分配得到，另一中建立最小堆的方式是通 第二个构造函数复制一个 数

10、并 其加以 整形成一个堆。路径 ：从 中一个 点到达另一个 点之 的分支构成 两 点之 的路径。路径 度： 是指路径上的分支条数， 的路径 度是从 的根 点到每一个 点的路径 度之和。由 的定 ，从根 点到达 中每一 点有且 有一条路径。huffman ： 路径 度最小的二叉 是 大的外 点离根 点最近的 充二叉 。 路径 度最小的 充二叉 不一定是完全二叉 。集合 是成 ( 元素 ) 的一个群集。集合中的成 可以是原子( 单元素 ) ，也可以是集合。字典 是一些元素的集合，每个元素有一个称作关 （key ）的域，不同元素的关 互不相同。散列方法： 理想的搜索方法是可以不 比 ，一次直接从字典

11、中得到要搜索的元素。如果在元素存 位置与其关 之 建立一个确定的 函数关系hash() ，使得每个关 与 构中一个唯一的存 位置相 ：addresshash(key) 。在插入 依此函数 算存 位置并按此位置存放。在搜索 元素的关 行同 的 算，把求得的函数 当做元素存 位置，在 构中按此位置搜索。 就是散列方法 。在散列方法中所用 函数叫做散列函数 。按此方法构造出来的表叫做散列表 。使用散列方法 行搜索不必 行多次关 的比 ,搜索速度比 快,可以直接到达或逼近具有此关 的表 的 存放地址。散列函数 是一个 映象函数。关 集合比散列表地址集合大得多。因此有可能 散列函数的 算，把不同的关 映

12、射到同一个散列地址上， 就 生了冲突搜索 就是在数据集合中 找 足某种条件的数据 象。搜索的 果通常有两种可能：搜索成功，即找到 足条件的数据 象。 ，作 果，可 告 象在 构中的位置 , 可 出 象中的具体信息。搜索不成功，或搜索失 。作 果， 告一些信息, 如失 志、位置等搜索 构 通常称用于搜索的数据集合 搜索 构，它是由同一数据 型的 象( 或 ) 成。在每个 象中有若干属性，其中有一个属性，其 可唯一地 个 象。称 关 。使用基于关 的搜索，搜索 果 是唯一的。但在 用 ，搜索条件是多方面的，可以使用基于属性的搜索方法，但搜索 果可能不唯一。 施搜索 有两种不同的 境。静 境，搜索

13、构在插入和 除等操作的前后不 生改 。?静 搜索表 境， 保持 高的搜索效率 , 搜索 构在 行插入和 除等操作的前后将自 行 整， 构可能 生 化。? 搜索表 序搜索 主要用于在 性表中搜索。 若表中有currentsize个元素， 序搜索从表的先端开始， 序用各元素的关 与 定 x 行比 若找到与其 相等的元素， 搜索成功， 出 元素在表中的位置。若整个表都已 完仍未找到关 与x 相等的元素， 搜索失 。 出失 信息二叉搜索 或者是一棵空 ，或者是具有下列性 的二叉 ： 1 每个 点都有一个作 搜索依据的关 (key) ，所有 点的关 互不相同。 2 左子 （如果非空）上所有 点的关 都小

14、于根 点的关 。3 右子 （如果非空）上所有 点的关 都大于根 点的关 。4 左子 和右子 也是二叉搜索 。二叉搜索树为二叉排序树 如果对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉搜索树为二叉排序树在二叉搜索树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设想要在二叉搜索树中搜索关键码为 x 的元素，搜索过程从根结点开始。 如果根指针为 null，则搜索不成功；否则用给定值 x 与根结点的关键码进行比较：若给定值等于根结点关键码，则搜索成功，返回搜索成功信息并报告搜索到结点地址。若给定值小于根结点的

15、关键码，则继续递归搜索根结点的左子树；否则。递归搜索根结点的右子二叉搜索树的插入算法： 为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。图定义 ：图是由顶点集合 (vertex)及顶点间的关系集合组成的一种数据结构：graph ( ,e)其中v= x|xv? 某个数据对象 是顶点的有穷非空集合；e = ( x, y)|x , y ? v 或 e = |x ,y ?v & path

16、 ( x, y) ，是顶点之间关系的有穷集合，也叫做边(edge)集合。 path (x,y) 表示从 x 到 y 的一条单向通路 ,它是有方向的。有向图与无向图 ：在有向图中，顶点对是有序的。在无向图中，顶点对(x, y) 是无序的。完全图 ：若有 n 个顶点的无向图有n( n-1)/2条边 , 则此图为完全无向图。 有 n 个顶点的有向图有n( n- 1)条边 ,则此图为完全有向图在图的 邻接矩阵 表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。邻接表 是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。在邻接表中，同一个顶点发出的边链接在同

17、一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标dest和指针 link 。对于带权图， 边结点中还要保存该边的权值cost 。顶点表的第 i个顶点中保存该顶点的数据，以及它对应边链表的头指针adj最短路径问题 ：如果从图中某一顶点（称为源点）另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。排序 ：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表 ( datalist ) :它是待排序数据元素的有限集合。排序码 ( key) : 通常数据元素有多个属性域 ,即多个数据成员组成 , 其中有一个属性域可用来区分元素, 作为排

18、序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。插入排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上,直到元素全部插入为止。 表1、 表中的插入与 除第一种情况：在第一个 点前插入第二种情况：在 表中 插入第三种情况：在 表末尾插入newnode link=first;newnode link=p link ;newnode link=p link ;first= newnode；p link=newnode；p link =last= newnode；2、 表插入算法 3、 表 点 除算法intlist:in

19、sert( constintx,const inti)intlist:(inti) /在 表中 除第i个 remove/ 在 表第i个 点 插入新元素x点listnode*p = first;intk = 0;node *p = first,*q ;intk = 0;while( p !=null & k i-1 )while(p !=null & ki -1 )p = p link;k+;/找第 i-1个 p = p link ;k+; /找第 i- 1 个 点点if(p = null |p link = null) if( p = null & first!=null )cout “无效的

20、 除位置!n ”;cout “ 无效的插入位置n” ;return0;return0;if(i = 0 )/ 除表中第1 个listnode *newnode=newlistnode(x,) ; 点null/ 建新 点 , 其数据 x, 指 0q = first;/ q 保存被 点地if(first = null|i =0 ) /插在址表前p = first = firstlink;/修改 firstnewnode link = first;if(first = null) last = newnode;else / 除表中或表尾元素first = newnode;q = p link ;pl

21、ink = q link ;/重新 接else /插在表中或末尾newnode link = p link;if(q = last)last = p;/可能修改 lastif(p link = null)last = newnode ;k = q data ;p link = newnode;deleteq ;/ 除qreturnk;return1;在 表 点的 表，第一个 点前插入新 点从 表 点的 表中 除第一个 点newnode link = p link;q =p link;p link = qlink;if (p link= null )last=newnode;deleteq;p

22、link = newnode;if (p link= null )last = p;排序直接插入排序的算法折半插入排序的算法#includedatalist.htemplate voidinsertsort(datalist& l, intleft, intright)#includedatalist.htemplate voidbinaryinsertsort (datalist& l,/ 依次将元素l.vectori按其排序 插入到有序表/l.vectorleft,l.vectori-1 中 , 使得/l.vectorleft到 l.vectori有序。element temp; inti

23、 ,j ;for(i= left+1;i =right;i+)if(li li-1)temp = li;j =i-1 ;do const intleft, const intright)/ 利用折半搜索,在 l.vectorleft到 l.vectori-1/ 找 l.vectori 插入的位置 ,再 行插入 。element temp;inti ,low ,high ,middle ,k;for(i=left+1;i =right;i+) temp =li;low = left;high =i-1 ;while(low = leftj-;& temp lj);if(temp lmiddle)

24、 high =/插入值小于中点值middle-1 ;/向左缩小区间lj+1=temp;堆排序的算法template voidheapsort (datalist& l) / 对表 l.vector0到 l.vectorn-1进行排序 ,使得表/ 中各个元素按其排序码非递减有序inti , n = l.length();for(i = (n - 2)/2;i= 0; i - ) /将表转换为堆siftdown (l,i,n-1) ;for (i = n- 1; i=0; i -) / 对表排序l.swap(0 ,i);siftdown (l, 0, i - 1) ;希尔排序的算法#include

25、datalist.htemplate voidshellsort (datalist& l,const intleft, const intright)inti ,j ,gap =right- left+1;/ 增量的初始值element temp;do gap =gap/3+1 ;/ 求下一增量值for(i=left+gap;i =right;i +)if(li= left& temp 1) ;elselow =middle+1 ;/否则 ,向右缩小区间for(k = i-1 ;k = low ;k-)lk+1=lk ;/ 成块移动 , 空出插入位置llow=temp;/插入;直接选择排序的

26、算法#includedatalist.htemplate voidselectsort (datalist& l,const intleft, const intright)for( inti=left;i right;i+)intk = i ;/在 li到 ln-1找最小排序码元素for( intj= i+1 ;j =right;j+)if(ljlk) k=j ;if(k !=i) swap (li,lk);/ 交换;起泡排序的算法template void bubblesort (datalist& l, const intleft,const intright)intpass = left+1,exchange = 1;while(pass= pass ;j