数据结构 作者 江家宝 程勇 数据结构-江家宝.pptVIP

An Introduction to Database Systenm 内容安排 ?第一章 数据结构的基础知识 ?第二章 线性表 ?第三章 栈与队列 ?第四章 串 ?第五章 数组与广义表 ?第六章 树 内容安排 ?第七章 图 ?第八章 查找 ?第九章 内部排序 基本概念和相关术语 数据 所有能输入到计算机之中，并能被计算机程序所处理的符号 的总称。如数字，字母，标点符号、图形图像 、声音等。 数据元素 描述数据的基本单位(数据项) 数据对象 性质相同的一类数据元素的集合 数据逻辑结构 数据元素之间的组织形式：集合、 线性结构、树形结构 网状结构。 基本概念和相关术语 物理结构 数据在计算机内部的实际存储结构 结点 存储在内存中的数据元素 域 数据元素中的每个数据项 线性存储结构 用物理地址相邻来表示数据元素在逻辑上的相邻关系。 链式存储结构 元素之间逻辑上的相邻关系物理地址上不一定相邻，而是通过指针来描述 抽象数据类型 数据类型是和数据结构密切相关的一 个概念。不同的数据类型拥有不同的取值 范围和允许的操作。从硬件的角度来看， 数据类型涉及具体存储单位。如int型占用 两个字节的存储空间，float型占用4个字节 的存储空间，可以帮助程序开发人员了解 内存的使用情况。 抽象数据类型 抽象数据类型（Abstract Data Type，ADT） 原子类型 固定聚合类型 可变聚合类型 抽象数据类型的组成（三元组 D S P） D表示数据对象 S是D上的数据关系 P表示D的基本操作 算法分析 算法 对特定问题求解步骤的一种描述，然后再依据算法编制程序完成 要求。 特性 有穷性 确定性 可行性 输入 输出 好的算法特性 正确性 可读性 健壮性 高效率 低存储 算法的时间复杂度分析 事后统计法 直接比较运行时间 事先分析法 用数学方法直接对算法的效率进行分析 指令的执行次数 抛弃特定的软硬件配置有关的因素，直接求出算法中 加法和乘法的执行次数。 下课了。。。 线性表 线性表顺序存储结构 定义 把线性表存储在一串连续的内存地址的结构叫做线性 表的顺序存储结构。 优点 只要知道第一个数据元素的位置，就可以很快地找到 表中任何一个元素。 基本操作 插入、删除、查询 线性表的链式存储结构 链表 一种动态存储结构，在需要插入一个结点时，按结 点的类型向系统申请一个结点的存储空间；当删除一 个结点时，就将这个结点的存储空间释放，它比顺序 存储方式更加灵活、高效。 结点 表示数据元素内容的部分称为数据域，表示直接后 继元素或直接前驱元素位置的部分称为指针。 单链表 单链表的基本操作 链表的建立 计算表长 查询元素 插入结点 删除结点 循环链表 将单链表的最后一个结点的指针域指向头结点，从而 形成一个环状，由此，从表中任意一结点出发都可以访 问到表中其他的结点。 循环链表 需要在第一个结点之前附加一个头结点作为标记，头 结点的数据域存储任何信息，指针域指向第一个结点。 循环链表的基本操作 循环链表的操作与单链表基本一致，如插入、删除、 查找、输出等。区别仅仅在于尾结点的判定条件不同。 双向链表 在需要同时频繁访问前驱和后继结点的时候，定义一 种新型的存储结构——双向链表。每个结点包含两个指 针域：一个指向前驱结点，另一个指向后继结点。 双向链表 双链表为当前结点与它们的前后继结点都建立明 确的逻辑关系，这样就解决了链表反方向访问结点的 问题。 双链表的基本操作 双链表的建立 插入 删除 循环双链表 一种变化的双链表形式。它借鉴了循环链表的思 想，将双链表的最后一个结点的后继指针指向头结点， 头结点的前驱指针指向最后一个结点。 循环双链表的基本操作 循环双链表的构造 循环双链表的遍历 插入 删除 查找 下课了。。。 栈和队列 定义 栈和队列是两种特殊的线性表。插入和删除操作均在 对首尾两个元素上进行。因此，从操作的角度上看，它 们属于操作受限的线性表。 应用背景 铁路调度中需要用到栈，民航机票订购中也会用到队 列。另外，栈和队列广泛应用于软件系统中。 栈(stack) 定义 限定在表的一端进行插入或删除操作的线性表。 相关术语