数据结构(严蔚敏)第1章

2007年9月5日，星期三，第一章导论，2007年9月5日，星期三，第一页，课前思考，学生已经看过这本书算法+数据结构=程序设计，这正好说明数据结构的本质是讨论程序设计的方法。通过本课程的学习，学生将掌握非数值计算编程的基本方法和技巧。在2007年9月5日星期三的第页，学习目标，熟悉名词和术语的含义，掌握基本概念。理解算法的五个元素的确切含义。掌握计算句子频率和估计算法时间复杂度的方法。本章讨论一些基本概念，所以没有困难。关键在于理解与数据结构相关的各种名词和术语的含义，以及句子频率、时间复杂度和空间复杂度的估计。知识点)，数据，数据元素，数据结构，数据类型，抽象数据类型，算法及其设计原则，时间复杂性和空间复杂性。2007年9月5日，星期三，第1页，学习指南。熟悉名词和术语的含义，掌握基本概念，尤其是数据的逻辑结构和存储结构之间的关系。区分哪些是逻辑结构的属性，哪些是存储结构的属性。2.理解抽象数据类型的定义、表示和实现。3.熟悉类C语言的编写标准，特别注意值调用和引用调用的区别，输入输出方法和错误处理方法。4.理解算法五要素的确切含义和算法的正确性。5.掌握计算句子频率和估计算法时间复杂度的方法。2007年9月5日，星期三。页面，1.1数据结构讨论的范围，1.2基本概念，1.3算法和算法度量，2007年9月5日，星期三。第1.1页，数据结构讨论的范围，尼古拉斯沃斯：算法数据结构=程序，编程：算术：数据结构：为计算机处理问题编译指令集，处理问题的策略，问题的数学模型，2007年9月5日，星期三。页面，结构静态分析和计算，编程问题，如：数值计算，-线性代数方程，-环流模型方程(球坐标系)，全球天气预报，星期三，2007年9月5日。第页，非数值计算的编程问题，示例：在一组(N个)整数中寻找最大值，算术：型号：基本操作是“比较两个数字的大小”，取决于整数值的范围，2007年9月5日星期三。页面，示例2:计算机游戏，算法：型号：下棋的规则和策略，棋盘及其布局，2007年9月5日，星期三，第3页，示例3:足球协会的数据库管理，算法：型号：要管理的项目？如何管理？用户界面？各种表格，2007年9月5日，星期三，第页，简而言之：数据结构是一门讨论“描述真实世界实体的数学模型(非数值计算)和对它们的操作如何在计算机中表示和实现”的学科。2007年9月5日，星期三，第1.2页，基本概念，1。数据和数据结构，2。数据类型，3。抽象数据类型，3。2007年9月5日，星期三，第1页。数据和数据结构，可以输入计算机并由计算机处理的所有符号集。数据：是由计算机操作的对象的总称。是由计算机处理的信息的特定符号表示。2007年9月5日星期三。页面是数据(集合)中的“个体”，数据元素：是数据结构中讨论的基本单元，数据对象是具有相同属性的数据元素集合，是数据的子集，2007年9月5日星期三，页面，数据项：是数据结构中讨论的最小单位，数据元素可以是数据项的集合，例如：描述运动员的数据元素可以是，它被称为组合，星期三，2007年9月5日。页面，数据结构：一组结构化数据元素，假设三个4位十进制数代表一个12位十进制数。，3214，6587，9345-a1 (3214)，a2 (6587)，a3 (9345)，则存在“顺序”关系a1，a2，A2，a3，3214，6587，9345a1a2a3，6587，3214，9345 A2A1A3，8800，例如，星期三，2007年9月5日。页面，另一个示例，具有两行和三列的二维数组a1，a2，a3，a4，a5，a6中的六个元素之间有两个关系：即行顺序关系：row=，col=，a1a3a5a2a4a6，a1a2a3a4a5a6，星期三，2007年9月5日，页面，另一个例子，在一维数组a1，a2，a3，a4，a5，a6中，数据元素之间存在以下顺序关系：| I=1，2，3，4，5，或者数据结构是一组彼此具有某种关系的数据元素。可以看出，不同的“关系”形成不同的“结构”。2007年9月5日，星期三，这一页。数据结构包括以下几个方面：数据元素之间的逻辑关系，即逻辑结构数据元素的存储方式及其在计算机内存中的关系，即数据存储结构对数据的操作，即数据的操作，2007年9月5日星期三，页面。数据的逻辑结构可以归纳为以下四类：线性结构，树形结构，图形结构，集合结构，星期三，2007年9月5日。页面，数据结构的形式定义为：数据结构是一个二进制组，数据结构=(D，S)，其中3336d是一组有限的数据元素，S是一组有限的关系。页面，数据的存储结构(物理结构)，内存中逻辑结构的映像，“数据元素”的映像？“关系”的反映？的映射方法。页面和数据元素如下：(321) 10=(501) 8=(101000001) 2，2007年9月5日星期三的映射方法。页面和数据元素如下：(x和y的方法)、顺序映射(顺序存储方法)和后续关系由相对存储位置表示。例如，表示y的存储位置和x的存储位置之间的差异，常数c，c是一个隐式值。整个存储结构只包含数据元素本身的信息。页面、链图(链存储方法)。需要x的附加信息来指示y的存储位置，yx、不需要逻辑上相邻的节点在物理上相邻，并且节点之间的逻辑关系由附加指针字段来表示。2007年9月5日，星期三。页，索引存储方法在创建附加索引表时存储节点信息。索引表中的每一项都称为索引项。索引项的一般形式是关键字和地址。散列(或散列)存储方法通过散列函数根据节点的关键字直接计算值，并将该值作为节点的存储地址。在2007年9月5日星期三，可以在不同的编程环境中以不同的方式描述页、存储结构。当用高级编程语言编程时，通常可以用高级编程语言提供的数据类型来描述。2007年9月5日星期三。当用具有顺序关系的三个整数表示一个长整数时，页面(如：)可以使用C语言中提供的整数数组类型。TypeDefinetLong _ int3，长整数：2007年9月5日，星期三。第2页，数据类型。在用高级编程语言编写的程序中，必须指定程序中每个变量、常数或表达式所属的数据类型。例如，在C语言中提供的基本数据类型是：整数整型、浮点浮点型、字符型、逻辑布尔型(C语言)、双精度型、实数型(C语言)，2007年9月5日星期三。数据类型是值的集合和在该集合上定义的一组操作。不同类型的变量有不同的值范围和不同的运算。在2007年9月5日星期三，第3页，抽象数据类型(ADT)指的是数学模型和在数学模型上定义的一组运算。，2007年9月5日，星期三。例如，第页，抽象数据类型复数的定义：数据对象：D=E1，E2 | E1，E2 Realset数据关系：R1=| E1是复数的实部|e2是复数的虚部，ADT COMPX ，星期三，2007年9月5日，页面，基本操作：赋值复杂(/选