首页计算机计算机基础程序设计基础与数据结构 02 第一章 数据结构绪论.pptx

02 第一章 数据结构绪论.pptx

页数:17页文件大小:119.2 KB来源: 程序设计基础与数据结构ppt课件

本课件为课程第一章绪论,从沃思提出的“程序=数据结构+算法”公式切入,逐步展开数据类型、数据元素、数据对象与数据结构的定义,并用工资表、组织机构图和城市航线图分别示例线性、树型与图型三类基本数据结构,最后说明算法的定义、五大特性与本课程采用的类C描述语言。

第一章绪论章节目录页,列出程序与数据结构算法、基本概念、算法描述与小结四节标题
程序与数据结构算法关系页,说明计算机的数据处理本质与沃思公式,并给出本课程的两大内容主线
数据结构基本概念概览页,列出数据类型、数据元素、数据对象、数据结构与三类基本结构
查看本课件的文字版(共 17 页,供检索与复制)

第1页:第一章 绪论

第一章 绪论

  • 1.1 程序 = 数据结构 + 算法
  • 1.2 数据结构的基本概念
  • 1.3 算法的概念与描述
  • 1.4 小结

第2页:程序=数据结构+算法

1.1 程序 = 数据结构 + 算法

  • 计算机是帮助人们对各种数据进行处理的机器。
  • 数据结构是一门对计算机处理的数据进行表示、组织及操作进行研究的学科。
  • 程序 = 数据结构 + 算法(N.Wirth)
  • 本课程内容:基本数据结构、基本算法

第3页:数据结构基本概念概览

1.2 数据结构的基本概念

  • 数据与结构:数据的类型、数据元素、数据对象、数据结构
  • 基本数据结构类型:线性数据结构、树型数据结构、图型数据结构

第4页:数据的类型

(1)数据的类型

数据类型
指的是一个值的集合以及定义在该集合上的操作的集合。
  • 分为固有数据类型和用户自定义数据类型两种。

第5页:数据元素

(2)数据元素

  • 是用于描述数据的基本单位。
  • 可由数据项组成。
  • 数据项是数据表示中不可分割的最小标识单位。

第6页:数据对象

(3)数据对象

  • 是具有相同性质的数据元素所组成的集合。
  • 一般情况下,数据对象中所包含的数据元素之间具有一定的组织形式和结构关系。

第7页:数据结构

(4)数据结构

  • 是对数据元素及其相互关系的描述。
  • 包含两方面内容:一是对数据元素的有限集合即数据对象的描述,二是对数据对象中数据元素的关系的描述。
  • 有三种基本类型:线性数据结构、树型数据结构、图型数据结构。

第8页:线性数据结构示例

线性数据结构示例(表1-1):职工工资表按工号顺序排列,每行是一条记录。

表1-1 线性数据结构示例(职工工资表)
工号姓名工资奖金合计
001张三500.00100.00600.00
002李四600.00100.00700.00
003王五550.0080.00630.00
004赵六700.00120.00820.00

第9页:树型数据结构示例

树型数据结构示例(图1-1-1):总经理下分三个部门经理,每位部门经理各带一名职员,呈现一对多的层次结构。

  • 根结点:总经理
  • 分枝结点:部门经理1、部门经理2、部门经理3
  • 叶子结点:职员1、职员2、职员3

第10页:图型数据结构示例

图型数据结构示例(图1-1-2):城市间的航线图,北京、武汉、杭州、上海、重庆、香港、济南之间彼此通航,顶点之间呈现多对多的网状关系。

第11页:算法的概念与描述

1.3 算法的概念与描述

  • 什么是算法?
  • 算法的特点
  • 算法描述语言
  • 本课程采用的算法描述语言

第12页:什么是算法

什么是算法?

  • 算法描述的是计算机解决问题的具体步骤的序列;
  • 这个序列必须是有限的。

第13页:算法的特点

算法的特点

确定性
算法的每一个步骤都必须有确定的含义,不能有二义性和模糊性,对同样的初始状态应得出相同的结果。
可行性
算法中的每一步都应在有限的执行时间内完成,否则该算法不可能得到实现。
有穷性
算法应在有限的执行步骤里完成。
输入
每个算法都应具有零个或多个输入以描述问题的初始状态。
输出
每个算法都应具有至少一个以上的输出作为它的结果。

第14页:算法描述语言的种类

算法描述语言

  • 自然语言
  • 程序语言:C、BASIC、PASCAL 等
  • 形式化语言:例如 ADT

第15页:本课程采用的算法描述语言

本课程采用的算法描述语言:结合自然语言的一种类 C 语言的描述方法。

  • 便于交流和理解;
  • 突出重点,不拘泥于局部的细节;
  • 条理性更好,便于表达;
  • 准确,便于程序实现和算法性能分析。

第16页:类C语言的基本语言要素

本课程采用的算法描述语言——基本语言要素:

  • 数据类型说明
  • 变量和符号常量
  • 数据运算
  • 赋值语句
  • 控制语句:条件、循环
  • 函数的定义、声明与调用
  • 输入、输出
  • 结束语句
  • 注释

第17页:第一章小结

1.4 小结

  • 数据结构及算法中的基本概念介绍
  • 用示例的方式对要介绍的数据结构类型进行了说明
  • 算法的描述采用的是一种结合了自然语言和 C 语言特点的类 C 描述语言
顶部目录