当前位置：文档之家 › 第一章_数据结构----绪论

第一章_数据结构----绪论

  • 格式：pdf
  • 大小：767.44 KB
  • 文档页数：14

下载文档原格式

  / 14

合集下载

《刘大有数据结构》 chapter 1 绪论

《刘大有数据结构》 chapter 1 绪论


数据元素是组成数据的基本单位，在不同情况 数据元素是组成数据的基本单位， 是组成数据的基本单位 下，数据元素可以有元素、结点或者顶点等不 数据元素可以有元素、 同的名称。一个数据元素可以由若干个域（或 同的名称。一个数据元素可以由若干个域（ 曰字段）组成。 曰字段）组成。
数据结构指的是数据之间的相互关系，它主要包含 数据结构指的是数据之间的相互关系， 指的是数据之间的相互关系 三部分内容： 三部分内容： （1）数据的逻辑结构，也就是数据元素之间的逻 ）数据的逻辑结构， 辑关系。 辑关系。 （2）数据的存储结构，也就是数据元素及其相互 ）数据的存储结构， 关系（逻辑结构）在存储器中的实现方式。 关系（逻辑结构）在存储器中的实现方式。 ( 3 ) 对数据需要施加的操作。 对数据需要施加的操作。 主要包括：查找、插入、删除、修改和排序等。 主要包括：查找、插入、删除、修改和排序等。
赋给变量Width的新值 无 将矩形的宽度值修改为新值 无 矩形宽度值被修改 无 无 计算矩形面积 返回矩形面积值 无 无 无 计算矩形周长 返回矩形周长值 无
1.3 算法概念和算法描述语言
让计算机完成解题任务，除了要选取适当的数 让计算机完成解题任务， 据结构外，还需要我们制定出解决问题的切实 据结构外， 可行的方法和步骤，这就是所谓的计算机算法. 可行的方法和步骤，这就是所谓的计算机算法 计算机算法
1.2 面向对象程序设计 面向对象程序设计OOP与抽象数据类型 与抽象数据类型 ADT
根据面向对象程序设计的思想， 根据面向对象程序设计的思想，可以将每 种数据结构都视为一个抽象类型，它定义数据 种数据结构都视为一个抽象类型， 的组织方式，且给出数据上的基本操作， 的组织方式，且给出数据上的基本操作，这种 结构称为抽象数据类型（ 结构称为抽象数据类型（Abstract Data Type， 抽象数据类型 ， 简称ADT）. ） 简称
《数据结构教程》第一章 绪论

《数据结构教程》第一章 绪论

《数据结构教程》第一章绪论数据结构教程第一章绪论数据结构是计算机科学中的重要概念之一，它是计算机程序设计的基础。

本教程的第一章将介绍数据结构的基本概念和作用。

一、什么是数据结构？在计算机科学中，数据结构用于存储和组织数据，以便在计算机程序中进行高效的操作。

数据结构可以分为两种基本类型：线性数据结构和非线性数据结构。

1.1 线性数据结构线性数据结构是最简单的数据结构之一，它将数据元素按照线性顺序组织，可以使用一对一的关系连接数据元素。

常见的线性数据结构有数组、链表和栈。

1.2 非线性数据结构非线性数据结构是指数据元素之间存在多对多的关系，不是简单的一对一关系。

常见的非线性数据结构有树和图。

二、数据结构的作用数据结构的设计和选择对于程序的效率和性能具有重要影响。

合理选择数据结构可以提高算法的执行速度，降低计算机资源的占用。

2.1 提高数据的存储效率通过选择适当的数据结构可以减少内存的占用，提高数据的存储效率。

例如，链表数据结构可以动态地分配内存空间，减少内存的浪费。

2.2 提高数据的访问效率不同的数据结构在数据的访问效率上有所差异。

例如，对于需要频繁插入和删除操作的场景，链表数据结构比数组数据结构更加高效。

2.3 优化算法的执行速度数据结构和算法是相辅相成的，通过选择合适的数据结构可以优化算法的执行速度。

例如，在查找操作中使用二叉搜索树可以降低时间复杂度。

三、数据结构的分类根据数据结构的存储方式和操作特性，可以将数据结构分为线性数据结构和非线性数据结构。

3.1 线性数据结构线性数据结构是最常用的数据结构之一，它将数据元素按照线性顺序排列，每个元素有一个直接前驱和直接后继。

常见的线性数据结构有数组、链表和栈。

3.1.1 数组数组是一种最简单的数据结构，它将数据元素存储在连续的内存空间中。

数组的访问速度很快，但是插入和删除操作的效率较低。

3.1.2 链表链表是一种动态数据结构，它通过指针将数据元素链接在一起。

数据结构

数据结构

第1章绪论1.1 什么是数据结构数据与数据之间的关系1.2 基本概念和术语1.基本定义(1).数据(Data) ：是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

(2)数据项(Data Item)：一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

数据项是对客观事物某一方面特性的数据描述。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

2.举例如字符集合C={‘A’,‘B’,‘C’,…}--C表示字符对象；A ，B等表示数据元素；再如学生集合Students={“Zhangsan”, “Lisi”，…}Zhangsan(ID,name,age,grade,…)……--Students表示学生对象；“Zhangsan”、“Lisi”表示数据元素；Zhangsan的ID、name、age等表示数据项。

3.数据结构的形式定义数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集4.逻辑结构与物理结构(1)数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

(2)数据结构在计算机中的表示（映像）称为数据的物理结构。

数据结构的存储方式1)顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。

2)链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。

3)例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的存储结构。

第1章 数据结构绪论

第1章 数据结构绪论

数学 代数系统
编译理论 数据表示法 存储装置 硬件(计算机系统设计)
算子关系 数据 数据的操作 类型 数据结构 文件系统 数据存取 数据组织 机器组织 信息检索 软件(计算机程序设计)
4
1.1 引
言
为了使读者对数据结构有一个感性的认识， 为了使读者对数据结构有一个感性的认识， 下面给出几个数据结构的示例， 下面给出几个数据结构的示例，读者可以 通过这些示例去理解数据结构的概念。 通过这些示例去理解数据结构的概念。 【示例1】 职工基本情况表。 参见教材P2 【示例2】 井字棋对弈问题。 【示例3】 教学计划编排问题。
9
1.3 抽象数据类型
首先我们了解一下在程序设 计语言中出现的各种数据类 型。
10
1.3.1 数据类型
数据类型是一个值的集合和定义在这个值集上 的一组操作的总称。 的一组操作的总称。 在高级程序设计语言中，数据类型可分为两类： 在高级程序设计语言中，数据类型可分为两类： 一类是原子类型，另一类则是结构类型。 一类是原子类型，另一类则是结构类型。 在某种意义上，数据结构可以看成是“ 在某种意义上，数据结构可以看成是“一组具 有相同结构的值” 有相同结构的值”，而数据类型则可被看成是 由一种数据结构和定义在其上的一组操作所组 成的。 成的。
6
1.2 基本概念与术语
1. 逻辑结构
(1) 线性结构。 (2) 集合结构。 (3) 树形结构。 (4) 图状结构。 数据的四种基本逻辑结构如图1.4所示。
7
1.2 基本概念与术语
2. 存储结构 (1) 顺序存储结构是指把逻辑上相邻的结 点存储在物理上相邻的存储单元里，结点 之间的逻辑关系由存储单元位置的邻接关 系来体现。 (2) 链式存储结构是把逻辑上相邻的结点 存储在物理上任意的存储单元里，结点之 间的逻辑关系由附加的指针域来体现。 (3) 索引存储结构是用结点的索引号来确 定结点的存储地址。
数据结构第1章 绪论

数据结构第1章 绪论


课程改革: 课程改革:
实验单独设课, 强调上机实践能力 数据结构课程: 理论课(68课时4学分)+实验课(24课时1.5 学分) 课程考核
1.3 基本概念和术语
1、 2、 3、 4、 5、 6、 数据 数据元素 数据对象 数据结构 数据类型 抽象数据类型
1. 数据 能输入到计算机中的符号集 数据: 合. 2. 数据元素 数据的基本单位. 数据元素: 3. 数据对象 数据对象: 具有相同性质的数据元素的集合. 4. 数据结构: DATA STRUCTURE 数据结构: 数据及其相互关 系的集合. 分为逻辑结构和存储结构(物理结 构). 数据结构-------------------------------类 数据结构----------------类 CLASS
数据的存储结构
1. 顺序存储结构 顺序存储结构：借助元素在存储器中的相对位置 来表示数据元素间的逻辑关系。 【例1.4】对于表1-1提出的学生信息登记表进行存储， 假定每个元素占用50个存储单元，数据从1000号单 元开始由低地址向高地址存放，对应的顺序存储结 构如表1-3所示。
数据的存储结构
顺序存储结构的主要特点： 可实现对各数据元素的随机访问。这是 因为只要知道存储的首地址以及每个数 据元素所占的存储单元，就可以计算出 各数据元素的存储地址。 不利于修改，在对数据元素进行插入、 删除运算时可能要移动一系列的数据元 素。
抽象数据类型的定义： 抽象数据类型的定义：
ADT： ADT：抽象数据类型名 data 数据元素之间逻辑关系定义 operation 操作1 操作1 操作2 操作2
……
操作n 操作n
抽象数据类型 的不同视图
1.4 1.4 算法和算法分析
1. 定义：算法（Algorithm）是对特定问题求 定义：算法（Algorithm） 解步骤的一种描述，它是指令的有限序列， 解步骤的一种描述，它是指令的有限序列，其 中每一条指令表示一个或多个操作。 中每一条指令表示一个或多个操作 特性： 2. 特性：
《数据结构》第一章重点知识梳理

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

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）数据结构的基本结构 根据数据元素之间关系的不同特性，通常有下列四类基本结构： ①集合。数据元素之间除了“同属于一个集合”的关系外，别无其它关系。 ②线性结构。数据元素之间存在一个对一个的关系。 ③树形结构。数据元素之间存在一个对多个的关系。 ④图状结构或网状结构。数据元素之间存在多个对多个的关系。
数据结构 第一章概论

数据结构 第一章概论


注意：常用DataType表示抽象元素类型。
H
13
1.3 算法和算法分析
数据的运算是通过算法描述的。
1.算法----求解一个特定任务的指令的有限序列。
例.求a[0..n-1]中n个数的平均值(假定n>0)。
float average(float a[ ],int n)
{ int i；float s=0.0； //累加器赋初值
8. }
其中:f(m,n)=1+m+2*m*n+m=2mn+2m+1
当m=n时,f(n)=2n2+2n+1
T(n)=O(f(n))=O(2n2+2n+1)=O(n2) 平方阶。
对嵌套层次的循环结构，时间的复杂度T(n)由最内 层循环体语句的频度f(n)决定。
H
22
例4 分析下面的算法
1. void sum(int n)
其中：D1，D3是有穷集，D2是无穷集。
5.抽象数据对象
ElemSet={某种同类型的数据元素}
H
8
6.数据结构(data structure)----
数据之间的相互关系，即数据的组织形式。 内容包括：数据逻辑结构、数据存储结构和数据运算。
数据逻辑结构：数据元素之间的逻辑关系。 数据存储结构：数据元素及其关系在存储器中的存储表示。 数据运算：定义在数据逻辑结构上的操作。如：查询，插入，
(4)
for (k=0；k<n；k++)
n2(n+1)
(5)
c[i][j]=c[i][j]+a[i][k]*b[k][j]； n3
}
}
算法所消耗的时间就是所有语句频度之和T(n):
数据结构第一章--绪论(严蔚敏版)

数据结构第一章--绪论(严蔚敏版)


解 T = (D, R ) D={A,B,a,b,c }
R是D上的关系的集合 是 上的关系的集合
A
B
a R={ P1,P2 } P1 ={<A,a>, <A,b>, <A,c>} P2 ={<B,a>, <B,b>, <B,c>}
b
c
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数可以表示为 a+bi 一个复数可以表示为 复数 C={a,b}
也可以表示成一个有序对 <a, b>
∴这里存在一种关系 P ={<a,b>} (只有一个有序对 只有一个有序对) 只有一个有序对
而R是C上的关系的集合 R={ P } 是 上的关系的集合
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数的数据结构为 Complex= (C , R) 其中， 其中， C={a,b} R={ P } P ={<a,b>}
a b c
解 其数据结构可描述为 d e T = (D, R ) D是数据元素的集合 D={a,b,c,d,e} 是数据元素的集合
R是D上的关系的集合 R={ P } 是 上的关系的集合
P ={<a,b>,<a,c>,<b,d>,<b,e>}
例2
一小组有a,b,c 三个学生，一个导师A 一小组有a,b,c 三个学生，一个导师A 和一个辅导员B 和一个辅导员B，此小组的数据结构如图：
48
ADT 抽象数据类型名 { 数据对象： 数据对象：〈数据对象的定义〉 数据关系： 数据关系：〈数据关系的定义〉 基本操作： 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 基本操作名 初始条件：〈初始条件描述〉 初始条件： 操作结果：〈操作结果描述〉 操作结果
数据结构-第一章 绪论

数据结构-第一章 绪论

计算机专业学生的必修课程课程编号课程名称需要的先导课程编号c1程序设计基础无c2离散数学c1c3数据结构c1c2c4汇编语言c1c5算法分析与设计c3c4c6计算机组成原理c11c7编译原理c5c3c8操作系统c3c6c9高等数学无c10线性代数c9c11普通物理c9c12数值分析c9c10c1?课程先后关系的图形描形式
free(T); T=NULL; return OK; } ……
算法
❖ 定义:是对特定问题求解步骤的一种描述,是 指令的有限序列
❖ 5个特性 有穷性 确定性 可行性 输入 输出
❖ 算法与程序的区别 程序未必满足有穷性。
算法的设计要求
❖ 正确性(correctness) ❖ 可读性(readability) ❖ 健壮性(robustness) ❖ 效率(efficiency)与存储量需求
基本概念和术语(4)
❖ 数据的存储结构(物理结构) 数据逻辑结构在计算机中的表示 两种存储结构 ❖顺序存储结构 ❖链式存储结构
注意:数据的逻辑结构和存储结构的区别
两种存储结构示例
顺序存储结构
链式存储结构
基本概念和术语(5)
❖ 数据运算 是在数据的逻辑结构上定义的操作算法. ❖算法的设计取决于选定的数据逻辑结构. ❖算法的实现依赖于采用的存储结构.
数据结构
第一章 绪论
主讲人:刘波
本章教学目标、重点、难点
❖ 教学目标：了解数据结构这门课程的主要内容,作 用,掌握数据结构的基本概念及术语
❖ 教学重点
数据、数据元素、数据结构、数据类型、抽象数据类型 等概念术语的确定含义、特别是数据结构的三个方面以 及这三方面的相互关系；
描述算法的类C语言与C语言的区别； 算法设计的基本要求及算法的时间分析和空间分析的方
数据结构

数据结构

数据结构知识整理（部分）第一章：绪论1．数据：数据是外部信息的载体，他能够被计算机识别、存储和加工处理，是计算机程序加工的原料；2．数据元素：数据元素是数据的基本单位，在计算机中通常被作为一个整体进行考虑和处理；3．一个数据元素可由若干个数据项组成。

数据项是不可分割的、含有独立意义的最小数据单位，数据项有时也称为字段或域；4．数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。

在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构；5．4种基本数据结构：集合：只有“同属一个集合”的关系；线性结构：存在着一对一的关系；树形结构：存在着一对多的关系；图状结构：存在着多对多的关系；6．数据结构包括数据的逻辑结构和物理结构。

逻辑结构：从具体问题抽象出来的数学模型，与数据在计算机中的具体储存没有关系。

从逻辑上可以把数据结构分为线性结构和非线性结构，其中集合、树、图形结构属于非线性结构；7．数据的物理结构又叫存储结构，是数据在计算机中的表示和存储，包括数据元素的表示和存储以及数据元素之间关系的表示和存储，存储结构必须依赖于计算机。

数据元素之间的关系在计算机中的表示有两种:顺序映像和非顺序映像。

分别对应两和数据的存储结构：顺序存储结构和链式存储结构；顺序存储结构是指把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中；链式存储结构不要求必须相邻。

链式存储结构中的数据元素叫做结点，在结点中附近设地址域来存储与该结点相邻的结点的地址来实现结点之间逻辑关系；8．在软件设计中，抽象数据类型通常包括定义、表示和实现三部分9．算法：是指在有限的时间范围之内为解决某一问题而采取的方法和步骤的准确完整的描述，他是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算；10算法的特征：有穷性，确定性，可行性，输入，输出；算法+数据结构=程序；11．评价一个算法的主要标准：正确性，可读性，健壮性，运行时间，占用空间；健壮性要求算法要全面细致的考虑所有可能出现的边界情况和异常情况；实际上，算法的时间效率和空间效率经常是一对矛盾，相互抵触，我们要根据实际问题进行处理，有时要牺牲空间换取时间，有时要牺牲时间换取空间。

第1章 绪论

第1章 绪论


ADT 有两个重要特征:
数据抽象 用ADT描述程序处理的实体时，
强调的是其本质的特征 其所能完成的 本质的特征、其所能完成的 本质的特征 功能以及它和外部用户的接口 外部用户的接口（即外界 功能 外部用户的接口 外界 使用它的方法） 使用它的方法 外部特性和其内部 数据封装 将实体的外部特性和其内部 实现细节分离，并且对外部用户隐藏 对外部用户隐藏 实现细节分离 其内部实现细节
抽象数据类型需要通过固有数据 固有数据 类型(高级编程语言中已实现的数据 类型 类型)来实现。 类C语言详见10-11页。
例如，对以上定义的复数
// -----存储结构的定义 存储结构的定义
typedef struct { float realpart； float imagpart； }complex；
数据的存储结构 存储结构
—— 逻辑结构在存储器中的映像 映像 “数据元素”的映像 ？ “关系”的映像 ？
数据元素的映像方法： 数据元素的映像方法：
用二进制位(bit)的位串表示数据元素 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2
数据结构: 数据结构 问题的数学模型
例如: 例如 数值计算的程序设计问题 结构静力分析计算 ─━ 线性代数方程组 全球天气预报 ─━ 环流模式方程 (球面坐标系)
非数值计算的程序设计问题
例一: 整数中的最大值 例一 求一组(n个)整数 整数
比较两个数的大小” 比较两个数的大小 算法: ? 基本操作是“比较两个数的大小
（ ） 关系的映像方法： 关系的映像方法：表示<x, y>的方法） 顺序映像
以相对的存储位置表示后继关系 例如: 例如:令 y 的存储位置和 x 的存储位置 之间差一个常量 C 而 C 是一个隐含值，整个存储结构中只 整个存储结构中只 含数据元素本身的信息

数据结构重点

第一章：绪论：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计;：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称;数据元素：表示一个事物的一组数据称作是一个数据元素,是数据的基本单位;数据项：是数据元素中有独立含义的、不可分割的最小标识单位;数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作;数据的逻辑结构指数据元素之间的逻辑关系,用一个数据元素的集合定义在此集合上的若干关系来表示,数据结构可以分为三种：线性结构、树结构和图;：数据元素及其关系在计算机中的存储表示称为数据的存储结构,也称为物理结构;数据的存储结构基本形式有两种：顺序存储结构和链式存储结构;：算法：一个算法是一个有穷规则的集合,其规则确定一个解决某一特定类型问题的操作序列;算法规则需满足以下五个特性：输入——算法有零个或多个输入数据;输出——算法有一个或多个输出数据,与输入数据有某种特定关系;有穷性——算法必须在执行又穷步之后结束;确定性——算法的每个步骤必须含义明确,无二义性;可行性——算法的每步操作必须是基本的,它们的原则上都能够精确地进行,用笔和纸做有穷次就可以完成;有穷性和可行性是算法最重要的两个特征;：算法与数据结构：算法建立数据结构之上,对数据结构的操作需用算法来描述;算法设计依赖数据的逻辑结构,算法实现依赖数据结构的存储结构;：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求,这是算法设计的基本目标;健壮性：即使输入数据不合适,算法也能做出适当的处理,不会导致不可控结高时间效率：算法的执行时间越短,时间效率越高; 果;高空间效率：算法执行时占用的存储空间越少,空间效率越高;可读性：算法的可读性有利于人们对算法的理解;：度量算法的时间效率,时间复杂度,课本39页;：递归定义：即用一个概念本身直接或间接地定义它自己;递归定义有两个条件：至少有一条初始定义是非递归的,如1=1.由已知函数值逐步递推计算出未知函数值,如用n-1定义n;第二章：线性表线性表：线性表是由nn>=0个类型相同的数据元素a0,a1,a2,…an-1,组成的有限序列,记作：Linear List = a0,a1,a2,…an-1其中,元素ai可以是整数、浮点数、字符、也可以是对象;n是线性表的元素个数,成为线性表长度;若n=0,则LinearList为空表;若n>0,则a0没有前驱元素,an-1没有后继元素,ai0<i<n-1有且仅有一个直接前驱元素ai-1和一个直接后继元素ai+1;线性表的顺序存储是用一组连续的内存单元依次存放线性表的数据元素,元素在内存的物理存储次序与它们在线性表中的逻辑次序相同;线性表的数据元素数据同一种数据类型,设每个元素占用c字节,a0的存储地址为Loca0,则ai的存储地址Locai为：Locai = Loca0+ ic数组是顺序存储的随机存储结构,它占用一组连续的存储单元,通过下标识别元素,元素地址是下标的线性函数;：顺序表的插入和删除操作要移动数据元素;平均移动次数是属数据表长度的一半;课本第50页：线性表的链式存储是用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻,必须采用附加信息表示数据元素之间的顺序关系;它有两个域组成：数据域和地址域;通常成为节点;课本第55页及56页单链表课本56页单链表的遍历：Node<E> p = head; whilep=null{ 访问p节点；p = ;}单链表的插入和删除操作非常简便,只要改变节点间的链接关系,不需移动数据元素;单链表的插入操作：1：空表插入/头插入2中间插入/尾插入ifhead == null Node<E> q = new Node<E>x;{ head = new Node<E>x; = ;}else{ = q;Node<E> q=new Node<E>x; 中间插入或尾插入都不会改变单表= head; 的头指针head;head = q;}单链表的删除操作：头删除：head = ;中间/尾删除：if=null{ =循环单链表：如果单链表最后一个节点的next链保存单链表的头指针head值,则该单链表成为环形结构,称为循环单链表;课本67若rear是单链表的尾指针,则执行=head;语句,使单链表成为一条循环单链表;当==head时,循环单链表为空;：双链表结构：双链表的每个结点有两个链域,分别指向它的前驱和后继结点,当==null时,双链表为空;设p指向双链表中非两端的某个结点,则成立下列关系：p=;双链表的插入和删除：1插入2删除q=new DLinkNodex；= ;=; =p; if=null{= q;=q; .prev = ;}循环双链表：当==head且==head时,循环双链表为空;第三章：栈和队列栈：栈是一种特殊的线性表,其中插入和删除操作只允许在线性表的一端进行;允许操作的一端称为栈顶,不允许操作的一端称为栈底;栈有顺序栈和链式栈;栈中插入元素的操作称为入栈,删除元素的操作称为出栈;没有元素的中称为空栈;栈的进出栈顺序：后进先出,先进后出;及75页的思考题;：队列：队列是一种特殊的线性表,其中插入和删除操作分别在线性表的两端进行;向队列中插入元素的过程称为入队,删除元素的过程称为出对,允许入队的一端称为队尾,允许出队的一端称为对头;没有元素的队列称为空队列;队列是先进先出;第四章：串：串是一种特殊的线性表,其特殊性在于线性表中的每个元素是一个字符;一个串记为：s=“s0s1s2…sn-1” 其中n>=0,s是串名,一对双引号括起来的字符序列s0s1s2…sn-1是串值,sii=0,1,2,…n-1为特定字符集合中的一个字符;一个串中包含的字符个数称为串的长度;长度为0的串称为空串,记作“”,而由一个或多个空格字符构成的字符串称为空格串;子串：由串s中任意连续字符组成的一个子序列sub称为s的子串,s称为sub 的主串;子串的序号是指该子串的第一个字符在主串中的序号;串比较：两个串可比较是否相等,也可比较大小;两个串子串相等的充要条件是两个串子串的长度相同,并且各对应位置上的字符也相同;两个串的大小由对应位置的第一个不同字符的大小决定,字符比较次序是从头开始依次向后;当两个串长度不等而对应位置的字符都相同时,较长的串定义为较“大”;第五章：数组和广义表：数组是一种数据结构,数据元素具有相同的数据类型;一维数组的逻辑结构是线性表,多维数组是线性表的扩展;：一维数组：一维数组采用顺序存储结构;一个一维数组占用一组连续的存储单元;设数组第一个元素a0的存储地址为Loca0,每个元素占用c字节,则数组其他元素ai的存储地址Locai为：Locai= Loca0+ic数组通过下标识别元素,元素地址是下标的线性函数;一个下标能够唯一确定一个元素,所划给的时间是O1;因此数组是随机存取结构,这是数组最大的优点;：多维数组的遍历：有两种次序：行主序和列主序;行主序：以行为主序,按行递增访问数组元素,访问完第i行的所有元素之后再访问第i+1行的元素,同一行上按列递增访问数组元素;a00,a01,…a0n-1, a10,a11,…a1n-1,…am-10,am-11,…,am-1n-12列主序：以列为主序,按列递增访问数组元素,访问完第j列的所有元素之后再访问第j+1列的元素,同一列上按列递增访问数组元素;多维数组的存储结构：多维数组也是由多个一维数组组合而成,组合方式有一下两种;静态多维数组的顺序存储结构：可按行主序和列主序进行顺序存储;按行主序存储时,元素aij的地址为：Locaij= Loca00+in+jc按列主序存储时,Locaij= Loca00+jm+ic动态多维数组的存储结构;二维数组元素地址就是两个下标的线性函数;无论采用哪种存储结构,多维数组都是基于一维数组的,因此也只能进行赋值、取值两种存取操作,不能进行插入,删除操作;第六章：树是数据元素结点之间具有层次关系的非线性结构;在树结构中,除根以外的结点只有一个直接前驱结点,可以有零至多个直接后继结点;根没有前驱结点;树是由nn>=0个结点组成的有限集合树中元素通常称为结点;N=0的树称为空树；n>0大的树T；有一个特殊的结点称为根结点,它只有后继结点,没有前驱结点;除根结点之外的其他结点分为mm>=0个互不相交的集合T0,T1,T3……..,Tm-1,其中每个集合Ti0<=i<m本身又是一棵树,称为根的子树;树是递归定义的;结点是树大的基本单位,若干个结点组成一棵子树,若干棵互不相交的子树组成一棵树;树的每个结点都是该树中某一棵子树的根;因此,树是由结点组成的、结点之间具有层次关系大的非线性结构;结点的前驱结点称为其父母结点,反之,结点大的后继结点称为其孩子结点;一棵树中,只有根结点没有父母结点,其他结点有且仅有一个父母结点;拥有同一个父母结点的多个结点之间称为兄弟结点;结点的祖先是指从根结点到其父母结点所经过大的所有结点;结点的后代是指该结点的所有孩子结点,以及孩子的孩子等;结点的度是结点所拥有子树的棵数;度为0的结点称为叶子结点,又叫终端结点；树中除叶子结点之外的其他结点称为分支结点,又叫非叶子结点或非终端结点;树的度是指树中各结点度的最大值;结点的层次属性反应结点处于树中的层次位置;约定根结点的层次为1,其他结点的层次是其父母结点的层次加1;显然,兄弟结点的层次相同;树的高度或深度是树中结点的最大层次树;设树中x结点是y结点的父母结点,有序对x,y称为连接这两个结点的分支,也称为边;设X0,X1,….,Xk-1是由树中结点组成的一个序列,且Xi,Xi+10<=i<k-1都是树中的边,则该序列称为从X0到Xk-1的一条路径;路径长度为路径上的边数;在树的定义中,结点的子树T0,T1…..,Tm-1之间没有次序,可以交换位置,称为无序树,简称树;如果结点的子树T0,T1……,Tm-1从左到右是有次序的,不能交换位置,则称该树为有序树;森林是mm>=0棵互不相干的树的集合;给森林加上一个根结点就变成一棵树,将树的根节点删除就变成森林;二叉树的性质1：若根结点的层次为1,则二叉树第i层最多有2 的i-1次方i>=1个结点;二叉树的性质2：在高度为k的二叉树中,最多有2的k次方减一个结点;二叉树的性质3：设一棵二叉树的叶子结点数为n0,2度结点数为n2,则n0=n2+1;一棵高度为k的满二叉树是具有2的k次方减一个结点的二叉树;满二叉树中每一层的结点数目都达到最大值;对满二叉树的结点进行连续编号,约定根节点的序号为0,从根节点开始,自上而下,每层自左至右编号;一棵具有n个结点高度为k的二叉树,如果他的每个节点都与高度为k的满二叉树中序号为0~n-1的结点一一对应,则这棵二叉树为为完全二叉树;满二叉树是完全二叉树,而完全二叉树不一定是满二叉树;完全二叉树的第1~k-1层是满二叉树第k层不满,并且该层所有结点必须集中在该层左边的若干位置上;二叉树的性质4：一棵具有n个结点的完全二叉树,其高度k=log2n的绝对值+1二叉树的性质5：一棵具有n个结点的完全二叉树,对序号为i的结点,有若i=0,则i为根节点,无父母结点；若i>0,则i的父母结点的序号为i-1/2;若2i+1<n,则i的左孩子结点序号为2i+1；否则i无左孩子;若2i+2<n,则i的右孩子结点的序号为2i+2,否则i无右孩子;二叉树的遍历二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点,并且每个结点仅被访问一次;二叉树的三种次序遍历1：先根次序；访问根节点,遍历左子树,遍历右子树;2：中根次序；遍历左子树,访问右子树,遍历右子树;3：后根次序；遍历左子树,遍历右子树,访问根节点;先根次序遍历时,最先访问根节点；后根次序遍历时,最后访问根节点；中根次序遍历时,左子树上的结点在根节点之前访问,右子树上的结点在根节点之后访问;二叉树的插入和删除操作P147二叉树的层次遍历P149习题P167 6—10,6—19第七章图是由定点集合及顶点间的关系集合组成的一种数据关边系;顶点之间的关系成为边;一个图G记为G=V,E,V是顶点A的有限集合,E是边的有限集合;即V={A|A属于某个数据元素集合}E={A,B|A,B属于V}或E={<A,B>|A,B属于V且PathA,B}其中PathA,B表示从顶点A到B的一条单向通路,即PathA,B是有方向的;无向图中的边事没有方向,每条边用两个顶点的无序对表示;有向图中的边是有方向,每条边用两个顶点的有序对表示;完全图指图的边数达到最大值;n个顶点的完全图记为Kn;无向完全图Kn的边数为nn-1/2,有向完全图Kn的边数为nn-1;子图：设图G==V,E,G’=V’,E’,若V’包含于V且E’包含于E,则称图G’是G的子图;若G’是G的真子图;连通图：在无向图G中,若从顶点VI到Vj有路径,则称Vi和Vj是联通的;若图G 中任意一对顶点Vi和VjVi不等于Vj都是联通的,则称G为连通图;非连通图的极大联通子图称为该图的联通分量;强连通图：在有向图中,若在每一对顶点Vi和VjVi不等于Vj之间都存在一条从Vi到Vj的路径,也存在一条从Vi到Vj的路径,也存在一条从Vi到Vj的路径,则称该图的强连通图;非强连通图的极大强连通子图称为该图的强连通图分量;图的遍历遍历图是指从图G中任意一个顶点V出发,沿着图中的边前行,到达并访问图中的所有顶点,且每个顶点仅被访问一次;遍历图要考虑一下三个问题：指定遍历的第一个访问顶点由于一个顶点可能与多个顶点相邻,因此要在多个邻接顶点之间约定一种访问次序;由于图中可能存在回路,在访问某个顶点之后,可能沿着某条路径又回到该顶点;深度优先搜索图的深度优先搜索策略是,访问某个顶点v,接着寻找v的另一个未被访问的邻接顶点w访问,如此反复执行,走过一条较长路径到达最远顶点；若顶点v没有未被访问的其他邻接顶点,则回到前一个被访问顶点,再寻找其他访问路径;图的深度优先搜索遍历算法P188联通的无回路的无向图,简称树;树中的悬挂点又成为树叶,其他顶点称为分支点;各连通分量均为树的图称为森林,树是森林;由于树中无回路,因此树中必定无自身环也无重边否则他有回路若去掉树中的任意一条边,则变成森林,成为非联通图；若给树加上一条边,形成图中的一条回路,则不是树;P191生成树和生成森林：一个连通无向图的生成树是该图的一个极小联通生成子图,它包含原图中所有顶点n个以及足以构成一棵树的n-1条边;一个非联通的无向图,其各连通图分量的生成图组成该图的生成森林;图的生成图或生成森林不是唯一的,从不同顶点开始、采用不同遍历可以得到不同的生成树或森林;在生成树中,任何树中,任何两个顶点之间只有唯一的一条路径;第八章折半查找算法描述P206,P207二叉排序树及其查找：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树：每个结点都有一个作为查找依据的关键字,所有结点的关键字互不相同;若一个结点的左子树不空,则左子树上所有结点的关键字均小于这个节点的关键字；每个结点的左右子树也分别为二叉排序树;在一棵二叉排序树中,查找值为value的结点,算法描述如下：从根结点开始,设p指向根结点将value与p结点的关键字进行比较,若两者相等,则查找成功；若value值较小,则在p的左子树中继续查找；若value值较大,则在p的右子树中继续查找;重复执行上一步,直到查找成功或p为空,若p为空,则查找不成功;习题8-6第九章直接插入排序算法描述：p228冒泡排序算法的描述：p232快速排序算法描述p233直接选择排序算法描述p236直接选择排序算法实现如下：Public static void selectSortinttable{forint i=0;i<;i++{int min=I;forint j=i+1;j<;j++{iftablej<tableminmin=j;ifmin=i{int temp=tablei;tablei==tablemin;tablemin=temp;}}}}堆排序是完全二叉树的应用,是充分利用完全二叉树特性的一种选择排序;堆定义：设n个元素的数据序列{k0,k1,;;;;kn-1},当且仅当满足下列关系k1<=k2i+1且ki<=k2i+2 i=0,1,2,3,….,n/2-1或ki>==k2i+1且ki>=2i+2i=0,1,2,3,…..n/2-1时,序列{k0,k1…….kn-1}称为最小堆或最大堆;将最小大堆看成是一颗完全二叉树的层次遍历序列,则任意一个结点的关键字都小于等于大于等于它的孩子节点的关键字值,由此可知,根结点值最小大;根据二叉树的性质5,完全二叉树中的第i0<=i<n个结点,如果有孩子,则左孩子为第2i+1个结点,右孩子为第2i+2个结点;。

数据结构(一)绪论


1.3 算法和算法分析 1.3.1 算法：
是对特定问题求解步骤的一种描述，是指令的有限序列，其中 每一条指令表示一个或多个操作。 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每 一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义 性。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通 过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特 定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着 某些特定关系的量。
数据元素:
是数据（集合）中的一个“个体” 是数据结构中讨论的基本单位
数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常 分为四类基本结构： 一、集合 结构中的数据元素除了同属于一 种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一 对一的关系。 三、树型结构 结构中的数据元素之间存在一 对多的关系。 四、图状结构或网状结构 结构中的数据元素 之间存在多对多的关系。
求整数n（n>=0）阶乘的算法如下，其时间复杂度， int fact（int n） {if （n<=1） return 1； return n*fact（n-1）； }
A ) O(log2 n) B) O(n)
C)
O(n （2分）
作业：
１. 计算时间复杂度 sum=1; for(i=0;sum<n;i++) sum+=i; 2.设给定若干n值，比较两函数n2和50nlog2n的增长 趋势，并确定在什么范围内，函数n2的值大于
例４ for(i=1;i<=n;++i) for(j=1;j<=n;++j) {++x;s+=x;} 语句频度为：n2 其时间复杂度为：O(n2) 即时间复杂度为平方阶。

数据结构1

第 1 章 绪 论1.1 数据结构的兴起和发展一、数据结构起源于程序设计。

·程序设计的新问题：应如何组织待处理的数据以及数据之间的关系（结构）。

·70年代初，数据结构作为一门独立的课程开始进入大学课堂。

二、数据结构随着程序设计的发展而发展。

程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：三、数据结构的发展并未终结。

1． 数据结构将继续随着程序设计的发展而发展；2． 面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在探索中。

应用领域：科学计算；程序设计面向计算机 应用领域：科学计算与非数值处理；算法＋数据结构=程序 应用领域：更多地应用于非数值处理；（算法＋数据结构）=程序1.2 数据结构的研究对象例1-1 学籍管理问题例1-2 人——机对弈问题例1-3 教学计划编排问题表1-1 学生学籍登记表 (a) 井字棋的一个格局 (b) 对弈树的局部 图1-2 对弈问题中格局之间的关系1.3 数据结构的基本概念1.3.1 数据结构1. 数据：在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。

2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

构成数据元素的不可分割的最小单位称为数据项。

3. 数据对象：是具有相同性质的数据元素的集合，是数据的子集。

4. 数据结构：是指相互之间存在一定关系的数据元素的集合。

按照视点的不同，数据结构分为逻辑结构和存储结构。

数据的逻辑结构是指数据元素之间逻辑关系的整体。

根据数据元素之间逻辑关系的不同，数据结构分为四类：⑴集合数据元素之间的关系是。

⑵线性结构数据元素之间的关系是。

⑶树结构数据元素之间的关系是。

⑷图结构数据元素之间的关系是。

数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。

有两种存储结构：顺序存储结构和链接存储结构。

数据结构讲义第一章绪论


注：一个抽象数据类型确定了一个模型，但将模型的实 现细节隐藏起来；它定义了一组运算，但将运算 的实现过程隐藏起来。
用抽象数据类型的概念来指导问题的求解过程：
数学模型 非形式算法
抽象数据模型 伪语言程序
数据结构 可执行程序
§ 1.3 抽象数据类型
ADT的定义格式 ADT <ADT名> { 数据对象:<数据对象的定义> 结构关系:<结构关系的定义> 基本操作:<基本操作的定义> }ADT <ADT名>
初始化数据结构；
Destroy( )
销毁数据结构；
Get (i )
查找第 i 个元素；
Insert (i , b ) 在第 i 个位置插入元素 b ；
Delete( i )
删除第 i 个元素；
Traverse( )
遍历整个数据结构
§ 1.3 抽象数据类型
用C语言实现抽象数据类型ADT 用标准C语言表示和实现ADT描述时，主要
§ 1.2 数据结构的基本概念
数 据：描述客观事物的数字、字符以及一切 能够输入到计算机中，并且能够被计 算机程序处理的符号的集合。
数据是一个广义的概念，可以指普通的数据 （可参加算术运算），也可以指符号（源程序、 产品名称等）或数字化了的声音、图形、图像等。
§ 1.2 数据结构的基本概念
数据元素：数据(集合)中的一个个"个体"，是组 成数据的"基本单位"。
a2 d4 d1
a1 d1 d2
list
a1
a2
a4 d5 d3
a3 d3 … d4
a3
…
a30 ∧
§ 1.3 抽象数据类型

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

态）。
（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)。

1-2-2 实例分析
例 1-4 复数关系的定义。 数据结构： Complex=(C,R)。 其中，C 是两个实数集合 {c1,c2}；R 是定义在 C 上的一种关系，即 R={P}={<c1,c2>}。其 中，序偶< c1,c2>中的 c1 表示复数的实部，c2 表示复数的虚部。 例 1-5 事务管理程序中的课题小组信息的数据结构。假设 1 位老师带 1~3 名研究生，1 位研究生带 1~6 位学生，则数据结构 如下： Group=(P,R)。 其中，P={T,G1,…,Gn,S11,… Snm,1<=n<=3, 1<= m<=2} R={R1, R2} R1={<T, Gi>|1<=i<=n,1<=n<=3} R2={<Gi,Sij>|1<=i<=n, 1<=j<=m, 1<=n<=3, 1<=m<=2}
数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班
课程导入
课程性质： 专业必修课 总学时数： 20*3=60 学时 上机学时： 18*2=36 学时 假设前提： 已有程序设计基础（C/C++基础，尤其是 C 语言程序设计基础） 学习目标： 培养数据抽象能力(Data Abstraction Ability) 。 注：C 程序设计 课则是培养结构化程序设计的能力。 具体涉及两个方面内容的学习和训练： 1) 学会分析研究计算机加工数据结构的特征，以便学会 针对不同的应用问 题，选择合适的逻辑结构、存储结构及相应的算法描述 。并做相应的 时间复杂 度和空间复杂度的分析。 2) 复杂程序设计方法的训练过程。学会将问题求解的程序设计成结构清楚、 正确、符合软件工程规范的系统。 学习方法： 勤奋练习，积极上机实践。( 熟悉各种数据结构的基本思想和算 法描述，并不断尝试结合教材内容和课外训练的数据抽象能力的培养) 教学步骤：整体上分为两个部分内容，一是数据结构的基本思想、方法与应 用技巧，二是上机实践。 具体内容： 第一章 绪论 第二、三、四、五、六、七章 基础(强调从 ADT 的角度进行描述的思想) 第八章 OS/Compiler 中的动态存储管理技术 (×) 第九、十章 查找/内排序 第十一章 外排序(×) 第十二章 文件结构(×) 注：由于学时数的限制，第八章、第十一章和第十二章暂时不做要求。其它 章节中，带**号的章节不做要求或不做考试要求。
作者：冯山
数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班
(6) 数据元素之间关系的两种映射方法 顺序映射 ----顺序存储结构。 借助元素在存储器中存储的相对位置关系来表示数据元素 之间的逻辑关系。 非顺序映射 ----链式存储结构。 借助指示元素存储地址的指针来表示元素之间的逻辑关 系。 注：数据的逻辑结构与物理结构是紧密相关的。一般来将，任何一个算法的设计取决 于其数据的逻辑结构，而算法的实现取决于其数据的存储结构。 (7) 虚拟存储结构 ----存储结构的基于高级程序设计语言的描述方法 通过高级语言的数据类型来描述。 DS C 语言 OS Hardware 物理存储结构 虚拟存储结构 例如：一维数组用于描述顺序存储结构；指 针用于描述链式存储结构；struct, union 等用来表 示复杂问题的数据结构。 DS 中的虚拟存储结构在计算机系统中的层 次位置如图 1-3 所示。
课程材
《数据结构》 ，严蔚敏，吴伟民 编著，北京：清华大学出版社，2003 年 3 月
参考书目
(1) 《计算机算法：设计和分析引论》 ，[美] S 巴斯, 朱洪 等译，上海：复旦 大学出版社，1985 (2) 《Data Structures with C++》,[美] William Ford, William Topp, 北京：清华 大 学 出 版 社 ， Printice-Hall International, inc. 1998 年 4 月 ， ISBN 7-302-02413-8 (3) 《数据结构、算法与应用----C++语言描述》 ，[美] Sartaj Sahni 著，汪诗林，
作者：冯山
数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班
结构就是其检索问题中的基本数据关系的数学模型 ( 此为 线性的结构关系模型 ) 。( 见教材 P1-2) 例 1-3 人机对弈问题。 其对弈策略、规则驱动、棋盘状态、前景预测方法等模型的建立，同时，棋盘状态描述 模型是对弈问题的关键性数据描述模型， 但棋局之间的关系往往不是线性的， 需要用非数值 型结构来描述。例如：#字游戏问题( 见教材 P2) 。需要用到所谓“树结构”来描述这些棋盘 状态之间转换过程。 例 1-4 多叉路口交通灯的管理问题( 在多叉路口需要设多少颜色的灯，使得车辆之间互 不碰撞，同时车流量最大) (见教材 P2-3) 对图的顶点作图的问题。 与此相关的还有如哥黎斯堡七桥问题、逻辑电路设计问题等，用传统的数学模型是无法 描述的。必须用新型的所谓“图结构” 进行描述。
1-1 什么是数据结构？
Data Structure (DS): Data---- (1) facts; (2) Information prepared for or stored by a computer; Structure---- way in which something is put together, organized, built, etc.
1-1-1 不同问题的数据结构模型构建实例分析
用计算机解决问题的步骤： 抽象其数学模型求解该模型的算法编制程序 测试或调 试 得解 (1) 对数值计算问题 例 1-1 求解梁架结构中应力的数学模型 ；预报人口增长的微分方程模型 。 其关键在于分析问题，提取或寻找对象之间的结构关系，然后用数学语言加以描述。 (2) 对无法用数学模型描述的非数值计算问题 其数学模型集中在数据结构的建立中。 例 1-2 图书馆书目检索系统自动化问题。 按书名的索引表、按作者名的索引表、按分类号的索引表、按登录号排列的书目表表示
1-2-3 其它概念与术语
(1) 逻辑结构 (Logical Structure)--- 描述数据元素之间的逻辑关系的结构。 (2) 物理结构 (Physical Structure)---- 描述数据元素在计算机中的实际存储映射关系的 结构，又称存储结构。 存储结构一般包含两个部分的内容 ：一是数据元素的存储，二是数据元素之间关系的 存储。 (3) 容量单位问题 Byte, bit, KB, MB, GB, TB (4) 数据域 (Data Field)----当数据元素由若干个数据项组成时，各数据项位串被称为数 据域。 (5) 数据节点 (Node)----既数据元素。
1-2 数据结构中涉及的基本概念与术语 1-2-1 基本概念和术语
(1) Data----(facts/information)能被计算机处理的符号总称,是待加工的 “原料 ” 例如： 求解代数方程组时的 Data 为 integer/real 型的系数或根等； 编译器的 Data 为：程序代码或字符序列； 文字编辑器的 Data 为：字符、图形等。 (2) Data Element----对数据进行处理的基本单位 例如： 前述的棋盘之格局；图中的顶点等。 注：数据元素一般由若干数据项 (Data Item)组成。
习题及实验参考书
(1) 《数据结构实验教程》(C 语言版)，王玲 主编，成都：四川大学出版社， 2003 年 7 月 (2) 《数据结构习题集》(C 语言版)，严蔚敏，吴伟民 编著，北京：清华大 学出版社，2003 年 1 月
第一章 绪论
需要对程序的处理对象进行组织研究的两大主要原因： 一是 计算机领域的渗透早已使其应用不再局限于早期的科学计算领域 其加工处理对 象由纯粹的数值类发展到具有一定结构的数据类型 ，如字符、表、图形、图像、声音等， 使得程序设计活动面临了许多新的问题需要解决 。 二是 要编写出好的程序系统 ，人们发现，必须要对待处理对象的数据特性、各处理对象 之间的关系进行分析、组织 ，使编写出的程序能够有效地处理和解决它们。 它们构成了数据结构的研究动力和研究内容。
1-1-2 DS 课程的研究内容及课程历史
DS 研究内容： 研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系 和操作的一门学科课程。 DS 作为一门独立课程的发展历史： 1968 年，DS 与图论、表、树为“同义语” 。后来，扩充到了网络、集合代数、格、关系 等(它们又构成了“离散数学”的基础内容)。再后来，将大型数据库系统中的文件管理以及 内 存管理等技术也纳入了本课程中来。 《计算机程序设计艺术》(第一卷) ，Donald Knuth 1 (Turing 奖获得者)（开创 了最初的 DS 体系， 是第一本系统阐述数据的逻辑结构、 存储结构及其操作的著作） 目前，DS 是许多专业的选修或必修课。 DS 课程的地位(综合性非常强)( 见教材 P4 图 1.4)：界于数学、计算机软件和 计算机硬件之间的核心课程。既是一般程序设计的基础，更是编译程序、OS、DBS 及其它大 型的系统程序和应用程序设计与实现的重要基础 。 发展方向： 1) 向各专门领域中的特殊问题之数据结构研究发展； 2) 从 ADT 观点来研究。
1
作者：冯山
数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班
又如： 前述图书书目中的书卡数据 由作者姓名、书名、书号 等数据项 构成。 (3) Data Object----相同性质的数据元素之集合 例如： 整数数据对象即集合 N {0,1,2,...} ;字母字符对象即 C {' A' , ' B' ,...} ；计 算机信息与计算科学专业 2003 级学生对象即全体该班的学生集合等。 (4) Data Structure----相互之间存在某种特定关系的数据元素之集合 (从操作对象抽象出 来的数学模型 ) 注 1 ：DS 中的数据元素不是孤立存在的； 注 2 ：数据元素之间的关系即可称为“结构” ； 注 3 ：数据元素之间的关系有 4 种基本结构： 集合(set)关系----无序的松散关系； 线性(linear)关系----一一对应关系(one-one)； 树 (tree)关系 ----一对多关系 (one-many)； 图 (graph)关系或者网(net)关系 ----多对多关系(many-many)。 （如教材 P5 图 1.5 所示） 注 4 ： DS 的形式定义为： D_S=(D,S)。其中， D 为数据对象有限集合， S 为 D 上的关 系有限集合。 注 5 ：一般而言， DS 要表达的是一组具 有相同结构的数据对象之值的集合。