数据结构(C语言版).ppt

1 数据结构 C语言版 计算机科学技术系易叶青 2 教材 数据结构 C语言版 清华大学出版社 严蔚敏吴伟民编著 教参 数据结构习题集 数据结构 第二版 3 教学计划 第一章绪论4学时第二章线性表10学时 含C语言链表 第三章栈和队列10学时第四章串4学时第五章数组和广义表6学时第六章树和二叉树14学时第七章图12学时第八章动态存储管理 自学 第九章查找8学时第十章排序10学时复习4学时机动2学时考试2学时 周课时 5节 周 4 第一章绪论 内容 什么是数据结构基本概念与术语抽象数据类型的表示与实现算法与算法分析 重点 数据结构的基本概念与术语算法的与算法评价 难点 数据结构的概念算法的分析与评价 5 数据结构 第一章绪论 1 1什么是数据结构 用计算机解决问题的方法 问题 建模 编程 设计算法 调试 运行 建模 分析问题 提取操作对象 并分析对象之间的包含关系 用数学方程或非数学方程表示 算法 求解问题的一种方法或一种描述 编程 用某种高级语言实现的可以在计算机上运行的程序 6 第一章绪论 建模的几个例子 1 数学方程 梁架结构应力模型线性方程组人口增长模型常微分方程曲面面积模型微积分等等2 非数学方程 数据结构的范畴 图书馆书目检索系统表格 关系模型人 机对弈树状模型多交叉路口交通控制灯管理图模型服务业窗口排队情况的最佳方案队列模型多数据排序数据模型 7 第一章绪论 图1 1 三子棋 对弈树的局部情况 初始状态 E 图1 2 五叉路口 交通灯控制 可能通路 连线表示不可同时通行通路 图的顶点着色问题 8 第一章绪论 数据结构的地位与作用 计算机硬件 计算机软件 数学 编码理论算子关系数据类型数据的表示数据运算数据结构数据存取机器组织 数据结构 是计算机专业教学计划中的核心课程之一 是一门综合性的专业基础课程 9 第一章绪论 1 2基本概念与术语 1 数据 客观事物的符号表示 2 数据元素 数据的基本单位 通常当作一个整体来处理 它常由数据项组成 数据项是不可分割的最小单位 3 数据对象 数据相同的数据元素的集合 是数据的子集 4 数据结构 相互之间存在的一种或多种特定关系的数据元素的集合 5 结构 数据元素之间的相互关系 集合 图或网络 线性结构 树 10 第一章绪论 数据结构的形式定义 Data Structure D S 其中D数据元素的集合 S是建立在D上的关系 例1 计算机中的算数可定义为 Complex C R 其中 C是两个实数的集合 C1 C2 R P 而P是定义在集合C上的关系 表示C上的有序偶对 C1表示复数的实部 C2表示复数的虚部 例2 含有N个元素的数组 Array i R 其中i表示 ai ai为整数 i 1 2 N R i 1 2 N 1 11 第一章绪论 例3 设某课题小组由一名教授 1 3名副教授 1 6名讲师组成 它们之间构成课题开发的指导关系 教授指导副教授 副教授指导1 2名讲师 6 逻辑结构 数据结构中定义的数据元素之间的逻辑关系 则课题小组的数据结构为 Group P R 其中 P P V1 Vm T11 Tmn 1 m 3 1 n 2 R R1 R2 R1 1 i m 1 m 3 R2 1 i m 1 m 3 1 j n 1 n 2 7 物理结构 存储结构 数据结构在计算机中的表示 又称映象 12 第一章绪论 8 结点数据元素在计算机中的存储映象 9 顺序存储结构 顺序映象 借助元素在存储器中的相对位置表示数据元素之间的逻辑关系 即数据逻辑位置与存储位置顺序相一致 10 链式存储结构 非顺序映象 借助元素在存储器中的地址 指针 表示数据元素之间的逻辑关系 即数据逻辑位置与存储位置顺序不一致 11 数据类型一个值的集合和定义在这个值集上的一组操作的总称 一般分成 原子类型和构造类型 13 第一章绪论 12 抽象数据类型ADT指一个数学模型以及定义在该模型上的一组操作 它仅取决于一组逻辑特性 而与计算机的存储与实现无关 一个抽象数据类型的软件模块通常由定义 表示和实现三部分组成 抽象数据类型的表示 ADT D S P 其中 D表示数据对象 S表示D上的关系 P表示对D的操作 ADT抽象数据类型名 数据对象 数据对象的定义 伪代码数据关系 数据关系的定义 伪代码基本操作 基本操作的定义 函数调用及说明 ADT抽象数据类型名 14 第一章绪论 例 用抽象数据类型定义一个三元组 e1 e2 e3 ADTTriplet 数据对象 D e1 e2 e3 数据关系 S 基本操作 initTriplet 初始条件 T已定义的三元组 v1 v2 v3已赋值操作结果 构造T v1 v2 v3分别赋给e1 e2 e3Max T e 表示能返回值初始条件 三元组T已存在操作结果 用e返回T的最大值 ADTTriplet 15 第一章绪论 通过固有的数据类型来表示与实现 本书采用类C语言作为描述工具 目的 易于描述与讨论算法 但不拘泥于C语言本身的细节 又容易转换成C或C 程序 主要有以下方面 1 预定义一些常量与类型 1 3抽象数据类型的表现与实现 2 数据结构表示用typedef描述元素类型约定用ElemType 用户根据实际自行定义 16 第一章绪论 3 基本操作的算法用如下形式的函数描述 函数类型函数名 函数参数表 算法说明语句序列 函数名函数参数需要说明类型 而辅助变量则可以不做说明 在形参表中以 开头的参数即为引用参数 传地址 4 赋值语句有多种灵活的表示如成组赋值 交换赋值 条件赋值等5 选择语句if if else switch6 循环语句for while do while 17 第一章绪论 7 结束语句return break exit 8 输入 输出语句scanf printf9 注释 10 基本函数max min abs floor ceil eof eoln 11 逻辑判定与 或 采用优先判定法 特别注意 以上表示类似于C语言 但又不同于C语言 同学们务必掌握其表现方法 为将来学习算法描述奠定基础 在将算法转换成C程序时 必须遵守C语言的语法规则 上机时不能盲目照搬照抄算法 否则上机将得不到结果 18 19 20 21 第一章绪论 1 4算法与算法分析 一 算法 Algorithm 对特定问题求解步骤的一种描述 是指令的有限序列 算法特性 1 有穷性一个算法对任何输入均应在有限步内完成 且每一步都可在有限时间内完成 时间可接受性 2 确定性对同一输入的不同运行只能得到同一输出 3 可行性算法操作只能通过已经实现的基本运算执行有限次来实现4 输入可以是0个或多个5 输出至少1个以上 22 第一章绪论 二 算法设计的要求1 正确性 correctness 分四层1 不含语法错误2 对几组数据运行正确3 对精心选择的 比较边缘的数据运行正确4 对任何输入均能正确运行 无错误程序 2 可读性 readability 3 健壮性 robustness 4 效率与存储容量要求效率指算法执行时间 存储容量指算法执行过程中所需的最大存储空间 23 第一章绪论 三 算法效率的度量度量方法 1 事后统计法 根据运行结果去统计时间2 事前分析估计法一个程序的执行时间取决于 1 算法的选取主观因素2 问题的规模3 语言的选取4 编译程序所产生的机器代码质量5 机器执行指令的速度客观因素中的问题的规模是无法抗拒的 而其它因素则是可以改变的 因此算法效率主要考虑1 和2 两方面 客观因素 24 第一章绪论 一般地 算法中的基本操作的重复执行次数是问题规模n的某个函数f n 因此算法的时间度量记作 T n O f n 在分析基本操作的重复执行次数时 可以考虑最深层循环语句的执行频度 为什么 例1 x s x O 1 2 for i 0 i n i x s i O n 3 for i 0 i n i for j 0 j n j x s i j O n2 4 for i 0 i n i O n3 for j 0 j n j for k 0 k n k x s i j k 为什么 25 第一章绪论 常见的算法时间复杂度还有 O logn O nlogn O 2n O nk 其中n为问题规模 常见函数的增长率 平均时间复杂度 对所有可能的输入数据的期望值 最坏时间复杂度 最坏时间的一个上界 26 第一章绪论 四 算法的存储空间需求类似于时间复杂度 空间复杂度记作 S n O f n 空间占用考虑 指令 常量 变量 输入数据 为完成算法而增设的临时单元 辅助单元 在分析空间复杂度时常指辅助单元的空间量 有时也包含输入数据所占用的存储空间量等 在比较时依问题说明而定 算法设计追求 较少的T n 和S n 减少T n 往往是科学研究的一个重要方面 27 作业 28 第8题编程和上机练习题 第18题 数据自定 第19题 29 第二章线性表 线性表的特点 1 存在唯一一个被称做 第一个 的数据元素 2 存在唯一一个被称做 最后一个 的数据元素 3 除第一个元素外 每个元素均有一个前驱 3 除最后一个元素外 每个元素均有一个后继 2 1线性表的类型定义 线性表 liner list 是N个元素的有限序列 n 0称为长度 元素 item 称为记录 由若干数据项组成 属于同一数据对象 文件 file 含有大量记录 record 的线性表 基本操作 访问 求长度 插入 删除等 30 第二章线性表 线性表的抽象数据类型 ADTList 数据对象 D ai i 1 2 3 n n 0 数据关系 R1 ai D i 1 2 n 基本操作 initList L DestoryList L ClearList L ListEmpty L ListLength L GetElem L i e LocateElem L e compare PriorElem L cur e next e NextElem L cur e next e Listinsert L i e ListDelete L i e ListTraverse L visit ADTList 31 第二章线性表 例2 1利用表LA和LB分别表示两个集合A和B 求A A B voidunion list union 算法思想 把lb中不属于la的元素加入到la的后面 时间复杂度 O la len lb len 32 第二章线性表 例2 2两个线性表la和lb均以非递减顺序存放 将la和lb归并到lc中后仍以非递减顺序存放 voidMergeList listla listlb list MergeList 时间复杂度 O la len lb len 33 2 2线性表的顺序表示与实现 线性表的循序表示 用一组地址连续的存储单元依次存储线性表的数据元素 数据元素的存储位置LOC ai 满足下列关系 LOC ai 1 LOC ai LOC ai LOC a1 i 1 l 线性表数据元素的关系 逻辑上相邻在物理上也相邻 34 第二章线性表 线性表的顺序存储 用高级语言中的一维数组实现 其描述如下 defineList init size100 初始分配量 defineListincrement10 分配增量typedefstruct Elemtype elem 存储空间基址intlength 当前长度intlistsize 当前分配的存储容量 以sizeof ElemType 为单位 sqlist 35 第二章线性表 初始化线性表 StatusinitList sqlist 访问线性表的第i个元素 在C语言中用L elem i 1 实现 36 第二章线性表 插入算法 在线性表L中的第i个位置前插入新元素e StatusListinsert sq sqlist 元素后移 时间复杂度 O n n为线性表长度 37 第二章线性表 删除算法 在线性表L中删除第i个元素 并返回给e StatusListdelete sq sqlist 元素前移 时间复杂度 O n n为线性表长度 38 第二章线性表 查找 在线性表L中查找第1个值与e满足compare 的元素的位序 intLocateElem sq sqlistL ElemTypee status compare Elemtype Elemtype 成功返回位序 否则返回0 i 1 p l elem while i l length locateElem sq 39 第二章线性表 两有序序列归并 voidmergelist sq sqlistla sqlistlb sqlist 40 第二章线性表 2 3线性表的链式表示与实现 线性表的顺序表示的特点 逻辑上相邻的两个元素在物理位置上相邻 插入 删除操作需移动大量数据 平均移动一半 但能随机访问 线性表的链式表示的特点 逻辑上相邻的两个元素在物理位置上不相邻 插入 删除操作不需移动数据 但不能随机访问 2 3 1线性链表 数据域指针域 Node 指示下一个元素的地址 链表 n个结点 ai 1 i n 的存储映象 链结成一个链表 即为线性表 a1 a2 an 的链式存储结构 单链表 链表中的每个结点只包含一个指针域 41 第二章线性表 链表表示示例 线性表 zhao qian sun li zhou wu zheng wang 的链式存储 存储地址数据域指针域 1li437qian1313sun119wangNULL25wu3731zhao737zheng1943zhou25 头指针 尾指针 42 第二章线性表 线性表的存储结构 typedefstructLNode elemtypedata 数据域structLnode next 指针域 LNode LinkList 链表类型 头结点 为了方便 人为添加进来的结点 访问下一个结点 设P指向元素 结点 ai 则p next指向下一个元素 结点 ai 1 43 第二章线性表 GetElem在单链表中的实现 StatusGetElem l linklistl inti elemtype GetElem l 44 第二章线性表 在单链表中插入一个元素 a 初始状态 在a后面插入元素x b 构造x结点s 将x指针链到b p后面 操作 s next p next c 把x结点s链到p后面 操作 p next s 注意操作次序 45 第二章线性表 在单链表中插入一个元素的算法 Statuslistinsert L linklisi 46 第二章线性表 在单链表中删除一个元素 初始 删除元素b a 保存b结点q p next b 删除b结点p next p next next c 释放b结点free q 注意操作要点与步骤 47 第二章线性表 在单链表中删除一个元素的算法 Statuslistdelete L linklisi时间复杂度为O n 48 第二章线性表 创建链表 方法1 每次将数据插入到头结点的后面 逆序输入 Voidcreatlist L linklist 49 第二章线性表 创建链表 方法2 每次将数据插入到链表尾部 正序输入数据 Voidcreatlist L linklist 50 第二章线性表 链表归并 特点 不增加空间 只改变原链指针 voidmergelist l linklist 时间复杂度O m n 51 第二章线性表 2 3 2循环链表 特点 一个结点的指针域指向头结点 链表形成一个环 非空表 操作 同单链表 只需改变循环判别条件 有时为了方便 可以只设立尾指针 而不设头指针 如用尾指针表示的两个循环链表的连接运算 其算法时间为O 1 52 第二章线性表 2 3 3双向链表 1 单链表的不足 查找前趋结点的时间为O n 因为必须从头找起 为此设立双向链表 2 双向链表结点有两个指针域 一个指向其前趋 一个指向其后继 空表 非空表 53 第二章线性表 3 双向链表的存储结构 Typedefstructdulnode elemtypedata structdulnode prior structdulnode next dulnode dulinklist 设d为双向循环链表中的一个结点 则显然有 d next prior d prior next d p p a 删除前 删除P结点 b 删除后 删除操作 1 2 54 第二章线性表 删除算法 Statuslistdelete dul dulinklidt 55 第二章线性表 插入算法 Statuslistinsert dul dulinklidt 注意顺序 先挂后断 56 第二章线性表 2 4一元多项式表示及相加 一 多项式的表示 设多项式按升幂写成 pn x p0 p1x p2x2 pnxn则可用n 1个系数唯一确定 因此可用线性表P来表示 p p0 p1 p2 pn 其中指数隐含在其系数序号中 二 多项式存储结构的思考 1 顺序存放 适用于多项式指数分布比较均匀的情形 2 链表存储 适用于多项式指数分布比较稀疏的情形 此时 多项式结点结表示为 三 多项式相加算法 实际上是归并算法的改进 注意合并 删除等 57 第三章栈和队列 本章重点 1 栈结构的表示与实现2 队列结构的表示实现3 栈与队列的典型应用 难点 1 栈的应用2 回溯算法 表达式计算方法 编译 实验报告 用C语言实现迷宫求解算法 58 第三章栈和队列 3 1栈 一 栈的ADT定义与特点 栈 stack 是限定在表尾进行插入或删除操作的线性表 栈顶 top 进行插入或删除的一端 栈底 bottom 线性表中固定不动的一端 top bottom push pop 1 概念 2 特点 LiFO LastinFirstOut 59 第三章栈和队列 ADTStack 数据对象 d ai ai elemset i 1 2 n n 0 数据关系 r1 ai 1 ai D i 1 2 n 基本操作 initstack S destorystack S clearstack S stackempty s stacklength s gettop s e push s e pop s e stacktraverse s visit ADTstack 60 第三章栈和队列 3 1 2栈的表示与实现 和线性表一样 栈同样有两种存储实现 即顺序与链式存储 本节只讨论栈的顺序存储 definestack init size100 definestackincrement10typedefstruct selemtype base 栈底selemtype top 栈顶指针 指向栈顶的空位置intstacksize 栈空间大小 sqstack an top bottom push pop 61 第三章栈和队列 基本算法 Statusinitstack sqstack Statusgettop sqstacks selemtyope 62 第三章栈和队列 基本算法 Statuspush sqstack Statuspop sqstack pop 63 第三章栈和队列 3 2栈的应用 一 数制转换十进制到其它进制的转换 其结果的生成是一个典型的LiFO 后进先出 类型 Voidconversion intn intp n转换为p进制数 initstack s while n push s n p n n p while stack empty s pop s e printf d e 二 括号匹配的检查检查表达式中 的匹配情况 设立一个栈 读入 则进栈 读入 则出栈 当表达式结束时栈恰为空 匹配 其余任何情况均出错 64 第三章栈和队列 3 2 3行编辑程序 通常做法 数据输入缓冲区 如发现错误及时改正 待输入回车键后存入用户数据区 如 删除前一个字符 删除本行前面所有字符 如输入 whli ilr e s s outcha putchsr s 等价于 while s putchar s 为此可将缓冲区设为一个栈 输入非 则压栈 是 则弹栈 是 则清空栈 65 第三章栈和队列 算法 Voidlinedit initstack s Ch getchar While ch EOF while ch EOF lineedit 66 第三章栈和队列 3 2 4迷宫求解 入口 出口 思想 穷举求解 即从入口出发 沿某一方向前进 若能走 则继续 否则 沿原路退回一格 回溯 换一个方向继续 直到到达出口 成功 或已搜索所有可能路径 失败 计算机走宫应解决的几个问题 1 迷宫存放 通与不通的表示2 当前位置3 搜索方向4 改变方向5 当前路径6 前进一步7 后退一步8 实现方法 67 第三章栈和队列 描述算法 设定入口位置 当前位置 do 若当前位置可通则 将当前位置插入栈顶 若该位置是出口位置 则结束 否则改变当前位置到东邻位置 否则若栈不空且栈顶位置尚有其它方向未搜索则设定新的当前位置为栈顶位置的下一邻块若栈不空且栈顶位置四周不通则 删去栈顶位置 若栈不空 则重新测试新的栈项位置 直到找到一个可通的邻块或栈空 while 栈不空 68 第三章栈和队列 栈的元素结构 typedefstruct intord 路径号posttypeseat intdi 方向 selemtype Statusmazepath mazetypemaze poptypestart poptypeeds initstack s curpos start Curstep 1 do if pass curpos footprint curpose e curstep curpos 1 push s e if curpos end return true curpos nextpos curpos 1 curstep 69 第三章栈和队列 else 当前位置不通 pop s e while e di 4 mazepath 算法续上页 70 第三章栈和队列 3 2 5表达式求值 方法 利用编译原理知识中的算法优先关系表对日常表达式进行运算 要求 从键盘以字符串方式输入一算术表达式 只含 和括号运算 建立算符优先表为计算 设立两个栈 OPTR 运算符栈和OPND 运算操作数栈按下面算法求值 1 OPND置空 OPTR清空再将 压栈2 读表达式字符 若是操作数 则进OPND栈 是运算符 则和OPTR栈顶元素比较 选择进栈或运算 重复上述过程 直到结束 71 第三章栈和队列 OperandtypeEvaluateExpression initstack optr push optr initstack opnd c getchar while c gettop optr if in c op push opnd c c getchar elseswitch precde gettop optr c case pop optr theta pop opnd b pop opnd a push onpd operate a theta b break whilereturngettop opnd 表达式运算算法 72 第三章栈和队列 3 4队列 一 抽象数据类型队列的定义 特点 队列是一种先进先出表 FiFO 插入和删除分别在队列的两端进行 类似于日常生活中的各种排队现象 队头 FRONT 允许删除的一端队尾 REAR 允许插入元素的一端典型应用 操作系统中作业队列 就绪进程等 a1a2a3 an front rear out in 73 第三章栈和队列 ADTqueue 数据对象 d ai ai elemset i 1 2 n n 0 数据关系 r1 ai 1 ai D i 1 2 n 基本操作 a1为队头an为队尾initqueue Q destoryqueue Q clearqueue Q queueempty Q queuelength Q Gethead Q e enQueue Q e DeQueue Q e queuetraverse Q visit ADTqueue 74 第三章栈和队列 双端队列 队列两端均可以插入和删除 形变 a1a2a3 an end1 end2 a1a2a3 an end1 end2 a1a2a3 an end1 end2 75 第三章栈和队列 3 4 2链队列 两个指针 一个指向队头 一个指向队尾 a1 an 1 a2 an Q front Q rear a1 an 1 a2 an Q 其操作实现同链表运算 详见教材P62 76 第三章栈和队列 3 4 3循环队列 在队列顺序存储方式中 数组存储 为充分利用给定的存储空间和避免队列操作时数据移动 我们需将队列改造成为循环队列 01 maxsize 1 q front q rear 队列元素 关键问题 队空与队满条件的区别 q front q rear 区别方法 1 专设标志位2 腾空一个单元 当队尾追上队头时队满 反之当队头追上队尾时队空 一般常采用第2种方法 77 第三章栈和队列 算法 循环队列 顺序存储 Tyopedefstruct Qelemtype base intfront intrear Squeue Statusinitqueue squeue 队列初始化 intqueuelength squeueq returnq rear q front maxqsize maxqsize 队长度 78 第三章栈和队列 statusenqueue squeue 入队 statusdequeue squeue 出队 79 第4章串 字符串的特点 非数值计算问题 因而其操作比数值问题要复得多 字符串的应用非常广泛 如源程序 文字处理 事物处理 信息检索 自然语言翻译系统及音乐分析程序等均以字符串数据作为处理对象的 4 1串类型定义 串 String 是由0个或多个字符的有限序列 表示 s a1a2 an n 0 空串 长度为0 即n 0 的字符串称为串 子串 串中任意个连续的字符组成的子序列 主串 包含子串的串位置 字符在序列中的序号 80 第4章串 串相等 串长度相等并且对应字符全部相等 空格串 同一个或多个空格字符组成的串 ADTstring 数据对象 D ai ai Characterseti 1 2 n n 0 数据关系 Ri ai Di 1 2 n 基本操作 destorystring s strassign t chars concat t s1 s2 strcopy t s substring sub s pos len strempty s index s t pos strcompare s t replace s t v strlength s strinsert s pos t claerstring s strdelete s pos len ADTstring 81 第4章串 算法例子 intindex strings stringt intpos if pos 0 n strlength s m strlength t i pos while i n m 1 substring sub s i m if str compare sub t 0 i elsereturni return0 82 第4章串 4 2串的表示与实现 4 2 1定长顺序存储表示一般用定长数组实现 definemaxstrlen255typedefunsignedcharsstring maxstrlen 1 0号单元存放字符串的长度算法 1 串连接concat t s1 s2 分三种情况 s1 0 s2 0 maxstelens1 0 maxstrlen s1 0 s2 0 maxstelens1 0 maxstrlen 83 第4章串 Statusconcat sstring returnuncut 84 第4章串 Statussubstring sstring 2 求子串substring sub s pos len 首先进行合法检查如合法 则求出其中的子串部分 85 第4章串 4 3串的模式匹配算法 4 3 1求子串位置的定位函数 子串的定位操作通常称作串的模式匹配 它是字符串处理系统中最重要的操作之一 intindex sstrings sstringt intpos S为源串 T为模式串 pos为S中的起始位置 i pos j 1 while it 0 returni t 0 elsereturn0 匹配成功 返回其位置 否则返回0 86 第4章串 应用 文本编辑 求子串例子 s ababcabcacbab t abcac pos 1 第一趟 ababcabcacbababc 第二趟 ababcabcacbaba 第四趟 ababcabcacbaba 第三趟 ababcabcacbababcac 第五趟 ababcabcacbaba 第六趟 ababcabcacbababcac i 3 i 2 i 7 i 4 i 5 i 11 j 3 j 1 j 5 j 1 j 1 j 6 返回坐标6 87 第4章串 intstrlen char s 98年程序员下午试题一 char t s while t returnt s 1 intcommstr char str1 char str2 int sublen char s1 s2 intcount 0 len1 len2 k j i p len1 strlen str1 len2 strlen str2 if len1 len2 s1 str1 s2 str2 else len2 len1 s1 str2 s2 str1 应用举例 求两个字符串的最长公共子串和它们的个数 88 第4章串 for j len2 j 0 j for k 0 k j0 break sublen count 0 j 0 returncount main char st1 agabcdeagfabcdeaaa char st2 gaaabcdeafd intx y x commstr st1 st2 斜线为待填项 89 第4章串 4 4串的操作应用 一 文本编辑文本编辑程序是一个面向用户的系统服务程序 广泛应用于源程序的输入和修改 书报排版系统 办公自动化系统等 基本操作 串的查找 串的插入 串的删除操作等 二 建立词索引表从书目文件生成有序词表的方法 1 从书目文件中读入一个书目单2 从书目串中提取所有关键词插入词表3 对词表的每一个关键词 在索引表中进行查找 并作相应的修改 重复上过程 直到书目文件的结尾 90 第5章数组与广义表 本章所讨论的数组是线性表的扩充 即线性表的每个元素均是一种数据结构 俗称多维数组 广义表指 表中有表 即线性表中的每个元素可能仍然是一个线性表 5 1数组定义 ADTArray 数据对象 ji 0 1 bi 1 i 1 2 n d aj1j2 jn n 0 称为数组的维数 bi是第i维的长度 ji是数组第i维下标 aj1j2 jn Elemset 数据关系 R R1 R2 Rn 91 Ri 0 jk bk 11 k n且k i 0 ji bi 2 aj1 ji jn aj1 ji 1 jn D i 1 2 n 基本操作 iinitarray A n bound1 boundn 初始化Destoryarray A 销毁数组Value A e index1 indexn 取值Assign A e index1 indexn 赋值 ADTarray 第5章数组与广义表 n维数组中含有b1 b2 bn个元素 n 1为线性表 92 第5章数组与广义表 二维数组定义 a00a01a02 a0 n 1a00a01a02 a0 n 1 a00a01a02 a0 n 1 Am n a00a01 a0 n 1 a10a11 a1 n 1 am 1 0am 1 1 am 1 n 1 Am n a00a01 a0 n 1a10a11 a1 n 1 am 1 0am 1 1 am 1 n 1 Am n a0a1 am 1 a0a1 an 1 用行向量表示 用列向量表示 矩阵表示 其中ai代表数组中第i行 其中aj代表数组中第j行 93 第5章数组与广义表 5 2数组的顺序表示和实现 由于数组运算没有插入和删除 因此用顺序表示是自然的 数组存放 行主序 rowmajororder 列主序 columnmajororder 存储位置 以行主序为例二维数组由m n组成 每个元素占L个存储单元 则 LOC i j LOC 0 0 i n j L 0 i m 1 0 j n 1 推广 已知n维数组每维长度分别为b1 b2 bn 每个元素占L个存储单元 则 Loc j1 j2 jn loc 0 0 0 b2 b3 bn j1 b3 bn j2 bn jn 1 jn L loc 0 0 0 c1 j1 c2 j2 cn 1 jn 1 cn jn 其中 cn L ci 1 bi ci 2 i n 为映象函数 94 第5章数组与广义表 数组的顺序存储表示与实现 definemax dim8typedefstruct 数组结构elemtype base 数组元素基址intdim 数组维数int bounds 数组维界基址int constants 数组映象函数常量基址 array 此结构表示的优点可以实现去态维数的数组 Statusinitarray array 95 第5章数组与广义表 elemtotal 1 计算数组元素总个数for i 0 i 0 i 见幻灯片87a constants i a bounds i 1 a constants i 1 returnok 96 第5章数组与广义表 Statusdestory array Ststuslocate arraya intsubscript int 97 第5章数组与广义表 Statusvalue arrayA elemtype Statusassign array 98 第5章数组与广义表 5 3矩阵的压缩存储 矩阵压缩存储 为多个值相同的元素只一个存储空间 对0不分配空间 特殊矩阵 假设多个值相同的元素或零元素在矩阵中的排列具有一定的规律 稀疏矩阵 矩阵中零元素的数目占绝大多数 5 3 1特殊矩阵 一 对称矩阵1 性质 若n阶二维矩阵A中的元素满足下列性质 aij aji0 i j n 12 压缩存储 为每一对称元素只分配一个存储单元 则n2个数组元素只需n n 1 2个存储单元 99 第5章数组与广义表 不失一般性 考虑行主序存放下 只存储其下三角 含对角线 中的元素 假设以一维数组sa n n 1 2 作为n阶矩阵A的存储结构 则sa k 和矩阵元素aij之间存在着如下一一对应关系 i i 1 2 j 1当i jj j 1 2 i 1当i j k 反过来 已知sa k 中的k 如何确定其元素在二维数组中的位置 i j 基本思想 利用循环进行判别 此问题要求学生编写相应的算法 讲解要点 利用图例分析上述公式的推导过程 100 第5章数组与广义表 二 上 下 三角矩阵指矩阵中的下 上 三角 不包括对角线 中的元素均为常数c或0的n阶矩阵 其相邻存储与对称矩阵相邻相似 外加一个常数c的存储单元 如c为0 则此单元还可以省略 三 对角矩阵所有非0元素均集中在主对角线为中心的带形区域中 0 0 n条对角线 a00a010a10a11a12a21a22a23 0an 1 n 2an 1 n1 写出三对角线矩阵元素的一维数组存放关系的算法或公式 101 第5章数组与广义表 5 3 2稀疏矩阵 稀疏因子 设一m n的矩阵中有t个非0元素 则令 t m n 称 为稀疏因子 稀疏矩阵 通常称 0 05时的矩阵为稀疏矩阵 一 稀疏矩阵的抽象类型 二 稀疏矩阵的压缩存储 三元组 用 i j aij 唯一确定稀疏矩阵的非0元素 其中i j表示元素的位置 坐标 aij表示元素的值 稀疏矩阵的三元组存储 所有非0元素的三元组存储 外加矩阵行 m 列值 n 的存储 102 第5章数组与广义表 012900000000000 3000014000240000018000001500 7000 M 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 存储行数6 列数7 三元组存放 1 三元组顺序表示存储 defineMAXSiZE1000typedefstruct 三元组inti j elemtypee tripletypedefunion tripledata MAXSiZE 1 intmu nu tu 矩阵行数 列数 非0元素个数 Tsmatrix 稀疏矩阵 103 第5章数组与广义表 2 矩阵三元组的转置 ijv121213931 3361443245218611564 7矩阵A行数6 列数7 ijv13 3161521122518319342446 76314矩阵B行数7 列数6 左连两个矩阵互A B为转置矩阵 算法 1 交换矩阵的行 列值2 交换三元组的i和j3 重排三元组的次序 按i值重排 104 第5章数组与广义表 StatustransposeSmatrix tsmatrixM tsmatrix transposesmatrix 矩阵转置 算法分析与比较 当tu mu nu时本算法效率提高了 105 第5章数组与广义表 改进算法 希望在转换过程中能直接计算出列元素的存放位置 从而省去排序过程 为此通过计算首先确定列的第一个元素在转置后的三元组中的位置 引入 为此引入num和cpot两个向量 num col 表示矩阵M中第col列中非0元素的个数cpot col 表示矩阵M中第col第1个非0元素在b data中的位置 则 cpot 1 1 Cpot col cpot col 1 num col 1 2 col a nu 矩阵M的cpot的值 106 第5章数组与广义表 StstusfastransposeSmatrix tsmatrixM tsmatrix fastransposesmatrix 矩阵转置 107 第6章树和二叉树 本章重点讨论二叉树的存储结构及其种种操作 并研究树和森林与二叉树的转换 最后介绍几个重要例子 6 1树的定义与基本术语 一 树的定义 树 Tree 是n n 0 个结点的有限集 空树 树的结点个数为0 n 0 非空树 树的结点个数 0 n 0 1 它有且仅有一个特定的称为树根 Root 的结点 2 当n 1时 其余结点可分成m m 0 个互不相交的有限集 其中每个有限集本身又是一棵树 称为根的子树 subtree 108 第6章树和二叉树 树的示例 A A B D F G C E J L K i H 层次 1 2 4 3 空树 一般的树 只有根结点的树 思考 右边的树中有多少棵子树 109 第6章树和二叉树 A B C D E H F i G J L K A B F E H i C D G J K L ABEHiFCDGJKL 图的其它三种表示 110 第6章树和二叉树 树的ADT ADTtree 数据对象D 具有相同特性的数据元素的集合 数据关系R 若D为空集 则称为空集 若D仅含1个元素 则R 该元素为根 否则R H H满足如下二元关系 1 D中存在唯一的称为树根的元素root 它在H下元前驱 2 若D root 则存在它的互不相交的划分D1 D2 Dm m 0 且在Di中存在唯一的Xi Di 有 H 3 上述划分中以X1 x2 Xm为根的树称为root的子树 111 第6章树和二叉树 基本操作 inittree T DestoryTree T CcreatTree t definition ClearTree T TreeEmpty T TreeDepth T Root T Value T cur e Assign T cur e value Parent T cur e LeftChild T cur e RightSibling T cur e insertChild T p i c DeleteChild T p i TraverseTree T visit ADTTree 112 第6章树和二叉树 结点 包含1个元素及若干指向其子树的分支结点的度 Degree 结点的子树个数叶子 Leaf 度为0的结点 又称终端结点分支结点 度不为0的结点 又非叶结点树的度 内部结点的度最大的值 孩子 Child 结点的子树的根双亲 Parent 孩子定义中的结点称为其子树根的双亲兄弟 同一双亲的孩子祖父 子孙 堂兄弟等概念的理解 层次 level 即家簇中的代数 根为第一层 下推树的深度 depth 或高度 树的最大层数 有序树 无序树 森林的定义 113 第6章树和二叉树 6 2二叉树 1 二叉树的定义二叉树是另一种树型结构 它的是每个结点最多只有二棵子树 并且 这二棵子树中有左右之分 不能颠倒 ADTbinarytree 数据对象D 具有相同特性的数据元素的集合 数据关系R 若D为空集 R 则称为空二叉树 若D非空 则R H 1 D中存在唯一的称为树根的元素root 它在H下元前驱 2 若D root 则D root Dl Dr 且Dl Dr 3 若Dl 则Dl中存在唯一元素xl H 且存在Dl上的关系Hl H 若Dr 则Dr中存在唯一元素xr H 且存在Dr上的关系Hr H H Hl Hr 4 Dl Hl 是一棵二叉树 称为根的左子树 Dr Hr 是一棵二叉树 称为根的右子树 114 第6章树和二叉树 二叉树的五种形态 6 2 2二叉树的性质 性质1 在二叉树的第i层上至多只有2i 1结点 i 1 性质2 深度为k的二叉树至多只有2k 1个结点 k 1 性质3 对任何一棵二叉树T 如果其终端结点的个数为n0 度为2的结点个数为n2 则n0 n2 1定义 深度为k的二叉树且结点个数等于2k 1 则称为满二叉树 对满二叉树的编号从上至下 从左至右进行编号 如一棵深度为k 有n个结点的二叉树恰好位于一棵深度为k的满二叉树的前n个编号的位置 则称为完全二叉树 115 第6章树和二叉树 性质4 具有n个结点的完全二叉树的深度为 log2n 1性质5 如果对一棵有n个结点的完全二叉树的结点按层次顺序编号 从1到n 则对任意结点i 1 I 1为根结点 无双亲 i 1则其双亲结点是 n 2 2 若2i n 则结点i无左孩子 否则其左孩子结点是2i 3 若2i 1 n 则结点i无右孩子 否则其右孩子结点是2i 1 6 2 3二叉树的存储结构 1 顺序存储 definemax tree size100TypedefTelemtypeSqbitree max tree size Sqbitreebt 结构简单 对完全二叉树存储十分有效 但不用于一般的二叉树的存储结构 116 第6章树和二叉树 2 链式存储结构 TypedefstructbitNode Telemtypedata structbitNode lchild rchild bitNode bitree 容易证明 一棵包含n个结点的二叉树的链式表中有n 1个空指针域 6 3二叉树的遍历 三种遍历方法 TLR LTR LTR 它