文档介绍：第二部分数据结构
电子工程学院
2
数据结构的教学目的和要求
掌握线性表、栈、队列、串、数组、树等数据的逻辑结构、存储结构及有关的算法,以及数据的查找和排序方法。
使用类C语言描述算法,能够分析算法和设计算法。
数据结构的学习过程也是较复杂程序设计的训练过程。在编写程序解决实际问题时,应当采用规范的算法,并且按照软件开发方法所要求的模块独立性高的原则,设计出高质量的程序。
电子工程学院
3
数据结构目录
数据结构概述
线性表
栈
队列
串
数组
树
图
查找
排序
电子工程学院
4
一、数据结构概述
主要内容:
1. 数据结构的基本概念和术语
2. 算法的概念
3. 算法的时间特性及时间复杂度的分析
4. 算法的空间特性及空间复杂度的分析
电子工程学院
5
数据结构的基本概念和术语
数据:数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。例如:一个二维表是一个数据。
数据元素:数据的基本单位。数据元素也称为元素、结点、顶点、记录。例如:二维表中的某一行是一个数据元素。
数据项:一个数据元素可以由若干个数据项组成,数据项是具有独立含义的,不可再分割的最小标识单位。例如:二维表中某一行的某一列是一个数据项。
电子工程学院
6
数据结构:数据之间的相互关系,即数据的组织形式。
数据结构所研究的主要内容包括以下三个方面:
(1)数据的逻辑结构——数据元素之间的逻辑关系
(2)数据的存储结构——数据结构在计算机中的存储方法
(3)数据的运算——对数据施加的操作
电子工程学院
7
数据类型:确定了一个值域以及对该类型数据可以进行的操作。按“值”是否可分解,可以将数据类型划分为两类:
(1)原子类型,其值不可分解。
如C语言中的基本类型(整型、实型、字符型等)、指针类型。
(2)结构类型,其值可分解为若干个成分。
如数组、结构体等类型的数据还可以进一步分解。
电子工程学院
8
数据的逻辑结构分为两大类:
(1)线性结构。其逻辑特征为:若数据结构是非空集,第一个结点没有直接前趋结点,最后一个结点没有直接后继结点,其余结点都有一个直接前趋结点和一个直接后继结点。线性表、栈、队列、串等都是线性结构。
(2)非线性结构。其逻辑特征为:一个结点可能有多个直接前趋和直接后继结点。树、图等属于非线性结构。
电子工程学院
9
数据的存储结构可以有以下四种基本的存储方法:
(1)顺序存储方法。结点间的逻辑关系由存储单元的邻接关系来体现。
(2)链接存储方法。通过指示元素存储地址的指针表示数据元素之间的逻辑关系,即逻辑上相邻的结点在物理位置上不一定相邻。
(3)索引存储方法。在存储结点的同时,还建立附加的索引表,索引表中的每一项称为索引项(索引项包括:关键字,地址),关键字是能够唯一标识一个结点的那些数据项。
若每个结点在索引表中都有一个索引项,称为稠密索引;若一组结点在索引表中对应一个索引项,称为稀疏索引。
电子工程学院
10
(4)散列存储方法。根据结点的关键字直接计算出该结点的存储地址。
上述四种基本的存储方法,既可以单独使用,也可以组合起来对数据结构进行存储。例如采用拉链法表示散列表,是顺序存储方法与连接存储方法的组合。
同一种逻辑结构采用不同的存储方法,可以得到不同的存储结构。例如线性表可以采用顺序存储结构(顺序表)和链式存储结构(链表)。