数据结构 教学课件 ppt 作者 江家宝 程勇 数据结构-江家宝

数据结构,学习方式, 听课 （启发式、讨论式） 读书 （预习、复习） 报告 （综合练习）,考试成绩,平时成绩 （书面作业、上机练习、综合练习） 上机考试 期末笔试,内容安排,第一章 数据结构的基础知识 第二章 线性表 第三章 栈与队列 第四章 串 第五章 数组与广义表 第六章 树,内容安排,第七章 图 第八章 查找 第九章 内部排序,数据结构 第一章 数据结构的基础知识,基本概念和相关术语,数据 所有能输入到计算机之中，并能被计算机程序所处理的符号 的总称。如数字，字母，标点符号、图形图像 、声音等。 数据元素 描述数据的基本单位(数据项) 数据对象 性质相同的一类数据元素的集合 数据逻辑结构 数据元素之间的组织形式：集合、 线性结构、树形结构 网状结构。,基本概念和相关术语,物理结构 数据在计算机内部的实际存储结构 结点 存储在内存中的数据元素 域 数据元素中的每个数据项 线性存储结构 用物理地址相邻来表示数据元素在逻辑上的相邻关系。 链式存储结构 元素之间逻辑上的相邻关系物理地址上不一定相邻，而是通过指针来描述,抽象数据类型,数据类型是和数据结构密切相关的一 个概念。不同的数据类型拥有不同的取值 范围和允许的操作。从硬件的角度来看， 数据类型涉及具体存储单位。如int型占用 两个字节的存储空间，float型占用4个字节 的存储空间，可以帮助程序开发人员了解 内存的使用情况。,抽象数据类型,抽象数据类型（Abstract Data Type，ADT） 原子类型 固定聚合类型 可变聚合类型 抽象数据类型的组成（三元组 D S P） D表示数据对象 S是D上的数据关系 P表示D的基本操作,算法分析,算法 对特定问题求解步骤的一种描述，然后再依据算法编制程序完成 要求。 特性 有穷性 确定性 可行性 输入 输出 好的算法特性 正确性 可读性 健壮性 高效率 低存储,算法的时间复杂度分析,事后统计法 直接比较运行时间 事先分析法 用数学方法直接对算法的效率进行分析 指令的执行次数 抛弃特定的软硬件配置有关的因素，直接求出算法中 加法和乘法的执行次数。,下课了。,追求,休息一会儿。,数据结构 第二章 线性表,线性表,定义 具有相同类型的n个数据元素的有限序列。元素之间存在着线性的逻辑关系。,前驱结点和后继结点,以ai为例， ai+1是它的直接后继元素， ai-1是它的直接前驱元素。,线性表顺序存储结构,定义 把线性表存储在一串连续的内存地址的结构叫做线性 表的顺序存储结构。 优点 只要知道第一个数据元素的位置，就可以很快地找到 表中任何一个元素。 基本操作 插入、删除、查询,线性表的链式存储结构,链表 一种动态存储结构，在需要插入一个结点时，按结 点的类型向系统申请一个结点的存储空间；当删除一 个结点时，就将这个结点的存储空间释放，它比顺序 存储方式更加灵活、高效。 结点 表示数据元素内容的部分称为数据域，表示直接后 继元素或直接前驱元素位置的部分称为指针。,单链表,单链表结点由两部分组成：一部分是该结点的数值， 另一部分是指向直接后继结点的指针。,可以将链表画成如下的形式,h是头指针，它指向单链表的第一个结点，是单链表的入口地 址访问单链表的任何结点必须由头指针出发。,单链表的基本操作,链表的建立 计算表长 查询元素 插入结点 删除结点,循环链表,将单链表的最后一个结点的指针域指向头结点，从而 形成一个环状，由此，从表中任意一结点出发都可以访 问到表中其他的结点。,循环链表,需要在第一个结点之前附加一个头结点作为标记，头 结点的数据域存储任何信息，指针域指向第一个结点。,循环链表的基本操作,循环链表的操作与单链表基本一致，如插入、删除、 查找、输出等。区别仅仅在于尾结点的判定条件不同。,双向链表,在需要同时频繁访问前驱和后继结点的时候，定义一 种新型的存储结构双向链表。每个结点包含两个指 针域：一个指向前驱结点，另一个指向后继结点。,双向链表,双链表为当前结点与它们的前后继结点都建立明 确的逻辑关系，这样就解决了链表反方向访问结点的 问题。,可以方便地向前访问结点，既不需要像单链表那样重新遍历结点，也不需要像循环链表那样从尾结点“跳回”到头结点 。,双链表的基本操作,双链表的建立 插入 删除,循环双链表,一种变化的双链表形式。它借鉴了循环链表的思 想，将双链表的最后一个结点的后继指针指向头结点， 头结点的前驱指针指向最后一个结点。,循环双链表实质上是两个单循环链表的合成，结点类型和基 本操作与双链表完全一样，直接采用双链表结点的定义。,循环双链表的基本操作,循环双链表的构造 循环双链表的遍历 插入 删除 查找,下课了。,追求,休息一会儿。,数据结构 第三章 栈与队列,栈和队列,定义 栈和队列是两种特殊的线性表。插入和删除操作均在 对首尾两个元素上进行。因此，从操作的角度上看，它 们属于操作受限的线性表。 应用背景 铁路调度中需要用到栈，民航机票订购中也会用到队 列。另外，栈和队列广泛应用于软件系统中。,栈(stack),定义 限定在表的一端进行插入或删除操作的线性表。 相关术语 栈顶 栈底 栈长 空栈,进栈和出栈,a0先进栈，an最后进栈，如图3-1所示。an是栈顶元素，所有出栈、入栈操作都是针对它进行的。a0是栈底元素，最后一个出栈。总之，栈是按后进先出（Last In First Out，LIFO）的原则进行处理的。,栈的顺序存储结构(顺序栈),顺序栈在存储地址上也是连续的，因此可以用数组表示顺 序栈中的所有元素。,定义一个整型变量top来存储栈顶元素的下标，其作用相当 于栈顶指针。指向最后一个入栈的元素。,顺序栈的基本操作,顺序栈的基本操作 计算栈长 返回栈顶元素 入栈 出栈 遍历栈,栈的链式存储结构(链栈),栈的链式存储结构是通过单链表实现的。此时表头（第一个结点，非头结点）指针被称为栈顶指针，由栈顶指针指向的表头结点称为栈顶结点。,链栈的基本操作与顺序栈相同,栈的应用,表达式求值 计算两个运算数之间的加、减、乘、除运算 数值转换 十进制数和其他数制（比如二进制）之间的转换 括号匹配 判断表达式中的括号是否成对出现 递归的实现 递归运算满足“后运算先返回”原则，可以利用栈来实 现,队列(Queue),定义 队列也是一种特殊的线性表，和栈相比，队列只 允许在一端进行插入操作，而在另一端进行删除操 作。 相关术语 队尾（Rear）：可以插入元素的一端。 队头（Front）：可以删除元素的一端。,队列,0是队头元素，最早出队；n是队尾元素，最后出队，元素 是按照入队顺序出队的。由此可见，队列的特点是先进先出 （First in First out，FIFO）。,队列的应用背景,操作系统中的作业排队 在允许多道程序运行的计算机系统中，同时有几个作 业运行时，就需要按作业的先后次序进行排队。位于队 头的作业先退出队列送入CPU进行处理；当一个任务完毕 以后，新队头的作业从队列中出队，进行处理；另外， 新的作业被送入到队列的队尾处，等待处理。,队列的顺序存储结构(顺序队列),队列的顺序存储结构和栈类似，也是在连续的存 储空间中存储数据元素。因此，可以借助一维数 组来表示队列中的元素。,需要设置front和rear 两个指针，并约定front指针在rear指针之前。当两者相等时，队列为空。初始化队列时，令front=rear=-1，此时队列空。为了指示队头和队尾，需要设置front和rear 两个指针，并约定front指针在rear指针之前。,入队,插入新元素到队尾时，尾指针rear加1。在非空队列中，头 指针front总是指向当前队头元素的前一个位置；当front=rear 时，表示队列为空。,出队,删除队头元素时，指针front加1。,顺序队列的基本操作,入队 出队 取队头元素 遍历队列 删除队列,顺序队列的问题,顺序队列因为队尾指针rear越出数组上界而“溢出”，最 终导致新元素无法入队。因此，,当队列中rear指针的值等于数字最大值时，新元素无法入队。但实际上，队列中仍然有两个存储空间可供存储，此时的“溢出”并不是真的因为存储空间不够而引的。,循环队列,为了克服这种问题，可以将队列的首尾连接在一起，形成一个环状,如果有元素出队的话，那么进队的元素可以存储到出队的元素位置上，直到数组全部填满为止。在实际的软件系统中，这种队列经常被使用，而顺序队列却很少使用。,循环队列的基本操作,判断循环队列是否为空 以“队头指针front在队尾指针rear的下一个位置上”作为队 列是 “满”状态的标志。 入队 出队 计算队长 取队头元素,队列的链式存储(链式队列),用链表的形式存储的队列称作链式队列。与顺序队列一 样，链式队列也需要定义队头和队尾两个指针（分别称 为队头指针和队尾指针），队头指针指向第一个结点， 队尾指针指向尾结点。所以，一个表头和一个表尾唯一 地确定一个队列。,链式队列的基本操作与顺序队列相同,链式队列的应用,舞会配对(男女配对问题) 先入队的男士或女士亦先出队配成舞伴。因此该问题 具有典型的先进先出的特性，可用队列作为算法的数据 结构。 模拟病人看病 医院看病者先到先看，所以使用队列来实现看病过程,下课了。,追求,休息一会儿。,数据结构 第四章 串,第四章 串,定义 串（String）是字符串的简称，它是由有限的字符组 成的序列，一般记为s=“s0s1s2sn-1”。其中，s是串名 ，n是串的长度。双引号括起来的字符序列s0s1s2sn-1 称作串的值。,串,相关术语 串的长度 空串 子串 主串 两个串相等,串的顺序存储结构,串的顺序存储结构用一组连续的存储单元（数组）依次存 储串中的字符序列，需要事先定义一个固定长度的存储区域 存储字符串(如数组)。,串的顺序存储结构,顺序串的基本操作 字符串的初始化 字符串的复制 字符串的连接 子串的提取 字符串的插入 字符串的删除 字符串的遍历,串的堆存储结构,为了处理在串操作中出现串的长度超过预定义的长 度的情况，可以采用堆分配的存储方式。 堆存储方式的特点：仍以一组地址的连续的存储单 元存放字符序列，但它们的存储空间是在程序执行过 程中动态分配的。在C语言中，存在一个称之为“堆” 的自由存储区，可由C语言中的malloc函数和free函数 管理，为了处理方便，规定串的长度也作为存储结构 的一部分。,串的块链存储结构,串的链式存储结构分为单字符结点链和块链两种。 串的链式存储结构就是把串值分别存放在链表的若干个结点 的数据域中。,块链就是每个结点的数据域包括若干个字符,由于串的大小不一定等于结点大小的整数倍，则链表中的最后一个结点不一定全部被串值占满，此时可以补上“#”或其他非串值字符,块链的基本操作,统计块链的长度 统计字符数组的长度 初始化块链 替换操作 提取子串操作 链接操作 块链的遍历,串的模式匹配方法,定义 设s和t是给定的两个串，且s的长度大于t的长度， 在s中找到等于t的子串的过程称为串的模式匹配， 如果找到，则称为匹配成功，否则，匹配失败。 应用背景 模式匹配是一种重要的串操作，在文字处理等软 件中有着广泛的应用。如word。,简单的模式匹配算法(BF算法),主要思想 蛮力算法，从主串的第一个字符开始和模式串的第一个字符开始比较，若相等则继续比较后续字符；否则从主串s的第二个字符开始重新与模式串t的第一个字符比较，按照这个方式，继续下去。如果模式串t和主串s的某一段连续子串相等，则匹配成功，并返回模式串t的第一个字符在主串中的位置；若匹配不成功，则返回-1。,BF算法的缺点,BF算法虽然简单，易于理解，但时间效率低。这是因为 在主串和子串已有相当多个字符相等的情况下，只要有一 个字符不相等，就需要重新将主串的比较位置后移一位， 之前做过的比较工作也需要重新进行。 为了克服这个缺点，D.E.Knuth、J.H.Morris和V.R.Pratt 提出了克努特