数据结构基础.pptVIP

数据结构电子教案

第1章概述

数据结构第1章概述1

课程简介

本课程是一门专业技术基础课程，课程分析、

研究计算机加工数据的特征、数据的逻辑结构、

数据的存储结构、数据涉及的算法、以及不同

特征数据应用情况。

数据结构第1章概述2

内容提要

Ø“数据结构”是一门随着计算机科学的发展而逐

渐形成的新兴学科。随着计算机技术的发展，计

算机的应用领域从最初的科学计算发展到人类社

会的各个领域，计算机处理的对象也由纯粹的数

值发展到字符、表格、图像和声音等各种具有一

定结构的数据，这就给程序设计带来一些新的问

题。与飞速发展的计算机硬件相比，计算机软件

的发展相对缓慢。因此，研究数据结构对设计出

一个高性能的算法和高性能软件是至关重要的。

数据结构第1章概述3

内容提要

Ø本章将介绍数据结构的基本概念：数据、数据

元素、数据结构、数据的逻辑结构和存储结构、

数据运算、算法和算法分析等，了解这些概念

有助于对以后章节加深理解。

数据结构第1章概述4

第1章概论

1.1概述

1.2数据结构的基本概念

1.2.1数据结构的基本术语

1.2.2数据的逻辑结构

1.2.3数据的存储结构

1.3算法性能分析与度量

1.3.1算法和算法的描述方法

1.3.2算法的特性

1.3.3算法设计的要求

1.3.4算法时间复杂度的度量

1.3.5算法存储空间的需求

数据结构第1章概述5

1.1概述

•什么是数据结构

•一般来说，用计算机解决一个实际问题时，

大致需要以下几个步骤：首先从具体问题抽

象出一个适当的数学模型，然后设计一个解

此数学模型的算法，最后编出程序进行调试

直至得到最终的解答。寻求数学模型的实质

是分析问题，从中提取操作的对象，并找出

这些操作对象之间的关系，然后用数学的语

言加以描述。

数据结构第1章概述6

•然而，随着计算机应用领域的不断扩大，计算

机处理的更多的是非数值计算问题。

•例如，图书资料查询、电话号码的自动管理、

交通道路规划、博弈游戏等问题。

•它们的数学模型一般无法用数学方程式加以描

述，因此，解决此类问题的关键已不再是分析

数学和计算方法，而是要建立有效的数据结构

来进行描述，分析问题中所用到的数据是如何

组织的，研究数据之间的关系如何，进而为解

决这些问题设计出合适的数据结构。

•为了增加对数据结构的感性认识，下面举例说

明数据结构的概念。

数据结构第1章概述7

2、实例

Ø酒店管理（房间的使用，先退房先启用）

Ø图书馆书目检索（各级编码建索引）

Ø电话号码检索【例1.1】

Ø字典查找【例1.2】

数据结构第1章概述8

【例1.1】电话号码自动查询问题。

Ø电话号码查询的最主要的工作是，当给出某个

单位名称或某个人的姓名时，能在电话号码表中

迅速找到其电话号码，若找不到，则给出该单位

或个人的电话号码不存在的信息。此外，当有新

用户要加入、旧用户要改号或撤销时，要对电话

号码表进行相应的修改。

Ø那么，如何组织电话号码表，实现上述查询、插

入、删除和修改等操作呢？

数据结构第1章概述9

Ø假设电话号码表的组成见表1.1。表中各用户的

电话号码是随机罗列出来的。若要查找某人或

某单位的电话号码，就必须从表的开始依次往

后顺序查找。若该用户确实注册，就会找到该

用户的电话号码。但是，采用这种方式进行查

找，效率是很低的。

Ø为了提高查找效率，可以重新组织电话号码表，

将单位和私人电话分开登记。单位电话按行业

分