第2章 常用数据结构及其运算

《第2章 常用数据结构及其运算》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章常用数据结构及其运算第2章常用数据结构及其运算2．1概述2．1．1本章的特点及学习建议数据结构是计算机软件技术中的基础课程，它介绍软件设计中的几种常用的数据结构形式及相应的各种算法，并对各算法进行分析和比较，以便为后续课程打下基础。学习本课程必须具备一定的预备知识及正确的学习方法，因此建议：1.语言要求数据结构中各种算法均是通过编程实现的，因此在学习数据结构前，必须具备高级语言的编程能力。目前适用于数据结构的语言有Pascal、C等，尤其C语言的使用更为普遍。但有的同学由于语言没有过关就匆忙上阵，以致在做练习及上机实验时，显得一筹莫展，结果只能事倍功半。2.重视

2、实践数据结构是一门实践性很强的课程，只有通过自己动手编制各种算法程序，并上机调试后，才能对课程内容有较深刻的了解，这也是真正检验学习效果的手段。因此上机操作是必不可少的教学环节。2.1.2重点和难点数据结构中的结构形式及算法种类较多，必须对它们有基本的了解，并且能对它们进行分析、比较，以便根据实际情况灵活应用。尤其是贯穿在课程始终的动态存储结构和递归技术是其中的难点，它将给学习带来一定的难度。我们将在相应的部分，作重点的分析和讲解。2.1.3有关的概念与方法有关数据结构的基本概念和术语已在教材中作了叙述，现在就下列三个问题作进一步说明。1.逻辑结构和存储结构数据结构是

3、研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。所以，逻辑结构和存储结构是两个有区别又相关的概念。2.算法描述语言和上机试验语言为了教学方便，并不失一般性，在教材中的各种算法均采用一种接近高级语言的算法描述语言来表述。但同学要上机实践，必须将它转换成相应的上机语言。以下用一个简单的例子，说明两者的转换过程。例2.1用简单选择排序算法，在长度为n的数组r中，使数组中的元素按由大到小的数值进行排序。所谓简单选择算法是把数组中

4、的最小的元素与第1数组元素交换位置，然后再从余下的n-1个元素中找出次小元素与第2个元素对换。如此反复进行，直到数组中的元素成为有序序列为止。用算法描述语言表示为：SELSORT（r,n）//对长度为n的数组r中元素进行递增排序//1.fori=1ton-12.j←i3.fork=i+1ton4.if(r[i]i)thenr[i]r[j]//r[i]与r[j]对换7.end(i)8.return用C语言表示为：voidselsort(r,n)intr[];intn;/*参量定义*/{i

5、nti，j,k,t;/*局部变量的定义*/for（i=0；ii){t=r[j];r[j]=r[i];r[i]=t}/*r[i]与r[j]对换*/}}通过上述例子可以看出：（1）算法描述语言主要为表达算法本身，省略了各种参量、变量的定义。但是上机实验语言必须按严格的算法语言要求，对参量、变量作相应的定义。（2）算法描述语言表示中的语句6.r[i][j]表示两个数组元素进行对换，在C语言表示中需用3个语句和一个辅助变量t来实现。（3）由于C语言中数组下标是有0起算，

6、因此循环控制变量的起、止值也需作相应的改变。所以转换过程中必须根据各种上机实验语言的特性作相应的处理。3．算法分析在解决实际问题时，除了设计一个基本算法外，还需考虑有的算法是否已经很完善了，还有没有更好的算法，称为算法分析。算法的内容很多，这里仅考虑算法的复杂度，通常以算法执行时在时间和空间资源方面的消耗多寡作为评价算法的优劣标准，称为时间复杂度和空间复杂度。（1）时间复杂度时间复杂度是估计算法执行所需的时间，也就是算法中每一个语句的执行次数乘以每一个执行所需要的时间总和。但是由于语句的执行时间与所采用的机器与编译程序的功能强弱有关，所以单从执行时间上来判断容易掩盖算

7、法本身的优劣，为此人们通常用语句的执行次数来估计，使它成为与硬、软件无关的量度。例2.2①②fori=1ton③fori=1tonx←x+1x←x+1forj=1tonend(i)x←x+1end(j)end(i)在例2.2中有3个程序段，每个程序段中都有语句x←x+1,它在3个程序段中执行的次数分别为①1次、②2次、③n次。算法中语句的重复次数成该语句的频度，记作F(n),它是n的函数。某一算法的时间复杂度T(n)是以该算法中频度最大的语句频度f(n)作为该算法的时间复杂度，记作T(n)=O(f(n)),也就是该算法执行次数的数量阶。在例2.2中的