数据库第1章 绪论

《数据库第1章 绪论》由会员分享，可在线阅读，更多相关《数据库第1章 绪论（12页珍藏版）》请在金锄头文库上搜索。

1、数据库第数据库第 1 1 章章 绪论绪论本文由被风掠过一贡献ppt 文档可能在 WAP 端浏览体验不佳。建议您优先选择 TXT，或下载源文件到本机查看。数据结构(C+版)彭慧卿 主讲具体安排共 48 学时 学时 6 次实验 次实验 成绩： 成绩：70%（期末考试）+30%（平时成绩） （期末考试） （平时成绩） 平时成绩：考勤（ 分） 、作业 作业（ 分） 、上机情况及实 平时成绩：考勤（10分） 、作业（10 分） 、上机情况及实 验报告（ 分 验报告（10 分）等关于教材主教材 王红梅.数据结构（ 版 王红梅.数据结构（C版）.清华大学出版社 辅导及实验教材 王红梅.数据结构学习辅导与实验

2、指导. 王红梅.数据结构学习辅导与实验指导.清华大学出版社 参考教材 严蔚敏.数据结构.清华大学出版社.1997 1. 严蔚敏.数据结构.清华大学出版社.1997 王晓东.数据结构与算法设计.电子工业出版社.2002 2. 王晓东.数据结构与算法设计.电子工业出版社.2002 曹宏庆译.如何求解问题.中国水利水电出版社.2003 3. 曹宏庆译.如何求解问题.中国水利水电出版社.2003学习目标掌握基本的数据结构工具箱复用、修改、 工具箱复用、修改、重组培养算法设计能力、 培养算法设计能力、程序设计能力算法程序的灵魂 程序的灵魂 算法 问题求解过程：问题想法算法 问题求解过程：问题想法算法程序

3、 程序设计研究的层次：算法方法学语言 程序设计研究的层次：算法方法学语言工具培养算法分析能力评价算法、 评价算法、改进算法第 1 章 绪 论本章的基本内容是： 本章的基本内容是：数据结构的兴起和发展 数据结构的研究对象 数据结构的基本概念 算法及算法分析1.1 数据结构的兴起和发展程序设计的实质是什么? 程序设计的实质是什么 数据表示： 数据表示：将数据存储在计算机中 数据处理：处理数据， 数据处理：处理数据，求解问题 数据结构问题起源于程序设计 计算机的应用领域从科学计算发展到非数值处理领域1.1 数据结构的兴起和发展数据结构随着程序设计的发展而发展1. 无结构阶段 2. 结构化阶段：数据结

4、构算法程序 结构化阶段：数据结构算法 3. 面向对象阶段： （数据结构算法）程序 面向对象阶段： 数据结构算法） ）程序数据结构的发展并未终结1.2 数据结构的研究对象计算机求解问题:问题抽象出问题的模型 问题抽象出问题的模型求模型的解问题数值问题、非数值问题数 值 问 题数学方程 非数值问题 非数值问题数据结构1.2 数据结构的研究对象学籍管理问题表结构 例 1 学籍管理问题 表结构完成什么功能?各表项之间是什么关系？ 完成什么功能 各表项之间是什么关系？ 各表项之间是什么关系学号 0001 0002 0003 姓名 王 军 李 明 汤晓影 性别 男 男 女 出生日期 1983/09/02

5、1982/12/25 1984/03/26 政治面貌 团员 党员 团员 1.2 数据结构的研究对象人机对弈问题树结构 例 2 人机对弈问题 树结构如何实现对弈?各格局之间是什么关系？ 如何实现对弈 各格局之间是什么关系？ 各格局之间是什么关系.1.2 数据结构的研究对象教学计划编排问题图结构 例 3 教学计划编排问题 图结构如何表示课程之间的先修关系？ 如何表示课程之间的先修关系？编号C1 C2 C3 C4 C5 C6 C7课程名称高等数学 计算机导论 离散数学 程序设计 数据结构 计算机原理 数据库原理先修课无 无 C1 C1, C2 C3, C4 C 2 , C4 C4, C5, C6C3

6、 C1 C4 C2 C6C5C71.2 数据结构的研究对象数据结构是研究非数值问题中计 数据结构是研究非数值问题中计 非数值 算机的操作对象以及它们之间的关系 操作对象以及它们之间的 算机的操作对象以及它们之间的关系 操作的学科 的学科。 和操作的学科。1.3 数据结构的基本概念数据结构的基本概念数据：所有能输入到计算机中并能被计算机程序识别和处理 数据 的符号集合。 数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个 数据元素 整体进行考虑和处理。 数据项：构成数据元素的不可分割的最小单位。 数据项 数据对象：具有相同性质的数据

7、元素的集合。1.3 数据结构的基本概念数据、数据元素、 数据、数据元素、数据项之间的关系 包含关系：数据是由数据元素组成，数据元素是由数据项组成。 包含关系：数据是由数据元素组成，数据元素是由数据项组成。 数据元素是讨论数据结构时涉及的最小数据单位， 数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项 是讨论数据结构时涉及的最小数据单位 一般不予考虑。 一般不予考虑。1.3 数据结构的基本概念数据结构的基本概念数据结构：相互之间存在一定关系的数据元素的集合。 数据结构：相互之间存在一定关系的数据元素的集合。按照视 关系的数据元素的集合 点的不同，数据结构分为逻辑结构和存储结构。 点的不同

8、，数据结构分为逻辑结构和存储结构。 逻辑关系的整体 逻辑结构：指数据元素之间逻辑关系的整体。 逻辑结构：指数据元素之间逻辑关系的整体。关联方式或邻接关系学籍管理问题中，表项之间的逻辑关系指的是什么？ 学籍管理问题中，表项之间的逻辑关系指的是什么？ 人机对弈问题中，格局之间的逻辑关系指的是什么？ 人机对弈问题中，格局之间的逻辑关系指的是什么？ 教学计划编排问题中，课程之间的逻辑关系指的是什么？ 教学计划编排问题中，课程之间的逻辑关系指的是什么？数据的逻辑结构是从具体问题抽象出来的数据模型 数据的逻辑结构是从具体问题抽象出来的数据模型1.3 数据结构的基本概念数据结构的基本概念数据结构：相互之间存

9、在一定关系的数据元素的集合。 按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。 存储结构：又称为物理结构，是数据及其逻辑结构在计 算机中的表示。 内存存储结构实质上是内存分配， 存储结构实质上是内存分配， 在具体实现时，依赖于计算机语言。 在具体实现时，依赖于计算机语言。1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类： 数据结构从逻辑上分为四类： 集合： 集合：数据元素之间就是 属于同一个集合” “属于同一个集合” ；1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合”

10、 ； 线性结构：数据元素之间 存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类： 集合：数据元素之间就是 “属于同一个集合” ； 线性结构：数据元素之间 存在着一对一的线性关系； 树结构：数据元素之间存在 着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念数据结构从逻辑上分为四类： 数据结构从逻辑上分为四类： 集合： 集合：数据元素之间就是 属于同一个集合” “属于同一个集合” ； 线性结构： 线性结构：数据元素之间 存在着一对一的线性关系； 存在着一对一的线性关系； 树结构： 树结构：数据元素之间存在 着一对多的层次关系； 着一对多的

11、层次关系； 图结构： 图结构：数据元素之间存在 着多对多的任意关系。 着多对多的任意关系。1.3 数据结构的基本概念通常有两种存储结构： 通常有两种存储结构： ：（bat, cat, eat） 例：（ ） 1. 顺序存储结构：用一组连续的存储 顺序存储结构：用一组连续 连续的存储 依次存储数据元素 单元依次存储数据元素， 单元依次存储数据元素，数据元素之间 的逻辑关系由元素的存储位置来表示。 存储位置来表示 的逻辑关系由元素的存储位置来表示。 起始地址bat cat eat1.3 数据结构的基本概念通常有两种存储结构： 通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储 顺序存储结构：

12、用一组连续 连续的存储 依次存储数据元素 单元依次存储数据元素， 单元依次存储数据元素，数据元素之间 的逻辑关系由元素的存储位置来表示。 存储位置来表示 的逻辑关系由元素的存储位置来表示。 2. 链接存储结构：用一组任意的存储 链接存储结构：用一组任意 任意的存储 单元存储数据元素， 单元存储数据元素，数据元素之间的逻 辑关系用指针 指针来表示 辑关系用指针来表示 。例：（bat, cat, eat） ：（ ）0200 0208 cat 0325 bat 0200 03000325 eat 1.3 数据结构的基本概念逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，面向问题的 数据的逻

13、辑结构属于用户视图，是面向问题的，反映了数据内部 的构成方式；数据的存储结构属于具体实现的视图， 的构成方式；数据的存储结构属于具体实现的视图，是面向计算 机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的 一种数据的逻辑结构可以用多种存储结构来存储， 存储结构，其数据处理的效率往往是不同的。 存储结构，其数据处理的效率往往是不同的。数据结构的基本概念（小结） 1.3 数据结构的基本概念（小结）非数值问题 数据的逻辑结构 集合 线性结构 树结构 图结构 顺序存储 链式存储数 据 表 示数据的存储结构数据的操作：插入、删除、修改、检索、 数据的操作：插入、删除、修改、检索、排序等1

14、.4 算法及算法分析算法的相关概念1.算法 （ Algorithm） :是对 特定问题 求解步骤的 算法（ 是对特定问题 算法 ） 是对 特定问题求解步骤的 一种描述， 指令的有限序列。 一种描述，是指令的有限序列。 2. 算法的五大特性： 算法的五大特性： 输入：一个算法有零个或多个输入。 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束， 有穷性：一个算法必须总是在执行有穷步之后结束，且 每一步都在有穷时间内完成。 每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义， 确定性

15、：算法中的每一条指令必须有确切的含义，对于 相同的输入只能得到相同的输出。 相同的输入只能得到相同的输出。 可行性： 可行性：算法描述的操作可以通过已经实现的基本操作 执行有限次来实现。 执行有限次来实现。1.4 算法及算法分析算法的描述方法 算法的描述方法 自然语言 流程图 程序设计语言 伪代码1.4 算法及算法分析算法的描述方法自然语言 自然语言 算法的描述方法 优点：优点：容易理解 缺点：冗长、 缺点：冗长、二义性 使用方法： 使用方法：粗线条描述算法思想 注意事项：避免写成自然段 注意事项：1.4 算法及算法分析算法的描述方法流程图 流程图 算法的描述方法 优点： 优点：流程直观 缺点

16、：缺少严密性、 缺点：缺少严密性、灵活性 使用方法： 使用方法：描述简单算法 注意事项： 注意事项：注意抽象层次1.4 算法及算法分析例：欧几里德算法开始 输入 m 和 n流 程 图r=m % n r=0 N m=n；n=r 输出 n 结束 Y1.4 算法及算法分析算法的描述方法程序设计语言 程序设计语言 算法的描述方法 优点： 优点：能由计算机执行 缺点：抽象性差， 缺点：抽象性差，对语言要求高 使用方法： 使用方法：算法需要验证 注意事项： 注意事项：将算法写成子函数1.4 算法及算法分析算法的描述方法伪代码 伪代码 算法的描述方法 伪代码（ ）：介于自然语言和 伪代码（Pseudocode）：介于自然语言和 ）：程序设计语言之间的方法， 程序设计语言之间的方法，它采用某一程序 设计语言的基本语法， 设计语言的基本语法，操作指令可以结合自 然语言来