North China Electric Power University 数据结构 Data Structure 华北电力大喾计算机斛学与工程柰 Dept of Computer Science& Engineering of North China Electric Power University
数据结构 North China Electric Power University Data Structure 华北电力大学计算机科学与工程系 Dept. of Computer Science&Engineering of North China Electric Power University
North China Electric Power University 第一章绪论 ★課程简介 ★基本念 ★算法 ★算法语言的说明
第一章 绪 论 ★ 课程简介 ★ 基本概念 ★ 算法 ★ 算法语言的说明 North China Electric Power University
North China Electric Power University ★课程简介 开设本课程的必要性以及课程的特点: 1.计算机专业重要的专业基础课之 2需要有关“程序设计语言”和“离散数学 3.祖较抽果程的基础
开设本课程的必要性以及课程的特点： 1. 计算机专业重要的专业基础课之一. 2. 需要有关“程序设计语言”和“离散数学 ” 的知识作为课程的基础. 3. 实践性较强. North China Electric Power University ★ 课程简介
North China Electric Power University 算法+数据结构=程序( Niklaus wirth) (Algorithm+ Data structure=Program) 程序设计:为计算机处理问题编写的一组指令 算法:处理问题的策略。 数据结构:问题的数学模型。 程序设计的实质是数据的表示和数据处理为此 应提出问题的数学模型和设计相应的算法。 例如:桥梁结构的应力计算 (结构静力分析、线性代数方程) 例如:全球天气预报(环流模式方程)
算法+数据结构=程序(Niklaus Wirth) （Algorithm+Data structure=Program) 程序设计：为计算机处理问题编写的一组指令。 算法：处理问题的策略。 数据结构：问题的数学模型。 程序设计的实质是数据的表示和数据处理,为此 应提出问题的数学模型和设计相应的算法。 例如：桥梁结构的应力计算 （结构静力分析、线性代数方程） 例如：全球天气预报（环流模式方程） North China Electric Power University
North China Electric Power University 例如:预报人口增长率(微分方程) 例如:计算机对弈(对弈的规则和策略) 例如:酒店客房管理系统中的客房分配问题 例如:铺设煤气管道问题 18.2 328 8. 328 8. 121 2.1 44652.792 79.2 56.4 213/41110 21.3 41.1 105 85.6 673 98.7 (a)居民区示意图 (b)铺设煤气管道设计图
例如：预报人口增长率（微分方程） 例如：计算机对弈（对弈的规则和策略） 例如：酒店客房管理系统中的客房分配问题 例如：铺设煤气管道问题 A B C D I H G E F 18.2 32.8 44.6 12.1 8.7 56.4 21.3 41.1 67.3 10.5 85.6 98.7 52.5 79.2 A B C D I H G E F 32.8 12.1 8.7 21.3 41.1 10.5 79.2 (a) 居民区示意图 (b) 铺设煤气管道设计图 North China Electric Power University
ch china Electric power University 例如:图书馆的书目检索问题 登录号 书名 作者 分类号 172832 离散数学 樊映川 S01 172833 理论力学 罗远祥 S01 172834 高等数学 华罗庚 S01 172835 线性代数 滦汝书 S02 书名 登录号 作者 登录号 类别登录号 高等数学172832 樊映川172832 17283A 172833 理论力学172833. 华罗庚172834 172832 线性代数172835 滦汝书172835 172834
例如：图书馆的书目检索问题 登录号 书名 作者 分类号 … … … … … … 172832 离散数学 樊映川 S01 … 172833 理论力学 罗远祥 S01 … 172834 高等数学 华罗庚 S01 … 172835 线性代数 滦汝书 S02 … … … … … … 书名 登录号 … … 高等数学 172832 、 172834… 理论力学 172833… 线性代数 172835… … … 作者 登录号 … … 樊映川 172832… 华罗庚 172834… 滦汝书 172835… … … 类别 登录号 … … L 172833… S 172832 、 172834… … … North China Electric Power University
North China Electric Power University ★基本念 1数据:所有能输入到计算机中并为计算机程序 处理的对象的集合。 2数据元素:数据的基本单位,在程序中作为 个整体加以考虑和处理。 3.数据项:数据处理的最小单位 (学生情况) 出生 980604刘哗女 日期 学号 姓名性别 801018 年月日 组合项原子项
★ 基本概念 1. 数据：所有能输入到计算机中并为计算机程序 处理的对象的集合。 2.数据元素：数据的基本单位，在程序中作为一 个整体加以考虑和处理。 3.数据项：数据处理的最小单位。 980604 刘晔 女 80 10 18 学号 姓名 性别 年 月 日 组合项 原子项 出生 日期 （学生情况） North China Electric Power University
North China Electric Power University 4数据对象:性质相同的数据元素的集合。 5数据的逻辑结构:对数据元素之间逻辑关系的 描述。它可以用一个数据元素的集合和定义在 这个集合上的若干关系来表示。 Data Structure=(D, S) D:数据元素的集合;S:D上关系的集合 1)集合:集合中任何两个结点之间都 没有逻辑关系,组织形式松散。 2)线性结构:元素之间存在着一对一 的关系。依次排列形成一条“锁链
4.数据对象：性质相同的数据元素的集合。 5.数据的逻辑结构：对数据元素之间逻辑关系的 描述。它可以用一个数据元素的集合和定义在 这个集合上的若干关系来表示。 Data Structure=(D,S) D:数据元素的集合; S:D上关系的集合 1）集合：集合中任何两个结点之间都 没有逻辑关系，组织形式松散。 2）线性结构：元素之间存在着一对一 的关系。依次排列形成一条“锁链” 。 North China Electric Power University
North China Electric Power University 3)树形结构:数据元素之间存在着一对 多的关系,具有分支、层次特性 4)图状结构:数据元素之间存在多对多 的关系,元素之间互相缠绕,具有分支 层次特性 6数据的存储结构:数据在计算机中的表示,包 括数据元素的表示和关系的表示。 1)顺序存储方式(向量存储)2)链式存储方式 3)索引存储方式 4)散列存储方式
3）树形结构：数据元素之间存在着一对 多的关系，具有分支、层次特性。 4）图状结构：数据元素之间存在多对多 的关系，元素之间互相缠绕，具有分支、 层次特性。 6.数据的存储结构：数据在计算机中的表示，包 括数据元素的表示和关系的表示。 1）顺序存储方式（向量存储） 2）链式存储方式 3）索引存储方式 4）散列存储方式 North China Electric Power University
North China Electric Power University 7数据类型:一个值的集合和定义在这个值上的 组操作。 8抽象数据类型:一个数学模型和定义在这个数 学模型的一组操作。 数据抽象:用ADT描述程序处理的实体时,强调的是其本 特性 质的特征,其完成的功能以及和外部的接口。 数据封装:将实体的外部特性和其内部实现分离,并对外 部用户隐藏其内部实现细节。 ADT抽象数据类型名{ 数据对象: 数据关系: 基本操作: }ADT抽象数据类型名
7.数据类型：一个值的集合和定义在这个值上的 一组操作。 8.抽象数据类型：一个数学模型和定义在这个数 学模型的一组操作。 特性 数据抽象：用ADT描述程序处理的实体时，强调的是其本 质的特征，其完成的功能以及和外部的接口。 数据封装：将实体的外部特性和其内部实现分离，并对外 部用户隐藏其内部实现细节。 ADT 抽象数据类型名{ 数据对象： 数据关系： 基本操作： } ADT 抽象数据类型名 North China Electric Power University