2011 2012 学年第 学期
教 案
课程名称 数结构 教材数结构（C语言版）
教学时数 56 课程性质 必修
课班级（数）信（53）
信息 系（部） 信 教研室
课教师
山东科技学泰山科技学院
课 时 授 课 计 划
20112012学年第 二学期 第1周
授 课 日 期
2月 20 日
星期1
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 第1章 绪 1112
教学目求：
1 解数结构基概念
2 理解常术语
教学重点：
数结构基概念术语
教学难点：
数元素间四种结构关系
作业参考书：
1 什数结构？
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：介绍——开课——引入——展开——举例——结——作业
介绍课程介绍 约8min
课时：64
二引入 约2min
问题提出引入
三讲课进程设计
11 什数结构
111数结构关系 约15min
数结构 +算法 程序
程序设计 计算机处理问题编制组指令集
算法 处理问题策略
数结构 问题数学模型
112计算机应特点： 约25min
l) 处理数量具定关系
2) 操作单纯数值计算更需进行组织理检索
举例说明：
1) 学生成绩表 2)井安棋弈 3)交通理
结
计算机操作象关系更加复杂操作形式单纯数值计算更具定关系数进行组织理称非数值性处理计算机够更效进行非数值性处理必须弄清楚操作象特点计算机中表示方式操作具体实现手段
12 基概念术语
111数数结构 约20min
数：客观事物符号表示
输入计算机中计算机处理符号集合计算机操作象总称计算机处理信息某种特定符号表示形式
数元素：数（集合）中体数结构中讨基单位
数象：性质相数元素集合数子集
数结构：相互间存种种特定关系数元素集合种集合称结构
数逻辑结构结四类
种类
特征
示例
集合
元素间松散关系
线性结构
元素间严格关系
面成绩表中元素
树形结构
元素间严格关系
图状结构（网状结构）
元素间关系
数结构形式定义数结构二元组
数存储结构 ：—— 逻辑结构存储器中映
数元素映象方法：计算机中存储信息单位：位8位字节两字节字字节字更二进制位称位串逻辑描述中位串称元素结点
关系映象方法：序映象 链式映象
122数类型 约5min
数类型 值集合定义集合 组操作总称
123抽象数类型 约20min
指数学模型定义数学模型组操作
关键：关心逻辑特征需解存储方式定义样必关心存储
抽象数类型表示法：
三元组表示：（DSP）
中D数象SD关系集PD基操作集
书中定义格式：
ADT 抽象数类型名{
数象：<数象定义>
数关系：<数关系定义>
基操作：<基操作定义>
}ADT 抽象数类型名
ADT 两重特征
数抽象 数封装
四次课结： 约3min
1 熟悉名词
2 术语含义
3 掌握基概念
五作业 约2min
2 什数结构？
课 时 授 课 计 划
20112012学年第 二 学期 第1周
授 课 日 期
2月 24日
星期5
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 抽象数类型表示实现 算法算法分析
教学目求：
类C语言种句型算法描述规范
教学重点：
类C语言种句型算法描述规范
教学难点：
类C语言种句型算法描述规范
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：复——引入——展开——举例——结——作业
复： 约5min
1数结构基概念
2基术语
二引入 约2min
程序设计程遇问题引入
三讲课进程设计
13 抽象数类型表示实现
131基操作： 约15min
AssignComplex( &Z v1 v2 )
操作结果：构造复数 Z实部虚部
分赋参数 v1 v2 值
DestroyComplex( &Z)
操作结果：复数Z销毁
GetReal( Z &realPart )
初始条件：复数已存
操作结果：realPart返回复数Z实部值
GetImag( Z &ImagPart )
初始条件：复数已存
操作结果：ImagPart返回复数Z虚部值
Add( z1z2 &sum )
初始条件：z1 z2复数
操作结果：sum返回两复数z1 z2 值
132书采类C语言作简说明 约18min
1 预定义常量类型
2数结构存储结构typedef
3算法描述函数形式：
4 算法描述中赋值语句形式：
5 算法描述中选择结构语句形式：
6 算法描述中循环结构语句形式：
7 描述算法中结束语句形式：
8 算法描述中输入输出语句形式：
9 算法描述中注释格式：
10 算法描述中扩展函数：
11逻辑运算约定
14 算法算法分析
141算法 约10min
算法解决某类问题规定限长操作序列算法必须满足五重特性：
1．穷性 2．确定性 3．行性 4．输入 5．输出
142算法设计原 约10min
设计算法时通常应考虑达目标：
1．正确性2 读性3．健壮性4．高效率低存储量需求
143算法效率衡量方法准 约20min
通常两种衡量算法效率方法
事统计法 缺点：1．必须执行程序 2．素掩盖算法质
事前分析估算法 算法执行时间相关素：1．算法选策略2．问题规模3．编写程序语言4．编译程序产生机器代码质量5．计算机执行指令速度
算法 控制结构 + 原操作 （固数类型操作）
算法执行时间致等语句执行时间总语句执行时间指该条语句执行次数执行次需时间积
计算时间复杂度时采记号O数学符号严格数学定义：T(n)f(n)定义正整数集合两函数T(n)O(f(n))表示存正常数cn0n>n0时满足0程序分析法：
1 执行条读写赋值语句O(1)时间2次执行系列语句时间准
3判断语句耗时执行语句时间检验条件需O(1)4循环语句运行时间次叠代中执行循环体检验循环条件耗时常法准
算法两部分时间复杂度T1(n)o(f(n)) T2(n)o(g(n)) O：
求准 T1(n)+ T2(n)O(max(f(n)g(n)) 法准 T1(n)* T2(n)O( (f(n )*g(n))
144算法存储空间需求 约10min
算法空间复杂度定义
S(n) O(g(n))
表示着问题规模 n 增算法运行需存储量增长率 g(n) 增长率相
算法存储量包括
1．输入数占空间2．程序身占空间3．辅助变量占空间
四结： 约5min
1 理解算法五素确切含义
2 掌握计算语句频度估算算法时间复杂度方法
五作业 约5min
1试编写算法求元项式Pn(x)a0+a1x+a2x2+a3x3+…anxn值Pn(x0)确定算法中语句执行次数整算法时间复杂度求时间复杂度规定算法中求幂函数注意：题中输入ai(i01…n)xn输出Pn(x0)通常算法输入输出采列两种方式：
• （1）通参数表中参数显式传递（2）通全局变量隐式传递
• 试讨两种方法优缺点题算法中认较种方式实现输入输出
课 时 授 课 计 划
20112012学年第 二学期 第2周
授 课 日 期
2月 27 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 线性表类型定义 线性表序表示实现
教学目求：
1掌握线性表概念类型定义
2掌握线性表序表示实现方法
教学重点：
线性表类型定义
线性表序表示实现方法
教学难点：
线性表类型定义
线性表序存储实现方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：复——引入——展开——举例——结
引入 约3min
序算法引入
二讲课进程设计
2．1线性表类型定义
1211线性表定义 约27min
线性表n（n≥0）类型相数元素组成限序列
抽象数类型线性表定义：
ADT List {
数象
D＝{ ai | ai ∈ElemSet i12n n≥0 }
{称 n 线性表表长 称 n0 时线性表空表}
数关系
R1＝{|ai1 ai∈D i2n }
基操作：
结构初始化操作：
InitList( &L )
操作结果：构造空线性表L结构销毁操作：
DestroyList( &L )
初始条件：线性表 L 已存操作结果：销毁线性表 L
引型操作
ListEmpty( L )（线性表判空）
ListLength( L )（求线性表长度）
PriorElem( L cur_e &pre_e )（求数元素前驱）
NextElem( L cur_e &next_e )（求数元素继）
GetElem( L i &e )（求线性表中某数元素）
LocateElem( L e compare( ) )（定位函数）
ListTraverse(L visit( ))（遍历线性表）
加工型操作
ClearList( &L )（线性表置空）
PutElem( &L i &e )（改变数元素值）
ListInsert( &L i e )（插入数元素）
ListDelete(&L i &e) （删数元素）
212举例 约10min
两线性表合LALB
22 线性表序表示实现
221序映象 约15min
—— x 存储位置 y 存储位置间某种关系表示逻辑关系
简单种序映象方法： 令y存储位置x存储位置相邻线性表基操作序表中实现
InitList(&L) 结构初始化
LocateElem(L e compare()) 查找
ListInsert(&L i e) 插入元素
ListDelete(&L i) 删元素
211线性表操作 约20min
ListInsert(&L i e)实现：
首先分析
插入元素时线性表逻辑结构发生什变化？
线性表操作
ListDelete(&L i &e)实现：
首先分析：
删元素时线性表逻辑结构发生什变化？线性表类型实现
212线性表序存储结构特点： 约20min
种简单方便存储方式求线性表数元素次存放连续存储单元中利数元素存储序表示相应逻辑序种存储方式属静态存储形式 暴露问题
(1)做插入删元素操作时会产生量数元素移动 (2)长度变化较线性表次性分配足够存储空间空间常常充分利
(3)线性表容量难扩充
三结 约5min
1解线性表逻辑结构特性数元素间存着线性关系计算机中表示种关系两类存储结构序存储结构链式存储结构前者表示线性表简称序表者表示线性表简称链表
2熟练掌握两类存储结构描述方法线性表种基操作实现
课 时 授 课 计 划
20112012学年第 二 学期 第2周
授 课 日 期
3月 3 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 线性表链式表示实现 元项式表示相加
教学目求：
1掌握线性链表单链表静态链表概念表示实现方法
2掌握循环链表概念
3掌握双链表表示实现
教学重点：
1线性链表单链表表示实现方法
2双链表表示实现
教学难点：
1线性链表
2双链表存储表示
作业参考书：
写算法单链表中值重复结点删结果表中结点值均相
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：复——引入——展开——举例——结——作业
复 约5min
复线性表概念
二引入 约2min
线性表表示方便引入
三讲课进程设计
23 线性表链式表示实现
线性表序存储结构特点： 约10min
种简单方便存储方式求线性表数元素次存放连续存储单元中利数元素存储序表示相应逻辑序种存储方式属静态存储形式
暴露问题
(1)做插入删元素操作时会产生量数元素移动
(2)长度变化较线性表次性分配足够存储空间空间常常充分利
(3)线性表容量难扩充
231单链表 约10min
组址意存储单元存放线性表中数元素（组存储单元连续连续）
232结点单链表 C 语言描述 约10min
233单链表操作实现 约13min
生成链表程结点逐插入程
操作步骤：
1建立空表
2输入数元素an建立结点插入
3输入数元素an1建立结点插入
4次类推直输入a1止
234形式链表 约5min
1 循环链表2 双链表
235序表类型 约5min
24元项式表示
241元项式 约20min
计算机中线性表表示
P (p0 p1 …pn)
抽象数类型元项式定义：
ADT Polynomial {
数象：D＝{ ai| ai∈TermSeti12m m≥0
TermSet 中元素包含
表示系数实数表示指数整数 }
数关系：R1＝{|ai1 ai∈D i2n
ai1中指数值＜ai中指数值 }
基操作：
CreatPolyn ( &P m ) 操作结果：输入 m 项系数指数
建立元项式 P
DestroyPolyn ( &P ) 初始条件：元项式 P 已存
操作结果：销毁元项式 P
PrintPolyn ( &P ) 初始条件：元项式 P 已存
操作结果：印输出元项式 P
PolynLength( P ) 初始条件：元项式 P 已存
操作结果：返回元项式 P 中项数
AddPolyn ( &Pa &Pb ) 初始条件：元项式 Pa Pb 已存
操作结果：完成项式相加运算：
Pa Pa＋Pb销毁元项式 Pb
SubtractPolyn ( &Pa &Pb )
… …
} ADT Polynomial
242元项式实现： 约10min
typedef OrderedLinkList polynomial
带表头结点序链表表示项式
四结 约5min
1够时间空间复杂度角度综合较线
性表两种存储结构特点适场合
五章作业： 约5min
写算法单链表中值重复结点删结果表中结点值均相
题样考虑先取开始结点中值结点值较发现相删掉然取第二结点值重复述程直结点
课 时 授 课 计 划
20112012学年第 学期 第3周
授 课 日 期
9月22日 五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 栈 栈应举例
教学目求：
1 栈数类型定义
2 栈序存储实现
3 掌握栈应方法理解栈重作
教学重点：
1栈序存储表示实现方法
2利栈实现行编辑利栈实现表达式求值
教学难点：
1栈定义
2利栈实现表达式求值
作业参考书：
1栈定义应
2栈特点
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约10min
1 什线性结构？
2 餐馆中叠叠盘子例引出栈特点
二讲课进程设计
31 栈类型定义
311栈栈顶(top)栈底(bottom)定义 约10min
312栈类型定义 约10min
32 栈应举例
例 数制转换 约10min
十进制数Nd进制数转换计算机实现计算基问题简单算法基列原理： N (N div d)×d + N mod d (中：div整运算mod求余运算)
例二 括号匹配检验 约10min
检验括号否匹配方法期急迫程度概念描述
三种情况应栈操作： 1．栈顶左括弧相匹配 2．栈中没左括弧等里3．栈中左括弧没等相匹配右括弧
例三 行编辑程序问题 约10min
户输入行程中允许户输入出差错发现误时时更正
合理作法：设立输入缓区接受户输入行字符然逐行存入户数区假设#退格符@退行符
例四 迷宫求解 约10min
假设栈S记录前路径栈顶中存放前路径通道块 纳入路径操作前位置入栈 前路径删前通道块操作出栈
例五表达式求值 约10min
表达式操作数(operand)运算符(operator)界限符(delimiter)组成
例六 实现递 约10min
递函数实现
递函数运行程类似函数嵌套调差仅调函数调函数函数保证层递调层数进行操作执行递函数程中需递工作栈
三结 约5min
1 掌握栈队列类型特点相 应应问题中正确选
2 熟练掌握栈类型两种实现方法特 应注意栈满栈空条件描述方法
四作业 约5min
14元素a1a2a3a4次通栈a4进栈前栈状态出栈序（ ） (A)a4a3a2a1 (B)a3a2a4a1 (C)a3a1a4a2 (D)a3a4a2a1
2栈特点（）
课 时 授 课 计 划
20112012学年第 学期 第3周
授 课 日 期
9月27日 三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 队列
教学目求：
1 熟练掌握循环队列链队列基操作实现算法
2 理解递算法执行程中栈状态变化程
教学重点：
1．链队表示实现
教学难点：1链队表示实现
作业参考书：
1．栈队列较
2．读程序段
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
日常生活中维持正常社会秩序出现常见现象什？
排队计算机程序中模拟排队数结构队列
二讲课进程设计
34 队列
1队列定义 约10min
2队列抽象类型定义 约15min
3队列基操作： 约20min
InitQueue(&Q) 操作结果：构造空队列Q
DestroyQueue(&Q) 初始条件：队列Q已存
操作结果：队列Q销毁存
QueueEmpty(Q) 初始条件队列Q已存
操作结果Q空队列返回TRUE否返回FALSE
QueueLength(Q) 初始条件队列Q已存
操作结果返回Q元素数队列 长度
GetHead(Q &e) 初始条件：Q非空队列
操作结果：e返回Q队头元素
ClearQueue(&Q) 初始条件：队列Q已存 操作结果：Q清空队列
EnQueue(&Q e) 初始条件队列Q已存
操作结果插入元素eQ新队尾元素
DeQueue(&Q &e) 初始条件：Q非空队列
操作结果：删Q队头元素e返回值
QueueTravers(Q visit())
队列类型实现
4链队列——链式映象 约15min
5循环队列——序映象 约20 min
队列程序设计中典型应例子作业排队问题
三结 约5min
1 熟练掌握循环队列链队列基操作实现算法特注意队满队空描述方法
2 理解递算法执行程中栈状态变化程
四作业 约10min
1线性表栈队列（）结构线性表（）位置插入删元素栈（）插入删元素队列（）插入元素（）删元素
2 指出述程序段功什
(1) void Demo1(SeqStack *S){
int i arr[64] n0
while ( StackEmpty(S)) arr[n++]Pop(S)
for (i0 i< n i++) Push(S arr[i])
} Demo1
课 时 授 课 计 划
20112012学年第 学期 第4周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 实验二 栈队列总结复
教学目求：
1 深入解栈队列特征便实际问题背景灵活运
2 巩固两种结构构造方法接触较复杂问题递算法设计
教学重点：
巩固两种结构构造方法接触较复杂问题递算法设计
教学难点：
巩固两种结构构造方法接触较复杂问题递算法设计
作业参考书：
数结构算法实现解析高 编著
教具：
课堂类型：
教学程：
停车场理
[问题描述]
设停车场停放n辆汽车狭长通道门供汽车进出汽车停车场车辆达时间先序次北南排列（门南端先达第辆车停放车场北端）车场已停满n辆汽车汽车门外便道等候旦车开走排便道第辆车开入停车场某辆车离开时开入车辆必须先退出车场路该辆车开出门外车辆原次序进入车场辆停放车场车离开停车场时必须停留时间长短交纳费试停车场编制述求进行理模拟程序
[测试数]
设n2输入数：（A’15）（A’210）（D’115）（A’3 20） （A’425）（A’530）（D’235）（D’440）（E’00）中A’表示达D’表示离E’表示输入结束
[基求]
栈模拟停车场队列模拟车场外便道终端读入输入数序列进行模拟理组输入数包括三数项：汽车达离信息汽车牌号码达离时刻组输入数进行操作输出数：车辆达输出汽车停车场便道停车位置车离输出汽车停车场停留时间应交纳费（便道停留时间收费）栈序结构实现队列链表实现
[实现提示]
需设栈时停放离汽车路停车场退出汽车序存储结构实现输入数达离时刻序栈中元素表示辆汽车包含两数项：汽车牌号码进入停车场时刻
[选作容]
（1） 两栈享空间思考应开辟数组空间少？
（2） 汽车种类占面积收费标准1辆客车15辆汽车占面积相1辆十轮卡车占面积相3辆汽车占面积
（3） 汽车直接便道开走时派前面汽车先开走路然次排队尾
（4） 停放便道汽车收费收费标准停放停车场车低请思考修改结构满足种求
课 时 授 课 计 划
20112012学年第 学期 第4周
授 课 日 期
10月8日 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 串
教学目求：
1熟悉串七种基操作定义利基操作实现传种操作方法
2熟悉掌握串定长序存储结构实现串种操作方法
3掌握串堆存储结构实现串种操作基方法
教学重点：
1串七种基操作定义
2串定长序存储
3串堆存储结构
教学难点：
1串七种基操作定义
2串堆存储结构
作业参考书：
串操作应
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
计算机非数值处理象基字符串数
二讲课进程设计
41串抽象数类型定义
1定义 约10min
串串长空串子串串位置相等空格串
2串抽象数类型定义 约10min
StrAssign (&T chars) StrCopy (&T S) DestroyString (&S) StrEmpty(S) StrCompare(ST) StrLength(S) Concat(&TS1S2) SubString (&SubSposlen) Index(STpos) Replace(&STV) StrInsert (&S pos T) StrDelete (&S pos len) ClearString(&S)
42 串表示实现
421串定长序存储表示 约15min
1串联接 2求子串
422串堆分配存储表示 约20min
通常C语言中提供串类型种存储方式实现系统利函数malloc( )free( )进行串值空间动态理新产生串分配存储区称串值享存储空间堆
423串块链存储表示 约10min
链表存储串值串数元素字符 8 位二进制数链表存储时通常结点中存放字符子串
44 串操作应举例
441文编辑 约20min
文编辑程序功强弱差基操作致：包括串查找插入删等基操作
户讲文（文件）包括干页页包括干行行包括干文字
文编辑程序讲整文成长字符串称文串页文串子串行页子串简化程序复杂程度简单文分成干行
三结 约5min
1 熟悉串七种基操作定义利基操作实现串种操作方法
2 熟练掌握串定长序存储结构实现串种操作方法
3 解串堆存储结构实现串操作基方法
4 解串操作应方法特点
四作业 约5min
假设串说明：
char s1[30]StocktomCA
s2[30]March 5 1999 s3[30] *p
(1)执行列语句s3值什
strcopy(s3s1) concat(s3) concat(s3s2)
(2)调函数strcompare(s1s2)返回值什
(3)调函数strcompare(&s1[5]ton)返回值什
(4)调函数strlength(concat(s1s2))返回值什
课 时 授 课 计 划
20112012学年第 学期 第5周
授 课 日 期
10月11日 三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 数组
教学目求：
1 掌握数组定义
2 掌握数组序表示方法
教学重点：
1 数组定义
2 数组序表示方法
教学难点：
数组序表示方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结
引入 约5min
前章讨线性结构中数元素非结构原子类型引入数组
二讲课进程设计
51 数组类型定义
抽象数类型定义 约5min
ADT Array {
数象：
数关系：
} ADT Array
二维数组定义 约10min
数象
D {aij | 0≤i≤b11 0 ≤j≤b21}
数关系
R { ROW COL }
ROW {| 0≤i≤b12 0≤j≤b21}
COL {| 0≤i≤b11 0≤ j≤b22}
基操作： 约10min
InitArray(&A nbound1boundn) DestroyArray(&A)
Value(A &e index1 indexn) Assign(&A e index1 indexn)
52 数组序表示实现
类型特点 约10min
1) 引型操作没加工型操作
2) 数组维结构存储空间 维结构
两种序映象方式 约10min
1)行序序(低标优先)2)列序序(高标优先)
53 矩阵压缩存储
531特殊矩阵
a称矩阵 约15min
定义 压缩存储方式
b三角矩阵 约15min
定义 压缩存储方式
c 角矩阵 约20min
定义 压缩存储方式
三结
1数组特殊性
2数组存储
3特殊矩阵存储
课 时 授 课 计 划
20112012学年第 二 学期 第5周
授 课 日 期
3月23日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 稀疏矩阵 广义表
教学目求：
1掌握稀疏矩阵定义三元组表示
2掌握广义表定义链接存储结构
教学重点：
1三元组表示
2广义表存储结构
教学难点：
1三元组表示法
2定义
作业参考书：
1画出出广义表两种存储结构
2求广义表运算
3象矩阵中求标变换公式
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
特殊矩阵引入
二讲课进程设计
532 稀疏矩阵
1定义 约5min
两类稀疏矩阵：1) 特殊矩阵2) 机稀疏矩阵
2机稀疏矩阵压缩存储方法
1三元组序表 约20min
2行逻辑联接序表 约20min
3十字链表 约10min
54 广义表
广义表定义 约20min
1 广义表：
表头：非空广义表第元素α1 表尾：余元素（α2… αn）组成表
2 广义表抽象数类型定义 3广义表操作：
55广义表存储结构
广义表中数元素具结构．采链式存储结构表示广义表数元素结点表示
1 广义表头尾链表存储表示 约10min
typedef enum{ATOM LIST}ElemTag
typedef struct GLNode{
ElemTag tag
union{
AtomType atom
struct {struct GLNode *hp *tp}ptr
}
}*GList
三结 约5min
1 解数组两种存储表示方法掌握数组行存储结构中址计算方法2 掌握特殊矩阵进行压缩存储时标变换公式3 解稀疏矩阵两类压缩存储方法特点适范围领会三元组表示稀疏矩阵时进行矩阵运算采处理方法4掌握广义表结构特点存储表示方法读者根惯熟练掌握意种结构链表学会非空广义表进行分解两种分析方法：非空广义表分解表头表尾两部分者分解n子表
四课作业题 约5min
1画出面广义表两种存储结构图示： ((((a) b)) ((( ) d) (e f)))
2求列广义表运算结果：
（1） GetHEAD[((ab)(cd))] （2） GetTAIL[((ab)(cd))]
（3） GetTAIL[HEAD[((ab)(cd))]] （4） GetHEAD[TAIL[HEAD[((ab)(cd))]]]
（5） GetTAIL[HEAD[TAIL[((ab)(cd))]]]
3设三角矩阵An×n 三条角线元素逐行存数组B(13n2)中B[k] aij 求：（1） ij表示k标变换公式（2） k表示ij标变换公式
课 时 授 课 计 划
20112012学年第 学期 第6周
授 课 日 期
10月20日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 树定义基术语 二叉树
教学目求：
1掌握树二叉树基概念术语二叉树性质
2掌握二叉树两种存储结构
教学重点：
1二叉树性质定义
2链式存储结构
教学难点：
1二叉树性质
2链式存储二叉树基操作
作业参考书：
1棵度2树二叉树区
23结点树3结点二叉树
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
前章线性结构带问题引出非线性结构
二讲课进程设计
第6章 树二叉树
61树定义基术语
1 树定义 约10min
树包含n结点限集合(n>0)
Tree(DR)
中D具相性质数元素集合D中元素R空集否RD某二元关系H集合H描述二元关系：
（1） D中存唯称根元素r0关系H前驱
（2） 结点r0外K中结点关系H说前驱
（3）结点r0外结点rR存结点序列r0r1…rsH(1 树例子：家族机构等
2 树抽象数类型定义 约5min
ADT Tree
数象 D：
数关系 R：
基操作 P：
InitTree(&T)
DestroyTree(&T)
CreateTree(&Tdefinition)
ClearTree(&T)
……
3 树术语 约10min
结点：数元素指子树分枝终端结点（叶子）分枝结点
子女：结点子树根称结点子女该结点称子女双亲
层次：根第层根子女第二层类推
深度：树中结点层次称树深度（高度）
度：结点分枝数目
树度：树中结点度
兄弟：双亲子女互称兄弟父母兄弟结点互称堂兄
祖先：结点祖先根该结点分支结点
子孙：某结点根子树中结点称该结点子孙
序树：结点子树左右序否称序树
森林 树相交集合根结点子树集合森林
RF{|i12…mm>0}
62二叉树
621二叉树类型定义 约15min
二叉树种树型结构特点结点二棵子树（二叉树中存度2结点)二叉树子树左右分次序意颠倒二叉树空树根结点加两棵分称左子树右子树互交二叉树组成(树度2)
二叉树基操作：
查 找 类
Root(T) Value(T e) Parent(T e) LeftChild(T e) RightChild(T e)
LeftSibling(T e) RightSibling(T e) BiTreeEmpty(T) BiTreeDepth(T)
PreOrderTraverse(T Visit()) InOrderTraverse(T Visit()) PostOrderTraverse(T Visit())
LevelOrderTraverse(T Visit())
插 入 类
InitBiTree(&T) Assign(T &e value) CreateBiTree(&T definition) InsertChild(T p LR c)
删 类
ClearBiTree(&T) DestroyBiTree(&T) DeleteChild(T p LR)
622二叉树性质 约20min
性质1： 二叉树第i 层2i1 结点 (i≥1)
性质 2 ：深度 k 二叉树含 2k1结点（k≥1）
性质 3 ：棵二叉树含n0 叶子结点（0度结点）n2 度 2结点必存关系式：n0 n2+1
两类特殊二叉树：
满二叉树：指深度k含2k1结点二叉树
完全二叉树：树中含 n 结点满二叉树中编号 1 n 结点应（编号规左右）
性质 4 ：具 n 结点完全二叉树深度 ëlog2nû +1
性质 5 ：含 n 结点完全二叉树左右进行 1 n 编号完全二叉树中意编号 i 结点：（1）i1序号i结点根结点双亲结点i>1序号i结点双亲结点序号（2）2×i>n序号i结点左孩子2×i≤n序号i结点左孩子结点序号2×i（3）2×i＋1>n序号i结点右孩子2×i＋1≤n序号i结点右孩子结点序号2×i＋1
623 二叉树存储结构 约25min
1 二叉树序存储表示
2二叉树链式存储表示
1) 二叉链表 2)．三叉链表 3)．双亲链表 4)．线索链表
三结 约5min
1树二叉树定义
2二叉树性质
3存储结构
四作业 约5min
1棵度2树棵二叉树区？
2试分画出具3结点二叉树3 结点二叉树形态
课 时 授 课 计 划
20112012学年第 学期 第7周
授 课 日 期
10月25日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 遍历二叉树线索二叉树
教学目求：
1 遍历二叉树二叉树种操作基础掌握种遍历策略递算法灵活运遍历算法实现二叉树操作
2理解二叉树线索化实质熟练掌握二叉树线索化程中序线索化树找定结点前驱继方法
教学重点：
1 遍历二叉树二叉树种操作基础
2．种遍历策略递算法运遍历算法实现二叉树操作
教学难点：
种遍历策略递算法运遍历算法实现二叉树操作
二叉树线索化程中序线索化树找定结点前驱继方法
作业参考书：
写出二叉树前中序序列
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
二叉树结构引出结点遍历
二 讲课进程设计
63遍历二叉树线索二叉树
631二叉树遍历
问题提出 约7min
着某条搜索路径巡访二叉树中结点结点均访问次仅访问次（树线性化）
二叉树言三条搜索路径：
Ø 1．先层次遍历
Ø 2．先左（子树）右（子树）遍历
Ø 3．先右（子树）左（子树）遍历
二先左右遍历算法 约10min
先（根）序遍历算法
二叉树空树空操作
否
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
中（根）序遍历算法
二叉树空树空操作否
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
（根）序遍历算法
二叉树空树空操作
否
（1）序遍历左子树
（2）序遍历右子树
（3）访问根结点
三算法递描述 约10min
总结：先序中序序遍历二叉树遍历时搜索路线相：根结点出发逆时针延二叉树外缘移动结点均途径三次
先序遍历：第次结点时访问
中序遍历：第二次结点时访问
序遍历：第三次结点时访问
四中序遍历算法非递描述 约10min
五遍历算法应举例 约30min
1统计二叉树中叶子结点数(先序遍历)
先序(中序序)遍历二叉树
遍历程中查找叶子结点计数需遍历算法中增添计数
参数算法中访问结点操
作改：叶子计数器增1
2求二叉树深度(序遍历)
算法基思想
首先分析二叉树深度左右子树深度间关系
3复制二叉树(序遍历)
基操作：生成结点
4建立二叉树存储结构
p 定义方法相应存储结构建立算法
定表达式建相应二叉树
先缀表示式建树
原表达式建树
已知道二叉树结构某遍历序列存应关系已知二叉树前序序列中序序列定惟确定二叉树结构
632线索二叉树 约20min
• 谓线索二叉树？
• 遍历二叉树结果求结点线性序列
• 保存种遍历程中信息？
• 简单方法结点增加二指针域：fwdbkwd指示结点遍历中前驱继结点
• 线索链表遍历算法
• 线索链表中添加遍历中前驱继信息简化遍历算法
• 建立线索链表？
结索化实质二叉链表中空指针改指前驱继线索前驱继信息遍历时线索化程遍历程中修改空指针程记遍历程中访问结点先关系附设指针pre始终指刚刚访问结点指针p指前访问结点pre指前驱中序遍历程中修改结点左右指针域保存前访问结点前驱继信息遍历程中附设指针pre 始终保持指针pre指前访问指针p指结点前驱
三结 约7min
1遍历总结
2线索化总结
四作业
1出二叉树写出前中序遍历序列
课 时 授 课 计 划
20112012学年第 学期 第7周
授 课 日 期
11月1日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 树森林
教学目求：
1．熟悉树种存储结构特点掌握树森林二叉树转换方法
2．学会编写实现树种操作算法
教学重点：
1树森林二叉树转换方法
2．学会编写实现树种操作算法
教学难点：
1树森林二叉树转换方法
2．学会编写实现树种操作算法
作业参考书：
树森林转换
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
前面树二叉树回顾引入
二讲课进程设计
64树森林
6·4·1 树存储结构 约25min
1 双亲表示法
组连续存储空间存放树结点结点中附设指针指示双亲结点连续存储空间中位置（标种结构属静态链表）形式表示：
typrdef struct tnode
{ datatype data
int parent
}tree[n]
2 孩子表示法
重链表表示两种方法：构：度结点设置结点结构数域d指针域容易造成空间浪费异构：结点棵子树设指针样操作困难子女链单链表中形式描述：
typrdef struct tagnode * 表结点 *
{ int child
struct tagnode *next
}node *link
typedef struct * 头结点 *
{datatype data
link headptr
}headnode
typedef headnode childlink[maxnode] * 表头数组 *
带双亲孩子链表表示法：
typedef struct * 头结点 *
{datatype data
int parent
link headptr
}headnode1
3 孩子兄弟表示法
该方法称二叉树表示法二叉链表表示法二叉链表作存储结构结点两链域分指该结点第孩子兄弟分命名fchnsib形式描述：
typedef struct treenode
{datatype data
struct treenode *fch*nsib
}treenode *tree
树种表示质二叉树二叉链表表示二叉树树种存储结构致性导致树二叉树相互转换
6·4·2 森林二叉树相互转换 约30min
1 森林转二叉树
树（树林）转换成二叉树时结果唯转换递描述：树（树林）空二叉树空否树（树林）中第棵树根二叉树根第棵树根结点子树林二叉树左子树树林中第棵树树林形成二叉树右子树
形象说转换程面三步曲说明：
三步曲： 连线 切线 旋转
连线： 兄弟结点连接起
切线： 保留双亲第子女连线双亲子女连线切掉
旋转： 根轴面时针方旋转450
2 二叉树转树林
二叉树转换成树（树林）时结果唯
转换递描述二叉树空树（树林）空否二叉树根树（树林）中第棵树根二叉树左子树构成树（树林）中第棵树根结点子树林二叉树右子树构成树林中第棵树树林
形象说面三步曲逆
6·4·3 树森林遍历 约30min
树遍历方法分宽度优先法深度优先法两类前者指（根）第层开始左右逐结点遍历者分先根次序根次序
（1） 先根次序遍历（相相应二叉树先序遍历）
树（森林）空空操作否：
·访问左面第棵树根
·先根次序左右遍历根子树
·先根次序左右遍历第棵树外树（森林）
（2） 根次序遍历（相相应二叉树中序遍历）
树（森林）空空操作否：
·根次序左右遍历左面树子树
·访问左面树根
·根次序左右遍历第棵树外树（森林）
三结 约7min
1树存储
2树森林间转换
3树森林遍历
四作业 约3min
1完成树森转换
课 时 授 课 计 划
20112012学年第 学期 第8周
授 课 日 期
11月3日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 哈夫曼树
教学目求：
1掌握哈夫曼树构造方法
2掌握哈夫曼编码
3带权路径计算
4解优树特性
教学重点：
1哈夫曼树构造
2掌握建立优树哈夫曼编码方法
教学难点：
1建立优树哈夫曼编码方法
2带权路径计算
作业参考书：
1构造棵哈夫曼树计算权值
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
优树概念提出引入哈夫曼树
二讲课进程设计
6·6 哈夫曼树应
6·6·1 优二叉树（哈夫曼树带权路径长度短树）
1 哈夫曼树基概念 约20min
（1） 路径 树中结点结点间分支
（2） 路径长度 路径分支数目称路径长度
（3） 树路径长度 树根结点路径长度称树路径长度完全二叉树路径长度短二叉树
（4） 结点带权路径长度 该结点树根间路径长度结点权积
（5） 树带权路径长度 树中叶子结点带权路径长度通常记WPLwili
（6） 哈夫曼树（优二叉树） 带权路径长度二叉树称哈夫曼树（优二叉树）
（7） 哈夫曼编码 哈夫曼树左分枝0右分枝1根结点开始直叶子结点组成编码序列称叶子结点哈夫曼编码
2 哈夫曼树判定问题中应 约15min
百分制转五级记分制例子说明哈夫曼树判定次数少树（带权路径长度短节省计算时间）
3 构造哈夫曼树 约20min
（1） 根定n权值{w1w2…wn}构成n棵二叉树集合F{T1T2…Tn}棵二叉树Ti根结点F中选两棵根结点权值树作左右子树构造棵二叉树新二叉树根结点权值等左右子树根结点权值
（2） F中删两棵子树时新二叉树加入F中
（3） 重复（2）（3）直F中剩棵树（哈夫曼树）止
举例说明程：
应该说明哈夫曼树形态唯具组权值哈夫曼树WPL唯
6·6·2 哈夫曼编码
1 哈夫曼编码提出背景 约10min
(1)电报编码变短非前缀编码出现二义性(2)二叉树构造前缀编码(3)哈夫曼树优编码
2 构造哈夫曼树哈夫曼编码算法 约20min
前缀编码：字符编码字符集中字符编码前缀
A B C D 四字符率高低编码A 0 B 10 C 110 D 111
利赫夫曼树构造种等长二进制编码构造赫夫曼编码种优前缀编码传电文总长度短哈夫曼编码算法实现：哈夫曼树中没度1结点棵n叶子哈夫曼树2×n－1结点2×n－1 维数组存放哈夫曼树结点结点时包含双亲信息孩子结点信息构成静态三叉链表
三结 约5min
1构造哈夫曼树 2哈夫曼编码
四作业 约5min
1求带权913565叶子节点生成哈夫曼树带权路径长度
2设哈夫曼树叶节点数n0节点总数少？
课 时 授 课 计 划
20112012学年第 学期 第8周
授 课 日 期
10月27日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 树二叉树复题课
教学目求：
1． 熟悉二叉树结点结构二叉树基操作
2． 掌握二叉树种操作具体实现
3． 学会利递方法编写二叉树种递数结构进行处理算法
教学重点：
1． 学会利递方法编写二叉树种递数结构进行处理算法
教学难点：
1利递方法编写二叉树种递数结构进行处理算法
作业参考书：
数结构算法实现解析高 编著
教具：
课堂类型：
总结复
教学程： 提出问题――问题提示――完成问题――检查
二叉树基操作
复目
4． 熟悉二叉树结点结构二叉树基操作
5． 掌握二叉树种操作具体实现
6． 学会利递方法编写二叉树种递数结构进行处理算法
复容
该程序功实现二叉树结点类型定义二叉树基操作该程序包括二叉树结构类型种操作具体函数定义函数
* 定义DataTypechar类型 *
typedef char DataType
* 二叉树结点类型 *
typedef struct BitNode
{DataType data
struct BitNode *lchild*rchild
}BitNode*BitTree
* 初始化二叉树树根指针置空 *
void BinTreeInit(BitTree *BT)
* 先序次序建立二叉树*
void BinTreeCreat(BitTree *BT)
* 检查二叉树否空 *
int BinTreeEmpty(BitTree *BT)
* 种遍历次序（包括先序中序序层次）输出二叉树中结点 *
void BinTraverse(BitTree *BT)
* 求二叉树深度 *
int BinTreeDepth(BitTree BT)
* 求二叉树中结点数 *
int BinTreeCount(BitTree BT)
* 清二叉树变空树 *
void BinTreeClear(BitTree *
课 时 授 课 计 划
20112012学年第 学期 第11周
授 课 日 期
11月8日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 图定义术语 图存储结构
教学目求：
1掌握图定义常术语
2掌握图二种存储表示法
教学重点：
1图常术语
2图数组表示邻接表表示法
教学难点：
1图常术语
2邻接表表示法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
城市间通信引出图
二讲课进程设计
第 七 章 图
图进行概述 约5min
图种线性表树复杂数结构图结构中结点间关系意图中意两元素间关系图应非常广泛
71图定义术语
1 图定义 约5min
图种数结构形式化定义写
Graph(VR)
中V{x|xdatatype}
R{VR}
VR{|P(xy)(xyV)}
图中数元素常称顶点V顶点穷集合R边（弧）穷集合
2 抽象数类型图定义 约5min
ADT Graph
{数象V：
数关系R：
基操作P：
}ADT Graph
3 图术语概念 约15min
(1) 图图 弧： 边 (xy)
(2) （）完全图 稀疏图 稠密图 子图
完全图：n顶点n(n1)2条边完全图：n顶点n(n1)条弧
(3) 权网 边（弧）相关数权带权图称网
(4) 邻接邻接点 图：条边连起两顶点互称邻接点
图：顶点x顶点y条弧说顶点x邻接顶点y顶点y邻接顶点x
(5) 度出度入度图中顶点相关边(e)数顶点度e
图中顶点出发弧数该顶点出度入该顶点弧数该顶点入度TD(v)ID(v)+OD(v)
(6) 路径路径长度回路(环)简单路径
(7) 连通连通图连通分量图顶点v1顶点v2路径说v1v2连通意两顶点连通说该图连通连通分量图中极连通子图
(8) 强连通图强连通分量
(9) 生成树树生成森林
连通图生成树极连通子图含图全部顶点足构成棵树n1条边
图中顶点入度0余顶点入度均1该图称树图生成森林干棵树组成含图全部顶点足构成干棵相交树弧
7·2 图存储结构
7·2·1 图序存储结构数组表示法 约20min
1 数组表示法
两数组分表示数元素（顶点）信息边（弧）信息
顶点编号信息边（弧）面邻接矩阵表示
2 邻接矩阵定义
n顶点图G(V{VR})邻接矩阵n阶方阵定义： 0 （vivj）VR
3 图邻接矩阵性质
（1） 图邻接矩阵称矩阵
（2） 顶点vi度邻接矩阵中第i行（第i列）元素(1)
4 图邻接矩阵性质
（1） 图邻接矩阵定称矩阵
（2） 顶点vi出度邻接矩阵中第i行元素入度邻接矩阵中第i列元素
5 网邻接矩阵
邻接矩阵中01换成权值网邻接矩阵
6 邻接矩阵优缺点
容易实现图前4操作容易判定顶点间边（弧）容易计算顶点度（出度入度）缺点占空间顶点数关边数关边数较少时空间浪费较
7 建立邻接矩阵算法
7·2·2 图邻接表表示法 约15min
邻接矩阵稀疏图时空间浪费较克服缺点采邻接表表示法
1 邻接表结点结构
2 邻接表顶点量结构边（弧）单链表结构顶点结点包括两域n顶点放量中（称序存储结点表）顶点邻接点链接成单链表该顶点量中指针域指第邻接点
3 邻接表优缺点
容易实现图前4操作
空间较省
图容易求顶点度边表中结点数边两倍
图容易求顶点出度求顶点入度容易遍历整表求顶点入度时设逆邻接表（指某顶点邻接点链接成单链表）
4 建立邻接表算法
7·2·3 图十字链表表示法 约15min
图邻接表表示法中查顶点出度非常容易查顶点入度遍历整邻接表解决办法建立逆邻接表成两表方便节介绍图种表示方法十字链表表示法
7·2·4 图邻接重表表示法 约10min
图种表示方法邻接表中条边需两边结点边处理图时需判断边否处理增加复杂性图邻接重表中边结点
三结 约5min
1图基概念术语
2图两种存储结构间较
课 时 授 课 计 划
20112012学年第 学期 第11周
授 课 日 期
11月15日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 图遍历 图连通性问题
教学目求：
1掌握图深度优先遍历方法算法
2掌握广度优先遍历方法算法
3掌握生成树
教学重点：
1深度优先遍历
2生成树
教学难点：
1深度优先遍历
2生成树
作业参考书：
1图基概念
2生成树
3生成树
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
复图存储结构引出图遍历
二讲课进程设计
73 图遍历
731深度优先搜索遍历图 约20min
连通图深度优先搜索遍历图中某顶点V0 出发访问顶点然次V0未访问邻接点出发深度优先搜索遍历图直图中V0路径相通顶点访问
732广度优先搜索遍历图 约15min
连通图起始点V余顶点必定存路径图中某顶点V0出发访问顶点次访问V0未访问邻接点顶点访问先次序次访问邻接点直图中V0路径相通顶点访问时图中尚顶点未访问选图中未访问顶点作起始点重复述程直图中顶点访问止
733遍历应举例 约10min
1求两顶点间条路径长度短路径
74图连通问题
741图连通分量生成树 约15min
1图遍历时连通图顶点出发便遍历图中顶点非连通图需次调搜索程次调顶点访问序列恰连通分量中顶点集
2生成树连通图调DFSBFS边集合图全部顶点构成图极连通子图连通图棵生成树
3生成森林非连通图连通分量顶点集边起构成干棵生成树连通图生成树构成非连通图生成森林
743生成树 约25min
普里姆(Prim)算法基思想取图中意顶点 v 作生成树根生成树添加新顶点 w添加顶点 w 已生成树顶点v 间必定存条边该边权值连通顶点 v w 间边中取值继续生成树添加顶点直生成树含 n1 顶点止
克鲁斯卡尔算法基思想：考虑问题出发点 生成树边权值达应生成树中条边权值
三结 约5min
1深度优先搜索遍历图
2生成树
四作业 约5min
1已知右图示图请出该图
（1）顶点入出度（2）邻接矩阵（3）逆邻接表（4）强连通分量
2画出顶点v1初始源点遍历图示图DFS BFS生成森林
3图（图）示连通图请分PrimKruskal算法构造生成树
课 时 授 课 计 划
20112012学年第 学期 第12周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 拓扑排序 短路径
教学目求：
1掌握拓扑排序
2掌握迪杰斯特算法
教学重点：
1拓扑排序
2短路径
教学难点：
拓扑排序
作业参考书：
71已知右图示图请出该图
（1）顶点入出度（2）邻接矩阵（3）逆邻接表（4）强连通分量
72画出顶点v1初始源点遍历图（图）示图DFS BFS生成森林
73图（图）示连通图请分PrimKruskal算法构造生成树
74已知图示AOE网试求：事件早发生时间晚发生时间活动早开始时间晚开始时间出关键路径
75 试基图深度优先策略写算法判邻接表方式存储图中否存顶点vi顶点vj路径（ij)
注意：算法中涉图基操作必须存储结构实现
76 试利栈基操作编写深度优先搜索策略遍历强连通图非递形式算法算法中规定具体存储结构图Craph成种抽象数类型
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
城市间通信引入
二讲课进程设计
75环图应
环图基础 约10min
1 环图定义 环图环图简称DAG图
2 DAG图描述带公子式表达式
((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)
3 图中否环检查
4 环图应
环图描述工程系统进行程效工具工程否利进行二估算工程完成需短时间拓扑排序关键路径问题
7·5·1 拓扑排序 约20min
1拓扑排序基概念
（1） AOV网 顶点表示活动弧表示活动间优先关系图顶点表示活动网（Activity On Vertex Network）
（2）拓扑序列 AOV网顶点排成线性序列该序列满足AOV网中顶点vivj条路径该线性序列中vi必vj前面样序列称拓扑序列
（3） 拓扑排序 AOV网构造拓扑序列操作拓扑排序
（4）AOV网中应环否会先决条件AOV网代表工程AOV网拓扑序列工程利完成行方案
2拓扑排序方法
1）图中选择入度0顶点输出2）图中删该顶点源该顶点弧3） 重复两步直全部顶点输出拓扑排序利完成否剩入度非0顶点说明图中环拓扑排序进行
3 拓扑排序算法
邻接表顶点量中量元素增加入度域存放顶点入度值输出该顶点删源该顶点弧该顶点邻接点入度减1实际实现时设栈存放入度0顶点退栈输出顶点邻接点入度域减1减0时入栈拓扑排序完成时栈应空
4 拓扑排序算法分析
O（n+e）
7·5·2 关键路径 约25min
1 AOE网
顶点表示事件弧表示活动弧权值表示活动持续时间图AOE（Activity On Edge Network）网 AOE网常估算工程完成时间
2 AOE网研究问题
1)完成整工程少需少时间2)活动影响工程关键
1956年美国杜邦公司提出关键路径法1957年首先1000万美圆化工厂建设工期原计划缩短4月杜邦公司采关键路径法年中节省100万美圆
3 关键路径术语
（1） 关键路径 源点汇点路径长度长路径关键路径
（2） 活动开始早时间e(i)
（3） 活动开始晚时间l(i) 定义e(i)l(i)活动关键活动
（4） 事件开始早时间ve(i)
（5） 事件开始晚时间vl(i)
4 求关键路径算法
(1) 输入e条弧建立AOE网存储结构
(2) 源点v1出发令ve(1)0求 ve(j) 2(3) 汇点vn出发令vl(n)ve(n)求 vl(i) 1(4) 根顶点vevl值求条弧s（活动）早开始时间e(s)晚开始时间l(s)中e(s)l(s)关键活动
求关键路径拓扑排序前提进行进行拓扑排序然求关键路径
5 求关键路径算法分析
（1） 求关键路径必须拓扑排序前提进行环图求关键路径
（2） 缩短关键活动工期缩短工期
（3） 关键活动关键路径减少减少工期
（4） 改变关键路径前提缩短关键活动缩短整工期
76短路径
网络中常见问题：两点间否通路条路径短书讨两类问题：类顶点顶点间短路径类意两顶点间短路径图应
7·6·1 某源点顶点间短路径 约10min
里路径指两顶点间通路路径长度指边总长短路径问题指两顶点间通路条时找出边长总短条Dijkstra提出路径长度递增次序求短路径方法
1 Dijkstra 求短路径基思想
顶点分成两组第组已确定短路径结点集合第二组尚未确定短路径结点集合路径长度递增次序逐第二组顶点放第组中设求v1顶点间短路径意时刻v1第组顶点间短路径v1第二组顶点间短路径
2 Dijkstra 求短路径步骤
设图邻接矩阵arcs存储矩阵中元素值边权值顶点间边时应权值穷表示
3 Dijkstra 求短路径实例模拟
4 Dijkstra 求短路径算法
5 Dijkstra 求短路径算法分析
n顶点图求顶点余顶点短路径循环n1次加修改短路径循环二层循环时间复杂度O(n2)求源点某顶点间短路径求余顶点间短路径相时间复杂度O(n2)
6·4·2 顶点间短路径 约20min
n顶点图求顶点间短路径方法二：Dijkstra算法求顶点顶点间短路径面基础加层循环时间复杂度O(n3)种方法弗洛伊德（floyd）提出时间复杂度O(n3)形式简单
1弗洛伊德（floyd）算法基思想
设求顶点vivj间短路径vivj弧弧权值条路径未必短路径n1次测试首先顶点v1加入(viv1)(v1vj)否路径(vivj)低两段路径代称vivj中间顶点序号1短路径顶点v2加入vivj中间顶点序号2短路径直vn加入vivj中间顶点序号n短路径算法结束
2弗洛伊德（floyd）算法实例模拟
4 弗洛伊德（floyd）算法
三 结 约3min
1 拓扑排序
2 短路径
四作业题 约8min
71已知右图示图请出该图
（1）顶点入出度（2）邻接矩阵（3）逆邻接表（4）强连通分量
72画出顶点v1初始源点遍历图（图）示图DFS BFS生成森林
73图（图）示连通图请分PrimKruskal算法构造生成树
74已知图示AOE网试求：事件早发生时间晚发生时间活动早开始时间晚开始时间出关键路径
75 试基图深度优先策略写算法判邻接表方式存储图中否存顶点vi顶点vj路径（ij)
注意：算法中涉图基操作必须存储结构实现
76 试利栈基操作编写深度优先搜索策略遍历强连通图非递形式算法算法中规定具体存储结构图Craph成种抽象数类型
课 时 授 课 计 划
20112012学年第 学期 第12周
授 课 日 期
11月17日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 图总结复
教学目求：
1掌握图种存储结构
教学重点：
熟练掌握邻接矩阵邻接表存储结构
教学难点：
熟练掌握邻接矩阵邻接表存储结构
作业参考书：
数结构算法实现解析高 编著
教具：
课堂类型：
教学程：提出问题――问题提示――完成问题――检查
图基操作
复目
1． 掌握图种存储结构特熟练掌握邻接矩阵邻接表存储结构
2． 遍历图种应算法基础熟练掌握图深度优先遍历广度优先遍历算法复栈队列应
复容
程序1
* 定义邻接矩阵类型 *
typedef int adjmatrix[n+1][n+1]
* 建立图邻接矩阵 *
void CreatMatrix(adjmatrix GA)
* 初始点v出发深度优先遍历邻接矩阵GA表示图 *
void DfsMatrix(adjmatrix GAint v)
*初始点v出发广度优先遍历邻接矩阵GA表示图*
void BfsMatrix(adjmatrix GAint v)
程序2
* 邻接表结点类型 *
typedef struct arc
{int adjvex
struct arc *next}ArcNode
typedef struct VexNode
{int vertex
ArcNode *firstarc
}VerNode
typedef VerNode AdjList[MAXNODE]
* 建立图邻接表 *
void CreatAdjlist(AdjList GL)
* 初始点v出发深度优先遍历邻接表GL表示图 *
void DfsAdjlist(AdjList GLint v)
*初始点v出发广度优先遍历邻接表GL表示图*
void BfsAdjlist(AdjList GLint v)
课 时 授 课 计 划
20112012学年第 学期 第13周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 静态查找表 动态查找表（）
教学目求：
1熟练掌握序表序表查找方法
2熟悉静态查找树构造方法查找算法理解静态查找树折半查找关系
3熟练掌握二叉排序树构造查找方法
4掌握二叉衡树维护衡方法
教学重点：
1查找基概念 2折半查找 3二叉排序树实现 4衡二叉树
教学难点：
1序查找性分析
2折半查找
3构造二叉排序树 衡二叉树
作业参考书：
1具n元素序序表序序表分进行序查找试述两种情况分讨两者等概率时均查找长度：
(1)查找成功表中关键字等定值K记录
(2)查找成功表中关键字等定值K记录
2设序表(abcefgijkpq)请分画出定值bgn进行折半查找程
3 画出长度10序表进行折半查找判定树求等该率时查找成功均查找长度
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
日常生活中遇找电话查找学生信息引入
二讲课进程设计
第 九 章 查找
基定义 约5min
1 查找定义 查找关键字等定值操作
2 关键字概念 关键字数元素（记录）中某数项值标识记录唯标识称关键字否称次关键字
3 查找结果 查关键字等定值记录称查找成功否称查找失败
4 查找算法效率度量
（1）均查找长度ASL：查找关键字等定值程中需定值进行较关键字数期值称查找成功时均查找长度
（2）需辅助存储空间
91 静 态 查 找 表
9·1·1 序查找 约12min
1 序查找定义 查关键字线性表中结点关键字逐较直找关键字值相等结点查找成功查完全表未找关键字相等结点查找失败
2 序查找算法
3 序查找算法时间复杂度
均查找长度ASL 查找成功
(1) 查找失败 n+1
(2) 设查找成功概率p查找成功概率q(1p)均较次数：
E(n)p +q(n+1) p +(1p)(n+1)(n+1)(1)
成功失败概率占50均性
查找结点概率等应查找概率高结点放前边提高查找效率
9·2·2 序表查找（二分查找） 约20min
1 二分法查找基概念 序表中元素已关键字序排列查找时必序查找查关键字中间位置元素关键字较相等查找成功查关键字中间位置分开左子表中查找否右子表中进行直查找成功查找失败
2 二分法查找算法
3 二分法查找时间复杂度
二分法查找程二叉树描述中间结点二叉树根左子表相左子树右子表相右子树二叉树便描述二分法查找判定树二分法查找程走条根结点叶子结点程查找成功失败查找长度均超树高度均性h élog2(n+1) ù
4 二分法查找优缺点
优点：查找速度快 表必须序
缺点：频繁插入删方便
二分法查找适表中元素少变化查找频繁情况序表查找适查找少表中元素频繁变化情况
9·2·3 索引序表查找（分块查找） 约15min
分块查找综合序查找二分法查找优点动态结构适快速查找
1 分块查找基思想
查找文件等长分干子文件（子文件长度）子文件元素序子文件间序第子文件高关键字第二子文件高关键字第二子文件高关键字第三子文件高关键字次类推建立索引表（文件）文件中元素含子文件高关键字子文件中第元素址（标）索引文件关键字序
查找时索引表序查找二分法查找块序查找
2 分块查找均长度
设查找文件n记录均分成b块块s记录考虑查找成功概率块索引表中均序查找均查找长度：
E(n)Eb+Ew+(s2+2s+n)(2s)
s均查找长度取值：+1
索引表采二分法查找均查找长度：
E(n)Eb+Ewélog2(b+1) ù+
3 种查找方法较
9·2 动态查找表
适应元素结点动态插入删
9·2·1 二叉排序树
1 什二叉排序树 约10min
（1） 二叉排序树定义
二叉排序树棵空树具性质二叉树：
· 左子树空左子树结点值均根结点值
· 右子树空右子树结点值均根结点值
· 左右子树分二叉排序树
（2） 二叉排序树建立实例
设关键字序列k(k1k2…km) (m>0)建立二叉排序树步骤：
· 令关键字k1二叉排序树根
·k1>k2k2做k1左子树根结点否做k1右子树根结点子树中继续子树根较重复前面操作
· 序列中关键字递面步骤
例定关键字序列 k(45125333710024619078)
（3） 中序（称序）遍历二叉排序树结点序列序序列
二叉排序树进行中序遍历遍历序列序序列二叉排序树定义决定
（4） 二叉排序树中结点插入
二叉排序树中插入结点保证插入结点二叉排序树然二叉排序树行插入结点叶子结点结果唯
（5） 二叉排序树中结点删
二叉排序树中删结点删结点二叉排序树然二叉排序树结果唯结点删立插入二叉排序树结点删前二叉排序树般说形态等
2 佳二叉排序树 约10min
（1） 佳二叉排序树定义
n结点二叉树n二叉排序树中均查找（检索）长度短棵二叉排序树佳二叉排序树
（2） 扩充二叉排序树
二叉树中度10结点补充虚结点结点（虚结点外）度均2样二叉树称扩充二叉排序树设加虚结点数N原结点（称部结点）数n时二叉树度1结点根二叉树性质3式成立：
Nn+1
定义外部路径长度扩充二叉树根外部结点路径长度E表示部路径长度指扩充二叉树根部结点路径长度I表示式成立：
EI+2n
数学纳法证明：
n1时I0E2等式成立
设n部结点时式成立
En In+2n （1）
考虑n+1结点扩充二叉树删部结点时结点路径长度K
InIn+1K (2)
时外部路径长度减少两路径长度K+1外部结点增加路径长度K部结点 EnEn+12(K+1)+K (3)
三式
En+1 En+2(K+1)K
(In+2n)+K+2
((In+1K)+2n)+K+2
In+1+2(n+1) 证毕
（3） 二叉排序树检索效率 E（n）<1+4logn
（4） 构造佳二叉排序树 首先关键字排序序表构造静态查找判定树二叉树佳二叉排序树判定树唯着佳二叉排序树定义佳二叉排序树唯
3 衡二叉树(AVL树) 约10min
二叉排序树差情况成单枝树检索效率等序表佳二叉排序树难构造提出种称衡二叉树二叉排序树检索效率界佳二叉排序树般二叉排序树间求树中结点左右子树高度差1四种旋转：LLRRLRRL
三结 约3min
1序存储 2动态存储
四作业 约2min
1具n元素序序表序序表分进行序查找试述两种情况分讨两者等概率时均查找长度：
(1)查找成功表中关键字等定值K记录
(2)查找成功表中关键字等定值K记录
2设序表(abcefgijkpq)请分画出定值bgn进行折半查找程
课 时 授 课 计 划
20112012学年第 学期 第13周
授 课 日 期
12月6日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 B树 哈希表
教学目求：
1 B－树建树查找
2 哈希表构造
3 查找时间
教学重点：
1 B－树构造查找
2 哈希表构造
教学难点：
1 B－树构造
2 哈希表构造
作业参考书：
1 B－树构造
2 哈希表构造
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
前面讲动态存储引入B－树哈希表
二讲课进程设计
922 B 树B+树 约25min
1．B树定义 B树种衡路查找树：
2．查找程：根结点出发指针搜索结点结点进行序（折半）查找两程交叉进行
3．插入
查找成功需进行插入显然关键字插入位置必定层非叶结点
4．删
插入考虑相反首先必须找删关键字结点求删结点中关键字数ém2ù1否左(右)兄弟结点调关键字左右兄弟结点均关键字(结点中少量关键字)必须进行结点合
5．查找性分析
B树中进行查找时查找时间花费搜索结点（访问外存）取决B树深度
结：
含 N 关键字 B树进行次查找需访问结点数超logém2ù((N+1)2)+1
9·3 哈希表
9·3·1 什哈希表 约12min
1 散列函数提出
前讲检索检索关键字记录关键字较相等检索成功否继续较希找函数关键字进行计算函数值解释记录存储址散列检索函数散列函数散列法存储线性表散列表查找时样方法计算址相应单元找记录找查找成功该单元记录查找失败该单元记录找继续查找种方法称关键字址转换法
2 散列检索术语
（1） 碰撞（突）：两关键字散列函数值相key1<>key2f(key1)f(key2)突避免举标识符例子1939年 davenport生日悖
（2） 义词：发生碰撞（突）关键字称义词
（3） 负载子：定义a（散列表中结点数目）（散列表长度）a般取06~09
（4） 采散列表着重考虑两问题：选择散列函数选择种解决碰撞（突）方法
3 散列表较详细叙述
根设定散列函数h(key)处理突方法组关键字映象限连续址集（区间）关键字址集中象作记录表中存储位置种表称散列表映象程散列（哈希造表）存储址称散列址哈希址
9·3·2 哈希函数构造方法 约20min
1 数字选择法 分析关键字位掉分布均匀位留均匀位作址
2 方取中法 数方结果中间位数位关系取中间位作址
3 折叠法 关键字位数较分布均匀折叠法折叠法分移位折叠间界折叠
4 余法 关键字p余数作址：h(key)key mod p
通常p取散列表长素数
5 基数转换法 基数数作基数数转换基数数
6 机数法 H(key)random(key)
9·3·3 处理突方法 约20min
处理突方法分两类：拉链法开放址法
1 拉链法
拉链法基思想散列表（量）元素两域组成域存放关键字域址指针指该关键字义词义词该域空
（1） 建立分离义词子表方法：象前动态建立单链表样义词建成单链表例关键字序列28325537740738480180320365949177551961199设量空间0—18散列函数h(key)key mod 19
检索（查找）方法先计算关键字址该址处关键字检索失败该址正找关键字检索成功该址关键字找关键字链查找直检索成功链空时失败
(2)建立结合义词子表方法： 该方法动态开辟空间建立单链表利散列表量空间遇义词时量空间中前找尚未占空间义词放入中关键字址（标）该义词处拉链（静态链表）种方法易产生堆积（聚集）义词非义词争夺散列址解决方法两遍处理：第遍插入义词子表表头关键字第2遍插入关键字
2 开放址法
开放址法处理突基思想：发生突时某种方法散列表中形成探查序列着探查序列逐单元查找直找定关键字碰开放址（该单元空）止插入时碰开放址插入中查找时碰开放址查找失败
（1） 开放定址法
Hi(H(key)+di) mod m (i12…m1)
中H(key)散列函数m散列表长度di增量序列三种取法：
· di12…m1 称线性探查散列探查单元序列：d+1d+2…m10…d1
· di12 1222 2232…+()k2(k· di伪机数序列称伪机探查散列
（2） 双散列函数探查法
散列函数计算散列址发生突时第二散列函数进行计算设两散列函数h1h2关键字变量设m素数取
h1(key)key mod mh2(key)key mod (m2)+1h2(key)[keym] mod (m2)+1
h1(key)d发生碰撞双散列函数探查序列：
(d+h2(key)) mod m (d+2h2(key)) mod m (d+3h2(key)) mod m
双散列函数探查法检索程造表类似
9·3·4 散列表查找分析 约12min
三结 约3min
1B－树 2哈希表
四作业 约6min
1．序列（245642867061）构造23树
2．已知散列函数H(K)K mod 12健值序列2537524384991201526117082采拉链法处理突试构造开散列表计算查找成功均查找长度
课 时 授 课 计 划
20112012学年第 学期 第14周
授 课 日 期
6月13日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 排序概念 插入排序 快速排序
教学目求：
1 解排序定义种排序方法特点熟悉种方法排序程原基关键字间较进行排序方法排序程原分插入排序交换排序选择排序排序计数排序等五类
2 掌握种排序方法时间复杂度分析方法关键字间较次数分析排序算法均情况坏情况时间性
3．理解排序方法稳定稳定含义弄清楚什情况求应排序方法必须稳定
教学重点：
熟悉种方法排序程原
教学难点：
熟悉种方法排序程原
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
现实生活中遇问题引入排序作引入排序
二讲课进程设计
第十章 部 排 序
10·1 基概念 约15min
1 排序定义：排序中结点（数元素）称记录记录集合称文件存中文件常称线性表
2 排序分类
部排序外部排序
部排序分5类：插入排序选择排序交换排序分配排序排序
3 稳定排序稳定排序
排序文件中关键字相等记录排序前相次序排序前未发生变化种排序称稳定排序否稳定排序稳定排序稳定排序表示排序方法说明种方法差
4 排序中记录存储方式 序存储结构 静态链表 址排序
5 排序算法评价
（1） 算法执行时需时间 情况差情况均情况
算法执行时需附加空间 特说明书排序指记录关键字递增排序数组作排序记录文件存储结构
10·2 插入排序
10·2·1 直接插入排序 约10min
1 直接插入排序基思想：
先假定第记录序序列然第二记录开始次记录插入前边序序列中直全部记录序列序避免总查询文件尾特设监视哨
2 直接插入排序实例模拟
3 直接插入排序算法
4 直接插入排序算法复杂度 空间复杂度：占单元（r[0]）
时间复杂度：
（1）佳情况：排序文件已序时关键字进行次较总进行n1次较记录移动次数2(n1)
（2）差情况：排序文件完全逆序时第i（2（2） 均情况 均较次数均移动次数均约n24
10·2·2 希尔(shell)排序 约20min
称缩增量排序shell1959年提出
1 基思想
排序记录较少排序记录基序时直接插入排序效率较高基种思想希尔提出排序记录分d组相距d记录放组进行直接插入排序
2 Shell 排序分组选择
认di取成奇数认di间互质di系列选没1外公子
3 排序实例
4 Shell 排序算法
5 Shell 排序算法复杂度
10·3 快速排序
10·3·1 起泡排序 约15min
1 起泡排序基思想
起泡排序称泡排序排序记录R1R2…Rn应关键字K1K2…K n 起泡排序作法：
（1） K1K2 逆序（K1>K2）交换然较K2K3……直Kn1Kn时关键字（第n位置）趟起泡排序进行n1次较
（2） 重复（1）较第n1元素（关键字）称第二趟较
（3） 进行n1趟较完成整排序
2 起泡排序实例模拟
3 起泡排序算法
4 起泡排序算法时间复杂度
起泡排序较次数记录初始序关正序时较次数n1交换次数0逆序时较次数交换次数均：
（n1）
移动次数n(n1)存储开销记录空间供交换
10·3·2 快速排序 约25min
1 快速排序基概念
第记录枢轴查询记录序列确定枢轴位置枢轴排序文件分成两部分：枢轴左面记录关键字关键字枢轴右面记录关键字关键字枢轴左右两部分继续实施程直全部文件序
2 快速排序实例模拟
3 快速排序算法
4 快速排序时间复杂度
较次数约nlog2n交换次数约nlog2n6移动次数等nlog2n排序文件序（正序逆序）快速排序退化成起泡排序（n1）≈n22存储开销栈深度超log2n
5 快速排序差情况改进
防止差情况出现般采取三者取中法确定枢轴第记录记录中间位置记录中选取值中间作枢轴样防止差情况出现
三结 约5min
1插入排序 2快速排序
四作业 约5min
1关键码序列（503087061908170897275653426）例手工执行排序算法写出趟排序结束时关键码状态：
1）直接插入排序 2）希尔排序（增量d[1]5） 3）快速排序：
课 时 授 课 计 划
20112012学年第 学期 第14周
授 课 日 期
12月15日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 选择排序 排序 基数排序 种部排序方法较讨
教学目求：
1 解排序定义种排序方法特点熟悉种方法排序程原基关键字间较进行排序方法排序程原分插入排序交换排序选择排序排序计数排序等五类
2 掌握种排序方法时间复杂度分析方法关键字间较次数分析排序算法均情况坏情况时间性
3．理解排序方法稳定稳定含义弄清楚什情况求应排序方法必须稳定
教学重点：
1选择排序 2排序
3基数排序
教学难点：
1堆排序
作业参考书：
种排序应
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
前面两种排序引入面排序
二讲课进程设计
104 选 择 排 序
10．4．1 直接选择排序 约15min
1 直接选择排序基思想
设排序文件n记录第趟进行n1次较选出关键字记录第记录交换第二趟进行n2次较选出关键字次记录第二记录交换……进行n1趟直排序文件全部序
2 直接选择排序实例演示
3 直接选择排序算法
4 直接选择排序算法复杂度
直接选择排序较次数记录初始序关较次数：
（n1）
交换次数超(n1)次文件初始正序时发生交换初始文件逆序时发生（n1）次交换移动次数3(n1)
10·4·2 树形选择排序 约7min
1 树形选择排序基概念
树形排序步骤：
（1） n排序关键字两两较n2较关键字保留
（2） n2关键字两两较n4较关键字保留
（3） 反复进行述操作直关键字（树根）
(4) 关键字输出原位置改极数位置相关部分重新（树根方）进行较选出次关键字保留结果直全部排序完成
该方法直接选择排序速度提高缺点：
（1） 需开储存空间保存排序结果
（2） n排序关键字需额外（n1）部结点（包括根结点）增加存开销
（3） 关键字改极数兄弟结点较属余
2 树形选择排序算法复杂度
树形选择排序第次选值时较n1次选次值较log2n次总较次数(n1)+(n1)log2nnlog2n结点移动次数超较次数总开销O（nlog2n）
10．4．3 堆排序 约20min
1 堆定义
堆含n关键字{k1k2…kn}序列具特性：
ki ki
ki>k2i
ki>k2i+1 (1 ki>k2i
满足式（1）称极化堆极堆堆满足式（2）称极化堆极堆堆节极化堆例子进行讲解
堆完全二叉树关系：堆n元素（关键字）序列满足完全二叉树序存储中结点间关系（双亲子女序号间关系）
2 堆排序基问题
然堆顶元素（关键字）元素排序序列元素输出元素调整成堆新堆顶元素排序序列第二元素通堆序序列变序序列堆排序基问题：建堆 调堆
3 调堆
元素堆顶元素交换（相堆顶元素输出）时堆顶倒数第二元素堆顶元素外余元素均符合堆定义面采筛选法包括堆顶元素元素调成堆
4 建堆
具n结点完全二叉树叶子结点认符合堆定义非终端结点编号n2该结点开始直根结点次调面筛选法完成堆建立具体算法放面堆排序算法中
5 堆排序算法
6 堆排序算法分析
时间复杂度O（nlogn）需记录供交换辅助存储空间
10·5 排序 约10min
1 排序基思想
设排序文件n记录开始首先假定n记录序（然记录然序）然进行相邻序子文件合成较子文件直整文件序二路说第次长1序子文件两两长2éù序子文件两两长4éù序子文件直长n序文件
2 二路排序算法
3 二路排序时间复杂度
第i趟排序序子文件长度2i具n记录文件排序必须做「log2nù趟趟花时间O（n）二路排序时间复杂度O（nlog2n）需空间O（n）
3·7 种排序方法较
10·6 基数排序
10·6·1 关键字排序 约8 min
1 分配排序实例
（1） 扑克牌排序
扑克牌花色面值（点数）规定花色高面值花色中规定梅花>方块>红心>黑桃面值中2<3<4<…<10方法1：先花色分成4堆堆面值排序花色序收集起种方法高位（MSD）优先法
方法2：先面值分成13堆13堆排序花色分成4堆花色序收集起种方法低位（LSD）优先法
（2） 卡片排序
卡片日期（年月日）建立然建立日期关键字进行排序
方法1：先年份分堆年卡片月份分堆月卡片日分堆序收集卡片种方法高位（MSD）优先法
方法2：先日分堆收集月份分堆收集年分堆收集种方法低位（LSD）优先法
2分配排序方法
高位（MSD）优先法高位分成干子集子集分成子集子集中排序收集低位（LSD）优先法低位开始高位结束进行干次分配收集
关键字字段时分配排序方法000999
10·6·2 链式基数排序 约15min
低位优先法单关键字情况
1 基数排序基思想
n记录关键字进行排序关键字成d元组：
ki(ki1 ki2 kid)
中
c0排序时先kid 值记录分r（称基数）盒子中次收集然kid1值样作直ki1分配收集序列止排序结束
关键字数字时r10 0关键字字母时 r26 ’A’2 基数排序实例模拟
3 基数排序算法
107 种排序方法综合较 约12min
1时间性 均时间性 排记录序列关键字序序时 简单选择排序堆排序排序时间性记录序列中关键字分布改变
2空间性
指排序程中需辅助空间
1)简单排序方法(包括：直接插入起泡简单选择) 堆排序空间复杂度O(1)
2) 快速排序O(logn)递程序执行程中栈需辅助空间
3) 排序需辅助空间空间复杂度 O(n)
4) 链式基数排序需附设队列首尾指针空间复杂度 O(rd)
3排序方法稳定性
1) 稳定排序方法指两关键字相等记录序列中相位置排序前排序没改变
2) 关键字记录序列进行LSD方法排序时必须采稳定排序方法
3) 稳定排序方法举出实例说明
4) 快速排序堆排序希尔排序 稳定排序方法
4关排序方法时间复杂度限
三结 约7min
1种排序方法进行总结
2章讨种排序方法基数排序外方法基较关键字进行排序排序方法
四作业 约3min
101关键码序列（503087061908170897275653426）例手工执行排序算法写出趟排序结束时关键码状态： 1）堆排序： 2）排序 3）基数排序
102编写教科书1022节中述链表插入排序算法
103 2路排序策略先排序序列扫描遍找出划分干序子列子列作初始段试写出算法链表结构实现策略
课 时 授 课 计 划
20112012学年第 学期 第15周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 排序查找算法辅导（）
教学目求：
进步掌握种排序查找方法
教学重点：
掌握方法
教学难点：
选择排序查找方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：出问题――学生思考――学生解答――问题讲解
讲课进程设计
排序查找算法辅导
题先学生做学生做情况讲解
1 （约8min）设L单链表头结点址数结点数正整数相试设计利直接插入原该链表整理成数递增序单链表算法
2 （约8min）二路插排序排关键字序列r[1n]中关键字分二路分序插入辅助量d[1n]前半部半部（注量d视循环表）原先r[l]赋d[1]r[2]记录开始分二路插入编写实现二路插入转序算法
3 （约8min）N记录存储带头结点双链表中现双起泡排序法升序进行排序请写出种排序算法
（注：双起泡排序相两趟排序方相反起泡）
4（约8min）设数组中存放序关键序列K1K2……Kn现求Kn放元素排序正确位置试编写实现该功算法求较关键字次数超n
5．（约8min）设序放置n桶桶中装粒砾石粒砾石颜色红白蓝求重新安排砾石红色砾石前白色砾石居中蓝色砾石居重新安排时粒砾石颜色次允许交换操作调整砾石位置 6．（约12min）设文件（R1R2……Rn）堆Rn+1意结点试设计算法该算法Rn+1添加堆中添加形成文件堆求算法时间复杂性O(log2n)
课 时 授 课 计 划
20112012学年第 学期 第15周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 排序查找算法辅导（）
教学目求：
进步掌握种排序查找方法
教学重点：
掌握方法
教学难点：
选择排序查找方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：出问题――学生思考――学生解答――问题讲解
讲课进程设计
7．（约10min）数结构DEAP定义：DEAP棵完全二叉树者棵空树者满足列特性：（1）树根包含元素．（2）左子树堆（MINHEAP）右子树堆（MAXHEAP）．（3）右子树非空设ｉ左子树结点ｊ右子树中ｉ相应结点．样ｊ结点存取ｊ右子树中ｉ父结点相应结点结点ｉ关键字总等结点ｊ关键字值．
DEAP例子右图示结点１５相应结点２０结点１
９应结点２５．
（1） 出该DEAP中插入结点４结果．
（2） 写出DEAP中插入新结点算法．
（3） CPASCAL语言编写实现述算法程序．
8 (约6min)出折半查找递算法出算法时间复杂度性分析
9(约7min)设记录R1R2…Rn关键字值序存贮数组r[1n]中r[n+1]出设立监督哨关键字值+∞ 试写查找定关键字k 算法画出查找程判定树求出等概率情况查找成功时均查找长度
10(约7min)二叉排序树采二叉链表存储写算法删节点值X结点求删该结点树然棵二叉排序树高度没增长（注：考虑删结点根情况）
11(约10min)二叉排序树结构中数元素值相设计算法实现递增序印结点数域求相数元素仅输出算法应报出滤掉未输出数元素数图示二叉排序树输出：101213151821273542．滤掉3元素
12．(约10min)知输入关键字序列（１００９０１２０６０７８３５４２３１１５）址区０~１１设计哈希表函数述关键字散０~１１中画出散列表（突线性探测法）写出查找算法计算等概率情况查找长度
课 时 授 课 计 划
20112012学年第 学期 第16周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 复1～5章
教学目求：
1 数结构中基概念做更深理解
2 掌握线性表法
3 栈队列作
4 串应
5 数组应
教学重点：
章知识点
教学难点：
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：出容提学重点例题解析
讲课进程设计
第章 绪 约10min
容提
1 数结构研究容2 基概念：数数元素数象数结构数类型抽象数类型形数类型3 算法定义五特征4 算法描述：类PASCAL语言5 算法设计求6 算法分析
二学重点
1 数结构三素：逻辑结构物理（存储）结构种结构定义操作（运算） 2 抽象数类型定义表示实现方法3 类PASCAL书写规范程（函数）中值参变参差程调规4 计算语句频度估算算法时间复杂度
三例题解析
1 写出语句执行次数（左边括号数字语句序号）
第二章 线性表 约25min
容提
1．线性表元素间约束力强类数结构 2．线性表逻辑结构定义线性表定义操作3．线性表存储结构：序存储结构链式存储结构4．线性表操作两种存储结构中实现5．元项式线性表表示方法高次（稀疏）项式抽象数类型定义表示加法实现
二 学重点
1． 线性表逻辑结构指线性表数元素间存着线性关系序存储结构中元素存储先位置反映出种线性关系链式存储结构中指针反映种关系2． 序存储结构量（维数组）表示定标存取相应元素属机存取存储结构3． 知道某结点指针存取该元素链表存取需头指针开始链行链表属机存取结构4． 链表章学重点难点理解头结点首元结点元素结点差理解头结点插入删等操作时算法统设立（头结点第元素前插入元素删第元素时链表头指针总变化）掌握通画出结点图进行链表生成插入删遍历等操作5． 链表操作中应注意链意外断开某结点前插入元素删某元素必须知道该元素前驱结点指针6． 时间空间复杂度角度综合较线性表序链式两种存储结构特点7． 静态链表重点难点应链表进行较理解
三例题解析
１．设线性表序存储结构存a(1n)中试编写算法该线性表逆置
２．编写单链表进行排序算法
3．设两非递减序线性表mn元素（m>0n>0）分存维数组ab中a 存储空间足够试编写算法两线性表合成线性表结果非递减序求算法时间复杂度o(m+n)
第三章 栈队列 约30min
容提
1．数结构角度讲栈队列线性表操作线性表操作子集属操作受限线性表数类型角度线性表相重抽象数类型2．栈定义操作栈准端进行插入删操作线性表该端称栈顶端3．栈序链式存储结构两种结构实现栈操作4．栈应：表达式求值递程消递5．队列定义操作队列删端（尾）插入队列端（头）两种存储结构中需队头队尾两指针6．链队列空条件首尾指针相等循环队列满条件判定队尾加1等队头设标记两种方法
二 学重点
1．栈队列操作两种存储结构实现2．中缀表达式转成前缀缀表达式求值3．递解决问题：定义递数结构递问题解法递掌握典型问题算法
4． 链队列删时空处理（令队尾指针指队头）特仅设尾指针循环链队列种操作实现5． 循环队列队空定义队头指针等队尾指针队满单元（教材中示） 设标记办法（面例题）里特注意取模运算6． 续章节中注意栈队列应串中心称判定二叉树遍历递非递算法图深度优先遍历等栈树层次遍历图宽度优先遍历等队列
三例题解析
1．两栈享量空间编写入栈出栈算法
2．中缀表达式转换成缀表达式进行表达式求值
3设标记判定循环队列满编写入队出队算法
第四章 串 约10min
容提
1 数元素字符线性表串定义操作2 基操作编制算法求串操作3 存储结构串数元素字符线性表存结点问题静态动态（块链结构堆结构）存储优缺点 4 朴素模式匹配算法改进（KMP）算法
二学重点
1 串基操作编写串操作（indexreplace等）2串模式匹配中求匹配串nextval 函数值3朴素模式匹配时间复杂度O(m*n) KMP算法O(m+n)般情况前者实际执行时间似O(m+n)采4KMP算法仅串模式串存许部分匹配时显前者块优点串回嗍5 串操作存储结构实现
三例题解析
1利串基运算create(s)assign(st)length(s)substr(sstartlen)concat(s1s2)编写操作replace算法
2 设目标 t’abcaabbabcabaacbacba’模式串 p’abcabaa’
(1)计算PNEXTVAL函数值(2)写出算法画出利KMP算法进行模式匹配时趟匹配程
第五章 数组广义表 约25min
容提
1 数组逻辑结构定义存储2 稀疏矩阵（含特殊矩阵）存储运算3 广义表定存储4 广义表运算递算法
二学重点
1 数组（二维）行序存储中址计算方法2 特殊矩阵压缩存储时标变换3 稀疏矩阵三元组表存储结构矩阵移植算法4 稀疏矩阵十字链表存储方法十字链表生成算法5 广义表HEADTAIL 运算6 定广义表画出存储结构7 广义表递算法掌握编写递算法
三例题解析
1字符串二维数组A[08110] 元素6字符组成字符占存储单元（1）存放A需少字节？（2）A第8列第5行占少字节？(3) 行序存储时A[85]列存储时元素时址相？
2求列广义表操作结果：(1)HEAD(TAIL(HEAD(((ab)(cd))))(2)TAIL(HEAD(TAIL(((ab)(cd))))
解答 （1）b (2) (d)
3广义表HEADTAIL操作写出题表达式原子banana列广义表中分离出
（1）（apple(pear)((banana))(((orange)))）（2） L2(apple(pear(banana)orange))
课 时 授 课 计 划
20112012学年第 学期 第16周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 复6～10章
教学目求：
1树基知识
2图基知识
3查找应
4排序选择
教学重点：
章重点
教学难点：
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
讲课进程设计
第六章 树二叉树 约25min
容提
1树复杂非线性数结构树二叉树递定义基概念术语2二叉树性质存储结构3二叉树遍历算法（递非递）4线索二叉树5树存储结构树森林遍历二叉树相互转换6二叉树应：表达式求值判定问题哈夫曼树哈夫曼编码
二学重点
（章容课程重点）
1二叉树性质证明方法种方法推广K叉树2二叉树遍历递算法书中介绍三种（先中序）方法三种应会前序中序非递遍历遍历基础导出许实算法求二叉树高度结点层次数度012结点数二叉树相似全等复制等等算法3二叉树遍历前序中序序列序中序序列唯构造棵二叉树手工模拟编写算法前序序序列唯确定棵二叉树4二叉树线索化实质建立结点相应序列中前驱继间直接联系序（前中）进行种（全前驱继）线索化求某结点相应前驱继5完全二叉树性质序存储结构二叉树链表存储结构相互转换6树双亲表示法孩子兄弟表示法间相互转换7树森林二叉树间相互转换（连线切线旋转）8哈夫曼树定义构造求哈夫曼编码
三例题分析
1二叉树中查找数域 x结点存返回该结点指针否返回空指针
２．设二叉树采二叉链表作存储结构试编写算法求二叉树结点数
３．印二叉树中结点x（假定存）祖先结点
第七章 图 约25min
容提
1． 图定义概念术语基操作 2．图存储结构3．图遍历4．图应（连通分量生成树拓扑排序关键路短路）
二学重点
图应广泛种数结构章门课程重点
1 基概念中连通分量生成树邻接点重点2 图复杂数结构序链式两种存储结构：数组表示法（重点邻接距阵） 邻接表两种存储结构图图均适十字链表图种表示图邻接表逆邻接表合邻接重表图邻接表改进边结点数量减少半（正等边数量）3 图遍历图种算法基础应熟练掌握图深度广度优先遍历手工模拟图遍历中栈队列指针状态变化4 （强）连通图中程次调深（宽）度优先遍历程（dfsbfs）遍历完全部顶点方法求出连通分量数画出遍历中形成深（宽）度优先生成树5连通图生成树唯生成树边权值唯 应熟练掌握primkruscal算法特手工分步模拟生成树生成程6 拓扑排序图入度（先）零顶点种排序结果唯关键路拓扑序前提求出源点汇点长路径应掌握两种算法熟练手工模拟理解减少关键活动时间缩短工期指该活动关键路径减少尚未改变关键路前提效7 单源点顶点顶点间短路问题掌握算法熟练手工模拟
三例题解析
1邻接重表实现图种运算
2 编写图深度优先非递遍历算法
第九章 查找 约25min
容提
1 章介绍查找表称集合数结构元素间约束力差数结构：元素间关系元素仅集合中 2 查找表操作：查找检索插入删成员关系判断
3 静态查找表：序表序表静态树表索引序表 4 动态查找表：二叉排序树衡二叉树B树B+树键树 5 哈希表
二 学重点
1查找表称集合数结构元素间关系非常松散操作需助数结构实现章列举三种方法（静态查找表动态查找表哈希表）实现查找表运算2序表引设置监视哨查找效率提高序表均查找长度超树深度判定树唯索引序查找综合述二者优点较快速查找适应动态变化求3二叉排序树形态取决元素输入序中序遍历结点序序列应熟练掌握建立查找插入删算法4佳二叉排序树均查找长度短二叉排序树衡二叉树介佳般间折中应熟练掌握手工绘制衡二叉树5 键树中结点关键字字符该树序树（层兄弟间左右递增结束符号）6 哈希表查找表（集合）表示方法根选定哈希函数处理突方法关键字映哈希表中突避免7 哈希表中关键字查找哈希函数计算序折半查找元素删作标记物理删
三例题解析
1．设二叉排序树中元素均整数试编写算法输出元素值
2． 编写二叉排序树插入结点s算法
3．编写索引序表中查找数k算法
4．已知含100记录表关键字中国名拼音请出表哈希表设计方案求等概率情况查找成功均查找长度超3
第十章 部排序 约25min
容提
1排序定义排序作线性表种操作2排序分类稳定排序稳定排序定义3插入排序（分插入二路插入表插入希尔插入排序）4交换排序（泡排序快速排序）5选择排序（简单选择排序树形选择排序堆排序）6排序基数排序
二学点
1．种排序基基思想2．差情况排序性分析否稳定排序结3．插入排序基假定排序文件第记录序然第二记录起次插入已排序序子文件中直整文件序减少较次数移动次数进行种改进产生折半二路表插入希尔等系列插入排序4．交换排序基相邻记录较逆序进行交换泡排序快速排序交换排序例子快速排序目前快部排序法应采三者取中法防止性退化5．简单选择排序树形选择排序堆排序选择排序例子堆排序较重差性快速排序差性（Ologn）6．排序基数排序时间复杂度O(n2)排序稳定排序希尔排序快速排序堆排序等时间性排序方法包括简单选择排序稳定排序7．种排序方法学应掌握质（排序基思想）举反三
二例题解析
1．设排序文件n ( n>0 )记录试编写算法全部排序第j (02．已知（k1k2┄kp）堆试编写算法（k1k2┄k[p]k[p+1]）调整堆算法复杂度O(logn)
3编写排序非递排序算法
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
教 案
课程名称 数结构 教材数结构（C语言版）
教学时数 56 课程性质 必修
课班级（数）信（53）
信息 系（部） 信 教研室
课教师
山东科技学泰山科技学院
课 时 授 课 计 划
20112012学年第 二学期 第1周
授 课 日 期
2月 20 日
星期1
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 第1章 绪 1112
教学目求：
1 解数结构基概念
2 理解常术语
教学重点：
数结构基概念术语
教学难点：
数元素间四种结构关系
作业参考书：
1 什数结构？
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：介绍——开课——引入——展开——举例——结——作业
介绍课程介绍 约8min
课时：64
二引入 约2min
问题提出引入
三讲课进程设计
11 什数结构
111数结构关系 约15min
数结构 +算法 程序
程序设计 计算机处理问题编制组指令集
算法 处理问题策略
数结构 问题数学模型
112计算机应特点： 约25min
l) 处理数量具定关系
2) 操作单纯数值计算更需进行组织理检索
举例说明：
1) 学生成绩表 2)井安棋弈 3)交通理
结
计算机操作象关系更加复杂操作形式单纯数值计算更具定关系数进行组织理称非数值性处理计算机够更效进行非数值性处理必须弄清楚操作象特点计算机中表示方式操作具体实现手段
12 基概念术语
111数数结构 约20min
数：客观事物符号表示
输入计算机中计算机处理符号集合计算机操作象总称计算机处理信息某种特定符号表示形式
数元素：数（集合）中体数结构中讨基单位
数象：性质相数元素集合数子集
数结构：相互间存种种特定关系数元素集合种集合称结构
数逻辑结构结四类
种类
特征
示例
集合
元素间松散关系
线性结构
元素间严格关系
面成绩表中元素
树形结构
元素间严格关系
图状结构（网状结构）
元素间关系
数结构形式定义数结构二元组
数存储结构 ：—— 逻辑结构存储器中映
数元素映象方法：计算机中存储信息单位：位8位字节两字节字字节字更二进制位称位串逻辑描述中位串称元素结点
关系映象方法：序映象 链式映象
122数类型 约5min
数类型 值集合定义集合 组操作总称
123抽象数类型 约20min
指数学模型定义数学模型组操作
关键：关心逻辑特征需解存储方式定义样必关心存储
抽象数类型表示法：
三元组表示：（DSP）
中D数象SD关系集PD基操作集
书中定义格式：
ADT 抽象数类型名{
数象：<数象定义>
数关系：<数关系定义>
基操作：<基操作定义>
}ADT 抽象数类型名
ADT 两重特征
数抽象 数封装
四次课结： 约3min
1 熟悉名词
2 术语含义
3 掌握基概念
五作业 约2min
2 什数结构？
课 时 授 课 计 划
20112012学年第 二 学期 第1周
授 课 日 期
2月 24日
星期5
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 抽象数类型表示实现 算法算法分析
教学目求：
类C语言种句型算法描述规范
教学重点：
类C语言种句型算法描述规范
教学难点：
类C语言种句型算法描述规范
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：复——引入——展开——举例——结——作业
复： 约5min
1数结构基概念
2基术语
二引入 约2min
程序设计程遇问题引入
三讲课进程设计
13 抽象数类型表示实现
131基操作： 约15min
AssignComplex( &Z v1 v2 )
操作结果：构造复数 Z实部虚部
分赋参数 v1 v2 值
DestroyComplex( &Z)
操作结果：复数Z销毁
GetReal( Z &realPart )
初始条件：复数已存
操作结果：realPart返回复数Z实部值
GetImag( Z &ImagPart )
初始条件：复数已存
操作结果：ImagPart返回复数Z虚部值
Add( z1z2 &sum )
初始条件：z1 z2复数
操作结果：sum返回两复数z1 z2 值
132书采类C语言作简说明 约18min
1 预定义常量类型
2数结构存储结构typedef
3算法描述函数形式：
4 算法描述中赋值语句形式：
5 算法描述中选择结构语句形式：
6 算法描述中循环结构语句形式：
7 描述算法中结束语句形式：
8 算法描述中输入输出语句形式：
9 算法描述中注释格式：
10 算法描述中扩展函数：
11逻辑运算约定
14 算法算法分析
141算法 约10min
算法解决某类问题规定限长操作序列算法必须满足五重特性：
1．穷性 2．确定性 3．行性 4．输入 5．输出
142算法设计原 约10min
设计算法时通常应考虑达目标：
1．正确性2 读性3．健壮性4．高效率低存储量需求
143算法效率衡量方法准 约20min
通常两种衡量算法效率方法
事统计法 缺点：1．必须执行程序 2．素掩盖算法质
事前分析估算法 算法执行时间相关素：1．算法选策略2．问题规模3．编写程序语言4．编译程序产生机器代码质量5．计算机执行指令速度
算法 控制结构 + 原操作 （固数类型操作）
算法执行时间致等语句执行时间总语句执行时间指该条语句执行次数执行次需时间积
计算时间复杂度时采记号O数学符号严格数学定义：T(n)f(n)定义正整数集合两函数T(n)O(f(n))表示存正常数cn0n>n0时满足0
1 执行条读写赋值语句O(1)时间2次执行系列语句时间准
3判断语句耗时执行语句时间检验条件需O(1)4循环语句运行时间次叠代中执行循环体检验循环条件耗时常法准
算法两部分时间复杂度T1(n)o(f(n)) T2(n)o(g(n)) O：
求准 T1(n)+ T2(n)O(max(f(n)g(n)) 法准 T1(n)* T2(n)O( (f(n )*g(n))
144算法存储空间需求 约10min
算法空间复杂度定义
S(n) O(g(n))
表示着问题规模 n 增算法运行需存储量增长率 g(n) 增长率相
算法存储量包括
1．输入数占空间2．程序身占空间3．辅助变量占空间
四结： 约5min
1 理解算法五素确切含义
2 掌握计算语句频度估算算法时间复杂度方法
五作业 约5min
1试编写算法求元项式Pn(x)a0+a1x+a2x2+a3x3+…anxn值Pn(x0)确定算法中语句执行次数整算法时间复杂度求时间复杂度规定算法中求幂函数注意：题中输入ai(i01…n)xn输出Pn(x0)通常算法输入输出采列两种方式：
• （1）通参数表中参数显式传递（2）通全局变量隐式传递
• 试讨两种方法优缺点题算法中认较种方式实现输入输出
课 时 授 课 计 划
20112012学年第 二学期 第2周
授 课 日 期
2月 27 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 线性表类型定义 线性表序表示实现
教学目求：
1掌握线性表概念类型定义
2掌握线性表序表示实现方法
教学重点：
线性表类型定义
线性表序表示实现方法
教学难点：
线性表类型定义
线性表序存储实现方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：复——引入——展开——举例——结
引入 约3min
序算法引入
二讲课进程设计
2．1线性表类型定义
1211线性表定义 约27min
线性表n（n≥0）类型相数元素组成限序列
抽象数类型线性表定义：
ADT List {
数象
D＝{ ai | ai ∈ElemSet i12n n≥0 }
{称 n 线性表表长 称 n0 时线性表空表}
数关系
R1＝{
基操作：
结构初始化操作：
InitList( &L )
操作结果：构造空线性表L结构销毁操作：
DestroyList( &L )
初始条件：线性表 L 已存操作结果：销毁线性表 L
引型操作
ListEmpty( L )（线性表判空）
ListLength( L )（求线性表长度）
PriorElem( L cur_e &pre_e )（求数元素前驱）
NextElem( L cur_e &next_e )（求数元素继）
GetElem( L i &e )（求线性表中某数元素）
LocateElem( L e compare( ) )（定位函数）
ListTraverse(L visit( ))（遍历线性表）
加工型操作
ClearList( &L )（线性表置空）
PutElem( &L i &e )（改变数元素值）
ListInsert( &L i e )（插入数元素）
ListDelete(&L i &e) （删数元素）
212举例 约10min
两线性表合LALB
22 线性表序表示实现
221序映象 约15min
—— x 存储位置 y 存储位置间某种关系表示逻辑关系
简单种序映象方法： 令y存储位置x存储位置相邻线性表基操作序表中实现
InitList(&L) 结构初始化
LocateElem(L e compare()) 查找
ListInsert(&L i e) 插入元素
ListDelete(&L i) 删元素
211线性表操作 约20min
ListInsert(&L i e)实现：
首先分析
插入元素时线性表逻辑结构发生什变化？
线性表操作
ListDelete(&L i &e)实现：
首先分析：
删元素时线性表逻辑结构发生什变化？线性表类型实现
212线性表序存储结构特点： 约20min
种简单方便存储方式求线性表数元素次存放连续存储单元中利数元素存储序表示相应逻辑序种存储方式属静态存储形式 暴露问题
(1)做插入删元素操作时会产生量数元素移动 (2)长度变化较线性表次性分配足够存储空间空间常常充分利
(3)线性表容量难扩充
三结 约5min
1解线性表逻辑结构特性数元素间存着线性关系计算机中表示种关系两类存储结构序存储结构链式存储结构前者表示线性表简称序表者表示线性表简称链表
2熟练掌握两类存储结构描述方法线性表种基操作实现
课 时 授 课 计 划
20112012学年第 二 学期 第2周
授 课 日 期
3月 3 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 线性表链式表示实现 元项式表示相加
教学目求：
1掌握线性链表单链表静态链表概念表示实现方法
2掌握循环链表概念
3掌握双链表表示实现
教学重点：
1线性链表单链表表示实现方法
2双链表表示实现
教学难点：
1线性链表
2双链表存储表示
作业参考书：
写算法单链表中值重复结点删结果表中结点值均相
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：复——引入——展开——举例——结——作业
复 约5min
复线性表概念
二引入 约2min
线性表表示方便引入
三讲课进程设计
23 线性表链式表示实现
线性表序存储结构特点： 约10min
种简单方便存储方式求线性表数元素次存放连续存储单元中利数元素存储序表示相应逻辑序种存储方式属静态存储形式
暴露问题
(1)做插入删元素操作时会产生量数元素移动
(2)长度变化较线性表次性分配足够存储空间空间常常充分利
(3)线性表容量难扩充
231单链表 约10min
组址意存储单元存放线性表中数元素（组存储单元连续连续）
232结点单链表 C 语言描述 约10min
233单链表操作实现 约13min
生成链表程结点逐插入程
操作步骤：
1建立空表
2输入数元素an建立结点插入
3输入数元素an1建立结点插入
4次类推直输入a1止
234形式链表 约5min
1 循环链表2 双链表
235序表类型 约5min
24元项式表示
241元项式 约20min
计算机中线性表表示
P (p0 p1 …pn)
抽象数类型元项式定义：
ADT Polynomial {
数象：D＝{ ai| ai∈TermSeti12m m≥0
TermSet 中元素包含
表示系数实数表示指数整数 }
数关系：R1＝{
ai1中指数值＜ai中指数值 }
基操作：
CreatPolyn ( &P m ) 操作结果：输入 m 项系数指数
建立元项式 P
DestroyPolyn ( &P ) 初始条件：元项式 P 已存
操作结果：销毁元项式 P
PrintPolyn ( &P ) 初始条件：元项式 P 已存
操作结果：印输出元项式 P
PolynLength( P ) 初始条件：元项式 P 已存
操作结果：返回元项式 P 中项数
AddPolyn ( &Pa &Pb ) 初始条件：元项式 Pa Pb 已存
操作结果：完成项式相加运算：
Pa Pa＋Pb销毁元项式 Pb
SubtractPolyn ( &Pa &Pb )
… …
} ADT Polynomial
242元项式实现： 约10min
typedef OrderedLinkList polynomial
带表头结点序链表表示项式
四结 约5min
1够时间空间复杂度角度综合较线
性表两种存储结构特点适场合
五章作业： 约5min
写算法单链表中值重复结点删结果表中结点值均相
题样考虑先取开始结点中值结点值较发现相删掉然取第二结点值重复述程直结点
课 时 授 课 计 划
20112012学年第 学期 第3周
授 课 日 期
9月22日 五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 栈 栈应举例
教学目求：
1 栈数类型定义
2 栈序存储实现
3 掌握栈应方法理解栈重作
教学重点：
1栈序存储表示实现方法
2利栈实现行编辑利栈实现表达式求值
教学难点：
1栈定义
2利栈实现表达式求值
作业参考书：
1栈定义应
2栈特点
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约10min
1 什线性结构？
2 餐馆中叠叠盘子例引出栈特点
二讲课进程设计
31 栈类型定义
311栈栈顶(top)栈底(bottom)定义 约10min
312栈类型定义 约10min
32 栈应举例
例 数制转换 约10min
十进制数Nd进制数转换计算机实现计算基问题简单算法基列原理： N (N div d)×d + N mod d (中：div整运算mod求余运算)
例二 括号匹配检验 约10min
检验括号否匹配方法期急迫程度概念描述
三种情况应栈操作： 1．栈顶左括弧相匹配 2．栈中没左括弧等里3．栈中左括弧没等相匹配右括弧
例三 行编辑程序问题 约10min
户输入行程中允许户输入出差错发现误时时更正
合理作法：设立输入缓区接受户输入行字符然逐行存入户数区假设#退格符@退行符
例四 迷宫求解 约10min
假设栈S记录前路径栈顶中存放前路径通道块 纳入路径操作前位置入栈 前路径删前通道块操作出栈
例五表达式求值 约10min
表达式操作数(operand)运算符(operator)界限符(delimiter)组成
例六 实现递 约10min
递函数实现
递函数运行程类似函数嵌套调差仅调函数调函数函数保证层递调层数进行操作执行递函数程中需递工作栈
三结 约5min
1 掌握栈队列类型特点相 应应问题中正确选
2 熟练掌握栈类型两种实现方法特 应注意栈满栈空条件描述方法
四作业 约5min
14元素a1a2a3a4次通栈a4进栈前栈状态出栈序（ ） (A)a4a3a2a1 (B)a3a2a4a1 (C)a3a1a4a2 (D)a3a4a2a1
2栈特点（）
课 时 授 课 计 划
20112012学年第 学期 第3周
授 课 日 期
9月27日 三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 队列
教学目求：
1 熟练掌握循环队列链队列基操作实现算法
2 理解递算法执行程中栈状态变化程
教学重点：
1．链队表示实现
教学难点：1链队表示实现
作业参考书：
1．栈队列较
2．读程序段
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
日常生活中维持正常社会秩序出现常见现象什？
排队计算机程序中模拟排队数结构队列
二讲课进程设计
34 队列
1队列定义 约10min
2队列抽象类型定义 约15min
3队列基操作： 约20min
InitQueue(&Q) 操作结果：构造空队列Q
DestroyQueue(&Q) 初始条件：队列Q已存
操作结果：队列Q销毁存
QueueEmpty(Q) 初始条件队列Q已存
操作结果Q空队列返回TRUE否返回FALSE
QueueLength(Q) 初始条件队列Q已存
操作结果返回Q元素数队列 长度
GetHead(Q &e) 初始条件：Q非空队列
操作结果：e返回Q队头元素
ClearQueue(&Q) 初始条件：队列Q已存 操作结果：Q清空队列
EnQueue(&Q e) 初始条件队列Q已存
操作结果插入元素eQ新队尾元素
DeQueue(&Q &e) 初始条件：Q非空队列
操作结果：删Q队头元素e返回值
QueueTravers(Q visit())
队列类型实现
4链队列——链式映象 约15min
5循环队列——序映象 约20 min
队列程序设计中典型应例子作业排队问题
三结 约5min
1 熟练掌握循环队列链队列基操作实现算法特注意队满队空描述方法
2 理解递算法执行程中栈状态变化程
四作业 约10min
1线性表栈队列（）结构线性表（）位置插入删元素栈（）插入删元素队列（）插入元素（）删元素
2 指出述程序段功什
(1) void Demo1(SeqStack *S){
int i arr[64] n0
while ( StackEmpty(S)) arr[n++]Pop(S)
for (i0 i< n i++) Push(S arr[i])
} Demo1
课 时 授 课 计 划
20112012学年第 学期 第4周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 实验二 栈队列总结复
教学目求：
1 深入解栈队列特征便实际问题背景灵活运
2 巩固两种结构构造方法接触较复杂问题递算法设计
教学重点：
巩固两种结构构造方法接触较复杂问题递算法设计
教学难点：
巩固两种结构构造方法接触较复杂问题递算法设计
作业参考书：
数结构算法实现解析高 编著
教具：
课堂类型：
教学程：
停车场理
[问题描述]
设停车场停放n辆汽车狭长通道门供汽车进出汽车停车场车辆达时间先序次北南排列（门南端先达第辆车停放车场北端）车场已停满n辆汽车汽车门外便道等候旦车开走排便道第辆车开入停车场某辆车离开时开入车辆必须先退出车场路该辆车开出门外车辆原次序进入车场辆停放车场车离开停车场时必须停留时间长短交纳费试停车场编制述求进行理模拟程序
[测试数]
设n2输入数：（A’15）（A’210）（D’115）（A’3 20） （A’425）（A’530）（D’235）（D’440）（E’00）中A’表示达D’表示离E’表示输入结束
[基求]
栈模拟停车场队列模拟车场外便道终端读入输入数序列进行模拟理组输入数包括三数项：汽车达离信息汽车牌号码达离时刻组输入数进行操作输出数：车辆达输出汽车停车场便道停车位置车离输出汽车停车场停留时间应交纳费（便道停留时间收费）栈序结构实现队列链表实现
[实现提示]
需设栈时停放离汽车路停车场退出汽车序存储结构实现输入数达离时刻序栈中元素表示辆汽车包含两数项：汽车牌号码进入停车场时刻
[选作容]
（1） 两栈享空间思考应开辟数组空间少？
（2） 汽车种类占面积收费标准1辆客车15辆汽车占面积相1辆十轮卡车占面积相3辆汽车占面积
（3） 汽车直接便道开走时派前面汽车先开走路然次排队尾
（4） 停放便道汽车收费收费标准停放停车场车低请思考修改结构满足种求
课 时 授 课 计 划
20112012学年第 学期 第4周
授 课 日 期
10月8日 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 串
教学目求：
1熟悉串七种基操作定义利基操作实现传种操作方法
2熟悉掌握串定长序存储结构实现串种操作方法
3掌握串堆存储结构实现串种操作基方法
教学重点：
1串七种基操作定义
2串定长序存储
3串堆存储结构
教学难点：
1串七种基操作定义
2串堆存储结构
作业参考书：
串操作应
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
计算机非数值处理象基字符串数
二讲课进程设计
41串抽象数类型定义
1定义 约10min
串串长空串子串串位置相等空格串
2串抽象数类型定义 约10min
StrAssign (&T chars) StrCopy (&T S) DestroyString (&S) StrEmpty(S) StrCompare(ST) StrLength(S) Concat(&TS1S2) SubString (&SubSposlen) Index(STpos) Replace(&STV) StrInsert (&S pos T) StrDelete (&S pos len) ClearString(&S)
42 串表示实现
421串定长序存储表示 约15min
1串联接 2求子串
422串堆分配存储表示 约20min
通常C语言中提供串类型种存储方式实现系统利函数malloc( )free( )进行串值空间动态理新产生串分配存储区称串值享存储空间堆
423串块链存储表示 约10min
链表存储串值串数元素字符 8 位二进制数链表存储时通常结点中存放字符子串
44 串操作应举例
441文编辑 约20min
文编辑程序功强弱差基操作致：包括串查找插入删等基操作
户讲文（文件）包括干页页包括干行行包括干文字
文编辑程序讲整文成长字符串称文串页文串子串行页子串简化程序复杂程度简单文分成干行
三结 约5min
1 熟悉串七种基操作定义利基操作实现串种操作方法
2 熟练掌握串定长序存储结构实现串种操作方法
3 解串堆存储结构实现串操作基方法
4 解串操作应方法特点
四作业 约5min
假设串说明：
char s1[30]StocktomCA
s2[30]March 5 1999 s3[30] *p
(1)执行列语句s3值什
strcopy(s3s1) concat(s3) concat(s3s2)
(2)调函数strcompare(s1s2)返回值什
(3)调函数strcompare(&s1[5]ton)返回值什
(4)调函数strlength(concat(s1s2))返回值什
课 时 授 课 计 划
20112012学年第 学期 第5周
授 课 日 期
10月11日 三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 数组
教学目求：
1 掌握数组定义
2 掌握数组序表示方法
教学重点：
1 数组定义
2 数组序表示方法
教学难点：
数组序表示方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结
引入 约5min
前章讨线性结构中数元素非结构原子类型引入数组
二讲课进程设计
51 数组类型定义
抽象数类型定义 约5min
ADT Array {
数象：
数关系：
} ADT Array
二维数组定义 约10min
数象
D {aij | 0≤i≤b11 0 ≤j≤b21}
数关系
R { ROW COL }
ROW {
COL {
基操作： 约10min
InitArray(&A nbound1boundn) DestroyArray(&A)
Value(A &e index1 indexn) Assign(&A e index1 indexn)
52 数组序表示实现
类型特点 约10min
1) 引型操作没加工型操作
2) 数组维结构存储空间 维结构
两种序映象方式 约10min
1)行序序(低标优先)2)列序序(高标优先)
53 矩阵压缩存储
531特殊矩阵
a称矩阵 约15min
定义 压缩存储方式
b三角矩阵 约15min
定义 压缩存储方式
c 角矩阵 约20min
定义 压缩存储方式
三结
1数组特殊性
2数组存储
3特殊矩阵存储
课 时 授 课 计 划
20112012学年第 二 学期 第5周
授 课 日 期
3月23日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 稀疏矩阵 广义表
教学目求：
1掌握稀疏矩阵定义三元组表示
2掌握广义表定义链接存储结构
教学重点：
1三元组表示
2广义表存储结构
教学难点：
1三元组表示法
2定义
作业参考书：
1画出出广义表两种存储结构
2求广义表运算
3象矩阵中求标变换公式
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
特殊矩阵引入
二讲课进程设计
532 稀疏矩阵
1定义 约5min
两类稀疏矩阵：1) 特殊矩阵2) 机稀疏矩阵
2机稀疏矩阵压缩存储方法
1三元组序表 约20min
2行逻辑联接序表 约20min
3十字链表 约10min
54 广义表
广义表定义 约20min
1 广义表：
表头：非空广义表第元素α1 表尾：余元素（α2… αn）组成表
2 广义表抽象数类型定义 3广义表操作：
55广义表存储结构
广义表中数元素具结构．采链式存储结构表示广义表数元素结点表示
1 广义表头尾链表存储表示 约10min
typedef enum{ATOM LIST}ElemTag
typedef struct GLNode{
ElemTag tag
union{
AtomType atom
struct {struct GLNode *hp *tp}ptr
}
}*GList
三结 约5min
1 解数组两种存储表示方法掌握数组行存储结构中址计算方法2 掌握特殊矩阵进行压缩存储时标变换公式3 解稀疏矩阵两类压缩存储方法特点适范围领会三元组表示稀疏矩阵时进行矩阵运算采处理方法4掌握广义表结构特点存储表示方法读者根惯熟练掌握意种结构链表学会非空广义表进行分解两种分析方法：非空广义表分解表头表尾两部分者分解n子表
四课作业题 约5min
1画出面广义表两种存储结构图示： ((((a) b)) ((( ) d) (e f)))
2求列广义表运算结果：
（1） GetHEAD[((ab)(cd))] （2） GetTAIL[((ab)(cd))]
（3） GetTAIL[HEAD[((ab)(cd))]] （4） GetHEAD[TAIL[HEAD[((ab)(cd))]]]
（5） GetTAIL[HEAD[TAIL[((ab)(cd))]]]
3设三角矩阵An×n 三条角线元素逐行存数组B(13n2)中B[k] aij 求：（1） ij表示k标变换公式（2） k表示ij标变换公式
课 时 授 课 计 划
20112012学年第 学期 第6周
授 课 日 期
10月20日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 树定义基术语 二叉树
教学目求：
1掌握树二叉树基概念术语二叉树性质
2掌握二叉树两种存储结构
教学重点：
1二叉树性质定义
2链式存储结构
教学难点：
1二叉树性质
2链式存储二叉树基操作
作业参考书：
1棵度2树二叉树区
23结点树3结点二叉树
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
前章线性结构带问题引出非线性结构
二讲课进程设计
第6章 树二叉树
61树定义基术语
1 树定义 约10min
树包含n结点限集合(n>0)
Tree(DR)
中D具相性质数元素集合D中元素R空集否RD某二元关系H集合H描述二元关系：
（1） D中存唯称根元素r0关系H前驱
（2） 结点r0外K中结点关系H说前驱
（3）结点r0外结点rR存结点序列r0r1…rs
2 树抽象数类型定义 约5min
ADT Tree
数象 D：
数关系 R：
基操作 P：
InitTree(&T)
DestroyTree(&T)
CreateTree(&Tdefinition)
ClearTree(&T)
……
3 树术语 约10min
结点：数元素指子树分枝终端结点（叶子）分枝结点
子女：结点子树根称结点子女该结点称子女双亲
层次：根第层根子女第二层类推
深度：树中结点层次称树深度（高度）
度：结点分枝数目
树度：树中结点度
兄弟：双亲子女互称兄弟父母兄弟结点互称堂兄
祖先：结点祖先根该结点分支结点
子孙：某结点根子树中结点称该结点子孙
序树：结点子树左右序否称序树
森林 树相交集合根结点子树集合森林
RF{
62二叉树
621二叉树类型定义 约15min
二叉树种树型结构特点结点二棵子树（二叉树中存度2结点)二叉树子树左右分次序意颠倒二叉树空树根结点加两棵分称左子树右子树互交二叉树组成(树度2)
二叉树基操作：
查 找 类
Root(T) Value(T e) Parent(T e) LeftChild(T e) RightChild(T e)
LeftSibling(T e) RightSibling(T e) BiTreeEmpty(T) BiTreeDepth(T)
PreOrderTraverse(T Visit()) InOrderTraverse(T Visit()) PostOrderTraverse(T Visit())
LevelOrderTraverse(T Visit())
插 入 类
InitBiTree(&T) Assign(T &e value) CreateBiTree(&T definition) InsertChild(T p LR c)
删 类
ClearBiTree(&T) DestroyBiTree(&T) DeleteChild(T p LR)
622二叉树性质 约20min
性质1： 二叉树第i 层2i1 结点 (i≥1)
性质 2 ：深度 k 二叉树含 2k1结点（k≥1）
性质 3 ：棵二叉树含n0 叶子结点（0度结点）n2 度 2结点必存关系式：n0 n2+1
两类特殊二叉树：
满二叉树：指深度k含2k1结点二叉树
完全二叉树：树中含 n 结点满二叉树中编号 1 n 结点应（编号规左右）
性质 4 ：具 n 结点完全二叉树深度 ëlog2nû +1
性质 5 ：含 n 结点完全二叉树左右进行 1 n 编号完全二叉树中意编号 i 结点：（1）i1序号i结点根结点双亲结点i>1序号i结点双亲结点序号（2）2×i>n序号i结点左孩子2×i≤n序号i结点左孩子结点序号2×i（3）2×i＋1>n序号i结点右孩子2×i＋1≤n序号i结点右孩子结点序号2×i＋1
623 二叉树存储结构 约25min
1 二叉树序存储表示
2二叉树链式存储表示
1) 二叉链表 2)．三叉链表 3)．双亲链表 4)．线索链表
三结 约5min
1树二叉树定义
2二叉树性质
3存储结构
四作业 约5min
1棵度2树棵二叉树区？
2试分画出具3结点二叉树3 结点二叉树形态
课 时 授 课 计 划
20112012学年第 学期 第7周
授 课 日 期
10月25日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 遍历二叉树线索二叉树
教学目求：
1 遍历二叉树二叉树种操作基础掌握种遍历策略递算法灵活运遍历算法实现二叉树操作
2理解二叉树线索化实质熟练掌握二叉树线索化程中序线索化树找定结点前驱继方法
教学重点：
1 遍历二叉树二叉树种操作基础
2．种遍历策略递算法运遍历算法实现二叉树操作
教学难点：
种遍历策略递算法运遍历算法实现二叉树操作
二叉树线索化程中序线索化树找定结点前驱继方法
作业参考书：
写出二叉树前中序序列
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
二叉树结构引出结点遍历
二 讲课进程设计
63遍历二叉树线索二叉树
631二叉树遍历
问题提出 约7min
着某条搜索路径巡访二叉树中结点结点均访问次仅访问次（树线性化）
二叉树言三条搜索路径：
Ø 1．先层次遍历
Ø 2．先左（子树）右（子树）遍历
Ø 3．先右（子树）左（子树）遍历
二先左右遍历算法 约10min
先（根）序遍历算法
二叉树空树空操作
否
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
中（根）序遍历算法
二叉树空树空操作否
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
（根）序遍历算法
二叉树空树空操作
否
（1）序遍历左子树
（2）序遍历右子树
（3）访问根结点
三算法递描述 约10min
总结：先序中序序遍历二叉树遍历时搜索路线相：根结点出发逆时针延二叉树外缘移动结点均途径三次
先序遍历：第次结点时访问
中序遍历：第二次结点时访问
序遍历：第三次结点时访问
四中序遍历算法非递描述 约10min
五遍历算法应举例 约30min
1统计二叉树中叶子结点数(先序遍历)
先序(中序序)遍历二叉树
遍历程中查找叶子结点计数需遍历算法中增添计数
参数算法中访问结点操
作改：叶子计数器增1
2求二叉树深度(序遍历)
算法基思想
首先分析二叉树深度左右子树深度间关系
3复制二叉树(序遍历)
基操作：生成结点
4建立二叉树存储结构
p 定义方法相应存储结构建立算法
定表达式建相应二叉树
先缀表示式建树
原表达式建树
已知道二叉树结构某遍历序列存应关系已知二叉树前序序列中序序列定惟确定二叉树结构
632线索二叉树 约20min
• 谓线索二叉树？
• 遍历二叉树结果求结点线性序列
• 保存种遍历程中信息？
• 简单方法结点增加二指针域：fwdbkwd指示结点遍历中前驱继结点
• 线索链表遍历算法
• 线索链表中添加遍历中前驱继信息简化遍历算法
• 建立线索链表？
结索化实质二叉链表中空指针改指前驱继线索前驱继信息遍历时线索化程遍历程中修改空指针程记遍历程中访问结点先关系附设指针pre始终指刚刚访问结点指针p指前访问结点pre指前驱中序遍历程中修改结点左右指针域保存前访问结点前驱继信息遍历程中附设指针pre 始终保持指针pre指前访问指针p指结点前驱
三结 约7min
1遍历总结
2线索化总结
四作业
1出二叉树写出前中序遍历序列
课 时 授 课 计 划
20112012学年第 学期 第7周
授 课 日 期
11月1日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 树森林
教学目求：
1．熟悉树种存储结构特点掌握树森林二叉树转换方法
2．学会编写实现树种操作算法
教学重点：
1树森林二叉树转换方法
2．学会编写实现树种操作算法
教学难点：
1树森林二叉树转换方法
2．学会编写实现树种操作算法
作业参考书：
树森林转换
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
前面树二叉树回顾引入
二讲课进程设计
64树森林
6·4·1 树存储结构 约25min
1 双亲表示法
组连续存储空间存放树结点结点中附设指针指示双亲结点连续存储空间中位置（标种结构属静态链表）形式表示：
typrdef struct tnode
{ datatype data
int parent
}tree[n]
2 孩子表示法
重链表表示两种方法：构：度结点设置结点结构数域d指针域容易造成空间浪费异构：结点棵子树设指针样操作困难子女链单链表中形式描述：
typrdef struct tagnode * 表结点 *
{ int child
struct tagnode *next
}node *link
typedef struct * 头结点 *
{datatype data
link headptr
}headnode
typedef headnode childlink[maxnode] * 表头数组 *
带双亲孩子链表表示法：
typedef struct * 头结点 *
{datatype data
int parent
link headptr
}headnode1
3 孩子兄弟表示法
该方法称二叉树表示法二叉链表表示法二叉链表作存储结构结点两链域分指该结点第孩子兄弟分命名fchnsib形式描述：
typedef struct treenode
{datatype data
struct treenode *fch*nsib
}treenode *tree
树种表示质二叉树二叉链表表示二叉树树种存储结构致性导致树二叉树相互转换
6·4·2 森林二叉树相互转换 约30min
1 森林转二叉树
树（树林）转换成二叉树时结果唯转换递描述：树（树林）空二叉树空否树（树林）中第棵树根二叉树根第棵树根结点子树林二叉树左子树树林中第棵树树林形成二叉树右子树
形象说转换程面三步曲说明：
三步曲： 连线 切线 旋转
连线： 兄弟结点连接起
切线： 保留双亲第子女连线双亲子女连线切掉
旋转： 根轴面时针方旋转450
2 二叉树转树林
二叉树转换成树（树林）时结果唯
转换递描述二叉树空树（树林）空否二叉树根树（树林）中第棵树根二叉树左子树构成树（树林）中第棵树根结点子树林二叉树右子树构成树林中第棵树树林
形象说面三步曲逆
6·4·3 树森林遍历 约30min
树遍历方法分宽度优先法深度优先法两类前者指（根）第层开始左右逐结点遍历者分先根次序根次序
（1） 先根次序遍历（相相应二叉树先序遍历）
树（森林）空空操作否：
·访问左面第棵树根
·先根次序左右遍历根子树
·先根次序左右遍历第棵树外树（森林）
（2） 根次序遍历（相相应二叉树中序遍历）
树（森林）空空操作否：
·根次序左右遍历左面树子树
·访问左面树根
·根次序左右遍历第棵树外树（森林）
三结 约7min
1树存储
2树森林间转换
3树森林遍历
四作业 约3min
1完成树森转换
课 时 授 课 计 划
20112012学年第 学期 第8周
授 课 日 期
11月3日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 哈夫曼树
教学目求：
1掌握哈夫曼树构造方法
2掌握哈夫曼编码
3带权路径计算
4解优树特性
教学重点：
1哈夫曼树构造
2掌握建立优树哈夫曼编码方法
教学难点：
1建立优树哈夫曼编码方法
2带权路径计算
作业参考书：
1构造棵哈夫曼树计算权值
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
优树概念提出引入哈夫曼树
二讲课进程设计
6·6 哈夫曼树应
6·6·1 优二叉树（哈夫曼树带权路径长度短树）
1 哈夫曼树基概念 约20min
（1） 路径 树中结点结点间分支
（2） 路径长度 路径分支数目称路径长度
（3） 树路径长度 树根结点路径长度称树路径长度完全二叉树路径长度短二叉树
（4） 结点带权路径长度 该结点树根间路径长度结点权积
（5） 树带权路径长度 树中叶子结点带权路径长度通常记WPLwili
（6） 哈夫曼树（优二叉树） 带权路径长度二叉树称哈夫曼树（优二叉树）
（7） 哈夫曼编码 哈夫曼树左分枝0右分枝1根结点开始直叶子结点组成编码序列称叶子结点哈夫曼编码
2 哈夫曼树判定问题中应 约15min
百分制转五级记分制例子说明哈夫曼树判定次数少树（带权路径长度短节省计算时间）
3 构造哈夫曼树 约20min
（1） 根定n权值{w1w2…wn}构成n棵二叉树集合F{T1T2…Tn}棵二叉树Ti根结点F中选两棵根结点权值树作左右子树构造棵二叉树新二叉树根结点权值等左右子树根结点权值
（2） F中删两棵子树时新二叉树加入F中
（3） 重复（2）（3）直F中剩棵树（哈夫曼树）止
举例说明程：
应该说明哈夫曼树形态唯具组权值哈夫曼树WPL唯
6·6·2 哈夫曼编码
1 哈夫曼编码提出背景 约10min
(1)电报编码变短非前缀编码出现二义性(2)二叉树构造前缀编码(3)哈夫曼树优编码
2 构造哈夫曼树哈夫曼编码算法 约20min
前缀编码：字符编码字符集中字符编码前缀
A B C D 四字符率高低编码A 0 B 10 C 110 D 111
利赫夫曼树构造种等长二进制编码构造赫夫曼编码种优前缀编码传电文总长度短哈夫曼编码算法实现：哈夫曼树中没度1结点棵n叶子哈夫曼树2×n－1结点2×n－1 维数组存放哈夫曼树结点结点时包含双亲信息孩子结点信息构成静态三叉链表
三结 约5min
1构造哈夫曼树 2哈夫曼编码
四作业 约5min
1求带权913565叶子节点生成哈夫曼树带权路径长度
2设哈夫曼树叶节点数n0节点总数少？
课 时 授 课 计 划
20112012学年第 学期 第8周
授 课 日 期
10月27日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 树二叉树复题课
教学目求：
1． 熟悉二叉树结点结构二叉树基操作
2． 掌握二叉树种操作具体实现
3． 学会利递方法编写二叉树种递数结构进行处理算法
教学重点：
1． 学会利递方法编写二叉树种递数结构进行处理算法
教学难点：
1利递方法编写二叉树种递数结构进行处理算法
作业参考书：
数结构算法实现解析高 编著
教具：
课堂类型：
总结复
教学程： 提出问题――问题提示――完成问题――检查
二叉树基操作
复目
4． 熟悉二叉树结点结构二叉树基操作
5． 掌握二叉树种操作具体实现
6． 学会利递方法编写二叉树种递数结构进行处理算法
复容
该程序功实现二叉树结点类型定义二叉树基操作该程序包括二叉树结构类型种操作具体函数定义函数
* 定义DataTypechar类型 *
typedef char DataType
* 二叉树结点类型 *
typedef struct BitNode
{DataType data
struct BitNode *lchild*rchild
}BitNode*BitTree
* 初始化二叉树树根指针置空 *
void BinTreeInit(BitTree *BT)
* 先序次序建立二叉树*
void BinTreeCreat(BitTree *BT)
* 检查二叉树否空 *
int BinTreeEmpty(BitTree *BT)
* 种遍历次序（包括先序中序序层次）输出二叉树中结点 *
void BinTraverse(BitTree *BT)
* 求二叉树深度 *
int BinTreeDepth(BitTree BT)
* 求二叉树中结点数 *
int BinTreeCount(BitTree BT)
* 清二叉树变空树 *
void BinTreeClear(BitTree *
课 时 授 课 计 划
20112012学年第 学期 第11周
授 课 日 期
11月8日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 图定义术语 图存储结构
教学目求：
1掌握图定义常术语
2掌握图二种存储表示法
教学重点：
1图常术语
2图数组表示邻接表表示法
教学难点：
1图常术语
2邻接表表示法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
城市间通信引出图
二讲课进程设计
第 七 章 图
图进行概述 约5min
图种线性表树复杂数结构图结构中结点间关系意图中意两元素间关系图应非常广泛
71图定义术语
1 图定义 约5min
图种数结构形式化定义写
Graph(VR)
中V{x|xdatatype}
R{VR}
VR{
图中数元素常称顶点V顶点穷集合R边（弧）穷集合
2 抽象数类型图定义 约5min
ADT Graph
{数象V：
数关系R：
基操作P：
}ADT Graph
3 图术语概念 约15min
(1) 图图 弧：
(2) （）完全图 稀疏图 稠密图 子图
完全图：n顶点n(n1)2条边完全图：n顶点n(n1)条弧
(3) 权网 边（弧）相关数权带权图称网
(4) 邻接邻接点 图：条边连起两顶点互称邻接点
图：顶点x顶点y条弧说顶点x邻接顶点y顶点y邻接顶点x
(5) 度出度入度图中顶点相关边(e)数顶点度e
图中顶点出发弧数该顶点出度入该顶点弧数该顶点入度TD(v)ID(v)+OD(v)
(6) 路径路径长度回路(环)简单路径
(7) 连通连通图连通分量图顶点v1顶点v2路径说v1v2连通意两顶点连通说该图连通连通分量图中极连通子图
(8) 强连通图强连通分量
(9) 生成树树生成森林
连通图生成树极连通子图含图全部顶点足构成棵树n1条边
图中顶点入度0余顶点入度均1该图称树图生成森林干棵树组成含图全部顶点足构成干棵相交树弧
7·2 图存储结构
7·2·1 图序存储结构数组表示法 约20min
1 数组表示法
两数组分表示数元素（顶点）信息边（弧）信息
顶点编号信息边（弧）面邻接矩阵表示
2 邻接矩阵定义
n顶点图G(V{VR})邻接矩阵n阶方阵定义： 0 （vivj）
3 图邻接矩阵性质
（1） 图邻接矩阵称矩阵
（2） 顶点vi度邻接矩阵中第i行（第i列）元素(1)
4 图邻接矩阵性质
（1） 图邻接矩阵定称矩阵
（2） 顶点vi出度邻接矩阵中第i行元素入度邻接矩阵中第i列元素
5 网邻接矩阵
邻接矩阵中01换成权值网邻接矩阵
6 邻接矩阵优缺点
容易实现图前4操作容易判定顶点间边（弧）容易计算顶点度（出度入度）缺点占空间顶点数关边数关边数较少时空间浪费较
7 建立邻接矩阵算法
7·2·2 图邻接表表示法 约15min
邻接矩阵稀疏图时空间浪费较克服缺点采邻接表表示法
1 邻接表结点结构
2 邻接表顶点量结构边（弧）单链表结构顶点结点包括两域n顶点放量中（称序存储结点表）顶点邻接点链接成单链表该顶点量中指针域指第邻接点
3 邻接表优缺点
容易实现图前4操作
空间较省
图容易求顶点度边表中结点数边两倍
图容易求顶点出度求顶点入度容易遍历整表求顶点入度时设逆邻接表（指某顶点邻接点链接成单链表）
4 建立邻接表算法
7·2·3 图十字链表表示法 约15min
图邻接表表示法中查顶点出度非常容易查顶点入度遍历整邻接表解决办法建立逆邻接表成两表方便节介绍图种表示方法十字链表表示法
7·2·4 图邻接重表表示法 约10min
图种表示方法邻接表中条边需两边结点边处理图时需判断边否处理增加复杂性图邻接重表中边结点
三结 约5min
1图基概念术语
2图两种存储结构间较
课 时 授 课 计 划
20112012学年第 学期 第11周
授 课 日 期
11月15日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 图遍历 图连通性问题
教学目求：
1掌握图深度优先遍历方法算法
2掌握广度优先遍历方法算法
3掌握生成树
教学重点：
1深度优先遍历
2生成树
教学难点：
1深度优先遍历
2生成树
作业参考书：
1图基概念
2生成树
3生成树
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
复图存储结构引出图遍历
二讲课进程设计
73 图遍历
731深度优先搜索遍历图 约20min
连通图深度优先搜索遍历图中某顶点V0 出发访问顶点然次V0未访问邻接点出发深度优先搜索遍历图直图中V0路径相通顶点访问
732广度优先搜索遍历图 约15min
连通图起始点V余顶点必定存路径图中某顶点V0出发访问顶点次访问V0未访问邻接点顶点访问先次序次访问邻接点直图中V0路径相通顶点访问时图中尚顶点未访问选图中未访问顶点作起始点重复述程直图中顶点访问止
733遍历应举例 约10min
1求两顶点间条路径长度短路径
74图连通问题
741图连通分量生成树 约15min
1图遍历时连通图顶点出发便遍历图中顶点非连通图需次调搜索程次调顶点访问序列恰连通分量中顶点集
2生成树连通图调DFSBFS边集合图全部顶点构成图极连通子图连通图棵生成树
3生成森林非连通图连通分量顶点集边起构成干棵生成树连通图生成树构成非连通图生成森林
743生成树 约25min
普里姆(Prim)算法基思想取图中意顶点 v 作生成树根生成树添加新顶点 w添加顶点 w 已生成树顶点v 间必定存条边该边权值连通顶点 v w 间边中取值继续生成树添加顶点直生成树含 n1 顶点止
克鲁斯卡尔算法基思想：考虑问题出发点 生成树边权值达应生成树中条边权值
三结 约5min
1深度优先搜索遍历图
2生成树
四作业 约5min
1已知右图示图请出该图
（1）顶点入出度（2）邻接矩阵（3）逆邻接表（4）强连通分量
2画出顶点v1初始源点遍历图示图DFS BFS生成森林
3图（图）示连通图请分PrimKruskal算法构造生成树
课 时 授 课 计 划
20112012学年第 学期 第12周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 拓扑排序 短路径
教学目求：
1掌握拓扑排序
2掌握迪杰斯特算法
教学重点：
1拓扑排序
2短路径
教学难点：
拓扑排序
作业参考书：
71已知右图示图请出该图
（1）顶点入出度（2）邻接矩阵（3）逆邻接表（4）强连通分量
72画出顶点v1初始源点遍历图（图）示图DFS BFS生成森林
73图（图）示连通图请分PrimKruskal算法构造生成树
74已知图示AOE网试求：事件早发生时间晚发生时间活动早开始时间晚开始时间出关键路径
75 试基图深度优先策略写算法判邻接表方式存储图中否存顶点vi顶点vj路径（ij)
注意：算法中涉图基操作必须存储结构实现
76 试利栈基操作编写深度优先搜索策略遍历强连通图非递形式算法算法中规定具体存储结构图Craph成种抽象数类型
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
城市间通信引入
二讲课进程设计
75环图应
环图基础 约10min
1 环图定义 环图环图简称DAG图
2 DAG图描述带公子式表达式
((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)
3 图中否环检查
4 环图应
环图描述工程系统进行程效工具工程否利进行二估算工程完成需短时间拓扑排序关键路径问题
7·5·1 拓扑排序 约20min
1拓扑排序基概念
（1） AOV网 顶点表示活动弧表示活动间优先关系图顶点表示活动网（Activity On Vertex Network）
（2）拓扑序列 AOV网顶点排成线性序列该序列满足AOV网中顶点vivj条路径该线性序列中vi必vj前面样序列称拓扑序列
（3） 拓扑排序 AOV网构造拓扑序列操作拓扑排序
（4）AOV网中应环否会先决条件AOV网代表工程AOV网拓扑序列工程利完成行方案
2拓扑排序方法
1）图中选择入度0顶点输出2）图中删该顶点源该顶点弧3） 重复两步直全部顶点输出拓扑排序利完成否剩入度非0顶点说明图中环拓扑排序进行
3 拓扑排序算法
邻接表顶点量中量元素增加入度域存放顶点入度值输出该顶点删源该顶点弧该顶点邻接点入度减1实际实现时设栈存放入度0顶点退栈输出顶点邻接点入度域减1减0时入栈拓扑排序完成时栈应空
4 拓扑排序算法分析
O（n+e）
7·5·2 关键路径 约25min
1 AOE网
顶点表示事件弧表示活动弧权值表示活动持续时间图AOE（Activity On Edge Network）网 AOE网常估算工程完成时间
2 AOE网研究问题
1)完成整工程少需少时间2)活动影响工程关键
1956年美国杜邦公司提出关键路径法1957年首先1000万美圆化工厂建设工期原计划缩短4月杜邦公司采关键路径法年中节省100万美圆
3 关键路径术语
（1） 关键路径 源点汇点路径长度长路径关键路径
（2） 活动开始早时间e(i)
（3） 活动开始晚时间l(i) 定义e(i)l(i)活动关键活动
（4） 事件开始早时间ve(i)
（5） 事件开始晚时间vl(i)
4 求关键路径算法
(1) 输入e条弧
(2) 源点v1出发令ve(1)0求 ve(j) 2
求关键路径拓扑排序前提进行进行拓扑排序然求关键路径
5 求关键路径算法分析
（1） 求关键路径必须拓扑排序前提进行环图求关键路径
（2） 缩短关键活动工期缩短工期
（3） 关键活动关键路径减少减少工期
（4） 改变关键路径前提缩短关键活动缩短整工期
76短路径
网络中常见问题：两点间否通路条路径短书讨两类问题：类顶点顶点间短路径类意两顶点间短路径图应
7·6·1 某源点顶点间短路径 约10min
里路径指两顶点间通路路径长度指边总长短路径问题指两顶点间通路条时找出边长总短条Dijkstra提出路径长度递增次序求短路径方法
1 Dijkstra 求短路径基思想
顶点分成两组第组已确定短路径结点集合第二组尚未确定短路径结点集合路径长度递增次序逐第二组顶点放第组中设求v1顶点间短路径意时刻v1第组顶点间短路径v1第二组顶点间短路径
2 Dijkstra 求短路径步骤
设图邻接矩阵arcs存储矩阵中元素值边权值顶点间边时应权值穷表示
3 Dijkstra 求短路径实例模拟
4 Dijkstra 求短路径算法
5 Dijkstra 求短路径算法分析
n顶点图求顶点余顶点短路径循环n1次加修改短路径循环二层循环时间复杂度O(n2)求源点某顶点间短路径求余顶点间短路径相时间复杂度O(n2)
6·4·2 顶点间短路径 约20min
n顶点图求顶点间短路径方法二：Dijkstra算法求顶点顶点间短路径面基础加层循环时间复杂度O(n3)种方法弗洛伊德（floyd）提出时间复杂度O(n3)形式简单
1弗洛伊德（floyd）算法基思想
设求顶点vivj间短路径vivj弧弧权值条路径未必短路径n1次测试首先顶点v1加入(viv1)(v1vj)否路径(vivj)低两段路径代称vivj中间顶点序号1短路径顶点v2加入vivj中间顶点序号2短路径直vn加入vivj中间顶点序号n短路径算法结束
2弗洛伊德（floyd）算法实例模拟
4 弗洛伊德（floyd）算法
三 结 约3min
1 拓扑排序
2 短路径
四作业题 约8min
71已知右图示图请出该图
（1）顶点入出度（2）邻接矩阵（3）逆邻接表（4）强连通分量
72画出顶点v1初始源点遍历图（图）示图DFS BFS生成森林
73图（图）示连通图请分PrimKruskal算法构造生成树
74已知图示AOE网试求：事件早发生时间晚发生时间活动早开始时间晚开始时间出关键路径
75 试基图深度优先策略写算法判邻接表方式存储图中否存顶点vi顶点vj路径（ij)
注意：算法中涉图基操作必须存储结构实现
76 试利栈基操作编写深度优先搜索策略遍历强连通图非递形式算法算法中规定具体存储结构图Craph成种抽象数类型
课 时 授 课 计 划
20112012学年第 学期 第12周
授 课 日 期
11月17日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 图总结复
教学目求：
1掌握图种存储结构
教学重点：
熟练掌握邻接矩阵邻接表存储结构
教学难点：
熟练掌握邻接矩阵邻接表存储结构
作业参考书：
数结构算法实现解析高 编著
教具：
课堂类型：
教学程：提出问题――问题提示――完成问题――检查
图基操作
复目
1． 掌握图种存储结构特熟练掌握邻接矩阵邻接表存储结构
2． 遍历图种应算法基础熟练掌握图深度优先遍历广度优先遍历算法复栈队列应
复容
程序1
* 定义邻接矩阵类型 *
typedef int adjmatrix[n+1][n+1]
* 建立图邻接矩阵 *
void CreatMatrix(adjmatrix GA)
* 初始点v出发深度优先遍历邻接矩阵GA表示图 *
void DfsMatrix(adjmatrix GAint v)
*初始点v出发广度优先遍历邻接矩阵GA表示图*
void BfsMatrix(adjmatrix GAint v)
程序2
* 邻接表结点类型 *
typedef struct arc
{int adjvex
struct arc *next}ArcNode
typedef struct VexNode
{int vertex
ArcNode *firstarc
}VerNode
typedef VerNode AdjList[MAXNODE]
* 建立图邻接表 *
void CreatAdjlist(AdjList GL)
* 初始点v出发深度优先遍历邻接表GL表示图 *
void DfsAdjlist(AdjList GLint v)
*初始点v出发广度优先遍历邻接表GL表示图*
void BfsAdjlist(AdjList GLint v)
课 时 授 课 计 划
20112012学年第 学期 第13周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 静态查找表 动态查找表（）
教学目求：
1熟练掌握序表序表查找方法
2熟悉静态查找树构造方法查找算法理解静态查找树折半查找关系
3熟练掌握二叉排序树构造查找方法
4掌握二叉衡树维护衡方法
教学重点：
1查找基概念 2折半查找 3二叉排序树实现 4衡二叉树
教学难点：
1序查找性分析
2折半查找
3构造二叉排序树 衡二叉树
作业参考书：
1具n元素序序表序序表分进行序查找试述两种情况分讨两者等概率时均查找长度：
(1)查找成功表中关键字等定值K记录
(2)查找成功表中关键字等定值K记录
2设序表(abcefgijkpq)请分画出定值bgn进行折半查找程
3 画出长度10序表进行折半查找判定树求等该率时查找成功均查找长度
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
日常生活中遇找电话查找学生信息引入
二讲课进程设计
第 九 章 查找
基定义 约5min
1 查找定义 查找关键字等定值操作
2 关键字概念 关键字数元素（记录）中某数项值标识记录唯标识称关键字否称次关键字
3 查找结果 查关键字等定值记录称查找成功否称查找失败
4 查找算法效率度量
（1）均查找长度ASL：查找关键字等定值程中需定值进行较关键字数期值称查找成功时均查找长度
（2）需辅助存储空间
91 静 态 查 找 表
9·1·1 序查找 约12min
1 序查找定义 查关键字线性表中结点关键字逐较直找关键字值相等结点查找成功查完全表未找关键字相等结点查找失败
2 序查找算法
3 序查找算法时间复杂度
均查找长度ASL 查找成功
(1) 查找失败 n+1
(2) 设查找成功概率p查找成功概率q(1p)均较次数：
E(n)p +q(n+1) p +(1p)(n+1)(n+1)(1)
成功失败概率占50均性
查找结点概率等应查找概率高结点放前边提高查找效率
9·2·2 序表查找（二分查找） 约20min
1 二分法查找基概念 序表中元素已关键字序排列查找时必序查找查关键字中间位置元素关键字较相等查找成功查关键字中间位置分开左子表中查找否右子表中进行直查找成功查找失败
2 二分法查找算法
3 二分法查找时间复杂度
二分法查找程二叉树描述中间结点二叉树根左子表相左子树右子表相右子树二叉树便描述二分法查找判定树二分法查找程走条根结点叶子结点程查找成功失败查找长度均超树高度均性h élog2(n+1) ù
4 二分法查找优缺点
优点：查找速度快 表必须序
缺点：频繁插入删方便
二分法查找适表中元素少变化查找频繁情况序表查找适查找少表中元素频繁变化情况
9·2·3 索引序表查找（分块查找） 约15min
分块查找综合序查找二分法查找优点动态结构适快速查找
1 分块查找基思想
查找文件等长分干子文件（子文件长度）子文件元素序子文件间序第子文件高关键字第二子文件高关键字第二子文件高关键字第三子文件高关键字次类推建立索引表（文件）文件中元素含子文件高关键字子文件中第元素址（标）索引文件关键字序
查找时索引表序查找二分法查找块序查找
2 分块查找均长度
设查找文件n记录均分成b块块s记录考虑查找成功概率块索引表中均序查找均查找长度：
E(n)Eb+Ew+(s2+2s+n)(2s)
s均查找长度取值：+1
索引表采二分法查找均查找长度：
E(n)Eb+Ewélog2(b+1) ù+
3 种查找方法较
9·2 动态查找表
适应元素结点动态插入删
9·2·1 二叉排序树
1 什二叉排序树 约10min
（1） 二叉排序树定义
二叉排序树棵空树具性质二叉树：
· 左子树空左子树结点值均根结点值
· 右子树空右子树结点值均根结点值
· 左右子树分二叉排序树
（2） 二叉排序树建立实例
设关键字序列k(k1k2…km) (m>0)建立二叉排序树步骤：
· 令关键字k1二叉排序树根
·k1>k2k2做k1左子树根结点否做k1右子树根结点子树中继续子树根较重复前面操作
· 序列中关键字递面步骤
例定关键字序列 k(45125333710024619078)
（3） 中序（称序）遍历二叉排序树结点序列序序列
二叉排序树进行中序遍历遍历序列序序列二叉排序树定义决定
（4） 二叉排序树中结点插入
二叉排序树中插入结点保证插入结点二叉排序树然二叉排序树行插入结点叶子结点结果唯
（5） 二叉排序树中结点删
二叉排序树中删结点删结点二叉排序树然二叉排序树结果唯结点删立插入二叉排序树结点删前二叉排序树般说形态等
2 佳二叉排序树 约10min
（1） 佳二叉排序树定义
n结点二叉树n二叉排序树中均查找（检索）长度短棵二叉排序树佳二叉排序树
（2） 扩充二叉排序树
二叉树中度10结点补充虚结点结点（虚结点外）度均2样二叉树称扩充二叉排序树设加虚结点数N原结点（称部结点）数n时二叉树度1结点根二叉树性质3式成立：
Nn+1
定义外部路径长度扩充二叉树根外部结点路径长度E表示部路径长度指扩充二叉树根部结点路径长度I表示式成立：
EI+2n
数学纳法证明：
n1时I0E2等式成立
设n部结点时式成立
En In+2n （1）
考虑n+1结点扩充二叉树删部结点时结点路径长度K
InIn+1K (2)
时外部路径长度减少两路径长度K+1外部结点增加路径长度K部结点 EnEn+12(K+1)+K (3)
三式
En+1 En+2(K+1)K
(In+2n)+K+2
((In+1K)+2n)+K+2
In+1+2(n+1) 证毕
（3） 二叉排序树检索效率 E（n）<1+4logn
（4） 构造佳二叉排序树 首先关键字排序序表构造静态查找判定树二叉树佳二叉排序树判定树唯着佳二叉排序树定义佳二叉排序树唯
3 衡二叉树(AVL树) 约10min
二叉排序树差情况成单枝树检索效率等序表佳二叉排序树难构造提出种称衡二叉树二叉排序树检索效率界佳二叉排序树般二叉排序树间求树中结点左右子树高度差1四种旋转：LLRRLRRL
三结 约3min
1序存储 2动态存储
四作业 约2min
1具n元素序序表序序表分进行序查找试述两种情况分讨两者等概率时均查找长度：
(1)查找成功表中关键字等定值K记录
(2)查找成功表中关键字等定值K记录
2设序表(abcefgijkpq)请分画出定值bgn进行折半查找程
课 时 授 课 计 划
20112012学年第 学期 第13周
授 课 日 期
12月6日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 B树 哈希表
教学目求：
1 B－树建树查找
2 哈希表构造
3 查找时间
教学重点：
1 B－树构造查找
2 哈希表构造
教学难点：
1 B－树构造
2 哈希表构造
作业参考书：
1 B－树构造
2 哈希表构造
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
前面讲动态存储引入B－树哈希表
二讲课进程设计
922 B 树B+树 约25min
1．B树定义 B树种衡路查找树：
2．查找程：根结点出发指针搜索结点结点进行序（折半）查找两程交叉进行
3．插入
查找成功需进行插入显然关键字插入位置必定层非叶结点
4．删
插入考虑相反首先必须找删关键字结点求删结点中关键字数ém2ù1否左(右)兄弟结点调关键字左右兄弟结点均关键字(结点中少量关键字)必须进行结点合
5．查找性分析
B树中进行查找时查找时间花费搜索结点（访问外存）取决B树深度
结：
含 N 关键字 B树进行次查找需访问结点数超logém2ù((N+1)2)+1
9·3 哈希表
9·3·1 什哈希表 约12min
1 散列函数提出
前讲检索检索关键字记录关键字较相等检索成功否继续较希找函数关键字进行计算函数值解释记录存储址散列检索函数散列函数散列法存储线性表散列表查找时样方法计算址相应单元找记录找查找成功该单元记录查找失败该单元记录找继续查找种方法称关键字址转换法
2 散列检索术语
（1） 碰撞（突）：两关键字散列函数值相key1<>key2f(key1)f(key2)突避免举标识符例子1939年 davenport生日悖
（2） 义词：发生碰撞（突）关键字称义词
（3） 负载子：定义a（散列表中结点数目）（散列表长度）a般取06~09
（4） 采散列表着重考虑两问题：选择散列函数选择种解决碰撞（突）方法
3 散列表较详细叙述
根设定散列函数h(key)处理突方法组关键字映象限连续址集（区间）关键字址集中象作记录表中存储位置种表称散列表映象程散列（哈希造表）存储址称散列址哈希址
9·3·2 哈希函数构造方法 约20min
1 数字选择法 分析关键字位掉分布均匀位留均匀位作址
2 方取中法 数方结果中间位数位关系取中间位作址
3 折叠法 关键字位数较分布均匀折叠法折叠法分移位折叠间界折叠
4 余法 关键字p余数作址：h(key)key mod p
通常p取散列表长素数
5 基数转换法 基数数作基数数转换基数数
6 机数法 H(key)random(key)
9·3·3 处理突方法 约20min
处理突方法分两类：拉链法开放址法
1 拉链法
拉链法基思想散列表（量）元素两域组成域存放关键字域址指针指该关键字义词义词该域空
（1） 建立分离义词子表方法：象前动态建立单链表样义词建成单链表例关键字序列28325537740738480180320365949177551961199设量空间0—18散列函数h(key)key mod 19
检索（查找）方法先计算关键字址该址处关键字检索失败该址正找关键字检索成功该址关键字找关键字链查找直检索成功链空时失败
(2)建立结合义词子表方法： 该方法动态开辟空间建立单链表利散列表量空间遇义词时量空间中前找尚未占空间义词放入中关键字址（标）该义词处拉链（静态链表）种方法易产生堆积（聚集）义词非义词争夺散列址解决方法两遍处理：第遍插入义词子表表头关键字第2遍插入关键字
2 开放址法
开放址法处理突基思想：发生突时某种方法散列表中形成探查序列着探查序列逐单元查找直找定关键字碰开放址（该单元空）止插入时碰开放址插入中查找时碰开放址查找失败
（1） 开放定址法
Hi(H(key)+di) mod m (i12…m1)
中H(key)散列函数m散列表长度di增量序列三种取法：
· di12…m1 称线性探查散列探查单元序列：d+1d+2…m10…d1
· di12 1222 2232…+()k2(k
（2） 双散列函数探查法
散列函数计算散列址发生突时第二散列函数进行计算设两散列函数h1h2关键字变量设m素数取
h1(key)key mod mh2(key)key mod (m2)+1h2(key)[keym] mod (m2)+1
h1(key)d发生碰撞双散列函数探查序列：
(d+h2(key)) mod m (d+2h2(key)) mod m (d+3h2(key)) mod m
双散列函数探查法检索程造表类似
9·3·4 散列表查找分析 约12min
三结 约3min
1B－树 2哈希表
四作业 约6min
1．序列（245642867061）构造23树
2．已知散列函数H(K)K mod 12健值序列2537524384991201526117082采拉链法处理突试构造开散列表计算查找成功均查找长度
课 时 授 课 计 划
20112012学年第 学期 第14周
授 课 日 期
6月13日
三
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 排序概念 插入排序 快速排序
教学目求：
1 解排序定义种排序方法特点熟悉种方法排序程原基关键字间较进行排序方法排序程原分插入排序交换排序选择排序排序计数排序等五类
2 掌握种排序方法时间复杂度分析方法关键字间较次数分析排序算法均情况坏情况时间性
3．理解排序方法稳定稳定含义弄清楚什情况求应排序方法必须稳定
教学重点：
熟悉种方法排序程原
教学难点：
熟悉种方法排序程原
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约5min
现实生活中遇问题引入排序作引入排序
二讲课进程设计
第十章 部 排 序
10·1 基概念 约15min
1 排序定义：排序中结点（数元素）称记录记录集合称文件存中文件常称线性表
2 排序分类
部排序外部排序
部排序分5类：插入排序选择排序交换排序分配排序排序
3 稳定排序稳定排序
排序文件中关键字相等记录排序前相次序排序前未发生变化种排序称稳定排序否稳定排序稳定排序稳定排序表示排序方法说明种方法差
4 排序中记录存储方式 序存储结构 静态链表 址排序
5 排序算法评价
（1） 算法执行时需时间 情况差情况均情况
算法执行时需附加空间 特说明书排序指记录关键字递增排序数组作排序记录文件存储结构
10·2 插入排序
10·2·1 直接插入排序 约10min
1 直接插入排序基思想：
先假定第记录序序列然第二记录开始次记录插入前边序序列中直全部记录序列序避免总查询文件尾特设监视哨
2 直接插入排序实例模拟
3 直接插入排序算法
4 直接插入排序算法复杂度 空间复杂度：占单元（r[0]）
时间复杂度：
（1）佳情况：排序文件已序时关键字进行次较总进行n1次较记录移动次数2(n1)
（2）差情况：排序文件完全逆序时第i（2
10·2·2 希尔(shell)排序 约20min
称缩增量排序shell1959年提出
1 基思想
排序记录较少排序记录基序时直接插入排序效率较高基种思想希尔提出排序记录分d组相距d记录放组进行直接插入排序
2 Shell 排序分组选择
认di取成奇数认di间互质di系列选没1外公子
3 排序实例
4 Shell 排序算法
5 Shell 排序算法复杂度
10·3 快速排序
10·3·1 起泡排序 约15min
1 起泡排序基思想
起泡排序称泡排序排序记录R1R2…Rn应关键字K1K2…K n 起泡排序作法：
（1） K1K2 逆序（K1>K2）交换然较K2K3……直Kn1Kn时关键字（第n位置）趟起泡排序进行n1次较
（2） 重复（1）较第n1元素（关键字）称第二趟较
（3） 进行n1趟较完成整排序
2 起泡排序实例模拟
3 起泡排序算法
4 起泡排序算法时间复杂度
起泡排序较次数记录初始序关正序时较次数n1交换次数0逆序时较次数交换次数均：
（n1）
移动次数n(n1)存储开销记录空间供交换
10·3·2 快速排序 约25min
1 快速排序基概念
第记录枢轴查询记录序列确定枢轴位置枢轴排序文件分成两部分：枢轴左面记录关键字关键字枢轴右面记录关键字关键字枢轴左右两部分继续实施程直全部文件序
2 快速排序实例模拟
3 快速排序算法
4 快速排序时间复杂度
较次数约nlog2n交换次数约nlog2n6移动次数等nlog2n排序文件序（正序逆序）快速排序退化成起泡排序（n1）≈n22存储开销栈深度超log2n
5 快速排序差情况改进
防止差情况出现般采取三者取中法确定枢轴第记录记录中间位置记录中选取值中间作枢轴样防止差情况出现
三结 约5min
1插入排序 2快速排序
四作业 约5min
1关键码序列（503087061908170897275653426）例手工执行排序算法写出趟排序结束时关键码状态：
1）直接插入排序 2）希尔排序（增量d[1]5） 3）快速排序：
课 时 授 课 计 划
20112012学年第 学期 第14周
授 课 日 期
12月15日
五
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 选择排序 排序 基数排序 种部排序方法较讨
教学目求：
1 解排序定义种排序方法特点熟悉种方法排序程原基关键字间较进行排序方法排序程原分插入排序交换排序选择排序排序计数排序等五类
2 掌握种排序方法时间复杂度分析方法关键字间较次数分析排序算法均情况坏情况时间性
3．理解排序方法稳定稳定含义弄清楚什情况求应排序方法必须稳定
教学重点：
1选择排序 2排序
3基数排序
教学难点：
1堆排序
作业参考书：
种排序应
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
引入 约3min
前面两种排序引入面排序
二讲课进程设计
104 选 择 排 序
10．4．1 直接选择排序 约15min
1 直接选择排序基思想
设排序文件n记录第趟进行n1次较选出关键字记录第记录交换第二趟进行n2次较选出关键字次记录第二记录交换……进行n1趟直排序文件全部序
2 直接选择排序实例演示
3 直接选择排序算法
4 直接选择排序算法复杂度
直接选择排序较次数记录初始序关较次数：
（n1）
交换次数超(n1)次文件初始正序时发生交换初始文件逆序时发生（n1）次交换移动次数3(n1)
10·4·2 树形选择排序 约7min
1 树形选择排序基概念
树形排序步骤：
（1） n排序关键字两两较n2较关键字保留
（2） n2关键字两两较n4较关键字保留
（3） 反复进行述操作直关键字（树根）
(4) 关键字输出原位置改极数位置相关部分重新（树根方）进行较选出次关键字保留结果直全部排序完成
该方法直接选择排序速度提高缺点：
（1） 需开储存空间保存排序结果
（2） n排序关键字需额外（n1）部结点（包括根结点）增加存开销
（3） 关键字改极数兄弟结点较属余
2 树形选择排序算法复杂度
树形选择排序第次选值时较n1次选次值较log2n次总较次数(n1)+(n1)log2nnlog2n结点移动次数超较次数总开销O（nlog2n）
10．4．3 堆排序 约20min
1 堆定义
堆含n关键字{k1k2…kn}序列具特性：
ki
ki>k2i
ki>k2i+1 (1
满足式（1）称极化堆极堆堆满足式（2）称极化堆极堆堆节极化堆例子进行讲解
堆完全二叉树关系：堆n元素（关键字）序列满足完全二叉树序存储中结点间关系（双亲子女序号间关系）
2 堆排序基问题
然堆顶元素（关键字）元素排序序列元素输出元素调整成堆新堆顶元素排序序列第二元素通堆序序列变序序列堆排序基问题：建堆 调堆
3 调堆
元素堆顶元素交换（相堆顶元素输出）时堆顶倒数第二元素堆顶元素外余元素均符合堆定义面采筛选法包括堆顶元素元素调成堆
4 建堆
具n结点完全二叉树叶子结点认符合堆定义非终端结点编号n2该结点开始直根结点次调面筛选法完成堆建立具体算法放面堆排序算法中
5 堆排序算法
6 堆排序算法分析
时间复杂度O（nlogn）需记录供交换辅助存储空间
10·5 排序 约10min
1 排序基思想
设排序文件n记录开始首先假定n记录序（然记录然序）然进行相邻序子文件合成较子文件直整文件序二路说第次长1序子文件两两长2éù序子文件两两长4éù序子文件直长n序文件
2 二路排序算法
3 二路排序时间复杂度
第i趟排序序子文件长度2i具n记录文件排序必须做「log2nù趟趟花时间O（n）二路排序时间复杂度O（nlog2n）需空间O（n）
3·7 种排序方法较
10·6 基数排序
10·6·1 关键字排序 约8 min
1 分配排序实例
（1） 扑克牌排序
扑克牌花色面值（点数）规定花色高面值花色中规定梅花>方块>红心>黑桃面值中2<3<4<…<10
方法2：先面值分成13堆13堆排序花色分成4堆花色序收集起种方法低位（LSD）优先法
（2） 卡片排序
卡片日期（年月日）建立然建立日期关键字进行排序
方法1：先年份分堆年卡片月份分堆月卡片日分堆序收集卡片种方法高位（MSD）优先法
方法2：先日分堆收集月份分堆收集年分堆收集种方法低位（LSD）优先法
2分配排序方法
高位（MSD）优先法高位分成干子集子集分成子集子集中排序收集低位（LSD）优先法低位开始高位结束进行干次分配收集
关键字字段时分配排序方法000999
10·6·2 链式基数排序 约15min
低位优先法单关键字情况
1 基数排序基思想
n记录关键字进行排序关键字成d元组：
ki(ki1 ki2 kid)
中
c0
关键字数字时r10 0
3 基数排序算法
107 种排序方法综合较 约12min
1时间性 均时间性 排记录序列关键字序序时 简单选择排序堆排序排序时间性记录序列中关键字分布改变
2空间性
指排序程中需辅助空间
1)简单排序方法(包括：直接插入起泡简单选择) 堆排序空间复杂度O(1)
2) 快速排序O(logn)递程序执行程中栈需辅助空间
3) 排序需辅助空间空间复杂度 O(n)
4) 链式基数排序需附设队列首尾指针空间复杂度 O(rd)
3排序方法稳定性
1) 稳定排序方法指两关键字相等记录序列中相位置排序前排序没改变
2) 关键字记录序列进行LSD方法排序时必须采稳定排序方法
3) 稳定排序方法举出实例说明
4) 快速排序堆排序希尔排序 稳定排序方法
4关排序方法时间复杂度限
三结 约7min
1种排序方法进行总结
2章讨种排序方法基数排序外方法基较关键字进行排序排序方法
四作业 约3min
101关键码序列（503087061908170897275653426）例手工执行排序算法写出趟排序结束时关键码状态： 1）堆排序： 2）排序 3）基数排序
102编写教科书1022节中述链表插入排序算法
103 2路排序策略先排序序列扫描遍找出划分干序子列子列作初始段试写出算法链表结构实现策略
课 时 授 课 计 划
20112012学年第 学期 第15周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 排序查找算法辅导（）
教学目求：
进步掌握种排序查找方法
教学重点：
掌握方法
教学难点：
选择排序查找方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：出问题――学生思考――学生解答――问题讲解
讲课进程设计
排序查找算法辅导
题先学生做学生做情况讲解
1 （约8min）设L单链表头结点址数结点数正整数相试设计利直接插入原该链表整理成数递增序单链表算法
2 （约8min）二路插排序排关键字序列r[1n]中关键字分二路分序插入辅助量d[1n]前半部半部（注量d视循环表）原先r[l]赋d[1]r[2]记录开始分二路插入编写实现二路插入转序算法
3 （约8min）N记录存储带头结点双链表中现双起泡排序法升序进行排序请写出种排序算法
（注：双起泡排序相两趟排序方相反起泡）
4（约8min）设数组中存放序关键序列K1K2……Kn现求Kn放元素排序正确位置试编写实现该功算法求较关键字次数超n
5．（约8min）设序放置n桶桶中装粒砾石粒砾石颜色红白蓝求重新安排砾石红色砾石前白色砾石居中蓝色砾石居重新安排时粒砾石颜色次允许交换操作调整砾石位置 6．（约12min）设文件（R1R2……Rn）堆Rn+1意结点试设计算法该算法Rn+1添加堆中添加形成文件堆求算法时间复杂性O(log2n)
课 时 授 课 计 划
20112012学年第 学期 第15周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 排序查找算法辅导（）
教学目求：
进步掌握种排序查找方法
教学重点：
掌握方法
教学难点：
选择排序查找方法
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：出问题――学生思考――学生解答――问题讲解
讲课进程设计
7．（约10min）数结构DEAP定义：DEAP棵完全二叉树者棵空树者满足列特性：（1）树根包含元素．（2）左子树堆（MINHEAP）右子树堆（MAXHEAP）．（3）右子树非空设ｉ左子树结点ｊ右子树中ｉ相应结点．样ｊ结点存取ｊ右子树中ｉ父结点相应结点结点ｉ关键字总等结点ｊ关键字值．
DEAP例子右图示结点１５相应结点２０结点１
９应结点２５．
（1） 出该DEAP中插入结点４结果．
（2） 写出DEAP中插入新结点算法．
（3） CPASCAL语言编写实现述算法程序．
8 (约6min)出折半查找递算法出算法时间复杂度性分析
9(约7min)设记录R1R2…Rn关键字值序存贮数组r[1n]中r[n+1]出设立监督哨关键字值+∞ 试写查找定关键字k 算法画出查找程判定树求出等概率情况查找成功时均查找长度
10(约7min)二叉排序树采二叉链表存储写算法删节点值X结点求删该结点树然棵二叉排序树高度没增长（注：考虑删结点根情况）
11(约10min)二叉排序树结构中数元素值相设计算法实现递增序印结点数域求相数元素仅输出算法应报出滤掉未输出数元素数图示二叉排序树输出：101213151821273542．滤掉3元素
12．(约10min)知输入关键字序列（１００９０１２０６０７８３５４２３１１５）址区０~１１设计哈希表函数述关键字散０~１１中画出散列表（突线性探测法）写出查找算法计算等概率情况查找长度
课 时 授 课 计 划
20112012学年第 学期 第16周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 复1～5章
教学目求：
1 数结构中基概念做更深理解
2 掌握线性表法
3 栈队列作
4 串应
5 数组应
教学重点：
章知识点
教学难点：
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：出容提学重点例题解析
讲课进程设计
第章 绪 约10min
容提
1 数结构研究容2 基概念：数数元素数象数结构数类型抽象数类型形数类型3 算法定义五特征4 算法描述：类PASCAL语言5 算法设计求6 算法分析
二学重点
1 数结构三素：逻辑结构物理（存储）结构种结构定义操作（运算） 2 抽象数类型定义表示实现方法3 类PASCAL书写规范程（函数）中值参变参差程调规4 计算语句频度估算算法时间复杂度
三例题解析
1 写出语句执行次数（左边括号数字语句序号）
第二章 线性表 约25min
容提
1．线性表元素间约束力强类数结构 2．线性表逻辑结构定义线性表定义操作3．线性表存储结构：序存储结构链式存储结构4．线性表操作两种存储结构中实现5．元项式线性表表示方法高次（稀疏）项式抽象数类型定义表示加法实现
二 学重点
1． 线性表逻辑结构指线性表数元素间存着线性关系序存储结构中元素存储先位置反映出种线性关系链式存储结构中指针反映种关系2． 序存储结构量（维数组）表示定标存取相应元素属机存取存储结构3． 知道某结点指针存取该元素链表存取需头指针开始链行链表属机存取结构4． 链表章学重点难点理解头结点首元结点元素结点差理解头结点插入删等操作时算法统设立（头结点第元素前插入元素删第元素时链表头指针总变化）掌握通画出结点图进行链表生成插入删遍历等操作5． 链表操作中应注意链意外断开某结点前插入元素删某元素必须知道该元素前驱结点指针6． 时间空间复杂度角度综合较线性表序链式两种存储结构特点7． 静态链表重点难点应链表进行较理解
三例题解析
１．设线性表序存储结构存a(1n)中试编写算法该线性表逆置
２．编写单链表进行排序算法
3．设两非递减序线性表mn元素（m>0n>0）分存维数组ab中a 存储空间足够试编写算法两线性表合成线性表结果非递减序求算法时间复杂度o(m+n)
第三章 栈队列 约30min
容提
1．数结构角度讲栈队列线性表操作线性表操作子集属操作受限线性表数类型角度线性表相重抽象数类型2．栈定义操作栈准端进行插入删操作线性表该端称栈顶端3．栈序链式存储结构两种结构实现栈操作4．栈应：表达式求值递程消递5．队列定义操作队列删端（尾）插入队列端（头）两种存储结构中需队头队尾两指针6．链队列空条件首尾指针相等循环队列满条件判定队尾加1等队头设标记两种方法
二 学重点
1．栈队列操作两种存储结构实现2．中缀表达式转成前缀缀表达式求值3．递解决问题：定义递数结构递问题解法递掌握典型问题算法
4． 链队列删时空处理（令队尾指针指队头）特仅设尾指针循环链队列种操作实现5． 循环队列队空定义队头指针等队尾指针队满单元（教材中示） 设标记办法（面例题）里特注意取模运算6． 续章节中注意栈队列应串中心称判定二叉树遍历递非递算法图深度优先遍历等栈树层次遍历图宽度优先遍历等队列
三例题解析
1．两栈享量空间编写入栈出栈算法
2．中缀表达式转换成缀表达式进行表达式求值
3设标记判定循环队列满编写入队出队算法
第四章 串 约10min
容提
1 数元素字符线性表串定义操作2 基操作编制算法求串操作3 存储结构串数元素字符线性表存结点问题静态动态（块链结构堆结构）存储优缺点 4 朴素模式匹配算法改进（KMP）算法
二学重点
1 串基操作编写串操作（indexreplace等）2串模式匹配中求匹配串nextval 函数值3朴素模式匹配时间复杂度O(m*n) KMP算法O(m+n)般情况前者实际执行时间似O(m+n)采4KMP算法仅串模式串存许部分匹配时显前者块优点串回嗍5 串操作存储结构实现
三例题解析
1利串基运算create(s)assign(st)length(s)substr(sstartlen)concat(s1s2)编写操作replace算法
2 设目标 t’abcaabbabcabaacbacba’模式串 p’abcabaa’
(1)计算PNEXTVAL函数值(2)写出算法画出利KMP算法进行模式匹配时趟匹配程
第五章 数组广义表 约25min
容提
1 数组逻辑结构定义存储2 稀疏矩阵（含特殊矩阵）存储运算3 广义表定存储4 广义表运算递算法
二学重点
1 数组（二维）行序存储中址计算方法2 特殊矩阵压缩存储时标变换3 稀疏矩阵三元组表存储结构矩阵移植算法4 稀疏矩阵十字链表存储方法十字链表生成算法5 广义表HEADTAIL 运算6 定广义表画出存储结构7 广义表递算法掌握编写递算法
三例题解析
1字符串二维数组A[08110] 元素6字符组成字符占存储单元（1）存放A需少字节？（2）A第8列第5行占少字节？(3) 行序存储时A[85]列存储时元素时址相？
2求列广义表操作结果：(1)HEAD(TAIL(HEAD(((ab)(cd))))(2)TAIL(HEAD(TAIL(((ab)(cd))))
解答 （1）b (2) (d)
3广义表HEADTAIL操作写出题表达式原子banana列广义表中分离出
（1）（apple(pear)((banana))(((orange)))）（2） L2(apple(pear(banana)orange))
课 时 授 课 计 划
20112012学年第 学期 第16周
授 课 日 期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
月 日
星期
班 级
信101
基课题 复6～10章
教学目求：
1树基知识
2图基知识
3查找应
4排序选择
教学重点：
章重点
教学难点：
作业参考书：
数结构算法实现解析高 编著
教具：
媒体
板书
课堂类型：
讲授
教学程：引入——展开——举例——结——作业
讲课进程设计
第六章 树二叉树 约25min
容提
1树复杂非线性数结构树二叉树递定义基概念术语2二叉树性质存储结构3二叉树遍历算法（递非递）4线索二叉树5树存储结构树森林遍历二叉树相互转换6二叉树应：表达式求值判定问题哈夫曼树哈夫曼编码
二学重点
（章容课程重点）
1二叉树性质证明方法种方法推广K叉树2二叉树遍历递算法书中介绍三种（先中序）方法三种应会前序中序非递遍历遍历基础导出许实算法求二叉树高度结点层次数度012结点数二叉树相似全等复制等等算法3二叉树遍历前序中序序列序中序序列唯构造棵二叉树手工模拟编写算法前序序序列唯确定棵二叉树4二叉树线索化实质建立结点相应序列中前驱继间直接联系序（前中）进行种（全前驱继）线索化求某结点相应前驱继5完全二叉树性质序存储结构二叉树链表存储结构相互转换6树双亲表示法孩子兄弟表示法间相互转换7树森林二叉树间相互转换（连线切线旋转）8哈夫曼树定义构造求哈夫曼编码
三例题分析
1二叉树中查找数域 x结点存返回该结点指针否返回空指针
２．设二叉树采二叉链表作存储结构试编写算法求二叉树结点数
３．印二叉树中结点x（假定存）祖先结点
第七章 图 约25min
容提
1． 图定义概念术语基操作 2．图存储结构3．图遍历4．图应（连通分量生成树拓扑排序关键路短路）
二学重点
图应广泛种数结构章门课程重点
1 基概念中连通分量生成树邻接点重点2 图复杂数结构序链式两种存储结构：数组表示法（重点邻接距阵） 邻接表两种存储结构图图均适十字链表图种表示图邻接表逆邻接表合邻接重表图邻接表改进边结点数量减少半（正等边数量）3 图遍历图种算法基础应熟练掌握图深度广度优先遍历手工模拟图遍历中栈队列指针状态变化4 （强）连通图中程次调深（宽）度优先遍历程（dfsbfs）遍历完全部顶点方法求出连通分量数画出遍历中形成深（宽）度优先生成树5连通图生成树唯生成树边权值唯 应熟练掌握primkruscal算法特手工分步模拟生成树生成程6 拓扑排序图入度（先）零顶点种排序结果唯关键路拓扑序前提求出源点汇点长路径应掌握两种算法熟练手工模拟理解减少关键活动时间缩短工期指该活动关键路径减少尚未改变关键路前提效7 单源点顶点顶点间短路问题掌握算法熟练手工模拟
三例题解析
1邻接重表实现图种运算
2 编写图深度优先非递遍历算法
第九章 查找 约25min
容提
1 章介绍查找表称集合数结构元素间约束力差数结构：元素间关系元素仅集合中 2 查找表操作：查找检索插入删成员关系判断
3 静态查找表：序表序表静态树表索引序表 4 动态查找表：二叉排序树衡二叉树B树B+树键树 5 哈希表
二 学重点
1查找表称集合数结构元素间关系非常松散操作需助数结构实现章列举三种方法（静态查找表动态查找表哈希表）实现查找表运算2序表引设置监视哨查找效率提高序表均查找长度超树深度判定树唯索引序查找综合述二者优点较快速查找适应动态变化求3二叉排序树形态取决元素输入序中序遍历结点序序列应熟练掌握建立查找插入删算法4佳二叉排序树均查找长度短二叉排序树衡二叉树介佳般间折中应熟练掌握手工绘制衡二叉树5 键树中结点关键字字符该树序树（层兄弟间左右递增结束符号）6 哈希表查找表（集合）表示方法根选定哈希函数处理突方法关键字映哈希表中突避免7 哈希表中关键字查找哈希函数计算序折半查找元素删作标记物理删
三例题解析
1．设二叉排序树中元素均整数试编写算法输出元素值
2． 编写二叉排序树插入结点s算法
3．编写索引序表中查找数k算法
4．已知含100记录表关键字中国名拼音请出表哈希表设计方案求等概率情况查找成功均查找长度超3
第十章 部排序 约25min
容提
1排序定义排序作线性表种操作2排序分类稳定排序稳定排序定义3插入排序（分插入二路插入表插入希尔插入排序）4交换排序（泡排序快速排序）5选择排序（简单选择排序树形选择排序堆排序）6排序基数排序
二学点
1．种排序基基思想2．差情况排序性分析否稳定排序结3．插入排序基假定排序文件第记录序然第二记录起次插入已排序序子文件中直整文件序减少较次数移动次数进行种改进产生折半二路表插入希尔等系列插入排序4．交换排序基相邻记录较逆序进行交换泡排序快速排序交换排序例子快速排序目前快部排序法应采三者取中法防止性退化5．简单选择排序树形选择排序堆排序选择排序例子堆排序较重差性快速排序差性（Ologn）6．排序基数排序时间复杂度O(n2)排序稳定排序希尔排序快速排序堆排序等时间性排序方法包括简单选择排序稳定排序7．种排序方法学应掌握质（排序基思想）举反三
二例题解析
1．设排序文件n ( n>0 )记录试编写算法全部排序第j (0
3编写排序非递排序算法
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
