数据结构在计算机中的标识课件

1课程介绍l教材：数据结构（C语言版）严蔚敏、吴伟民编 清华大学出版社 学时：48学时 上机：48学时 学习方法：多思考、多练习课外2课程性质及学习方法l课程性质：专业基础课 核心课程l学习方法l 多思考、多练习l 多写程序l 多读程序l 多上机l 少背书3第一章 绪 论1.1 数据结构的概念1.2 抽象数据类型1.3 算法和算法分析 1.3.1 算法 1.3.2 算法描述 1.3.3 算法性能分析与度量4 第一章 绪 论l计算机科学是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：l 信息的表示 信息的处理 而信息的表示和处理又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。5l1.1数据结构的概念l1.1.1 为什么要学习数据结构 l众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。l 例1、电话号码查询系统l 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：l (a1，b1)(a2，b2)(an，bn)l其中ai，bi(i=1，2n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够给出报告没有这个人的标志。6l 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。l 数据的结构，直接影响算法的选择和效率。l 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1in 数据结构还要提供每种结构类型所定义的数据结构还要提供每种结构类型所定义的各种运算的算法。各种运算的算法。7除电话号码自动查号系统外，还有许多诸如此类的问题，如：学生信息检索系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。学生信息检索系统：当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。8学生信息检索系统：学号 姓名性别 专业年级980001吴承志 男计算机科学与技术 98级 980002李淑芳 女信息与计算科学 98级 990301刘 丽 女数学与应用数学 99级 990302张会友 男信息与计算科学99级 990303石宝国 男计算机科学与技术99级 000801何文颖 女计算机科学与技术2000级 000802赵胜利 男数学与应用数学 2000级 000803崔文靖 男信息与计算科学 2000级 010601刘 丽 女计算机科学与技术2001级 010602魏永鸣 男数学与应用数学2001级 （a）学生信息表 9崔文靖 8何文颖 6李淑芳 2刘 丽 3，9石宝国 5魏永鸣 10吴承志 1赵胜利 7张会有 4（b）姓名索引表 计算机科学与技术 1，5，6，9 信息与计算科学 2，4，8 数学与应用数学 3，7，10 2000级 6，7，8 2001级 9，10 98级 1，2，3 99级 4，5 （c）专业索引表（d）年级索引表 线形结构10例2、八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。11图1.2 四皇后问题中隐含的状态树 树型结构12例3 教学计划编排问题l一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边，则表示课程i必须先于课程j进行。13 （a）计算机专业的课程设置 14图1.3 教学计划编排问题的数据结构l图型结构 （b）表示课程之间优先关系的有向图 15 由以上几个例子可以直接地认为：数据结构就是研究由以上几个例子可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的类型。到的新结构仍然是原来的类型。由以上几个例子可见，描述这类非数值计算问题的数由以上几个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。的关系和操作的学科。学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高思维能力，通过程序设计的技能训练来促进综合应用能力和素质的提高。161.1.2 有关概念和术语 l数据（Data）：是信息的载体，它能够被计算机识别、存储和加工处理。计算机科学中，所谓数据就是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。l数据元素（Data Element）：是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。l数据对象（Data Object）或数据元素类（Data Element Class）：是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。l例、整数的数据对象是-3，-2，-1，0，1，2，3，l数据结构（Data Structure）：指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的关系，这种数据元素之间的关系称为结构。17据数据元素间关系不同特性，通常有下列四类基本结构：据数据元素间关系不同特性，通常有下列四类基本结构：集合结构 线形结构树状结构网状结构数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。18数据结构的形式定义为：数据结构是 一个二元组：Data_Structure（D，R）其中：D是数据元素的有限集 R是D上关系的有限集 19数据结构包括数据的逻辑结构和数据的物理结构。数据的数据的逻辑结构逻辑结构可以看作是从具可以看作是从具体问题抽象出来的数学模型，它体问题抽象出来的数学模型，它与数据的存储无关。我们研究数与数据的存储无关。我们研究数据结构的目的是为了在计算机中据结构的目的是为了在计算机中实现对它的操作，为此还需要研实现对它的操作，为此还需要研究如何在计算机中表示一个数据究如何在计算机中表示一个数据结构。结构。数据结构在计算机中的标识（又数据结构在计算机中的标识（又称映像）称为数据的称映像）称为数据的物理结构物理结构，或称或称存储结构存储结构。它所研究的是数。它所研究的是数据结构在计算机中的实现方法，据结构在计算机中的实现方法，包括数据结构中元素的表示及元包括数据结构中元素的表示及元素间关系的表示。素间关系的表示。数据数据的存的存储结储结构可构可采用采用顺序存储方法顺序存储方法:是是用数据元素在存储器中的相对位置来表示用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系数据元素之间的逻辑关系。顺序存储结构是一种最基本的存顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。储表示方法，通常借助于程序设计语言中的数组来实现。链式存储方法链式存储方法:在每一个数据元素中增加一个存放地址的指在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。针，用此指针来表示数据元素之间的逻辑关系。对逻辑上相对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，链式存储结构通常借助于程序设计语设的指针字段来表示，链式存储结构通常借助于程序设计语言中的指针类型来实现。言中的指针类型来实现。除了通常采用的顺序存储方法和链式存储方法外，有时除了通常采用的顺序存储方法和链式存储方法外，有时为了查找的方便还采用为了查找的方便还采用索引存储方法索引存储方法和和散列存储方法散列存储方法。201.1.3：数据结构课程的内容 方面 层次数据表示数据处理抽象 逻辑结构 基本运算实现 存储结构 算 法评价 不同数据结构的比较及 算法分析21 1.2 抽象数据类型 l1.2.1 数据类型:在一种程序设计语言中，变量所具有的数据种类。l类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。l数据类型（Data Type）是一个值的集合和定义在这个值集上的一组操作的总称。l例1、在FORTRAN语言中：变量的数据类型有整型、实型、和复数型 l例2、在C语言中，数据类型：基本类型和构造类型l基本类型：整型、浮点型、字符型l构造类型：数组、结构、联合、指针、枚举型、自定义22l1.2.2 抽象数据类型 l是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型一般可以由元素、关系及操作三种要素来定义。l 抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。l用三元组描述如下：（，）抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。231.3 算法和算法分析 l1.3.1 1.3.1 算法特性算法特性 l算法（算法（Algorithm）是对特定问题求解步骤的一种描述，是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个是指令的有限序列。其中每一条指令表示一个或多个操作。操作。l算法的五个特征：算法的五个特征：1.有有穷穷性性。一一个个算算法法必必须须在在有有穷穷步步之之后后结结束束，即即必必须须在在有有限限时时间间内完成。内完成。2.确确定定性性。算算法法的的每每一一步步必必须须有有确确切切的的定定义义，无无二二义义性性。算算法法的的执行对应着的相同的输入仅有唯一的一条路经。执行对应着的相同的输入仅有唯一的一条路经。3.可可行行性性（有有效效性性）。算算法法中中的的每每一一步步都都可可以以通通过过已已经经实实现现的的基基本运算的有限次执行得以实现。本运算的有限次执行得以实现。4.输输入入。一一个个算算法法具具有有零零个个或或多多个个输输入入，这这些些输输入入取取自自特特定定的的数数据对象集合。据对象集合。5.5.输出。一个算法具有一个或多个输出，这些输出是同输输出。一个算法具有一个或多个输出，这些输出是同输 入之间存在某种特定的关系的量。入之间存在某种特定的关系的量。24算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)算法应满足具体问题的需求，预先规定的功能和性能要求。(2)可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。251.3.3 算法性能分析与度量 l可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。l将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：1.硬件的速度 2.书写程序的语言 3.编译程序所生成目标代码的质量 4.问题的规模 26时间复杂度 l一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。l定义（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，有：lf(n)cg(n)l则有：lf(n)(g(n)指程序运行从开始到结束所需要的时间。例:一个程序的实际执行时间为T(n)2.7n3+3.8n2+5.3。则T(n)(n3)。使用大记号表示的算法的时间复杂度，称为算法的渐进时间复杂度（Asymptotic Complexity）。27一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作：T(n)=O(f(n)例、for(I=1，I=n;+I)for(j=1;j=n;+j)cIj=0;for(k=1;k=n;+k)cIj+=aIk*bkj;由于是一个三重循环，每个循环从1到n，则总次数为:nnn=n3时间复杂度为：T(n)=O(n3)频度：是指语句重复执行的次数28l例+x;s=0;l分析：将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)；l如果将s=0也看成是基本操作，则语句频度l为，其时间复杂度仍为(1)，即常量阶。l例、for(I=1;I=n;+I)l +x;s+=x;语句频度为：2n其时间复杂度为：O(n)即时间复杂度为线性阶l例、for(I=1;I=n;+I)lfor(j=1;j=n;+j)l +x;s+=x;语句频度为：2n2其时间复杂度为：O(n2)，即时间复杂度为平方阶。29l定理：若A(n)=a m n m+a m-1 n m-1+a1n+a0是一个m次多项式，则A(n)=O(n m)证略。例for(i=2;i=n;+I)for(j=2;j=i-1;+j)+x;ai，j=x;l语句频度为：l 1+2+3+n-2l =(1+n-2)(n-2)/2l =(n-1)(n-2)/2l =n2-3n+2l时间复杂度为O(n2)l即此算法的时间复杂度为平方阶.一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。30l通常用(1)表示常数计算时间。常见的渐进时间复杂度有:l(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)这几种计算算法时间的多项式是最常用的。l指数时间的l关系为：O(2n)O(n!)1&change;-I)l change=false;l for(j=0;jaj+1)l aj aj+1;l change=TURE;l l l 最好情况：0次l最坏情况：1+2+3+n-1=n(n-1)/2平均时间复杂度为:O(n2)322.空间复杂度l一个程序的空间复杂度（Space complexity）是指程序运行从开始到结束所需的存储量。l算法所需存储空间的度量,记作:S(n)=O(f(n)l其中n为问题的规模(或大小)程序运行所需的存储空间包括以下两部分：固定部分。这部分空间与所处理数据大小和个数无关,或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100个数据元素的排序算法与1000个数据元素的排序算法所需的存储空间显然是不同的。