- 1、本文档共35页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
主讲教师:罗先文E-mail:xianwenl@swu.edu.cn 1、上课认真听讲,适当做好笔记,按时交作业。 2、考试成绩分两部分:平时成绩(包括作业、出勤)占30%,期末成绩占70%。实验单独计算成绩,单独计算学分。 3、课后需要多读课文和参考书,上网查看相关内容,在理解基本内容的基础上,多看、多做习题。 4、上机实验十分重要,一定要在上机前做好充分准备,多采用不同的数据存储结构和不同的实现算法解决一个问题。 第1章 绪 论 1.1 数据结构的基本概念 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 1.1 数据结构的基本概念 1、举例 建立一个学生档案。学生表包括学号、姓名、性别、籍贯。要求:查找“王红”是否存在。 解决的方法步骤: 如何记录所有学生记录(及选择何种逻辑数据结构)? 选择何种存储结构? 若把所有记录依次存储在一个数组中——采用顺序存储结构 若采用指针链表——采用链式存储结构 2、基本术语 (1)数据:所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息 )。 (2)数据元素:是数据的基本单位,具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。 (3)数据项:构成数据元素的项目。它是数据不可分割的最小单位。 (4)数据类型:指一个类型和定义在这个类型上的操作集合。例:C语言(基本类型:整型、浮点型、字符型等构造类型:数组、结构、联合、指针、枚举等) (5)抽象数据元素:抽象定义的、没有实际含义的数据元素。 (6)抽象数据类型:用户自己定义的数据类型。 2、基本术语 (续) (1) R=(D, S) D={ a, b, c, d, e, f } S={a,e, b,c, c,a, e,f, f,d} d1 d5 d2 d4 d3 答:物理结构亦称存储结构,是数据的逻辑结构在计算机存储器内的表示(或映像)。它依赖于计算机。 答:在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 1.4 什么是抽象数据类型 1 数据类型与抽象数据类型的区别 2 抽象数据类型如何定义 抽象数据类型示例 ADT Triplet { 数据对象:D = {e1,e2,e3| e1,e2,e3属于ElemSet} 数据关系:R = {e1,e2,e2,e3} 基本操作:InitTriplet(T,v1,v2,v3) DestroyTriplet(T) Get(T,i,e) Put(T,i,e) …… } ADT Triplet 3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。即利用处理器中已存在的数据类型来说明新的结构,用已经实现的操作来组合新的操作。 1.5 算法和算法分析 1 什么是算法?如何评判算法的好坏? 2 时间复杂度和空间复杂度如何表示? 3 计算举例 1 什么是算法?如何评判一个算法的好坏? (2)算法的描述方式 ? 自然语言 ? 程序设计语言 ? 流程图 ? 类高级语言(类C语言、类Pascal语言等) (3)类C语言的描述语法 类C语言精选了C语言的一个核心子集,也做了若干扩充,以利于描述。如:存储结构用typedef;数据元素类型约定为ElemType;在形参表中,以打头的参数为引用参数;等等。 (4)算法选择时效率的考虑 虽然我们希望所选的算法占用额外空间小,运行时间短,其他性能也好,但计算机的时间和空间这两大资源往往相互抵触。所以,一般算法选择的原则是: 对于反复使用的算法应选择运行时间短的算法;而使用次数少的算法可力求简明、易于编写和调试;对于处理的数据量较大的算法可从如何节省空间的角度考虑。 本章小结 数据结构课程—— 数据结构+算法=程序,涉及数学、计算机硬件和软件。 数据结构定义——指互相有关联的数据元素的集合,可用data_Structure=(D,S)表示。 数据结构内容——数据的逻辑结构、存储结构和基本运算 。 数据结构描述工具——抽象数据类型和类C语言。 算法效率——时间效率和空间效率 。 作 业 1.1 判断下列叙述的对错。 (1) 数据元素是数据的最小单位。 (2) 数据结构是数据对象与对象中数据元素之间关系的集合。 (3) 数据的逻辑结构是指各数据元素
文档评论(0)