数据结构相关文档和PPT.ppt

数据结构 任课教师：邱 保 志 Email：iebzqiu@zzu.edu.cn 单位：郑州大学信息工程学院 为什么要学习数据结构？ 介于数学、计算机软件、硬件三者之间的核心课程 一般程序设计（尤指非数值计算的程序设计）的基础 设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。 如何利用计算机解决实际应用问题？ 需经过以下三步骤： 从具体问题中抽象出一个适当的数学模型。 设计一个解此数学模型的算法 编程调试，得到最终答案 图书馆的书目检索系统自动化问题 人机对弈问题 怎样学数据结构？ 本书的内容简介 1.2 基本概念和术语 数据：信息的载体，是描述客观事物的数、字符及所有能输入到计算机中被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据元素：数据的基本单位 一个数据元素可由若干个数据项组成。 数据项是数据不可分割的最小单位。 数据对象：数据的子集。具有相同性质的数据元素集合。 例如：整数对象 N = { 0, ?1, ?2, … } 数据结构（逻辑结构） 数据结构：相互间存在一种或多种特定关系的数据元素集合。 结构：数据元素相互之间的关系 特定关系： 数据的物理结构(存储结构) 数据结构在计算机中的表示： 数据元素的表示 数据元素之间关系的表示 顺序映象：借助元素在存储器的相对位置表示数据元素之间的逻辑关系。对应于顺序存储结构(sequential sets). 非顺序映象：利用指示元素存储地址的指针表示数据元素间的逻辑关系。对应于 链式存储结构(linked lists) 索引树(indexed trees) 散列表(hash tables) 数据逻辑结构和物理结构之间的关系 关系： 任意一个算法的设计取决于选定的逻辑结构 算法的实现依赖于采用的物理结构。 数据结构主要研究什么？ 解决问题时可能遇到的典型的逻辑结构 逻辑结构的存储映象（物理结构） 数据结构的相关操作及其实现（算法） 数据类型 抽象数据类型 抽象数据类型的定义格式(仅适用于本书) ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 基本操作的定义格式为 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 参数表有两种参数： 赋值参数：只为操作提供输入值； 引用参数：以打头， 除可提供输入值外，还将返回操作结果。 初始条件描述了操作执行前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。 抽象数据类型举例-矩阵 ADT Matrix{ 数据对象:D={ai,j|i=1,2,…,m;j=1,2,…,n;ai,j∈ElemSet} 数据关系:R={Row,Col} Row={ai,j,ai,j+1|1≤i≤m,1≤j≤n-1} Col={ai,j,ai+1,j|1≤i≤m-1,1≤j≤n} 基本操作： CreateMatrix(M) DestroyMatrix(M) PrintMatrix(M) AddMatrix(M,N,Q) SubMatrix(M,N,Q) MultMatrix(M,N,Q) TransposeMatrix(M,T) } ADT Matrix 1.3 类Ｃ语言的语法规则 1、预定义常量和类型： 2、数据结构的描述，数据元素类型的定义 3、基本操作的算法可以使用的函数表示 4、算法描述中可以使用的赋值语句形式 5、算法描述中可以使用的选择结构语句形式 6、算法描述中可以使用的循环结构语句形式 7、描述算法中可以使用的结束语句形式 8、算法描述中可以使用的输入输出语句形式 9、算法描述中可以使用的注释格式 10、算法描述中可以使用的扩展函数 11、算法描述中可以使用的逻辑运算的约定 类Ｃ语言的语法规则示例 例1 typedef int Status; void example_1( ) { Status a[10]; a[0..9]=0; } 类Ｃ语言的语法规则示例（续） 例3 typedef struct student{ char id[5]; char name[11]; int age; int math; int eng; int ds; int os; }student; void example_3( )