本章主要介绍以下内容

《数据结构》教案 吴文国

第1章 绪论

本章主要介绍以下内容

数据结构研究的主要内容1 数据结构中涉及的基本概念2

算法的概念、描述方法以及评价标准3

课时分配：2，两个学时，3两个学时 重点、难点：ADT、算法的概念、描述方法以及评价标准

1.1 数据结构研究的主要内容

当今计算机应用的特点：

所处理的数据量大且具有一定的关系； 对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。 例1--学籍档案管理

假设一个学籍档案管理系统应包含如下表所示的学生信息。学生基本情况

学号 20080101 20080102 20080103 20080104 …… 姓名 吴跃 王琳 张小微 李正直 …… 性别 女 男 男 女 …… 出生年月 1980.1.12 1981.5.10 1979.12.8 1979.4.25 …… …… …… …… …… …… …… 特点：

每个学生的信息占据一行，所有学生的信息按学号顺序排列；每个学生的信息按学号的大小存在着一种前后关系，即线性结构关系；对它的操作通常是插入某个学生、删除某个学生的信息，或修改某个学生的信息。

例2 计算机学院的制订授课计划 例3

输出n个对象的全排列可以使用下图所示的形式描述。

物理与电子信息学院

《数据结构》教案 吴文国

结论

计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。

1.2 基本概念和术语

1． 数据

是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。 2． 数据元素

是数据集合中的一个实体，是计算机程序中加工处理的基本单位。 数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。 3． 数据结构

物理与电子信息学院

《数据结构》教案 吴文国

简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。===》（集合关系） 4．逻辑结构

数据结构中所说的\关系\实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。 存储结构（物理结构）==》（散列、索引） 是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。

常见的存储结构

顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；

链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。

1.3 算法

1．算法的概念

算法是解决某个特定问题的一种方法或一个有限过程。 计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。

设计算法的基本过程

通过对问题进行详细地分析，抽象出相应的数学模型；确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法； 选用某种语言将算法转换成程序；调试并运行这些程序。

2． 算法应该具有下列五个特性

（1）有穷性：一个算法必须在执行有穷步之后结束。

（2）确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。 （3）动态性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。 （4）输入：一个算法应该有零个或多个输入。

（5）输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。 例1

问题：按从小到大的顺序重新排列x，y，z三个数值的内容。 算法：

（1）输入x，y，z三个数值；

（2）从三个数值中挑选出最小者并换到x中；

（3）从y，z中挑选出较小者并换到y中；（4）输出排序后的结果。 3． 算法的描述

选择算法描述语言的准则

（1）该语言应该具有描述数据结构和算法的基本功能； （2）该语言应该尽可能地简捷，以便于掌握、理解；

（3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。

\类C\描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。 (略介绍)

（1）预定义常量及类型(略介绍)

物理与电子信息学院

《数据结构》教案 吴文国

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1

数据元素被约定为Elemtype 类型，用户需要根据具体情况，自行定义该数据类型。 （2）算法描述为以下的函数形式： 函数类型 函数名（函数参数表） {

语句序列； }

为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。 （3）在算法描述中可以使用的赋值语句形式有： 简单赋值 变量名 = 表达式；

串联赋值 变量名1 = 变量名2 = ... = 变量名n = 表达式；

成组赋值 （变量名1，...，变量名n）=（表达式1，...，表达式n）； 结构赋值 结构名1 = 结构名2；

结构名 =（值1，值2，...，值n）；

条件赋值 变量名 = 条件表达式 ? 表达式1：表达式2； 交换赋值 swap(变量名1,变量名2)；

（4）在算法描述中可以使用的选择结构语句形式有： 条件语句1 if （表达式） 语句； 条件语句2 if （表达式） 语句； else 语句；

开关语句1 switch （表达式） { case 值1：语句序列1；break； case 值2：语句序列2；break； ...

case 值n：语句序列n；break； default：语句序列n+1； }

开关语句2 switch {

case 条件1：语句序列1；break； case 条件2：语句序列2；break； ...

case 条件n：语句序列n；break； default：语句序列n+1； }

（5）在算法描述中可以使用的循环结构语句形式有：

for循环语句 for （表达式1；循环条件表达式；表达式2） 语句； while循环语句 while （循环条件表达式） 语句； do-while循环语句 do {

物理与电子信息学院