2007东北大学网络学院计算机软件技术基础课程组11数据结构

数据元素是数据对象的实例。 整数数据对象是集合N={…-2,-1,0,1,2…..} 数据结构-概述2007年东北大学网络学院计算机软件技术基础课程第12组数据结构的基本概念数据结构( ）数据结构是相互之间具有一定逻辑关系的数据元素的集合。 例如：在一维数组{a1,a2,a3,a4,a5,a6}中，数据元素之间存在如下顺序关系{ai,ai+1|数据结构-概述2007年东北大学网络学院计算机软件技术基础课程第十三组计算机中数据结构（也称图像）的标识称为数据的物理结构，数据的逻辑结构是计算机内存中实现检索、排序、插入、删除、修改的数据结构等-概述2007年东北大学网络学院计算机软件技术基础课程第14组数据的逻辑结构可以看成是一组数据（表示为节点集D），以及一组二元关系（关系集S）这些数据之间的关系来表示：（它是数据元素的有限集合，由有限个节点组成的集合，每个节点代表一个数据或一组明确的关系）结构化数据D上的有限关系集合是一个集合集合D上定义的关系，用于描述节点数据之间的逻辑关系。 数据结构——概述 2007 东北大学网络学院计算机软件技术基础课程第15组高级 在语言中，是指数据的取值范围以及对其可以进行的操作的总称。 基本数据类型：int、char、float等。用户也可以定义自己的数据类型。 节点的类型可以是基本数据类型，也可以根据应用的需要而定。 灵活定义;[20];;};,*pstu;数据结构-概述2007东北大学网络学院计算机软件技术基础课程第16组线性结构()树结构()图结构()多对多数据结构-概述2007东北大学网络学院计算机软件技术基础课程第17组关系S是线性关系，或者称为“前后关系”，有时也称为“大小关系”。

关系S是有向的并且满足全序和各向异性的约束。 每个节点a都有唯一的直接后继节点b数据结构——概述2007东北大学网络学院计算机软件技术基础课群18 每个节点可以有多个“子节点”，但只能有一个唯一的“父节点” “节点”，也称为节点互连的网络结构，它允许节点有多个“父节点”图，结构关系S没有任何约束，并且关系S的约束不能用来设计图结构。 互联网的网页链接关系是一种非常复杂的图结构数据结构——概述2007东北大学网络学院计算机软件技术基础课群19树结构和图结构的基本区别在于“每个节点是否只属于一个父节点”。 线性结构与树结构的基本区别在于“每个节点是否只有一个直接后继” 数据结构 - 概述 2007 东北大学网络学院计算机软件技术基础课程第20组 数据在计算机内存中的逻辑结构的实现（下图）存储器中的逻辑结构）存储空间提供了一组具有非负整数地址编码的相邻单元计算机指令具有通过地址随机访问存储空间中的任何单元的能力。 访问不同地址所需的访问时间基本相同。 数据结构-概述2007东北大学网络学院计算机软件技术基础课程第21组数据的存储结构就是建立一种映射，为数据逻辑结构（其节点集D）建立从D到内存单元的映射：对于每个节点dD对应一个唯一的连续存储区域。

对于每个关系元组（d1，d2）s（其中d1，d2D​​为节点），d1，d2的逻辑后继关系应映射到存储单元的地址顺序关系（或链接关系）数据结构 - 概述2007东北大学网络学院计算机软件技术基础课程第22组借助元素在内存中的相对位置来表示数据元素之间的逻辑关系。 节点之间的逻辑后继关系用存储单元的自然顺序关系来表示。 数据借助指示元素存储地址的指针来表示。 元素之间的逻辑关系以及两个节点之间的逻辑后继关系可以用指向数据结构的指针来表达——概述2007东北大学网络学院计算机软件技术基础课程第23组什么是数据结构？ (10)Lo+mLo+(i-1)*mLo+(n-1)*m存储地址存储内容Loc(元素i)=Lo+(i-1)*m顺序存储元素1元素2元素i元素nhead数据结构——东北大学网络学院2007计算机软件技术基础课组综述 24 什么是数据结构？ (11)数据的逻辑结构与存储结构密切相关。 算法设计逻辑结构算法实现存储结构数据结构-概述2007年东北大学网络学院计算机软件技术基础课程第25组抽象数据类型（其特点是将数据结构视为独立于应用程序）将程序描述为抽象代数结构的目的是为了数据结构-概述 2007 东北大学网络学院计算机软件技术基础课群 26 抽象数据类型 (1) 抽象 数据的定义类型取决于它的一组逻辑特征，而与它在计算机内部如何表示和实现无关，即无论其内部结构如何变化，只要其数学特征不变，就不会影响其外部使用的数据结构——概述2007年东北大学网络学院计算机软件技术基础课程第27组 摘要数据类型（2）是指一个数学模型以及在这个数学模型上定义的一组运算。

抽象数据类型的正式定义：ADT=(D,S,P)其中：D为数据对象； S是D上的关系集； P 是 D 上基本操作的集合。 ADT 抽象数据类型名 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 ADT 抽象数据类型名 数据结构 -概述 2007 东北大学网络学院计算机软件技术 基础课程组 28 例如抽象数据类型复数的定义： ADT 数据对象：D＝{e1,e2|e1，数据关系：R1＝{e1,e2 e1 是复数的实部； |e2 是复数的虚部} 基本运算：( v1, v2 运算结果：复数 Z 被破坏。( 初始条件：复数已存在。运算结果：使用返回复数的实部值 Z. ( 初始条件：复数已经存在。运算结果：使用返回复数 Z 的虚部值。Add( z1,z2, &sum 初始条件：z1,z2 是复数。运算结果：使用 sum返回两个复数 z1,z2 数据结构 - 概述 2007 东北大学网络学院计算机软件技术基础课群 29 摘要数据类型 (3) ADT 的重要特点 当使用 ADT 来描述程序处理的实体时，重点是它的本质特征、它能完成的功能以及它与外部用户的接口（即外界使用它的方式），将外部功能与其内部实现细节分开，并对外部用户隐藏其内部实现细节数据结构-概述2007年东北大学网络学院计算机软件技术基础课第30组摘要数据类型（四）