第1章-概论

教材:《数据结构简明教程》李春葆，清华大学出版社，2014参考书:1.数据结构（C语言版）严蔚敏清华大学出版社20092.数据结构教程(第4版)李春葆清华大学出版社2013(该书配套学习指导和上机指导）3.数据结构考研指导试题研究编写组机械工业出版社20094.数据结构习题与解析李春葆清华大学出版社2005数据结构课程学习要求•课前预习、认真听课、及时复习•认真独立完成实验•一定要多做练习，多动手编程Practicemakesperfect课程考核平时：40%（作业、实验、小测验）期末：60%（闭卷）授课教师：米天胜Email:[e-mail]前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程承上启下在计算机科学课程体系（偏软）中的地位C语言数据结构软件工程掌握基本编程方法掌握数据组织、表示和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）第1章概论教学要求建议学时：4学时总体要求:了解数据结构的意义，数据结构在计算机领域的地位和作用；掌握数据结构各名词、术语的含义和有关的基本概念；数据的逻辑结构和存储结构之间的关系；了解使用C语言对数据结构进行抽象数据类型的表示和实现的方法；了解算法的五要素；掌握计算语句频度、估算算法时间复杂度的方法教学要求•相关知识点–相关术语：数据、数据元素、数据项、数据对象、数据结构–数据逻辑结构：集合、线性结构、树和图–数据的物理结构：顺序和非顺序结构–算法的五要素和时间复杂度及空间复杂度•学习重点–数据的逻辑结构和存储结构及其之间的关系–算法时间复杂度及空间复杂度及其计算第1章概论1.1数据结构概述1.1.1什么是数据结构计算机数据运算的一般过程如图1.1所示。数据是信息的载体，能够被计算机识别、存储和加工处理，数据包括文字、表格、图像等。信息是数据的内涵，即数据所表达的意义，数据的基本单位是数据元素（有时称为结点、记录等），通常把数据元素作为一个整体进行处理。例如，一个班的学生数据包括张三、李四等数据元素。数据对象是具有相同类型的数据元素的集合，因为所有数据元素类型相同时处理起来更加方便，所以在数据结构中除特别指定外数据通常都是数据对象。有时一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立意义的不可分割的最小标识单位。例如在1～100的整数数据中，10就是一个数据元素；又比如在一个学生表中，一个学生记录可称为一个数据元素，而这个元素中的某一字段（如姓名）就是一个数据项。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，如图1.2所示。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合，因此，可时把数据结构看成是带结构的数据元素的集合。数据结构包括如下几个方面：（1）数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。（2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。（3）施加在该数据上的操作，即数据的运算。例如一个学生成绩表Score如表1.1所示，它由多个学生成绩记录（即数据元素）组成，每个元素又包括多个数据项，其中学号数据项是关键字，即学号唯一标识一个学生记录。现求计算所有学生的平均分。其数据运算是求所有学生的平均分。为了实现这个功能，先要设计对应的存储结构，即把Score表存放到计算机内存中，然后设计出实现求平均分的算法逻辑结构表示数据元素之间的逻辑关系称为数据的逻辑结构，数据逻辑结构主要是从数据元素之间的相邻关系来确定的。根据数据元素之间逻辑关系的不同特性，分为下列4类基本结构。1.1.2逻辑结构集合：所属的数据元素同属于一个集合（集合类型由于元素之间的关系过于松散，数据结构课程中较少讨论）。线性结构：所属的数据元素存在一对一的关系。树形结构：所属的数据元素存在一对多的关系。图形结构：所属的数据元素存在多对多的关系。也称为网状结构。数据的逻辑结构可以采用多种方式描述，二元组是一种既常用也十分通用的数据逻辑结构表示方式。二元组表示如下：S=(D,R)D={di|1≤i≤n}R={rj|1≤j≤m}其中，D是数据元素的有限集合，即D是由有限个数据元素（简称为元素）所构成的集合，R是D上的关系的有限集合，即R是由有限个关系rj（1≤j≤m）所构成的集合，而每个关系都是指从D→D的关系。每个关系rj用序偶集合来表示，用尖括号表示有向关系，如a,b表示存在元素a到b之间的关系；用圆括号表示无向关系，如（a,b）表示既存在元素a到b之间的关系，又存在元素b到a之间的关系。设rk是一个D到D的关系，rk∈R，若元素d，d'∈D，且d,d'∈rk，则称d'是d的后继元素，d是d'的前驱元素，这时d和d'是相邻的元素（都是相对rk而言的）；如果不存在一个d'使d,d'∈rk，则称d为rk的终端元素；如果不存在一个d'使d',d∈rk，则称d为r的开始元素；如果d既不是终端元素也不是开始元素，则称d是内部元素。S=(D,R)D={di|1≤i≤n}R={rj|1≤j≤m}从该表中看出，学号为201201的元素作为开始元素没有前驱元素，学号为201204的元素作为终端元素没有后继元素，除此之外，所有元素都只有一个前驱元素和一个后继元素，如学号为201205的学生记录的唯一前驱元素为学号为201201的学生记录，唯一后继元素为学号为201206的学生记录。由此可知，这个表的逻辑结构为线性结构。实际上，Score表完整地描述了该数据的逻辑结构，也可以用二元组表示其逻辑结构如下（用学号表示相应的元素）：Score=(D,R)D={201201,201202,201204,201205,201206}R={r}//只有一个逻辑关系r={201201,201205,201205,201206,201206,201202,201202,201204}【例1.1】设数据的逻辑结构如下：B1=(D,R)D={1,2,3,4,5,6,7,8,9}R={r}r={1,2,1,3,3,4,3,5,4,6,4,7,5,8,7,9}试画出对应的逻辑结构图，并指出哪些是开始结点，哪些是终端结点，说明是何种数据结构。解：B1对应的逻辑结构图如图1.3所示。其中1是开始结点，2、6、8、9是终端结点，除开始结点外，每个结点有唯一的前驱结点，除终端结点外，每个结点有一个或多个后继结点，所以它是一种树形结构。123456798图1.3B1的逻辑结构图【例1.2】设数据的逻辑结构如下：B2=(D,R)D={1,2,3,4,5,6}R={r}r={1,2,2,4,1,3,3,4,3,5,3,6,5,6}试画出对应的逻辑结构图，说明是何种数据结构。解：B2对应的逻辑结构图如图1.4所示，其中每个结点都零个或多个前驱结点，每个结点都零个或多个后继结点，所以每它是一种图形结构。图1.4B2的逻辑结构图1234561.1.3存储结构数据逻辑结构在计算机中的存储表示称为数据的存储结构，也称为物理结构。通常情况下，同一种逻辑结构可以设计多种存储结构，在不同的存储结构中，实现同一种运算的算法可能不同。逻辑结构、存储结构和运算三者之间的关系如图1.5所示。在将逻辑结构映射为存储结构时，不仅要存储逻辑结构中的所有元素，还要存储逻辑结构中元素之间的关系。下面简要介绍主要的几种存储结构。1．顺序存储结构顺序存储结构是采用一组连续的存储单元存放所有的数据元素，而且逻辑上相邻的元素的存储单元也相邻，也就是说，元素之间的逻辑关系由存储单元地址间的关系隐含表示，即顺序存储结构将数据的逻辑结构直接映射到存储结构。顺序存储结构可实现对各数据元素的随机存取。所谓随机存取是指给定某元素的逻辑序号，能在O(1)时间内查找到对应的元素）。对于前面的逻辑结构Score，假设每个元素占用30个字节，且从100号单元开始由低地址向高地址方向存储，对应的顺序存储结构如图1.6所示。2．链式存储结构链式存储结构中每个结点单独存储，无需占用一整块存储空间，但为了表示结点之间的关系，给每个结点附加指针字段，用于存放相邻结点的存储地址。对于前面的逻辑结构Score，在设计其链式存储结构时，每个结点存放一个学生成绩记录，每个结点附加一个“下一个结点地址”即后继指针域，用于存放后继结点的首地址，如图1.8所示，head作为第一个结点的地址来标识整个链式存储结构。201201王实85head201205李斌82201206刘英92201202张山78201204陈功90∧图1.8Score链式存储结构示意图3．索引存储结构索引存储结构是在存储数据表的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式如下：（关键字，相对地址）在索引表中，所有关键字有序排列（如递增），每个关键定的相对地址为该关键字的记录在数据表中的存储地址。如图1.9所示的是Score对应的一种索引存储结构。在进行关键字（如学号）查找时，先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字，然后通过对应地址在数据表中找到该记录的数据。4．哈希（散列）存储结构哈希存储结构是根据元素的关键字来确定其存储地址。具体做法是：以元素的关键字为自变量，通过某个哈希函数H(key)（或散列函数）计算出对应的函数值，再把该函数值当作该元素的存储地址。对于前面的逻辑结构Score，假设哈希表长度m=6（存储单元的地址为0～5），记录个数n=5，以学号作为自变量，选用哈希函数如下：H(学号)=学号-201201对于每个学生记录，计算的存储地址如下：key201201201205201206201202201204H(key)04513于是，可以得到如图1.10所示的哈希存储结构（其中2地址单元空闲）。如果要查找学号为id的学生记录，只需要求出H(id)，以它为地址在该哈希表中直接找到该学号的学生记录。1.1.4数据运算数据运算就是施加于数据的操作。如图1.5所示，数据运算包括运算定义和运算实现两部分，前者确定运算的功能，是抽象的，后者是在存储结构上确定对应运算实现算法，是具体的。这种将运算定义和运算实现相互分离的做法具体软件工程的思想，更加便于软件开发。1.1.5数据结构、数据类型和抽象数据类型数据结构是指带结构的数据元素的集合，包括数据逻辑结构、存储结构和数据运算。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。数据类型显式或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。例如，在16位计算机中，C语言的int（整型）数据类型隐含取值范围为-32768～32767，其运算有+、-、*、/、%等。因此可以认为，数据类型是在程序设计语言中已经实现了的数据结构。抽象数据类型（ADT）是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。对一个抽象数据类型进行定义时，必须给出它的名称及各运算的运算名称（即函数名），并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。在用高级程序语言（如C/C++语言）编写的程序中，通常需要对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。short（-32768～32767）+-*/%…从数据结构的角度看，一个求解问题可以通过抽象数据类型来描述，也就是说，抽象数据类型对一个求解问题从逻辑上进行了准确的定义，所以抽象数据类型由数据逻