《大学计算机基础：第二单元 数据结构基础》由会员分享，可在线阅读，更多相关《大学计算机基础：第二单元 数据结构基础（80页珍藏版）》请在金锄头文库上搜索。
1、第二单元第二单元 数据结构基础数据结构基础Unit 2: Basics of Data Structure2学习指导学习指导（Learning Guide）l概述概述(Overview)l重要内容重要内容(Important Parts)l教学目标教学目标(Objectives)l重要示图重要示图(Important Diagrams)l重要习题重要习题(Important Exercises)3概述概述(Overview)l数据结构基本知识数据结构基本知识l线性表及其操作线性表及其操作l二叉树及其操作二叉树及其操作4重要内容重要内容（Important Parts）3.1 数据结构数据结构5
2、教学目标教学目标（Objectives）l了解数据的逻辑结构与存储结构概念了解数据的逻辑结构与存储结构概念l了解链式存储结构了解链式存储结构l掌握栈和队列的顺序存储结构掌握栈和队列的顺序存储结构l掌握栈和队列的基本运算掌握栈和队列的基本运算l掌握完全二叉树的顺序存储结构掌握完全二叉树的顺序存储结构l掌握二叉树的前序、中序和后序遍历方法掌握二叉树的前序、中序和后序遍历方法6重要示图重要示图(Important Diagrams) 图3.20完全二叉树的顺序存储示意图7重要习题重要习题（Important Exercises）第 三章习题：一、1-18二、1-14三、1-7四、1-982.1 数据
3、结构基本知识数据结构基本知识(Basics of Data Structure)l数据结构的概念l数据的逻辑结构l数据的存储结构92.1.1 数据结构的概念数据结构的概念(The Concept of DataStructure)(1)(1)定义：定义：数据的组织形式称数据结构e.g.为了便于存储、提取、更新和检索，图书馆用一组帖有标签的柜子来组织图书。这种形式就相当于所说的”数据结构”(2)(2)分类分类：数据的逻辑结构和数据的存储结构 (3)(3)程序与数据结构的关系程序与数据结构的关系a.程序涉及两大方面对数据的描述/对操作的描述 b.对数据的描述 涉及数据的类型和数据结构112.1.2
4、 数据的逻辑结构数据的逻辑结构1.定义在逻辑上，数据元素被组织起来。此种组织形式称为数据的逻辑结构。亦称抽象数据结构2.特点不考虑计算机实现，是抽象的Note: “逻辑逻辑”指系统化互连指系统化互连(systemized interconnection)3.示例示例(Examples)线性结构：ABCD树形结构：AFBECDGNote:对于线性结构中的对于线性结构中的A和和B，A可看成复合判断中的前件而可看成复合判断中的前件而B可可看成后件。另一方面，在组织结构中，看成后件。另一方面，在组织结构中，A可看成可看成B的上级的上级132.1.3 数据的存储结构数据的存储结构(Internal St
5、ructure)141. 概念概念(Concept)(1)定义：在存储上，数据元素被组织起来。此种组织形式被称为数据的存储结构。亦称内部存储结构(2)特点：考虑计算机实现。涉及计算机内部存储器(3)分类：顺序存储结构和链式存储结构152. 顺序存储结构顺序存储结构（1）定义在存储上，数据元素被顺序分配在一块连续的存储单元中。此种组织形式被称为顺序存储结构。亦称向量（2）示例）示例（Example）e.g. 采用顺序存储结构存储三个数：192,168,12812819216800000000000010100000101100001100内存储器地址(码)Note: 00001010称作起始地址
6、称作起始地址(码码)173. 链式存储结构链式存储结构(1)定义在存储上，数据元素之间有链式关系。此种组织形式被称为链式存储结构(2)示例示例（Example）e.g. 采用链式存储结构存储三个数：192,168,128192168001000000000101000100000010000000100000012800000000Notes:1 00100000为为168的地址被认为：此的地址被认为：此地址指向地址指向1682 内容内容00000000表表示：无所指示：无所指3特点：特点：只要知道只要知道第一个数据元素的第一个数据元素的存储地址，所有数存储地址，所有数据元素都可根据关据元素都
7、可根据关系链被找到系链被找到(3)简化表示简化表示（Simplification）192 20168 40128 0020H40H0AH192168128 头指针Notes1结点：每一部分称为一个结点。由数据域和指针域组成结点：每一部分称为一个结点。由数据域和指针域组成2数据域：即数据元素本身数据域：即数据元素本身3指针域：即下一个结点的开始地址码指针域：即下一个结点的开始地址码4头指针：其值为第一个结点的开始地址头指针：其值为第一个结点的开始地址5:即即null(意意为“无无”)。因。因读音音为n l,故用故用代代null20Assignment for Section 3Exercises
8、 of Chapter 1 Part 3: 4 Part 4: 1,2,5Exercises of Chapter 2 Part 1: 6,7 Part 2: 6 Part 3: 2-5 Part 4: 5-8212.2 线性表及其操作线性表及其操作222.2.1线性表的概念线性表的概念(The Concept of Linear List) 由n（n0）个具有相同数据类型的数据元素所构成的有限序列称为线性表 当n1时，线性表可记为（a1,a2ai-1,aian) l前趋和后继：ai-1称ai的前驱，ai称ai-1的后继l位序：对于ai,下标i称ai在线性表中的位序。它用于确定元素在线性表中的
9、位置。l插入操作：使插入点后面数据元素往后依次移动一个位置。然后在空出的位置上将待插的数据元素放入。l删除操作：被删数据元素后面的数据元素往前依次移动一个位置。292.2.3 栈栈（Stack）1. 栈的概念（The Concept of Stack）l定义：只能在限定的一端进行操作的线性表被称为栈l栈的操作：进栈（插入一个数据元素）；出栈（删除一个数据元素）l操作规则：后进先出或先进后出(LIFO/FILO)30 A1 A2 A3 An 栈底元素 栈顶元素 入栈（插入）出栈（删除）l示意图示意图(Illustration)线性表Note:一次进栈或出栈的数据元素个数均为一 312. 例题：例
10、题：已知三个入栈元素。写出全部出栈序列已知三个入栈元素。写出全部出栈序列e.g. 假定有三个元素A,B,C依次进栈。整个进栈过程允许出栈。试写出所有可能的出栈序列（要求：先出栈的元素写在出栈序列的最左边）32l分析分析 先按先按“接连进栈接连进栈”对元素进行分组；然对元素进行分组；然后对全部分组情形逐一写出相应的出栈序列后对全部分组情形逐一写出相应的出栈序列 所有分组情形如下：所有分组情形如下： A,B,C； A,BC； AB,C；ABC； 33A,B,C: ABC(A进A出，B进B出，C进C出）A,BC : ACB (A进A出，B进C进，C出B出）AB,C : BAC (A进B进，B出A出，
11、C进C出） BCA (A进B进，B出，C进，C出A出）ABC : CBA (A进B进C进，C出B出A出）Note: C开头的只有一种开头的只有一种3. 进一步的问题：已知四个入栈元素。写出全进一步的问题：已知四个入栈元素。写出全部出栈序列。假定和要求同上例。部出栈序列。假定和要求同上例。分析：先按分析：先按“接连进栈接连进栈 ”对元素进行分组；然后写出相应对元素进行分组；然后写出相应的出栈序列。的出栈序列。 A,B,C,D: ABCD A,BC,D: ACBD/ACDB A,B,CD: ABDC A,BCD: ADCB AB,C,D: BACD/BCAD/BCDA AB,CD: BADC/BD
12、CA ABC,D: CDBA/CBDA/CBAD ABCD: DCBANote: D开头的只有一种开头的只有一种352.2.4 顺序栈顺序栈1. 顺序栈概念：(1)定义：即栈的顺序存储结构。数据元素被顺序分配在一块连续的存储单元中(2)实现：设置一个指针型变量来指示栈顶e.g. 栈栈S的大小为的大小为6个存储单元；个存储单元；top为指针型变量，为指针型变量，用于指示栈顶。栈底处于低地址码端。用于指示栈顶。栈底处于低地址码端。 (a)空栈 (b) A进栈 (c)栈满 (d) F，E出栈top=-1543210top=0A543210FEDCBA543210top=5top=3DCBA54321
13、0分析：这里，出于简化，视单元编号分析：这里，出于简化，视单元编号0,1,2,3,4,5为与该栈为与该栈有关的连续的存储单元的地址。有关的连续的存储单元的地址。 用用Maxsize表示该栈所表示该栈所含存储单元的个数。所以，含存储单元的个数。所以， Maxsize=6372. 顺序栈的进栈算法顺序栈的进栈算法l若topMaxsize-1，则top增1，将新元素存入top所指示的位置l否则(即：top=Maxsize-1) ，提示栈已满383. 顺序栈的出栈算法顺序栈的出栈算法l若top-1,则将top所指示的元素取走，使top减1l否则（即：top=-1)，提示栈已空392.2.5队列队列(Q
14、ueue)1. 队列的概念(The Concept of Queue) (1)定义：只能在限定的一端进行插入操作，而在另一端进行删除操作的线性表 (2)操作规则：先进先出(FIFO)40(3)示意图示意图(Sketch)A1 A2 A3 An队头元素队尾元素入队列(插入)出队列(删除)线性表Note:一次入队列或出队列的数据元素个数均为一 442.3 树与二叉树树与二叉树452.3.1 树的概念树的概念(The Concept of Tree)1.一棵树示意如下：T1T2T3第1层第2层第3层第4层46l要点要点(Basics)a.结点A称树根b.结点B为结点A的儿子结点c.结点B,C,D有兄
15、弟关系d.T1，T2,T3称A的子树e.树有层次性472. 相关术语相关术语(Terms) l结点的度和树的度结点的度和树的度：结点的度指结点的儿子结：结点的度指结点的儿子结点的个数。树的度指所有结点的最大度点的个数。树的度指所有结点的最大度l叶结点或终端结点叶结点或终端结点：度为零的结点：度为零的结点l分支结点或非终端结点分支结点或非终端结点：除去根结点和叶结点：除去根结点和叶结点l结点结点A到结点到结点I的路径的路径：ABFI结点序列结点序列l路径长度路径长度：路径上边的数目：路径上边的数目l祖先和子孙祖先和子孙：F的祖先有的祖先有B，A和自己；和自己；F的子孙有的子孙有I，J和自己和自己
16、T1T2T3第1层第2层第3层第4层 l结点的高度和树的高度：结点的高度和树的高度：结点的高度指结点到子孙叶结点结点的高度指结点到子孙叶结点路径的最大长度。树的高度指根结点的高度路径的最大长度。树的高度指根结点的高度l结点的深度和结点的深度和树的深度树的深度：结点的深度：指结点所在的层的结点的深度：指结点所在的层的层号的大小。树的深度：指树的层次的个数。层号的大小。树的深度：指树的层次的个数。l有序树和无序树：有序树和无序树：有序树的特点是兄弟结点之间有从左到有序树的特点是兄弟结点之间有从左到右的次序。无序树的特点是兄弟结点之间无此关系右的次序。无序树的特点是兄弟结点之间无此关系T1T2T3第
17、1层第2层第3层第4层502.3.2二叉树的概念二叉树的概念(The Concept of Binary Tree)1.一棵二叉树示意如下：ABDEFHJILM第1层第2层第3层第4层51l要点要点(Basics)树中任何结点的度不超过2二叉树的子树有左右之分l完美对称的二叉树称为满二叉树完美对称的二叉树称为满二叉树e.g. 一棵满二叉树如下：l完全二叉树：与相应的满二叉树比较，一般仅完全二叉树：与相应的满二叉树比较，一般仅底层右侧有残缺底层右侧有残缺 e.g. 下面左图为一棵完全二叉树。而右图为一棵非完全二叉树2.3.3 二叉树的性质二叉树的性质(The Properties of Bina
18、ry Tree)(1)在二叉树中，第i层的结点总数不超过2i-1。这里，i1(2)深度为h的二叉树最多有2h -1个结点(h1)，最少有h个结点。第1层第2层第3层第4层(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1对于上图：N0=5, N2=4(4)具有n个结点的完全二叉树的深度为:log2n的整数部分加一。对于上图：n=9, 树的深度4log29取整加一第1层第2层第3层第4层(5)对于有对于有N个结点的完全二叉树，从个结点的完全二叉树，从1开始从上到下从左开始从上到下从左到右对所有结点编号。到右对所有结点编号。I对应对应某结点的编号。则如下关
19、某结点的编号。则如下关系成立：系成立：如果如果I1，则其父结点的编号由，则其父结点的编号由I/2取整来确定；取整来确定；如果如果2*IN，则其左儿子的编号由，则其左儿子的编号由2*I来确定来确定；若；若2*IN，则无左儿子；，则无左儿子；如果如果2*I+1 N，则其右儿子的结点编号由，则其右儿子的结点编号由2*I+1来来确定；若确定；若2*I+1N，则无右儿子。，则无右儿子。582.3.4 完全二叉树的顺序存储结构完全二叉树的顺序存储结构(The Sequential Structure of a Complete Binary Tree)1. 概念：定义：用一组连续的存储单元按结点编号连续存
20、放完全二叉树中的结点。这种存储结构称为完全二叉树的顺序存储结构l示例示例(Example)e.g. 一棵完全二叉树及其对应的顺序存储结构如下所示一棵完全二叉树及其对应的顺序存储结构如下所示 A B C D E F G H I 0 1 2 3 4 5 6 7 8 (视为地址码）Note: 这里地址码值比编号值小这里地址码值比编号值小1652.3.6遍历二叉树遍历二叉树(Traversal of Binary Tree) 系统地检查二叉树中的每个结点，使得每个结点仅被访问一次。这种过程称二叉树的遍历。 对于这种遍历，任一给定结点可执行的操作有三种：访问结点本身，遍历该结点的左子树和遍历该结点的右子
21、树。根据三种操作的执行次序不同，可形成六种树的遍历方法。661. 先序遍历方法先序遍历方法（1）概念先访问根结点，然后遍历其左子树。最后遍历其右子树。这种遍历的特点是：树中任意结点的访问操作发生在遍历其左右子树之前。因此，此方法称先序遍历。 （2）要点涉及“递”和“归”两个方面访问结点的操作发生在遍历其左右子树之前（3）示例）示例（Example）遍历结果：FBADCEGIHNote:这里用结点符号序列表示先序遍历的结点访问顺序。而且先访问到的写在序列的左侧。682.中序遍历方法中序遍历方法（1）概念从根结点开始，先遍历其左子树，然后访问该结点。最后遍历其右子树。这种遍历的特点是：树中任意结点
22、的访问操作发生在遍历其左右子树之间。因此，此方法称中序遍历。（2）要点涉及“递”和“归”两个方面访问结点的操作发生在遍历其左右子树之间69（3）示例）示例(Example)遍历结果：ABCDEFGHI703. 后序遍历方法后序遍历方法（1）概念从根结点开始，先遍历其左子树，然后遍历其右子树。最后访问该结点。这种遍历的特点是：树中任意结点的访问操作发生在遍历其左右子树之后。因此，此方法称后序遍历。（2）要点涉及“递”和“归”两个方面访问结点的操作发生在遍历其左右子树之后71（3）示例）示例(Example)遍历结果：ACEDBHIGF72Assignment for Section 4 Exer
23、cises of Chapter 3 Part 1: 1,3-11,17,18 Part 2: 1-10 Part 3: 1-7 Part 4: 1-8732.4 图结构图结构2.4.1图的定义图G由一个顶点的有穷非空集合V(G)和一个弧的集合E(G)组成，通常记做G=(V，E)。 Notes： 1.图中的顶点对应数据元素图中的顶点对应数据元素 2.用有序对用有序对表示从顶点表示从顶点v到顶点到顶点w的一条有向弧。在的一条有向弧。在图示中以带箭头的弧线表示。若图的弧具有方向性则称这样图示中以带箭头的弧线表示。若图的弧具有方向性则称这样的图为有向图。的图为有向图。 3.用无序对用无序对(v,w)
24、表示无向弧。在图示中以不带箭头的线段表示无向弧。在图示中以不带箭头的线段表示。若图的弧被认为不具方向性则称这样的图为无向图。表示。若图的弧被认为不具方向性则称这样的图为无向图。74e.g. 图图G1是一个有向图是一个有向图G1=(V1，E1)。其中V1=A，B，C，D，E，F，G；E1=， ，75e.g. 图图G2是一个无向图是一个无向图G2=V2，E2。其中：V2=A，B，C，D，E，F；E2=(A，B)，(A，C)，(B，C)，(B，E)， (B，F)， (C，D)，(C，E)，(C，F)，(E，F)762.4.2 图的遍历图的遍历l根据搜索方法的不同，图的遍历方法有两种：一种叫做深度优先
25、搜索（DFS）方法；另一种叫做广度优先搜索（BFS）方法。77（1）深度优先搜索遍历（）深度优先搜索遍历（DFS）l深度优先搜索遍历类似于树的先序遍历。对于上图，以v3为遍历的初始点，则一种访问顶点的次序为：v3v2v4v9v1v6v5v8 v778（2）广度优先搜索遍历（）广度优先搜索遍历（BFS）l广度优先搜索遍历类似于树的按层次遍历对于上图，以v3为遍历的初始点，则一种访问顶点的次序为：v3v2v1v6v4v5v9v8 v779Note:l对于一个图，如果确定了其存储结构，那么其DFS序列和BFS序列就是唯一的。因为在存储时，人为定义了第1个顶点，以及各顶点之间邻接关系的顺序。若单纯从逻辑上考虑，则它们是不唯一的。l思路图思路图(Mental Map) 数据结构存储结构链式存储结构逻辑结构数据域/指针域顺序存储结构线性表树二叉树非线性线性遍历方法 性质先序/中序/后序遍历特例栈/队列抽象具体特例
