《国二复习必备 数据结构》由会员分享，可在线阅读，更多相关《国二复习必备 数据结构（57页珍藏版）》请在金锄头文库上搜索。
1、数据结构 datastructure 数据元素和数据元素关系的集合Data Structure D R 数据的逻辑结构 抽象反映数据元素的逻辑关系 从逻辑关系上描述数据 与数据的存储无关从具体问题抽象出来的数据模型 与数据元素本身的形式 内容无关 与数据元素的相对位置无关 数据结构 datastructure 数据元素和数据元素关系的集合Data Structure D R 数据的逻辑结构 抽象反映数据元素的逻辑关系 数据的存储结构 物理结构 数据的逻辑结构在计算机存储器中的实现 时间复杂度 同一问题可用不同算法解决 各种算法中 语句执行次数越多 则该算法耗费的时间越长 一个算法中的语句执行次
2、数称为语句频度或时间频度 记为T n T n 语句执行次数 该语句执行时间 语句执行次数该方法可独立于机器的软件 硬件系统来分析算法在效率方面的优劣 11 2n n2 时间耗费T n 4 6n 2n2 当n充分大时 T n 与n2在数量级上相同 记T n O n2 2n 1 n 1 n n 1 执行次数 时间复杂度 算法耗用时间相对问题规模n的增长率 一般指基本操作重复执行的次数的阶数大O表示法 T n O f n 加法规则与乘法规则 1 O f n O g n max O f n O g n 2 O f cn O f n c是正整数3 O f n O g n O f n g n T1 n O
3、 1 T2 n O n T3 n O n2 T n T1 n T2 n T3 n O max 1 2n n2 O n2 频度最大语句重复执行次数的阶数 例 n n矩阵相乘for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j c i j a i k b k j 时间复杂度 基本操作重复执行的次数的阶数 算法耗用时间的增长率 渐近 空间复杂度 S n O f n 辅助存储空间增长率或者说是算法所需存储空间的量度 常用时间复杂度 O 1 常量型O n O n2 O n3 多项式型O log2n O nlog2n 对数型O 2n O en 指数
4、型 线性结构特点 在数据元素的非空有限集中存在唯一的一个被称作 第一个 的数据元素存在唯一的一个被称作 最后一个 的数据元素除第一个外 集合中的每个数据元素均只有一个前驱除最后一个外 集合中的每个数据元素均只有一个后继 2 1线性表的逻辑结构定义 一个线性表是n个数据元素的有限序列 例英文字母表 A B C Z 是一个线性表 特征 有限 序列 同构元素个数n 表长度 n 0空表1 i n时ai的直接前驱是ai 1 a1无直接前驱ai的直接后继是ai 1 an无直接后继元素同构 且不能出现缺项 2 2线性表的顺序存储结构顺序表 定义 用一组地址连续的存储单元存放一个线性表叫 元素地址计算方法 L
5、OC ai LOC a1 i 1 LLOC ai 1 LOC ai L其中 L 一个元素占用的存储单元个数LOC ai 线性表第i个元素的地址 实现 可用一维数组或动态分配顺序存储结构实现 已知某元素序号i 可计算出该元素地址LOC ai 进行操作 无需从表头查找 特点 实现逻辑上相邻 物理地址相邻实现随机存取 顺序存储结构的优缺点优点逻辑相邻 物理相邻可随机存取任一元素存储空间使用紧凑缺点插入 删除操作需要移动大量的元素 2 3线性表的链式存储结构特点 用一组任意的存储单元存储线性表的数据元素利用指针 链 实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai 除存储本身信息外 还需存
6、储其直接后继的地址结点数据域 元素本身信息指针域 指示直接后继的存储位置 指针 或 链 指示表中元素的逻辑关系 例线性表 ZHAO QIAN SUN LI 13 19 7 例线性表 ZHAO QIAN SUN LI 19 7 例线性表 ZHAO QIAN SUN LI 7 例线性表 ZHAO QIAN SUN LI 例线性表 ZHAO QIAN SUN LI 头指针 单链表特点它是一种动态结构 整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取 查找速度慢删除 插入等操作方便 RailwaySwitchingNetwork 栈和队列是两种特殊的线性表是操作受限的线性表
7、称限定性数据结构限定插入和删除只能在表的 端点 进行的线性表 3 1栈 stack 栈的定义和特点定义 限定仅在表尾进行插入或删除操作的线性表 表尾 栈顶 表头 栈底 不含元素的空表称空栈特点 先进后出 FILO 或后进先出 LIFO 栈的存储结构顺序栈 base 栈底指针 始终指向栈底的位置top 栈顶指针 指向实际栈顶后的空位置 初始指向栈底 即top base 入栈 A 出栈 栈满 B C D E F 设栈容量为stacksize栈满 top base stacksize 栈空 栈空 top base ABCDE 操作序列 出栈序列 元素A入栈 A A 元素B入栈 B B 元素C入栈 C
8、 C 能否由入栈序列A B C D E 得到出栈序列CBDAE DE 操作序列 出栈序列 元素A入栈 A 元素B入栈 B 元素C入栈 元素C出栈 C C 元素B出栈 B 能否由入栈序列A B C D E 得到出栈序列CBDAE DE 操作序列 出栈序列 元素A入栈 A 元素B入栈 元素C入栈 元素C出栈 C 元素B出栈 B 元素D入栈 D D 元素D出栈 D 元素A出栈 A 能否由入栈序列A B C D E 得到出栈序列CBDAE E 操作序列 出栈序列 元素A入栈 元素B入栈 元素C入栈 元素C出栈 C 元素B出栈 B 元素D入栈 元素D出栈 D 元素A出栈 A 元素E入栈 E E 元素E出
9、栈 E 能否由入栈序列A B C D E 得到出栈序列CBDAE 可以得到 按1 2 3 4顺序进栈 有几种出栈序列 链栈 typedefstructSnode SElemTypedata 数据域structSnode link 指针域 LinkStack 链栈的操作是线性表的特例 比较易于实现 链栈结点结构 队列的定义及特点定义 队列是限定只能在表的一端进行插入 在表的另一端进行删除的线性表 队列的逻辑结构 队尾 rear 允许插入的一端队头 front 允许删除的一端队列特点 先进先出 FIFO front 队头 队尾 设队首 队尾指针front和rear front指向头结点 rear指
10、向队尾 rear 链队列 队列的链式存储结构 入队 J1 溢出 J2 J3 J4 J5 J6 真 队列的顺序存储结构 SqQueueQ defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 存储空间基址intfront 头指针 指向队头元素intrear 尾指针 指向队尾元素的下一个位置 SqQueue 顺序队列存储结构 初值 Q front Q rear 0 队空 Q front Q rear 入队 真溢出条件 Q base Q rear e Q front 0 Q rear MAXQSIZE SqQueueQ defineMAXQSIZE
11、100 最大队列长度typedefstruct QElemType base 存储空间基址intfront 头指针 指向队头元素intrear 尾指针 指向队尾元素的下一个位置 SqQueue 顺序队列存储结构 出队 假溢出条件 e Q base Q front 出队 J1 J2 J3 J4 J5 J6 溢出 假 队列的顺序存储结构 Q front 0 Q rear MAXQSIZE 方案一 队首固定 每次出队 剩余元素下移 J1出队 J1 J2 J3 J4 真溢出条件 Q front 0 Q rear MAXQSIZE 假溢出条件 Q front 0 Q rear MAXQSIZE 队列的顺
12、序存储结构 假溢出问题解决方案 J2出队 J2 J3 J4 缺点 浪费时间 方案一 队首固定 每次出队 剩余元素下移 队列的顺序存储结构 假溢出问题解决方案 真溢出条件 Q front 0 Q rear MAXQSIZE 假溢出条件 Q front 0 Q rear MAXQSIZE 方案二 循环队列 把队列设想成环形 首尾相接 若Q rear MAXSIZE 则令Q rear 0 实现 利用 模 运算 队列的顺序存储结构 假溢出问题解决方案 真溢出条件 Q front 0 Q rear MAXQSIZE 假溢出条件 Q front 0 Q rear MAXQSIZE 方案二 循环队列 把队列
13、设想成环形 首尾相接 若Q rear MAXSIZE 则令Q rear 0 实现 利用 模 运算 队列的顺序存储结构 假溢出问题解决方案 模 运算x MAXSIZE 结果范围为0 MAXSIZE 1 则 x 1 MAXSIZE可实现 x加1 满足范围要求 利用 模 运算实现循环队列 J8 J9 J7 初始状态 循环队列入队 队满 队列的顺序存储结构 循环队列 Q base Q rear e Q rear Q rear 1 MAXQSIZE 利用 模 运算实现循环队列 J8 J9 J7 初始状态 队满 J4 J5 J6 队空 循环队列出队 队列的顺序存储结构 循环队列 e Q base Q fr
14、ont Q front Q front 1 MAXQSIZE 利用 模 运算实现循环队列 J8 J9 J7 初始状态 队满 队空 队列的顺序存储结构 循环队列 循环队列中 队空条件 Q front Q rear队满条件 Q front Q rear 解决方案 1 设一个标志区分队空 队满2 少用一个元素空间 利用 模 运算实现循环队列 J8 J7 初始状态 队满 队空 队列的顺序存储结构 循环队列 解决方案 1 设一个标志区分队空 队满2 少用一个元素空间 队空 Q front Q rear队满 Q rear 1 MAXQSIZE Q front 五子棋游戏 树的实例 树是一类重要的非线性数据
15、结构 是以分支关系定义的层次结构 定义 树 tree 是n n 0 个结点的有限集T 其中 有且仅有一个特定的结点 称为树的根 root 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一个集合本身又是一棵树 称为根的子树 subtree 特点 非空树中存在唯一一个称为根结点非空树中各子树是互不相交的集合 树的定义 根 子树 结点 node 表示树中的元素 包括数据项及若干指向其子树的分支结点的度 degree 结点拥有的子树数叶子 leaf 度为0的结点孩子 child 结点子树的根称为该结点的孩子双亲 parents 孩子结点的上层结点叫该结点的 兄弟 si
16、bling 同一双亲的孩子树的度 一棵树中最大的结点度数结点的层次 level 从根结点算起 根为第一层 它的孩子为第二层 深度 depth 树中结点的最大层次数森林 forest m m 0 棵互不相交的树的集合 树的基本术语 结点A的度 结点B的度 结点M的度 叶子 结点A的孩子 结点B的孩子 结点I的双亲 结点L的双亲 结点B C D为结点K L为 树的度 结点A的层次 结点M的层次 树的深度 结点F G为结点A是结点F G的 3 2 0 B C D E F 3 1 4 4 K L F G M I J D E 兄弟 兄弟 堂兄弟 祖先 树的基本术语 定义 二叉树是n n 0 个结点的有限集 它或为空树 n 0 或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树 即不存在度大于2的结点 二叉树的子树有左 右之分 且其次序不能任意颠倒基本形态 二叉树的定义 二叉树的性质 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 用归纳法证明 归纳基 归纳假设 归纳证明 i 1层时 只有一个根结点 2i 1 20 1 假设对所有的j 1 j i 命
