《数据结构总复习讲解》由会员分享，可在线阅读，更多相关《数据结构总复习讲解（23页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论1 1 基本概念1 数据数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2 数据元素数据元素是数据的基本单位， 数据项是数据的不可分割的最小单位。3 数据对象数据对象是性质相同的数据元素的集合。4 数据结构数据的逻辑结构是相互之间存在一种或多种特定关系的数据元素的集合， 形式定义为一个二元组： D ata_St ructur e=(D， S)其中， D 是数据元素的有限集； S 是D 上关系的有限集。 ( 1)集合： 数据元素之间除了“ 同属于一个集合” 的关系外， 别无其他关系。 ( 2)线性结构： 数据元素之间存在一个一对一的关
2、系， 有且仅有一个开始结点和终端结点， 除开始结点外， 每个结点有且仅有一个前趋结点， 除终端结点外， 每个结点有且仅有一个后继结点。 (3)树型结构： 数据元素之间存在一个对多个的关系， 有一个开始1结点和多个终端结点，除开始结点外，每个结点有且仅有一个前趋结点，除终端结点外， 每个结点可能有多个后继结点。 (4)网状结构或图状结构： 数据元素之间存在多个对多个的关系，每个结点可能有多个前趋结点和多个后继结点。 树型结构和网状结构又称为非线性结构。 顺序存储、链接存储、索引存储、散列存储。1 .2 算法及其分析 算法是是指令的有限运算序列。 算法具有以下5 个重要特性： 1.有穷性； 2.确
3、定性； 3 .可行性； 4.输入； 5.输出1 .3 算法的性能分析与度量 1.算法的性能标准 ( 1)正确性； (2 )可读性； (3)健壮性； (4)高效率与低存储量 2.算法效率的度量 时间复杂度T (n)=O(f (n) 空间复杂度S (n)=O(f (n) 算法+数据结构=程序第二章 线性表2.1 线性表的顺序存储 1.线性表的顺序存储特点逻辑上相邻的元素， 物理位置也相邻。静态有序表。线性表的顺序存储结构是一种随机存取的存储结构。表2-1 插入、删除、查找、合并算法的时间复杂度2.2 线性表的动态链式存储特点： 逻辑上相邻的元素， 物理位置可以不相邻， 表中元素只能顺序访问， 插入
4、、删除等操作只需修改指针而不需移动元素。线性表的链式存储结构是一种顺序存取的存储结构。2.3 线性表的静态链式存储特点： 用一维数组描述线性链表。2.4其他形式的链表1循环线性链表特点：最后一个结点的指针域指向头结点，从任意结点出发都可以找到表中的其他结点。2.双向链表特点:双向链表克服了在单链表中求前趋需要遍历链表而导致效率较低的缺点。从任意结点出发都可以找到表中的其他结点。第3 章 栈和队列栈和队列是操作受限制的线性表。3.1 栈及其应用栈( s ta ck ) 是限定只在表尾（ 栈顶）进行插入或删除操作的线性表，是后进先出(LIFO)的线性表。栈结构通常采用的两种存储结构是顺序存储结构和
5、链表存结构。图3 1 栈结构的示意图(A， B， C， D)(C， A， B， D) 3.2队列及其应用队列(Queue) 是限定只能在表的一端（ 队尾）进行插入， 而在表的另一端（ 队头）进行删除操作的线性表。和栈相反， 队列是一种先进先出(FIFO)的线性表。 图3 2 队列的示意图链队列： 队列的链式存储结构循环队列： 队列的顺序存储结构1， 2， 3， 4线性表、栈和队列都是线性结构， 可以在线性表的任何位置插入和删除元素； 对于栈只能在栈顶插入和删除元素； 对于队列只能在队尾插入元素和在队首删除元素。第4 章 串4.1 有关概念1、串(或字符串)， 是由零个或多个字符组成的有序序列。
6、s =a1a2 an (n 0 )2、串中字符的数目称为串的长度。零个字符的串称为空串，它的长度为零。3、串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。4、空串是所有字符串的子串， 任何字符串是自身的子串。4.2 串的存储表示1串的定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列，每个串变量分配一个固定长度的存储区。2串的变长顺序存储(堆分配存储)表示用一组地址连续的存储单元存储串值的字符序列，它们的存储空间是在程序执行过程中动态分配而得，对字串进行操作时不存在溢出问题。3串的块链存储表示适用于不改变数据结点的操作,如查找(或模式匹配)。4.3 串的常用
7、运算串赋值StrA ssign、串的比较S trC ompare、求串长StrL ength、串连接Strcat 以及求子串Sub String 构成串类型的最小操作子集。如果s=I AM A STUD ENT， t=GOO D， 则LENGTH(s)的结果是1 4，CONCAT(SU BSTR(s ,6,2), CONCAT (t,SUB ST R(s,7,8) )A GOOD STUDENTA=BEI B=J ING C= D =BEIJ INGStrLength (S) 求串长StrLength (A)=3 S trLeng th( B)=4Concat(&T， S1， S2) 联接函数
8、Concat(&T ,A,B) T= B EIJINGConcat(&T ,B,A) T= J INGBEISubString (&Sub， S， po s， len ) 求子串SubString (&Sub， D， 1， 3)=B EISubString (&Sub， D， 4， 0) SubString (&Sub， D， 4， 4) JINGIndex(S， T， pos ) 定位函数Index(d， b， pos )=4 Index(d， c， pos )=0如果设e= I 则 Index (d,e， pos)=3Replace(& S， T， V) 置换操作例如， 设S= BBABB
9、AB BA， T AB， V= C则Replace(S， T， V)的操作结果为S= B BCBCBA。StrInsert (&S， p os， T) 插入操作例如： Str Insert (&B,1, A)= B EIJINGStrDelete (&S， p os， le n) 删除操作例如： Str Delete (&D,1, 3)= J ING例如， 假设 s= ZHONGG UOConcat(Su bStrin g(s,1, 5), , Su bS tring (s, 6,3) ZHONG GU OConcat(Su bStrin g(s,1, 2), Su bStrin g( s,7
10、,2) ZHUOSubString (d,1,3 )= NAN S=NANJING第五章 数组和广义表5 .1 多维数组类型特点:1 ) 只有引用型操作， 没有加工型操作；2 ) 数组是多维的结构， 而存储空间是一个一维的结构。有两种顺序映象的方式:以行序为主序(低下标优先)；以列序为主序(高下标优先)。L OC( ai j ) = LO C( a1 1 ) + ( (i- 1)* n + j-1 ) * L称为基地址或基址。5 .2 特殊矩阵的压缩存储对称矩阵（书）k =I* (I -1) /2+ J-1下（ 上） 三角矩阵带状矩阵5 .3 稀疏矩阵稀疏矩阵的三元组表存储 （书） 三元组表
11、稀疏矩阵的十字链表存储 （书）5 .4 广义表A （ ）B （ e）C （ a，（ b， c， d）D （ A， B， C）E （ a， E）F （ ）广义表基本运算H ead (l s)： 返回广义表ls 的头部T ail (l s)： 返回广义表的尾部H ead（ B） e Tail（ B） （ ）H ead（ C） a Tail（ C） （ b， c， d）H ead（ D） A Tail（ D） （ B， C）H ead（ E） a Tail（ E） （ E）H ead（ F） （ ） Tail（ F） （ ）广义表的存储1.头尾表示法2.孩子兄弟表示法第六章 树与二叉树6.1 树的结
12、构特性树中只有根结点没有前趋， 其余结点有且仅有一个前趋， 所有结点可有零个或多个后继。6.2 二叉树及其性质二叉树：是结点的有限集，该集合或者为空或者是由一个根结点和两棵互不相交的被称为该根的左子树和右子树所组成。二叉树的五种基本形态(a)空二叉树； (b )仅有根结点的二叉树， (c)右子树为空的二叉树；(d)左、右子树均非空的二叉树； (e)左子树为空的二叉树。性质1 在二叉树的第i 层上至多有2i -1 个结点(i 1)。性质2 深度为k 的二叉树至多有2k-1 个结点， (k 1)。满二叉树： 深度为k 且结点数为2k -1 的二叉树。完全二叉树： 深度为k、有n 个结点的二叉树，
13、当且仅当每一个结点都与深度为k 的满二叉树中编号从1 到n 的结点一一对应。性质3 对任何一棵二叉树T， 如果其终端结点数为n0， 而度为2的结点数为n2， 则n0=n2+1。例n0=6 n2=5 n0=n2+1=6特殊形态的二叉树(a)满二叉树； (b )完全二叉树；(c)和(d)非完全二叉树。性质4 具有n 个结点的完全二叉树的深度为 log2 n+1性质5 如果对一棵有n 个结点的完全二叉树（ 其深度为 log2 n+1）的结点按层序编号(从第1 层到第 log2 n+1 层，每层从左到右)，则对任一结点i(1 i n)， 有( 1)如果i 1， 则结点i 是二叉树的根， 无双亲； 如果i 1， 则其双亲是结点 i 2。( 2)如果2i n， 则结点i 无左孩子； 否则其左孩子是结点2i。( 3)如果2i +1n， 则结点i 无右孩子； 否则其右孩子是结点2i +1。(1)n 个结点的二叉树最多有n 层， 最少有 log2 n+1 层；(2)完全二叉树中度为1 的结点最多1 个；(3)具有n 个结点的完全二叉树， 编号最大的非叶结点是 n/2， 编号最小的叶结点是 n/2+1；(4)度为1 的结点数为(n +1) mod 2， 度为0 的结点数为 n/2， 度为2 的结点数为 n/2- 1。6.3 二叉树的存储结构1 .顺序存储结构按照完全二叉树的结构对
