数据结构基础.doc

《数据结构基础.doc》由会员分享，可在线阅读，更多相关《数据结构基础.doc（17页珍藏版）》请在三一文库上搜索。

1、第二章 数据结构基础2.1 基本概念程序 = 算法 + 数据结构也就是说，计算机按照程序所描述的算法对某种结构的数据进行加工处理。1 数据结构数 据：在计算机领域，指能够被计算机输入、存储、处理和输出的一切信息。数 据 项：是数据的最小单位，有时也称为域（field）。数据记录：是数据处理领域组织数据的基本单位，它由数据项组成。数据元素：是数据集合中相对独立的单位，也称结点。它和数据是相对而言的（如一条记录相对于所在文件被认为是数据元素，而它相对于所含的数据项又被认为是数据）。数据结构：是描述一组数据元素及元素间的相互关系的。逻辑结构：是指数据元素之间抽象化的相互关系 。存储结构：或称物理结构

2、，是数据的逻辑结构在计算机存储器中的存储形式 。 线性结构：每个结点有且只有一个前驱结点和一个后继结点（第一和最后一个结点除外） 逻辑结构 树型结构：每个结点有且只有一个前驱结点（树根结点除 非线性结构 外），但可以有任意多个后继结点。 图型结构：每个结点可以有任意多个前驱结点和任意多个后继结点 数据结构 顺序存储结构：将数据结构的数据元素按某中顺序存放在计算机存储器的连续存储单元中。其结构简单，可节省存放指针的空间，但需要连续的存储空间，当数据元素的数目不确定时，会造成存储空间的闲置。 链接存储结构：为数据结构的每个结点元素附加一个数据项，其中存放一个与其相邻接的元素的地址（指针），通过指针

3、找到下一个相关元素的实际存储地址。每个结点由数据域和指针域组成。 存储结构 其存储空间不必连续，在进行插入、删除操作时不必移动结点，但结点指针要占用额外的存储空间。 索引存储结构：将全部记录分别存放在存储器的不同位置，系统为整个记录建立一张索引表，表中登记了每条记录的长度、逻辑记录号和在存储器中位置。通过索引表来访问记录。 散列存储结构：在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。由关键字作某种运算后直接确定元素的地址。在数据的逻辑结构中，树型结构（1:N）是图型结构（M:N）的特例（M=1）， 线性结构（1:1）是树型结构（1:N）的

4、特例（N=1）。 一种数据结构可以表示成一种或多种物理结构。在数据处理过程中，一个恰当的数据结构起着非常重要的作用。2 算法算 法：即解决特定问题的方法。 数值算法：是解决数值问题的算法，主要进行算术运算，如：求解代数方程、求算法种类 解数值积分等 。早期的计算机主要用于数值计算 。 非数值算法：是解决非数值问题的算法，主要进行比较和逻辑运算，如：排序、查找、插入、删除等。随着计算机技术的发展，非数值计算的应用越来越广。 有穷性： 在执行有限步之后必须终止 确定性： 所给出的每一计算步骤必须是精确定义的算法准则 可行性： 要执行的每一计算步骤都可在有限时间内完成 输入： 一般应具有0个或多个输

5、入信息，它是算法所需的初始数据 输出： 一般应具有0个或多个输出信息，它是算法对输入信息的运算结果 正确性：指在合理的数据输入下，能在有限的运行时间内得到正确的结果。算法评价 运行时间（时间复杂性）：指一个算法在计算机上运算所花费的时间 占用的存储空间（空间复杂性）：指一个算法在计算机存储器中所占用的存储空间 简单性 ：指容易验证其正确性，且便于编写、修改、阅读和调试3 Pascal语言简介 整型 integer 一个整型数据占用2个字节的存储单元 实型 real 一个实型数据占用4个字节的存储单元 简单类型 字符型 char 一个字符型数据占用1个字节的存储单元 布尔型 boolean 一个

6、布尔型数据（false 或true）占用1个字节的存储单元 数组： 数组中的元素在位置上是顺序排列的，存储结构是顺序存储结构，逻辑结构为线性结构 。 （1）数据类型 记录：记录中的成分在位置上是顺序排列的，存储结构是顺序存储结构，逻辑结构为线性结构 。 结构类型 集合：集合与元素的位置无关，存储结构是顺序存储结构，逻辑结构是关系为空（即不存在次序关系）的结构 文件：文件中的成分在位置上是顺序排列的，但逻辑结构和存储结构可以有多种不同结构。 指针类型 是以存储单元的地址作为其值的一种数据类型，它也是一种整体变量，系统为指针变量分配一个固定的存储单元，一般为2个字节。指针类型的定义为: 类型标识符

7、 数组、记录、集合之间的区别区别 数组记录集合定义Array T1 of T2 ;Record域名1 : 类型1域名2 : 类型2 :域名n : 类型nEND;Set of 基类型成分类型T1:下标类型,可以是除整型和实型外的其它任何类型简单类型;T2: 成分(元素)类型,可以是任何类型类型1n : 可以是任何类型基类型：可以是除整型和实型外的其它任何类型简单类型;特征· 成分是同一类型的· 每个成分占有的存储单元具有相同的字节数· 每个成分是通过下标来指明和访问的· 元素个数是固定的、位置上是有序的·成分允许具有不同类型· 每个成分

8、占有的存储单元可能具有不同的字节数·每个成分是通过域名来指明和访问的· 元素个数是固定、有序的·元素个数是不固定的·元素在位置上是无序的·其中的元素不能单独地访问和运算，只能作为整体进行访问 （2） 语句 赋 值 语 句 ： 变量名：= 表达式； 转 向 语 句 ： goto 语句标号； 调用过程语句： 过程名（参数表）； 退出循环语句： exit； 返 回 语 句 ： return； 出错处理语句： error（字符串）； 复 合 语 句 ： begin 语句1；语句2；语句n end； 条 件 语 句 ： if 条件 then 语句1 el

9、se 语句2 ； 情 况 语 句 ： case 变量名 of 常量1：语句1； 常量2：语句2； end； for循环语句： for 变量名 ：= 初值 to downto 终值 do 语句； while循环语句： while 条件 do 语句； repeat循环语句： repeat 一组语句 until 条件；2.2 线性表1 线性表的逻辑结构线性表：是具有相同特征的数据元素的一个有限序列，除第一个和最后一个元素外，每个元素都只有一个之间前驱和一个直接后驱。表示为：（a1，a2， ai an） 逻辑结构： 是线性结构。2 线性表的存储结构线性表的存储结构有两种： 顺序存储结构 和 链接存储结

10、构 。 顺序表：具有顺序存储结构的线性表线性链表：具有链接存储结构的线性表 单链表：每个结点有一个指针域，有一个头指针h而无尾指针，表中最后一个结点的指针域是空的。其结构简单，但查找效率不高（查某结点总要从头开始）线性链表 循环链表：每个结点有一个指针域，有一个头指针h和一个尾指针r，表中最后一个结点的指针域不是空的，尾指针指向表的第一个结点。它形成环行结构，可显著提高查找效率（从任何结点出发都能查到所需结点）。 双向链表：每个结点有两个指针域，一个指向直接前驱，一个指向直接后驱。它形成双环行结构，可进一步提高查找效率（从某结点出发，既可以向前查又可以向后查）。 h 单链表 h r 循环链表

11、双向链表3 线性表的运算（1） 基本运算插入：在表中任一位置插入一个结点删除：删除表中任一结点修改：修改表中给定结点的值读值：读取表中给定结点的数据求长：计算表中结点的个数清表：清除表中结点，使其成为空表检索：找出表中给定特征的结点排序：按给定要求对表中元素重新排序（2） 常用算法举例· 顺序表的插入 例题： * 向线性表中第i个元素位置插入一个新元素 *算法步骤： 1）检查i值是否超出所允许的范围（1in+1），若超出，则进行“超出范围”错误处理；2）将线性表的第i个元素和它后面的所有元素均向后移动一个位置；3）将新元素写入到空出的第I个位置上；4）使线性表的长度增1。 A B C

12、 D E F G 1# 2# 3# 4# 5# 6# 7#PROCEDURE insertlist(v,n,i,x) BEGIN1) IF (i<1) OR (i>n+1) THEN error ('out of range') 此处 7 i42) ELSE FOR j:=n DOWNTO i DO 插入 A B C H D E F G vj+1:=vj;3) vi:=x;4) n:=n+1 1# 2# 3# 4# 5# 6# 7# 8# END; · 顺序表的删除 例题： * 删除线性表中第i个元素 *算法步骤： 1）检查i值是否超出所允许的范围（1in

13、），若超出，则进行“超出范围”错误处理；2）将线性表的第i个元素后面的所有元素均向前移动一个位置； A B C E F G A B C D E F G3）使线性表的长度减1。 1# 2# 3# 4# 5# 6# 7# PROCEDURE deletelist(v,n,i) BEGIN1) IF (i<1) OR (i>n+1) THEN error ('out of range') 此处 7 i42) ELSE FOR j:=i TO n-1 DO 删除 vj:=vj+1;3) n:=n-1 1# 2# 3# 4# 5# 6# 7# END; · 单链表的

14、插入 例题： * 向单链表中第i个结点(i0)之后插入一个元素为b的结点 *算法步骤： 1）为待插入元素b分配一个结点(假定是由s指针变量所指向的结点,即s结点) ,并把b赋给s结点的值域;2） 如果i=0,则将s结点插入表头后返回；3） 从单链表中查找第i个结点；4）若查找成功,则在第i个结点后插入s结点,。否则表明值超出单链表的长度,应进行错误处理。 插入前 head插入后 headdatanext 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 CEDAGBFCEDAGBFb372601587260153插入前FEDCBAhead 4 6 1 3 2 7 5 G 0 插入后G

15、 0EDbCBAhead 4 6 1 8 3 2 7 5 F PROCEDURE insert(head,i,b)BEGIN1) NEW(S) ； S.data:=b；2) IF i=0 THEN s.next:= head； head:=s； RETURN；3) P:=head； j:=1 ； 用指针P指向单链表中第j个结点While (p< > nil) and (j<i) do j:=j+1； p:=p.next； 4) IF p< >nil THEN 若条件成立，则表明查找成功 s.next:=p.next； 使s结点的指针域指向p结点的后继 p.next

16、:=s； 使p结点的指针域指向s结点ELSE error ('error') END; · 单链表的删除 例题： * 在单链表中删除结点d *算法步骤： 1） 如果单链表为空，则进行出错处理；2） 如果表头结点是被删除结点，则删除该结点后返回；3） 从单链表中查找其值等于d的结点，直到查找结束（成功或失败）为止；4）若查找成功,则删除被查找到的结点后，否则进行错误处理。 删除前 head删除后 headdatanext 1 2 3 4 5 6 7 1 2 3 4 5 6 7 CEdAGBFCE AGBF 37260152 76015 删除前FEdCBAhead 4 6

17、 1 3 2 7 5 G 0 删除后EG 0CBAhead 4 6 1 2 7 5 F PROCEDURE delete(head,d)BEGIN1) IF head=nil THEN error（'this is a empty list'）； 2) IF head.data =d THEN p:=head； 把表头指针赋给P，以便删除表头结点后收回该结点 head:=head.next； 删除表头结点 dispose(p)； 系统回收由p所指向的结点，即原表头结点 RETURN ； 返回3) q:=head； p:=q.next ； P指向待比较的结点,q指向p的前驱结点W

18、hile p< > nil do IF p.data=d THEN exit ELSE q:=p; p:=p.next； 4) IF p< >nil THEN q.next:=p.next； 删除p结点,即值为d的结点 dispose(p)； 回收p结点 ELSE error('error')END; 结论：在表很长时，采用顺序方式时插入和删除元素的效率很低，只有在很少进行插入和删除运算的情况下，采用顺序表才是合适的。而线性链表的插入和删除运算效率总是很高，与表长无关。4. 线性表的应用线性表是应用最广的数据结构。常见的有：（1） 高级语言中的数组（2）

19、 操作系统中的文件系统、目录系统（3） 事务管理中的表格2.3 数组1. 数组的概念数组：按一定格式排列起来的一列同一属性的项目。有一维数组、二维数组、三维数组等。二维数组：每一行都是一个线性表，每一个数据元素既在一个行表中，又在一个列表中。2. 数组的存储结构计算机中的存储单元是一维结构，数组是多维结构，用一维的连续单元存放数组时，按存放次序的不同有下列不同的存放形式：· 按行优先顺序存放 元素aij的存储地址为： Loc（aij）= Loc（a11）+（i-1）x n +（j-1） （1im， 1jn） (式中：m为二维数组的总行数，n为总列数，aij代表其中第i行、第j列的那个

20、元素)· 按列优先顺序存放 元素aij的存储地址为： Loc（aij）= Loc（a11）+（j-1）x m +（i-1） （1im， 1jn） · 压缩存储结构 适用于数组中含有大量零元素的特殊数组，如下三角阵、三对角阵、稀疏矩阵，它只存储非零元素，这样可以节省大量存储空间。 2.4 栈与队1 栈(1) 基本概念 栈(或称堆栈): 是一种仅允许在一端进行插入和删除运算的线性表, 遵循后进先出的原则。 栈顶：栈中可以进行插入和删除的那一端。 栈底：栈中不可以进行插入和删除的那一端。 进栈（或称入栈、压栈）：向一个栈插入新元素，即把新元素放到栈顶元素的上面，使其成为新的栈顶元

21、素。 出栈（或称退栈）：一个栈删除元素，即把栈顶元素删除掉，使其下面相邻的元素成为新的栈顶元素。 （2） 存储结构 有顺序存储和链接存储两种结构，链接存储的栈叫链栈。顺序存储的栈： 进栈a1a2a3an 栈底 栈顶 出栈 链栈： HS data next （3） 运算 运算种类顺序存储的栈链栈算法步骤算法描述算法步骤算法描述插入一个新的栈顶元素，即进栈1） 检查栈是否已满，若满，则进行错误处理；2) 将栈顶指针上移（即加1）；3) 将新元素赋给栈顶元素。Procedure push（s,x,top）;BeginIf top=m Then error('overflow') el

22、se top:=top+1; stop:=xend;1） 为待进栈元素x分配一个结点P，并把x赋给P结点的值域；2） 把P结点推入栈顶。Procedure push（HS,x）;Begin1) New（p）；P.data:=x;2) P.next:=HS; HS:=pend;删除栈顶元素，即出栈1) 检查栈是否为空，若空，则进行错误处理；2) 将栈顶元素赋给指定变参y;3) 将栈顶指针下移（即减1）。Procedure pop stack（s,y,top ）;BeginIf top=0 Then error('underflow') else y:=stop; top:=top

23、-1end;1) 检查HS是否为空，若空，则进行错误处理；2) 将栈顶结点的值赋给函数名,并将栈顶指针暂存p,以便回收栈顶结点;3) 删除栈顶结点;4) 回收P结点Function pop(HS):elemtype;Begin1) if HS=nil then error('underflow')2) pop:=HS.data; p:=HS;3) HS:=HS.next;4) Dispose(p)End;读取栈顶元素只要将栈顶元素赋给指定变参y即可，栈顶指针保持不变。Procedure readtop（s,y,top ）;BeginIf top=0 Then error(

24、9;empty') else y:=stop end; 只要取出Hsdata的值即可。Procedure readtop（HS,y）;BeginIf HS=nil Then error('empty') else y:= Hsdata end;设置一个空栈只要把栈顶指针置0即可。Procedure setnull（s,top）;Begin top:=0 end;若不考虑回收结点，只要将HS置空即可，若考虑回收链栈中的所有结点，算法如右。Procedure setnull(HS)； BeginWhile HS< >nil dop:=HS;HS:=HS.next

25、;Dispose(p)End;判断一个栈是否为空可用一个函数来描述，栈空时返回“真”值，非空时返回“假”值。Function empty（s）：boolean；Begin If s.top:=0 then empty：=true Else empty：=false end;只要当HS=nil时返回“真”值，否则返回“假”值即可。Function empty（hs）：boolean；Begin If HS=nil then empty：=true Else empty：=false end;（4） 应用· 过程的嵌套和递归· 表达式求值· 程序编译过程中的语法检查&

26、#183; 地图四染色问题2 队(1) 基本概念 队: 是一种限定在一端进行插入而在另一端进行删除的线性表, 遵循先进先出的原则。 进队：从队尾插入一个新的队尾元素。 出队：将一个队中的队头元素删除。（2） 存储结构 有顺序存储和链接存储两种结构，链接存储的队叫链队。 队可以用一维数组表示q（1：m），m表示队列的最大容量，front表示头指针，rear表示尾指针，入队时，尾指针增1，出队时，头指针增1，当rear-front=m时，队满。 顺序存储的队： 出队 进队a1a2a3an 头 尾 链队： front data next rear（3） 运算· 插入一个新的队尾元素，即进队

27、;· 删除队头元素，即出队; · 设置一个空队列;运算种类顺序存储的队算法步骤算法描述插入一个新的队尾元素，即进队1) 检查队是否已满，若满，则进行错误处理；2) 将队尾指针后移；3) 将新元素赋给队尾元素；4) 若原队为空队，则进行插入后，同时把队首指针置为1。Procedure insert（q,x,front,rear）;BeginIf rear=m Then error('overflow') Rear:=rear+1; qrear:=x;if front=0 then front:=1end;删除队头元素，即出队1) 检查队是否为空，若空，则进行错

28、误处理；2) 将队首元素赋给指定变参y;3) 若删除后队空,将队首和队尾指针置0,否则将队首指针后移。Procedure delete（q,y,front,rear）;BeginIf front=0 Then error('underflow') y:=qfront;if front=rear then front:=0;rear:=0else front=front+1end;设置一个空队只要把队首和队尾指针均赋0即可。Procedure setnull（q，front，rear）;Begin front:=0；rear:=0 end;运算种类链队算法步骤算法描述插入一个新的

29、队尾元素，即进队1) 为待入队元素x分配一个结点P，并把x赋给P结点的值域，nil赋给P结点的指针域；2) 若链队为空，则表明待插入P的结点既是队首结点也是队尾结点，否则把P结点插入队尾，并使队尾指针指向P结点。Procedure insert（hq,x, front,rear）;Begin1) New（p）; P.data:=x; P.next:=nil;2) if rear=nil then front:=p; rear:=p else rear.next:=p; rear:=pend;删除队头元素，即出队1） 若链队为空，则进行错误处理；2） 将队首结点的值赋给变参;3） 把队首指针暂存

30、指针变量p,以便回收该结点;4） 删除队首结点,即若链队中只有一个结点(即front=rear),则应同时把front和 rear置空,否则只修改队首指针,使之成为下一个结点;5） 回收原队首结点,即P结点。 Procedure delete（hq,x, front,rear）;Begin1) if front=nil then error('underflow');2) x:=front.data;3) p:=front;4) if front=rear then front:=nil;rear:=nil else front:=front.next;5) dispose(p

31、)end;设置一个空队 只要把队首和队尾指针置空即可 。Procedure setnull(hq，front，rear)； Begin Front：=nil； rear：=nil End;（4） 应用· 划分子集问题· 离散事件仿真2.5 树1 树的概念树：是由一个或多个结点组成的有限集T，其中有且仅有一个结点称为根结点，其余结点可以分为m（m0）个互不相交的有限集T1，T2，Tm，其中每个集合本身又是一棵树（叫子树）。是一个递归定义。结 点： 表示树中的元素，包含数据项及若干指向其子树的分支。结点的度： 结点拥有的子树数。叶 子： 度为0的结点，又称端结点。孩 子： 结点

32、子树的根称为该结点的孩子结点。双 亲： 孩子结点的上层结点。兄 弟： 同一双亲的孩子。结点的层次： 从根结点开始算起，根为第一层。深 度：树中结点的最大层次数。森 林：是m棵互不相交的树的集合。有序树：树中结点同层间从左至右有次序排列，不能互换的树。能互换的树称为无序树。二叉树：是n（n0）个结点的有限集，它或为空树（n=0），或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。也是一个递归定义。满二叉树： 深度为h且含有2h-1个结点的二叉树，即树中每一层的结点数是满的二叉树。完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是右边缺少连续

33、若干个结点的二叉树。满足关系式：2h-1 -1<n2h -12 二叉树的存储结构可以有顺序存储和链接存储两种。顺序存储只适合完全二叉树，能够充分利用存储空间，但对一般二叉树不合适，会造成许多存储单元空闲。一般的二叉树通常用具有两个指针域的链表作为二叉树的存储结构。其中每个结点由数据域、左指针域和右指针域组成。 L child DataR child F E C A AFECB B D D二叉树的基本性质：1） 二叉树的第i层上至多有2i-1（i1）个结点；2） 深度为h的二叉树中至多含有2h-1个结点。3） 若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则必有：n0=n2

34、+1 3 将树转换成二叉树的方法：1） 在兄弟间加一连线2） 对每个结点，除了其左孩子外，去除其与右孩子之间的联系3） 以树的根结点为轴心，将整树顺时针转45°。3 二叉树的运算二叉树的运算包括: 二叉树的遍历、求二叉树的深度、输出二叉树、二叉树的线索化和利用线索进行遍历等。 （1） 二叉树的遍历这是二叉树中其它所有运算的基础。它是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。遍历一棵非空二叉树的问题可分解为三个子问题：访问根结点、遍历左子树、遍历右子树。相应的二叉树的遍历方案有六种：DLR、LDR、LRD、DRL、RDL、RLD。遍历方案算法（均为递归算法）运算结

35、果代号名称 E D C B ADLR前序遍历 或先根遍历 Procedure preorder（bt）；Begin If bt< >nil thenwrite (bt.data); 访问根结点preorder(bt.left); 前序遍历左子树preorder(bt.right); 前序遍历右子树end; bt为具有billist类型的树根指针 G FLDR中序遍历 或中根遍历 Procedure inorder（bt）；Begin If bt< >nil theninorder(bt.left); 中序遍历左子树write (bt.data); 访问根结点inorde

36、r(bt.right); 中序遍历右子树end; LRD后序遍历 或后根遍历 Procedure postorder（bt）；Begin If bt< >nil theninorder(bt.left); 后序遍历左子树inorder(bt.right); 后序遍历右子树 write (bt.data); 访问根结点end; 前序：A，B，C，D，E，F，G中序：C，B，D，A，E，G，F 后序：C，D，B，G，F，E，A （2） 求二叉树的深度 若一棵二叉树为空，则深度为0；否则求二叉树深度的递归定义为：它等于左子树和右子树中的最大深度加1。即： depth=max（depL，depR）+1 求二叉树深度的递归算法： function depth（bt）：integer； begin if bt=nil then depth：=0 else depL：= depth（bt.Left）； depR：= depth（bt.right）； if depL>=depR then depth:=depL+1 else depth:=depR+1 end; 5 二叉树的应用1） 判定树 是用一系列判定构成的树，用于判定。2） 哈夫曼树 是一类带权路径最短的树，用于信息检索。3） 二叉排序树 是一种特殊结构的树，可作