1
大学计算机 (理工科类 )
6学时授课
2
直觉思维,以天资和悟性在整体上对诸多现象直觉领悟而获得智慧
，
以公理宣告,受人推崇 。 产生人文学 。 如孔子,耶酥,诸葛亮等 。
类比思维,以事物之间存在的普遍联系而联想,比较,推理,从而达到举一反三,触类旁通 。 易形成技术 。 如前人的鲁班大师 。
形象思维,从感性上形象地反映客体的具体形状和姿态,通过意想
、
联想和想象揭示对象的本质及规律 。 如中医的脉络,气功,功夫 。
逻辑思维,在感性认识的基础上,运用概念,判断,推理对客观世界的认识过程 。 推动了科学 。 如牛顿,爱因斯坦及贝尔 ·盖慈等 。逻辑思维的低级阶段：
分析,把客观对象的整体分解为一定单元,要素,if<e>then<S>
综合,在分析基础上把单元,要素,部分的认识联系起来 。
逻辑思维的高级阶段：
归纳,通过个别实验得到科学规律的方法 。 即从现象到本质 。
演绎,通过一般规律进一步认识,解决个别问题的方法 。
逻辑思维方法正是我们中国人缺乏的思维方法,注意思维方式改变 。
程序设计中的思维方式程序设计,安排计算机操作的步骤，以逻辑思维工作、人 —机交互语言实现。应注意语言学习与思维方式改变同等重要。
3
程序设计课程特点语言,人类表达意念,交流思想的工具，由语音,词汇和语法组成。
① 机器语言,以‘ 0/1?表示数据和指令，使静态机器变成自动机
。
② 汇编语言,以符号编码数据和指令,使自动工具变成人类助手
。
③ 高级语言,以人语言表示机器操作方法 (算法 )，人教机器工作
。
④ 查询语言,以数据结构和对象方法表现主题,人命令机器工作
。
程序设计逻辑性,以,是 /否”判断多重推理,严密而清晰,需要耐心
。
二进制特殊性,0/1简单性,信息再生性,单加运算性,编码还原性 。
数据的多型性,以值 /制 /型 /位 /格组织，形成类型,存贮,逻辑结构。
运算符多样用性,算术,关系,逻辑等几十种。有结合性和优先级。
算法的灵活性,以指令与数据描述，实现操作步骤 (算法 )灵活多变
。
操作的严密性,输入,1/0”错、全错 ； 变量错结果乱 ； 程序错死机。
程序结构的自由性,面向问题自由化、过程结构化、对象系统化。
教学方法不适应性,内容多、学时短、学生习惯讲教而非引导。
解决办法,
1,加强逻辑思维训练，循序渐进，引导学生从上到下分析问题。
2,程序设计教学须长流水、不断线，不能连续十周草草结束。
4
语 言 特 点 数 据 语 句初学者语言 BASIC 简单,易学方便 使用不分类型 1,输入输出工程语言 FORTRAN 便于计算,快速 整、实、逻辑 2,赋值语句教学 语言 PASCAL 思路清晰好懂 数组,字符串 3,调用语句计算机工作者 (函数,过程语言 C 程序块 )
4,控制语句实用程序设计 选择 if else
语言 C++ 循环 for(… )
while,DO
大众化视窗语 5.辅助语句言 Visual C ++ 空,转向,中断应用查询语言
C程序设计复习程序设计语言简介语 句算式连数据言 算按步加工数环 饶结果编译连境 遇错误能提示算 符变量表达式法 有穷效行确对语 句函数结构化言 外指针构造类操作地址的低级语言以函数为基本单元数据及运算符复杂以对象为基本单元使用封装,继承,多态完成软件重组、复用利用控件资源组装文件嵌入程序实现功能增指针 (地址 )、
结构体,联合,
枚举,位域,流窗口,按钮,控件组数据,嵌编程指针,应用,枚举类,对象,事件成员 (变量,函数 )
用于管理、网络等，让计算机编程由“怎么做”变为“做什么
”？
5
算 符数据表达式法 则编码字控数语 句函数组程序言 外指针构造类数据,类型 (算法 ),存贮 (机器 )、逻辑 (算题 )
运算符,型式符号,优先级,结合性,自增减表达式,算术、关系、逻辑、条件、赋值。
数值算法,解析,判断,穷举,递推,矩阵。
字符算法,统计,排序,(添删改 )编辑,转换。
控制算法,分支,循环,跳转、交换、分类。
语句,加工数据,组成程序的基本元素。
包括表达式,函数,控制,复合,空语句 。
函数,完成具体功能，程序的基本单元。
包括函数头,函数参数,函数体,返回值 。
程序,文件组成,编译运行,预定义,调函数指针,可指向变量,数组,函数,结构体的地址结构体,不同类相关数据集合 。 联合,枚举等
C 语言复习一、程序设计概念
6
细化题义定函数安排数据逻类贮确定算法基数符加工编码算式句主函数 (输入,调用,输出 )
函 函数,类,名,(参数 )
自定义 函数体 (变量,语句 )
数 返回值 (数组名,指针 )
库函数 (包含、功能、返回 )
C程序设计复习二,C程序 设计方法解析,穷举转换，递推比较，转换排序，查找迭代，积分基本：
算 字符
,法数值：
输入 /出,控制,中间数据常 /变量、局 /全域整 (长短 )、实 (单双 )
字符 (字串 )、数组结构,联合,指针,位域动,静,内,外,寄存,位逻辑结构数类型结构据存贮结构
+/-/*/除 /与
/或 /非 /大小 /等数据 +算符 +数算 /逻 /条 /逗 /位表达式,空语句复合,函数调用条件开关控制 循环辅助运算符表达式语句编码
7
值确定的常量与变量 。 如,3,-2.13,2.5e-4,PI等 。
值变化的量。用前定义,确定地址,分配单元 。
short int a,score[n];
long as a[n];
单精度,float c,ax[n];
double d,max[n];
字符,char c,sa=?a?;
字串,char a[n]=“student”
C 语言复习三、数据类型运算中自动转换
int?char,short
Unsigned? 必然
long?按需
double? float
数 有整实字串型据 守补码占内存结 合题意想逻辑构 造新类与指针同类数据集合。一维与多维。
多维可按行列顺序使用。如,a[N];b{m][n];
不同类型的相关数集合。如：姓名、性别、年龄等占用同一存贮单元的不同类型相关数据集合 。如职业等。
用于存放地址的变量。按地址操作程序紧凑快捷。
值 存补码型不同位 出值入保精度型符制 算自转换格 式转义修饰符
00-00 0 0
00-01 1 2
：,,
01-11 127 127
10-00 128 -126
:,,
11-10 254 -2
11-11 255 -1
字节存贮数据：常值：
变量：
整型：短整：
基 长整：
本 实型：
型 双精度：
字符型：
构 数组：
造型 结构：
联合：
指针型：
8
外部变量：
作 局部变量,
用域 全局变量：
动态变量,
存贮 静态变量：
类寄存器变量：
C 语言复习四、简单变量即全局变量，定义在本文件之外，用 extern引用。
在定义范围内有效 。 如函数,复合语句内。
1,auto 型 (省略时隐含 )。 2,静态局部型 3,寄存器型。
定义在函数外 (即外部变量 )，
在函数或程序块内 auto(可省 ),用时分配地址用完回收。如：局部、寄存器、形参。
static 编译时分配地址，程序结束回收。
1,内部 (局部 )静态。 static int a,b
2,外部 (全局 )静态。 static int a,b
register 设的定在 CPU或主板中的变量。
数据在内存、运行速度快。如,register int
变量,计算机中有名子的存贮单元。代替固定类型的数据，
其存贮方式 (存贮结构 )直接影响着计算机的运行速度 。
9
1、小故事 1,千年虫”问题？
当 2000年新年钟声即将敲响，亿万人们在企盼新的千年会给他们带来好运的时刻，有些人却难以高兴起来。因为“千年虫”可能给他的事业带来难以预料的损失，因百年时间可能为零、飞机难以降落等。
2、小故事 2,啤酒”和“尿布”的故事
：
年轻的爸爸在购买尿布之余，总是忘不了给自己带上几罐啤酒。百货公司将原本放在两处的啤酒和尿布集中一起摆放，还提供包括啤酒和尿布在内的日用杂货，结果销售额大增。
1.1 数据结构基本概念
10
启示
1、类似以上的故事情况早有发生，启发我们：
① 数据在内存中占有一定的空间，如何组织它们？
② 许多数据之间是孤立、离散的，但也可能在数据之间具有明显的一定关系，需要管理；
③ 有许多数据具有隐藏在深处的关系，需要挖掘 。
2、研究数据的三个工具：
① 程序设计人员要熟悉数据结构。
② 软件应用人员利用数据库可以动态管理数据。
③ 高层管理人员利用数据仓库可以获得决策支持
3,数据结构,指数据与数据间相互关系。包括数据类型结构、数据存贮 (逻辑 )结构和对数据的操作。即研究计算机中放置二进制数据及符号的方法。以便快速运行。
1.1 数据结构基本概念
11
④ 数据对象,某种数据类型元素的集合,即一类数据例如，整数的数据对象是 {… -3,-2,-1,0,1,2,3 …
英文字符类型的数据对象是 {A,B,C,…,±,⊙,★,… }
4、数据结构中常用术语：
① 数据,是对客观事物的描述、是信息的载体，能被计算机加工、处理的数字和符号集合。
② 数据元素,是数据的基本单位，可包含若干数据项、也称为记录。由记录组成的线性表称为文件。
③ 数据项,具有独立意义的最小数据单位,即数值 。
1.1 数据结构基本概念学 号 姓 名 性 别 政治面貌 马 列 高 数 英 语 计算机
0709101 张三 男 团员 85 90 85 90
0709101 李四 女 党员 90 87 90 78
0709101 王五 男 群众 76 86 80 69
… … … … 表中一行或一列均为一个数据元素 … … … …
12
5,数据逻辑结构,数据间相互关系，分为：
① 集合结构 数据元素除了同属于一种类型外，别无其它关系。
② 线性结构,数据元素之间存在一对一的关系。
③ 树型结构,结构中数据元素间存在一对多的关系。
④ 图状 (网状 )结构,数据元素之间存在多对多的关系。
6、数据结构的表示方法,即数据的存贮方式 。
① 顺序存储结构,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
② 链式存储结构,在每一个数据元素中增加一个存放地址的指针,用此指针来表示数据元素之间的逻辑关系。
1.1 数据结构基本概念
13
数据 (存贮 )结构不同于数据类型,也不同于数据对象,它不仅要描述数据类型的数据对象，而且要描述数数据对象各元素之间的相互关系。
1.1 数据结构基本概念数 型表栈队树图据 题算法时空度结 合取存要快速构 造顺序与链存例：履历表的数据结构定义如下,S=(C,R)
其中,C 是含若干个项目，如年龄、职业、填表日期等的集合 ﹛ C1,C2,Cn ﹜,
R={P},P 是定义在集合上的一种关系
{<C1,C2>},如，年龄与出生年月日有关。
7、数据结构的形式定义,数据结构是数据存贮逻辑结构、由二元组成：数据 -结构 =(D,S)
其中,D 是数据元素的有限集，
S 是 D 上关系的有限集。
14
8,数据的运算,数据运算定义在数据逻辑结构上的操作,但运算的具体实现要在存贮结构上进行 。
数据运算对数据结构是非常重要,各种逻辑结构有相应的各种运算要求 。 常用的几种运算为：
① 插入,向数据结构里加入新的节点 。
② 删除,把指定的节点从数据结构里去掉 。
③ 查找,在数据结构里找寻满足一定条件的节点 。
④ 替换,改指定节点一个域或多个域的值 。
⑤ 排序,在线性结构中保证节点数不变的情况下,
按某种指定的顺序排列 。 它是用量最大是算法
1.1 数据结构基本概念
15
1.2 算法分析与设计
1、算法 (Algorithm),对特定问题求解步骤的一种描述。 如、查找元素的二分法。
算法是指令的有限序列,其中每一条指令表示一个或多个操作。如两个变量交换数据,swap a,b
2、算法的五个重要特性：
1),有穷性,一个算法必须在执行有限次后结束,每步定时
2),确定性,每条指令必须有确定含义,不能有二义性。
3),可行性,算法描述的执行步骤必须在计算机上可行 。
4),输入,一个算法按功能应有零个或多个输入。
5),输出,算法执行结束要有结果输出或产生相应动作。
算 值设计结构类法 有穷效行确对分 解表树队栈串析 剖计量操作序
a b
c①
②
③
16
1.2 算法分析与设计
3、算法的正确性,只有保证正确的解算结果，才能讨论算法的好坏。如：设计一个求三角形面积的算法，给定三角形的三条边分别为 a,b,c,求面积 area的简单算法为：
step1 read(a,b,c)
step2 S:=(a+b+c)/2
step3 area=sqrt(s*(s-a)*(s-b)*(s-c))
step4 write(area)
应从以下几个方面考虑：
① 数学原理正确吗？三角形的两边之和应大于第三边?
② 解题条件正确吗？边常能为负数？，能否开平方？
③ 执行路径合理吗？程序 (调函数 )中常有判断转移,对？
显然、该题上机运行后有时正确、有时错误，甚至死机。为什么？
a
b c
17
1.2 算法分析与设计
3、算法的正确性：,正确,的含义在通常的用法中有很大的差别 (不严密 )，大体可分为以下四个层次,① 程序可运行,程序不含语法错误；可用于运行。
② 结果也正确,对几组输入数据能得出满足要求的结果
③ 条件下正确,程序对一切合法的输入数据都能产生满足规格说明要求的结果。符合程序功能的基本要求。
④ 完全正确,对于精心选择的典型、苛刻而带有刁难性的数据能够得出满足规格说明要求的结果；由测试完成。
最简单和最直接的算法往往不是最有效的，但算法的简单使得证明其正确比较容易，同时便于编写、修改、阅读和调试，所以应强调简洁。但对经常使用的算法来说,高效率 (减少运行时间和压缩存储空间 )比简单性更为重要。
18
4,时间复杂性分析,何达到高效? 省时省内存 。
学习时间复杂度意义,时间复杂性能给出算题运算需要的估计时间,相应计算机的解题时间及如何选择计算机 。
① 时间频度,一个算法中的语句执行次数称为语句频度或时间频度 。 其实质是在一个循环中找关键操作 。
执行一个算法所耗费的时间,理论上难以计算,须上机运行测试 。 但实际不能也不必,只需知道各算法的花费时间 。 同时一个算法花费的时间与算法中语句的执行次数成正比例 。 记为 T(n)。 如 下列算法段的语句频度：
1.2 算法分析与设计
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
分析：该算法为一个二重循环,执行次数为内外循环次数相乘,但内循环次数不固定,与外循环有关,因些,时间频度 T(n)=1+2+3+… +n=
2 )1(?nn
19
4,时间复杂性分析：
② 算法的时间复杂度,算法中实现基本操作的语句 (基本语句 )重复执行的次数 f(n),称为算法的频度 。
记作,T(n)=O(f(n)) 随问题规模 n的增大，算法的频度 T(n)和重复次数 f(n)的增长率同阶。
例 1,x+=5; 单个语句频度为 1，则 程序段的时间复杂度为 T(n)=O(1)。
1.2 算法分析与设计例 2,for (i=1; i<=n; ++i) /* n+1 */
for (j=1; j<=n; ++j) /* n(n+1) */
c [i][j]=0; /* n2 */
共执行,T(n)=2n2+2n+1 当 n充分大时 T(n)与 n2是同阶的。该算法时间复杂度为,T(n)=O(n2)
20
4,时间复杂性分析,② 时间复杂度
1),O(n2)复杂度,在 时间频度中,n称为问题的规模,
当 n不断变化时,时间频度 T(n)也会不断变化 。 要知道变化规律,引入时间复杂度概念 。
1.2 算法分析与设计例如,若 T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1/2,故它的时间复杂度为Ｏ (n2),即Ｔ (n)与 n2 数量级相同 。
设 T(n)的一个辅助函数为 g(n),定义为当 n大于等于某一足够大的正整数 n0时,存在两个正的常数 A和 B（ 其中
A≤B）,使得 A≤T(n)/g(n)≤B均成立,则称 g(n)是 T(n)的同数量级函数 。 把 T(n)表示成数量级的形式为：
T(n)=Ｏ (g(n)),其中大写Ｏ为 Order(次 /阶 /序 /量 /级 )的首字母 。
21
4,时间复杂性分析,② 时间复杂度
2),O(n3)复杂度,分析该算法段的时间频度及时间复杂度：
1.2 算法分析与设计
for（ i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k; =
= = +
= [ + ]
n
k
k
1
)...321(
n
k
kk
1
2
)1(?
n
k
k
1
2[
2
1?
n
k
k
1
]
2
1
6
)12)(1( nnn
2
)1(?nn
由于有 1/6 ≤ T（ n)/ n3 ≤1，
故,时间复杂度为Ｏ (n3)。
分析算法规律可知 时间频度
T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)
i 变化范围,j变化一段,K改变值
i
=
1
2
…
↓
n k=1,2 … →j
… … …∶
∶
22
4,时间复杂性分析,② 时间复杂度
3),O(log2N)复杂度,对于二分发查找一个数,粗略的可以看作,每经过一次关键码比较,则将查找范围缩小一半,
因此经过 [log2n]次比较就可完成查找过程,因此表示为：
T(n)=O(log2n)
1.2 算法分析与设计
I J K L MHGFEDCBA
①
②③
④
4),O(nlog2N)复杂度,对于快速排序,归并排序,堆排序,均可看成 T(n)=N(nlog2N),显然其运算量：
大于 O(log2N) 而小于 N2。
23
1.2 算法分析与设计
4,时间复杂性分析：
② 时间复杂度 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为 O(1),另外,在具体的时间频度不相同时,时间复杂度却有可能相同,如
T(n)=n2+3n+4与 T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为 O(n2)。
时间复杂度按数量级递增排列,常见的时间复杂度有：
常数阶 O(1),对数阶 O(log2n),线性阶 O(n),
线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),...，
k次方阶 O(nk),指数阶 O(2n)。 随着问题规模 n的不断增大,
上述时间复杂度不断增大,算法的执行效率越低 。
24
1.2 算法分析与设计
4、时间复杂性分析,如当计算机操作为 1ms/次、即 1000次 /秒。
算法类时 间复杂度可解问题最大长度 (n) 计算机速度对解题长度影响
1秒钟 n 1分钟 1 小时 提高前 提高 10倍 对应算法
A1 O(n) 1000 60000 3.6× 106 s1 10s1 顺序,分支
A2 (nlog2n) 140 4893 2.0× 105 s2 7.2s2 排序,查找
A3 O(n2) 31.6 245 1897 s3 3.16s3 循环,排序
A4 O(n3) 10 39 153.3 s4 2.15s4 三重循环
A5 O(2n) 9.9 15.8 21.7 s5 s5+3.3 穷举,遍历
5、大 O表示法加法规则,当两个并列的程序段时间代价分别为 T1(n)=O(f(n))和 T2(m)=O(g(m))时，其连在一起的时间代价为,T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))
显然,C<log2n<n<nlog2n<n2<n3<2n<n!
当,A2算法在 1秒内可完成问题长度为 n=140的算题 (由 nlog2n=1000)。
25
6,空间复杂度,与时间复杂度类似,指算法在计算机内执行时所占用的内存开销规模 (称为空间频度 ),一般所讨论的是除正常占用内存开销外的辅助存储单元规模 。
1.2 算法分析与设计
① 程序运行所需的存贮空间包括两部分：
固定部分,如指令代码,常数,简单变量定长变量
(数组,结构,变量 ),对这些静态空间只需统计即可 。
可变部分,与问题规模有关成分所占空间,如引用变量,递归栈,运行中 new,delete命令动态使用空间 。
② 空间复杂度表示,应分析一个程序实际占用存贮空间,主要是完成问题 n过程中不断占用 ---释放 ---占用的瞬时渐进最大空间 。 而不是指令,常数,指针及输入数据占用空间,主要是解算问题所需的辅助空间 。 空间复杂度可表示为,S(n)=O(f(n))
26
1.3 线性表
1,线性表,线性表是 n(n≥0) 个元素的有限序列，它们之间的关系可以排成一个线性序列：
a1,a2,……,ai,……,an
其中,n称作表的长度,当 n=0时,称作空表 。
2,除首尾两个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱,最后一个数据元素无后继。
2、线性表的特点：
1,线性表中所有元素的性质相同。如数组，它就是一个线性表。
3,数据元素在表中的位置只取决于它自身的序号。
假设线性表中的第一个数据元素的存储地址为 Loc(a0)，
每一个数据元素占 d字节，则线性表中第 i个元素 ai在计算机存储空间中的存储地址为,Loc(ai)= Loc(a0)+id
27
1.3 线性表例 3 学生健康情况登记表,每一 行或列都是线性表,但其内部元素的数据类型不同而有规律。
姓名 学 号 性别 年龄 健康情况王小林 790631 男 18 健康陈红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱
…,.,…,.,… … … … … …
3、线性表举例,
例一,26个英文字母的字母表 (A,B,C?,Z ）
例二、某校从 1981 年到 1986 年各种型号的计算机拥有量的变化情况。 ( 1,17,28,50,92,188 ）
28
1.3 线性表4、线性表的特征：
① 非空的线性表,有且仅有一个开始结点 a1,它没有直接前趋 (向左 ),而仅有一个直接后继 (向右 ) a2 ；
② 终端结点,有且仅有一个终端结点，该结点再没有直接后继，而仅有一个直接前趋 a n-1 ；
③ 其余的内部结点 ai(2 ≦ i ≦ n-1)； 它们 都有且仅有一个直接前趋 a i-1 和一个直接后继 a i+1 。
④ 元素间为一对一线性关系 。 即 ai是一个字,字母或记录对应的逻辑结构图如图所示。
a1 a2 … an
结论,线性表是一种典型的线性结构,用二元组表示为：
linear_list=(A,R) 其中,A={ai |1≤i≤n,n≥0,ai∈ elemtype}
注,elemtype为类型设定 R={r} r={<ai,ai+1> ∣ 1≤i≤n-1}
29
5、线性表算法,常见线性表的运算有：
1,置空表,SETNULL（ &L） 将线性表 L置成空表
2,求长度,LENGTH（ L） 求给定线性表 L的长度
3,取元素,GET（ L,i） 若 1≤i≤length(L),则取第 i个位置上的元素,否则取得的元素为 NULL。
4,求直接前趋,PRI0R（ L,X） 求线性表 L中元素值为 X
的直接前趋,若 X为第一个元素,前驱为 NULL。
1.3 线性表
5.求直接后继,NEXT（ L,X） 求线性表 L中元素值为 X
直接后继,若 X为最后一个元素,后继为 NULL。
6,插入,INSERT（ &L,X,i） 在线性表 L中第 i个位置上插入值为 X的元素 。
7,删除,DELETE（ &L,i） 删除线性表 L中第 i个位置上的元素 。
30
一个线性表 L定义为 L=(a1,a2,…,an),当 L=（ ） 时定义为一个空表,其操作为,
void setnull(&L) //将线性表 L置成空表
int Length(L) //求给定线性表 L的长度
elemtype Get(L,i) //取线性表 L第 i个位置上的元素
1.3 线性表
6、线性表数据类型描述例二,假设线性表 L=(23,56,89,76,18),i=3,x=56,y=88,则对 L的一组操作及结果如下：
Length(L);
Get(L,i)
Prior(L,x)
Next(L,x)
Locate(L,x)
Insert(&L,y,i)
Delete(&L,i+1)
// 所得结果为 5
// 所得结果为 89
// 所得结果为 23
// 所得结果为 89
// 定位,所得结果为 2
// 所得结果为 (23,56,88,89,76,18)
// 所得结果为 (23,56,88,76,18)
31
7、顺序表定义：
C语言描述顺序存储结构下的线性表
(顺序表 )如下：
#define TRUE 1
#define FALSE 0
#define MAXNUM <顺序表最大元素数 >
Elemtype List[MAXNUM] ; /*顺序表 List*/
int num=-1; /*当前数据元素下标，并初始化 */
1.3 线性表也可将数组和表长封装在一个结构体中：
struct Linear_list {
Elemtype List[MAXNUM]; /*定义数组域 */
int length; /*定义表长域 */
}
设,LOC(a1)是线性表第一个数据元素的存储位置,通常称做线性表的起始位置或基地址。 LOC(ai)=LOC(a1)+(i-1)*l
LOC(ai+1)=LOC(ai)+l
存储地址内存排列 位置序号
0
1
2
…
i
…
n
…
maxlen-1
b
b+d
…
…
b+(n-1)× d
顺序存储结构示意图
X
a1
a2
…
ai
…
an
…
b+(i-1)d
32
① 顺序表的插入算法,在顺序表 List[ ]中，当表尾元素为 *num位置，在第 i个元素前插入数据元素 x。
int Insert(Elemtype List[ ],int *num,int i,Elemtype x)
{
int j;
if (i<0||i>*num+1)
{ printf(“Error!”) ; return FALSE;} /*插入位置出错 */
if (*num>=MAXNUM-1) /* MAXNUM 内存最大空间 */
{ printf(“overflow!”); return FALSE;} /*表已满 */｝
for (j=*num;j>=i;j--)
List[j+1]=List[j]; /*数据元素后移 */
List[i]=x; /*插入 x*/
(*num)++; /*长度加 1*/
return TRUE;
}
1.3 线性表
8、顺序线性表运算：
33
int Delete(Elemtype List[],int *num,int i)
{ int j;
if(i<0||i>*num)
{ printf(“Error!”); return FALSE;} /* 删除位置出错 */
for(j=i+1;j<=*num;j++)
List[j-1]=List[j]; /* 数据元素前移 */
(*num)--; /* 长度减 1。 注意与 *num- -的区别 */
return TRUE;
}
② 顺序表的删除算法,在线性表 List[]中,*num为表尾元素下标位置，删除第 i个元素，线性表的元素减 1，
若成功，则返回 TRUE；否则返回 FALSE。
1.3 线性表
8、顺序线性表运算：
34
从上述两个算法看很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上 。 而移动元素的次数取决于插入或删除元素的位置 。
假设 Pi是在第 i个元素之前 插入一个元素的概率 (由题目确定 )，则在长度为 n的线性表中插入一个元素时所需的移动次数为：
)(
0
inpE
n
i
ii n s
9、线性表 算法分析 1.3 线性表
1
1
np i
2
)(
1
1
0
nin
n
E
n
i
i n s
则 移动的平均次数为,
如果在线性表 任何位置插 入 或删除元素的概率相等 (移 n插 1)，即：
35
如果在线性表的 任何位置 插入或删除元素的概率相等，即：
)1(
1
0
inqE
n
i
id e l
nq i
1?
9、线性表 算法分析
1.3 线性表假设 qi是删除第 i个元素的概率，则在长度为 n的线性表中删除 一个元素 时所需移动元素次数的平均次数为：
则平均移动次数为,2 1)1(1 1
0
nin
n
E
n
i
d e l
可见，在顺序存储结构的线性表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。
它的时间复杂度为Ｏ (n),即Ｔ (n)与 n 数量级相同。
36
小结,线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出,因此顺序存储结构的线性表是可以随机存取其中的任意元素 。 同时也有较高的存贮效率 。
但是,顺序存储结构也有不便之处,主要表现在：
1.3 线性表
（ 1） 数据元素最大个数需预先确定,使得高级程序设计语言编译系统需预先分配相应的存储空间；
（ 2） 插入与删除运算的效率很低 。 为了保持线性表中的数据元素顺序,在插入操作和删除操作时需移动大量数据 。 对于插入和删除操作频繁的线性表,将导致系统的运行速度难以提高 。
（ 3） 存储空间不便于扩充 。 当一个线性表分配顺序存储空间后,若线性表的存储空间已满,但还需要插入新的元素,则会发生,上溢,错误 。 并不能利用内存碎片 。
37
1.4 线性链表链表,用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位碎片。
pointdata pointdata pointdata… …
因此,链表中结点的逻辑次序和物理次序不一定相同 。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址 (位置 )信息，这个信息称为指针 (point)
或链 (link)。 结点值 (数据 )和指针 组成了链表中的结点结构。
38
data point1.4 线性链表显然，单链表中每个结点的存储地址是存放在其前趋结点下个域中，而开始结点无前趋，故应设头指针 head 指向开始结点,同时，由于终端结点无后继，故终端结点的指针域为空，即 Null。
其中,data是数据域,用来存放结点的值,
point是指针域 (亦称链域 )，用来存放结点的直接后继的地址 (或位置 )。由于上述链表的每一个结点只有一个 链域,故将这种链表称为单链表。
问图中的字母顺序？
链域数域
39
…..
a2
a1
an
…..
ai+1
ai
0
1
i-1
i
n-
1
① 在数组中插入运算,插入运算应先作安全性检查,再后移插入 。
实现顺序表插入元素的主函数
viod main( )
{ int M=10;n=6; /*M是数组的大小,n是表中已有元素个数,即表长 */
int result,k;
static int V[10]={3,5,7,10,8,6}; /*数组赋初值 */
result=insq(4,25,V,10,&n); /*执行函数调用,在第 4个元素前插入 25*/
if ( resul t= 1) { printf ("success ! \n");
for (k=0; k<n; k++) printf ("%d",V[k]);}
else printf("failure!");
}
1,顺序表运算 1.4 线性链表插入操作
a1head a2 a3 a4 an Nulla…
运算结果,3 5 7 25 10 8 6
X 5
X
40
int insq(int i,int x,int V[ ],int M,int *p） / *顺序表插入子函数 */
{ int n,j,/*在线性表 V中第 i个元素之前插入 X,i的合法值为 1?i?n */
n=*p; / *获取表长,p是指向存储表长的指针变量 */
if（ n==M) / *M是存储空间的大小 */
{ printf(“overflow\n”); return (0);} /*数组空间 M≤表长难插 */
if((i<1)‖ (i>n+1))
{ printf(“iis error \n”); return (0);} /*i值大小越界不合法 */
else { for (j=n; j>=i; j- -) V[j]=V[j-1]; /*插入位置后的元素依次右移 */
V[j-1]=x; /*插入 x */
p=++n; /*表长加 1,由 p返回 */
return (1); /* 1作为运行标志 */
}
}
注意数组元素从 0开始,I为 1存放在 V(0)
② 插入函数,主函数调用 result=insq(4,25,V,10,&n);
数组大小 10。 且有 4个元素,要求把 25插入到第 4个元素前
1.4 线性链表插入操作
3head 5 7 10 an Null
1,顺序表运算
X
25
41
…..
a2
a1
an
…..
ai+1
ai
0
1
i-1
i
n-1
③ 找内存单元插入原理：
对链表 L在在内存寻找 S处,后再插入 X，
2,链表运算 1.4 线性链表
(b)申请新结点 s,数据域置 x,s->data=x；
(a)寻找内存插入位置 S,并 强制链表类型
s=(LNode *)malloc(sizeof(LNode));
(c)修改指针域，将新结点 s插入：
s->next=q->next
q->next=s
关键语句：
head q
a1 a2 a3 a4
an Nulla…
pvoid Inselem(LinkList L,int i,int x){ LNode *p,*q,*s;
int pos=1;/*移动量
p=L;
if(i<1 || i>Getlen(L)+1) exit(1);
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
while(pos<=i)
{ q=p;p=p->next;
pos++;
}
s->next=q->next;
q->next=s;
}
X 5
XS
42
(b)返回被删除结点数据 x
(a)找到删除位置 p：
x=p->data；
(c)修改指针域，将结点 p删除关键语句
q->next=p->next；
free(p)；
④ 删除原理 delelem(L,i)的实现：
删除链表 L中第 i个元素,
2,链表运算 1.4 线性链表
a1
head
a2 a3 an Nulla…
q
a4
p
void Delelem(LinkList L,int i)
{ int pos=1; /* 位置记数器 */
LNode *q=L,*p; /*连接断开点
if(i<1||i>Getlen(L)) exit(1);
while(pos<i) /* 从第一点开始
{ q=q->next; /* 逐点查找
pos++; /*增加位置
}
p=q->next; /*找见位置
q->next=p->next; /* 重新连接
free(p); /*释放断开点
…X
43
⑤ 建立随机存贮链表,
建立一个学生姓名、成绩链表,通过 main()函数调用 main()
{ creat();
}
1,顺序表运算
1.4 线性链表
#define NULL 0
#define LEN
sizeof(struct student)
Struct student
{ long num;
float score;
struct studnt *next;
};
int n; /*全局变量供各函数 */
/*定义返回链表指针的函数 */
Struct student *creat(void)/*无形参直调用
{ struct student *head,*p,*q;
n=0; /*下面开辟一个新单元 */
p=q=( struct student *) malloc (LEN);
scanf(“%ld,%f”,&p ->num,&p->score);
head=NULL; /*头暂指向空，后面再赋值
while(p->num != 0)
{ n=n+1; /* 数据结点个数 */
if(n==1) head = p; /*p指向新开结点
else q->next=p; /*q指向最后结点
q=p;
p=(struct student*)malloc(LEN);/*新开
scanf(“%ld,%f,,&p->num,&p->score);
}
q->next=NULL; /*最后开辟结点为空未使用
retrn(head); /*返回链表起始地址。
}
num score next num score null
q 链表最后结点 P 链表新开结点head
44
1,顺序表运算
1.4 线性链表
⑥ 输出链表,先找见链表头 head地址，后移动指针变量 P，输出指向结点，再移动输出，直到连接终点 NULL：
Void print(struct student *head) /*链表头由实参传递
(struct student *p; /* 定义结构体元素指针
print(,\nNow,These %d records are:\n”,n);
p=head;
If (head != MULL) do
{ printf(“%ld %5.1 \n”,p ->num,p->score)；
p=p->next;
} while(p != NULL);
}
001 002 001head 001
NULL
P 指向打印 P 指向打印 P 指向打印 P 指向打印注意,为了辟免删除链表第一元素影响表头，链表通常第一结点不存贮元素，仅作链表表头使用。
45
Struct student *del(stuct student *head,long num)
{ struct student *p,*q;
if(head==NULL)printf(,\nlist null!\n”);return (head);)
p = head;
while (num != p->num && p->next !=NULL) /*未找到且还有 */
{ q=p,p=p->next;}
if (num ==p->num )
{ if (p == head )head=p->next; /*若找到头，第二地址给头
else q->next = p->next; /*将下一个地址给前一个地址
printf(“delete,%ld \n”,num;
n=n-1;
}
else printf(“%ld not been foud! \n”,num); /* 找完也未找到 */
return(head);
}
1,顺序表运算
1.4 线性链表
⑦ 删除链表一个元素：
从头开始逐渐查找，找到断开连接，并释放内存。
ai anai+1
删除操作
a
P已查结点 新找结点q已查结点 q P找到结点
46
P1
1,顺序表运算
1.4 线性链表
⑧ 寻找内存在链表中插入元素：
Struct student *insert( /* 顺序链表
struct student *head,struct student *stud)
{ struct student *p0,*p1,*p2; /*在 p2点后插
p1=head; p0=stud; /* p1检查点,p0为插入点
if(head==NULL){ head=p0,p0->next=NULL;}/*插空表
else /*从头到终逐个检查 P1结点,p0>p1向后 /P0<p1向前，从小到大插入
002 003 00n
NULL
002
P0
001head
p2 P1 P1p2
{ while((p0->num>p1->num)&&(p1->next != NULL))
{ p2=p1;p1=p1->next; } /*p0插入值大于检查点 p1，后移
if(p0->num<p1->num)/*p0插入值小于检查点 p1，插到 p1前
{if(head==p1)head=p0 else p2->next=p0;插头或插 p2后
p0->next =p1; } /*检查点紧跟新插点
else { p1->next = p0;p0->next = NULL; } /* 插到 p1后
}
n = n+1; /* 链表数据项数 +1
return(head)} /* 返回链表头
}
47
1.5 循环链表循环链表是一种头尾相接的链表其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活 。 有 单循环链表 和 双循环链表循环链表可以从表内任意位置开始插入或删除元素，而不仅是头结点，并要循环一圈或限制结束。
1、单循环链表,将终端结点的指针域改为指向表头结点或开始结点，就得到单链形式的循环链表，简称为单循环链表。为 使空表和非空表的处理一致,循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。
48
2、双循环链表,每个结点包括一个一个数据区和两个指针区，一个前项指针和一个反向指针。前向指针指向直接的前趋接点，反向指针指向其直接后继结点。这样每次处理结点时都可以从当前结点出发向前或向后查找。
1.5 循环链表
n a1 a2 an…head
a … ana1 a2head
为处理一致留出头结点
49
1.5 循环链表
3,静态链表,有些高级程序设计语言中没有指针类型,
这可以通过定义一个结构体数组实现类似于,链表,结构的形式,即为数组中每一个元素附加一个链接指针,从而形成静态链表结构 。 实际上它在不改变各元素物理位置基础上,通过重新链接就能够改变数组元素逻辑顺序 。 数组元素以记录形式构成 。 由于它是利用数组定义的,在整个运算过程中存储空间的大小不会发生变化,因此称这种结构为静态链表 。 设存放静态链表的数组 struct[MaxSize]
的定义如下,#define MaxSize 100
typedef struct
{ ElemType data;
int next;
}SNode; //结点类型
50
1.5 循环链表
4、动态链表,在程序执行过程中可从无到有的建立一个链表，即按使用开辟结点，输入各结点数据，并建立起前后的链接关系。从而避免了数组在使用前必须先定义固定的长度，以便在内存中临时分配空间，对于事前难以确定大小时，避免把数据空间定得足够大而浪费空间的弊端。
显然,各种存贮结构各有优缺点，使用中应根据实际应用需求选用适宜的存贮结构。
5,链表特点,链式存贮虽然比顺序存贮多占用一些指针空间，但存贮中的碎片可得到充分利用。删除后的结点也都能串接到一个链上，等待重新使用。 链式存取只能顺序存取，不能随机存取。对插入和删除操作，则利用链接存贮比较方便，无需移动元素 。
51
复习：选择填表例一,数据结构反映了数据元素之间的关系，链表是一种 (A),它对数据元素的插入和删除 (B)。
A,① 顺序存贮线性表。 ② 非顺序存贮非线性表。
③ 顺序存贮非线性表。 ④ 非顺序存贮线性表。
B,① 不需移动结点，不需改变指针 ② 不需移动结点，只需改变指针。
③ 只需移动结点，不需改变指针。 ④ 既需移动结点，又需改变指针。
1.5 循环链表通常查找线性表数据的方法有 (C)和 (D)两种方法，其中 (C)是一种适合已排顺序存贮结构但 (E)的方法，而 (D)
是一种对顺序及链式存贮结构均适应的方法。
C,① 顺序查找。② 循环查找。③ 条件查找。④ 二分查找。
D,① 顺序查找。② 随机查找。③ 二分查找。④ 分块查找。
E,① 效率较低的线性查找。 ② 效率较低的非线性查找。
③ 效率较高的非线性查找。④ 效率较高的线性查找。
√
√
√
√
√
52
复习：选择填表例二,线性表具有顺序和链接两种存贮方式，现有一个五元素的线性表 L={23,17,47,05,31},若它以链接方式存贮在下列 100～ 119号地址空间中，每个结点由数据 (占两字节 )和指针 (占两字节 )组成，其指针 X,Y,Z的值分别为
(A),(B),(C).
按上述连接方式存贮时，该线性表的首结点的起点地址为 (D),末结点的起始地址为 (E)。
供选择的答案,A～ E：
① 100 ② 104 ③ 108 ④ 112 ⑤ 116
⑥ 118 ⑦ NUll ⑧ 102 ⑨ 106 ⑩ 110
1.5 循环链表
⑤
③ ④
⑦ ①
104 108 112 116
Z47Y31V23X17U05
100 119
53
1.6 栈例,一叠书或一叠盘子。栈的抽象数据类型的定义如左,
假设栈 S=(a1,a2,a3,… )，
则 a1称为栈底元素,an为栈顶，栈中元素按 a1,a2,a3,… 的次序进栈，退栈的第一个元素应为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（ LIFO ）。
1,栈 (stack) 是限制只能在表的一端进行插入和删除运算的线性表，通常称插入,删除的这一端为栈顶 (顶端 )
，另一端为栈底 (底部 ) 当表中没有元素时称为空栈。
a1
a2
a n-1
a n
…
…
栈顶栈底 bottom
Top
54
1.6 栈
2、顺序栈 栈是一种运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表，因此可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量 top表示顶。
3、链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行，
由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。
55
1.6 栈
4、栈的应用,用一个数组 S(m)可实现栈的顺序存贮结构，数据入栈依次存入 S[0]S[1],
…,栈顶指针 top指向栈顶元素 S[top]，
top<0 表示栈空,top>=M表示栈上溢。
① 元素 x进栈操作：
S[0]
S[1]
∶
S[top]
∶
S[M-1]
T0p
if (top = M-1) {printf(“stack is full\n”; return (0); } /* 栈满返回 0*/
top ++; /* top 指针上移一个位置 */
S[top] =x ; /* x进栈 */
return (1); /* 进栈成功，返回 1 */
② 从栈弹出过程：
if (top<0) {printf (“stack is empty \n”),return (0);} /* 栈空返回 0 */
x = s[top]; /* 取出栈顶元素 */
Top --; /* Top指针移下一位置 */
return (x); /* 出栈成功，返回栈顶元素 */
56
结论,后进先出 (Last In First Out)，简称为 LIFO线性表。
举例 1：家里吃饭的碗，通常在洗干净后一个一个地在一起存放，在使用时，若一个一个地拿，一定最先拿取最上面的那只碗，而最后拿出最下面的那只碗。
举例 2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
显然、在描述括号运算的数据结构中，大中小 {[( )]}的运送顺序就是一个栈的操作。
1.6 栈栈结构的基本操作,
（ 1）初始化栈 InitStack(S) （ 2）判断栈是否为空 StackEmpty(S)
（ 3）入栈 Push(S,item) （ 4）出栈 Pop(S,item)
（ 5）获取栈顶元素内容 GetTop(S,item)
57
1.7 队列队列 (Queue) 也是一种运算受限的线性表它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头 (Front),允许插入的一端称为队尾 (Rear)。
例如：排队购物时的队列操作系统中的作业排队。由于先进入队列的成员总是先离开队列，因此队列亦称作先进先出 (First In First Out) 的线性表，简称 FIFO 表。
1、顺序队列 当队列中没有元素时称为空队列,在空队列中依次加入元素 a1,a2,… 之后,a1 是队头元素,a2
是队尾元素。显然退出队列的次序也只能是 a1,a2…,
也就是说队列的修改是依,先进先出,的原则进行的。
58
由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。
1.7 队列队列结构的基本操作：
（ 1）初始化队列
InitQueue(Q)
（ 2）入队 EnQueue(Q,item)
（ 3）出队 DeQueue(Q,item)
（ 4）获取队头元素内容
GetFront(Q,item)
（ 5）判断队列是否为空
QueueEmpty(Q)
59
2 循环队列 将向量空间想象为一个首尾相接的圆环
，并称这种向量为循环向量，存储在其中的队列称为循环队列（ Circular Queue)在循环队列中进行出队,入队操作时
，头尾指针仍要加 1,朝前移动。只不过当头尾指针指向向量上界 (QueueSize-1)时，其加 1 操作的结果是指向向量的下界 0 (转了一圈 )。
1.7 队列
60
1.7 队列端和删除端都是浮动的。 通常我们将插入端称为队尾，
用一个,队尾指针,指示 ； 而删除端被称为队头,用一个,队头指针,指示 。
结论,队列也是先进先出线性表 。
举例 1,到医院看病，首先需要到挂号处挂号，然后，
按号码顺序救诊。
举例 3,在 Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。
61
1.8 串由一个或多个空格组成的串称为空白串 (Blank String)。
如,,和,” 分别表示长度为 1的空白串和长度为 0的空串 。 程序中串只能被引用但不能改变其值,即只能读不能修改串 (String) 是零个或多个字符组成的有限序列。一般记作 S=“a1a2a3… an”,其中 S是串名，双引号括起来的字符序列是串值； ai(1≦i≦n) 可以是字母,数码或其它字符；
串中所包含的字符个数称为该串的长度。 长度为零的串称为空串 (Empty String),它不包含任何字符。
串的基本操作包括：
1 串复制 (copy)：将串 s1 复制到串 s2 中。
2 联接 (concatenation)：将串 s1复制到串 s2的末尾。
3 串比较 (compare)：比较串 s1 和串 s2 的大小。
4 索引 (index)：找某字符 c在字串中第一次出现的位置
62
1.9 数组 例如，二维数组：
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn
多维数组是向量的推广。
可以看成是由 m个行向量组成的向量，也可以看成是 n个列向量组成的向量。
1,行优先顺序 —— 将数组元素按行排列，第 i+1个行向量紧接在第 i个行向量后面以二维数组为例，一个 m*n 个元素数组,按行优先顺序存储的线性序列为,a11,a12,…,a1n,a21,a22,…
a2n,……,am1,am2,…,amn。
在 PASCAL,C 语言中，数组就是按行优先顺序存储的。
2,列优先顺序 —— 将数组元素按列向量排列，第 j+1 个列向量紧接在第 j 个列向量之后，一个 m*n 个元素数组,按列优先顺序存储的线性序列为,a11,a21,…,am1,a12,a22,… am2，
……,an1,an2,…,anm
在 FORTRAN语言中，数组就是按列优先顺序存储的。
63
1.10 树和二叉树树型结构 树 是一类重要的非线性结构。
树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。
树结构在客观世界中大量存在，如家谱、行政组织机构等的形象表示，树在计算机领域中也广泛应用，如编译程序中用树表示源程序的语法结构；数据库系统中用树来组织信息；在分析算法行为时，用树来描述其执行过程等。
1、树 (tree) 是 n个结点 (n>=0)的有限集合，记为 T，
T 为空时称为空树，否则 T 应满足如下两个条件：
① 有且仅有一个特定的称为根 (root)的结点；
② 其余的结点可分为 m(m>=0)个互不相交的子集 T1，
T2,…,Tm,其中各子集又是一棵树,并称为子树 (Sub tree)。
64
1.10 树和二叉树孩子、双亲,结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 B,C,D是 A的孩子,A是双亲。
子孙,以某结点为根的子树中的所有结点都被称为是该结点的子孙。 B的子孙是 E,F,K,l。
祖先,从根结点到该结点路径上的所有结点。
兄弟,同一个双亲的孩子之间互为兄弟。
堂兄弟,双亲在同一层的结点互为堂兄弟。
根A
B C D
E
LK
F G H L
M
2、树结构常用术语,注意：结点 (对 )、节点 (可 )、接点 (错 )。
结点,数据元素内容及其指向其子树根的分支统称为结点度 (Degree),记作 d(v)。 结点的度,即树分支的个数 。
树的度,树中最大的结点度。终端结点 (叶子 )度为 0。
树的深度,树中结点层数最大值。
森林,m(m≥0) 棵互不相交的树。子树的结点为森林。
65
二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树,
这是二叉树与树的最主要的差别。
下图列出二叉树的 5种基本形态，图 (C)和图 (d)是不同的两棵二叉树。
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
1.10 树和二叉树
2、二叉树,是由 n(n>=0) 个结点的有限集合构成，
此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
66
1.10 树和二叉树
3、树与二叉树的区别,二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；树的子树没有次序。 深度为 K且具有 2k-1节点的二叉树称为满二叉树。
深度为 k的 n结点二叉树当且仅当每结点与深度 k满二叉树中层次编号从 1～ n的结点一一对应则称为完全二叉树。
树不区别左右，但二叉树是区别左右的，二叉树为左右不同的两种二叉树。二叉树有以下特征：
性质 1,在二叉树第 i层上至多有 2i-1个结点 (i≥1) 。
性质 2,深度为 k的二叉树中,最多有 2k-1个结点 (K≥1) 。
性质 3,具有 n个结点的完全二叉树的深度是,[log2n]+1
性质 4,任意一棵二叉树中，若其叶子的结点数为 n0，深度 2的结点数为 n2，则 n0=n2+1。
67
1.10 树和二叉树
4、二叉树的存贮,二叉树的存贮采用链接方式，以链表示一棵二叉树，用链指示元素的逻辑关系。链表中每个节点由三个域组成，数值域及表示左右子树的两个指针域，
以表示链接点的存贮地址。
lchild data rchild
其中 data是存放节点的数据信息,lchild 与 rchild
分别指向左右子树的指针,当子树不存在时,对应指针域值为空 (以 ^或 NULL表示 )。 链式存贮结构比较适合存贮二叉树 。
G
A
C
F
E
B
D
A ^
B
^ E C
^ D ^^ D ^ ^ D ^
68
1.10 树和二叉树
5、二叉树的常用操作及算法,遍历是二叉树的一种重要运算，按一定次序访问该结构中所有节点，可分两大类：
一、先根遍历,即先访问根，然后遍历每棵子树。
二、后根遍历,即先遍历每一棵子树，最后访问根。
按树的递归定义，树遍历按根 (N)、左 (L)、右 (L)次序可分为 NLR,LNR,LRN,NRL,RNL,RLN六种，实际常用以下三种二叉树遍历方法：
f
a
c
e
d
b
g
h
① 先序遍历法 NLR,先访问根节点、后序遍历左子树，再序遍历右子树。 Abdecfgh
② 中序遍历法 LNR,先序遍历左子树，后访问根节点，再序遍历右子树。 debfcgah
③ 后序遍历法 LRN,先序遍历左子树，
后序遍历右子树，再访问根节点。 edfgcbha
69
1.11 图
10.1 图的基本概念
BA C
D 6
3
2
1
5图是复杂的数据结构，有其完整的理论 ----图论。其基本概念为：
顶点,图中的数据元素
V：表示 顶 点的非空有限集合。
VR：表示两个 顶 点之间关系的集合。
无向图图有向图在有向图中,<V1,V3>表示从 V1到 V3的一条弧。
V1为弧尾或初始点,V3为弧头或终端点。
在无向图中,(V1,V3)表示 V1和 V3之间的一条边 。
V1 V3
V2 V4
V1 V3
V2 V4
p1
p2 p4p3
70
1.11.1 图
G=( V,E )
V1 V3
V2 V4
顶点集合 V={V1,V2,V3,V4 }
弧的集合 G={<V1,V3>,<V3,V4>,
<V2,V4>,<V4,V1>}
顶点集合 V={V1,V2,V3,V4 }
边的集合 E={(V1,V3),(V1,V2),
(V1,V4),(V2,V4)}
顶点 (V1,V3)与 (V3,V1)表示同一条边
V1 V3
V2 V4
权：与图的边或弧相关的数。
网：带权的图。
顶点的度：依附于该顶点的边数或弧数。
出度：（仅对有向图）以该顶点为尾的弧数。
路径：顶点 A与顶点 C之间存在一条路径。路径上边或弧的数目称为该路径的路径长度。
入度：（仅对有向图）以该顶点为头的弧数。
71
1、图的连接矩阵表示法：
2、图的邻接表示法：
1.11.2 图的存储结构
V1 V3
V2 V4
V1 V2 V3 V4
V1 0 0 1 0
V2 0 0 0 1
V3 0 0 0 1
V4 1 0 0 0
V1 V3
V2 V4
V1 V2 V3 V4
V1 0 1 1 1
V2 1 0 0 1
V3 1 0 0 0
V4 1 1 0 0
图的连接矩阵表示法
72
邻接矩阵表示法对求顶点的度很方便。
在无向图中,顶点的度数 =矩阵中对应该顶点的行 或 列中非零元素的个数。
在有向图中：
顶点的出度 =矩阵中对应该顶点的 行 中非零元素的个数。
顶点的入度 =矩阵中对应该顶点的 列 中非零元素的个数。
1.11.2 图的存储结构
V1 V3
V2 V4
V1 V3
V2 V4
V1 V2 V3 V4
V1 0 0 1 0
V2 0 0 0 1
V3 0 0 0 1
V4 1 0 0 0
V1 V2 V3 V4
V1 0 1 1 1
V2 1 0 0 1
V3 1 0 0 0
V4 1 1 0 0
入度 出度
1 1
1 1
2 1
0 1
度数
3
2
1
2
73
V1 V3
V2 V4
4
3
2
1 2
1
∧1
1
3
∧4
∧4
∧2
V1 V3
V2 V4
图的邻接表存贮法,即对图中每个顶点建立一个单链表，第 i
个单链表中的结点表示依附于该顶点 Vi的边（或弧）
1.11.2 图的存储结构
1.10.3 图的应用,图的应用非常广泛,例如：
① 用图可以表示一座城市的交通联系的情况；
② 用有值图可表示两城市间距离,车费,或航班数目 。
③ 表示城市之间建立的通讯网络
④ 可以描述化学结构式 。
⑤ 图中两点之间的最短距离问题 。
3
2
1
∧1
∧3
∧4
∧4
4
74
1.12 文件文件,是存于磁盘上的数据的集合，它不是传统意义上内存中的数据存储格式。
记录,以若干字节组成的一组数据。
1、顺序文件,是按存储的先后顺序，连续存于磁盘上的记录的集合。逻辑上顺序文件的记录是连续存储的。
2、随机文件,是以标号标记每个记录，以随序号顺序存于磁盘上的记录的集合。逻辑上随机文件的记录是不连续存储的。
75
一、录入文字,个人简历部分。 出生幼年环境，童年烂漫生活，
小学花朵时代，中学未来向往。大学远大抱负，个人特长等。
二、要求,一项为 20分，二中其它各项均为 10分。
① 文字,500个以上，在适当处加入?,?,?,?,?等 符号。
② 表格：制作不等距表元,斜线,插图,标题,求均分,绘直方图
③ 公式,编写 含有?,?、上下标、嵌套分子式的上下限积分。
④ 图片：在文本适当位置插入几个图片,使其环绕文字、作水印
⑤ 编辑：分栏,倾斜,变色,空心,加边框,底纹,沉底、组合
⑥ 艺术字：改变艺术体，旋转角度、制作二三维造型。
⑦ 自选图形：在封闭图中输入文字，改变边框、填充颜色。
⑧ 移动对象：将图形或公式插入文本框，并移位于任何位置。
⑨ 设置：纸张大小、边距，以电子邮件发往 shouz.c@nuc.edu.cn邮箱三、希望,体现个性，图文并茂，标新立异、创意无穷，让读赏心悦目、爱不释手、能择优录取，一书即成 (取得高分 )。
注,版面内容相同者均以盗板拷贝看待，成绩定为不及格。
模拟考题：自荐求职书
76
本课程作业二、将 Excel应用穿插在求职自荐书中。
1,Excel 表的应用要求：实现编辑、格式化表格，利用公式和函数对表格进行必要的统计、运算和管理，插入统计图表等主要功能。
2,PowerPoint 制作：
要求：查询 2007年以来自己感兴趣的五条新闻，并制作成演示文稿，插入在 PowerPoint的演示文稿中。主要内容：
(1).改写求职自荐书成三个幻灯片。
(2).新闻标题和详细内容有 internet的超级链接。
三、单向链表算法实现 (参考 C程序设计课本 )
完成主程序及插入、删除、改写等子程序。
书写实验报告，格式参考 C语言实验报告格式。
请于 4月 30日以前完成。书面打印提交。
77
实验是高等教育教育的组成部分，特别是工科院校更应如此：
1、预习报告,体现自己实验进程思想，作为本人实验工作指南。
内容：实验目的、实验原理、实验条件、实验内容、实验步骤、实验结果预测及实验中可能发生的问题与注意事项等。
2、结果分析报告,实验结果的分析与总结，需交教师批阅。
内容：实验过程、实验方法、实验结果、实验结论、对结果的分析、处理，及对实验内容要求、建议、意见等。
3、实验性质,操作性,验证性,分析性,设计性,综合性等实验 。
4、实验目的,提高素质、积累知识、训练方法、培养技术、
拓宽能力 (思维能力、行为能力、适应能力 )
4、实验报告书写,书写实验报告是实验教学的一部分，要求报告条理清晰、简单明了、分析透彻，避免简而不明或繁而无绪两种不良情况。一般情况写 1500字左右能阐明清楚即可。
实验报告分：
预习与分析
大学计算机 (理工科类 )
6学时授课
2
直觉思维,以天资和悟性在整体上对诸多现象直觉领悟而获得智慧
，
以公理宣告,受人推崇 。 产生人文学 。 如孔子,耶酥,诸葛亮等 。
类比思维,以事物之间存在的普遍联系而联想,比较,推理,从而达到举一反三,触类旁通 。 易形成技术 。 如前人的鲁班大师 。
形象思维,从感性上形象地反映客体的具体形状和姿态,通过意想
、
联想和想象揭示对象的本质及规律 。 如中医的脉络,气功,功夫 。
逻辑思维,在感性认识的基础上,运用概念,判断,推理对客观世界的认识过程 。 推动了科学 。 如牛顿,爱因斯坦及贝尔 ·盖慈等 。逻辑思维的低级阶段：
分析,把客观对象的整体分解为一定单元,要素,if<e>then<S>
综合,在分析基础上把单元,要素,部分的认识联系起来 。
逻辑思维的高级阶段：
归纳,通过个别实验得到科学规律的方法 。 即从现象到本质 。
演绎,通过一般规律进一步认识,解决个别问题的方法 。
逻辑思维方法正是我们中国人缺乏的思维方法,注意思维方式改变 。
程序设计中的思维方式程序设计,安排计算机操作的步骤，以逻辑思维工作、人 —机交互语言实现。应注意语言学习与思维方式改变同等重要。
3
程序设计课程特点语言,人类表达意念,交流思想的工具，由语音,词汇和语法组成。
① 机器语言,以‘ 0/1?表示数据和指令，使静态机器变成自动机
。
② 汇编语言,以符号编码数据和指令,使自动工具变成人类助手
。
③ 高级语言,以人语言表示机器操作方法 (算法 )，人教机器工作
。
④ 查询语言,以数据结构和对象方法表现主题,人命令机器工作
。
程序设计逻辑性,以,是 /否”判断多重推理,严密而清晰,需要耐心
。
二进制特殊性,0/1简单性,信息再生性,单加运算性,编码还原性 。
数据的多型性,以值 /制 /型 /位 /格组织，形成类型,存贮,逻辑结构。
运算符多样用性,算术,关系,逻辑等几十种。有结合性和优先级。
算法的灵活性,以指令与数据描述，实现操作步骤 (算法 )灵活多变
。
操作的严密性,输入,1/0”错、全错 ； 变量错结果乱 ； 程序错死机。
程序结构的自由性,面向问题自由化、过程结构化、对象系统化。
教学方法不适应性,内容多、学时短、学生习惯讲教而非引导。
解决办法,
1,加强逻辑思维训练，循序渐进，引导学生从上到下分析问题。
2,程序设计教学须长流水、不断线，不能连续十周草草结束。
4
语 言 特 点 数 据 语 句初学者语言 BASIC 简单,易学方便 使用不分类型 1,输入输出工程语言 FORTRAN 便于计算,快速 整、实、逻辑 2,赋值语句教学 语言 PASCAL 思路清晰好懂 数组,字符串 3,调用语句计算机工作者 (函数,过程语言 C 程序块 )
4,控制语句实用程序设计 选择 if else
语言 C++ 循环 for(… )
while,DO
大众化视窗语 5.辅助语句言 Visual C ++ 空,转向,中断应用查询语言
C程序设计复习程序设计语言简介语 句算式连数据言 算按步加工数环 饶结果编译连境 遇错误能提示算 符变量表达式法 有穷效行确对语 句函数结构化言 外指针构造类操作地址的低级语言以函数为基本单元数据及运算符复杂以对象为基本单元使用封装,继承,多态完成软件重组、复用利用控件资源组装文件嵌入程序实现功能增指针 (地址 )、
结构体,联合,
枚举,位域,流窗口,按钮,控件组数据,嵌编程指针,应用,枚举类,对象,事件成员 (变量,函数 )
用于管理、网络等，让计算机编程由“怎么做”变为“做什么
”？
5
算 符数据表达式法 则编码字控数语 句函数组程序言 外指针构造类数据,类型 (算法 ),存贮 (机器 )、逻辑 (算题 )
运算符,型式符号,优先级,结合性,自增减表达式,算术、关系、逻辑、条件、赋值。
数值算法,解析,判断,穷举,递推,矩阵。
字符算法,统计,排序,(添删改 )编辑,转换。
控制算法,分支,循环,跳转、交换、分类。
语句,加工数据,组成程序的基本元素。
包括表达式,函数,控制,复合,空语句 。
函数,完成具体功能，程序的基本单元。
包括函数头,函数参数,函数体,返回值 。
程序,文件组成,编译运行,预定义,调函数指针,可指向变量,数组,函数,结构体的地址结构体,不同类相关数据集合 。 联合,枚举等
C 语言复习一、程序设计概念
6
细化题义定函数安排数据逻类贮确定算法基数符加工编码算式句主函数 (输入,调用,输出 )
函 函数,类,名,(参数 )
自定义 函数体 (变量,语句 )
数 返回值 (数组名,指针 )
库函数 (包含、功能、返回 )
C程序设计复习二,C程序 设计方法解析,穷举转换，递推比较，转换排序，查找迭代，积分基本：
算 字符
,法数值：
输入 /出,控制,中间数据常 /变量、局 /全域整 (长短 )、实 (单双 )
字符 (字串 )、数组结构,联合,指针,位域动,静,内,外,寄存,位逻辑结构数类型结构据存贮结构
+/-/*/除 /与
/或 /非 /大小 /等数据 +算符 +数算 /逻 /条 /逗 /位表达式,空语句复合,函数调用条件开关控制 循环辅助运算符表达式语句编码
7
值确定的常量与变量 。 如,3,-2.13,2.5e-4,PI等 。
值变化的量。用前定义,确定地址,分配单元 。
short int a,score[n];
long as a[n];
单精度,float c,ax[n];
double d,max[n];
字符,char c,sa=?a?;
字串,char a[n]=“student”
C 语言复习三、数据类型运算中自动转换
int?char,short
Unsigned? 必然
long?按需
double? float
数 有整实字串型据 守补码占内存结 合题意想逻辑构 造新类与指针同类数据集合。一维与多维。
多维可按行列顺序使用。如,a[N];b{m][n];
不同类型的相关数集合。如：姓名、性别、年龄等占用同一存贮单元的不同类型相关数据集合 。如职业等。
用于存放地址的变量。按地址操作程序紧凑快捷。
值 存补码型不同位 出值入保精度型符制 算自转换格 式转义修饰符
00-00 0 0
00-01 1 2
：,,
01-11 127 127
10-00 128 -126
:,,
11-10 254 -2
11-11 255 -1
字节存贮数据：常值：
变量：
整型：短整：
基 长整：
本 实型：
型 双精度：
字符型：
构 数组：
造型 结构：
联合：
指针型：
8
外部变量：
作 局部变量,
用域 全局变量：
动态变量,
存贮 静态变量：
类寄存器变量：
C 语言复习四、简单变量即全局变量，定义在本文件之外，用 extern引用。
在定义范围内有效 。 如函数,复合语句内。
1,auto 型 (省略时隐含 )。 2,静态局部型 3,寄存器型。
定义在函数外 (即外部变量 )，
在函数或程序块内 auto(可省 ),用时分配地址用完回收。如：局部、寄存器、形参。
static 编译时分配地址，程序结束回收。
1,内部 (局部 )静态。 static int a,b
2,外部 (全局 )静态。 static int a,b
register 设的定在 CPU或主板中的变量。
数据在内存、运行速度快。如,register int
变量,计算机中有名子的存贮单元。代替固定类型的数据，
其存贮方式 (存贮结构 )直接影响着计算机的运行速度 。
9
1、小故事 1,千年虫”问题？
当 2000年新年钟声即将敲响，亿万人们在企盼新的千年会给他们带来好运的时刻，有些人却难以高兴起来。因为“千年虫”可能给他的事业带来难以预料的损失，因百年时间可能为零、飞机难以降落等。
2、小故事 2,啤酒”和“尿布”的故事
：
年轻的爸爸在购买尿布之余，总是忘不了给自己带上几罐啤酒。百货公司将原本放在两处的啤酒和尿布集中一起摆放，还提供包括啤酒和尿布在内的日用杂货，结果销售额大增。
1.1 数据结构基本概念
10
启示
1、类似以上的故事情况早有发生，启发我们：
① 数据在内存中占有一定的空间，如何组织它们？
② 许多数据之间是孤立、离散的，但也可能在数据之间具有明显的一定关系，需要管理；
③ 有许多数据具有隐藏在深处的关系，需要挖掘 。
2、研究数据的三个工具：
① 程序设计人员要熟悉数据结构。
② 软件应用人员利用数据库可以动态管理数据。
③ 高层管理人员利用数据仓库可以获得决策支持
3,数据结构,指数据与数据间相互关系。包括数据类型结构、数据存贮 (逻辑 )结构和对数据的操作。即研究计算机中放置二进制数据及符号的方法。以便快速运行。
1.1 数据结构基本概念
11
④ 数据对象,某种数据类型元素的集合,即一类数据例如，整数的数据对象是 {… -3,-2,-1,0,1,2,3 …
英文字符类型的数据对象是 {A,B,C,…,±,⊙,★,… }
4、数据结构中常用术语：
① 数据,是对客观事物的描述、是信息的载体，能被计算机加工、处理的数字和符号集合。
② 数据元素,是数据的基本单位，可包含若干数据项、也称为记录。由记录组成的线性表称为文件。
③ 数据项,具有独立意义的最小数据单位,即数值 。
1.1 数据结构基本概念学 号 姓 名 性 别 政治面貌 马 列 高 数 英 语 计算机
0709101 张三 男 团员 85 90 85 90
0709101 李四 女 党员 90 87 90 78
0709101 王五 男 群众 76 86 80 69
… … … … 表中一行或一列均为一个数据元素 … … … …
12
5,数据逻辑结构,数据间相互关系，分为：
① 集合结构 数据元素除了同属于一种类型外，别无其它关系。
② 线性结构,数据元素之间存在一对一的关系。
③ 树型结构,结构中数据元素间存在一对多的关系。
④ 图状 (网状 )结构,数据元素之间存在多对多的关系。
6、数据结构的表示方法,即数据的存贮方式 。
① 顺序存储结构,用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
② 链式存储结构,在每一个数据元素中增加一个存放地址的指针,用此指针来表示数据元素之间的逻辑关系。
1.1 数据结构基本概念
13
数据 (存贮 )结构不同于数据类型,也不同于数据对象,它不仅要描述数据类型的数据对象，而且要描述数数据对象各元素之间的相互关系。
1.1 数据结构基本概念数 型表栈队树图据 题算法时空度结 合取存要快速构 造顺序与链存例：履历表的数据结构定义如下,S=(C,R)
其中,C 是含若干个项目，如年龄、职业、填表日期等的集合 ﹛ C1,C2,Cn ﹜,
R={P},P 是定义在集合上的一种关系
{<C1,C2>},如，年龄与出生年月日有关。
7、数据结构的形式定义,数据结构是数据存贮逻辑结构、由二元组成：数据 -结构 =(D,S)
其中,D 是数据元素的有限集，
S 是 D 上关系的有限集。
14
8,数据的运算,数据运算定义在数据逻辑结构上的操作,但运算的具体实现要在存贮结构上进行 。
数据运算对数据结构是非常重要,各种逻辑结构有相应的各种运算要求 。 常用的几种运算为：
① 插入,向数据结构里加入新的节点 。
② 删除,把指定的节点从数据结构里去掉 。
③ 查找,在数据结构里找寻满足一定条件的节点 。
④ 替换,改指定节点一个域或多个域的值 。
⑤ 排序,在线性结构中保证节点数不变的情况下,
按某种指定的顺序排列 。 它是用量最大是算法
1.1 数据结构基本概念
15
1.2 算法分析与设计
1、算法 (Algorithm),对特定问题求解步骤的一种描述。 如、查找元素的二分法。
算法是指令的有限序列,其中每一条指令表示一个或多个操作。如两个变量交换数据,swap a,b
2、算法的五个重要特性：
1),有穷性,一个算法必须在执行有限次后结束,每步定时
2),确定性,每条指令必须有确定含义,不能有二义性。
3),可行性,算法描述的执行步骤必须在计算机上可行 。
4),输入,一个算法按功能应有零个或多个输入。
5),输出,算法执行结束要有结果输出或产生相应动作。
算 值设计结构类法 有穷效行确对分 解表树队栈串析 剖计量操作序
a b
c①
②
③
16
1.2 算法分析与设计
3、算法的正确性,只有保证正确的解算结果，才能讨论算法的好坏。如：设计一个求三角形面积的算法，给定三角形的三条边分别为 a,b,c,求面积 area的简单算法为：
step1 read(a,b,c)
step2 S:=(a+b+c)/2
step3 area=sqrt(s*(s-a)*(s-b)*(s-c))
step4 write(area)
应从以下几个方面考虑：
① 数学原理正确吗？三角形的两边之和应大于第三边?
② 解题条件正确吗？边常能为负数？，能否开平方？
③ 执行路径合理吗？程序 (调函数 )中常有判断转移,对？
显然、该题上机运行后有时正确、有时错误，甚至死机。为什么？
a
b c
17
1.2 算法分析与设计
3、算法的正确性：,正确,的含义在通常的用法中有很大的差别 (不严密 )，大体可分为以下四个层次,① 程序可运行,程序不含语法错误；可用于运行。
② 结果也正确,对几组输入数据能得出满足要求的结果
③ 条件下正确,程序对一切合法的输入数据都能产生满足规格说明要求的结果。符合程序功能的基本要求。
④ 完全正确,对于精心选择的典型、苛刻而带有刁难性的数据能够得出满足规格说明要求的结果；由测试完成。
最简单和最直接的算法往往不是最有效的，但算法的简单使得证明其正确比较容易，同时便于编写、修改、阅读和调试，所以应强调简洁。但对经常使用的算法来说,高效率 (减少运行时间和压缩存储空间 )比简单性更为重要。
18
4,时间复杂性分析,何达到高效? 省时省内存 。
学习时间复杂度意义,时间复杂性能给出算题运算需要的估计时间,相应计算机的解题时间及如何选择计算机 。
① 时间频度,一个算法中的语句执行次数称为语句频度或时间频度 。 其实质是在一个循环中找关键操作 。
执行一个算法所耗费的时间,理论上难以计算,须上机运行测试 。 但实际不能也不必,只需知道各算法的花费时间 。 同时一个算法花费的时间与算法中语句的执行次数成正比例 。 记为 T(n)。 如 下列算法段的语句频度：
1.2 算法分析与设计
for(i=1; i<=n; i++)
for(j =1; j <=i ; j++)
x=x+1;
分析：该算法为一个二重循环,执行次数为内外循环次数相乘,但内循环次数不固定,与外循环有关,因些,时间频度 T(n)=1+2+3+… +n=
2 )1(?nn
19
4,时间复杂性分析：
② 算法的时间复杂度,算法中实现基本操作的语句 (基本语句 )重复执行的次数 f(n),称为算法的频度 。
记作,T(n)=O(f(n)) 随问题规模 n的增大，算法的频度 T(n)和重复次数 f(n)的增长率同阶。
例 1,x+=5; 单个语句频度为 1，则 程序段的时间复杂度为 T(n)=O(1)。
1.2 算法分析与设计例 2,for (i=1; i<=n; ++i) /* n+1 */
for (j=1; j<=n; ++j) /* n(n+1) */
c [i][j]=0; /* n2 */
共执行,T(n)=2n2+2n+1 当 n充分大时 T(n)与 n2是同阶的。该算法时间复杂度为,T(n)=O(n2)
20
4,时间复杂性分析,② 时间复杂度
1),O(n2)复杂度,在 时间频度中,n称为问题的规模,
当 n不断变化时,时间频度 T(n)也会不断变化 。 要知道变化规律,引入时间复杂度概念 。
1.2 算法分析与设计例如,若 T(n)=n(n+1)/2,则有 1/4≤T(n)/n2≤1/2,故它的时间复杂度为Ｏ (n2),即Ｔ (n)与 n2 数量级相同 。
设 T(n)的一个辅助函数为 g(n),定义为当 n大于等于某一足够大的正整数 n0时,存在两个正的常数 A和 B（ 其中
A≤B）,使得 A≤T(n)/g(n)≤B均成立,则称 g(n)是 T(n)的同数量级函数 。 把 T(n)表示成数量级的形式为：
T(n)=Ｏ (g(n)),其中大写Ｏ为 Order(次 /阶 /序 /量 /级 )的首字母 。
21
4,时间复杂性分析,② 时间复杂度
2),O(n3)复杂度,分析该算法段的时间频度及时间复杂度：
1.2 算法分析与设计
for（ i=1;i<=n;i++）
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k; =
= = +
= [ + ]
n
k
k
1
)...321(
n
k
kk
1
2
)1(?
n
k
k
1
2[
2
1?
n
k
k
1
]
2
1
6
)12)(1( nnn
2
)1(?nn
由于有 1/6 ≤ T（ n)/ n3 ≤1，
故,时间复杂度为Ｏ (n3)。
分析算法规律可知 时间频度
T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)
i 变化范围,j变化一段,K改变值
i
=
1
2
…
↓
n k=1,2 … →j
… … …∶
∶
22
4,时间复杂性分析,② 时间复杂度
3),O(log2N)复杂度,对于二分发查找一个数,粗略的可以看作,每经过一次关键码比较,则将查找范围缩小一半,
因此经过 [log2n]次比较就可完成查找过程,因此表示为：
T(n)=O(log2n)
1.2 算法分析与设计
I J K L MHGFEDCBA
①
②③
④
4),O(nlog2N)复杂度,对于快速排序,归并排序,堆排序,均可看成 T(n)=N(nlog2N),显然其运算量：
大于 O(log2N) 而小于 N2。
23
1.2 算法分析与设计
4,时间复杂性分析：
② 时间复杂度 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为 O(1),另外,在具体的时间频度不相同时,时间复杂度却有可能相同,如
T(n)=n2+3n+4与 T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为 O(n2)。
时间复杂度按数量级递增排列,常见的时间复杂度有：
常数阶 O(1),对数阶 O(log2n),线性阶 O(n),
线性对数阶 O(nlog2n),平方阶 O(n2),立方阶 O(n3),...，
k次方阶 O(nk),指数阶 O(2n)。 随着问题规模 n的不断增大,
上述时间复杂度不断增大,算法的执行效率越低 。
24
1.2 算法分析与设计
4、时间复杂性分析,如当计算机操作为 1ms/次、即 1000次 /秒。
算法类时 间复杂度可解问题最大长度 (n) 计算机速度对解题长度影响
1秒钟 n 1分钟 1 小时 提高前 提高 10倍 对应算法
A1 O(n) 1000 60000 3.6× 106 s1 10s1 顺序,分支
A2 (nlog2n) 140 4893 2.0× 105 s2 7.2s2 排序,查找
A3 O(n2) 31.6 245 1897 s3 3.16s3 循环,排序
A4 O(n3) 10 39 153.3 s4 2.15s4 三重循环
A5 O(2n) 9.9 15.8 21.7 s5 s5+3.3 穷举,遍历
5、大 O表示法加法规则,当两个并列的程序段时间代价分别为 T1(n)=O(f(n))和 T2(m)=O(g(m))时，其连在一起的时间代价为,T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))
显然,C<log2n<n<nlog2n<n2<n3<2n<n!
当,A2算法在 1秒内可完成问题长度为 n=140的算题 (由 nlog2n=1000)。
25
6,空间复杂度,与时间复杂度类似,指算法在计算机内执行时所占用的内存开销规模 (称为空间频度 ),一般所讨论的是除正常占用内存开销外的辅助存储单元规模 。
1.2 算法分析与设计
① 程序运行所需的存贮空间包括两部分：
固定部分,如指令代码,常数,简单变量定长变量
(数组,结构,变量 ),对这些静态空间只需统计即可 。
可变部分,与问题规模有关成分所占空间,如引用变量,递归栈,运行中 new,delete命令动态使用空间 。
② 空间复杂度表示,应分析一个程序实际占用存贮空间,主要是完成问题 n过程中不断占用 ---释放 ---占用的瞬时渐进最大空间 。 而不是指令,常数,指针及输入数据占用空间,主要是解算问题所需的辅助空间 。 空间复杂度可表示为,S(n)=O(f(n))
26
1.3 线性表
1,线性表,线性表是 n(n≥0) 个元素的有限序列，它们之间的关系可以排成一个线性序列：
a1,a2,……,ai,……,an
其中,n称作表的长度,当 n=0时,称作空表 。
2,除首尾两个数据元素之外，其它数据元素有且仅有一个前驱和一个后继。第一个数据元素无前驱,最后一个数据元素无后继。
2、线性表的特点：
1,线性表中所有元素的性质相同。如数组，它就是一个线性表。
3,数据元素在表中的位置只取决于它自身的序号。
假设线性表中的第一个数据元素的存储地址为 Loc(a0)，
每一个数据元素占 d字节，则线性表中第 i个元素 ai在计算机存储空间中的存储地址为,Loc(ai)= Loc(a0)+id
27
1.3 线性表例 3 学生健康情况登记表,每一 行或列都是线性表,但其内部元素的数据类型不同而有规律。
姓名 学 号 性别 年龄 健康情况王小林 790631 男 18 健康陈红 790632 女 20 一般刘建平 790633 男 21 健康张立立 790634 男 17 神经衰弱
…,.,…,.,… … … … … …
3、线性表举例,
例一,26个英文字母的字母表 (A,B,C?,Z ）
例二、某校从 1981 年到 1986 年各种型号的计算机拥有量的变化情况。 ( 1,17,28,50,92,188 ）
28
1.3 线性表4、线性表的特征：
① 非空的线性表,有且仅有一个开始结点 a1,它没有直接前趋 (向左 ),而仅有一个直接后继 (向右 ) a2 ；
② 终端结点,有且仅有一个终端结点，该结点再没有直接后继，而仅有一个直接前趋 a n-1 ；
③ 其余的内部结点 ai(2 ≦ i ≦ n-1)； 它们 都有且仅有一个直接前趋 a i-1 和一个直接后继 a i+1 。
④ 元素间为一对一线性关系 。 即 ai是一个字,字母或记录对应的逻辑结构图如图所示。
a1 a2 … an
结论,线性表是一种典型的线性结构,用二元组表示为：
linear_list=(A,R) 其中,A={ai |1≤i≤n,n≥0,ai∈ elemtype}
注,elemtype为类型设定 R={r} r={<ai,ai+1> ∣ 1≤i≤n-1}
29
5、线性表算法,常见线性表的运算有：
1,置空表,SETNULL（ &L） 将线性表 L置成空表
2,求长度,LENGTH（ L） 求给定线性表 L的长度
3,取元素,GET（ L,i） 若 1≤i≤length(L),则取第 i个位置上的元素,否则取得的元素为 NULL。
4,求直接前趋,PRI0R（ L,X） 求线性表 L中元素值为 X
的直接前趋,若 X为第一个元素,前驱为 NULL。
1.3 线性表
5.求直接后继,NEXT（ L,X） 求线性表 L中元素值为 X
直接后继,若 X为最后一个元素,后继为 NULL。
6,插入,INSERT（ &L,X,i） 在线性表 L中第 i个位置上插入值为 X的元素 。
7,删除,DELETE（ &L,i） 删除线性表 L中第 i个位置上的元素 。
30
一个线性表 L定义为 L=(a1,a2,…,an),当 L=（ ） 时定义为一个空表,其操作为,
void setnull(&L) //将线性表 L置成空表
int Length(L) //求给定线性表 L的长度
elemtype Get(L,i) //取线性表 L第 i个位置上的元素
1.3 线性表
6、线性表数据类型描述例二,假设线性表 L=(23,56,89,76,18),i=3,x=56,y=88,则对 L的一组操作及结果如下：
Length(L);
Get(L,i)
Prior(L,x)
Next(L,x)
Locate(L,x)
Insert(&L,y,i)
Delete(&L,i+1)
// 所得结果为 5
// 所得结果为 89
// 所得结果为 23
// 所得结果为 89
// 定位,所得结果为 2
// 所得结果为 (23,56,88,89,76,18)
// 所得结果为 (23,56,88,76,18)
31
7、顺序表定义：
C语言描述顺序存储结构下的线性表
(顺序表 )如下：
#define TRUE 1
#define FALSE 0
#define MAXNUM <顺序表最大元素数 >
Elemtype List[MAXNUM] ; /*顺序表 List*/
int num=-1; /*当前数据元素下标，并初始化 */
1.3 线性表也可将数组和表长封装在一个结构体中：
struct Linear_list {
Elemtype List[MAXNUM]; /*定义数组域 */
int length; /*定义表长域 */
}
设,LOC(a1)是线性表第一个数据元素的存储位置,通常称做线性表的起始位置或基地址。 LOC(ai)=LOC(a1)+(i-1)*l
LOC(ai+1)=LOC(ai)+l
存储地址内存排列 位置序号
0
1
2
…
i
…
n
…
maxlen-1
b
b+d
…
…
b+(n-1)× d
顺序存储结构示意图
X
a1
a2
…
ai
…
an
…
b+(i-1)d
32
① 顺序表的插入算法,在顺序表 List[ ]中，当表尾元素为 *num位置，在第 i个元素前插入数据元素 x。
int Insert(Elemtype List[ ],int *num,int i,Elemtype x)
{
int j;
if (i<0||i>*num+1)
{ printf(“Error!”) ; return FALSE;} /*插入位置出错 */
if (*num>=MAXNUM-1) /* MAXNUM 内存最大空间 */
{ printf(“overflow!”); return FALSE;} /*表已满 */｝
for (j=*num;j>=i;j--)
List[j+1]=List[j]; /*数据元素后移 */
List[i]=x; /*插入 x*/
(*num)++; /*长度加 1*/
return TRUE;
}
1.3 线性表
8、顺序线性表运算：
33
int Delete(Elemtype List[],int *num,int i)
{ int j;
if(i<0||i>*num)
{ printf(“Error!”); return FALSE;} /* 删除位置出错 */
for(j=i+1;j<=*num;j++)
List[j-1]=List[j]; /* 数据元素前移 */
(*num)--; /* 长度减 1。 注意与 *num- -的区别 */
return TRUE;
}
② 顺序表的删除算法,在线性表 List[]中,*num为表尾元素下标位置，删除第 i个元素，线性表的元素减 1，
若成功，则返回 TRUE；否则返回 FALSE。
1.3 线性表
8、顺序线性表运算：
34
从上述两个算法看很显然，在线性表的顺序存储结构中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上 。 而移动元素的次数取决于插入或删除元素的位置 。
假设 Pi是在第 i个元素之前 插入一个元素的概率 (由题目确定 )，则在长度为 n的线性表中插入一个元素时所需的移动次数为：
)(
0
inpE
n
i
ii n s
9、线性表 算法分析 1.3 线性表
1
1
np i
2
)(
1
1
0
nin
n
E
n
i
i n s
则 移动的平均次数为,
如果在线性表 任何位置插 入 或删除元素的概率相等 (移 n插 1)，即：
35
如果在线性表的 任何位置 插入或删除元素的概率相等，即：
)1(
1
0
inqE
n
i
id e l
nq i
1?
9、线性表 算法分析
1.3 线性表假设 qi是删除第 i个元素的概率，则在长度为 n的线性表中删除 一个元素 时所需移动元素次数的平均次数为：
则平均移动次数为,2 1)1(1 1
0
nin
n
E
n
i
d e l
可见，在顺序存储结构的线性表中插入或删除一个元素时，平均要移动表中大约一半的数据元素。
它的时间复杂度为Ｏ (n),即Ｔ (n)与 n 数量级相同。
36
小结,线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出,因此顺序存储结构的线性表是可以随机存取其中的任意元素 。 同时也有较高的存贮效率 。
但是,顺序存储结构也有不便之处,主要表现在：
1.3 线性表
（ 1） 数据元素最大个数需预先确定,使得高级程序设计语言编译系统需预先分配相应的存储空间；
（ 2） 插入与删除运算的效率很低 。 为了保持线性表中的数据元素顺序,在插入操作和删除操作时需移动大量数据 。 对于插入和删除操作频繁的线性表,将导致系统的运行速度难以提高 。
（ 3） 存储空间不便于扩充 。 当一个线性表分配顺序存储空间后,若线性表的存储空间已满,但还需要插入新的元素,则会发生,上溢,错误 。 并不能利用内存碎片 。
37
1.4 线性链表链表,用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位碎片。
pointdata pointdata pointdata… …
因此,链表中结点的逻辑次序和物理次序不一定相同 。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址 (位置 )信息，这个信息称为指针 (point)
或链 (link)。 结点值 (数据 )和指针 组成了链表中的结点结构。
38
data point1.4 线性链表显然，单链表中每个结点的存储地址是存放在其前趋结点下个域中，而开始结点无前趋，故应设头指针 head 指向开始结点,同时，由于终端结点无后继，故终端结点的指针域为空，即 Null。
其中,data是数据域,用来存放结点的值,
point是指针域 (亦称链域 )，用来存放结点的直接后继的地址 (或位置 )。由于上述链表的每一个结点只有一个 链域,故将这种链表称为单链表。
问图中的字母顺序？
链域数域
39
…..
a2
a1
an
…..
ai+1
ai
0
1
i-1
i
n-
1
① 在数组中插入运算,插入运算应先作安全性检查,再后移插入 。
实现顺序表插入元素的主函数
viod main( )
{ int M=10;n=6; /*M是数组的大小,n是表中已有元素个数,即表长 */
int result,k;
static int V[10]={3,5,7,10,8,6}; /*数组赋初值 */
result=insq(4,25,V,10,&n); /*执行函数调用,在第 4个元素前插入 25*/
if ( resul t= 1) { printf ("success ! \n");
for (k=0; k<n; k++) printf ("%d",V[k]);}
else printf("failure!");
}
1,顺序表运算 1.4 线性链表插入操作
a1head a2 a3 a4 an Nulla…
运算结果,3 5 7 25 10 8 6
X 5
X
40
int insq(int i,int x,int V[ ],int M,int *p） / *顺序表插入子函数 */
{ int n,j,/*在线性表 V中第 i个元素之前插入 X,i的合法值为 1?i?n */
n=*p; / *获取表长,p是指向存储表长的指针变量 */
if（ n==M) / *M是存储空间的大小 */
{ printf(“overflow\n”); return (0);} /*数组空间 M≤表长难插 */
if((i<1)‖ (i>n+1))
{ printf(“iis error \n”); return (0);} /*i值大小越界不合法 */
else { for (j=n; j>=i; j- -) V[j]=V[j-1]; /*插入位置后的元素依次右移 */
V[j-1]=x; /*插入 x */
p=++n; /*表长加 1,由 p返回 */
return (1); /* 1作为运行标志 */
}
}
注意数组元素从 0开始,I为 1存放在 V(0)
② 插入函数,主函数调用 result=insq(4,25,V,10,&n);
数组大小 10。 且有 4个元素,要求把 25插入到第 4个元素前
1.4 线性链表插入操作
3head 5 7 10 an Null
1,顺序表运算
X
25
41
…..
a2
a1
an
…..
ai+1
ai
0
1
i-1
i
n-1
③ 找内存单元插入原理：
对链表 L在在内存寻找 S处,后再插入 X，
2,链表运算 1.4 线性链表
(b)申请新结点 s,数据域置 x,s->data=x；
(a)寻找内存插入位置 S,并 强制链表类型
s=(LNode *)malloc(sizeof(LNode));
(c)修改指针域，将新结点 s插入：
s->next=q->next
q->next=s
关键语句：
head q
a1 a2 a3 a4
an Nulla…
pvoid Inselem(LinkList L,int i,int x){ LNode *p,*q,*s;
int pos=1;/*移动量
p=L;
if(i<1 || i>Getlen(L)+1) exit(1);
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
while(pos<=i)
{ q=p;p=p->next;
pos++;
}
s->next=q->next;
q->next=s;
}
X 5
XS
42
(b)返回被删除结点数据 x
(a)找到删除位置 p：
x=p->data；
(c)修改指针域，将结点 p删除关键语句
q->next=p->next；
free(p)；
④ 删除原理 delelem(L,i)的实现：
删除链表 L中第 i个元素,
2,链表运算 1.4 线性链表
a1
head
a2 a3 an Nulla…
q
a4
p
void Delelem(LinkList L,int i)
{ int pos=1; /* 位置记数器 */
LNode *q=L,*p; /*连接断开点
if(i<1||i>Getlen(L)) exit(1);
while(pos<i) /* 从第一点开始
{ q=q->next; /* 逐点查找
pos++; /*增加位置
}
p=q->next; /*找见位置
q->next=p->next; /* 重新连接
free(p); /*释放断开点
…X
43
⑤ 建立随机存贮链表,
建立一个学生姓名、成绩链表,通过 main()函数调用 main()
{ creat();
}
1,顺序表运算
1.4 线性链表
#define NULL 0
#define LEN
sizeof(struct student)
Struct student
{ long num;
float score;
struct studnt *next;
};
int n; /*全局变量供各函数 */
/*定义返回链表指针的函数 */
Struct student *creat(void)/*无形参直调用
{ struct student *head,*p,*q;
n=0; /*下面开辟一个新单元 */
p=q=( struct student *) malloc (LEN);
scanf(“%ld,%f”,&p ->num,&p->score);
head=NULL; /*头暂指向空，后面再赋值
while(p->num != 0)
{ n=n+1; /* 数据结点个数 */
if(n==1) head = p; /*p指向新开结点
else q->next=p; /*q指向最后结点
q=p;
p=(struct student*)malloc(LEN);/*新开
scanf(“%ld,%f,,&p->num,&p->score);
}
q->next=NULL; /*最后开辟结点为空未使用
retrn(head); /*返回链表起始地址。
}
num score next num score null
q 链表最后结点 P 链表新开结点head
44
1,顺序表运算
1.4 线性链表
⑥ 输出链表,先找见链表头 head地址，后移动指针变量 P，输出指向结点，再移动输出，直到连接终点 NULL：
Void print(struct student *head) /*链表头由实参传递
(struct student *p; /* 定义结构体元素指针
print(,\nNow,These %d records are:\n”,n);
p=head;
If (head != MULL) do
{ printf(“%ld %5.1 \n”,p ->num,p->score)；
p=p->next;
} while(p != NULL);
}
001 002 001head 001
NULL
P 指向打印 P 指向打印 P 指向打印 P 指向打印注意,为了辟免删除链表第一元素影响表头，链表通常第一结点不存贮元素，仅作链表表头使用。
45
Struct student *del(stuct student *head,long num)
{ struct student *p,*q;
if(head==NULL)printf(,\nlist null!\n”);return (head);)
p = head;
while (num != p->num && p->next !=NULL) /*未找到且还有 */
{ q=p,p=p->next;}
if (num ==p->num )
{ if (p == head )head=p->next; /*若找到头，第二地址给头
else q->next = p->next; /*将下一个地址给前一个地址
printf(“delete,%ld \n”,num;
n=n-1;
}
else printf(“%ld not been foud! \n”,num); /* 找完也未找到 */
return(head);
}
1,顺序表运算
1.4 线性链表
⑦ 删除链表一个元素：
从头开始逐渐查找，找到断开连接，并释放内存。
ai anai+1
删除操作
a
P已查结点 新找结点q已查结点 q P找到结点
46
P1
1,顺序表运算
1.4 线性链表
⑧ 寻找内存在链表中插入元素：
Struct student *insert( /* 顺序链表
struct student *head,struct student *stud)
{ struct student *p0,*p1,*p2; /*在 p2点后插
p1=head; p0=stud; /* p1检查点,p0为插入点
if(head==NULL){ head=p0,p0->next=NULL;}/*插空表
else /*从头到终逐个检查 P1结点,p0>p1向后 /P0<p1向前，从小到大插入
002 003 00n
NULL
002
P0
001head
p2 P1 P1p2
{ while((p0->num>p1->num)&&(p1->next != NULL))
{ p2=p1;p1=p1->next; } /*p0插入值大于检查点 p1，后移
if(p0->num<p1->num)/*p0插入值小于检查点 p1，插到 p1前
{if(head==p1)head=p0 else p2->next=p0;插头或插 p2后
p0->next =p1; } /*检查点紧跟新插点
else { p1->next = p0;p0->next = NULL; } /* 插到 p1后
}
n = n+1; /* 链表数据项数 +1
return(head)} /* 返回链表头
}
47
1.5 循环链表循环链表是一种头尾相接的链表其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活 。 有 单循环链表 和 双循环链表循环链表可以从表内任意位置开始插入或删除元素，而不仅是头结点，并要循环一圈或限制结束。
1、单循环链表,将终端结点的指针域改为指向表头结点或开始结点，就得到单链形式的循环链表，简称为单循环链表。为 使空表和非空表的处理一致,循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。
48
2、双循环链表,每个结点包括一个一个数据区和两个指针区，一个前项指针和一个反向指针。前向指针指向直接的前趋接点，反向指针指向其直接后继结点。这样每次处理结点时都可以从当前结点出发向前或向后查找。
1.5 循环链表
n a1 a2 an…head
a … ana1 a2head
为处理一致留出头结点
49
1.5 循环链表
3,静态链表,有些高级程序设计语言中没有指针类型,
这可以通过定义一个结构体数组实现类似于,链表,结构的形式,即为数组中每一个元素附加一个链接指针,从而形成静态链表结构 。 实际上它在不改变各元素物理位置基础上,通过重新链接就能够改变数组元素逻辑顺序 。 数组元素以记录形式构成 。 由于它是利用数组定义的,在整个运算过程中存储空间的大小不会发生变化,因此称这种结构为静态链表 。 设存放静态链表的数组 struct[MaxSize]
的定义如下,#define MaxSize 100
typedef struct
{ ElemType data;
int next;
}SNode; //结点类型
50
1.5 循环链表
4、动态链表,在程序执行过程中可从无到有的建立一个链表，即按使用开辟结点，输入各结点数据，并建立起前后的链接关系。从而避免了数组在使用前必须先定义固定的长度，以便在内存中临时分配空间，对于事前难以确定大小时，避免把数据空间定得足够大而浪费空间的弊端。
显然,各种存贮结构各有优缺点，使用中应根据实际应用需求选用适宜的存贮结构。
5,链表特点,链式存贮虽然比顺序存贮多占用一些指针空间，但存贮中的碎片可得到充分利用。删除后的结点也都能串接到一个链上，等待重新使用。 链式存取只能顺序存取，不能随机存取。对插入和删除操作，则利用链接存贮比较方便，无需移动元素 。
51
复习：选择填表例一,数据结构反映了数据元素之间的关系，链表是一种 (A),它对数据元素的插入和删除 (B)。
A,① 顺序存贮线性表。 ② 非顺序存贮非线性表。
③ 顺序存贮非线性表。 ④ 非顺序存贮线性表。
B,① 不需移动结点，不需改变指针 ② 不需移动结点，只需改变指针。
③ 只需移动结点，不需改变指针。 ④ 既需移动结点，又需改变指针。
1.5 循环链表通常查找线性表数据的方法有 (C)和 (D)两种方法，其中 (C)是一种适合已排顺序存贮结构但 (E)的方法，而 (D)
是一种对顺序及链式存贮结构均适应的方法。
C,① 顺序查找。② 循环查找。③ 条件查找。④ 二分查找。
D,① 顺序查找。② 随机查找。③ 二分查找。④ 分块查找。
E,① 效率较低的线性查找。 ② 效率较低的非线性查找。
③ 效率较高的非线性查找。④ 效率较高的线性查找。
√
√
√
√
√
52
复习：选择填表例二,线性表具有顺序和链接两种存贮方式，现有一个五元素的线性表 L={23,17,47,05,31},若它以链接方式存贮在下列 100～ 119号地址空间中，每个结点由数据 (占两字节 )和指针 (占两字节 )组成，其指针 X,Y,Z的值分别为
(A),(B),(C).
按上述连接方式存贮时，该线性表的首结点的起点地址为 (D),末结点的起始地址为 (E)。
供选择的答案,A～ E：
① 100 ② 104 ③ 108 ④ 112 ⑤ 116
⑥ 118 ⑦ NUll ⑧ 102 ⑨ 106 ⑩ 110
1.5 循环链表
⑤
③ ④
⑦ ①
104 108 112 116
Z47Y31V23X17U05
100 119
53
1.6 栈例,一叠书或一叠盘子。栈的抽象数据类型的定义如左,
假设栈 S=(a1,a2,a3,… )，
则 a1称为栈底元素,an为栈顶，栈中元素按 a1,a2,a3,… 的次序进栈，退栈的第一个元素应为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（ LIFO ）。
1,栈 (stack) 是限制只能在表的一端进行插入和删除运算的线性表，通常称插入,删除的这一端为栈顶 (顶端 )
，另一端为栈底 (底部 ) 当表中没有元素时称为空栈。
a1
a2
a n-1
a n
…
…
栈顶栈底 bottom
Top
54
1.6 栈
2、顺序栈 栈是一种运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表，因此可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量 top表示顶。
3、链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行，
由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。
55
1.6 栈
4、栈的应用,用一个数组 S(m)可实现栈的顺序存贮结构，数据入栈依次存入 S[0]S[1],
…,栈顶指针 top指向栈顶元素 S[top]，
top<0 表示栈空,top>=M表示栈上溢。
① 元素 x进栈操作：
S[0]
S[1]
∶
S[top]
∶
S[M-1]
T0p
if (top = M-1) {printf(“stack is full\n”; return (0); } /* 栈满返回 0*/
top ++; /* top 指针上移一个位置 */
S[top] =x ; /* x进栈 */
return (1); /* 进栈成功，返回 1 */
② 从栈弹出过程：
if (top<0) {printf (“stack is empty \n”),return (0);} /* 栈空返回 0 */
x = s[top]; /* 取出栈顶元素 */
Top --; /* Top指针移下一位置 */
return (x); /* 出栈成功，返回栈顶元素 */
56
结论,后进先出 (Last In First Out)，简称为 LIFO线性表。
举例 1：家里吃饭的碗，通常在洗干净后一个一个地在一起存放，在使用时，若一个一个地拿，一定最先拿取最上面的那只碗，而最后拿出最下面的那只碗。
举例 2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
显然、在描述括号运算的数据结构中，大中小 {[( )]}的运送顺序就是一个栈的操作。
1.6 栈栈结构的基本操作,
（ 1）初始化栈 InitStack(S) （ 2）判断栈是否为空 StackEmpty(S)
（ 3）入栈 Push(S,item) （ 4）出栈 Pop(S,item)
（ 5）获取栈顶元素内容 GetTop(S,item)
57
1.7 队列队列 (Queue) 也是一种运算受限的线性表它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头 (Front),允许插入的一端称为队尾 (Rear)。
例如：排队购物时的队列操作系统中的作业排队。由于先进入队列的成员总是先离开队列，因此队列亦称作先进先出 (First In First Out) 的线性表，简称 FIFO 表。
1、顺序队列 当队列中没有元素时称为空队列,在空队列中依次加入元素 a1,a2,… 之后,a1 是队头元素,a2
是队尾元素。显然退出队列的次序也只能是 a1,a2…,
也就是说队列的修改是依,先进先出,的原则进行的。
58
由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。
1.7 队列队列结构的基本操作：
（ 1）初始化队列
InitQueue(Q)
（ 2）入队 EnQueue(Q,item)
（ 3）出队 DeQueue(Q,item)
（ 4）获取队头元素内容
GetFront(Q,item)
（ 5）判断队列是否为空
QueueEmpty(Q)
59
2 循环队列 将向量空间想象为一个首尾相接的圆环
，并称这种向量为循环向量，存储在其中的队列称为循环队列（ Circular Queue)在循环队列中进行出队,入队操作时
，头尾指针仍要加 1,朝前移动。只不过当头尾指针指向向量上界 (QueueSize-1)时，其加 1 操作的结果是指向向量的下界 0 (转了一圈 )。
1.7 队列
60
1.7 队列端和删除端都是浮动的。 通常我们将插入端称为队尾，
用一个,队尾指针,指示 ； 而删除端被称为队头,用一个,队头指针,指示 。
结论,队列也是先进先出线性表 。
举例 1,到医院看病，首先需要到挂号处挂号，然后，
按号码顺序救诊。
举例 3,在 Windows这类多任务的操作系统环境中，每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。
61
1.8 串由一个或多个空格组成的串称为空白串 (Blank String)。
如,,和,” 分别表示长度为 1的空白串和长度为 0的空串 。 程序中串只能被引用但不能改变其值,即只能读不能修改串 (String) 是零个或多个字符组成的有限序列。一般记作 S=“a1a2a3… an”,其中 S是串名，双引号括起来的字符序列是串值； ai(1≦i≦n) 可以是字母,数码或其它字符；
串中所包含的字符个数称为该串的长度。 长度为零的串称为空串 (Empty String),它不包含任何字符。
串的基本操作包括：
1 串复制 (copy)：将串 s1 复制到串 s2 中。
2 联接 (concatenation)：将串 s1复制到串 s2的末尾。
3 串比较 (compare)：比较串 s1 和串 s2 的大小。
4 索引 (index)：找某字符 c在字串中第一次出现的位置
62
1.9 数组 例如，二维数组：
a11 a12 … a1n
a21 a22 … a2n
…………
am1 am2 … amn
多维数组是向量的推广。
可以看成是由 m个行向量组成的向量，也可以看成是 n个列向量组成的向量。
1,行优先顺序 —— 将数组元素按行排列，第 i+1个行向量紧接在第 i个行向量后面以二维数组为例，一个 m*n 个元素数组,按行优先顺序存储的线性序列为,a11,a12,…,a1n,a21,a22,…
a2n,……,am1,am2,…,amn。
在 PASCAL,C 语言中，数组就是按行优先顺序存储的。
2,列优先顺序 —— 将数组元素按列向量排列，第 j+1 个列向量紧接在第 j 个列向量之后，一个 m*n 个元素数组,按列优先顺序存储的线性序列为,a11,a21,…,am1,a12,a22,… am2，
……,an1,an2,…,anm
在 FORTRAN语言中，数组就是按列优先顺序存储的。
63
1.10 树和二叉树树型结构 树 是一类重要的非线性结构。
树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。
树结构在客观世界中大量存在，如家谱、行政组织机构等的形象表示，树在计算机领域中也广泛应用，如编译程序中用树表示源程序的语法结构；数据库系统中用树来组织信息；在分析算法行为时，用树来描述其执行过程等。
1、树 (tree) 是 n个结点 (n>=0)的有限集合，记为 T，
T 为空时称为空树，否则 T 应满足如下两个条件：
① 有且仅有一个特定的称为根 (root)的结点；
② 其余的结点可分为 m(m>=0)个互不相交的子集 T1，
T2,…,Tm,其中各子集又是一棵树,并称为子树 (Sub tree)。
64
1.10 树和二叉树孩子、双亲,结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 B,C,D是 A的孩子,A是双亲。
子孙,以某结点为根的子树中的所有结点都被称为是该结点的子孙。 B的子孙是 E,F,K,l。
祖先,从根结点到该结点路径上的所有结点。
兄弟,同一个双亲的孩子之间互为兄弟。
堂兄弟,双亲在同一层的结点互为堂兄弟。
根A
B C D
E
LK
F G H L
M
2、树结构常用术语,注意：结点 (对 )、节点 (可 )、接点 (错 )。
结点,数据元素内容及其指向其子树根的分支统称为结点度 (Degree),记作 d(v)。 结点的度,即树分支的个数 。
树的度,树中最大的结点度。终端结点 (叶子 )度为 0。
树的深度,树中结点层数最大值。
森林,m(m≥0) 棵互不相交的树。子树的结点为森林。
65
二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树,
这是二叉树与树的最主要的差别。
下图列出二叉树的 5种基本形态，图 (C)和图 (d)是不同的两棵二叉树。
(a)
空二叉树
A A
B
A
B
A
CB
(b)
根和空的左右子树
(c)
根和左子树
(d)
根和右子树
(e)
根和左右子树
1.10 树和二叉树
2、二叉树,是由 n(n>=0) 个结点的有限集合构成，
此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
66
1.10 树和二叉树
3、树与二叉树的区别,二叉树中每个结点的孩子至多不超过两个，而树对结点的孩子数无限制；树的子树没有次序。 深度为 K且具有 2k-1节点的二叉树称为满二叉树。
深度为 k的 n结点二叉树当且仅当每结点与深度 k满二叉树中层次编号从 1～ n的结点一一对应则称为完全二叉树。
树不区别左右，但二叉树是区别左右的，二叉树为左右不同的两种二叉树。二叉树有以下特征：
性质 1,在二叉树第 i层上至多有 2i-1个结点 (i≥1) 。
性质 2,深度为 k的二叉树中,最多有 2k-1个结点 (K≥1) 。
性质 3,具有 n个结点的完全二叉树的深度是,[log2n]+1
性质 4,任意一棵二叉树中，若其叶子的结点数为 n0，深度 2的结点数为 n2，则 n0=n2+1。
67
1.10 树和二叉树
4、二叉树的存贮,二叉树的存贮采用链接方式，以链表示一棵二叉树，用链指示元素的逻辑关系。链表中每个节点由三个域组成，数值域及表示左右子树的两个指针域，
以表示链接点的存贮地址。
lchild data rchild
其中 data是存放节点的数据信息,lchild 与 rchild
分别指向左右子树的指针,当子树不存在时,对应指针域值为空 (以 ^或 NULL表示 )。 链式存贮结构比较适合存贮二叉树 。
G
A
C
F
E
B
D
A ^
B
^ E C
^ D ^^ D ^ ^ D ^
68
1.10 树和二叉树
5、二叉树的常用操作及算法,遍历是二叉树的一种重要运算，按一定次序访问该结构中所有节点，可分两大类：
一、先根遍历,即先访问根，然后遍历每棵子树。
二、后根遍历,即先遍历每一棵子树，最后访问根。
按树的递归定义，树遍历按根 (N)、左 (L)、右 (L)次序可分为 NLR,LNR,LRN,NRL,RNL,RLN六种，实际常用以下三种二叉树遍历方法：
f
a
c
e
d
b
g
h
① 先序遍历法 NLR,先访问根节点、后序遍历左子树，再序遍历右子树。 Abdecfgh
② 中序遍历法 LNR,先序遍历左子树，后访问根节点，再序遍历右子树。 debfcgah
③ 后序遍历法 LRN,先序遍历左子树，
后序遍历右子树，再访问根节点。 edfgcbha
69
1.11 图
10.1 图的基本概念
BA C
D 6
3
2
1
5图是复杂的数据结构，有其完整的理论 ----图论。其基本概念为：
顶点,图中的数据元素
V：表示 顶 点的非空有限集合。
VR：表示两个 顶 点之间关系的集合。
无向图图有向图在有向图中,<V1,V3>表示从 V1到 V3的一条弧。
V1为弧尾或初始点,V3为弧头或终端点。
在无向图中,(V1,V3)表示 V1和 V3之间的一条边 。
V1 V3
V2 V4
V1 V3
V2 V4
p1
p2 p4p3
70
1.11.1 图
G=( V,E )
V1 V3
V2 V4
顶点集合 V={V1,V2,V3,V4 }
弧的集合 G={<V1,V3>,<V3,V4>,
<V2,V4>,<V4,V1>}
顶点集合 V={V1,V2,V3,V4 }
边的集合 E={(V1,V3),(V1,V2),
(V1,V4),(V2,V4)}
顶点 (V1,V3)与 (V3,V1)表示同一条边
V1 V3
V2 V4
权：与图的边或弧相关的数。
网：带权的图。
顶点的度：依附于该顶点的边数或弧数。
出度：（仅对有向图）以该顶点为尾的弧数。
路径：顶点 A与顶点 C之间存在一条路径。路径上边或弧的数目称为该路径的路径长度。
入度：（仅对有向图）以该顶点为头的弧数。
71
1、图的连接矩阵表示法：
2、图的邻接表示法：
1.11.2 图的存储结构
V1 V3
V2 V4
V1 V2 V3 V4
V1 0 0 1 0
V2 0 0 0 1
V3 0 0 0 1
V4 1 0 0 0
V1 V3
V2 V4
V1 V2 V3 V4
V1 0 1 1 1
V2 1 0 0 1
V3 1 0 0 0
V4 1 1 0 0
图的连接矩阵表示法
72
邻接矩阵表示法对求顶点的度很方便。
在无向图中,顶点的度数 =矩阵中对应该顶点的行 或 列中非零元素的个数。
在有向图中：
顶点的出度 =矩阵中对应该顶点的 行 中非零元素的个数。
顶点的入度 =矩阵中对应该顶点的 列 中非零元素的个数。
1.11.2 图的存储结构
V1 V3
V2 V4
V1 V3
V2 V4
V1 V2 V3 V4
V1 0 0 1 0
V2 0 0 0 1
V3 0 0 0 1
V4 1 0 0 0
V1 V2 V3 V4
V1 0 1 1 1
V2 1 0 0 1
V3 1 0 0 0
V4 1 1 0 0
入度 出度
1 1
1 1
2 1
0 1
度数
3
2
1
2
73
V1 V3
V2 V4
4
3
2
1 2
1
∧1
1
3
∧4
∧4
∧2
V1 V3
V2 V4
图的邻接表存贮法,即对图中每个顶点建立一个单链表，第 i
个单链表中的结点表示依附于该顶点 Vi的边（或弧）
1.11.2 图的存储结构
1.10.3 图的应用,图的应用非常广泛,例如：
① 用图可以表示一座城市的交通联系的情况；
② 用有值图可表示两城市间距离,车费,或航班数目 。
③ 表示城市之间建立的通讯网络
④ 可以描述化学结构式 。
⑤ 图中两点之间的最短距离问题 。
3
2
1
∧1
∧3
∧4
∧4
4
74
1.12 文件文件,是存于磁盘上的数据的集合，它不是传统意义上内存中的数据存储格式。
记录,以若干字节组成的一组数据。
1、顺序文件,是按存储的先后顺序，连续存于磁盘上的记录的集合。逻辑上顺序文件的记录是连续存储的。
2、随机文件,是以标号标记每个记录，以随序号顺序存于磁盘上的记录的集合。逻辑上随机文件的记录是不连续存储的。
75
一、录入文字,个人简历部分。 出生幼年环境，童年烂漫生活，
小学花朵时代，中学未来向往。大学远大抱负，个人特长等。
二、要求,一项为 20分，二中其它各项均为 10分。
① 文字,500个以上，在适当处加入?,?,?,?,?等 符号。
② 表格：制作不等距表元,斜线,插图,标题,求均分,绘直方图
③ 公式,编写 含有?,?、上下标、嵌套分子式的上下限积分。
④ 图片：在文本适当位置插入几个图片,使其环绕文字、作水印
⑤ 编辑：分栏,倾斜,变色,空心,加边框,底纹,沉底、组合
⑥ 艺术字：改变艺术体，旋转角度、制作二三维造型。
⑦ 自选图形：在封闭图中输入文字，改变边框、填充颜色。
⑧ 移动对象：将图形或公式插入文本框，并移位于任何位置。
⑨ 设置：纸张大小、边距，以电子邮件发往 shouz.c@nuc.edu.cn邮箱三、希望,体现个性，图文并茂，标新立异、创意无穷，让读赏心悦目、爱不释手、能择优录取，一书即成 (取得高分 )。
注,版面内容相同者均以盗板拷贝看待，成绩定为不及格。
模拟考题：自荐求职书
76
本课程作业二、将 Excel应用穿插在求职自荐书中。
1,Excel 表的应用要求：实现编辑、格式化表格，利用公式和函数对表格进行必要的统计、运算和管理，插入统计图表等主要功能。
2,PowerPoint 制作：
要求：查询 2007年以来自己感兴趣的五条新闻，并制作成演示文稿，插入在 PowerPoint的演示文稿中。主要内容：
(1).改写求职自荐书成三个幻灯片。
(2).新闻标题和详细内容有 internet的超级链接。
三、单向链表算法实现 (参考 C程序设计课本 )
完成主程序及插入、删除、改写等子程序。
书写实验报告，格式参考 C语言实验报告格式。
请于 4月 30日以前完成。书面打印提交。
77
实验是高等教育教育的组成部分，特别是工科院校更应如此：
1、预习报告,体现自己实验进程思想，作为本人实验工作指南。
内容：实验目的、实验原理、实验条件、实验内容、实验步骤、实验结果预测及实验中可能发生的问题与注意事项等。
2、结果分析报告,实验结果的分析与总结，需交教师批阅。
内容：实验过程、实验方法、实验结果、实验结论、对结果的分析、处理，及对实验内容要求、建议、意见等。
3、实验性质,操作性,验证性,分析性,设计性,综合性等实验 。
4、实验目的,提高素质、积累知识、训练方法、培养技术、
拓宽能力 (思维能力、行为能力、适应能力 )
4、实验报告书写,书写实验报告是实验教学的一部分，要求报告条理清晰、简单明了、分析透彻，避免简而不明或繁而无绪两种不良情况。一般情况写 1500字左右能阐明清楚即可。
实验报告分：
预习与分析
