章绪论讲-数据结构求解问题过程.pptx

元素之间关系：无。特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。1.1.2逻辑结构类型1、集合1/17各种各样的数据呈现出不同的逻辑结构，归纳为4种。

元素之间关系：一对一。特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。…2、线性结构2/17

元素之间关系：一对多。特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后续元素；除开始元素外，每个元素有且仅有一个前驱元素。3、树形结构3/17

【例1-3】有一种数据结构B2=（D，R），其中D={48，25，64，57，82，36，75}R={r1，r2}r1={25，36，36，48，48，57，57，64，64，75，75，82}r2={48，25，48，64，64，57，64，82，25，36，82，75}4/17画出其逻辑结构表示，指出是什么类型？

48253664578275r2关系表示r1关系表示解：B2的逻辑结构图如下。5/17r1为线性结构r2为树形结构

元素之间关系：多对多。特点：所有元素都可能有多个前驱元素和多个后继元素。4、图形结构6/17

1.1.3存储结构类型顺序存储结构链式存储结构索引存储结构哈希（散列）存储结构7/17在软件开发中，人们设计了各种存储结构。归纳为4种基本的存储结构。

在高级程序语言中提供了多种数据类型。不同数据类型的变量，其所能取的值的范围不同，所能进行的操作不同。1.1.4数据类型和抽象数据类型数据类型是一个值的集合和定义在此集合上的一组操作的总称。1、数据类型8/17

例如，C/C++中的int就是整型数据类型（16位计算机）。-32768~32767＋、－、*、／?值的集合一组操作9/17

inti=2，j=5，k;k=i+j;...?因为i、j和k都属于int，而int提供了各种运算，所以可以进行相应运算。inti=9999999999;i**;?例如，int数据类型：数据类型和数据结构的关系：数据类型就是已经实现了的数据结构。10/17

抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。2、抽象数据类型11/17抽象数据类型=逻辑结构＋抽象运算

ADTComplex{数据对象：D={e1，e2|e1，e2均为实数}数据关系：R={e1，e2|e1是复数的实部，e2是复数的虚部}一个复数的形式：e1+e2i或（e1，e2）例如，定义复数抽象数据类型Complex12/17

基本运算：AssignComplex(z，v1，v2)：构造复数Z。DestroyComplex(z)：复数z被销毁。GetReal(z，real)：返回复数z的实部值。GetImag(z，Imag)：返回复数z的虚部值。Add(z1，z2，sum)：返回两个复数z1、z2的和。}ADTComplex运算功能描述13/17

Complex编程实现该数据结构ADT抽象数据类型实质上就是对一个求解问题的形式化描述（与计算机无关），程序员可以在理解基础上实现它。14/17

思考题采用C/C++语言如何实现复数抽象数据类型Complex？15/17

?算法设计?设计存储结构?问题描述ADT＝逻辑结构＋抽象运算（功能描述）映射存储结构1存储结构n…算法11…算法1m算法n1…算法nm运算实现最佳算法算法分析?算法分析1.1.5数据结构求解问题的过程16/17

━━本讲完━━17/17