计算机数据结构 第1章 绪论

第1章绪论什么是数据结构基本概念和术语抽象数据类型的表示与实现算法和算法分析1.1什么是数据结构数值计算问题的计算机解决例鸡兔同笼问题：鸡和兔共n个头，m个脚，求各有多少？数学模型，二元一次方程组求解x+y=n和2x+4y=mx=(4n-m)/2和y=n-x的自然数（包括0）程序输入n和m计算x=(4n-m)/2和y=n-x判断x和y是否满足条件但是在实际中，很多是非数值计算问题例1书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例2人机对奕问题树……..……..…...…...…...…...例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图结论当前计算机的应用特点数据是各式各样的数据之间的联系也有多种情况不再仅仅是数值计算，大量的是非数值计算，通常要对数据进行组织、管理和检索等。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容为了解决这些问题我们该怎么做?!背景知识1968年开始独立开设《数据结构》课程1968年，唐.欧.克努特,《计算机程序设计技巧》第一卷《基本算法》面向过程的程序设计思想程序＝算法＋数据结构软件=程序+文档数据结构没有统一的定义数据结构仍然在不断发展中逻辑结构存储结构算法算法的分析指数据元素之间抽象化的相互关系。独立于计算机，是数据本身所固有的。

数据的逻辑结构在计算机中的存储形式(映象)。数据结构在计算机中的表示方法顺序影象——顺序存储结构非顺序影象——链式存储结构用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。在每一个数据元素中增加一个存放地址的指针(pointer)，用此指针来表示数据元素之间的逻辑关系。《数据结构》的研究内容是对信息的一种符号表示——人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。数据(Data)

在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称——包括数值型数据和非数值型数据

(包括文字、表格、图象、声音等，都称为数据)。数据元素(DataElement)：(也称结点)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的数据项(字段、域(field))，故不是组成数据的最小单位。数据项(dataitem)

是数据的不可分割的最小单位。1.2基本概念和术语数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构集合：数据元素除了同属于一种类型外，别无其它关系。线性结构：一对一。树型结构：一对多。图状结构或网状结构：多对多。数据结构的形式定义数据结构是一个二元组DataStructure=(D,S)其中D是数据元素的有限集，S是D上关系的有限集例4复数定义复数是一种数据结构，Complex=(C,R)其中C是两个实数的集合{c1,c2}；R={P}，P是定义在集合C上的一种关系{<c1,c2>}，其中有序偶<c1,c2>表示c1是复数的实部，c2是复数的虚部。逻辑结构和物理结构逻辑结构数据元素之间的逻辑关系物理结构数据结构在计算机中的表示又称为存储结构包括数据的表示和关系的表示顺序映像顺序存储结构借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系非顺序映像链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系数据的逻辑结构和物理结构是密切相关的两个方面任何一个算法的设计取决与选定的数据（逻辑）结构算法的实现依赖于算法的存储结构数据类型数据类型是一个值的集合和定义在这个集合上的一组操作的总称数据类型分类原子类型：类型的值是不可分解的结构类型：类型的值是由若干成分按某种结构组成，是可分解的。抽象数据类型ADT一个数学模型以及定义在该模型上的一组操作定义仅取决于它的一组逻辑特性，与计算机内部表示和实现无关抽象数据类型的分类原子类型值是不可分解的固定聚合类型值由确定数目的成分按某种结构组成可变聚合类型值得成分的数目不定ADT抽象数据类型名

{

数据对象:〈数据对象的定义〉

数据关系:〈数据关系的定义〉

基本操作:〈基本操作的定义〉

}ADT

抽象数据类型名抽象数据类型可用(D,S,P)三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。用伪码(不真正执行的符号)描述基本操作的定义格式为：

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

赋值参数只为操作提供输入值；

引用参数以&打头，除了可以提供输入值外，还将返回操作结果。

描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。说明操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。抽象数据类型的描述方法：例6抽象数据类型三元组的定义ADTTriplet{ 数据对象：D={e1,e2,e3|e1,e2,e3∈Elemset} 数据关系：R1={<e1,e2>,<e2,e3>} 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T…… DestroyTriplet(&T) 操作结果：三元组T被销毁 Get(T,i,&e) 初始条件：三元组T已存在，1≤i≤3 操作结果：用e返回T的第i元的值 。。。。。。。。。。。}ADTTriplet多形数据类型多形数据类型是指其值的成分不确定的数据类型例如：e1,e2,e3可以是整型、字符、字符串，也可以是构造的复杂类型要求：元素之间的关系相同，基本操作相同具有相同的数据抽象1.3抽象数据类型的表示与实现抽象数据类型可以通过固有数据类型来表示和实现用已存在的数据类型来说明新的结构用已实现的操作来组合新的操作采用类C语言作为描述工具本教材采用类C语言和伪码描述类C语言简要说明采用类C语言作为描述工具介于伪码和C语言之间的语言有时用伪码表示只含抽象操作的抽象算法预定义常量和类型数据结构的表示基本操作的算法用以下格式函数描述函数类型函数名（函数参数表）{//算法说明语句序列}函数名赋值语句简单赋值传来赋值成组赋值交换赋值条件赋值条件语句ifswitch循环语句forwhiledo-while结束语句函数结束语句：returncase结束语句：break异常结束语句：exit输入和输出语句输入语句：scanf输出语句：printf通常省略格式串注释单行注释//基本函数求最大值 max求最小值 min求绝对值 abs求不足整数值 floor求进位整数值 ceil判定文件结束 eof判定行结束 eoln逻辑运算约定短路！例7抽象数据类型Triplet的表示和实现//-----采用动态分配的顺序存储结构-----typedefElemType*Triplet;//由InitTriplet分配3个元素存储空间//-----基本操作的函数原型说明-----StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3); //操作结果:构造了三元组T，元素………………//-----基本操作的实现-----StatusInitTriplet(Triplet&T,ElemTypev1,ElemTypev2,ElemTypev3){ //构造三元组T，依次置T的3个元素的初值为v1，v2和v3。 T=(ElemType*)malloc(3*sizeof(ElemType));//分配三个单元的存储空间 if(!T)exit(OVERFLOW); //分配存储空间失败 T[0]=v1,T[1]=V2,T[2]=V3; returnOK;}//InitTriplet…………1.4算法和算法分析算法算法设计的要求算法效率的度量算法的存储空间需求1.4.1算法算法：对特定问题求解步骤的一种描述，是指令的有限序列，

其中每一条指令表示一个或多个操作算法应具有的5个重要特性有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成确定性：算法中每一条指令必须有确切的含义，无二义性。并且，在任何条件下，算法同时只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性算法描述的所有操作都必须足够基本，都是可以通过已经实现的基本运算执行有限次来实现的。输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。算法与程序的区别算法的含义与程序十分相似，但二者有区别一个程序不一定满足有穷性（如一个操作系统在用户未使用前一直处于“等待”的循环中,直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法若用计算机语言来书写，则它就可以是程序。一个算法可以用自然语言、数学语言或约定的符号来描述，也可以用流程图、计算机高级程序语言（如C语言）或伪代码等来描述。1.4.2算法设计的要求算法设计的目标正确性程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；程序对于一切合法的输入数据都能产生满足规格说明要求的结果。可读性在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是至关重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。效率与低存储量需求效率指的是算法执行的时间（时间复杂性）；存储量需求指算法执行过程中所需要的最大存储空间（空间复杂性）。一般这两者与问题的规模有关1.4.3算法效率的度量事后统计的方法必须编写好可运行程序依赖计算机的硬件和软件环境在算法中的某些部位插装时间函数time

(), 测定算法完成某一功能所花费时间

doublestart,stop;

time(&start);

intk=seqsearch(a,n,x);

time(&stop);

doublerunTime=stop-start;printf(”%d%d\n“,n,runTime)；事前分析估算的方法高级语言程序在计算机上运行时所需要消耗的时间取决于：依据算法选用何种策略问题的规模书写程序的语言编译程序产生的机器代码的质量机器执行指令的速度可见选择绝对的时间单位衡量算法的效率不可取一个特定算法的效率只依赖于问题的规模是问题规模的函数渐进时间复杂度例：NxN矩阵相乘算法for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k)

c[i][j]+=a[i,k]*b[k][j] }可见除了循环控制外，c[i][j]+=a[i,k]*b[k][j]是基本操作整个算法的执行时间与该基本操作执行次数的n3成正比。记为：T(n)=O(n3)算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法时间复杂度记作：

T(n)=O(f(n))

它表示随着问题规模的增大，算法执行的时间增长率和f(n)的增长率相同，称为算法的渐进时间复杂度，简称时间复杂度。语句的频度语句的频度是该语句重复执行的次数{++x;s=0}for(i=1;i<=n;++i){++x;s+=x;}for(j=1;j<=n;++j)

for(k=1;k<=n;++k){++x;s+=x}++x的频度分别是1、n1和n2。三个程序的时间复杂度分别为O(1)、O(n1)和O(n2)。称为常量阶、线性阶和平方阶其它可能的时间复杂度：对数阶：O(logn)指数阶：O(2n)其它：O(nlogn)、O(n!)等等时间复杂度的分析一般情况下，一个算法只选择一种基本运算讨论时间复杂度，根据需要也可能综合几个基本算法讨论时间复杂度特别的讨论有时算法中基本运算的重复执行次数随着问题的输入集不同而不同例如起泡排序中a[j]a[j+1]语句当a中初始序列为自小至大有序，基本操作的执行次数为0；当a中初始序列为自大至小有序，基本操作的执行次数