算法数据结构

1算法与数据结构包仲贤409872449@兰州理工大学计算机与通信学院2教材与参考书1.算法与数据结构，张永等2.数据结构,严蔚敏,吴伟民3.数据结构与算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译

电子工业出版社

2001年1月31.1问题求解分析1.2基本概念和术语1.3算法和算法分析

1.4抽象数据类型的表示与定义41．现实问题的计算机化----表示问题2．现实问题的处理过程-----程序化问题5例：魔方求解问题一个魔方（magicsquare）就是一个由1到n2的整数构成的n×n的矩阵，其中每行、每列以及两条对角线上的数字之和都相等。6求解过程当n为奇数时，Coxeter给出了产生魔方的具体过程：1）.把1放入第一行最中间的方格中；2）.向左上方移动，并按照数字的递增顺序，把数字填入空方格；3）.如果移出了魔方，即超越了魔方边界，则进入魔方对边的对应方格中；4）.如果一个方格已被填入数字，则向下继续填写方格；5）.依据上述方法，直到全部填写完毕。71、数据结构形式化结果为：intsquare[MAX_SIZE][MAX_SIZE];

2、将上述的产生魔方的过程算法化，用简洁的描述方式描述产生魔方的过程，即就是算法描述81）square[0][(size-1)/2]=1;/*把1放入第一行最中间的方格中*/2）for(count=2;count<=size*size;count++){

/*依次放入其后的数字*/row=(i-1<0)?(size-1):(i-1);/*i=0;j=(size-1)/2;上方*/column=(j-1<0)?(size-1):(j-1);/*左方*/9if(square[row][column])

/*如果方格已被填入数字，下方*/i=(++i)%size;else{i=row;j=column；}square[i][j]=count;}10本方法:15812417161475232220136432119121092251811111.1问题求解分析1.2基本概念和术语1.3算法和算法分析1.4抽象数据类型的表示与定义

121.2基本概念和术语一、基本概念二、结构的定义三、数据结构的定义四、数据结构的分类13一.基本概念数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机操作的对象的总称。是信息的载体。14数据元素(DataElement):是数据（集合）中的一个“个体”,是组成数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。是数据结构中讨论的基本单位15

数据项：是数据结构中讨论的最小单位（不可分割）。数据元素可以是数据项的集合（组成数据元素的各个项）16数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。例1、整数的数据对象。

例2、英文字符类型的数据对象。数据对象可以是有限的，也可以是无限的。17学生信息可包括学生的学号、姓名、性别、年龄等数据。这些数据构成学生情况的描述的数据项；包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。学生信息数据元素的C语言表示方法是：structStudent{longnumber;charname[10];charsex[3];intage;};18二.结构的定义结构（Structure）:数据元素之间的相互关系。如指数据在逻辑上的关系，称为逻辑结构。如指数据在物理上的关系，称为物理结构。19三.数据结构的定义数据结构(DataStructure)1.

描述性定义：是相互之间存在一种或多种特定关系的数据元素的集合。2.形式定义20数据结构一般包括以下三方面内容：1）数据元素之间的逻辑关系，也称数据的逻辑结构2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）3）数据的运算，即对数据施加的操作1.数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。2.最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。21四、数据结构的分类1.从逻辑结构角度分

线性结构：线性表、栈、队列

非线性结构：树、图2.从物理结构角度分存储结构：物理结构。22逻辑结构线性结构树结构图结构23四种不同的存储结构1、顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。2、链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。243、索引存储方法该方法通常在存储结点信息的同时，还建立附加的索引表。4.散列存储方法根据结点的关键字直接计算出该结点的存储地址。251.1问题求解分析1.2基本概念和术语1.3

算法和算法分析

1.4抽象数据类型的表示与定义

261.3算法和算法分析一、算法二、算法的描述三、算法分析27一、算法1、算法：是对特定问题求解步骤的一种描述。算法是指令的有限序列，其中每一条指令表示一个或多个操作。

2、算法具有以下五个特性：（1）有穷性（2）确定性（3）可行性（4）输入(5)输出

283、算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)(2)可读性(Readability)(3)健状性(Robustness)(4)效率与存储量需求⑴所设计的程序没有语法错误；⑵所设计的程序对于几组输入数据能够得出满足要求的结果；⑶所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果；⑷程序对于一切合法的输入数据都能产生满足要求的结果。

max:=0；

for（i=1；i<=n；i++）

{scanf("%f",&x);

if(x>max)

max=x;

}29二、算法的描述1、算法、语言、程序的关系2、设计实现算法的过程步骤301．算法、语言、程序的关系1）算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）2）描述算法的工具：（自然语言、框图或类C语言）3）程序是算法在计算机中的实现（与所用计算机及所用语言有关）312、设计实现算法过程步骤1）找出与求解有关的数据元素之间的关系（建立结构关系）；2）确定在某一数据对象上所施加运算；3）考虑数据元素的存储表示；4）选择描述算法的语言；5）设计实现求解的算法，并用程序语言加以描述。32三、算法分析1．性能评价对问题规模n与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。332．时间与空间数量关系计算数量关系评价体现在时间——算法编程后在机器中所耗费时间。数量关系评价体现在空间——算法编程后在机器中所占存储量。341）关于算法执行时间事先分析和事后测试事先分析

求出该算法的一个时间界限函数。事后测试

收集此算法的执行时间和实际占用空间的统计资料。35语句频度：是指该语句一个算法中重复执行的次数。例１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];}362）算法的时间复杂度:算法的时间度量记作T(n)=O(f(n))称作算法的渐近时间复杂度，简称时间复杂度。37例２、{++x;s=0;}例３、for(i=1;i<=n;++i){++x;s+=x;}例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}38例５for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}39例6：Voidbubble-sort(inta[]，intn)for(i=n-1,change=TURE;i>1&&change;--i){change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE}}

40for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本语句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本语句2}41

以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：

O(2n)<O(n!)<O(nn)42有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大“O”记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0nlgn+O(n)433）、算法的空间复杂度空间复杂度:算法所需存储空间的度量，记作:

S(n)=O(f(n))

其中n为问题的规模(或大小)44例以魔方为例来看一下实现魔方算法的评价。空间复杂度上，存贮一个nn的魔方，只需要nn的整数存贮空间，即O（n2）。时间复杂度上，操作的主要工作来自于两个for循环嵌套，所以时间复杂度是O（n2）。451.1问题求解分析1.2基本概念和术语1.3算法和算法分析

1.4抽象数据类型的表示与定义

461、数据类型数据类型

是一个值的集合和定义在此集合上的一组操作的总称。472.抽象数据类型（AbstractDataType简称ADT）在数据结构中我们常用到抽象数据类型。ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名假定把矩形定义为一种抽象数据类型，其数据部分包括矩形的长度和宽度，操作部分包括初始化矩形的尺寸、求矩形的周长和求矩形的面积。

4849假定该抽象数据类型名用RECtangle（矩形）表示，定义矩形长度和宽度的数据用length和width表示，并假定其类型为浮点（float）型。初始化矩形数据的函数名用InitRectangle表示，求矩形周长的函数名用Circumference表示求矩形面积的函数名用Area（面积）表示50矩形的ADT（抽象数据类型）描述如下：

ADT

RECtangle

is

Data:

一个矩形r，其长度和宽度分别用length和width表示

Operations:

//初始化矩形r的长度和宽度值为len和wid

void

InitRectangle(Rectangle&

r,

float

len,

float

wid);

//求矩形r的周长并返回

float

Circumference(Rectangle&

r);

//求矩形r的面积并返回

float

Area(Rectangle&

r);

end

RECtangle51假定数据部分的矩形r是类型名为Rectangle的一个结构对象，该类型的具体定义如下：structRectangle{floatlength,width;};初始化矩形尺寸

voidInitRectangle(Rectangle&r,floatlen,floatwid){ r.length=len;//把len值赋给r的length域

r.width=wid;//把wid值赋给r的width域

}52初始化矩形尺寸

voidInitRectangle(Rectangle&r,floatlen,floatwid){ r.length=len;//把len值赋给r的length域

r.width=wid;//把wid值赋给r的width域

}53求矩形周长

floatCircumference(Rectangle&r){return2*(r.length+r.width);}求矩形面积

float