数据结构PPT全套教学课件（完整版）.pptx

汪赫瑜

电子与信息工程学院计算机系;

之间的一门核心课程。

Data_Structure=(D,R)

关系

数学

软件硬件;

学时数：80

教材：严蔚敏等，数据结构(C语言版),清华大学出版社，

1997年4月第1版(配题集)

参考书：

[1]殷人昆等，数据结构(用面向对象方法与C++描述),清华大学出版社，1999年7月(2002年配习题集)

[2]资讯教育小组，数据结构C语言版，中国铁道出版社。;

第1章：绪论

1.1什么是数据结构

1.2学习数据结构的意义

1.3数据结构涵盖的主要内容1.4什么是抽象数据类型

1.5算法效率的度量;

2014-4-305;

数据结构产生的背景

-例2人机对奕问题;

例3多叉路口交通灯管理问题

图;

1.1什么是数据结构

是相互之间存在一种或多种特定关系的数据元素的集合，表示为：

Data_Structure=(D,R)

(数值或非数值)——元素有限集关系有限集

——是指同一数据元素类型中各元素之间存在的关系。;

术语简介：数据、数据元素和数据项

数据(data)所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息)。

数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等)。

数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小

标识单位(又称字段、域、属性等)。

三者之间的关系：数据数据元素数据项

例：班级通讯录个人记录姓名、年龄....;

学号;

1.2学习数据结构的意义

计算机内的数值运算依靠方程式，而非数值运算(如表、树、图等)则要依靠数据结构。

数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。;

1.3数据结构涵盖的内容

线性结构(线性表、栈、队、串、数组)

逻辑结构非线性结构树结构

顺序结构

数据结构物理(存储)结构

插入运算

删除运算

数据运算修改运算

查找运算

排序运算;

解释1:什么叫数据的逻辑结构?

答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。;

(1)S=(D,R)

D={a,b,c,d,e,f}

R={(a,e),(b,c),(c,a),(e,f),(f,d)}

解：上述表达式可用图形表示为：

b—→C—→a—→e—→f—→d;

d?d?

d?d3;

法1:地址

0300;

解释3:什么是数据的运算?

答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。;

1.4什么是抽象数据类型

抽象数据类型和伪码是学习数据结构的工具讨论：

1.4.1数据类型与抽象数据类型的区别?

1.4.2抽象数据类型如何定义?

1.4.3抽象数据类型如何表示和实现?;

数据类型：是一个值的集合和定义在该值上的

一组操作的总称。

抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务(或称操作);;

例：给出自然数(NaturalNumber)的抽象数据类型定义。—

ADTNatural_Numberis

objects:一个整数的有序子集合，它开始于0,结束于机器能表示的最大整数(MAX/NT)

functions:对于所有的x,y∈Natural_Number;TRUE,

FALSE∈Boolean;+,一，〈,二=,=等都是可用的

服务。;

抽象数据类型可以通过固有的数据类型(如整型、实

型、字符型等)来表示和实现。

注1:它有些类似C语言中的结构(struct)类型，但增加了相关的服务。

注2:教材中用类C语言(介于伪码和C语言之间)作为描述工具。其描述语法汇总在教材P10-11上。;

教材中例1-6和例1-7分别给出了抽象数据类型

“三元组”的定义、表示和实现，请自己先试读一遍。

当课程内容学习到50%以后，你再回