数据结构实用教程

第1章绪论数据结构（C++描述）目录1.1什么是数据结构1.2算法的描述1.3算法分析1.4退出2．数据元素（dataelement）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。1.1基本术语1．数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。数据结构示例学号姓名性别籍贯电话通讯地址01张三男长沙8639000麓山南路327号02李四男北京23456789学院路435号03王五女广州30472589天河路478号04赵六男上海41237568南京路1563号05钱七女南京5013472南京大学06刘八女武汉61543726武汉大学07朱九男昆明4089651云南大学08孙十女杭州6154372西湖路635号图1-1学生数据表对于一个文本文件每一个字符就是一个数据元素，对于数组来说，每一个成分就是一个数据元素。数据项数据元素或数据记录3．数据对象（dataobject）是性质相同的数据元素组成的集合，是数据的一个子集。例如，整数数据对象的集合可表示为N＝{0，±1，±2…….}，字母字符数据对象的集合可表示为C={‘A’,’B’,…’Z’}。4．数据处理（dataprocessing）是指对数据进行检索、插入、删除、合并、拆分、排序、统计、简单计算、转换、输入和输出等操作。数据结构（datastructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。或者说，是指数据以及数据之间的联系。数据之间的相互联系称为数据的逻辑结构，数据的逻辑结构獨立于計算机，是数据本身所固有的。一种逻辑结构在计算机中的存储方式称为存储结构。存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。4．数据结构的抽象描述数据结构可用二元组D=(K,R)的形式来描述。其中，K={a1,a2,…,an}为元素集合，R={r1,r2,…,rm}为关系的集合，R上的一个关系r是序偶的集合，任一序偶x,y(x,y∈K)，把x叫做第一个元素或叫y的前驱，y为第二个元素或叫x的后继。用图可形象地表示为：（x，y）则表示x和y没有次序关系xyxy例2一种数据结构linearity=(K,R)，其中K={01,02,03,04,05,06,07,08,09,10},R={r}，r={05,01,01,03,03,08,08,02,02,07,07,04,04,06,06,09,09,10}05010308020704060910例1一种数据结构set=(K,R)，其中K={01,02,03,04,05,06,07,08,09,10},R={}Set中，只存在有元素的集合，不存在元素之间的关系，具有词中特点的数据结构被称为集合结构。职工号姓名性别出生日期职务部门01万明华男1952.03.20处长02赵宁男1958.06.14科长教材科03张利女1954.12.07科长教务科04赵书芳女1962.08.05主任办公室05刘永年男1949.08.15科员教材科06王明理女1965.04.01科员教材科07王敏女1962.06.28科员教务科08张才男1957.03.17科员教务科09马立仁男1965.10.12科员教务科10邢怀常男1966.07.05科员办公室表1-2教务处人事简表在此表中，每个元素有且仅有一个直接前驱，有且仅有一个直接后继，这种特点时数据元素之间的1：1练习，既线性结构。0102030405080910图树形结构抽象描述示意图0706例3一种数据结构tree=(K,R)，其中K={01,02,03,04,05,06,07,08,09,10},R={r}，r={01,02,01,03,01,04,02,05,02,06,03,07,03,08,03,09,04,10}在这棵树中，最上面的一个没有前驱只有后继，叫树根。最下面一层的只有后继没有前驱，叫树叶。除树根和树叶外，每一个结点有且仅有一个前驱，有任意多个后继，叫树枝。数据之间是1:N的联系，既是树形结构。例4一种数据结构graph=(K,R)，其中K={01,02,03,04,05,06,07,08,09,10},R={r}，r={01,02,02,01,01,04,04,01,02,03,03,02,02,06,06,02,02,07,07,02,03,07,07,03,04,06,06,04,05,07,07,05}0302010406070503020104060705数据之间是N:M的联系，既图形结构例5一种数据结构B=(K,R)，其中K={k1,k2,k3,k4,k5,k6},R={r1,r2}，r1={k3,k2,k3,k5,k2,k1,k5,k4,k5,k6}r2={k1,k2,k2,k3,k3,k4,k4,k5,k5,k6}k3k2k5k1k4k6此数据结构是图形结构，但是单纯的看，r1是树形结构，r2是线性结构从逻辑结构划分数据结构数据结构从逻辑结构划分为：（1）线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。（2）非线性结构元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。图形、树形结构从存贮结构划分数据结构数据结构从存贮结构划分为：(1)顺序存贮（向量存贮）所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式存贮所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)索引存贮使用该方存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。(4)散列存贮通过构造散列函数，用函数的值来确定元素存放的地址。在本书中，描述一种抽象数据类型将采用如下书写格式：ADT抽象数据类型名isData:数据描述Operations:操作声明END5。抽象数据类型（AbstractDataType）是指一个数据结构以及定义在该结构上的一组操作。4。数据类型（datatype）是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。例如，高级语言中用到的整数数据类型，是指由－32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。例如：设计矩形的一种抽象数据类型，其数据部分有长度和宽度，操作部分有初始化矩形的尺度、求周长、求面积。ADTRECtangleisData：floatlength，width；Operation：RectangleInitRectangle（floatlen，floatwid）；//根据长、宽度初始化矩形Circumference（Rectangler）；//返回给定矩形的周长Area（Rectangler）；//返回给定矩形的面积EndRECtangle下面来看看该抽象数据类型用C++如何实现：矩形的结构体类型名用Rectangle表示，定义如下：structRectangle{floatlength，width；}；操作部分如下：RectangleInitRectangle(floatlen,floatwid){Rectangler;r.length=len;r.width=wid;return(r);}floatCircumference(Rectangler){return2*(r.length+r.width);}floatArea(Rectangler){returnr.length*r.width;}voidmain(){floatx,y,p,s;Rectangler;cout“请输入一个矩形的长度和宽度!”endl;cinxy;r=InitRectangle(x,y);p=Circunference(r);s=Area(r);cout“矩形的周长为:”pendl;cout“矩形的面积为:”sendl;}第一课小结数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并要提供结构所定义的各种运算的算法。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。第一课小结逻辑结构通常分为四类基本结构：集合结构中的数据元素除了同属于一种类型外，别无其它关系。线性结构结构中的数据元素之间存在一对一的关系。树型结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。数据结构在计算机中有两种不同的表示方法：顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。1.2算法基本概念1．算法（algorithm）通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）（2）输出：至少产生一个输出，它们是算法执行完后的结果。（3）有穷性：每条指令的执行次数必须是有限的。（4)确定性：每条指令的含义都必须明确，无二义性。（5)可行性：即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。算法描述1．用流程图描述算法一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。开始为n个元素a1~an输入数值a1→x2→ii=nai→xi+1→i输出x结束aixNNYY2．用自然语言描述算法用我们日常生活中的自然语言（可以是中文形式，也可以是英形式）也可以描述算法。1)给n个元素a1~an输入数值；2)把第一个元素a1赋给用于保存最大值元素的变量；3)把表示下标的变量I赋初值2；4)如果I=n则向下执行，否则输出最大值x后结束算法；5)如果aix则将ai赋给x，否则不改变x的值，这是的x始终保存当前比较过的所有元素的最大值；6)使下标增1，以指示下一个元素；7)转向第（4）步继续执行；3．用其它方式描述算法我们还可以用数学语言或约定的符号语言来描述算法。4．用C++描述算法在本教材中，我们将采用C＋＋或类C++来描述算法。并且用C＋＋描述算法遵循如下规则：（1）所有算法的描述都用C＋＋中的函数形式函数类型函数名（形参及类型说明）{函数语句部分return(表达式值)；}5．算法和程序的关系算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。1.3算法评价算法设计的要求1、正确性算法应当满足具体问题的要求。2、可读性算法主要是为了人的阅读与交流，可读性好事有助于人对算法的了解。3、健壮性当输入非法数据时，算法也应能做出反应或进行处理，而不会产生莫名其妙的输出结果。4、效率与低存储量需求效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。1.3.5时间复杂度1．时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必