软件技术基础

1、软件的定义：软件的定义：软件是程序数据与文档的总称。它包含软件是程序数据与文档的总称。它包含3 3个方面：个方面：（1 1）能以预期性能执行预期功能的一段指令；）能以预期性能执行预期功能的一段指令；（2 2）便于程序操纵信息的数据结构；）便于程序操纵信息的数据结构；（3 3）记录程序的操纵和使用的文档。）记录程序的操纵和使用的文档。第一章第一章 算法算法预备知识预备知识硬件硬件软件软件冯冯诺依曼结构：存贮程序、程序控制诺依曼结构：存贮程序、程序控制哈佛结构：指令流、数据流分离哈佛结构：指令流、数据流分离系统软件系统软件应用软件应用软件计算机计算机算法的定义：算法的定义：算法是一个有穷规则的集合

2、，其中之规则确定算法是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。了一个解决某一特定类型问题的运算序列。算法是对求解特定问题的方法和步骤完整而精算法是对求解特定问题的方法和步骤完整而精确的描述。确的描述。第一章第一章 算法算法1.1.1 1 算法算法的基本概念的基本概念算法具有四个基本特征： (1)(1)有穷性：有穷性：算法必须能在执行有穷步骤之后结束，每一算法必须能在执行有穷步骤之后结束，每一步骤都能在有限时间内完成；步骤都能在有限时间内完成；(2)(2)确定性：确定性：算法的每一个步骤必须是确切定义的。并且，算法的每一个步骤必须是确切定义的。并且，对于一种输入，

3、算法只有一条执行路径，即对于对于一种输入，算法只有一条执行路径，即对于相同的输入只能得到相同的输出；相同的输入只能得到相同的输出；(3)(3)能行性：能行性：算法中描述的操作都可以通过已经实现的基算法中描述的操作都可以通过已经实现的基本运算执行有限次来本运算执行有限次来实现；实现；(4)(4)拥有足够的情报拥有足够的情报：当算法拥有足够的情报时，次算法才当算法拥有足够的情报时，次算法才是有效的。是有效的。1.1 算法的基本概念算法的描述算法的描述: :本书采用本书采用C+C+语言描述可读性强，而且做简单的修语言描述可读性强，而且做简单的修改就可以转换成可以编译调试的改就可以转换成可以编译调试的

4、C+C+程序。程序。算法的要求：算法的要求：正确性，可读性，健壮性，高效率正确性，可读性，健壮性，高效率1.1 算法的基本概念对数据对象的运算和操作对数据对象的运算和操作 算术运算算术运算 逻辑运算逻辑运算 关系运算关系运算 数据传输数据传输算法的算法的控制结构控制结构1.1.1 1 算算法的基本概念法的基本概念1.1.21.1.2算算法的两个基本要素法的两个基本要素（1 1）列举法列举法基本思想:提出问题 列举所有可能 检验是否需要 ( (2) 2) 归纳法归纳法基本思想:列举少量的特殊情况 分析 找出一般的关系 ( (3) 3) 递推递推基本思想:已知的初始条件 所要求的各中间结果和最后结

5、果（4） 递归递归（5）减半递推技术）减半递推技术（6）回溯法）回溯法1.2 算法设计基本方法算法的复杂度主要包括：8 时间复杂度时间复杂度8 空间复杂度空间复杂度1.3 算法的复杂度分析1.算法的时间复杂度 所谓的时间复杂度，是指执行算法所需要的计所谓的时间复杂度，是指执行算法所需要的计算工作量算工作量 算法的工作量用算法所执行的基本运算次数算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模来度量，而算法所执行的基本运算次数是问题规模的函数，即的函数，即 算法的工作量算法的工作量 = = F F（N N）其中其中N N是问题的规模是问题的规模 1.3 算法的复

6、杂度分析在同一问题规模下，如果算法执行所需的基本运算在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：来分析算法的工作量：（1）平均性态）平均性态所谓平均性态分析，是指用各种特定输入下的基本所谓平均性态分析，是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。运算次数的带权平均值来度量算法的工作量。（2）最坏情况复杂度）最坏情况复杂度所谓最坏情况分析，是指在规模为所谓最坏情况分析，是指在规模为N时，算法所执时，算法所执行的基本运算的最大次数。行的基本运算的最大次数。1.3 算法的

7、复杂度分析 我们用我们用O(F(N)来做为算法时间耗费的度量，来做为算法时间耗费的度量，称为算法的称为算法的渐进时间复杂度，渐进时间复杂度，简称为算法的简称为算法的时间复杂时间复杂度。度。 例如对于例如对于 T(N)=2N3+3N2+2N+1, 可可记为记为: T(N)=O(N3)1.3 算法的复杂度分析常用来常用来表示时间表示时间复杂度的函数：复杂度的函数： O(1) O(LOG N) O(N) O(NLOG N) O(NC) O(CN) O(N!)时间性能越来越坏时间性能越来越坏无效算法无效算法1.3 算法的复杂度分析2.算法的空间复杂度： 一个算法的空间复杂度，一般是指执行这个算法一个算

8、法的空间复杂度，一般是指执行这个算法所所 需要的内存空间。需要的内存空间。 一个算法所占用的存储空间包括算法程序所占的一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。行过程中所需要的额外空间。1.3 算法的复杂度分析132.1 2.1 数据结构的基本概念数据结构的基本概念2.2 2.2 线性表及其顺序存储结构线性表及其顺序存储结构2.3 2.3 线性链表及其运算线性链表及其运算2.4 2.4 数组数组2.5 2.5 树与二叉树树与二叉树2.6 2.6 图图2.1.1 什么是数据结构数据结

9、构是指相互有关联的数据元素的集合数据结构是指相互有关联的数据元素的集合数据：计算机可以保存和处理的信息数据：计算机可以保存和处理的信息数据元素：组成数据的基本单位数据元素：组成数据的基本单位数据项：数据元素的分量数据项：数据元素的分量数据对象：同类型的数据元素的集合数据对象：同类型的数据元素的集合14 2.1 数据结构的基本概念1.1.数据的逻辑结构数据的逻辑结构 所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D D ；二是D D上的关系，它反映了D D中各数据元素之间的前后件关系，通常记为R R15 2.1 数据结构的基本

10、概念2. 2. 数据的存储结构数据的存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引、散列等存储结构。16 2.1 数据结构的基本概念序偶: 两个数据元素两个数据元素X和和Y之间存在某种特定关系之间存在某种特定关系(如图如图a所示所示)称为一个序偶，记为称为一个序偶，记为。 这里，这里，X称为称为Y的直接前驱；的直接前驱；Y称为称为X的直接后继。的直接后继。 如果这种关系是对称的，也就是说如果存在如果这种关系是对称的，也就是说如果存在,就必然有就必然有,

11、则记为则记为(X,Y),图图b表示。表示。17X图a图bYXY（x, y） 2.1 数据结构的基本概念2.2.2 2 线性表线性表及其顺序存储结构及其顺序存储结构2.2.1 线性表及其运算2.2.2 栈及其运算2.2.3 队列及其应用182.2.1 2.2.1 线性表及其运算线性表及其运算线性表线性表的形式定义：的形式定义：Linear_List=(D,R)D=a1, a2, , anR=rR=, , , , , 19a1a2ai-1aiai+1an-1an起始结点起始结点( (表头结点表头结点, ,首元结点首元结点) )终端结点终端结点( (表尾结点表尾结点) ) 2.2 线性表及其顺序存储

12、结构称：称：ai-1是是ai的直接前趋的直接前趋（有时简称前趋） ai+1是是ai的直接后继的直接后继（有时简称后继） 20ai-1aiai+1 2.2 线性表及其顺序存储结构8 线性表线性表是由是由n(nn(n=0)=0)个数据元素组成的一个有限个数据元素组成的一个有限序列序列; ;8 n=0n=0的表称为空表的表称为空表; ;8 数据元素呈线性关系数据元素呈线性关系, , 当线性表非空时，必存在当线性表非空时，必存在唯一的称为唯一的称为“第一个第一个”的数据元素的数据元素; ;必存在唯一必存在唯一的称为的称为“最后一个最后一个”的数据元素；的数据元素；8 除除a a1 1没有前趋外，其他结

13、点有且仅有一个直接前没有前趋外，其他结点有且仅有一个直接前驱；驱；8 除除a an n没有后继外，其他结点有且仅有一个直接后没有后继外，其他结点有且仅有一个直接后继继21 2.2.2 2 线性表线性表及其顺序存储结构及其顺序存储结构 线性表的顺序存储结构在计算机中存放线性表，一种最简单的方法是顺序存储，也成为顺序分配。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 2.2.2 2 线性表线性表及其顺序存储结构及其顺序存储结构在线性表的顺序存储结构下，可以对线性表进行各种处理。主要的运算有以下几

14、种：（1）在线性表的指定位置处加入一个新的元素（即线性表的插入）；（2）在线性表中删除制定的元素（即线性表的删除）；（3）在线性表中查找某个（或某些）特定的元素（即线性表的查找）；（4）对线性表中的元素进行整序（即线性表的排序）； 2.2.2 2 线性表线性表及其顺序存储结构及其顺序存储结构（5）按要求将一个线性表分解成多个线性表（即线性表的分解）；（6）按要求将多个线性表合并成一个线性表（即线性表的合并）；（7）复制一个线性表（即线性表的复制）；（8）逆转一个线性表（即线性表的逆转）等。 2.2.2 2 线性表线性表及其顺序存储结构及其顺序存储结构c用一组用一组地址连续地址连续的空间存放线性

15、表的数据元素。各的空间存放线性表的数据元素。各元素按其逻辑次序依次存放；元素按其逻辑次序依次存放；c采用顺序存储结构存储的线性表又称为采用顺序存储结构存储的线性表又称为顺序表顺序表；c顺序表的特点：顺序表的特点： 逻辑上相邻的元素，物理位置上也相邻；逻辑上相邻的元素，物理位置上也相邻； 元素之间的逻辑关系通过物理位置的先后来体现元素之间的逻辑关系通过物理位置的先后来体现25 2.2 线性表线性表及其顺序存储结构及其顺序存储结构a1a2 ai-101i-2i-1in-1n26插入操作（前插）：8 必须保证逻辑上相邻的元素物理上也相邻必须保证逻辑上相邻的元素物理上也相邻8 合法的插入位置有合法的插

16、入位置有n1个，个，i1.n+1e向右移一位anai+1ai线性表的顺序表示和实现-顺序表插入操作算法思想：1. 检查插入位置检查插入位置i是否合法：是否合法：1in1，共有，共有n+1个合法插入位置；个合法插入位置；2. 检查数组中是否有空闲的空间放新元素。如果没检查数组中是否有空闲的空间放新元素。如果没有，将数组扩展有，将数组扩展ListIncrement个结点个结点3. 将将an至至ai逐个右移一位逐个右移一位4. 新元素新元素e放入下标为放入下标为i1的单元的单元5. 修改表长：修改表长：K.length+河海大学 能源与电气学院27必须大量移动元素线性表的顺序表示和实现-顺序表栈是软

17、件设计中最基本的数据结构栈是软件设计中最基本的数据结构,学习栈结构时，需要掌握哪些方面的内容？学习栈结构时，需要掌握哪些方面的内容？为此，回顾一下上一章所介绍的数据结构的组成部分。为此，回顾一下上一章所介绍的数据结构的组成部分。28逻辑结构逻辑结构分析分析 运算实现（算法）运算实现（算法） 运算定义运算定义 存储结构存储结构数据结构的组成数据结构的组成2.22.2.2.2 栈及其应用栈及其应用 一一:栈的定义栈的定义 栈是只能在一端插入和删除元素的线性表。栈是只能在一端插入和删除元素的线性表。 术语术语：栈顶栈顶, 栈底栈底, 入栈（压栈）入栈（压栈）, 出栈（弹栈）出栈（弹栈） am am-

18、1 a129入栈(PUSH) 出栈(POP) 栈顶(top)栈底(bottom)逻辑结构和运算逻辑结构和运算a1 a2 am 特点：后进先出（特点：后进先出（LIFO）a1a2amama2a1 二二: :栈的运算栈的运算1.1.栈的基本运算定义栈的基本运算定义对栈的基本运算有如下几个：对栈的基本运算有如下几个：(1)(1)初始化初始化 ：设置栈为空。：设置栈为空。 (2)(2)判断栈为空：判断栈为空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断栈为满：判断栈为满： 若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回

19、FALSE. FALSE. (4)(4)取栈顶元素：取栈顶元素：取出栈顶元素。取出栈顶元素。 条件：栈不空。条件：栈不空。 否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)入栈：将元素入栈，即放到栈顶。入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处理？如果栈满，怎样处理？ (6)(6)出栈：删除当前栈顶的元素。出栈：删除当前栈顶的元素。 如因为栈空而不能进行，如因为栈空而不能进行，应怎样处理？应怎样处理？ 302.2.2 栈及其应用(1)(1)入栈运算入栈运算: : 在栈顶位置插入一个新元素在栈顶位置插入一个新元素. .操作过程如下操作过程如下:

20、:1)1)判断栈顶指针是否已经指向存储位置最后一个判断栈顶指针是否已经指向存储位置最后一个元素元素, ,若是若是, ,则栈空间已满则栈空间已满, ,否则上溢否则上溢, ,算法结算法结束束; ;2)2)栈顶指针进一栈顶指针进一(top(top加一加一););3)3)将新元素将新元素x x插入到栈顶指针指向的位置插入到栈顶指针指向的位置; ;31操作过程如下操作过程如下: :1)1) 判断栈顶指针是否为判断栈顶指针是否为0,0,若是若是, ,则栈空则栈空, ,不能进行不能进行退栈退栈( (下溢下溢),),算法结束算法结束; ;2)2) 将栈顶元素赋给一个指定的变量将栈顶元素赋给一个指定的变量; ;

21、3)3) 将栈顶指针退一将栈顶指针退一(top-1);(top-1);321 1 什么是队列什么是队列 队列是只能在一端插入队列是只能在一端插入, ,另一端删除元素的线性表另一端删除元素的线性表. .术语术语: :队头队头, ,队尾队尾, ,入队入队, ,出队出队33 1a2ama1a2amama2a1a特性特性: :先进先出先进先出FIFOFIFO 1a2ama出队队头队尾 入队(1)(1) 初始化初始化: :设置队列为空设置队列为空. .(2)(2) 判断队列为空判断队列为空: : 若为空若为空, ,则返回则返回TRUE,TRUE,否则返回否则返回FALSE.FALSE.(3) (3) 判

22、断队列为满判断队列为满: : 若为满若为满, ,则返回则返回TRUE,TRUE,否则返回否则返回FALSE.FALSE.(4) (4) 取队头元素取队头元素, ,取出队头元素取出队头元素. . 条件条件: :队列不空队列不空. . 否则否则, ,应能明确给出标识应能明确给出标识, ,以便程序的处理以便程序的处理. .(5) (5) 入队入队: :将元素入队将元素入队, ,即放到队列的尾部即放到队列的尾部. . 如果队列满如果队列满, ,怎样处理怎样处理? ?(6) (6) 出栈出栈: :删除当前对头的元素删除当前对头的元素. . 如因为队列空而不能进行如因为队列空而不能进行, ,应怎样处理应怎

23、样处理? ?34（1 1）入队运算）入队运算操作过程如下操作过程如下: :1)1) 判断循环队列是否满判断循环队列是否满. .若满若满, ,则算法结束则算法结束. .2)2) 将队尾指针进一将队尾指针进一(rear=rear+1),(rear=rear+1),并当并当rear=m+1rear=m+1时置时置rear=1.rear=1.3)3) 将新元素将新元素x x插入到队尾指针指向的位置插入到队尾指针指向的位置, ,并且置并且置循环队列非空标志循环队列非空标志. .35操作过程如下操作过程如下: :1)1) 判断循环队列是否为空判断循环队列是否为空, ,若为空若为空( (下溢下溢),),算法

24、结算法结束束. .2)2) 将排头指针进一将排头指针进一(front=front+1),(front=front+1),并当并当front=m+1front=m+1时置时置front=1.front=1.3)3) 再将排头指针指向的元素赋给指定的变量再将排头指针指向的元素赋给指定的变量. .4)4) 最后判断退队后循环队列是否为空最后判断退队后循环队列是否为空. .362.3.1 线性链表的基本概念线性链表的基本概念1 1 线性链表线性链表( (单链表单链表) ) 特点特点: :用一组可能连续，也可能不连续的任意存储单元用一组可能连续，也可能不连续的任意存储单元 存放线性表中的数据元素。存放线

25、性表中的数据元素。 元素之间的逻辑联系通过指向直接后继的指针来体现元素之间的逻辑联系通过指向直接后继的指针来体现; ; 指针指针nextnext本身并不是数据元素的成分本身并不是数据元素的成分。37V(i)NEXT(i)数据域数据域 指针域指针域( (附加空间附加空间) )2 2 线性链表类线性链表类 将线性链表的数据和基本操作将线性链表的数据和基本操作( (初始化初始化, ,扫描输出扫描输出, ,插入与删除链头元素等插入与删除链头元素等) )封装成一个线性单链表类封装成一个线性单链表类; ;(1)(1) 定义单链表类定义单链表类(2)(2) 建立空链表建立空链表(3)(3) 检测单链表状态检

26、测单链表状态(4)(4) 从头指针开始扫描输出链表中的元素从头指针开始扫描输出链表中的元素(5)(5) 将新元素插入到链头将新元素插入到链头(6)(6) 删除链头元素删除链头元素 382.3 2.3 线性链表及其运算线性链表及其运算线性链表的运算主要有以下几种线性链表的运算主要有以下几种: :(1)(1) 在线性链表中包含指定元素的结点之前插入一个新元素在线性链表中包含指定元素的结点之前插入一个新元素; ;(2)(2) 在线性链表中删除包含指定元素的结点在线性链表中删除包含指定元素的结点; ;(3)(3) 将两个线性链表按要求合并成一个线性链表将两个线性链表按要求合并成一个线性链表; ;(4)

27、(4) 将一个线性链表按要求进行分解将一个线性链表按要求进行分解; ;(5)(5) 逆转线性链表逆转线性链表; ;(6)(6) 复制线性链表复制线性链表; ;(7)(7) 线性线性链表的排序链表的排序; ;(8)(8) 线性线性链表的查找链表的查找; ;本本节主要讨论前两个节主要讨论前两个运算。运算。392.3.2 2.3.2 线性链表的基本运算线性链表的基本运算1.1.带链的栈带链的栈与顺序栈一样，带与顺序栈一样，带链栈的链栈的基本操作有以下几个基本操作有以下几个: :(1)(1) 栈的栈的初始化。即初始化。即建立一个空栈的顺序建立一个空栈的顺序存储空间。存储空间。(2)(2) 入入栈栈运算

28、。是运算。是指在栈顶位置插入一个新指在栈顶位置插入一个新元素。元素。(3)(3) 退退栈栈运算。是运算。是指取出栈指取出栈顶元素并顶元素并赋给一个指定赋给一个指定的的变量。变量。(4)(4) 读读栈栈顶元素。是顶元素。是指将栈顶元素赋给一个指定的指将栈顶元素赋给一个指定的变量。变量。402.3.3 2.3.3 带链的栈与队列带链的栈与队列2.2.带链的队列带链的队列与顺序队列一样，带与顺序队列一样，带链队列的基本链队列的基本操作有以下几个操作有以下几个: :(1(1) )队列队列的的初始化。即建立一个空队列的顺序存储空初始化。即建立一个空队列的顺序存储空间；间；(2(2) )入队运算。是指在循

29、环队列的队尾加入一个新元入队运算。是指在循环队列的队尾加入一个新元素；素；(3(3) )退退队队运算。是指在循环队列的排头位置退出一个运算。是指在循环队列的排头位置退出一个元素并赋给指定的变量。元素并赋给指定的变量。 412.3.3 2.3.3 带链的栈与队列带链的栈与队列循环链表的特点循环链表的特点: :(1)(1)在循环链表中增加了一个表头结点在循环链表中增加了一个表头结点, ,其数据域为任意或者根据需其数据域为任意或者根据需要来要来设置，指针设置，指针域指向线性表的第一个元素的域指向线性表的第一个元素的结点。循环链表的结点。循环链表的头指针指向表头结点。头指针指向表头结点。(2)(2)循

30、环循环链表中最后一个结点的指针域不是链表中最后一个结点的指针域不是空，而是空，而是指向表头指向表头结点。结点。即即在循环链表在循环链表中，所有中，所有结点的指针构成了一个环状结点的指针构成了一个环状链。链。42a1a2anHEAD(a) (a) 非空循环链表非空循环链表(b) (b) 空循环链表空循环链表HEAD循环链表的特点循环链表的特点: :(1)(1)在循环链表中增加了一个表头结点在循环链表中增加了一个表头结点, ,其数据域为任意或者根据需其数据域为任意或者根据需要来设置要来设置, ,指针域指向线性表的第一个元素的结点指针域指向线性表的第一个元素的结点. .(2)(2) 循环链表中最后一

31、个结点的指针域不是空循环链表中最后一个结点的指针域不是空, ,而是指向表头结点而是指向表头结点, ,即在循环链表中即在循环链表中, ,所有结点的指针构成了一个环状链所有结点的指针构成了一个环状链. .43a1a2anHEAD(a) (a) 非空循环链表非空循环链表(b) (b) 空循环链表空循环链表HEAD多项式的运算主要有以下多项式的运算主要有以下5 5种种: :（1 1）多项式）多项式链表的生成链表的生成; ;（2 2）多项式）多项式链表的释放链表的释放; ;（3 3）多项式）多项式的输出的输出; ;（4 4）多项式）多项式相加相加; ;（5 5）多项式）多项式的的相乘。相乘。442.3.

32、5 2.3.5 多项式的表示运算多项式的表示运算2.4.1 2.4.1 数组的顺序存储结构数组的顺序存储结构1.1.二二维数组以行为主的顺序存储维数组以行为主的顺序存储 二维数组以行为主的顺序存储指将数组中的元素一行接一行的顺序存储在计算机的连续存储空间中,即：先存储第1行,然后存储第2行,以此类推;每一行的元素以从左到右的顺序存储。2.2.二维数组以列为主的顺序存储二维数组以列为主的顺序存储 二维数组以列为主的顺序存储是指将数组中的元素一列接一列地顺序存储在计算机的连续存储空间中，即：先存储第1列，然后存储第2列，依此类推；每一列的元素以从上到下的顺序存储。452.4.2 规则矩阵的压缩 所

33、谓规则矩阵，是指矩阵中非零元素的分布有规律。 在规则矩阵中，由于非零元素有规律的分布在矩阵中，因此，在存储一个规则矩阵时，只需存储非零元素即可，而对于大部分的零元素或者重复的非零元素（如对称矩阵）不必存储，从而可以节省存储空间。矩阵的这种存储方法称为压缩存储。462.4 2.4 数组数组2.4.3 2.4.3 一般稀疏矩阵的表示一般稀疏矩阵的表示 定义：设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。设在矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。 稀疏矩阵的存储存储非零元素的同时，还必须记下所

34、属行和列的位置（i,j)。一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。这样的存储方法大大节约了存储空间，但矩阵的运算变得复杂。472.4 2.4 数组数组 十字链表类型定义十字链表类型定义稀疏矩阵中同一行的非零元通过向右的right指针链接成一个带表头结点的线性链表。同一列的非零元也通过down指针链接成一个带表头结点的线性链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。482.4

35、2.4 数组数组2.5.1 2.5.1 树的基本概念树的基本概念49RPQKDBENQTCHXYSZWAMFGL图图2.39 2.39 一般的树一般的树 学校学校行政层次结构树行政层次结构树502.5.1 2.5.1 树的基本概念树的基本概念经济管理学院经济信息系计划统计系外贸系经管系信息处理教研室经济数学教研室计划学教研室统计学教研室外语教研室国际贸易教研室宏观经济学教研室微观经济学教研室基本术语基本术语: :(1)(1) 父结点父结点: : 在树结构中在树结构中, ,每一个结点的前件每一个结点的前件. .(2)(2) 树的根树的根: : 在树中在树中, ,没有前件的结点只有一个没有前件的结

36、点只有一个, ,称为树的根结称为树的根结点点, ,简称为树的根简称为树的根. .(3) (3) 子结点子结点: : 在树结构中在树结构中, ,每一个结点可以有多个后件，它们每一个结点可以有多个后件，它们都称为该结点的子结点都称为该结点的子结点, , 没有后件的结点称为叶子结点没有后件的结点称为叶子结点. .(4)(4)结点的度结点的度: : 在树结构中，一个结点所拥有的后件个数称为该在树结构中，一个结点所拥有的后件个数称为该结点的度结点的度, , 在树中在树中, ,所有结点中的最大度称为树的度所有结点中的最大度称为树的度. .512.5.1 2.5.1 树的基本概念树的基本概念 用树来表示算术

37、表达式的原则如下：（1）表达式中的每一个运算符在数中对应一个结点，称为运算符结点。（2）运算符的每一个运算对象在树中为该运算符节点的子树（在树中的顺序为从左到右）。（3）运算对象中的单变量均为叶子结点。522.5.1 2.5.1 树的基本概念树的基本概念1.1.什么是二叉树什么是二叉树 二叉树是一种很有用的非线性结构。二叉树不同于前面介绍的树结构，但它与树结构很相似，并且树结构的所有术语都可以用到二叉树这种数据结构上。 二叉树具有以下两个特点：二叉树具有以下两个特点： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。532.5.2 2.5.2

38、 二叉树及其基本性质二叉树及其基本性质2.2.二叉树二叉树的基本性质的基本性质性质1 在二叉树的第k层上,最多有 (k1)个结 点； 性质2 深度为m的二叉树最多有 个结点.性质3 在任意一棵二叉树中,度为0的结点(叶子结点) 总是比度为2的结点多一个;性质4 具有n个结点的二叉树,其深度至少为log2n+1,其中log2n取log2n的整数部分;542.5.2 2.5.2 二叉树及其基本性质二叉树及其基本性质2.5.2 2.5.2 二叉树及其基本二叉树及其基本性质性质 几种特殊形态的二叉树（1 1）满二叉树）满二叉树满二叉树是指：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满

39、二叉树中，每一层上的结点数都达到最大值。（2 2）完全二叉树）完全二叉树完全二叉树是指：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。2.5.2 2.5.2 二叉树及其基本二叉树及其基本性质性质（3 3）平衡二叉树）平衡二叉树结点的平衡因子=左子树的深度-右子树的深度所有结点平衡因子的绝对值不大于1，称为平衡二叉树。（4 4）二叉排序树）二叉排序树key(L)key(B)Key(R)key(B)2.5.3 2.5.3 二叉树的二叉树的遍历遍历 二叉树的遍历是指不重复地访问二叉树中的所有结点 在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原

40、则下，根据访问根结点的次序，二叉树的遍历可分为三种： 前序遍历前序遍历 中序遍历中序遍历 后序遍历后序遍历572.5.3 2.5.3 二叉树的二叉树的遍历遍历 前序遍历（前序遍历（DLRDLR）（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。 中序遍历（中序遍历（LDRLDR）（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。 后序遍历（后序遍历（LRDLRD）（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。582.5.4 2.5.4 二叉树的存储结构二叉树的存储结构1.1.二叉链表二叉链表在计算机中，二叉树通常采用链式存储结构。与线性链表类似，用于存储

41、二叉树中各元素的存储结点也由两部分组成：数据域与指针域。2.2.二叉链表类二叉链表类（1）二叉链表的生成；（2）二叉链表的前序遍历；（3）二叉链表的中序遍历；（4）二叉链表的后序遍历；2.5.5 2.5.5 穿线二叉树穿线二叉树1.穿线二叉树的概念利用二叉链表中的空指针域来链接遍历序列，就好像在二叉链表中增加了一个遍历的线索。这样的二叉链表称为穿线二叉链表，简称穿线二叉树，又称线索二叉树。2.中序穿线二叉树（1）中序穿线二叉树的构造（2）中序穿线二叉树的遍历（3）中序穿线二叉链表类3.前序穿线二叉树（1）前序穿线二叉树的构造（2）前序穿线二叉树的遍历（3）前序穿线二叉链表类2.5.5 2.5.

42、5 穿线二叉树穿线二叉树4.4.后序穿线二叉树（1）后序穿线二叉树的构造 若当前访问到的结点的左指针为空，则将上次访问到的结点序号填入，并置左标志域为1。 若上次访问到的结点的右指针为空，则将当前访问到的结点序号填入，并置右标志域为1。（2）后序穿线二叉树的遍历（3）前序穿线二叉链表类1.1.有序有序树的二叉树表示树的二叉树表示 在二叉树中,由于每一个结点的度最大为2,即二叉树中的每一个结点最多有两个子结点,分为左子结点与右子结点,而在一般的树结构中,每一个结点的度是任意的,即树中每一个结点可以有任意个子结点,如果对某个结点的所有子结点按从左到右排上次序,则称该树为有序树. 在有序树中,某个结

43、点的所有子结点从左到右的次序是不能颠倒的.622.5.6 2.5.6 表达式的线性化表达式的线性化将有序树转化成二叉树的原则如下将有序树转化成二叉树的原则如下: :(1) 有序树T中的结点与二叉树BT中的结点一一对应;(2) 有序树T中某个结点N的第一个子结点(最左边的子结点)N1,在二叉树BT中为对应结点N的左子结点.(3) 有序树T中某个结点N的第一个子结点以后的其他子结点,在二叉树BT中被依次链接成一串起始于N1的右子结点.632.5.6 2.5.6 表达式的线性化表达式的线性化将有序树转化成二叉树将有序树转化成二叉树的方法：的方法：（1）兄弟结点之间加一条连线；（2）对每一个节点，只保

44、留其与左边第一个子结点的连线，与其它子结点的连线全部抹去；（3）以根为轴心，顺时针旋转45.642.5.6 2.5.6 表达式的线性化表达式的线性化2.2.表达式表达式的线性化的线性化 定义:将一般的表达式化为波兰表示式(后缀表示); 利用树结构与二叉树结构对表达式线性化的 步骤如下:(1) 将表达式用有序树表示,即构造表达式树;(2) 将表达式树化为二叉树;(3) 对相应的二叉树进行中序遍历,其遍历序列即为表达式的波兰表示式;652.5.6 2.5.6 表达式的线性化表达式的线性化2.6.1 2.6.1 图的基本概念图的基本概念1. 定义:如果数据元素集合D中的各数据元素之间存在任意的前后件

45、关系,则此数据结构称为图.图通常用G表示;无向图: 在图中,如果对于任意的两个结点a与b,当结点a是结点b的前件(结点b是结点a的后件),且结点b也是结点a的前件(结点a也是结点b的后件)时,则称该图为无向图;有向图: 如果对于任意的两个结点a与b,当结点a是结点b的前件(结点b是结点a的后件),结点b不都是结点a的前件(结点a不都是结点b的后件)时,则称该图为有向图;66基本术语基本术语: :(1) 出度:在有向图中，一个顶点依附的弧尾数目(2) 入度:在有向图中，一个顶点依附的弧头数目(3) 结点的度:在图中，一个顶点依附的边或弧的数目(4) 有值图:在图的边或弧中给出相关的数，称为权。

46、权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网、有值图。672.6.1 图的基本概念_68在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图强连通图，否则称为非强连通图非强连通图。 强连通图和非强连通图示例。 A B D C 1 2 6 5 4 3 (a)强连通图 (b)非强连通图 图 2-18 强连通图和非强连通图 强连通图和非强连通图强连通图和非强连通图下面介绍几种常用的图的存储结构。（1 1）关联矩阵）关联矩阵 无向图的关联矩阵是对称矩阵，且对角线上的元素均为0。每一行的累加和为该结点的出度，每一列的累

47、加和为该结点的入度。（2 2）求值矩阵）求值矩阵（3 3）邻接表）邻接表（4 4）邻接多重表）邻接多重表692.6.2 图的存储结构_ 常用的图的遍历方法有纵向优先搜索法和横向优先搜索法两种。 1.1.纵向纵向优先搜索法优先搜索法基本思想:依次将图中的每一个结点作为当前结点,然后进行以下过程:(1) 处理或输出当前结点,并记录当前结点的查访标志;(2) 若当前结点有后件结点,则取第一个后件结点,若该后件结点未被查访过,则以该后件结点为当前结点,用纵向优先搜索法进行查访;702.6.3 图的遍历_ 2.2.横向横向优先搜索法优先搜索法基本思想: 依次从图的每一个结点出发,首先依次访问该结点的后件

48、结点,然后再顺序访问这些后件结点的所有未被访问过的后件结点,依次类推,直到所有被访问结点的后件结点均被访问结点的后件结点均被访问过为止.712.6.3 图的遍历_ 1.1.由由键盘输入生成图邻表键盘输入生成图邻表构造图邻接表的方法如下:(1) 根据图中的结点数建立一个顺序存储空间,(2) 然后依次对图中的每一个结点建立链接所有后件的单链表,过程如下:a.由键盘输入或从文件读入该结点的后件信息(结点编号和求值函数值),并为他们申请一个存放这些信息的新结点.b.将新结点链接到当前单链表的链头;这个过程直到图中该结点的所有后件信息输入完为止,接着建立图中下一个结点的所有后见的单链表;722.6.4

49、图邻接表类2.6.4 图邻接表类_ 2.输出图邻接表 3 纵向优先搜索法遍历 4 横向优先搜索法遍历图733.1 3.1 基本的查找技术基本的查找技术3.2 3.2 哈希表技术哈希表技术3.3 3.3 基本的排序技术基本的排序技术3.4 3.4 二叉排序树及其查找二叉排序树及其查找75 3.1 3.1 基本的查找技术基本的查找技术 查找是数据处理领域的一个重要内容,查找的效率将直接影响到数据处理的效率. 所谓查找是指在一个给定的数据结构中查找某个指定的元素.通常,根据不同的数据结构,应采用不同的查找方法.76 基本的查找技术包括基本的查找技术包括: :u顺序查找顺序查找u有序表的对分查找有序表

50、的对分查找u分块查找分块查找77 3.1.1 3.1.1 顺序查找顺序查找 顺序查找又称顺序搜索.顺序查找一般是指在线性表中查找指定的元素. 基本方法: 从线性表的第一个元素开始查找,依次将线性表中的元素与要查找的元素进行比较,如相等则查找成功,否则继续查找直到线性表的最后元素,若线性表的所有元素与被查元素都不相等,则表示线性表中没有要查的元素(查找失败).78 当要查找的元素在线性表中比较靠前的位置时,顺序查找效率较高,查找的元素在线性表中比较靠后的位置时,顺序查找效率较低. 在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进行比较.79 对于大的线性表来说,顺

51、序查找的效率是比较低的，但在以下两种情况下也只能采用顺序查找: (1) 线性表为无序表(表中的元素的排列是无序的),则顺序存储和链式存储结构都只能采用顺序查找. (2) 即使是有序线性表,如果采用链式存储结构,只能采用顺序查找.803.1.2 3.1.2 有序表的对分查找有序表的对分查找 对分查找只适用于顺序存储的有序表(线性表中的元素按值非递减排列的,从小到大,但允许相邻元素值相等) 设有序线性表的长度为N,被查元素为X,对分查找的方法如下: 将X与线性表的中间项进行比较:若中间项的值等于X,则查到,查找结束,若X小于中间项的值,则在线性表的前半部分以相同的方法查找;若X大于中间项的值,则在

52、线性表的后半部分以相同的方法查找. 直到查找成功或子表长度为0(线性表没有这个元素)为止.813.1.3 3.1.3 分块分块查找查找 分块查找又称索引顺序查找。它是一种顺序查找的改进方法,用于在分块有序表中进行查找。 所谓分块有序表是指将长度为N的线性表分为M个子表，M个子表长度可以相等或不等，但要求后一个子表中的每一个元素均大于前一个子表中的所有元素。823.2 3.2 哈希表技术哈希表技术 在3.1节中介绍的查找方法都是通过被查元素与表中的元素进行直接比较.本节将要介绍HASH表技术是另一类重要的查找技术. HASH表技术的基本思想是对被查元素的关键字做某种运算后直接确定所要查找项目在表

53、中的位置.833.2.13.2.1哈希表的基本概念哈希表的基本概念 1 1. .直接查找技术直接查找技术 设表的长度为N.如果存在一个函数I=I(K),对于表中的任意一个元素的关键字K,满足以下条件:1I N对于任意的元素关键字K1K2,恒存在I(K1) I(K2),称此表为直接查找表.函数I=I(K)称为关键字K的印象函数.84对直接查找表的操作主要有以下两种:(1) (1) 直接查找表的填入直接查找表的填入计算关键字K的印象函数I=I(K).将关键字K及有关元素信息填入到表的第I项.(2)(2)直接查找表的取出直接查找表的取出.计算关键字K的印象函数I=I(K)检查表中的第I项: 若第I项

54、为空,则说明表中没有关键字为K的元素;否则取出第I项中的元素即可.852.2.哈希表哈希表 哈希表技术是直接查找技术的推广,其主要目标是提高查找效率. 哈希表技术的关键是要处理好表中元素的冲突问题,它主要包括以下两方面的工作:(1)构造合适的HASH码,以便尽量减少表中元素的冲突的次数,即HASH码的均匀性要比较好。(2)当表中元素发生冲突时,要进行适当的处理。863. 3. 哈希码哈希码的构造的构造 哈希表技术的主要目标是提高查找效率,即要缩短查表的时间.因此,在实际设计HASH码时,要考虑以下两方面的因素.(1)使各关键字尽可能地分布在HASH表中，即HASH码的均匀性比较好,以便减少冲突

55、发生的机会。(2)哈希的计算要尽量简单。 通常以上两个方面在实际应用中是相互矛盾的,因此在实际设计HASH码时，要根据具体情况，选择一个合理的方案。87下面介绍一些比较简单的哈希码的构造方法：（1）截断法 截断法,是指与关键字对应的数字串中的一段(一般选取低位数)作为该关键字的哈希码.（2）分段叠加法 分段叠加法是将关键字的编码串分割为若干段,然后把他们叠加后再进行截断.（3）除法 这种方法是将关键字的编码除以表的长度,最后所得的余数作为哈希码,即取哈希码为 I I=MOD(=MOD(K,NK,N) )（4）乘法将关键字编码与一个常数相乘后，再除以表长度N取其余数作为哈希码。3.2.2 3.2

56、.2 几种常用的哈希表几种常用的哈希表 1. 线性哈希表 2. 随机哈希表 3. 溢出哈希表 4. 拉链哈希表 5. 指标哈希表893.3 基本的排序技术 排序也是数据处理的重要内容.所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。 排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对位置保持不变，即在原序列当中，RI=RJ,且RI在RJ之前，而在排序后的序列中，RI仍在RJ之前，则此算法稳定。稳定算法有：冒泡、插入、归并、基数不稳定算法有：选择、快速、希尔、堆排序903.3.1 3.3.1 冒泡排序与快速排序冒泡排序与快速排序1.

57、冒泡排序 冒泡排序是一种最简单的互换类排序方法，它是通过相邻数据元素的交换逐步将线性表变为有序。2.快速排序 冒泡排序只对相邻两个元素进行比较，只能消除一个逆序。快速排序可以实现通过一次交换而消除多个序列。 快速排序是一种互换类的排序方法，但由于它比冒泡排序的速度快，因此称为快速排序。913.3.2 3.3.2 简单插入排序与希尔排序简单插入排序与希尔排序 冒泡排序与快速排序本质上都是通过数据元素交换来逐步消除线性表中逆序。本小节讨论另一类排序的方法，即插入类排序。 1.1.简单插入排序简单插入排序 简单插入排序是指将无序序列的元素依次插入到已经有序的线性表中.92 2.2.希尔排序希尔排序

58、希尔排序属于插入类排序，但它对简单插入排序做了较大的改进。 其基本思想是将整个无序序列分割成若干小的子序列分别进行插入排序。933.3.3 3.3.3 简单选择排序与堆简单选择排序与堆排序排序1.1.简单选择排序简单选择排序选择排序的基本思想: 扫描整个线性表，从中选出最小元素。将它变换到表的最前面(这是它应有的位置)；然后对剩下的子表采用同样的方法，直到子表空为止。 对于长度为N的序列，选择排序需要扫描N-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该元素与子表中的第一个元素进行交换。942.2.堆排序堆排序堆排序属于选择类的排序方法。堆的定义:具有N个元素的序列(H1,H2, ,

59、HN),当且仅当满足（I=1,2,，N/2）时称之为堆。222121iiiiiiih hhhhhhh 或 953.3.4 其他排序方法简介1.1.归并排序归并排序所谓归并是将两个或两个以上的有序表合并成一个新的有序表。2.2.基数排序基数排序基数排序又称为吊桶排序，它属于分配类的排序方法。963.4 二叉排序树及其查找3.4.1 二叉排序树的基本概念所谓二叉排序树是指满足下列条件的二叉树：左子树上的所有结点值均小于根结点值。右子树上的所有结点值均不小于根结点值。左右子树也满足上述两个条件。973.4.2 3.4.2 二叉排序树的插入二叉排序树的插入根据二叉排序树的定义，二叉排序树的插入过程如下

60、:若当前的二叉树为空，则插入的元素为根结点。若插入的元素值小于根结点值，则将元素插入到左子树中。若插入的元素值不小于根结点值，则将元素插入到右子树中。983.4.3 3.4.3 二叉排序树的删除二叉排序树的删除 为了在二叉排序树中删除一个指定的元素，首先要找到被删元素所在的结点P与它的父结点Q。然后分为下面3种情况处理：（1）P为叶子结点(左右子树均为空)。此时直接删除该结点。（2）P为单支子树。此时，如果P是Q的左子结点，则将P的单支子树链接到Q的左指针上，否则将P的单支子树链接到Q的右指针上。（3）P的右子树和左子树都不为空。993.4.4 3.4.4 二叉排序树二叉排序树查找查找根据二叉