搜索
第1章绪论1.数据(Data)：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。2.数据元素(DataElement)：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。3.数据项（DataItem）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。4.数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={A,B,C,…}。数据(Data)：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。数据元素(DataElement)：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）；数据元素是数据的基本单位。数据项（DataItem）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。一个数据元素可由若干个数据项组成。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={A,B,C,…}。数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示。四种逻辑结构：集合、线性结构、树型结构、图状结构。数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例1：设数据逻辑结构B=（K，R）K={k1,k2,…,k9}R={k1,k3，k1,k8，k2,k3，k2,k4，k2,k5，k3,k9，k5,k6，k8,k9，k9,k7，k4,k7，k4,k6有时候关系图不唯一（一般是无向图）数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。两种不同的存储结构：顺序存储结构和链式存储结构。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求，用该指针来表示数据元素之间的逻辑结构(关系)。顺序存储—使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序体现它们的逻辑次序。通常使用程序设计语言中的数组来实现。•链式存储—使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻。数据元素间的逻辑关系通过结点间的链接关系来体现。通常使用指针记载直接前驱元素或直接后继元素的存储地址。数据操作指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作。•初始化。•判断是否空状态。•统计元素的个数。•遍历：按某种次序访问所有元素，每个元素只被访问一次。•取值：获取指定元素值。•置值：设置指定元素值。•插入：增加指定元素。•删除：移去指定元素。•查找：在数据结构中寻找满足给定条件的数据元素。•排序：将数据元素•...数据操作定义在数据的逻辑结构上；数据操作的实现依赖于数据的存储结构。•数据结构三方面的关系：数据的逻辑结构、数据的存储结构及操作这三方面是一个整体例6：线性表是一种逻辑结构，若采用顺序存储，可称其为顺序表；若采用链式存储，则可称其为链表；若采用散列存储，则可称为散列表。•在给定了数据的逻辑结构和存储结构之后，按定义的操作集合及其操作的性质不同，也可能导致完全不同的数据结构。•类型（type）是具有相同逻辑意义的一组值的集合。•数据类型是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作例7：Java中整型类型int的值集是[-231,…,-2,-1,0,1,2,…,231-1]这个值集上的操作集合[+,-,*,/,%,=,==,!=,,=,,=]抽象数据类型(AbstractDataType，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT的一般定义形式是：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名例8：复数抽象数据类型描述如下：ADTComplex{doublereal,imag;Complex(doublereal,doubleimag);Complexadd(Complexc);Complexsub(Complexc);}1、算法定义：一个算法（algorithm）是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列（D.Knuth）。算法的规则必须满足以下5个特性：①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。2、算法设计目标–正确性–健壮性–高时间效率–高空间效率–可读性3、算法描述自然语言描述伪码描述传统流程图描述程序设计语言描述（本课程选Java）4、算法与数据结构•算法建立在数据结构之上，对数据的操作需用算法来描述。•算法设计依赖数据的逻辑结构，算法实现依赖数据的存储结构。•实现一种抽象数据类型，需要选择合适的存储结构。求解同一问题可能有许多不同的算法，如何去评价这些算法的优劣？主要考虑如下三点：A.执行算法所耗费的时间；B.执行算法所耗费的存储空间，其中主要考虑辅助存储空间；C.算法应易于理解，易于编码，易于调试等等。1、时间代价分析算法的时间效率指算法的执行时间随问题规模的增长而增长的趋势，通常采用时间复杂度来度量算法的时间效率,用大O表示法来记:T(n)=O(f(n))例1voidfun(){++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)。如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。一个简单语句的时间复杂度为Ｏ(1)。例2for(i=1;i=n;++i){++x;s+=x;}语句频度为：2n，其时间复杂度为：Ｏ(n)，即为线性阶。一个循环的时间复杂度为Ｏ(n)。例3for(i=1;i=n;++i){for(j=1;j=n;++j){++x;s+=x;}}语句频度为：2n2，其时间复杂度为：O(n2)，即为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)例4两个n阶方阵的乘法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];}}}由于是一个三重循环，每个循环从1到n，则总次数为：n×n×n=n3时间复杂度为T(n)=Ｏ(n3)例5for(i=2;i=n;++i){for(j=2;j=i-1;++j){++x;a[i,j]=x;}}语句频度为：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。例6：intn=8,count=0;for(inti=1;i=n;i*=2)for(intj=1;j=n;j++)count++;循环次数为。时间复杂度为O(nlog2n)。例7：intn=8,count=0;for(inti=1;i=n;i*=2)for(intj=1;j=i;j++)count++;总的循环次数为。时间复杂度为O(n)。以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(㏒n)O(n)O(n㏒n)O(n2)O(n3)指数时间的关系为：O(2n)O(n!)O(nn)当n取得很大时，指数时间算法运算时间远远超过多项式时间算法。2、空间代价分析算法的空间效率（空间复杂度）指算法在执行时为解决问题所需要的额外存储空间，不包括输入数据和程序指令所占用的存储空间,用大O表示法来记:S(n)=o(f(n))该存储空间一般包括三个方面：–指令常数变量所占用的存储空间;–输入数据所占用的存储空间;–辅助(存储)空间。•一般地，算法的空间复杂度指的是辅助空间。•变量i：空间复杂度O(1)•一维数组a[n]：空间复杂度O(n)•二维数组a[n][m]：空间复杂度O(n*m)第2章线性表线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：i.①存在一个唯一的被称为“第一个”的数据元素；ii.②存在一个唯一的被称为“最后一个”的数据元素；iii.③除第一个元素外，每个元素均有唯一一个直接前驱；iv.④除最后一个元素外，每个元素均有唯一一个直接后继。线性表(LinearList)：是由n(n≧0)个数据元素(结点)a0，a1，…an-1组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。b)当n=0时，称为空表。c)当n0时，将非空的线性表记作：(a0，a1，…an-1)线性表的顺序表示指的是一组地址连续的存储单元依次存储线性表的数据元素。用顺序存储实现的线性表称之为顺序表。线性表的逻辑顺序与物理顺序一致。•顺序表是一种随机存取结构。通常采用数组存储数据元素。•设线性表的每个元素需占用c个存储单元。publicbooleanisEmpty(){//时间复杂度O(1)returnthis.len==0;}publicintlength(){//时间复杂度O(1)returnthis.len;}publicTget(inti){//时间复杂度O(1)if(i=0&&ithis.len)return(T)this.element[i];returnnull;}publicvoidset(inti,Tx){//时间复杂度O(1)if(x==null)return;if(i=0&&ithis.len)this.element[i]=x;elsethrownewIndexOutOfBoundsException(i+“”)；}publicStringtoString(){//时间复杂度O(n)Stringstr=“(”;if(this.len0)str+=this.element[0].toString();for(inti=1;ithis.len;i++)str+=“，”+this.element[i].toString();returnstr+“)”;}}•两个线性表相等是指，它们长度相同并且各对应元素相等。•链式存储：用一组任意的存储单元存储线性表中的数据元素。存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。•链表中结点的逻辑顺序和物理顺序不一定相同。•链表中的结点结构：数据域和地址域n个结点构成的链表表示为(a0,a1,...,an-1)•链表中每个结点只含一个地址域，又称为线性链表或单链表。•每个结点有两个地址域的线性链表称为双链表。•单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。头结点的作用是，使所有链表（包括空表）的头指针非空，则对单链表的插入、删除操作不需要区分操作位置。头结点中不存储数据。