数据结构课件NO基本概念

《数据结构课件NO基本概念》由会员分享，可在线阅读，更多相关《数据结构课件NO基本概念（36页珍藏版）》请在金锄头文库上搜索。

1、第一章 数据结构主要内容1.1数据结构的基本概念与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 排序数据结构国家等级考试大纲要求1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树 的前序、中序和后序遍历。 7. 顺

2、序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。1.1 数据结构的基本概念与算法 1.1.1 数据结构的基本概念1.数据结构的定义(1)数据：信息载体，能够被计算机识别、存储和加工 处理。可以使数值数据(整数、实数)，也可以是非数值 数据(声音、图像等) 。(2)数据元素：数据的基本单位，在计算机程序中通常 作为一个整体进行考虑和处理(又称结点、记录)。 数据项：一个数据元素由若干数据项组成，数据的不可分割的最小单位。 关键码：其值能唯一确定一个数据元素的数据项。 举例：图书管理系统 数据元素 数据项 关键码(一本书)书目信息 书目信息每一项 书号(唯一确定一本书)

3、学号姓名系别别住址电话电话981111李洪机械六舍5371111982111王刚刚电电子四舍5372111983211王将计计算机五舍5373211983212张张强机械六舎53722214个数据元素5个数 据项1个数 据项1个数 据元素(3)数据对象：具有相同性质的数据元素的集合。数据 元素是数据对象类的一个实例。 学号姓名系别别住址电话电话 981111李洪机械六舍5371111982111王刚刚电电子四舍5372111983211王将计计算机五舍5373211983212张张强机械六舎5372221关键码：值唯一能区别不同的 数据元素的数据项数据对象-由4个记录组成, 表中每行是一个记录

4、,每个 记录由5个数据项组成.(4)数据结构定义:相互之间存在着一种或多种关系的数据元素的集合。研究内容:数据的逻辑结构：各数据元素之间的逻辑关系 数据的存储结构：各数据元素在计算机中的存储关系 对各种数据结构进行的运算：添加，删除，排序等。2.数据的逻辑结构四类基本逻辑结构(1)集合结构：数据元素间的关系是“属于同一个集合” (2)线性结构：数据元素之间存在一个对一个的关系。(3)树形结构：数据元素之间存在一个对多个的关系。 (4)图形结构：数据元素之间存在多个对多个的关系。 学号姓名语语文数学C语语言1001张张三855492 1002李四928464 1003王五877473 . 集合结

5、构线 性 结 构树型结构图形结构：数据元素之间存在多个对多个的 关系，图形结构也称作网状结构。 线性结构与非线性结构概念结点:组成数据结构的数据元素称为一个结点。前后件关系:数据元素之间的固有关系可以用前后件关系(前驱与后继关系 )描述。举例：家庭成员辈分关系(父亲、儿子、女儿)，“父亲”是 “儿子”和“女儿”的前件， “儿子”和“女儿”是 “父亲”后 件。 线性结构有且只有一个根结点每个结点最多有一个前件，也最多有一个后件非线性结构一个数据结构如果不是线性结构，则称之为非线性结构。数 据元素的前后关系复杂，一个结点既可以有多个前件，也可 以有多个后件。树型、图形结构属于非线性结构。3.数据的

6、存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式。 数据存储结构中不仅存放各数据元素信息，还存放前后件 关系的信息。 实现方式： (1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻 的存储单元中。主要用于线性结构。通常借助于数组来实 现。顺序存储结构的线性表线性表(a1, a2, a3, a4)存储单元 的地址即 物理地址(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址 相邻，元素间逻辑关系通过附加的指针字段来表示。通常 借助于指针类型实现。 链 式 存 储 结 构 的 线 性 表线性表(a1, a2, a3, a4)存储单元 的地址即 物理地址指针域：存 放下一个结 点的地

7、址a1,a2在逻辑 上相邻,而在 机内存储时, 存储单元的 地址(100,105) 并不相邻.链式存储结构的特点每个结点由两部分组成：一部分存放数据，另一部分存储 指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。数据运算(插入和删除等)灵活。 (3)索引存储方法和散列存储方法(为了查找方便) 4.数据结构的表示(1)二元关系表示B=( D, R ) B：数据结构 D：数据元素的集合 R：D上的关系 (反映数据元素前后件关系) 家庭成员数据结构 B=( D, R ) D =父亲,儿子,女儿 R =(父亲,儿子),(父亲,女儿)(2)图形表示D中每个数据元素用标有元素值的方框表示,简称

8、结点。R中每个二元组,用一条有向线段从前件结点指向后件结点。根结点：没有前件的结点叶子结点(终端结点)：没有后件的结点几种基本数据结构的节点图：叶子结点根结点叶子结点根结点5.数据的运算定义：在数据的逻辑结构上定义的操作算法 常见运算：插入、删除、查找、排序和更新等 分类： 加工型运算：运算改变了数据结构的值引用型运算：不改变值，只查询或求得结构的值。 6.数据类型及其分类定义：数据类型是一个值的集合和定义在这个值集上的一 组操作的总称。例：C语言中的整型变量，其值为某个区 间上整数，定义在其上的操作为：加，减、乘、除和求余 数等算术运算。分类：非结构的原子类型和结构类型（1）非结构的原子类型

9、：原子类型的值是不可分解的。如 ：程序设计语言中的基本类型（整型，实型，字符型，指 针类型和空类型）。 （2）结构类型：结构类型的值是由若干成分按某种结构组 成的，因此是可分解的，并且它的成分可以是非结构的， 也可以是结构的。 例如：用C语 言编程序时， 描述一个学生 信息的结构可 以如下表示： typedef struct int yy; / 年号 int mm; / 月号 int dd; / 日号 datetype; / 日期类型 typedef struct char nm8; / 学号 char name18; / 姓名 char sex; / 性别 datetype date; /

10、出生日期 studenttype; / 学生类型 1.1 数据结构的基本概念与算法 总结1.数据结构定义 2. 数据的逻辑结构（集合、线性、树形、图形） 3. 数据的存储结构（顺序、链式） 4. 数据结构的表示 5. 数据运算：插入、删除、查找、排序和更新等 6. 数据类型及其分类 一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析u首先要从具体问题抽象出一个适当的数学模型； u然后设计一个解此数学模型的算法； u最后采用一种计算机语言编出程序，调试、修改 直至得到最终答案。用计算机解决一个具体问

11、题时，大 致需要经过下列几个步骤： 一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析2.算法特性：有穷性： 一个算法应包含有限个操作步骤，而且每一步 都应在有限时间内完成。确定性：算法中每一条指令必须有确切的含义，确保不会 产生二义性。可行性：算法中指定的操作都是可以通过基本运算执行有 限次后实现。输入：一个算法有零个或多个的输入，这些输入取自于某 个特定的对象集合。输出：一个算法有一个或多个的输出，这些输出是同输入 有着某些特定关系的量。 一. 算法的基本概念 1.定义： 为解决某个特定问题而

12、采取的确定且有限的步骤。2.算法特性：有穷性： 一个算法应包含有限个操作步骤，而且每一步 都应在有限时间内完成。确定性：算法中每一条指令必须有确切的含义，确保不会 产生二义性。可行性：算法中指定的操作都是可以通过基本运算执行有 限次后实现。输入：一个算法有零个或多个的输入，这些输入取自于某 个特定的对象集合。输出：一个算法有一个或多个的输出，这些输出是同输入 有着某些特定关系的量。 二. 算法的基本要素及描述1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析1.算法基 本要素构 成对数据对 象的运算 和操作算法的控 制结构算术运算: 加、减、乘、除 逻辑运算：与、或、非等运

13、算 关系运算：大于、小于、等于等 数据传输：赋值、输入、输出顺序 选择 循环（重复）2. 算法的描述: 自然语言，伪代码，流程图, N-S图, 类C 一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。1.1 数据结构的基本概念与算法1.1.2 1.1.2 算法及算法分析 2.算法特性：有穷性： 一个算法应包含有限个操作步骤，而且每一步 都应在有限时间内完成。确定性：算法中每一条指令必须有确切的含义，确保不会 产生二义性。可行性：算法中指定的操作都是可以通过基本运算执行有 限次后实现。输入：一个算法有零个或多个的输入，这些输入取自于某 个特定的对象集合。输出：一个算法

14、有一个或多个的输出，这些输出是同输入 有着某些特定关系的量。 二. 算法的基本要素及描述1.算法基 本要素构 成对数据对 象的运算 和操作算法的控 制结构算术运算:加、减、乘、除 逻辑运算：与、或、非等运算 关系运算：大于、小于、等于等 数据传输：赋值、输入、输出顺序 选择 循环（重复）2. 算法的描述: 自然语言，伪代码，流程图, N-S图, 类C 三.算法设计要求（评价算法标准）1.正确性：执行结果应满足预先的功能和性能要求 2.可读性：思路清晰、层次分明、简单明了、易读易懂。 3.健壮性：输入数据非法时，算法能作适当处理，不致于引起严重后果 4 .效率： 有效使用存储空间和较高的时间效率

15、。 四.算法设计的基本方法1. 列举法：列举出所有可能情况，用给定条件检验哪些是需要的， 哪些是不需要的(如用循环解决百元买百鸡问题）。2. 归纳法：列举少量简单而又特殊的情况，分析归纳出一般结论。 3.递推法：从已知初始条件出发，逐步推出各种中间结果和最后结 果（如猴子吃桃）。 4.递归法：解决复杂问题时，将问题逐层分解，归纳为一些简单问 题，解决了最后简单问题后，再沿原来的逆过程逐步综合 （如求某数的阶乘）。5.减半递推技术（分治法）：(补充） 减少：把问题规模减半，而性质不变 递推：重复减半的过程6. 回溯法 （补充） 在工程上有些实际问题很难归纳出一组简单的递推公式或 直关的求解步骤，并且也不能进行无限的列举。对于这类 问题，一种有效的方法是“试”，通过对问题的分析，找出 一个解决问题的线索，然后沿着这个线索逐步试探，若试 探成功，就得到问题的解，若试探失败，就逐步回退，换 其他路线再逐步试探。 一. 算法的基本概念 1.定义： 为解决某个特定问题而采取的确定且有限的步骤。 二. 算法的基本要素及描述 三.算法设计要求（评价算法标准） 四.算法设计的基本方法1.1 数据结构的基本概念与算法1.1.2