第1章数据结构与算法.docx
- 文档编号:2015927
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:44
- 大小:590.28KB
第1章数据结构与算法.docx
《第1章数据结构与算法.docx》由会员分享,可在线阅读,更多相关《第1章数据结构与算法.docx(44页珍藏版)》请在冰点文库上搜索。
第1章数据结构与算法
第一章数据结构与算法
1.1.1算法的基本概念
算法是指解题方案的准确而完整的描述。
是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
对于一个问题,如果可以通过一个计算机程序,在有限的存储空间内运行有限长的时间而得到正确的结果,则称这个问题是算法可解的。
但算法不等于程序,也不等于计算方法。
程序的编制不可能优于算法的设计。
1.算法的基本特征
(1)可行性:
算法中要执行的每一个步骤都可以在有限时间内完成,且正确,否则是不会得到满意结果的。
N=-10;
for(k=1;k<=n;k++)
c=c+1;
(2)确定性:
算法的确定性,是指算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。
X=a·b/c·d
X=a·b/(c·d)
X=a·(b/c)·d
(3)有穷性:
算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。
算法的有穷性还应包括合理的执行时间的含义。
for(k=1;k<=n;k++)
c=c+1;
下例是无限循环:
for(k=1;k<=-10;k++)
c=c+1;
(4)拥有足够的情报:
一个算法是否有效,还取决于为算法所提供的情报是否足够。
2,算法的基本要素
一个算法通常由两种基本要素组成:
一是对数据对象的运算和操作,二是算法的控制结构。
(1)算法中对数据的运算和操作
计算机算法就是计算机能处理的操作所组成的指令序列。
一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。
计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列。
程序:
是使用某种程序设计语言对一个算法或多个算法的具体实现。
在一般的计算机系统中,基本的运算和操作有以下四类:
①算术运算:
主要包括加、减、乘、除等运算。
②逻辑运算:
主要包括“与”、“或”、“非”等运算。
⑧关系运算:
主要包括“大于”、“小于”、“等于”、“不等于”等运算。
④数据传输:
主要包括赋值、输入、输出等操作。
描述算法工具:
如流程图,专门的算法描述语言,甚至用自然语言等来描述算法。
算法的主要特征着重于算法的动态执行,它区别于传统的着重于静态描述或按演绎方式求解问题的过程。
计算机算法则是使用一些最基本的操作,通过对已知条件一步一步的加工和变换,从而实现解题目标。
(2)算法的控制结构:
算法中各操作之间的执行顺序称为算法的控制结构
算法的控制结构给出了算法的基本框架,它不仅决定了算法中各操作的执行顺序,而且也直接反映了算法的设计是否符合结构化原则。
描述算法的工具通常有传统流程图、N—S结构化流程图、算法描述语言等。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
3.算法设计基本方法
(1)列举法,
列举法的基本思想是,根据提出的问题,列举所有可能的情况,并用问题中给定的条件检验哪些是需要的,哪些是不需要的。
列举法的特点是算法比较简单。
但当列举的可能情况较多时,执行列举算法的工作量将会很大。
(2)归纳法
归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。
归纳法要比列举法更能反映问题的本质,并且可以解决列举量为无限的问题。
归纳是一种抽象,即从特殊现象中找出一般关系。
归纳得到的结论还只是一种猜测,还需要对这种猜测加以必要的证明。
(3)递推
所谓递推,是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。
其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简而确定。
递推关系式往往是归纳的结果。
(4)递归
将问题逐层分解的过程,实际上并没有对问题进行求解,而只是当解决了最后那些最简单的问题后,再沿着原来分解的逆过程逐步进行综合,这就是递归的基本思想。
递归分为直接递归与间接递归两种。
如果一个算法P显式地调用自己则称为直接递归。
如果算法P调用另一个算法Q,而算法Q又调用算法P,则称为间接递归调用。
递推与递归的实现方法是大不一样的。
递推是从初始条件出发,逐次推出所需求的结果;而递归则是从算法本身到达递归边界的。
(5)减半递推技术
所谓分治法,就是对问题分而治之。
工程上常用的分治法是减半递推技术。
所谓“减半”,是指将问题的规模减半,而问题的性质不变。
所谓“递推”,是指重复“减半”的过程。
(6)回溯法
通过对问题的分析,找出一个解决问题的线索,然后沿着这个线索逐步试探,对于每一步的试探,若试探成功,就得到问题的解;若试探失败,就逐步回退,换别的路线再进行试探。
这种方法称为回溯法。
1.1.2算法复杂度
算法的复杂度主要包括时间复杂度和空间复杂度。
1.算法的时间复杂度·
所谓算法的时间复杂度,是指执行算法所需要的计算工作量。
一个程序在计算机上运算所消耗的时间主要取决下述因素:
(1)程序运行时所需要输入的数据总量消耗时间。
(2)对源程序进行编译所需要的时间。
(3)计算机执行每条指令所需要的时间。
(4)计算机关键指令重复执行的次数。
分析算法的工作量。
(1)平均性态
所谓平均性态分析,是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入,p(x)是x出现的概率(即输入为x的概率),t(x)是算法在输入为x时所执行的基本运算次数,则算法的平均性态定义为
A(n)=∑p(x)t(x)
当规模为n时,算法执行时所有可能输入的集合。
p(x)必须由经验或用算法中有关的一些特定信息来确定。
如果确定p(x)比较困难,则会给平均性态的分析带来困难。
(2)最坏情况复杂性(Worst-CaseComplexity)
所谓最坏情况分析,是指在规模为n时,算法所执行的基本运算的最大次数。
它定义为
w(n)=max{t(x)}
算法分析
x=y+10
x=y*y+100
可是,在算法分析时,我们无论是计算拿一个x都认为是“一个操作步骤”,这样做是为了突出分析的重点,忽略细节。
为此,我们引入语句频度的概念(frequencycount)。
所谓语句频度即为“操作步骤”或“语句”重复执行的次数。
为描述算法的时间复杂性,我们可以将复杂性用函数T(n)表示,n表示算法中处理数据对象的数量或问题的规模的度量,如一算法时间复杂性是:
T(n)=2n3+3n2+2n+1
当n足够大时,有T(n)≈2n3,或者g(n)=2n3
因为,当n足够大时,2n3的复杂度大大超过3n2+2n+1,或者说,T(n)数量级与n3数量级相同。
所以,当n足够大时,可以忽略复杂性函数中复杂性较低的部分,而只用复杂度高的部分表示。
为此,我们进而引入渐进符号“O”,用大写O字母表示函数T(n)的上限函数,即当n足够大时的函数,记为:
O(g(n))=O(n3)
下面给出几种典型的复杂性函数的表示(a,b,c为已知数):
线性函数:
O(g(n))=O(a*n+b)=O(n)
平方函数:
O(g(n))=O(a*n2+b*n)=O(n2)
指数函数:
O(g(n))=O(an+b*n2+c*n)=O(an)
常数函数:
O(g(n))=O(9+12)=O
(1)
对数函数:
O(g(n))=O((a*n*log2n+b*n)=O(n*log2n)
常数函数是指算法的复杂性与算法中处理数据对象的数量无关,比如,
T(n)=15
T(n)=20056
两个T(n)函数中,无论n的值如何,函数值始终为一常量,这时认为算法的复杂性是O
(1),注意,不是T(n)函数的常量值。
例如,两个n×n的矩阵相乘,其算法可描述如下:
voidmatrix-product(inta[][],intb[][],intc[][],intn);
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
}
重复次数
n+1
n(n+1)
n2
n2(n+1)
n3
再如,下面有三个简单的程序段。
(a)x=x+1;
(b)for(i=1;i<=n;i++)
{x=x+1;}
(c)for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{x=x+1;}
假定(a)中语句x=x+1不在任何的循环中,则语句频度为1,其执行时间是一个常数,因此,其时间复杂性是常量级,即O
(1)。
在(b)中,同一语句x=x+1执行了n次,其频度为n,其时间复杂性依赖于n,所以,时间复杂性为O(n)。
在(c)中,语句x=x+1执行了n*n次,频度为n2,其时间复杂性依赖于n2,因此,时间复杂性为O(n2)。
通常情况下:
无循环结构,时间复杂性为量,记为:
O
(1)
单循环结构,时间复杂性为量,记为:
O(n)
双循环结构,时间复杂性为量,记为:
O(n2)
三层循环结构,时间复杂性为量,记为:
O(n3)
2.算法空间复杂性
算法执行所需要的内存空间
空间复杂性的组成
1)程序空间
程序空间是指用来存储经过编译之后的程序指令所需的空间。
指令空间一般不是数据结构所讨论的问题。
2)数据空间
数据空间是指用来存储所有常量和变量所需要的空间。
数据空间分成两部分:
●存储常量和简单变量所需要的空间。
●存储复合变量所需要的空间。
这一部分空间又由两部分组成:
一是数据结构定义的数据元素信息本身存储所需存储空间,二是动态分配的空间时存储链接空间。
1.2数据结构的基本概念
定义:
数据结构就是研究计算机中大量数据存储的组织形式,并定义且实现对数据的相应的运算,以提高计算机的数据处理能力的一门科学。
数据结构相关事例
问题一:
电话号码簿的使用及字典的使用。
党政机关
7
7
省委
55
55
省委办公厅一处
88060001
大学
12
市委
127
省委办公厅二处
88060002
企业
25
区委
224
·
·
·
·
·
·
·
·
·
127
市委办公一处
85800203
市委办公二处
85800105
·
·
·
旅游
32
12
综合类大学
325
325
华中科技大学
87870001
理工大学
430
武汉大学
86880206
图1.1.1电话号码簿
问题二:
某省各城市之间要架设电话通信线路,要保证各城市间互通,又要使设成本最少。
就是数据结构中讨论的图结构的应用--最小生成树。
结构类型
数据结构中讨论的结构类型分为两个层面,一是逻辑层面的数据结构,简称逻辑结构;另一个是物理层面的数据结构,简称物理结构。
1.逻辑结构
逻辑结构描述数据元素与数据元素之间的关联方式,简称为关系,表示的是事物本身的内在联系。
逻辑结构又可以分为:
线性结构和非线性结构两大类。
线性结构的特点表现为,线性结构中数据元素之间的正逆关系都是“一对一”的。
线性结构又可再分为:
线性表、堆栈、队列等。
非线性结构的特点表现为:
数据元素不一定存在确定的前后次序,甚至是无序的,数据元素之间存在从属或互为从属的关系或离散关系。
非线性结构又可再分为树形结构、图状或网状结构、纯集合结构。
在树型结构中,数据元素之间存在着“一对多”的关系。
在图或网状结构中,数据元素之间存在着“多对多”的关系。
在纯集合结构中,数据元素具有“同属于一个集合”的关系。
2.存储结构
存储结构,是逻辑结构的数据元素在计算机的物理存储空间上地映象,映象不仅包含数据元素本身,而且包含着数据元素之间的关联方式,即关系的映象。
映象表现为两种方式:
顺序映象和非顺序映象。
1)顺序映象
顺序映象是指数据元素在一块连续地物理存储空间上存储,物理存储空间只用于存放数据元素本身,数据元素之间的关联以两个数据元素存储的相邻关系来表示或通过某个函数来表示。
或者说,利用数据元素在存储空间上的相对位置来表示数据元素之间的逻辑关系。
如一组成绩信息,每个数据由姓名和成绩两个数据项构成:
{{彭亮,97},{王明,95},{李智,90},{刘丹,88},{肖象,78}}
数据元素是按成绩从高至低的顺序排列,即按成绩从高至低关联,在物理存储空间上的存储映象如图1.2.2所示,
再如,有一个下三角矩阵:
5
4
3
2
1
0
0
0
0
0
1
0
0
0
0
A
2
0
0
0
C
B
3
0
0
F
E
D
4
0
J
I
H
G
5
在物理存储空间上存放为如图1.2.3所示,数据元素存储的空间是连续地,每个数据元素以相邻方式存储,数组元素按行优先法则存储。
如要查找第i行,第j列(1
F(i,j)=((i-1)*(i-2))/2+j
顺序映象的最大优点就是空间的利用率最高,但一旦要在中间插入数据元素或删除中间数据元素,就必须移动大量数据元素,这种运算在计算机中是相当耗时的。
2)非顺序映象
非顺序映象是指数据元素在物理存储空间上非连续地存储,物理存储空间不仅存放数据元素本身,而且为实现数据元素之间的关联,在每个数据元素存储的相邻空间中存储该数据元素关联的另一个或多个数据元素的起始地址。
也可以说数据元素之间的关系是由附加“链接或指针”来表示。
非顺序映象存储结构中,数据元素的逻辑结构一般在物理空间上不是以物理空间的相邻来表现,而是在每个数据元素本身所占用空间的相邻空间中,存放该数据元素所关联的另一个或多个数据元素的位置,通常将这个空间称为链地址空间。
最后一个数据元素的链地址空间指向空地址。
可以看出数据元素在物理存储上是离散的,且物理顺序不一定与逻辑顺序保持一致。
成绩信息的物理映象如图1.2.4
3.数据域和链接域
1)数据域
数据域是物理存储空间中存储数据元素中数据值的空间,如成绩数据问题中,存储姓名和成绩两个数据项,所占用的空间大小(字节数)依实际应用的数据元素中包含的信息量的大小而定。
2)链接域
链接域又称指针域,是非顺序存储映象时表示数据元素之间关系的地址存储空间,是额外的空间付出。
在顺序存储映象结构中,链接域是不存在的,数据元素之间关系是以物理存储的邻接方式隐含表示的。
1.3线性表及其存储结构
1.3.1线性表的基本概念
线性表是有限元素(e1,...,ei,...,en)的有序序列的集合。
其中n是有穷自然数,ei是表中的元素,每个元素具有相同的特性,表中元素占用空间大小相同(记为:
size),n是表的长度。
当n=0时,表为空;当n>0时,e1是第一个元素(前件),en是最后一个元素(后件)。
数据元素通常称为结构或记录类型。
而包含多个结构或记录的线性表也可以称为文件。
线性表是一种线性结构。
特征:
1)有且只有一个根结点e0,它无前件;
2)有且只有一个终端结点en,它无后件;
3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
1.3.2线性表顺序存储结构
在计算机中存放线性表,一种最简单的方法是顺序存储,也称为顺序分配。
线性表的顺序存储结构具有以下两个基本特点:
①线性表中所有元素所占的存储空间是连续的;
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的。
在线性表的顺序存储结构中,如果线性表中各数据元素所占的存储空间<字节数)相等,线性表中查找某一个元素是很方便的。
元素ei的地址则可以立即由下面公式求出。
location(ei)=location(e1)+(i-1)×size
线性表中第k个数据元素之后插入元素x运算
它是指在线性表的元素ek+1和元素ek之间插入一个新的元素x。
即要在元素ek+1的地方插入一个元素。
插入过程:
首先需要将元素ek+1及以后的所有元素都要向后移动一个元素的位置,移动以后,空出ek元素的存储空间才能存入新的元素x。
需要注意,实现元素的插入是有前提条件的,就是要求在线性表的元素en的后面还有空闲的存储单元可以使用,否则插入是无法进行的。
插入后线性表的长度加1。
线性表中删除第k个数据元素运算
一般说来,删除运算是指需要删除线性表中的第K个数据元素。
删除的办法是将ek后所有元素ek+1,…,en依次向前移动一个元素的位置,然后修改线性表的长度(减1)。
在顺序存储线性表的删除运算中,不用专门进行存储空间的释放,事实上,移动数据元素的同时,被删除元素的空间同时已被释放了,释放到线性表数据元素尾端,即线性表中删除前最后一个数据元素的空间。
线性表顺序存储方式下,由于相邻元素之间是紧邻的,而无可利用的“空闲”空间。
因此,进行元素的插入或删除运算时,有着大量元素的移动,移动元素的多少取决于插入或删除元素的位置,而这种大量元素的移动是十分费时的,所以有着频繁的插入或删除运算的线性表,是不适合采用顺序存储方式的。
①在线性表的指定位置处加入一个新的元素(即线性表的插入);
②在线性表中删除指定的元素(即线性表的删除):
⑧在线性表中查找某个(或某些)特定的元素(即线性表的查找);
④对线性表中的元素进行整序(即线性表的排序);
⑤按要求将一个线性表分解成多个线性表(即线性表的分解);
⑥按要求将多个线性表合并成一个线性表(即线性表的合并);
⑦复制一个线性表(即线性表的复制):
⑧逆转一个线性表(即线性表的逆转)等。
1.4
1.4.1栈及其基本运算
1.堆栈的定义
堆栈(也简称栈)是一个线性表,其数据元素只能从这个有序集合的同一端插入或删除,这一端称为堆栈的栈顶(top),而另一端称为堆栈的栈底(bottom)。
故也称栈为后进先出表或先进后出表,简称LIFO(Lastinfirstout)或FILO(Firstinlastout)表。
2.堆栈顺序存储
堆栈顺序存储方式,是将堆栈中的数据元素连续顺序地存放于存储器相邻的单元,来保证堆栈数据元素逻辑上的有序性。
假设堆栈中每个数据元素占用size字节空间,top指向堆栈中进栈元素的栈顶元素,即栈顶元素的地址,MaxSize表示堆栈可以存储元素的最大空间。
一般约定下标为1的元素空间就是栈底,这样就不再另设一变量再来记录栈底指针bottom。
3.堆栈顺序存储运算
1)判断堆栈是否为空
所谓堆栈为空,是指堆栈中没有一个数据元素,即栈顶指针top指向数据空间的第一个位置的前面。
如堆栈不空,top总是指向栈顶元素。
2)判断堆栈是否为满
所谓堆栈为满,是指堆栈的所有数据空间已经全部用完,即栈顶指针top指向数据空间的最大下标位置。
如堆栈不满,top总是指向栈顶元素(top的值小于MaxSize)。
3)进栈(又称压入)运算
进栈运算是将一新元素x存储到当前top所指的空间的“上”一个位置,即top+1的的元素空间中。
进栈时,首先要判断堆栈中是否存在元素存放的空间,即先判断栈是否满,不满时,x可以进栈,否则出错(上溢)。
x进栈前,top指针要先做相应地移动。
4)出栈(又称弹出)运算
出栈运算是将栈顶元素取出,且将栈顶指针top向“下”移动一个位置,即取出top所指的元素,然后,top的值减1。
出栈时,首先要判断堆栈中是否存在元素可取,即先判断栈是否空,不空时,可以出栈,否则出错(下溢)。
出栈后,top指针要做相应地移动。
5)返回栈顶元素的值
返回堆栈栈顶元素的值,是指将top所指的堆栈元素的值取出,但是top指针不移动,当然,能够取得栈顶值的前提是栈中有元素存在(先判断栈是否空)。
这个算法与出栈算法有所不同,两个算法都可以取得栈顶指针所指的元素值,但此算法取值后不会移动top指针,即栈中元素的个数不发生改变。
1.4.2队列及其基本运算
1.队列的定义
队列是一个线性表,其数据元素只能从这个线性表的一端插入,而从另一端删除,删除端称为队列的队头(front),插入端称为队列的队尾(rear)。
取数据时(删除),又称出队,总是从队列中front所指的位置取走数据。
插入数据时,又称进队,总是在队列中rear所指的位置后面添加。
取走数据与放入时的顺序恰好相同,故也称队列为先进先出表,简称FIFO(Firstinfirstout)表。
2.循环队列及其运算
1.循环队列
由来
2.队列运算
1)判断队列是否为空
所谓队列为空,是指队列中没有数据元素,即队列队头指针和队尾指针指在同一个位置,即front=rear。
2)判断队列是否为满
所谓队列为满,是指队列的所有数据空间已经全部用完,即队列队头指针和队尾指针的关系是:
front=rear+1或1。
3)进队运算
进队列运算是将一新元素x存储到当前rear所指空间的“下一个”位置。
进队时,首先要判断队列中是否存在元素存放的空间,即先判断队列是否满,不满时,x可以进队列,否则出错。
4)出队运算
出队运算是将队列中队头指针所指的“下一个”位置的元素取出。
做法是:
首先将队列队头指针front先向“下一个”位置移动,然后,取出移动后front所指的数据元素。
出队时,首先要判断队列中是否存在元素可取,即先判断队列是否空,不空时,可以出队,否则出错。
1.5线性链表
线性表的顺序存储方式,它有着逻辑关系上相邻的两个数据元素在物理位置上也相邻的特征。
因此,只要知道第一个元素的位置(即下标),则可以利用寻址公式高效地存取一个元素。
但是,通过其插入,删除算法的分析也可以看出,它存在着一些缺点:
其一,在插入或删除的过程中有着大量元素的移动,运算时间较长。
其二,在为长度可变化的线性表预先分配空间时,必须按最大表长空间分配,因而造成存储空间得不到充分利用。
第三,表的空间不容易扩充。
为此,在有着频繁插入、删除运算时,不宜采用顺序存储结构。
线性链式存储结构时,物理存储空间的分配可以是静态存储空间分配,也可以是动态存储空间分配。
1.简单线性链表
在动态链式结构中,数据元素是由两部分构成的,一是数据元素的数据域;二是数据元素的链接域。
链接域指向下一个数据元素存储空间的起始地址,数据元素又被称为结点。
当某个结点后面没有结点时(无后继结点),该结点的link值为空(用NULL,或0,或用符号∧表示)。
一个链表除了数据元素结点外,通常将这个特殊结点称为“表头结点”,表头结点的链接域的类型是指向数据结点的指针类型,表头结点的数据域可以与数据结点的数据域的类型不同,用于存放线性表的有关“综合”信息。
2.双向链表的存储
Rlink指向直接后继结点,Llink指向直接前驱结点。
链表中最后一个结点的Rlink域为NULL,第一个结点的Llink域为NULL。
这样定
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第1章 数据结构与算法 数据结构 算法