当前位置：文档之家 › 自考数据结构课件 第一章 绪论

自考数据结构课件 第一章 绪论

  • 格式：ppt
  • 大小：492.50 KB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

自考互联网数据库实践重点分析课件复习资料

自考互联网数据库实践重点分析课件复习资料

第二章 关系数据库简介 1. 了解传统的集合运算和专门的关系运算的运算规则， 会识别不同的关系代数的运算符。能够进行各种集合运算 和专门的关系运算。 2. 了解元组关系演算语言，能够运用元组关系演算语言 ALPHA进行元组关系演算。 3. 了解域关系演算语言，能够运用关系演算语言QBE进行 域关系演算。
学习目标
第一章 绪论 1. 掌握数据结构、数据操作和完整性约束的含义及在数 据库中的作用；理解概念模型的含义及表示方法，掌握实 体——联系方法。 2. 理解三种常用的数据模型即层次模型、网状模型和关 系模型的数据结构、数据操作和完整性约束、存储结构和 各自的优缺点。 3. 能够进行实体抽象，运用E—R图建立满足一定完整性 约束条件的关系型数据模型。
第十章 数据库管理系统简介 了解Oracle数据库产品的特点、Sybase的特点和 Informix的特点。 第十一章 数据库新技术 1. 掌握面向对象数据库的语言及功能。 2. 了解分布式数据库系统的特点和模式结构。 3. 了解支持并行数据库系统的并行结构、共享内存结构、 共享磁盘结构和无共享资源结构。 4. 掌握多媒体数据库模型的建立方法：扩充关系模型、 语义模型和面向对象模型。 5. 了解数据仓库的结构和信息流程。
建立了数据库后，就会出现如图2所示的数据库编辑窗口， 通过它可以建立数据库中的各个组成部分。在图2中点击 左边对象栏中的“表”按钮，右边窗口中显示出表视图， 如图2所示。
双击“使用向导创建表”，弹出“表向导”对话框如图3所示。在图 3种从“示例表”中选择“客户”，在示例字段中选择新表中需要包 含的字段（如“客户ID”），然后点击 按钮，将其列入到“新表 中的字 4 段”。按照这种方法选择所有需要的字段（包括“客户 ID”“公司名称”“城市”“电话号码”“传真号码”“电子邮件 地址”）。选中“城市”，点击“重命名字段”按钮，把“城市” 字段的名称改为“公司所在城市”，完成后效果如图3所示，点及 “完成” 按钮，就建立好一个名为“客户”的新表，如图4所示。

数据结构 第一章 绪论

数据结构 第一章 绪论

理。
第一章
绪论
学习要点
了解数据结构有关概念的含义，特别是数据 的逻辑结构，数据的存储结构之间的关系；
1
2 熟悉类C语言的书写规范，特别要注意值调用 和引用调用的区别及出错处理方式； 3 了解算法时间复杂度的计算方法；
本章的主要内容：
1.1 1.2 1.3 1.4
什么是数据结构： 基本概念和术语 抽象数据类型的表示与实现 算法与算法分析 补充 类C语言简要说明
2）熟练掌握一门程序设计语言。
3) 熟知应用领域的相关知识。
其后两个条件比较容易实现，而第一个条件则需 要花相当的时间和精力才行。这也是区分一个程序设 计人员水平高低的一个重要标志。因此，我们学习数 据结构的目的，就是为了更好地进行程序设计。
1.1 什么是数据结构
数据结构课程就是要对不同的数据对象（Data object) 进行探索。对每种数据对象，首先考虑要执行的操作，然 后考虑表示这种数据对象的方法，以使这些操作有效地实 现(算法 Algorithm）。 学习数据结构，要掌握两种技术： 1）善于设计种种可供选择的数据表示形式(Data Structure）。 2）对相应的Data Structure设计出完成各种操作的 算法。 2.什么是数据结构？
数据结构是一门研究非数值计算的程序设计问题中计 算机的操作对象以及它们之间的关系和操作等等的学科。
本课程主要讨论以下三种数据结构：
1.1 什么是数据结构
1.1 什么是数据结构
Tt
a
b
c
a1
a2
b1
b2
c1
c2
d
d1
d2
d3
图 1-2
树形结构示意图
1.1 什么是数据结构

数据结构课件 第一章 绪论

数据结构课件 第一章 绪论

• 教室：1-404
数学与计算机科学学院
数 据 结 构 多 媒 体 课 件
第一章
1.1
1.2 1.3
绪 论
什么是数据结构
基本概念和术语 算法和算法分析
数学与计算机科学学院
数 据 结 构 多 媒 体 课 件
教学重点
⑴数据、数据元素、数据项 ⑵逻辑结构和数据结构 在概念上的联系与区别 ⑶运算的概念 ⑷存储结构及其三个组成部分 ⑸抽象数据类型和数据抽象 ⑹评价算法优劣的标准及方法。
数 据 结 构 多 媒 体 课 件
常见时间复杂度按递增排列为: O(1), O(log2n), O(n), O(nlog2n), O(n2), O(n3),……O(nk), O(2n)
数学与计算机科学学院
数 据 结 构 多 媒 体 课 件
空 间 复 杂 度
用空间复杂度作为算法所需 存储空间的度量,记做 S(n)=O(f(n))
数据元素
数学与计算机科学学院
数 据 结 构 多 媒 体 课 件
• 4、数据对象(Data Object) ：是性 质相同的数据元素的集合，是数据 的一个子集。 • 例如：整数数据对象是集合
N={0,±1,±2， …}，字母字符数据对 象是集合C={′A′，′B′，…，′Z′}
数学与计算机科学学院
数 据 结 构 多 媒 体 课 件
数学与计算机科学学院
数 据 结 构 多 媒 体 课 件
时 间 复 杂 度
一般算法中基本操作重复执行的次数是问 题规模n 的某个函数f(n),算法的时间量度记 做 T(n)=O(f(n)).它表示随问题规模n 的增大, 算法执行时间的增长率和f(n).的增长率相同. 例如1. x=x+1; 时间复杂度为O(1),称为常量阶 2. for(i=1;i<=n;i++) x=x+1;时间复杂度 为O(n),称为线性阶 3. for(i=1;i<=n;i++) for(j=1;j<=n;j++) x=x+1; 时间复杂度为O(n2), 称为平方阶 数学与计算机科学学院

《数据结构》第一章重点知识梳理

《数据结构》第一章重点知识梳理
12
第一章 绪论
求绝对值 abs（表达式） 求不足整数值 floor（表达式） 求进位整数值 ceil（表达式） 判定文件结束 eof（文件变量） （10）逻辑运算 与运算&&：对于A&&B，当A的值为0时，不在对B求值。 或运算||：对于A||B，当A的值为非0时，不在对B求值。 四、算法和算法分析 1．算法 （1）算法的定义
由于算法的时间复杂度考虑的只是对于问题规模n的增长率，因此在难以精确计算基本操作 执行次数（或语句频度）的情况下，只需求出它关于n的增长率或阶即可。 4．算法的存储空间需求
类似于算法的时间复杂度，以空间复杂度（spacecomplexity）作为算法所需存储空间的量 度，记作S（n）=O（f（n））其中n为问题的规模。
18
的表示。
①元素的表示。计算机数据元素用一个由若干位组合 起来形成的一个位串表示。
图1-1四类基本结构的关系图。
5
第一章 绪论
②关系的表示。 计算机中数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象。 并由这两种不同的表示方法得到两种不同的存储结构：顺序存储结构和链式存储结构。 a．顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 b．非顺序映象的特点是借助指示元素存储地址的指针（pointer）表示数据元素之间的逻辑
数据元素（dataelement）是数据的基本单位，在计算机程序中通常作为一个整体进行考 虑和处理。
3
第一章 绪论
3．数据对象 数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集。
4．数据结构 数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据结构的基本结构 根据数据元素之间关系的不同特性，通常有下列四类基本结构： ①集合。数据元素之间除了“同属于一个集合”的关系外，别无其它关系。 ②线性结构。数据元素之间存在一个对一个的关系。 ③树形结构。数据元素之间存在一个对多个的关系。 ④图状结构或网状结构。数据元素之间存在多个对多个的关系。

数据结构 课件 第一章绪论

数据结构 课件 第一章绪论
2010-112010-11-18 4
1.1 数据结构(续) 数据结构(
很多问题求解最后都转化为求解数学方程或数学方程组。 很多问题求解最后都转化为求解数学方程或数学方程组。 在房屋设计或桥梁设计中的结构应力分析 结构应力分析计算可化解为 在房屋设计或桥梁设计中的结构应力分析计算可化解为 线性代数方程组求解的问题 的问题, 线性代数方程组求解的问题, 天天看到的天气预报 它的数学模型是一个环流模式方 天气预报, 天天看到的天气预报,它的数学模型是一个环流模式方 程。 预报人口增长情况的数学模型为微分方程。 情况的数学模型为微分方程 预报人口增长情况的数学模型为微分方程。 当计算机进入非数值计算领域 非数值计算领域, 当计算机进入非数值计算领域,特别是用在管理上的时 候,计算机的操作对象之间的关系就无法用数学方程加以 描述了。 描述了。
按书名
高等数学 理论力学 线性代数 ……
S01 L01 S01 S02 ……
索引表
分类号: 001，003…… 001，003…… 出版单位: 樊映川 002，…….. 002，…….. 出版时间: 华罗庚 004， 004，…… 栾汝书 价格:
…….. ……..
……. …….
按作者名
001,… 001,… 002,…. 002,… 004,… 004,…. ……. …….
2010-112010-11-18
7
例2 - 1
人机对奕问题
树形的数据结 构
……..
……..
2010-112010-11-18
…...
…...
…...
…...
8
例2 - 2
学校问题
树形的数据结 构
刘志刚
部门
…….. ..

数据结构讲义精品PPT课件

数据结构讲义精品PPT课件

003 陈诚 02 男 19840910 638
… … … ……
…
数据元素
数据结构 具有结构的数据元素的集合。它包 括数据元素的逻辑结构、存储结构和相适应的 运算。
逻辑结构
数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。
《The Art of Computer Programming》
Art Evans
数据结构在计算机科学中是一门综合性的专业基础课， 也是计算机专业的必修课，是其它许多课程的先修课程， 是设计编译程序、操作系统、数据库系统等系统程序和 大型应用程序的重要基础。
1.2 基本概念和术语
基本术语
数据 被计算机加工处理的对象。 数据元素（记录、表目） 数据的基本单位，
几种常用的运算有： (1)建立数据结构 (2)清除数据结构 (3)插入数据元素 (4)删除数据元素 (5)排序
(6)检索* (7)更新 (8)判空和判满* (9)求长*
*操作为引用型操作，即数据值不发生变化； 其它为加工型操作。
抽象数据类型
抽象数据类型 ADT（ Abstract Data Type ）： 数据类型概念的引伸。指一个数学模型以及在其上定义的操作集 合，与计算机无关。 数据类型：一组值的集合和定义在其上的一组操作的总称。
抽象数据类型的描述方法
ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名
其中基本操作的定义格式为:
基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉

数据结构第一章ppt课件

数据结构第一章ppt课件
一组操作 – ADT = ( D，S，P )
其中：D 是数据对象， S 是 D 上的关系集， P 是 D 的基本操作集
算法
• 算法 算法是对问题求解过程的一种描述，是 为解决一个或一类问题给出的一个确定 的、有限长的操作序列。重要特性：
– 有穷性 对于任意一组合法的输入值，在执行有穷步 骤之后一定能结束。
– 赋值方式不同
• 对字符指针变量，可用赋值语句赋值 • 字符数组，可在定义时初始化，不能整体赋值
– 指针变量的值是可以改变的
• 数组名代表数组的起始地址，是一个常量，而常 量是不能被改变的
结构体
• 结构体类型与结构体变量的定义 • 结构体变量的引用与初始化 • 结构体指针 • 结构体数组
结构体
– 形式参数和实际参数 – 值传递
函数
• 递归调用
– 一个函数在它的函数体内，直接或间接地调用它自 身
– 例如求N！(n>=0)
long power(int n) { long f; if(n>1) f=power(n-1)*n; else f=1; return (f); }
函数
• 数组作为函数参数
• 数组的定义 • 数组元素的引用 • 数组的元素的初始化 • 应用举例
数组
• 数组的定义 – 数据类型 数组名[常量表达式] – int a[10];
– 下标从0开始 – 数组名代表整个数组的首地址
数组
• 一维数组元素的引用
– 数组名[下标表达式]
• 一维数组的元素的初始化
– 数据类型 数组名[常量表达式]＝{初值表}
– 使用指向数组的指针变量来引用数组元素
main()
{ int array[10], *pointer=array, i;

数据结构第一章绪论(1)PPT教学课件

数据结构第一章绪论(1)PPT教学课件

2020/12/10
7
二、 数据结构（ Data Structure ）
★ 数据结构是相互之间存在一种或多种特定关系的 数据元素的集合
◆ 数据结构＝数据＋结构（关系）
2020/12/10
8
数据结构的描述方式
1、逻辑结构
★ 是对数据元素之间逻辑关系（抛开具体的关系 含义以及存储方式等）的描述
◆ 它可以用一个数据元素的集合和定义在此集合 上的几个关系来表示
第一章 绪论
第一节 什么是数据结构 ★ 数据结构（Data Structure）
2020/12/10
1
什么是数据结构
★ 数据结构作为一门独立的课程在国外是从1968年 才开始设立的
◆ 当时，数据结构几乎和图论，特别是和表、树的 理论成为同义语
2020/12/10
2
什么是数据结构
◆ 但对于数据结构的概念，至今尚未有一个被一致 公认的定义
2020/12/10
9
★ 数据结构通常可用图形表示 圆圈表示数据元素，箭头表示关系
数据元素
数据元素
Ei
关系
E i+1
数据结构的描述方式
2、物理结构（存储结构）
★ 数据结构在计算机中的具体表示（representation） 和实现 （implementation）
2020/12/10
11
数据结构的分类 1、按逻辑结构分类 ★ 集合、线性结构、树型结构、图状结构 2、按物理结构分类 ★ 顺序存储结构、链式存储结构、索引存储结构
2020/12/10
12
数据结构的概念
★ 数据结构的形式定义为
◆ 数据结构是一个二元组 Data_Structure=（D，S）

《数据结构》讲义

《数据结构》讲义

数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。

包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成（）数据对象是性质相同的数据元素的集合，是数据的一个子集。

…}，字母字符数据对象是集合象。

由此可看出，不论数据元素集合是无限集（如整数集）Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

线性结构：结构中的数据元素之间存在着一对一的线性关系。

图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。

为数据结构的有限集，S是D上关系的有限集。

表示复数的虚部。

存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括据元素的表示和关系的表示形式化描述：要存入机器中，建立一从，使S（D逻辑结构与存储结构的关系为：数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。

按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合，即该类型的取值范围，以及该类型中可允许使用的一组运算。

例如高级语言中的数据类型就是已经实现的从这个意义上讲，数据类型是高级语言中允许的变量种类，计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如二进制数据的抽象; 使用者在编程时可以直接使用据抽象，出现了数据类型，(Abstract Data Type)）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。

抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

数据结构第一章 绪论PPT课件

数据结构第一章 绪论PPT课件

28.11.2020
21
算法设计的要求
算法的正确性 l 可读性 l 健壮性 l 高效率和低存储量
例如要求n个数的最大值问题 给出算法如下：
max:=0; for（i=1 ；i<= n ;i++） { scanf("%f", x);
if (x>max) max=x; }
28.11.2020
22
算法描述的工具
算法可用自然语言、框图或高级程序设计语言 进行描述。
类语言是接近于高级语言而又不是严格的高级 语言，具有高级语言的一般语句设施，撇掉语言中 的细节，以便把注意力主要集中在算法处理步骤本 身的描述上。
28.11.2020
23
设计实现算法过程步骤
1. 找出与求解有关的数据元素之间的关系
2. 确定在某一数据对象上所施加运算 3. 考虑数据元素的存储表示 4. 选择描述算法的语言 5.设计实现求解的算法，并用程序语言加以描述。
例如：
树
28.11.2020
8
图状结构或网状结构
定义： 结构中的数据元素之间存在着多对
多的任意关系。
例如：
图
28.11.2020
9
逻辑结构
定义： 数据的逻辑结构是指数据元素之间逻辑关系描述。
l形式化描述： Data_Structure=（D,R）其中D是数据元素的
有限集，R是D上关系的有限集。
28.11.2020
5
集合结构
定义： 结构中的数据元素之间除了同属于
一个集合的关系外，无任何其它关系。
例如：
集合
28.11.2020
6
线性结构
定义： 结构中的数据元素之间存在着一对

数据结构PPT第一章绪论

数据结构PPT第一章绪论
运算序列
特性
输入 有0个或多个输入
输出 有一个或多个输出(处理结果)
确定性 每步定义都是确切、无歧义的
有穷性 算法应在执行有穷步后结束
有效性 每一条运算应足够基本
算法定义
事例学习：选择排序问题
明确问题：非递减排序
解决方案：逐个选择最小数据
算法框架：
for ( int i=0; i<n-1; i++ ) { //n-1趟
从a[i]检查到a[n-1];
若最小的整数在a[k], 交换a[i]与a[k];
}
细化程序：程序 SelectSort
void selectSort ( int a[ ], const int n ) {
//对n个整数a[0],a[1],…,a[n-1], 按非递减顺序排序
for ( int i=0; i<n-1; i++ ) {
//交换Elem[j-1]与Elem[j]
exchange = 1;
//做“发生了交换”标志
}
}
−1
渐进时间复杂度：O(f (n)*g (n)) =
−1
෍ − =
2
=1
sum[i] = 0.0;
//数据累加
for ( int j=0; j<n; j++ ) sum[i] += x[i][j];
}
for ( i = 0; i < m; i++ ) //打印各行数据和
cout << “Line ” << i <<
“ : ” <<sum [i] << endl;

数据结构(从概念到算法)第一章 绪论

数据结构(从概念到算法)第一章 绪论
态）。
（2）可读性：算法的变量命名、格式符合行业规范，并在关键处给出注释，
以提升算法的可理解性。
（3）健壮性：算法能对不合理的输入给出相应的提示信息，并做出相应处
理。
（4）高执行效率与低存储量开销：涉及算法的时间复杂度和空间复杂度评
判。
算法设计的一般步骤
1.3.1算法定义与性质
算法设计出来后有多种表述方法，一般有如下几种描述工具：第一种是自然语
良好基础，数据结构与算法设计密不可分。算法是对特定问题求解步骤的一种描述。
换言之，算法给出了求解一个问题的思路和策略。
一个算法应该具有以下 5 个特征。
（1）有穷性，即算法的最基本特征，要求算法必须在有限步（或有限时间）
之后执行完成。
（2）确定性，即每条指令或步骤都无二义性，具有明确的含义。
（3）可行性，即算法中的操作都可以通过已经实现的基本运算执行有限次
成的集合，数据对象是数据的一个子集。实例说明如下。
由 4 个整数组成的数据对象： D1={20,- 30,88,45}
由正整数组成的数据对象： D2={1,2,3,…}
数据结构的基本概念
（5）数据结构。数据结构是相互之间存在一种或多种特定关系的数据元素
的集合。数据元素之间的关系称为结构，主要有 4 类基本结构，如下图所示。
址，数据'C'的指针指向数据'D'的结点地址，具体如图所示。
数据结构的基本概念
上图数据元素存储的地址在整体上具有前后次序，但实际对单链表数据元素
所分配的存储空间是随机的。如下图 所示，数据元素'A'在物理存储地址上可能位
于数据元素'B'和'D'存储地址之后。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

5．数据类型和抽象数据类型
数据类型（Data Type） 自20世纪70年代以来，几乎所有的高级程序设计语言都提供了这一 概念。在用高级语言编写的程序中间，程序中出现的每个变量，常量 或表达式，都必须事先说明它们所属的数据类型，每个类型都明显或 隐含的规定了在程序执行期间它的变量，它的表达式所允许取值的范 围，以及允许进行的操作，因此 所谓数据类型是一个值的集合以及在这些值上定义的一组操作的总称。 通常数据类型可以看作是程序设计语言中已实现的数据结构。 【例1．2】C语言的"整数类型"就定义了一个整数可取值的范围（其 最大值INT-MAX依赖于具体机器）以及对整数可施加的加、减、乘、 除和取模等操作。 按"值"是否可分解，可将数据类型划分为两类： ①原子类型：其值不可分解。通常是由语言直接提供。 【例】C语言的整型、字符型等标准类型及指针等简单的导出类型； ②结构类型：其值可分解为若干个成分（或称为分量）。是用户借助 于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故 它也是一种导出类型。 【例】C的数组、结构等类型。
3．数据的四种基本存储方法
数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻 的存储单元里，结点间的逻辑关系由存储单元的邻接 关系来体现。 由此得到的存储表示称为顺序存储结构，通常借助 程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数 据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相 邻，结点间的逻辑关系由附加的指针字段表示。由此 得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。
存储内容 元素1 元素4 …….. 元素2 ……..
指针 1400 ∧ ……. 1536 …….
1536
ห้องสมุดไป่ตู้
元素3
1346
（3）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。 索引表由若干索引项组成。若每个结点在索引表中都有一个 索引项，则该索引表称之为稠密索引（Dense Index）。若一组 结点在索引表中只对应一个索引项，则该索引表称为稀疏索引 (Spare Index)。索引项的一般形式是： (关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引 项的地址指示结点所在的存储位置；稀疏索引中索引项的地址 指示一组结点的起始存储位置。 （4）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点 的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结 构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结 构。选择何种存储结构来表示相应的逻辑结构，视具体要求而 定，主要考虑运算方便及算法的时空要求。
数据项（data
element）—是数据的基本单位，
由若干个数据项组成，也称结点、元素、顶点或记录。
item）—是具有独立含义的最小标
识单位，有时也称为域（field），即数据表中的字 段。
数据结构(data
structure)：指的是数据之间
的相互关系，即数据的组织形式。 数据结构一般包括以下三方面内容： ① 数据元素之间的逻辑关系，也称数据的 逻辑结构（Logical Structure）； ② 数据元素及其关系在计算机存储器内的 表示，称为数据的存储结构（Storage Structure）； ③ 数据的运算，即对数据施加的操作。
（2）存储结构 该表的存储结构是指用计算机语言如何表示结点之间的这种关 系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是 用指针将这些结点链接在一起？ （3）数据的运算 在上面的学生成绩表中，可能要经常查看某一学生的成绩；当 学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如 何进行查找、删除、插入，这就是数据的运算问题。 搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。
IsDescending(T) 初始条件：三元组T已存在。
操作结果：如果 T 的 3 个元素按降序排列，则 返回1，否则返回0。 Max(T,&e) 初始条件：三元组T已存在。 操作结果：用e返回T的3个元素中的最大值。 Min(T,&e) 初始条件：三元组T已存在。 操作结果：用e返回T的3个元素中的最小值。 }ADT Triplet
用户也可用typedef 自己定义数据类型
typedef struct { int num; char name[20]; float score; } STUDENT; STUDENT stu1,stu2, *p;
抽 象 数 据 类 型 ADT （ Abstract Data Type)
定义：是指抽象数据的组织和与之相关的操作。可以 看作是数据的逻辑结构及其在逻辑结构上定义的操作 。 数据结构+定义在此数据结构上的一组操作 = 抽象 数据类型
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概 念。 【例1．1】 学生成绩表，见下表。
（1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、 姓名、各科成绩及平均成绩等数据项组成。 表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且 在它前面的结点（亦称为直接前趋（Immediate Predecessor））最 多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后 继（Immediate Successor））也最多只有一个。表中只有第一个结 点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接 后继。故称之为终端结点。例如，表中"李四"所在结点的直接前趋 结点和直接后继结点分别是"张三"和"王五"所在的结点，上述结点 间的关系构成了这张学生成绩表的逻辑结构。
教材: 自考《数据结构》 苏仕华 编著
授课教师：涂风华 开始日期：2014年3月1日
第1章 概论
1.1 基本概念和术语
1.2 学习数据结构的意义 1.3 算法的描述和分析
§1.1 基本概念和术语
数据（data)—是信息的载体。它能够被计算机识
别、存储和加工处理，是计算机程序加工的"原料"。
数据元素（data
2．数据的逻辑结构分类
在不产生混淆的前提下，常将数据的逻辑结构简称 为数据结构。数据的逻辑结构有两大类： （1）线性结构 线性结构的逻辑特征是：若结构是非空集，则有且 仅有一个开始结点和一个终端结点，并且所有结点都 最多只有一个直接前趋和一个直接后继。 线性表是一个典型的线性结构。栈、队列、串等都 是线性结构。 （2）非线性结构 非线性结构的逻辑特征是：一个结点可能有多个直 接前趋和直接后继。数组、广义表、树和图等数据结 构都是非线性结构。
DestroyTriplet（&T） 操作结果：三元组T被销毁。 Get（T,i,&e） 初始条件：三元组T已存在， 1<=i<=3. 操作结果：用e返回T的第i元的值。 Put(&T,i,e) 初始条件：三元组T已存在，1<=i<=3. 操作结果：改变T的第i元的值为e。 IsAscending(T) 初始条件：三元组T已存在。 操作结果：如果T的3个元素按升序排列 ，则返回1，否则返回0。
存储地址 存储内容
Lo 元素1 元素2 ……..
Lo+m
顺序存储
Lo+(i-1)*m
元素i
…….. Lo+（n-1)*m
元素n
Loc(元素i)=Lo+（i-1)*m
h
1345
链式存储
元素2 1536 元素3 1346 元素4
h
元素1 1400
∧
存储地址 1345 1346 ……. 1400 …….
基本操作的定义格式： 赋值参数 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉
引用参数，以“ ＆”打头
例：抽象数据类型三元组的定义： ADT Triplet{ 数据对象：D={e1,e2,e3 |e1,e2,e3∈Elemset} 数据关系：R1={<e1,e2>, <e2,e3> } 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T， 元素e1，e2和e3分别被赋以 参数v1,v2和v3的值。
4．数据结构三方面的关系
数据的逻辑结构、数据的存储结构及数据的运算这三方面是 一个整体。孤立地去理解一个方面，而不注意它们之间的联系 是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的 不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示 ，可称其为顺序表；若采用链式存储方法，则可称其为链表； 若采用散列存储方法，则可称为散列表。 数据的运算也是数据结构不可分割的一个方面。在给定了数 据的逻辑结构和存储结构之后，按定义的运算集合及其运算的 性质不同，也可能导致完全不同的数据结构。 【例】若对线性表上的插入、删除运算限制在表的一端进行 ，则该线性表称之为栈；若对插入限制在表的一端进行，而删 除限制在表的另一端进行，则该线性表称之为队列。更进一步 ，若线性表采用顺序表或链表作为存储结构，则对插入和删除 运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列
①数据的逻辑结构是从逻辑关系上描述数据，与 数据的存储无关，是独立于计算机的。数据的逻 辑结构可以看作是从具体问题抽象出来的数学模 型。 ②数据的存储结构是逻辑结构用计算机语言的实 现（亦称为映象），它依赖于计算机语言。对机 器语言而言，存储结构是具体的。一般，只在高 级语言的层次上讨论存储结构。 ③数据的运算定义在数据的逻辑结构上，每种逻 辑结构都有一个运算的集合。最常用的检索、插 入、删除、更新、排序等运算实际上只是在抽象 的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是 "做什么"，而无须考虑"如何做"。只有确定了存 储结构之后，才考虑如何具体实现这些运算。 3