严蔚敏数据结构为主的笔记-吐血推荐

1、严蔚敏数据结构为主的笔记一_love逐鹿中原百度空间 | 百度首页 | 登录 love逐鹿中原逐鹿中原，天下第一，舍我其谁。 主页博客相册|个人档案 |好友 查看文章 严蔚敏数据结构为主的笔记一2008-03-23 16:15center第一章绪论/center 一、基本问题问答： 1、什么叫数据结构？如何理解“数据结构”？如何树立数据结构的学习体系？ 广义上的数据结构指的是：逻辑结构和物理结构。狭义上的数据结构专指逻辑结构，就是元素间的逻辑关系，主要类型有：集合型，线性结构 ，树型，图型！ 整个数据结构的课程就是围绕着以上几种数据类型展开的，加上基于这些结构的基本操作：插入，删除，查找，取元

2、素，取长度等等。另外， 还有基于这些数据结构的较为复杂的算法：查找和排序。在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立的部分，这一 部分实际上主要在探讨算法，而不在是结构本身了。算法的概念将在后面提到。 2、数据的物理结构和逻辑结构 定义数据结构，当计算机程序运行时，程序就按照定义给这些数据分配了空间。而数据定义，是在定义其逻辑结构。以链表为列，在实际定义 时，一个个的结点，由于其指针域可以指向另一个结点，那么依靠这种指向关系，就可在逻辑上建立起一条链状结构！但是，在实际的程序执 行时，是不会有这样的一条链的，而是通过在一个结点空间的某个空间内填入了下一个结点的地址！这样的每

3、个有数据和地址的结点，才是其 物理结构。 3、算法的概念、分析，算法时间复杂度的含义及分析 算法就是解决问题的方法或策略。一个算法好与坏的评价标准是：正确，可读，健壮，效率高，空间省！ 设计算法时，应该按照严教材上关于类C（或类P）语言的描述来作，格式为： status fun_name /算法说明 . for . ;/典型功能及复杂语句后加注释 . /fun_name 注意写好注释！不求多，但求精！ 时间复杂度：分析算法效率的重要工具。主要是靠推算语句执行次频度而得来的。时间复杂度考查的是“某数量级”的概念，即： T（n）=O（f（n）中，存在正的常数C和n0，使得当n=n0时，0=T(N)

4、=C*F(N) 当空间复杂度为O(1)时，称算法为就地工作（原地工作）。 算法时间复杂度的分析：时间复杂度的分析说到底是分析当系统规模增大时，系统所耗费时间的数量级。数量级的定义见上。简而言之，2n2 ，6n2，n2是同一数量级，因为由n2可推出其它两个（常数相乘）。此外，当时间复杂度的公式中出现n的多项式时，应该以高阶为准。因为 此时影响总体变化规律的是高阶项的值。在分析时间复杂度时，应该以程序或算法中执行次数最多的语句为准，通常情况下是最内层循环的时 间复杂茺，最内层语句的执行次数计算出来后，取最高的次数，然后去掉该项中的常数因子即可。 空间复杂度的度量主要是看当系统规模n增大时，系统所占

5、用的额外空间是否也在增大，按怎么的规律增大。如果没有增大，即额外空间始终是 个常数，算法就是原地工作！ 4、算法设计规范 1在算法设计中，第一个牵涉到的概念是：算法说明。 它是写在过程或函数首部以下的注释内容。虽是注释内容，却是必不可少的。在测试中也占有相当大的作用。此说明主要包括：算法的功能， 参数表中各参数的含义及输入输出定义；算法中引用了哪些全局变量或外部定义的变量，它们的作用，入口初值，以及应该满足哪些限制条件 。如：链表是否带头结点，表中元素是否有序，如果有序是递增还是递减等等！必要时，算法说明还可用来陈述算法思想，采用的存储结构等 。递归算法的说明特别重要，读者应该力求将它写为算法

6、的严格定义。几个例子： 2.29procedure DifferenceSqlist(VAR a;Sqlist;b,c:Sqlist); 删去增序顺序表中那些既在增序顺序表中B出现又在增序顺序表C中出现的元素 2.33procedure Sqlistlinkedlist(VAR lc,ld,lo:LinkedList;ll:LinkedList); 将线性表ll分割为3个循环链表lc,ld和lo, 其中每个循环链表只含一类字符，分别为A.Z、0.9和其它字符。 2注释与断言 在难懂的语句和关键的语句（段）之后加以注释可以大大提高程序的可读性。注释要恰当，并非越多越好；此外，注释句的抽象程度应略

7、高于 语句（段）。 断言是注释的一种特殊写法，它是一个逻辑谓词，陈述算法执行到此点时应满足的条件，即这种形式：当、时，、。最重要的就是算法 的入口断言与else分支断言。如果算法不含有参数佥性检测的代码段，书写入口断言是最低限度的要求。 3输入、输出 三种方式： a、通过专门的输入/出语句：read，write，scanf，printf等 b、通过参数表中的参数传递 c、通过全局及外部变量 4错误处理 三种处理方式： a、error语句实现 b、通过函数返回错误代码或错误状态值 c、exit语句实现 提倡使用第二种方式来实现错误处理 5语句的使用与算法结构 避免使用goto语句，算法结构结构应

8、该同层次对齐，下一层向上一层缩进两格，并以适当的符号标识语句段的开始与结束：， 6基本运算 未明确要求的，不得直接用教科书上的基本运算 非用不可的，要将这些基本运算的代码全部写出 7几点建议 a、建议以图说明算法 b、建议在算法书写完毕后，用边界条件的值验证一下算法能否正确执行 5、类P与类C大比拼 许多朋友问我类P与类C有啥区别，哪个更好？考试的时候用哪个语言？其实，这些都是一些很基础的问题，不客气地说这是考研门外汉的问题 。类P较类C的教材版本出得早，在后期的类C版数据中省去了类P中的一些内容，比如：栈一章的递归到非递归的转化等。但并不能因此就说类C 版要差，事实上，类C的更符合当前考试和

9、应用的发展趋势，从整体认同度而言，个人建议还是用类C好一点，原因：一，C语言本身很灵活，程 序简洁，是真正的程序员用的语言，更是一个计算机研究生必须掌握的；二，C语言本身在实际项目的应用中是一种通用语言，软件公司绝大多 数是要精通VC的，学好C的DS其意义更深远一些。另外，考虑到考上后绝大多数研友都会被导师拉去作项目，而作项目时多用的也是C！三，就 交流范围而言，现在计算机版里用C的人要多得多，所以，交流的机会应该要多一些，这样提高的也快些。四，其它原因。至于考试的时候用哪 一个，应该以报考学校的要求为准，如果没有作要求的，请参照一下该校给出的历年题的标准答案是用哪种语言。当然，一般情况下，用

10、两种 语言都行，只要算法正确，就会得分。 下面，罗列一下类C与类P的不同： 类P类C 类型定义TYPE、RECORD、ENDTYPEDEF、 常量定义CONSTDEFINE 函数定义PROC（或FUNC）名（参数） STATUS（VOID）名（参数）； 语句段、 条件语句IF、THEN、ELSEIF（）、ELSE、 赋值语句： 比较运算 多分支语句CASE变量名OFSWITCH（表达式） （只写一种）值1：、 CASE值1：、；BREAK； 、 ELSE语句DEFAULT：语句N1 ENDC； 循环语句WHILE条件DO、 WHILE条件、 REPEAT、UNTIL（） DO、WHILE（）

11、FOR（初值）TO（终值）DO语句FOR（初值；条件；表达式）语句 出错处理ERROR（错误）EXIT（出错代码） 输入/出 READ，WRITESCANF，PRINTF 注释 / 基本函数MAX，MIN，ABS，EOF，EOLN，上下取整上下取整分别为FLOOR，CEIL 逻辑运算AND，OR，NOT，CAND，COR，！ 注：以上不同之处在具体算法中的体现，请参照教材P版P25页和C版P24页的对应算法。 二、本章习题集中常考及已考题 1.1相同 1.2相同 1.3相似 1.4无 1.5相似 1.6相似 1.7相似 1.8相似 1.9相似 1.10相同 1.11相似（时间复杂度的比较） 1

12、.12相似（时间复杂度的比较） 1.13无 1.14相似于1.10 1.15无 三、本章例题及习题分析 由于本章较为简单，此部分省略。 数据结构序言在可视化化程序设计的今天，借助于集成开发环境可以很快地生成程序，程序设计不再是计算机专业人员的专利。很多人认为，只要掌握几种开发工具就可以成为编程高手，其实，这是一种误解。要想成为一个专业的开发人员，至少需要以下三个条件： 能够熟练地选择和设计各种数据结构和算法。 至少要能够熟练地掌握一门程序设计语言。 熟知所涉及的相关应用领域的知识。 其中，后两个条件比较容易实现，而第一个条件则需要花相当的时间和精力才能够达到，它是区分一个程序设计人员水平高低的

13、一个重要标志，数据结构贯穿程序设计的始终，缺乏数据结构和算法的深厚功底，很难设计出高水平的具有专业水准的应用程序。曾经有一本经典计算机专业书籍叫做数据结构+算法=程序，也说明了数据结构和算法的重要性。 数据结构是计算机科学与工程的基础研究之一，掌握该领域的知识对于我们进一步进行高效率的计算机程序开发非常重要。无论在中国还是在美国，数据结构一直是大学的计算机专业重要的专业基础课。例如，在著名的美国的加州大学伯克利分校（著名的BSD Unix的发源地，很多Unix操作系统由它派生而来或带有它的痕迹例如FreeBSD、Sun公司的Solaris、IBM的AIX），就用一个学期开设数据结构和算法课程（

14、在这之前，用一个学期开设C+程序设计课程）。 现行的中学相关的计算机教程或者是关于怎样使用Windows操作系统及其工具、或者是有关办公软件的使用，或者是打字教程。计算机对他们始终有一种神秘感，也许是理论导向吧，因为不可能每个人将来都成为计算机专业人员。 作为一个中学生，在学完C/C+以后，关键的问题是怎样熟练地应用和巩固。本网站希望能够结合数据结构和相关的数、理、化知识来巩固C/C+。其实数据结构并不难。可以说，数据结构贯穿于我们的数学课程之中，只是思考问题方法的不同。在大学的数据结构教程中，很多生僻的词语、晦涩难懂的语句，连大学生就感到望而生畏。本网站将集合小学和中学的数学、物理、化学教材

15、，深入浅出地讲解这门课程。希望不但能够对学习电脑有所帮助，更希望能够对数理化的学习起到一个促进作用。 在学习数据结构之前，要求学生有C/C+基础。可以这样说，C/C+是其他程序设计语言的基础。掌握了C/C+，学习其他语言就会易如反掌。例如，微软的MFC类库基于C+；ATL基于C+中的模板类；Java语言基于C+思想，其编程风格与C+差别很小；C+ Builder又是基于C+；Delphi中的有关对象的概念与C+中的对象几乎完全一致。C+相比其他语言具有与计算机硬件集合紧密、代码效率高，这是Java语言和其他高级语言所无法比拟的。这样，C/C+对于学习计算机系统结构有很大的好处。 第一章：概论(

16、包括习题与答案及要点) - 本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 需要达到层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。 需要达到层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。- 对于基本概念，仔细看书就能够理解，这里简单提一下： 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本

17、单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，

18、虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删

19、除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 - 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构 (这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。 - 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。 首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指

20、当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(n

21、k)、指数阶O(2n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 - 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 数据：指能够被计算机识别、存储和加工处理的信息载体。 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指各数据元素之间

22、的逻辑关系。 存储结构：就是数据的逻辑结构用计算机语言的实现。 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。- 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一

23、个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。 那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学C语言吧)。 最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现

24、这些操作就是数据的运算问题了。- 1.3 常用的存储表示方法有哪几种? 常用的存储表示方法有四种: 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。- 1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000

25、 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n) (2) g(n)=O(f(n) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) (1)成立。 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)，这里的O是数学符号，它的严格定义是若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C和n0 ,使得当nn0时都满足0T(n)C?f(n)。用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，

26、就好计算了吧。第(1)题中两个函数的最高次项都是n3,因此当n时，两个函数的比值是一个常数，所以这个关系式是成立的。 （2）成立。 （3）成立。 （4）不成立。- 1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 15 最简单最笨的办法就是拿自然数去代呗。假定n取为10，则前者的值是10000，后者的值是1024,小于前者，那我们就加个5，用15代入得前者为22500，后者为32768，已经比前者大但相差不多，那我们再减个1，用14代入得，前者为19600,后者为16384，又比前者小了，所以结果得出来就是n至少要是15. - 1.6 设

27、n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。1.6 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0 while(i k=k+10*i;i+; T(n)=n-1 T(n)=O(n) 这个函数是按线性阶递增的 (2) i=0; k=0; do k=k+10*i; i+; while(i T(n)=O(n) 这也是线性阶递增的 (3) i=1; j=0; while(i+j1 while (x=(y+1)*(y+1) y+; T(n)=n1/2 T(n)=O(n1/2) 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。 (5) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+; T(n)=O(1) 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数