01数据结构【荐】.ppt

数据结构与算法 计算机科学与技术系 王昆仑、李红 2007年2月28日 课程教学要求： 课程考核方法： 第1章 数据结构和算法 ? 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具－C语言 1.4 算法和算法评价 1.5 算法性能分析 1.1 数据与数据类型 ? 1.1.1 数据和数据元素 1.1.2 数据类型 1.1.3 数据对象 数据 在计算机科学中，数据是指描述客观事物的数值、字符、相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称。 例如： 数值数据、字符、声音、图像、图形等 数据元素 我们将数据中具有独立意义的个体称为数据元素。 数据元素是数据的基本单位，在程序设计时通常作为一个整体进行考虑和处理。 有时，一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 为实现图书馆书目的自动检索，将与图书相关的数据做成如图所示的表，试分析表中的数据元素、数据项。 1.1 数据与数据结构 1.1.1 数据和数据元素 ?1.1.2 数据类型 1.1.3 数据对象 ? 数据类型概念和定义 是一个同类值的集合和定义在这个值集上的一组操作的总称。 当我们在高级程序语言中定义每一种数据类型，在程序编译时计算机语言编译系统就知道了以下信息： (1) 一组性质相同的值集合， (2) 一个预定的存储体系， (3) 定义在这个值集合上的一组操作。 数据类型可分为两类： ? 简单数据类型 简单类型的数据是不可分解的整体，如整数、实数、字符、指针、枚举量等。 请解释整型数据类型。 答：整型数据类型通常有short(2字节)、int(2字节)、long(4字节)等形式，其值集为某个区间上的整数。 如果整型是两个字节表示的，其值集范围是：-32768～32767，定义在整型数据上的操作为：单目正(+)操作、负(-)操作，双目加(+)操作、减(-)操作、乘(*)操作、除(/)操作和取模(MOD)操作等算术运算，双目关系(，，=，=，等)操作运算以及赋值(=)操作等。 ? 结构数据类型 结构类型由简单数据类型按照一定的规则构造而成。 结构数据类型中还可包含结构数据类型，所以结构数据类型的数据可以分解成若干个简单数据类型的数据或子结构数据类型。也称作复合数据类型。 数组数据类型分析。 答：数组是结构数据类型，例如： char name[20],一维数组由若干个同种简单数据类型顺序排列而成，数组的每个值的数据类型相同； int a[10][10]，二维数组看成是一个以“一行”为一个元素的一维数组；而“一行”中简单元素有序。 float b[5][10][15]等。三维数组看成是一个以“一个面(行*列)”为一个元素的一维数组；“面”为二维数组。 定义表1.1表示的数据类型。 解：表1.1中每一个数据元素的数据项是由长整型的书号、字符型的书名、作者名以及实型的价格，我们可以采用如下的C语言语句来定义一个称为EmployeeType的、新的(用户自定义)数据类型： typedef struct{ long mun； char name[10]，book[100]； float price； }EmployeeType； 然后，将这个名为EmployeeType的新数据类型当作一个基本数据类型来使用。我们可以使用该数据类型定义一个变量x： EmployeeType x； 它表达的是“变量x将在后面的程序中用到，它指称一个大约118个字节的主存储器区域，用于以二进制依次存放四个值：一个整数、两个字符串和一个实数”。 1.1 数据与数据结构 1.1.1 数据和数据元素 1.1.2 数据类型 ? 1.1.3 数据对象 ? 数据对象 数据对象是数据类型的实例，简称对象。 数据对象举例。 答：例如：25，是整型数据对象。 ‘A’，是字符数据对象。 char *p ，定义p为一个字符指针对象。 int a[10]，定义a为一个含有10个整型数的整型数组对象。 Rectang