南京大学：《数据结构 Data Structures》课程教学资源（PPT课件讲稿）第一章 绪论

第一章绪论 §1.1数据结构的概念 早期：数值计算 运算对象是简单的整型、实型或布尔类 型数据 中后期：非数值计算 处理对象是类型复杂的数据，数据元素 之间的相互关系一般无法用数学方程式 加以描述

1 第一章 绪论 §1.1 数据结构的概念 早期：数值计算 —— 运算对象是简单的整型、实型或布尔类 型数据 中后期：非数值计算 —— 处理对象是类型复杂的数据，数据元素 之间的相互关系一般无法用数学方程式 加以描述

例1：“学生”表格 学号姓名 性别 籍贯 出生年月 98131 刘激扬 男 北 京 1979.12 2 98164 衣春生 男 青 岛 1979.07 3 98165 卢声凯 男 天 津 1981.02 4 98182 袁秋慧 女 广 州 1980.10 5 98203 林德康 男 上 海 1980.05 6 98224 洪伟 男 太 原 1981.01 7 98236 熊南燕 女 苏 州 1980.03 8 98297 宫力 男 北京 1981.01 9 98310 蔡晓莉 女 昆 明 1981.02 10 98318 陈健 男杭州 1979.12 2

学 号 姓 名 性别 籍 贯 出生年月 1 98131 刘激扬 男 北 京 1979.12 2 98164 衣春生 男 青 岛 1979.07 3 98165 卢声凯 男 天 津 1981.02 4 98182 袁秋慧 女 广 州 1980.10 5 98203 林德康 男 上 海 1980.05 6 98224 洪 伟 男 太 原 1981.01 7 98236 熊南燕 女 苏 州 1980.03 8 98297 宫 力 男 北 京 1981.01 9 98310 蔡晓莉 女 昆 明 1981.02 10 98318 陈 健 男 杭 州 1979.12 2 例1：“学生”表格

例2：八皇后问题用四皇后描述) ● ● ●●● g●● ● ● ● ● 四皇后问题的状态树 3

例2：八皇后问题(用四皇后描述) • • • • • • • • • • • • ... ... ... ... 四皇后问题的状态树 3

例3：教学计划编排问题 课程编号 课程名称 先修课程 C1 计算机导论 无 数据结构 C11 CA 汇编语言 C1 C程序设计语言 计算机图形学 C2 接口技术 数据库原理 8 编译原理 (a)摆算统型的课程设置 4

课程编号 课程名称 先修课程 C1 计算机导论 无 C2 数据结构 C1，C4 C3 汇编语言 C1 C4 C程序设计语言 C1 C5 计算机图形学 C2，C3， C4 C6 接口技术 C3 C7 数据库原理 C2，C9 C8 编译原理 C4 C9 操作系统 C2 例3：教学计划编排问题 （a）计算机专业的课程设置 4

S Co C Cs S 子 S (b)表示课程之间优先关系的有向图 5

C1 C2 C3 C6 C4 C5 C9 C8 C7 （b）表示课程之间优先关系的有向图 5

例4：城市的煤气管道问题 18.2 32.8 12.1 32.8 12. 8.7 44.6 B 5.9 79.2 5.9 79.2 56.4 52.5 41 10 21.3/ 21.3 67.3 85.6 98.7 (a)结点间管道的代价 (b)最经济的管道铺设 6

例4：城市的煤气管道问题 （a）结点间管道的代价 （b）最经济的管道铺设 6

>描述这类非数值计算问题的数学模型不再 是数学方程，而是诸如表、树、图之类的数 据结构。 >数据结构是一门研究（非数值计算的）程 序设计问题中所出现的计算机操作对象以及 它们之间的关系和操作的学科。 7

➢ 描述这类非数值计算问题的数学模型不再 是数学方程，而是诸如表、树、图之类的数 据结构。 ➢ 数据结构是一门研究（非数值计算的）程 序设计问题中所出现的计算机操作对象以及 它们之间的关系和操作的学科。 7

课程学习前掌握的基本概念： 数据 。 。 数据元素（数据成员） 数据对象 8

◼课程学习前掌握的基本概念： ⚫ 数据 ⚫ 数据元素（数据成员） ⚫ 数据对象 8

数据：数据是信息的载体，是描述客观 事物的数、字符、以及所有能输入到计 算机中，被计算机程序识别和处理的符 号（数值、字符等）的集合。 数据元素（数据成员)：是数据的基 本单位。在不同的条件下，数据元素又 可称为元素、结点、顶点、记录等。 9

• 数据：数据是信息的载体，是描述客观 事物的数、字符、以及所有能输入到计 算机中，被计算机程序识别和处理的符 号（数值、字符等）的集合。 • 数据元素（数据成员）: 是数据的基 本单位。在不同的条件下，数据元素又 可称为元素、结点、顶点、记录等。 9

数据对象：具有相同性质的数据元素( 数据成员)的集合。 整数数据对象W={0,±1，±2，.} 学生数据对象 10

⚫ 数据对象：具有相同性质的数据元素（ 数据成员）的集合。 - 整数数据对象 N = { 0, 1, 2, … } - 学生数据对象 10