学术讨论—严蔚敏数据结构为主的笔记-吐血推荐.doc
《学术讨论—严蔚敏数据结构为主的笔记-吐血推荐.doc》由会员分享,可在线阅读,更多相关《学术讨论—严蔚敏数据结构为主的笔记-吐血推荐.doc(15页珍藏版)》请在咨信网上搜索。
1、严蔚敏数据结构为主的笔记一_love逐鹿中原百度空间 | 百度首页 | 登录 love逐鹿中原逐鹿中原,天下第一,舍我其谁。 主页博客相册|个人档案 |好友 查看文章 严蔚敏数据结构为主的笔记一2022-03-23 16:15center第一章绪论/center 一、根本问题问答: 1、什么叫数据结构?如何理解“数据结构?如何树立数据结构的学习体系? 广义上的数据结构指的是:逻辑结构和物理结构。狭义上的数据结构专指逻辑结构,就是元素间的逻辑关系,主要类型有:集合型,线性结构 ,树型,图型! 整个数据结构的课程就是围绕着以上几种数据类型展开的,加上基于这些结构的根本操作:插入,删除,查找,取元素
2、,取长度等等。另外, 还有基于这些数据结构的较为复杂的算法:查找和排序。在严老师和其他很多的数据结构教材中都把查找和排序作为了一个独立的局部,这一 局部实际上主要在探讨算法,而不在是结构本身了。算法的概念将在后面提到。 2、数据的物理结构和逻辑结构 定义数据结构,当计算机程序运行时,程序就按照定义给这些数据分配了空间。而数据定义,是在定义其逻辑结构。以链表为列,在实际定义 时,一个个的结点,由于其指针域可以指向另一个结点,那么依靠这种指向关系,就可在逻辑上建立起一条链状结构!但是,在实际的程序执 行时,是不会有这样的一条链的,而是通过在一个结点空间的某个空间内填入了下一个结点的地址!这样的每个
3、有数据和地址的结点,才是其 物理结构。 3、算法的概念、分析,算法时间复杂度的含义及分析 算法就是解决问题的方法或策略。一个算法好与坏的评价标准是:正确,可读,健壮,效率高,空间省! 设计算法时,应该按照严教材上关于类C或类P语言的描述来作,格式为: status fun_name /算法说明 . for . ;/典型功能及复杂语句后加注释 . /fun_name 注意写好注释!不求多,但求精! 时间复杂度:分析算法效率的重要工具。主要是靠推算语句执行次频度而得来的。时间复杂度考查的是“某数量级的概念,即: Tn=Ofn中,存在正的常数C和n0,使得当n=n0时,0=T(N)=C*F(N) 当
4、空间复杂度为O(1)时,称算法为就地工作原地工作。 算法时间复杂度的分析:时间复杂度的分析说到底是分析当系统规模增大时,系统所消耗时间的数量级。数量级的定义见上。简而言之,2n2 ,6n2,n2是同一数量级,因为由n2可推出其它两个常数相乘。此外,当时间复杂度的公式中出现n的多项式时,应该以高阶为准。因为 此时影响总体变化规律的是高阶项的值。在分析时间复杂度时,应该以程序或算法中执行次数最多的语句为准,通常情况下是最内层循环的时 间复杂茺,最内层语句的执行次数计算出来后,取最高的次数,然后去掉该项中的常数因子即可。 空间复杂度的度量主要是看当系统规模n增大时,系统所占用的额外空间是否也在增大,
5、按怎么的规律增大。如果没有增大,即额外空间始终是 个常数,算法就是原地工作! 4、算法设计标准 1在算法设计中,第一个牵涉到的概念是:算法说明。 它是写在过程或函数首部以下的注释内容。虽是注释内容,却是必不可少的。在测试中也占有相当大的作用。此说明主要包括:算法的功能, 参数表中各参数的含义及输入输出定义;算法中引用了哪些全局变量或外部定义的变量,它们的作用,入口初值,以及应该满足哪些限制条件 。如:链表是否带头结点,表中元素是否有序,如果有序是递增还是递减等等!必要时,算法说明还可用来陈述算法思想,采用的存储结构等 。递归算法的说明特别重要,读者应该力求将它写为算法的严格定义。几个例子: 2
6、.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名参数 STATUSVOID名参数; 语句段、 条件语句IF、THEN、ELSEIF、ELSE、 赋值语句: 比较运算 多分支语句CASE变量名OFSWITCH表达式 只写一种值1:、 CASE值1:、;BREAK; 、 ELSE语句DEFAULT:语句N1 ENDC; 循环语句WHILE条件DO、 WHILE条件、 REPEAT、UNTIL DO、WHILE FOR初值TO终值DO语句FOR初值;条件;表达式语句 出错处理ERR
11、OR错误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相似时间复杂度的比较 1.13无 1.14相似于1.10 1.15无 三、本章例题及习题
12、分析 由于本章较为简单,此局部省略。 数据结构序言在可视化化程序设计的今天,借助于集成开发环境可以很快地生成程序,程序设计不再是计算机专业人员的专利。很多人认为,只要掌握几种开发工具就可以成为编程高手,其实,这是一种误解。要想成为一个专业的开发人员,至少需要以下三个条件: 能够熟练地选择和设计各种数据结构和算法。 至少要能够熟练地掌握一门程序设计语言。 熟知所涉及的相关应用领域的知识。 其中,后两个条件比较容易实现,而第一个条件那么需要花相当的时间和精力才能够到达,它是区分一个程序设计人员水平上下的一个重要标志,数据结构贯穿程序设计的始终,缺乏数据结构和算法的深厚功底,很难设计出高水平的具有专
13、业水准的应用程序。曾经有一本经典计算机专业书籍叫做?数据结构+算法=程序?,也说明了数据结构和算法的重要性。 ?数据结构?是计算机科学与工程的根底研究之一,掌握该领域的知识对于我们进一步进行高效率的计算机程序开发非常重要。无论在中国还是在美国,?数据结构?一直是大学的计算机专业重要的专业根底课。例如,在著名的美国的加州大学伯克利分校著名的BSD Unix的发源地,很多Unix操作系统由它派生而来或带有它的痕迹例如FreeBSD、Sun公司的Solaris、IBM的AIX,就用一个学期开设?数据结构和算法?课程在这之前,用一个学期开设?C+程序设计?课程。 现行的中学相关的计算机教程或者是关于怎
14、样使用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+对于学习计算机系统结构有很大的好处。 第一章:概论(包括习题与答案及要点) - 本章的重点是了解数据结构的逻辑结构、存储
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 精品 医学 专题 严蔚敏 数据结构 为主 笔记 吐血 推荐
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【Fis****915】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【Fis****915】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。