大一学习计算机基础课件datastructure

第二单元:数据结构基础

Unit2:BasicsofDataStructure2学习指导（LearningGuide）概述(Overview)重要内容(ImportantParts)教学目标(Objectives)重要示图(ImportantDiagrams)重要习题(ImportantExercises)3概述(Overview)数据结构基本知识线性表及其操作二叉树及其操作4重要内容（ImportantParts）3.1数据结构

5教学目标（Objectives）了解数据的逻辑结构与存储结构概念了解链式存储结构掌握栈和队列的顺序存储结构掌握栈和队列的基本运算掌握完全二叉树的顺序存储结构掌握二叉树的前序、中序和后序遍历方法6重要示图(ImportantDiagrams)

图3.20完全二叉树的顺序存储示意图7重要习题（ImportantExercises）第三章习题：一、1-18二、1-14三、1-7四、1-982.1数据结构基本知识

(BasicsofDataStructure)数据结构的概念数据的逻辑结构数据的存储结构92.1.1数据结构的概念(TheConceptofData

Structure)(1)定义：数据的组织形式称数据结构e.g.为了便于存储、提取、更新和检索，图书馆用一组帖有标签的柜子来组织图书。这种形式就相当于所说的”数据结构”(2)分类：数据的逻辑结构和数据的存储结构

(3)程序与数据结构的关系a.程序涉及两大方面

对数据的描述/对操作的描述

b.对数据的描述

涉及数据的类型和数据结构112.1.2数据的逻辑结构1.定义在逻辑上，数据元素被组织起来。此种组织形式称为数据的逻辑结构。亦称抽象数据结构2.特点不考虑计算机实现，是抽象的Note:“逻辑”指系统化互连(systemizedinterconnection)3.示例(Examples)线性结构：ABCD树形结构：AFBECDGNote:对于线性结构中的A和B，A可看成复合判断中的前件而B可看成后件。另一方面，在组织结构中，A可看成B的上级132.1.3数据的存储结构(InternalStructure)141.概念(Concept)(1)定义：在存储上，数据元素被组织起来。此种组织形式被称为数据的存储结构。亦称内部存储结构(2)特点：考虑计算机实现。涉及计算机内部存储器(3)分类：顺序存储结构和链式存储结构152.顺序存储结构（1）定义在存储上，数据元素被顺序分配在一块连续的存储单元中。此种组织形式被称为顺序存储结构。亦称向量（2）示例（Example）e.g.采用顺序存储结构存储三个数：192,168,128…128192…16800000000000010100000101100001100内存储器地址(码)Note:00001010称作起始地址(码)173.链式存储结构(1)定义在存储上，数据元素之间有链式关系。此种组织形式被称为链式存储结构(2)示例（Example）e.g.采用链式存储结构存储三个数：192,168,128……1921680010000000001010001000000100000001000000…12800000000Notes:

[1]00100000为168的地址被认为：此地址指向168

[2]内容00000000表示：无所指

[3]特点：只要知道第一个数据元素的存储地址，所有数据元素都可根据关系链被找到(3)简化表示（Simplification）19220168401280020H40H0AH192168128∧头指针Notes[1]结点：每一部分称为一个结点。由数据域和指针域组成[2]数据域：即数据元素本身[3]指针域：即下一个结点的开始地址码[4]头指针：其值为第一个结点的开始地址[5]Λ:即null(意为“无”)。因读音为[nΛl],故用Λ代null20AssignmentforSection3ExercisesofChapter1Part3:4Part4:1,2,5ExercisesofChapter2Part1:6,7Part2:6Part3:2-5Part4:5-8212.2线性表及其操作222.2.1线性表的概念(TheConceptofLinearList)

由n（n≥0）个具有相同数据类型的数据元素所构成的有限序列称为线性表

当n>1时，线性表可记为（a1,a2…ai-1,ai…an)

前趋和后继：ai-1称ai的前驱，ai称ai-1的后继位序：对于ai,下标i称ai在线性表中的位序。它用于确定元素在线性表中的位置。插入操作：使插入点后面数据元素往后依次移动一个位置。然后在空出的位置上将待插的数据元素放入。删除操作：被删数据元素后面的数据元素往前依次移动一个位置。242.2.2线性链表概念(TheConceptofLinearLinkedList)定义：可以采用链式存储结构存储线性表中的数据元素。这种存储结构被称为线性链表。亦称单链表特点：这种链表只有一个指针域，只能形成一个链251.线性链表的插入操作要点：使待插结点的指针域指向插入点后面的结点使插入点前面结点的指针域指向待插结点特点：数据元素不后移19220100168400AH20H待插(插入前)90H192901002016840(插入后)20H0AH90H272.线性链表的删除操作要点：使被删除结点的前趋的指针域指向被删除结点的后继特点：数据元素不前移192901002016840(删除前)20H0AH90H待删结点19220168400AH20H(删除后)1002090H292.2.3栈（Stack）1.栈的概念（TheConceptofStack）定义：只能在限定的一端进行操作的线性表被称为栈栈的操作：进栈（插入一个数据元素）；出栈（删除一个数据元素）操作规则：后进先出或先进后出(LIFO/FILO)30A1A2A3…An

栈底元素

栈顶元素入栈（插入）出栈（删除）示意图(Illustration)线性表Note:一次进栈或出栈的数据元素个数均为一

312.例题：

已知三个入栈元素。写出全部出栈序列

e.g.假定有三个元素A,B,C依次进栈。整个进栈过程允许出栈。试写出所有可能的出栈序列（要求：先出栈的元素写在出栈序列的最左边）32分析

先按“接连进栈”对元素进行分组；然后对全部分组情形逐一写出相应的出栈序列所有分组情形如下：

{A,B,C}；{A,BC}；{AB,C}；{ABC}；

33{A,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出，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/BDCA{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=3DCBA543210分析：这里，出于简化，视单元编号0,1,2,3,4,5为与该栈有关的连续的存储单元的地址。用Maxsize表示该栈所含存储单元的个数。所以，Maxsize=6372.顺序栈的进栈算法若top＜Maxsize-1，则top增1，将新元素存入top所指示的位置否则(即：top=Maxsize-1)，提示栈已满383.顺序栈的出栈算法若top>-1,则将top所指示的元素取走，使top减1否则（即：top=-1)，提示栈已空392.2.5队列(Queue)1.队列的概念(TheConceptofQueue)(1)定义：只能在限定的一端进行插入操作，而在另一端进行删除操作的线性表

(2)操作规则：先进先出(FIFO)40(3)示意图(Sketch)A1A2A3…An

队头元素

队尾元素入队列(插入)出队列(删除)线性表Note:一次入队列或出队列的数据元素个数均为一

412.顺序队列概念（1）定义：即队列的顺序存储结构。数据元素被分配在一块连续的存储单元中（2）实现：设置二个指针型变量来指示队头和队尾(3)示例(Example)e.g.下面队列的大小为3个存储单元。front为头指针变量；rear为尾指针变量。试分析队列的变化。分析：front=0rear=0(a)

队列初始为空

0

1

2

3front=0

rear=3(b)

A,B,C分别入队，此时队满ABC

0

1

2

3front=1rear=3(c)

A出队BC

0

1

2

3

front=3

rear=3(d)

B,C分别出队，此时队空

0

1

2

3442.3树与二叉树452.3.1树的概念(TheConceptofTree)1.一棵树示意如下：T1T2T3第1层第2层第3层第4层46要点(Basics)结点A称树根结点B为结点A的儿子结点结点B,C,D有兄弟关系T1，T2,T3称A的子树树有层次性472.相关术语(Terms)

结点的度和树的度：结点的度指结点的儿子结点的个数。树的度指所有结点的最大度叶结点或终端结点：度为零的结点分支结点或非终端结点：除去根结点和叶结点结点A到结点I的路径：ABFI结点序列路径长度：路径上边的数目祖先和子孙：F的祖先有B，A和自己；F的子孙有I，J和自己T1T2T3第1层第2层第3层第4层

结点的高度和树的高度：结点的高度指结点到子孙叶结点路径的最大长度。树的高度指根结点的高度结点的深度和树的深度：结点的深度：指结点所在的层的层号的大小。树的深度：指树的层次的个数。有序树和无序树：有序树的特点是兄弟结点之间有从左到右的次序。无序树的特点是兄弟结点之间无此关系T1T2T3第1层第2层第3层第4层502.3.2二叉树的概念

(TheConceptofBinaryTree)1.一棵二叉树示意如下：ABDEFHJILM第1层第2层第3层第4层51要点(Basics)树中任何结点的度不超过2二叉树的子树有左右之分完美对称的二叉树称为满二叉树e.g.一棵满二叉树如下：完全二叉树：与相应的满二叉树比较，一般仅底层右侧有残缺e.g.下面左图为一棵完全二叉树。而右图为一棵非完全二叉树2.3.3二叉树的性质

(ThePropertiesofBinaryTree)(1)在二叉树中，第i层的结点总数不超过2i-1。这里，i≥1(2)深度为h的二叉树最多有2h-1个结点(h≥1)，最少有h个结点。第1层第2层第3层第4层(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1对于上图：N0=5,N2=4(4)具有n个结点的完全二叉树的深度为:log2n的整数部分加一。对于上图：n=9,树的深度4＝log29取整加一第1层第2层第3层第4层(5)对于有N个结点的完全二叉树，从1开始从上到下从左到右对所有结点编号。I对应某结点的编号。则如下关系成立：如果I≠1，则其父结点的编号由I/2取整来确定；如果2*I≤N，则其左儿子的编号由2*I来确定；若2*I>N，则无左儿子；如果2*I+1≤N，则其右儿子的结点编号由2*I+1来确定；若2*I+1>N，则无右儿子。582.3.4完全二叉树的顺序存储结构

(TheSequentialStructureofaCompleteBinaryTree)1.概念：定义：用一组连续的存储单元按结点编号连续存放完全二叉树中的结点。这种存储结构称为完全二叉树的顺序存储结构示例(Example)

e.g.一棵完全二叉树及其对应的顺序存储结构如下所示ABCDEFGHI012345678(视为地址码）Note:这里地址码值比编号值小1602.确定顺序存储结构中结点近亲的方法画图法：画出相应的完全二叉树以确定某结点的父结点和左右儿子结点；再根据顺序存储结构可确定它们相应的存储地址码利用结点编号性质：根据完全二叉树的结点编号性质，可以根据某结点的存储地址码确定其父结点以及左右儿子结点的存储地址码613.确定近亲示例：

e.g.一棵完全二叉树的顺序存储结构如下所示。求D结点的父结点及其左右儿子结点的地址码ABCDEFGHI012345678(视为地址码）（1）求其父结点的地址码：D结点的地址码为3，其结点编号为3＋1父结点的编号为：int((3+1)/2)＝2

(int：取整运算)故父结点的地址码为：2－1（B的地址码）（2）求其左儿子结点的地址码：因为：2×(3+1)≤8+1;所以,结果为：2×(3+1)-1=7（3）求其右儿子结点的地址码：因为：2×(3+1)+1≤8+1;所以,结果为：2×(3+1)+1-1=8ABCDEFGHI012345678632.3.5二叉树的链式存储结构

(TheLinkedStructureofaBinaryTree)1.概念：（1）定义：用链表来存储二叉树中的数据元素。这种存储结构称二叉树的链式存储结构。亦称二叉链表（2）组成：二叉链表中的结点具有三个域lchild域：左儿子结点的开始地址rchild域：右儿子结点的开始地址data域：数据元素本身（3）实现：设置一个称为头指针的指针型变量来指示二叉树的根结点642.示例(Example)e.g.二叉链表如下所示：0AH30H50H70H90H30507090652.3.6遍历二叉树

(TraversalofBinaryTree)

系统地检查二叉树中的每个结点，使得每个结点仅被访问一次。这种过程称二叉树的遍历。对于这种遍历，任一给定结点可执行的操作有三种：访问结点本身，遍历该结点的左子树和遍历该结点的右子树。根据三种操作的执行次序不同，可形成六种树的遍历方法。661.先序遍历方法（1）概念先访问根结点，然后遍历其左子树。最后遍历其右子树。这种遍历的特点是：树中任意结点的访问操作发生在遍历其左右子树之前。因此，此方法称先序遍历。

（2）要点涉及“递”和“归”两个方面访问结点的操作发生在遍历其左右子树之前（3）示例（Example）遍历结果：FBADCEGIHNote:这里用结点符号序列表示先序遍历的结点访问顺序。而且先访问到的写在序列的左侧。682.中序遍历方法（1）概念从根结点开始，先遍历其左子树，然后访问该结点。最后遍历其右子树。这种遍历的特点是：树中任意结点的访问操作发生在遍历其左右子树之间。因此，此方法称中序遍历。（2）要点涉及“递”和“归”两个方面访问结点的操作发生在遍历其左右子树之间69（3）示例(Example)遍历结果：ABCDEFGHI703.后序遍历方法（1）概念

从根结点开始，先遍历其左子树，然后遍历其右子树。最后访问该结点。这种遍历的特点是：树中任意结点的访问操作发生在遍历其左右子树之后。因此，此方法称后序遍历。（2）要点涉及“递”和“归”两个方面访问结点的操作发生在遍历其左右子树之后71（3）示例(Example)遍历结果：ACEDBHIGF72AssignmentforSection4ExercisesofChapter3Part1:1,3-11,17,18Part2:1-10Part3:1-7Part4:1-8732.4图结构2.4.1图的定义

图G由一个顶点的有穷非空集合V(G)和一个弧的集合E(G)组成，通常记做G=(V，E)。Notes：

1.图中的顶点对应数据元素

2.用有序对<v,w>表示从顶点v到