计算机数据结构第一章绪言.

数据结构是一门研究在非数值计算领域中“描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现”的学科。《数据结构》课程的地位和作用算法设计及实现的基础1.“数据结构”在计算机科学中是一门综合性的专业基础课。2.数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。3.数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。与相关课程联系线性代数数据结构离散数学程序设计概率论编译原理操作系统算法设计与分析人工智能数据库原理……学习目标及方法•了解数据的特性，学会数据的组织及其在计算机内部的表示方法•掌握基本的算法原理和设计•训练基本的、良好的程序设计技能•注重实践，项目驱动学习•继续保持“研学小组”学习方式•课程有一定难度，要重视教材与参考书：•严蔚敏，吴伟民编．《数据结构》（C语言版）．北京：清华大学出版，2007年．•吴艳等．《数据结构与算法实验教程》．北京：科学出版社，2006年．•严蔚敏吴伟民.数据结构题集(C语言版),清华大学出版社第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。对于数值计算问题，其数学模型通常是数学方程；而对于更多的非数值计算问题，其数学模型通常无法用数学方程加以描述。数据结构重点研究此类问题的处理。过去我们知道：程序=算法+数据结构本课程将深刻理解该问题。程序:计算机处理问题编制一组指令集.算法:处理问题的策略.数据结构:问题的数学模型.1.1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例1.1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。•算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。•数据的结构，直接影响算法的选择和效率。•上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。例１.2图书馆书目检索系统（表）（１）问题目标：自动检索（２）操作对象：书目信息（登录号、书名、作者名、分类号、出版单位、出版时间等）（３）对象关系：顺序排列（４）数学模型：线形数据结构类似问题有：查号系统、仓库帐户系统等001高等数学樊映川S01……002理论力学罗远祥L01……003高等数学华罗庚S01……004线性代数栾汝书S02……..………………………………………高等数学001,003,…理论力学002,…线性代数004,…樊映川001,…华罗庚003,…栾汝书004,…L002,…S001,003,…图1.1图书目录文件示例书名索引表作者索引表分类号索引表例1.3人机对弈问题（１）问题目标：计算机不仅要会看格局，还能预测棋局发展，做出决策。（２）操作对象：格局（３）对象关系：一个格局可派生出多个格局（４）数学模型：树形数据结构例1.3计算机和人对弈问题（树）○○××○××○××○××○××○×××××××○○○○○例1.4多叉路口交通灯的管理（１）问题目标：设计交通灯方案，使车辆相互不冲突，且流量最大CBAED（２）操作对象：顶点（表示通路，用两个字母表示，前者为出发点，后者为到达点）（３）对象关系：连线（表示通路之间的冲突关系）（４）数学模型：图例1.3多叉路口交通灯的管理问题（图）EABCD(b)表示通路的图11111112223344(a)五叉路口EDABACADBABCBDDADBDCEAEBEC通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。1.2基本概念和术语•数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。•数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。•一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。•数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。•数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。•数据结构主要指逻辑结构和物理结构•数据之间的相互关系称为逻辑结构。通常分为四类基本结构：–集合结构中的数据元素除了同属于一种类型外，别无其它关系。–线性结构结构中的数据元素之间存在一对一的关系。–树型结构结构中的数据元素之间存在一对多的关系。–图状结构或网状结构结构中的数据元素之间存在多对多的关系。集合线性树图数据的逻辑结构示例数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，R)其中：D是数据元素的有限集，R是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。abcd例线性表L=(D,R),D={a,b,c,d},R={(a,b),(b,c),(c,d)}顺序存储结构链式存储结构（单链表）Labcd^指针项可以有多个,以指示多个后继.例如,S=(D,R),D={a,b,c,d,e,f},R={(a,b),(a,c),(b,d),(b,e),(c,f)}abcfedd1d2d3d4d5d6ΛΛΛΛΛΛΛ1.3抽象数据类型的表示和实现数据类型(DataType)•一般的高级语言都提供了一些数据类型,如整数型,字符型等.数据类型是一个值的集合和定义在此集合上的一组操作的总称.用户还可以定义自己的数据类型.•数据类型可分为原子类型(不可分解的,如int,bool,char等)和结构类型(由其他类型构成)•数据类型为程序员提供了极大的方便:它将数据集合及其上的操作与其实现细节分离开来,或者说将数据的逻辑表示和运算与它们的实现相分离。程序员只需要了解此集合由哪些值构成,可以进行那些运算.抽象数据类型抽象数据类型(AbstractDataType简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作.抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述如下：（Ｄ，R，Ｐ）D是数据对象(性质相同的数据元素的有限集)。R是D上关系的有限集。P是对D的基本操作的有限集。抽象数据类型描述：ADT{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为基本操作名（参数表）初始条件：〈初始条件描述〉操作结果：〈操作结果描述〉“初始条件:描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果:说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。例1.4定义一个抽象数据类型——三元组ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3ElemSet}数据关系：R1={e1,e2,e2,e3}基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T，元素e1,e2,e3分别被赋以参数v1,v2,v3的值。DestroyTriplet(&T)操作结果：三元组T被销毁。Get(T,i,&e)初始条件：三元组T已存在，1i3操作结果：用e返回T的第i元的值。…………抽象数据类型的表示与实现通常采用类语言（类程序设计语言，如类C，类PASCAL等）作为描述工具，和程序设计语言相比，类语言具有以下特点：1.抽象性类语言抽象而简洁，描述算法时可忽略许多细节问题。2.可读性类语言算法忽略细节而突出了解题的思路和方法。3.适应性用类语言写的算法可以方便地转换为各种程序设计语言的程序。类C语言简介//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函数的类型，其值是函数结果状态代码typedefintStatus;(1)预定义常量和类型：(2)数据结构的表示(即存储结构)用类型定义(typedef)描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。(3)基本操作的算法都用以下形式的函数描述:函数类型函数名（函数参数表）{//算法说明语句序列}//函数名(3)．赋值语句•简单赋值：〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；〈变量〉++，它表示变量加1后赋值给变量；〈变量〉--，它表示变量减1后赋值给变量；•成组赋值：1.（〈变量1〉,〈变量2〉,〈变量3〉,…〈变量k〉）=（〈表达式1〉，〈表达式2〉,〈表达式3〉,…〈表达式k〉）;2.〈数组名1〉[下标1…下标2]=〈数组名2〉[下标1…下标2]；•串联赋值：〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；•条件赋值：〈变量名〉=〈条件表达式〉？〈表达式1〉：〈表达式2〉；•交换赋值：〈变量1〉←→〈变量2〉，表示变量1和变量2互换；(5)．条件选择语句if（〈表达式〉）语句；if（〈表达式〉）语句1；else语句2；情况语句switch（〈表达式〉）{case判断值1；语句组1；break；case判断值2；语句组2；break；……case判断值n；语句组n；break；[default：语句组n+1；]}•注意：switchcase语句是先计算表达式的值，然后用其值与判断值相比较，若它们相一致时，就执行相应的case下的语句组；若不一致，则执行default下的语句组；其中的方括号代表可选项。(7)．输入、输出语句•输入语句：用函数scanf实现，特别当数据为字符时，用getchar函数实现。•输出语句：用printf函数实现，特别当要输出字符数据时，用putchar函数实现。(6)循环语句：for（赋初值表达式；条件；修改表达式序列）语句；while（条件）语句；do{语句序列}while