数据结构实用教程(C语言版)598.pptxVIP

数据结构实用教程数据结构实用教程;同学们好!同学们好!;课程安排;第1章绪论;简单地说，数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作等的学科。;例1.1学生信息表

当你想找某一学生的信息时，需要查找学生信息表。表1.1所示。;表1.1所示是一种数据结构，表中的每一行是一个记录(计算机操作的对象)，记录由学号、姓名、班级、性别和出生年月等数据项组成。在这种数据结构中，计算机的主要操作是按照某个特定要求(如给定学号)对信息表进行查询的，计算机处理的对象间存在一种线性关系，称为线性数据结构。;学生信息表程序设计;例2计算机和人对弈问题;;因此，若将从对奕开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的“树”。“树根”是对奕开始之前的棋盘格局，而所有的“叶子”就是可能出现的结局，对奕的过程就是从树根沿树叉到某个叶子的过程。“树”是某些非数值计算问题的数学模型，是一种数据结构。;人机对奕问题程序设计;例3制订教学计划;D;课程的先后关系用图1.2所示的形式描述;综合上述3个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。;从数学模型上分：

数值问题（数学方程）

非数值问题

非数值计算中数据元素之间的相互关系一般无法用数学方程加以描述;数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。;1.2基本概念和术语;1、数据:

是对客观事物的符号表示，在计算机科学中是指能被输入到计算机中且能被计算机处理的符号的集合。

;;4、数据结构;线性结构：数据元素之间存在着一对一的关系;数据结构的形式定义为：

数据结构是一个二元组

Data_Structures=(D,S)

其中:D是数据元素的有限集，S是D上关系的有限集。

这种二元组只反映出数据的逻辑结构。

;下面举两个简单例子说明。

例1.4表1.1的数据结构。

StudentInfo?=?(D，S)

其中，D是光126班级全体学生集合D?=?{Stu1，Stu2，…，Stun?|?n为班级人数}。S是定义在集合D上的一种关系S?=?{Stui，Stui+1?|?i=1，2，…，n}，有序偶Stui，Stui+1表示学号相邻。

例1.5表1.2的数据结构。

TeachPlan=(D，S)

其中，D是计算机专业必修课程集合D?=?{C1，C2，…，C12}。S是定义在集合D上的一种关系S?=?{C1，C4，C1，C2，C1，C3，C1，C12，…|?共16对}，有序偶表示课程的先导关系，例如C1，C4表示“程序设计基础”是“汇编语言”的先导课程。;

上述数据结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。

讨论数据结构的目的是为了在计算机中实现对它的操作，因此还需研究它如何在计算机中表示。;逻辑结构是指各数据元素之间的逻辑关系。;元素n;1536;以内存地址来描述存储结构，实现很困难，借用高级程序语言中提供的“数据类型”来描述，“一维数组”类型描述顺序存储结构，“指针”来描述链式存储结构。

可把C语言看成是一个执行C指令和C数据类型的虚拟处理器，存储结构是数据结构在C虚拟处理器中的表示，称之为虚拟存储结构。

;5、抽象数据类型;

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

例：整数类型是一个ADT，其数据对象是指能容纳的整数，基本操作有加、减、乘、除和取模等。;本书以下格式定义抽象数据结构：

ADT抽象数据类型名{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉

}

;例1.6抽象数据类型矩形的定义。

一个矩形必须具备长度和宽度，因此，矩形的抽象数据类型的基本数据项应该是矩形的长(Length)和宽(Width)。另外，对矩形的基本操作应该包括：构造矩形长度、求矩形的周长、求矩形的面积。;

ADTRectangle{

数据对象：D={Length，Width|∈实数}

数据关系：R={Length,Width}

基本操作：

InitRectangle(Rectanglere