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

严蔚敏数据结构为主的笔记一_love逐鹿中原百度空间 | 百度首页 | 登录 love逐鹿中原逐鹿中原，天下第一，舍我其谁。 主页博客相册|个人档案 |好友 查看文章 严蔚敏数据结构为主的笔记一2008-03-23 16:15[center]第一章　　绪　　论[/center] 一、基本问题问答： 1、什么叫数据结构？如何理解“数据结构”？如何树立数据结构的学习体系？ 广义上的数据结构指的是：逻辑结构和物理结构。狭义上的数据结构专指逻辑结构，就是元素间的逻辑关系，主要类型有：集合型，线性结构 ，树型，图型！ 整个数据结构的课程就是围绕着以上几种数据类型展开的，加上基于这些结构的基本操作：插入，删除，查找，取元素，取长度等等。另外， 还有基于这些数据结构的较为复杂的算法：查找和排序。在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立的部分，这一 部分实际上主要在探讨算法，而不在是结构本身了。算法的概念将在后面提到。 2、数据的物理结构和逻辑结构 定义数据结构，当计算机程序运行时，程序就按照定义给这些数据分配了空间。而数据定义，是在定义其逻辑结构。以链表为列，在实际定义 时，一个个的结点，由于其指针域可以指向另一个结点，那么依靠这种指向关系，就可在逻辑上建立起一条链状结构！但是，在实际的程序执 行时，是不会有这样的一条链的，而是通过在一个结点空间的某个空间内填入了下一个结点的地址！这样的每个有数据和地址的结点，才是其 物理结构。 3、算法的概念、分析，算法时间复杂度的含义及分析 算法就是解决问题的方法或策略。一个算法好与坏的评价标准是：正确，可读，健壮，效率高，空间省！ 设计算法时，应该按照严教材上关于类C（或类P）语言的描述来作，格式为： status fun_name{ //算法说明 ... 　for{ .... };//典型功能及复杂语句后加注释 ... }//fun_name 注意写好注释！不求多，但求精！ 时间复杂度：分析算法效率的重要工具。主要是靠推算语句执行次频度而得来的。时间复杂度考查的是“某数量级”的概念，即： T（n）=O（f（n））中，存在正的常数C和n0，使得当n>=n0时，0<=T(N)<=C*F(N) 当空间复杂度为O(1)时，称算法为就地工作（原地工作）。 算法时间复杂度的分析：时间复杂度的分析说到底是分析当系统规模增大时，系统所耗费时间的数量级。数量级的定义见上。简而言之，2n^2 ，6n^2，n^2是同一数量级，因为由n^2可推出其它两个（常数相乘）。此外，当时间复杂度的公式中出现n的多项式时，应该以高阶为准。因为 此时影响总体变化规律的是高阶项的值。在分析时间复杂度时，应该以程序或算法中执行次数最多的语句为准，通常情况下是最内层循环的时 间复杂茺，最内层语句的执行次数计算出来后，取最高的次数，然后去掉该项中的常数因子即可。 空间复杂度的度量主要是看当系统规模n增大时，系统所占用的额外空间是否也在增大，按怎么的规律增大。如果没有增大，即额外空间始终是 个常数，算法就是原地工作！ 4、算法设计规范 1＞在算法设计中，第一个牵涉到的概念是：算法说明。 它是写在过程或函数首部以下的注释内容。虽是注释内容，却是必不可少的。在测试中也占有相当大的作用。此说明主要包括：算法的功能， 参数表中各参数的含义及输入输出定义；算法中引用了哪些全局变量或外部定义的变量，它们的作用，入口初值，以及应该满足哪些限制条件 。如：链表是否带头结点，表中元素是否有序，如果有序是递增还是递减等等！必要时，算法说明还可用来陈述算法思想，采用的存储结构等 。递归算法的说明特别重要，读者应该力求将它写为算法的严格定义。几个例子： 　2.29　procedure DifferenceSqlist(VAR a;Sqlist;b,c:Sqlist); 　{删去增序顺序表中那些既在增序顺序表中B出现又在增序顺序表C中出现的元素} 　2.33　procedure Sqlistlinkedlist(VAR lc,ld,lo:LinkedList;ll:LinkedList); 　{将线性表ll分割为3个循环链表lc,ld和lo,} 　{其中每个循环链表只含一类字符，分别为［'A'..'Z'］、［'0'..'9'］和其它字符。} 2＞注释与断言 在难懂的语句和关键的语句（段）之后加以注释可以大大提高程序的可读性。注释要恰当，并非越多越好；此外，注释句的抽象程度应略高于 语句（段）。 断言是注释的一种特殊写法，它是一个逻辑谓词，陈述算法执行到此点时应满足的条件，即这种形式：当、、、时，、、。最重要的就是算法 的入口断言与else分支断言。如果算法不含有参数佥性检测的代码段，书写入口断言是最低限度的要求。 3＞输入、输出 三种方式： a、通过专门的输入/出语句：read，write，scanf，printf等 b、通过参数表中的参数传递 c、通过全局及外部变量 4＞错误处理 三种处理方式： a、error语句实现 b、通过函数返回错误代码或错误状态值　 c、exit语句实现 提倡使用第二种方式来实现错误处理 5＞语句的使用与算法结构 避免使用goto语句，算法结构结构应该同层次对齐，下一层向上一层缩进两格，并以适当的符号标识语句段的开始与结束：[　]，{ } 6＞基本运算 未明确要求的，不得直接用教科书上的基本运算 非用不可的，要将这些基本运算的代码全部写出 7＞几点建议 a、建议以图说明算法 b、建议在算法书写完毕后，用边界条件的值验证一下算法能否正确执行 5、类P与类C大比拼 许多朋友问我类P与类C有啥区别，哪个更好？考试的时候用哪个语言？其实，这些都是一些很基础的问题，不客气地说这是考研门外汉的问题 。类P较类C的教材版本出得早，在后期的类C版数据中省去了类P中的一些内容，比如：栈一章的递归到非递归的转化等。但并不能因此就说类C 版要差，事实上，类C的更符合当前考试和应用的发展趋势，从整体认同度而言，个人建议还是用类C好一点，原因：一，C语言本身很灵活，程 序简洁，是真正的程序员用的语言，更是一个计算机研究生必须掌握的；二，C语言本身在实际项目的应用中是一种通用语言，软件公司绝大多 数是要精通VC的，学好C的DS其意义更深远一些。另外，考虑到考上后绝大多数研友都会被导师拉去作项目，而作项目时多用的也是C！三，就 交流范围而言，现在计算机版里用C的人要多得多，所以，交流的机会应该要多一些，这样提高的也快些。四，其它原因。至于考试的时候用哪 一个，应该以报考学校的要求为准，如果没有作要求的，请参照一下该校给出的历年题的标准答案是用哪种语言。当然，一般情况下，用两种 语言都行，只要算法正确，就会得分。 下面，罗列一下类C与类P的不同： －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 　　　　　　｜　　　类　　P　　　　　　　　　｜　　　类　　C －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 类型定义　　｜TYPE、、、RECORD、、、END　　　｜TYPEDEF　　、、、｛、、、｝ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 常量定义　　｜CONST　　　　　　　　　　　　　｜＃DEFINE －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 函数定义　　｜PROC（或FUNC）　名（参数）[　] ｜STATUS（VOID）　名（参数）；｛｝ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 语句段　　　｜［　、、、　］　　　　　　　　｜｛　、、、　｝ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 条件语句　　｜IF、、THEN、、ELSE　　　　　　｜IF　（）　、、ELSE、、 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 赋值语句　　｜：＝　　　　　　　　　　　　　｜＝ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 比较运算　　｜＝　　　　　　　　　　　　　　｜＝＝ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 多分支语句　｜CASE　变量名　OF　　　　　　　｜SWITCH　（表达式）｛ （只写一种）｜　　值1：、、、　　　　　　　 ｜　CASE　值1：、、、、；BREAK； 　　　　　　｜　　、、、　　　　　　　　　　｜　、、、 　　　　　　｜　　ELSE　语句　　　　　　　　｜　DEFAULT：语句N＋1 　　　　　　｜ENDC；　　　　　　　　　　　　｜｝　 －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 循环语句　　｜WHILE　条件　DO　［、、、、］ ｜WHILE　　条件　｛、、、｝ 　　　　　　｜REPEAT、、、UNTIL　（）　　　 ｜DO　｛、、、｝　WHILE　（） 　　　　　　｜FOR（初值）TO（终值）DO［语句］｜FOR（初值；条件；表达式）｛语句｝ －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 出错处理　　｜ERROR（‘错误’）　　　　　　　｜EXIT（出错代码） －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 输入/出　　 ｜READ，WRITE　　　　　　　　　　｜SCANF，PRINTF －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 注释　　　　｜｛　｝　　　　　　　　　　　　 ｜// －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 基本函数　　｜MAX，MIN，ABS，EOF，EOLN，上下取整｜上下取整分别为FLOOR，CEIL －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ 逻辑运算　　｜AND，OR，NOT，CAND，COR