文档介绍：数据结构与算法
2017年6月28日
数据结构讲义
2
算法及其特性
算法(Algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。
一个算法应该具有下列特性:
⑴有穷性。一个算法必须在有穷步之后结束,即必须在有限时间内完成。
⑵确定性。算法的每一步必须有确切的定义,无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。
⑶可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。
⑷输入。一个算法具有零个或多个输入,这些输入取自特定的数据对象集合。
⑸输出。一个算法具有一个或多个输出,这些输出同输入之间存在某种特定的关系。
2017年6月28日
数据结构讲义
3
算法的性能分析
时间复杂度、空间复杂度:也成为时间性能和空间性能,是对某个算法的时间效率和空间效率的度量。
时间复杂度
将一个算法转换成程序并在计算机上执行时,其运行所需要的时间取决于下列因素:
空间复杂度:
一个算法的空间复杂度(plexity)是指算法运行从开始到结束所需的存储量。
2017年6月28日
数据结构讲义
4
有关概念和术语
1、数据项
2、数据元素
3、数据对象
4、数据结构
数据结构(Data Structure)是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中,数据元素之间都不会是孤立的,在它们之间都存在着这样或那样的关系,这种数据元素之间的关系称为结构。
根据数据元素间关系的不同特性,通常有下列四类基本的结构:
⑴集合结构。⑵线性结构。⑶树结构。⑷图结构。
2017年6月28日
数据结构讲义
5
(a)集合结构
(b)线性结构
(c)树结构
(d)图结构
图1. 5 四类基本结构的示意图
。
2017年6月28日
数据结构讲义
6
数据结构课程集中讨论软件开发过程中的设计阶段、同时涉及编码和分析阶段的若干基本问题。此外,为了构造出好的数据结构及其实现,还需考虑数据结构及其实现的评价与选择。因此,数据结构的内容包括三个层次的五个“要素”。
2、数据结构课程的内容
2017年6月28日
数据结构讲义
7
线性表的定义
线性表是线性结构的一般形式。
线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的,或者说线性表是由同一类型的数据元素构成的线性结构。
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列,通常记为:
(a1,a2,… ai-1,ai,ai+1,…an)
2017年6月28日
数据结构讲义
8
(a1,a2,… ai-1,ai,ai+1,…an)
其中n为表长, n=0 时称为空表。表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋,ai+1 称为 ai 的直接后继。就是说:对于ai,当 i=2,...,n 时,有且仅有一个直接前趋ai-1,当i=1,2,...,n-1 时,有且仅有一个直接后继ai+1,而 a1是表中第一个元素,它没有前趋,an是最后一个元素无后继。
需要说明的是:ai为序号为i的数据元素(i=1,2,…,n),通常我们将它的数据类型抽象为datatype,datatype根据具体问题而定,如在学生情况信息表中,它是用户自定义的学生类型; 在字符串中,它是字符型;等等。
2017年6月28日
数据结构讲义
9
线性表的基本运算
⑴线性表初始化:Init_List(L)
⑵求线性表的长度:Length_List(L)
⑶取表元:Get_List(L,i)
⑷按值查找:Locate_List(L,x)
⑸插入操作:Insert_List(L,i,x)
⑹删除操作:Delete_List(L,i)
线性表的顺序存储是指在内存中用地址连续的一块存储空间依次顺序存放线性表各元素,用这种存储形式存储的线性表称其为顺序表。
因为内存的地址空间是一维线性空间,因此顺序表的存储特点是:用物理上的相邻实现逻辑上的相邻。
2017年6月28日
数据结构讲义
10
⒉插入运算
(1) 运算说明:
线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素。
插入前:(a1, a2, ... , ai-1, ai , ai+1 , ... , an)
插入后:(a1, a2, ... , ai-1, x, ai, ai+1 , ... , an )
其中:1≤i≤n+1,n是原来的表长。
(3) 本算法中注意以下问题:
①顺序表中数据