- 1、本文档共86页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
第一章数据结构基础
本章主要掌握如下内容:
数据结构的概念、常用的术语,数据结构发展的历史以及数据结构在计算机科学中的地位,
数据结构描述语言,抽象数据类型ADT,数据存储结构,算法描述、分析及其复杂度问题。
1.基本概念和术语
数据:是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并
被计算机程序处理的符号集合。
数据元素:是数据集合中的一个实体,是计算机程序中加工处理的基本单位。
数据项就是数据中不可再分割的最小单位。
数据结构:相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有:集
合、线性结构、树形结构和图形结构。
线性表、堆栈、队列、串都可认为是线性结构,树和二叉树都是树形结构,而图则属于图
状结构。
逻辑结构:数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系。
存储结构(物理结构):是指数据结构在计算机存储器中的具体实现。与孤立的数据元素
表示形式不同,数据结构中的数据元素不但要表示其本身的实际内容,还要表示清楚数据元素
之间的逻辑结构。
常见的存储结构:
顺序存储结构:特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结
构;
链式存储结构:特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。
2.数据结构的定义
逻辑结构主要用于描述数据元素之间的逻辑关系;
物理结构是指数据结构在计算机中的表示。
有两种形式的存储结构:
1顺序存储结构:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。顺
序存储结构把数据元素存储在一段连续的存储单元里,结点之间的关系由存储单元的
关系来直接或间接反映。其主要特点为:
结点中只有自身信息域,没有连接信息域,因此存储密度大,存储空间利用率高;
存储空间是连续的,可以通过计算直接确定数据结构中任意一个结点的存储地址。
2链式存储结构:借助指针来指示逻辑上相邻的数据元素在存储器中的物理位置,因此
可以把逻辑上相邻的两个元素存放在物理上不相邻的存储单元中。其主要特点为:
结构中除自身信息外,还有表示连接信息的指针域,因此比顺序存储结构的存储
密度小,存储空间利用率低;
存储空间可以是不连续的,因而更适合动态数据的管理。
1
3.算法定义及其特征
算法是解决某个特定问题的一种方法或一个过程。
计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是
算术运算;而在非数值性操作中主要进行的是检索、排序、插入、删除等等。
设计算法的基本过程
通过对问题进行详细地分析,抽象出相应的数学模型;
确定使用的数据结构,并在此基础上设计对此数据结构实施各种操作的算法;
选用某种语言将算法转换成程序;
调试并运行这些程序。
算法的五大特征
①有穷性;②确定性;③可行性;④输入;⑤输出。
算法设计的要求
①正确性:要求算法能够正确地执行预先规定的功能,并达到所期望的性能要求。
②可读性:为了便于理解、测试和修改算法,算法应该具有良好的可读性。
③健壮性:算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的
结果检测,并通过与用户对话的形式做出相应的处理选择。
④时间与空间效率:算法的时间与空间效率是指将算法变换为程序后,该程序在计算机
上运行时所花费的时间及所占据空间的度量。
时间复杂度
算法执行时间需要该算法所对应的程序在计算机上执行时所消耗的时间来衡量。计算消耗
时间可以采用事后统计的方法,也可采用事前分析估计的方法。
①基本操作:一个算法由控制语句和原操作(指固有数据类型的操作)组成,则算法时
间取决于两者的综合效果。为便于比较同一问题的不同算法的效率,通常的做法是从算法中选
取一种对所研究问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法的时间
量度。
②问题规模函数f(n):如果某个算法的执行时间同其基本操作的重复次数f(n)成正比,则
您可能关注的文档
- 2024研硕教育数二 二模答案.pdf
- 25年专升本自荐专业课备考资料 29、建筑力学.pdf
- 25年专升本自荐专业课备考资料 129、数字电子技术.pdf
- 25年专升本自荐专业课备考资料 168、剧目表演.pdf
- 25年专升本自荐专业课备考资料 175、素描与色彩基础.pdf
- 25年专升本自荐专业课备考资料 广播电视编导-广播电视编导基础知识完整版.pdf
- 25年专升本自荐专业课备考资料 广播电视编导-影视鉴赏-第六章-影视艺术的鉴赏与评论.pdf
- 25年专升本自荐专业课备考资料 国际经济与贸易-国际贸易基础知识试题.pdf
- 客户分析报告(3篇).docx
- 寒假劳动实践活动心得体会.docx
最近下载
- 100以内加减法竖式练习题-两位数加减法竖式练习题A4直接打印.doc VIP
- 铁道供电技术职业生涯规划书.pptx VIP
- 会计职业生涯规划书5篇.pdf VIP
- 2024最新民事起诉状.doc VIP
- 3D工程图学(华中科大)中国大学MOOC慕课 章节测验 客观题答案.docx
- 血液透析患者护理查房课件.pdf VIP
- 初级消防设施操作员.docx VIP
- 北京市宣武区2024-2025学年六年级数学第一学期期末调研试题含解析.doc VIP
- 2024-2025学年英语三年级上册人教精通版(三起)(2024)教学设计(附教材目录).docx VIP
- 二年级语文上册-第七单元【教材解读】.pptx VIP
文档评论(0)