资源预览内容
第1页 / 共36页
第2页 / 共36页
第3页 / 共36页
第4页 / 共36页
第5页 / 共36页
第6页 / 共36页
第7页 / 共36页
第8页 / 共36页
第9页 / 共36页
第10页 / 共36页
亲,该文档总共36页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第一章 数据结构主要内容1.1数据结构的基本概念与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 排序数据结构国家等级考试大纲要求1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。 2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。 3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念;二叉树的定义及其存储结构;二叉树 的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法;基本排序算法(交换类排序,选择类排序,插入类排序)。1.1 数据结构的基本概念与算法 1.1.1 数据结构的基本概念1.数据结构的定义(1)数据:信息载体,能够被计算机识别、存储和加工 处理。可以使数值数据(整数、实数),也可以是非数值 数据(声音、图像等) 。(2)数据元素:数据的基本单位,在计算机程序中通常 作为一个整体进行考虑和处理(又称结点、记录)。 数据项:一个数据元素由若干数据项组成,数据的不可分割的最小单位。 关键码:其值能唯一确定一个数据元素的数据项。 举例:图书管理系统 数据元素 数据项 关键码(一本书)书目信息 书目信息每一项 书号(唯一确定一本书)学号姓名系别别住址电话电话981111李洪机械六舍5371111982111王刚刚电电子四舍5372111983211王将计计算机五舍5373211983212张张强机械六舎53722214个数据元素5个数 据项1个数 据项1个数 据元素(3)数据对象:具有相同性质的数据元素的集合。数据 元素是数据对象类的一个实例。 学号姓名系别别住址电话电话 981111李洪机械六舍5371111982111王刚刚电电子四舍5372111983211王将计计算机五舍5373211983212张张强机械六舎5372221关键码:值唯一能区别不同的 数据元素的数据项数据对象-由4个记录组成, 表中每行是一个记录,每个 记录由5个数据项组成.(4)数据结构定义:相互之间存在着一种或多种关系的数据元素的集合。研究内容:数据的逻辑结构:各数据元素之间的逻辑关系 数据的存储结构:各数据元素在计算机中的存储关系 对各种数据结构进行的运算:添加,删除,排序等。2.数据的逻辑结构四类基本逻辑结构(1)集合结构:数据元素间的关系是“属于同一个集合” (2)线性结构:数据元素之间存在一个对一个的关系。(3)树形结构:数据元素之间存在一个对多个的关系。 (4)图形结构:数据元素之间存在多个对多个的关系。 学号姓名语语文数学C语语言1001张张三855492 1002李四928464 1003王五877473 . 集合结构线 性 结 构树型结构图形结构:数据元素之间存在多个对多个的 关系,图形结构也称作网状结构。 线性结构与非线性结构概念结点:组成数据结构的数据元素称为一个结点。前后件关系:数据元素之间的固有关系可以用前后件关系(前驱与后继关系 )描述。举例:家庭成员辈分关系(父亲、儿子、女儿),“父亲”是 “儿子”和“女儿”的前件, “儿子”和“女儿”是 “父亲”后 件。 线性结构有且只有一个根结点每个结点最多有一个前件,也最多有一个后件非线性结构一个数据结构如果不是线性结构,则称之为非线性结构。数 据元素的前后关系复杂,一个结点既可以有多个前件,也可 以有多个后件。树型、图形结构属于非线性结构。3.数据的存储结构定义:数据的逻辑结构在计算机存储空间中的存放形式。 数据存储结构中不仅存放各数据元素信息,还存放前后件 关系的信息。 实现方式: (1)顺序存储方式:逻辑上相邻的元素存储在物理位置相邻 的存储单元中。主要用于线性结构。通常借助于数组来实 现。顺序存储结构的线性表线性表(a1, a2, a3, a4)存储单元 的地址即 物理地址(2)链式存储方式:对逻辑上相邻的元素不要求其物理地址 相邻,元素间逻辑关系通过附加的指针字段来表示。通常 借助于指针类型实现。 链 式 存 储 结 构 的 线 性 表线性表(a1, a2, a3, a4)存储单元 的地址即 物理地址指针域:存 放下一个结 点的地址a1,a2在逻辑 上相邻,而在 机内存储时, 存储单元的 地址(100,105) 并不相邻.链式存储结构的特点每个结点由两部分组成:一部分存放数据,另一部分存储 指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。数据运算(插入和删除等)灵活。 (3)索引存储方法和散列存储方法(为了查找方便) 4.数据结构的表示(1)二元关系表示B=( D, R ) B:数据结构 D:数据元素的集合 R:D上的关系 (反映数据元素前后件关系) 家庭成员数据结构 B=( D, R ) D =父亲,儿子,女儿 R =(父亲,儿子),(父亲,女儿)(2)图形表示D中每个数据元素用标有元素值的方框表示,简称结点。R中每个二元组,用一条有向线段从前件结点指向后件结点。根结点:没有前件的结点叶子结点(终端结点):没有后件的结点几种基本数据结构的节点图:叶子结点根结点叶子结点根结点5.数据的运算定义:在数据的逻辑结构上定义的操作算法 常见运算:插入、删除、查找、排序和更新等 分类: 加工型运算:运算改变了数据结构的值引用型运算:不改变值,只查询或求得结构的值。 6.数据类型及其分类定义:数据类型是一个值的集合和定义在这个值集上的一 组操作的总称。例:C语言中的整型变量,其值为某个区 间上整数,定义在其上的操作为:加,减、乘、除和求余 数等算术运算。分类:非结构的原子类型和结构类型(1)非结构的原子类型:原子类型的值是不可分解的。如 :程序设计语言中的基本类型(整型,实型,字符型,指 针类型和空类型)。 (2)结构类型:结构类型的值是由若干成分按某种结构组 成的,因此是可分解的,并且它的成分可以是非结构的, 也可以是结构的。 例如:用C语 言编程序时, 描述一个学生 信息的结构可 以如下表示: typedef struct int yy; / 年号 int mm; / 月号 int dd; / 日号 datetype; / 日期类型 typedef struct char nm8; / 学号 char name18; / 姓名 char sex; / 性别 datetype date; / 出生日期 studenttype; / 学生类型 1.1 数据结构的基本概念与算法 总结1.数据结构定义 2. 数据的逻辑结构(集合、线性、树形、图形) 3. 数据的存储结构(顺序、链式) 4. 数据结构的表示 5. 数据运算:插入、删除、查找、排序和更新等 6. 数据类型及其分类 一. 算法的基本概念 1.定义: 为解决某个特定问题而采取的确定且有限的步骤。1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析u首先要从具体问题抽象出一个适当的数学模型; u然后设计一个解此数学模型的算法; u最后采用一种计算机语言编出程序,调试、修改 直至得到最终答案。用计算机解决一个具体问题时,大 致需要经过下列几个步骤: 一. 算法的基本概念 1.定义: 为解决某个特定问题而采取的确定且有限的步骤。1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析2.算法特性:有穷性: 一个算法应包含有限个操作步骤,而且每一步 都应在有限时间内完成。确定性:算法中每一条指令必须有确切的含义,确保不会 产生二义性。可行性:算法中指定的操作都是可以通过基本运算执行有 限次后实现。输入:一个算法有零个或多个的输入,这些输入取自于某 个特定的对象集合。输出:一个算法有一个或多个的输出,这些输出是同输入 有着某些特定关系的量。 一. 算法的基本概念 1.定义: 为解决某个特定问题而采取的确定且有限的步骤。2.算法特性:有穷性: 一个算法应包含有限个操作步骤,而且每一步 都应在有限时间内完成。确定性:算法中每一条指令必须有确切的含义,确保不会 产生二义性。可行性:算法中指定的操作都是可以通过基本运算执行有 限次后实现。输入:一个算法有零个或多个的输入,这些输入取自于某 个特定的对象集合。输出:一个算法有一个或多个的输出,这些输出是同输入 有着某些特定关系的量。 二. 算法的基本要素及描述1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析1.算法基 本要素构 成对数据对 象的运算 和操作算法的控 制结构算术运算: 加、减、乘、除 逻辑运算:与、或、非等运算 关系运算:大于、小于、等于等 数据传输:赋值、输入、输出顺序 选择 循环(重复)2. 算法的描述: 自然语言,伪代码,流程图, N-S图, 类C 一. 算法的基本概念 1.定义: 为解决某个特定问题而采取的确定且有限的步骤。1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析 2.算法特性:有穷性: 一个算法应包含有限个操作步骤,而且每一步 都应在有限时间内完成。确定性:算法中每一条指令必须有确切的含义,确保不会 产生二义性。可行性:算法中指定的操作都是可以通过基本运算执行有 限次后实现。输入:一个算法有零个或多个的输入,这些输入取自于某 个特定的对象集合。输出:一个算法有一个或多个的输出,这些输出是同输入 有着某些特定关系的量。 二. 算法的基本要素及描述1.算法基 本要素构 成对数据对 象的运算 和操作算法的控 制结构算术运算:加、减、乘、除 逻辑运算:与、或、非等运算 关系运算:大于、小于、等于等 数据传输:赋值、输入、输出顺序 选择 循环(重复)2. 算法的描述: 自然语言,伪代码,流程图, N-S图, 类C 三.算法设计要求(评价算法标准)1.正确性:执行结果应满足预先的功能和性能要求 2.可读性:思路清晰、层次分明、简单明了、易读易懂。 3.健壮性:输入数据非法时,算法能作适当处理,不致于引起严重后果 4 .效率: 有效使用存储空间和较高的时间效率。 四.算法设计的基本方法1. 列举法:列举出所有可能情况,用给定条件检验哪些是需要的, 哪些是不需要的(如用循环解决百元买百鸡问题)。2. 归纳法:列举少量简单而又特殊的情况,分析归纳出一般结论。 3.递推法:从已知初始条件出发,逐步推出各种中间结果和最后结 果(如猴子吃桃)。 4.递归法:解决复杂问题时,将问题逐层分解,归纳为一些简单问 题,解决了最后简单问题后,再沿原来的逆过程逐步综合 (如求某数的阶乘)。5.减半递推技术(分治法):(补充) 减少:把问题规模减半,而性质不变 递推:重复减半的过程6. 回溯法 (补充) 在工程上有些实际问题很难归纳出一组简单的递推公式或 直关的求解步骤,并且也不能进行无限的列举。对于这类 问题,一种有效的方法是“试”,通过对问题的分析,找出 一个解决问题的线索,然后沿着这个线索逐步试探,若试 探成功,就得到问题的解,若试探失败,就逐步回退,换 其他路线再逐步试探。 一. 算法的基本概念 1.定义: 为解决某个特定问题而采取的确定且有限的步骤。 二. 算法的基本要素及描述 三.算法设计要求(评价算法标准) 四.算法设计的基本方法1.1 数据结构的基本概念与算法1.1.2
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号