《数据结构》讲义及题型.ppt

数据结构 题型 选择(30%) 填空(10%) 判断(20%) 应用(30%) 算法描述(10%) 计算机基础(30%) 数据结构(70%) 计算机基础 多媒体 计算机存储程序体系结构 局域网的网络拓扑结构 电子邮件和域名 计算机病毒 ROM和RAM存储器 TCP/IP协议的IP地址 计算机语言的分类 CPU的组成 输入和输出设备 计算机的字长 操作系统 什么是数据结构 基本概念和术语 算法分析 性能分析与度量 第一章 绪论 学生成绩表格 UNIX文件系统结构图 四个基本结构 集合 线性结构 树形结构 网状结构 数据的逻辑结构分类 线性结构 线性表 非线性结构 树 图（或网络） 程序的产生 五个阶段： 需求（输入、输出） 设计（编写算法） 分析（选择最佳算法） 细化与编码（编写程序） 验证（程序验证、测试、调试） 算法分析 算法定义：为了解决某类问题而规定的一个有限长的操作序列 。 特性： 有穷性 算法在执行有穷步后能结束 确定性 每步定义都是确切、无歧义 可行性 每一条运算应足够基本 输入 有0个或多个输入 输出 有一个或多个输出 性能分析与度量 算法的性能标准 正确性：包括 不含语法错误 对几组数据运行正确 对典型、苛刻的数据运行正确； 对所有数据运行正确 可读性 效率：高效、低存储需要。（算法执行时间短，同时所占用的存储空间小。 健壮性：当输入非法数据时，算法也能作出适当反应，而不会出现莫名其妙的输出结果。 时间复杂度度量 运行时间 = 算法中每条语句执行时间之和。 每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。 语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。 设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。 时间复杂度和问题规模及待处理数据初态相关 第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较 线性表 定义： n（0）个数据元素的有限序列，记作（a1, …ai-1, ai, ai+1,…, an） 其中,ai 是表中数据元素，n 是表长度。 特点: 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。 顺序表 定义：将线性表中的元素相继存放在一个连续的存储空间中。 存储结构：数组。 特点：线性表的顺序存储方式。 存取方式：顺序存取,随机存取 顺序存储结构示意图 45 89 90 67 40 78 0 1 2 3 4 5 链表（Linked List） 链表是线性表的链接存储表示 存储结构：链式存储结构 特点：存储单元可以不连续。 存取方式：顺序存取。 顺序表与链表的比较 基于空间的比较 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量 顺序表的存储密度 = 1 链表的存储密度 1 顺序表与链表的比较 基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数 顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针 栈 队列 第三章栈和队列 19 栈 ( Stack ) 定义:是限定仅在表尾进行插入或删除操作的线性表。 允许插入和删除的一端 称为栈顶(top)，另一端 称为栈底(bottom) 特点：后进先出 (LIFO) a1 top bottom an . . . . 进栈 出栈 20 数制转换十进制数转换为八进制数。采用对十进制数除8取余的方法，可得到八进制数的倒序。 N = (N div d)×d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 21 队列 定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。 在队列中，允许插入的一端叫队尾（rear） ，允许删除的一端称为对头(front)。 特点：先进先