数据结构第1章绪论资料.ppt

数据结构与算法 作 者：胡明 王红梅 出版社：电子工业出版社 邮 箱：wanghm@mail.ccut.edu.cn;课程性质;教学目标;学编程的境界;学习要求;;1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：The Art of Computer Programming，他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉——图灵奖，此时，他年仅36岁。;1.1 问题求解与程序设计 ;利用计算机求解问题的一般过程?;【问题】哥尼斯堡七桥问题;1.1 问题求解与程序设计 ;;;Smith先生和太太邀请四对夫妻来参加晚宴。每个人来的时候，房间里的一些人都要和其他人握手。当然，每个人都不会和自己的配偶握手，也不会跟同一个人握手两次???之后，Smith先生问每个人和别人握了几次手，他们的答案都不一样。问题是，Smith太太和别人握了几次手？;例1-2 手机电话号码查询问题;;; 计算机求解问题: 问题→抽象出问题的模型→求模型的解 问题——数值问题、非数值问题 数 值 问 题→数学方程 非数值问题→数据结构 ;;例1-5 学籍管理问题;例1-6 人——机对弈问题;例1-7 七巧板涂色问题 ;本书讨论非数值问题的数据组织和处理，主要内容如下： （1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系； （2）数据的存储结构：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系； （3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据； （4）常用的数据处理技术：包括查找技术和排序技术等； （5）基本的算法设计技术：包括蛮力法、分治法、减治法、贪心法和动态规划法等，并从算法设计技术的角度讨论线性表、树和图等数据结构的基本操作，以及查找算法和排序算法的设计思想和设计过程。;1.2 数据结构的基本概念;数据、数据元素、数据项之间的关系;数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。;数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。;数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。;数据结构：相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 逻辑结构：指数据元素之间逻辑关系的整体。 存储结构：又称为物理结构，是数据及其逻辑结构在计算机中的表示。;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系；;数据结构从逻辑上分为四类： ⑴ 集合：数据元素之间就是 “属于同一个集合” ； ⑵ 线性结构：数据元素之间 存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在 着一对多的层次关系； ⑷ 图结构：数据元素之间存在 着多对多的任意关系。;通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。;通常有两种存储结构： 1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。 2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。;逻辑结构和存储结构之间的关系;抽象数据类型;1.2 数据结构的基本概念;ADT 抽象数据类型名 Data 数据元素之间逻辑关系的定义 Operation 操作1 前置条件：执行此操作前数据所必须的状态 输