武汉理工大学华夏学院 -信息工程系数 据 结 构教材：数据结构北京邮电大学出版社蹇强主编授课班级：软件 2071-2073
学时,64（ 48+16)
主讲教师：黄启荃武汉理工大学华夏学院 -信息工程系参考书：
1.《数据结构导学》
苏光奎编著,清华大学出版社
2.《数据结构》
严蔚敏编著,清华大学出版社
3.《数据结构上机实验与习题解析》
王成端主编,中国电力出版社武汉理工大学华夏学院 -信息工程系第一章 绪论计算机是用来处理数据的，而且它是用来处理大批量的数据。这些数据决不是杂乱无章的，而是有着某种内在联系的。
只有分清数据的内在联系，合理地组织数据，才能对其进行有效管理。如何合理组织数据，高效率地处理数据，正是本门课需要解决的问题。
武汉理工大学华夏学院 -信息工程系
早期的计算机主要用于科学计算，其使用的数据结构的特点是数据类型简单、算法复杂、侧重于建立程序－－数值计算；
现在，计算机从单纯的数值计算扩展为数据处理，即需要处理大量数据且数据类型从数字扩充为表格、声音、图像等，所以为有效处理它们，必须研究数据自身的内在结构。
1.1 数据结构概述武汉理工大学华夏学院 -信息工程系例 1.1 学生基本情况表学号 姓名 性别 年龄 籍贯 成绩 1 成绩 2 成绩 3
1001 张三 男 18 武汉 78 90 89
1002 李四 女 18 武汉 89 90 89
1003 王五 女 18 上海 78 90 89
1004 赵六 男 19 北京 78 90 89
在这类数据信息中，计算机处理的数据之间存在着 1-1的简单结构，称之为线性结构。
武汉理工大学华夏学院 -信息工程系例 1.2 企业人事管理－－称为树结构总经理研发部 销售部 人事部销售 1 销售 2… …
武汉理工大学华夏学院 -信息工程系例 1.3 网络中的通信线路图例如：在 N个城市之间建立通信线路（ N=7）
E
F
B
D C
G
A3
5
1
10
9
6
11
2 128
1 4
7
E
F
B
D C
G
A3
1 2
1 4
7
如何连线，使造价最少？
武汉理工大学华夏学院 -信息工程系
1.2 数据结构的基本概念
1,数据和信息 在计算机学科领域内，
数据的含义非常广泛。我们将一切能够输入到计算机中并被计算机处理的信息：
包括文字、表格、声音、图象等等都称为数据。例如：每一个学生班的学生基本情况和所学课程的成绩组成的一个表。
它是客观事物的符号表示 ；
信息指的是其含义，不同的数据形式可以传递相同的信息。
常用术语武汉理工大学华夏学院 -信息工程系
2,集合与关系
简单地说，集合是一堆物品（东西），每个物品称为集合中的元素，其元素间无次序的区分，
例如｛ abc,bcd,ert,chu,qwe｝是集合主要集合的元素之间常具有某种关系又称为联系，
一般说对一种集合而言可以定义一个或多个关系。例如：一个班的同学是一个集合，定义一个同寝室关系、领导关系等。
常用术语武汉理工大学华夏学院 -信息工程系
3.结点 又称为数据元素。它是组成数据的基本单位。如上例中的每一行表示了一个学生的基本情况及成绩。一般情况下，一个结点当中含有若干个数据项 ( 它是数据的最小的不能再分割的单位 )。
4.数据的逻辑结构 结点与结点之间的逻辑关系称为数据的逻辑结构。例如表 1－ 1的学生的基本情况表中，各结点之间存在着一种线性关系，它指出了各结点在表中的排列次序。
常用术语武汉理工大学华夏学院 -信息工程系
5,数据的物理结构 又称为数据的存储结构，它是数据在计算机中的存储表示。例如把表 1－ 1中的数据用数组表示存放在内存中；或者表示成文件存放到磁盘上。
6,数据结构 用抽象定义的方法定义为：对于一个二元组 B=(K,R)称为数据结构是指,K为结点的有限集合； R为结点上的关系集合，两者的有机结合称为数据结构。用教材上的方法定义为：把按某种逻辑关系组织起来的一组结点，按一定的存储方式存储于计算机中，并在其上定义了一个运算的集合，
就称为数据结构。
常用术语武汉理工大学华夏学院 -信息工程系
7,抽象数据类型 它是数学模型和在该模型商定义的操作集合的总称。是程序设计语言中数据类型概念的推广。当我们在分析复杂的情况或处理复杂的事物时，经常使用抽象的思维方式，即：舍去复杂系统中非本质的细节，提炼出反映系统主要宏观特性的内容，构成系统模型，再深入研究这些模型。可以认为一个软件系统是由一些数据结构、操作过程和控制机能组成的。因此在软件设计中，可以对三种不同的对象进行抽象 （过程抽象、控制抽象和数据抽象）,抽象数据类型就是对数据类型进一步抽象所形成的概念。
一般掌握的术语武汉理工大学华夏学院 -信息工程系定义 在大多数情况下，数据的逻辑结构可以用一个二元组
B=(K,R)来表示，这里 K为结点的有限集合； R为结点上的关系集合，例如：二元组
LIST={K,R1},TREE={K,R2},GRAPH={K,R3}分别描述了具有 5
个结点的三种不同的逻辑结构，其中：
K={A,B,C,D,E}
R1={<A,B>,<B,C>,<C,D>,<D,E>}
R2={<A,B>,<A,C>,<B,D>,<B,C>}
R3={<A,B>,<A,C>,<D,A>,<E,C>}
对于任意一种逻辑结构 B=(K,R),若 A,B属于 K,<A,B>
属于 R则称 A是 B的 前驱,B是 A的 后继,若某结点无前驱，则称此结点为 开始结点 ；若某结点无后继，则称此结点为 终端结点 。
1.3 数据结构的分类武汉理工大学华夏学院 -信息工程系数据的逻辑结构可分为 线性结构 和 非线性结构 两大类。
即：
线性结构数据的逻辑结构非线性结构表树图在线性结构中，除开始结点无前驱，终端结点无后继以外，其余结点都有且仅有一个前驱，有且仅有一个后继。
武汉理工大学华夏学院 -信息工程系在树结构中，除开始结点无前驱（称为树根 ),其余 结点都有且仅有一个前驱，而后继可以有多个，也可以有多个终端结点
（树叶）。
在图状结构中，每个结点的前驱和后继是任意个的。即图中可以没有开始结点和终端结点，也可以有多个开始结点和终端结点。
注意 !
武汉理工大学华夏学院 -信息工程系前例中 LIST属于线性结构－表； TREE属于树型结构－树； GRAPH属于图状结构－图。
数据的逻辑结构也可以用图示法来表示,
如图,
b
d e
ca
其二元组表示为,k={a,b,c,d,e} (顶点集合 )
R={<a,b>,<a,c>,<b,d>,<b,e>} （ 边的集合）。
武汉理工大学华夏学院 -信息工程系将数据存储到计算机中时，不仅要存储各结点的数值，更要存储各结点之间的逻辑关系。
将数据的值与其关系保存在计算机的内存中即为数据的存储结构。
存储数据的方法很多，常用的有顺序存储索引存储链式存储散列存储
1.4 数据的存储结构武汉理工大学华夏学院 -信息工程系顺序存储就是把逻辑上相邻的结点存储在一组地址连续的存储单元中，其结点之间的逻辑关系由存储单元地址之间的关系隐含表示。例如：
LIST={A,B,C,D,E}结构中，每一个结点占用一个存储单元，数据从 100号单元开始由低地址向高地址方向存放，则该表的存储结构为：
1,顺序存储
101 102 103 104100
B C D EA
图 1.2 顺序结构存储示意图武汉理工大学华夏学院 -信息工程系
1） 节省存储空间；
2） 逻辑上相邻结点在物理次序上也相邻，其存储地址可以用计算公式表示为：
LOC(I)=LOC(1)+(I-1)*L
其中 I逻辑序号为 I的结点
LOC(1)为开始结点的地址
L为每一个结点占用的存储单元数
3） 可以实现对结点的随机访问。
顺序存储的优点是,
不便于动态修改，即在对结点进行插入或删除操作时，要移动较多的结点。
顺序存储的缺点是：
武汉理工大学华夏学院 -信息工程系
2,链式存储链式存储就是给每一个结点增设一个指针字段，
用来存放其相邻结点的存储地址。这是在访问每一个结点时，即能知道该结点的数值，又能知道其相邻结点的地址。例如在 LIST={A,B,C,D,E}结构中，
对每一个结点增加一个“后继指针”字段来存放后继结点的地址，则每一个结点用两个数据域来表示，
一个域用来存储结点的数值，一个域用来存储后继结点的首地址，这样可得到图 1.3所示的链式结构存储示意图。
武汉理工大学华夏学院 -信息工程系链式存储的缺点 是不能对结点进行随机访问，因为逻辑上连续的结点在物理存储上不一定连续；同时其占用的存储单元数比顺序存储要多一些。
链式存储的优点 是适用于动态操作，即在插入或删除操作时只需要进行对指针字段域的修改就可以了。
100
102
104
106
108
A
D
C
B
E
106
108
102
104
∧
图 1.3链式结构存储示意图武汉理工大学华夏学院 -信息工程系索引存储是根据结点的序号来确定结点的存储地址的一种存储结点方法的。具体做法是,建立索引表和结点表，即将结点的数值按任意顺序存放在结点表中，而将每一个结点的地址按序存放在索引表中,图 1.4 LIST
的索引存储表示。
3 索引存储注意线性结构索引存储后，可以对结点进行随机访问，且进行插入或删除操作时 只需移动索引表中的存储地址,不需移动结点表中的结点值。
200
201
202
203
204
100
104
102
101
103
100
101
102
103
104
A
D
C
E
B
索引表 结点表图 1.4 LIST的索引存储示意图武汉理工大学华夏学院 -信息工程系
4 散列存储散列存储是根据结点的数值来确定结点的存储地址的一种存储方法。具体做法是,将结点的值作为自变量，通过某个函数（称为散列函数）求出函数值，并以这个函数值作为存储该结点的地址。 例 LIST=(33,49,12,64,86),选取散列函数 LOC(KEY)=KEY MOD 10,则得到散列存储结构如图 1.5所示。
数字域 12 33 64 86 49
地址值 1 2 3 4 5 6 7 8 9
图 1.5
散列存储的优点 是查找速度快，只要知道结点的数值，就可以计算出结点的存放地址。
武汉理工大学华夏学院 -信息工程系数据的运算是数据结构研究的一个重要内容，它与数据的逻辑结构、存储结构有着密切关系。 数据的各种运算都是在逻辑结构的基础上定义的，而其实现又必须在数据的存储结构上进行。
常见的数据运算有以下几种：
（ 1） 查找 在给定的数据结构中查找给定值的结点地址。
（ 2） 插入 在给定的数据结构中适当位置增加一个新结点。
（ 3） 删除 在给定的数据结构中删除某个结点
（ 4） 排序 重新排列线性结构中的各结点的逻辑顺序。
数据的运算用算法来表示。
其表示算法的方法即可以用程序表示，也可以用框图来表示。
1.4 数据的运算武汉理工大学华夏学院 -信息工程系前面介绍了数据的运算是用算法来表示的,
1.算法，实际上就是完成某一特定问题的求解步骤的有穷序列集合。
对于数据的任何一种运算，当数据的存储结构不同时，其算法描述一般也是不同的；即使在同一种存储结构下，其求解策略不同，算法描述也是不相同的。因此如何选择“好”的算法是程序设计必需要考虑的问题。
1.5 算法和算法分析
（ 1） 正确 算法必须满足问题的要求，即对合法的输入能产生求解问题的正确结果；对不合法的输入能作出相适应的反映并进行处理。
（ 2） 可读 能交流，它有助于人们对算法的理解、调试和修。
（ 3） 运行时间短
（ 4） 占用内存尽量少
2.好算法的特征武汉理工大学华夏学院 -信息工程系
(1) 算法效率的度量 算法执行的时间通常是用该算法编制的程序在计算机上运行时所消耗的时间来度量的，而度量方法常有两种：事后统计和事前分析估算。
(2) 取决因素 一个用高级语言编制的程序在计算机上运行时所消耗的时间取决于下列因素：
§ 依据的算法选用何种策略；
§ 问题的规模,例如：是求 100还是求
1000以内的素数；
§ 书写程序的语言,同一种算法,实现语言的级别越高，执行的效率就越低；
§ 编译程序所产生的机器代码的质量；
§ 机器执行指令的速度。
3,算法分析武汉理工大学华夏学院 -信息工程系这些因素说明：同一种算法用不同的语言实现、
或者用不同的编译程序进行编译、或者在不同的计算机上进行编译，其效率均不相同。即说明用绝对的时间单位衡量算法的效率是不合适的，而需要撇开这些与计算机硬件、软件有关的因素，只依赖于问题的规模来测算“运行工作量”的大小的方法对算法的优劣进行评价。
武汉理工大学华夏学院 -信息工程系
（ 3） 算法执行时间的计算方法算法执行时间等于算法中各语句执行时间的总和，
而某条语句的执行时间等于该语句执行一次所需时间与重复执行次数（称语句的频度）的乘积。
一个算法是由 控制结构（顺序、分支和循环） 和 原操作（指固有数据类型的操作） 构成的，则算法的执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该操作重复执行的次数作为算法的时间度量。为了分析方便，算法的执行时间通常表示成数量级的形式,T(N)=O(F(N))
其含义为：当问题规模 N足够大时，算法的执行时间 T(N)
和函数 F(N)成正比 。
武汉理工大学华夏学院 -信息工程系
(4) 时间复杂度 用数量级表示的算法执行时间 T(N)称为算法的时间复杂度。 一般情况下，对一个问题只需选择一种基本操作来讨论算法的事件复杂度即可，有时又要同时考虑几种基本操作，以反映执行不同操作所需要的相对时间，便于综合比较解决同一问题的两种完全不同的算法。
(5) 关于数量级,O” 概念的补充,O” 读作大 O，
若设某一种算法的执行时间用函数 T(N)表示，则
O(T(N))的意思是说：存在着一个正的常量 C和 N0,使得对于所有大于或等于 N0的整数 N,有 |T(N)|<=CG(N)成立。则称 O(T(N))＝ O( G(N))。
例如,T(N)=2N+10有 O(T(N))＝ O(N)
因为 取 C=3,N0=10时，有 2N+10<3N
成立。
武汉理工大学华夏学院 -信息工程系作业
P16
书面作业,
1.3,1.4,1.6,1.7
思考题,
1.1,1.2,1.5
武汉理工大学华夏学院 -信息工程系
(6) 时间复杂度的几种常见形式
O(1) 常量型，表示执行时间为常数
O(N) 线性型，表示执行时间呈线性增长
O(N2)平方型，表示执行时间呈平方性增长
O(N3)立方型，表示执行时间呈立方性增长还有 对数型 O(LOG N)和 指数型 O(2N)以及 O(N*LOG(N))
这七种类型的时间复杂度的增长率由小到大的排序为：
O(1),O(LOG N),O(N),O(N*LOG(N)),O(N2),O(N3) 和 O(2N)。
时间复杂度的增长率如下图所示。
时间复杂度
O(1)
O(LOGN) O(N)
O(N*LOG(N)) O(N2)
O(N3)
O(2N)
学时,64（ 48+16)
主讲教师：黄启荃武汉理工大学华夏学院 -信息工程系参考书：
1.《数据结构导学》
苏光奎编著,清华大学出版社
2.《数据结构》
严蔚敏编著,清华大学出版社
3.《数据结构上机实验与习题解析》
王成端主编,中国电力出版社武汉理工大学华夏学院 -信息工程系第一章 绪论计算机是用来处理数据的，而且它是用来处理大批量的数据。这些数据决不是杂乱无章的，而是有着某种内在联系的。
只有分清数据的内在联系，合理地组织数据，才能对其进行有效管理。如何合理组织数据，高效率地处理数据，正是本门课需要解决的问题。
武汉理工大学华夏学院 -信息工程系
早期的计算机主要用于科学计算，其使用的数据结构的特点是数据类型简单、算法复杂、侧重于建立程序－－数值计算；
现在，计算机从单纯的数值计算扩展为数据处理，即需要处理大量数据且数据类型从数字扩充为表格、声音、图像等，所以为有效处理它们，必须研究数据自身的内在结构。
1.1 数据结构概述武汉理工大学华夏学院 -信息工程系例 1.1 学生基本情况表学号 姓名 性别 年龄 籍贯 成绩 1 成绩 2 成绩 3
1001 张三 男 18 武汉 78 90 89
1002 李四 女 18 武汉 89 90 89
1003 王五 女 18 上海 78 90 89
1004 赵六 男 19 北京 78 90 89
在这类数据信息中，计算机处理的数据之间存在着 1-1的简单结构，称之为线性结构。
武汉理工大学华夏学院 -信息工程系例 1.2 企业人事管理－－称为树结构总经理研发部 销售部 人事部销售 1 销售 2… …
武汉理工大学华夏学院 -信息工程系例 1.3 网络中的通信线路图例如：在 N个城市之间建立通信线路（ N=7）
E
F
B
D C
G
A3
5
1
10
9
6
11
2 128
1 4
7
E
F
B
D C
G
A3
1 2
1 4
7
如何连线，使造价最少？
武汉理工大学华夏学院 -信息工程系
1.2 数据结构的基本概念
1,数据和信息 在计算机学科领域内，
数据的含义非常广泛。我们将一切能够输入到计算机中并被计算机处理的信息：
包括文字、表格、声音、图象等等都称为数据。例如：每一个学生班的学生基本情况和所学课程的成绩组成的一个表。
它是客观事物的符号表示 ；
信息指的是其含义，不同的数据形式可以传递相同的信息。
常用术语武汉理工大学华夏学院 -信息工程系
2,集合与关系
简单地说，集合是一堆物品（东西），每个物品称为集合中的元素，其元素间无次序的区分，
例如｛ abc,bcd,ert,chu,qwe｝是集合主要集合的元素之间常具有某种关系又称为联系，
一般说对一种集合而言可以定义一个或多个关系。例如：一个班的同学是一个集合，定义一个同寝室关系、领导关系等。
常用术语武汉理工大学华夏学院 -信息工程系
3.结点 又称为数据元素。它是组成数据的基本单位。如上例中的每一行表示了一个学生的基本情况及成绩。一般情况下，一个结点当中含有若干个数据项 ( 它是数据的最小的不能再分割的单位 )。
4.数据的逻辑结构 结点与结点之间的逻辑关系称为数据的逻辑结构。例如表 1－ 1的学生的基本情况表中，各结点之间存在着一种线性关系，它指出了各结点在表中的排列次序。
常用术语武汉理工大学华夏学院 -信息工程系
5,数据的物理结构 又称为数据的存储结构，它是数据在计算机中的存储表示。例如把表 1－ 1中的数据用数组表示存放在内存中；或者表示成文件存放到磁盘上。
6,数据结构 用抽象定义的方法定义为：对于一个二元组 B=(K,R)称为数据结构是指,K为结点的有限集合； R为结点上的关系集合，两者的有机结合称为数据结构。用教材上的方法定义为：把按某种逻辑关系组织起来的一组结点，按一定的存储方式存储于计算机中，并在其上定义了一个运算的集合，
就称为数据结构。
常用术语武汉理工大学华夏学院 -信息工程系
7,抽象数据类型 它是数学模型和在该模型商定义的操作集合的总称。是程序设计语言中数据类型概念的推广。当我们在分析复杂的情况或处理复杂的事物时，经常使用抽象的思维方式，即：舍去复杂系统中非本质的细节，提炼出反映系统主要宏观特性的内容，构成系统模型，再深入研究这些模型。可以认为一个软件系统是由一些数据结构、操作过程和控制机能组成的。因此在软件设计中，可以对三种不同的对象进行抽象 （过程抽象、控制抽象和数据抽象）,抽象数据类型就是对数据类型进一步抽象所形成的概念。
一般掌握的术语武汉理工大学华夏学院 -信息工程系定义 在大多数情况下，数据的逻辑结构可以用一个二元组
B=(K,R)来表示，这里 K为结点的有限集合； R为结点上的关系集合，例如：二元组
LIST={K,R1},TREE={K,R2},GRAPH={K,R3}分别描述了具有 5
个结点的三种不同的逻辑结构，其中：
K={A,B,C,D,E}
R1={<A,B>,<B,C>,<C,D>,<D,E>}
R2={<A,B>,<A,C>,<B,D>,<B,C>}
R3={<A,B>,<A,C>,<D,A>,<E,C>}
对于任意一种逻辑结构 B=(K,R),若 A,B属于 K,<A,B>
属于 R则称 A是 B的 前驱,B是 A的 后继,若某结点无前驱，则称此结点为 开始结点 ；若某结点无后继，则称此结点为 终端结点 。
1.3 数据结构的分类武汉理工大学华夏学院 -信息工程系数据的逻辑结构可分为 线性结构 和 非线性结构 两大类。
即：
线性结构数据的逻辑结构非线性结构表树图在线性结构中，除开始结点无前驱，终端结点无后继以外，其余结点都有且仅有一个前驱，有且仅有一个后继。
武汉理工大学华夏学院 -信息工程系在树结构中，除开始结点无前驱（称为树根 ),其余 结点都有且仅有一个前驱，而后继可以有多个，也可以有多个终端结点
（树叶）。
在图状结构中，每个结点的前驱和后继是任意个的。即图中可以没有开始结点和终端结点，也可以有多个开始结点和终端结点。
注意 !
武汉理工大学华夏学院 -信息工程系前例中 LIST属于线性结构－表； TREE属于树型结构－树； GRAPH属于图状结构－图。
数据的逻辑结构也可以用图示法来表示,
如图,
b
d e
ca
其二元组表示为,k={a,b,c,d,e} (顶点集合 )
R={<a,b>,<a,c>,<b,d>,<b,e>} （ 边的集合）。
武汉理工大学华夏学院 -信息工程系将数据存储到计算机中时，不仅要存储各结点的数值，更要存储各结点之间的逻辑关系。
将数据的值与其关系保存在计算机的内存中即为数据的存储结构。
存储数据的方法很多，常用的有顺序存储索引存储链式存储散列存储
1.4 数据的存储结构武汉理工大学华夏学院 -信息工程系顺序存储就是把逻辑上相邻的结点存储在一组地址连续的存储单元中，其结点之间的逻辑关系由存储单元地址之间的关系隐含表示。例如：
LIST={A,B,C,D,E}结构中，每一个结点占用一个存储单元，数据从 100号单元开始由低地址向高地址方向存放，则该表的存储结构为：
1,顺序存储
101 102 103 104100
B C D EA
图 1.2 顺序结构存储示意图武汉理工大学华夏学院 -信息工程系
1） 节省存储空间；
2） 逻辑上相邻结点在物理次序上也相邻，其存储地址可以用计算公式表示为：
LOC(I)=LOC(1)+(I-1)*L
其中 I逻辑序号为 I的结点
LOC(1)为开始结点的地址
L为每一个结点占用的存储单元数
3） 可以实现对结点的随机访问。
顺序存储的优点是,
不便于动态修改，即在对结点进行插入或删除操作时，要移动较多的结点。
顺序存储的缺点是：
武汉理工大学华夏学院 -信息工程系
2,链式存储链式存储就是给每一个结点增设一个指针字段，
用来存放其相邻结点的存储地址。这是在访问每一个结点时，即能知道该结点的数值，又能知道其相邻结点的地址。例如在 LIST={A,B,C,D,E}结构中，
对每一个结点增加一个“后继指针”字段来存放后继结点的地址，则每一个结点用两个数据域来表示，
一个域用来存储结点的数值，一个域用来存储后继结点的首地址，这样可得到图 1.3所示的链式结构存储示意图。
武汉理工大学华夏学院 -信息工程系链式存储的缺点 是不能对结点进行随机访问，因为逻辑上连续的结点在物理存储上不一定连续；同时其占用的存储单元数比顺序存储要多一些。
链式存储的优点 是适用于动态操作，即在插入或删除操作时只需要进行对指针字段域的修改就可以了。
100
102
104
106
108
A
D
C
B
E
106
108
102
104
∧
图 1.3链式结构存储示意图武汉理工大学华夏学院 -信息工程系索引存储是根据结点的序号来确定结点的存储地址的一种存储结点方法的。具体做法是,建立索引表和结点表，即将结点的数值按任意顺序存放在结点表中，而将每一个结点的地址按序存放在索引表中,图 1.4 LIST
的索引存储表示。
3 索引存储注意线性结构索引存储后，可以对结点进行随机访问，且进行插入或删除操作时 只需移动索引表中的存储地址,不需移动结点表中的结点值。
200
201
202
203
204
100
104
102
101
103
100
101
102
103
104
A
D
C
E
B
索引表 结点表图 1.4 LIST的索引存储示意图武汉理工大学华夏学院 -信息工程系
4 散列存储散列存储是根据结点的数值来确定结点的存储地址的一种存储方法。具体做法是,将结点的值作为自变量，通过某个函数（称为散列函数）求出函数值，并以这个函数值作为存储该结点的地址。 例 LIST=(33,49,12,64,86),选取散列函数 LOC(KEY)=KEY MOD 10,则得到散列存储结构如图 1.5所示。
数字域 12 33 64 86 49
地址值 1 2 3 4 5 6 7 8 9
图 1.5
散列存储的优点 是查找速度快，只要知道结点的数值，就可以计算出结点的存放地址。
武汉理工大学华夏学院 -信息工程系数据的运算是数据结构研究的一个重要内容，它与数据的逻辑结构、存储结构有着密切关系。 数据的各种运算都是在逻辑结构的基础上定义的，而其实现又必须在数据的存储结构上进行。
常见的数据运算有以下几种：
（ 1） 查找 在给定的数据结构中查找给定值的结点地址。
（ 2） 插入 在给定的数据结构中适当位置增加一个新结点。
（ 3） 删除 在给定的数据结构中删除某个结点
（ 4） 排序 重新排列线性结构中的各结点的逻辑顺序。
数据的运算用算法来表示。
其表示算法的方法即可以用程序表示，也可以用框图来表示。
1.4 数据的运算武汉理工大学华夏学院 -信息工程系前面介绍了数据的运算是用算法来表示的,
1.算法，实际上就是完成某一特定问题的求解步骤的有穷序列集合。
对于数据的任何一种运算，当数据的存储结构不同时，其算法描述一般也是不同的；即使在同一种存储结构下，其求解策略不同，算法描述也是不相同的。因此如何选择“好”的算法是程序设计必需要考虑的问题。
1.5 算法和算法分析
（ 1） 正确 算法必须满足问题的要求，即对合法的输入能产生求解问题的正确结果；对不合法的输入能作出相适应的反映并进行处理。
（ 2） 可读 能交流，它有助于人们对算法的理解、调试和修。
（ 3） 运行时间短
（ 4） 占用内存尽量少
2.好算法的特征武汉理工大学华夏学院 -信息工程系
(1) 算法效率的度量 算法执行的时间通常是用该算法编制的程序在计算机上运行时所消耗的时间来度量的，而度量方法常有两种：事后统计和事前分析估算。
(2) 取决因素 一个用高级语言编制的程序在计算机上运行时所消耗的时间取决于下列因素：
§ 依据的算法选用何种策略；
§ 问题的规模,例如：是求 100还是求
1000以内的素数；
§ 书写程序的语言,同一种算法,实现语言的级别越高，执行的效率就越低；
§ 编译程序所产生的机器代码的质量；
§ 机器执行指令的速度。
3,算法分析武汉理工大学华夏学院 -信息工程系这些因素说明：同一种算法用不同的语言实现、
或者用不同的编译程序进行编译、或者在不同的计算机上进行编译，其效率均不相同。即说明用绝对的时间单位衡量算法的效率是不合适的，而需要撇开这些与计算机硬件、软件有关的因素，只依赖于问题的规模来测算“运行工作量”的大小的方法对算法的优劣进行评价。
武汉理工大学华夏学院 -信息工程系
（ 3） 算法执行时间的计算方法算法执行时间等于算法中各语句执行时间的总和，
而某条语句的执行时间等于该语句执行一次所需时间与重复执行次数（称语句的频度）的乘积。
一个算法是由 控制结构（顺序、分支和循环） 和 原操作（指固有数据类型的操作） 构成的，则算法的执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该操作重复执行的次数作为算法的时间度量。为了分析方便，算法的执行时间通常表示成数量级的形式,T(N)=O(F(N))
其含义为：当问题规模 N足够大时，算法的执行时间 T(N)
和函数 F(N)成正比 。
武汉理工大学华夏学院 -信息工程系
(4) 时间复杂度 用数量级表示的算法执行时间 T(N)称为算法的时间复杂度。 一般情况下，对一个问题只需选择一种基本操作来讨论算法的事件复杂度即可，有时又要同时考虑几种基本操作，以反映执行不同操作所需要的相对时间，便于综合比较解决同一问题的两种完全不同的算法。
(5) 关于数量级,O” 概念的补充,O” 读作大 O，
若设某一种算法的执行时间用函数 T(N)表示，则
O(T(N))的意思是说：存在着一个正的常量 C和 N0,使得对于所有大于或等于 N0的整数 N,有 |T(N)|<=CG(N)成立。则称 O(T(N))＝ O( G(N))。
例如,T(N)=2N+10有 O(T(N))＝ O(N)
因为 取 C=3,N0=10时，有 2N+10<3N
成立。
武汉理工大学华夏学院 -信息工程系作业
P16
书面作业,
1.3,1.4,1.6,1.7
思考题,
1.1,1.2,1.5
武汉理工大学华夏学院 -信息工程系
(6) 时间复杂度的几种常见形式
O(1) 常量型，表示执行时间为常数
O(N) 线性型，表示执行时间呈线性增长
O(N2)平方型，表示执行时间呈平方性增长
O(N3)立方型，表示执行时间呈立方性增长还有 对数型 O(LOG N)和 指数型 O(2N)以及 O(N*LOG(N))
这七种类型的时间复杂度的增长率由小到大的排序为：
O(1),O(LOG N),O(N),O(N*LOG(N)),O(N2),O(N3) 和 O(2N)。
时间复杂度的增长率如下图所示。
时间复杂度
O(1)
O(LOGN) O(N)
O(N*LOG(N)) O(N2)
O(N3)
O(2N)
