pascal 第12讲 树与图的简介.ppt

《pascal 第12讲 树与图的简介.ppt》由会员分享，可在线阅读，更多相关《pascal 第12讲 树与图的简介.ppt（98页珍藏版）》请在三一办公上搜索。

1、数据结构之树图简介,王桐林寿光现代中学,潍坊市2009信息学奥林匹克夏令营,寿光现代中学,数据结构,寿光现代中学,1.线性结构（栈、队列）的回顾,什么是栈？什么是队列？,寿光现代中学,栈的应用1【括号匹配】,1、栈S初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_（noip1998）(A)5,4,3,2,1(B)2,1(C)2,3(D)3,4,寿光现代中学,栈的应用2【括号匹配】,判断包含有括号，的字符串是否匹配。【样例1】输入：abcabbmaa 输出：

2、yes【样例2】输入：abcabbmaa 输出：no,寿光现代中学,从字符串中读入一个左括号时，就将其压入栈s中；当读入一个右括号时,就从栈顶取出左括号检查比较,看是否匹配,如果匹配,就将左括号出栈;否则显示不匹配。全部字符串读完后,最后检查栈是否为空,如果不空,左括号无右括号与之匹配,显示不匹配。,【问题分析】,寿光现代中学,var i,c:integer;s:string;a:array1.2000 of char;f:boolean;procedure push(l:char);begin inc(c);ac:=l;end;procedure pop;begin dec(c);end;,

3、【参考程序】,寿光现代中学,begin f:=true;readln(s);c:=0;for i:=1 to length(s)do begin if f=false then break;if si=then push();if si=then push();if si=then push();if si=(then push();,寿光现代中学,if si=then begin if ac=then pop else f:=false;end;if si=then begin if ac=then pop else f:=false;end;if si=then begin if ac=t

4、hen pop else f:=false;end;if si=)then begin if ac=(then pop else f:=false;end;end;if f and(c=0)then writeln(yes)else writeln(no);end.,n,寿光现代中学,一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。输入：整数m,n(m行，n列)（1=m=80,1=n=50）矩阵输出：细胞的个数。样例:输入:4 10 0234500067 1034560500 2045600671 0000000

5、089 输出:4,队列的应用【细胞】,寿光现代中学,0234500067103456050020456006710000000089,共4个细胞,寿光现代中学,算法步骤：1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入pic数组中；2、沿pic数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队h，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(picI,j=1)则将其位置入队，入队后的位置picI,j数组置为0；3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置pic数组置为0；4、重复3，直至h队空为止，则此时找出了一个细胞

6、；5、重复2，直至矩阵找不到细胞；6、输出找到的细胞数。,寿光现代中学,const dx:array1.4 of-1.1=(-1,0,1,0);dy:array1.4 of-1.1=(0,1,0,-1);var s:string;pic:array1.80,1.50 of 0.1;0:无细胞；1:有细胞 m,n,i,j,num:integer;h:array1.4000,1.2 of byte;队列:存细胞的坐标，1：行；2：列,寿光现代中学,procedure doing(p,q:integer);处理坐标（p,q）的细胞 var i,t,w,x,y:integer;begin inc(nu

7、m);细胞数量加1 picp,q:=0;t:=1;队列头 w:=1;队列尾 h1,1:=p;h1,2:=q;遇到的第一个细胞入队 repeat for i:=1 to 4 do 沿细胞的上下左右四个方向搜索细胞 begin x:=ht,1+dxi;y:=ht,2+dyi;if(x0)and(x0)and(yw;直至队空为止 end;,寿光现代中学,begin fillchar(pic,sizeof(pic),0);num:=0;fillchar(h,sizeof(h),0);readln(m,n);for i:=1 to m do begin readln(s);for j:=1 to n d

8、o if sj=0 then pici,j:=0 else pici,j:=1;end;for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩阵中寻找细胞 writeln(num);end.,寿光现代中学,数据结构,树,寿光现代中学,栈、队列属于线性结构。在这种结构中，不管其存储方式（顺序和链式）如何，数据元素的逻辑位置之间呈线性关系，即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）。但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素

9、）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种：树 图,树,寿光现代中学,一、树的概念1、树的定义 树是一种常见的非线性的数据结构。树的递归定义如下：树是n(n0)个结点的有限集，这个集合满足以下条件：有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；除根外，其余的每个结点都有且仅有一个前驱；除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。,寿光现代中学,寿光现代中学,2、结点的分类 结点一般分成三类根结点

10、：没有父亲的结点。在树中有且仅有一个根结点。分支结点：除根结点外，有孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是其子树的根；叶结点：没有孩子的结点称为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。根结点到每一个分支结点或叶结点的路径是唯一的。从根r到结点i的唯一路径为rcti。,寿光现代中学,3、有关度的定义 结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。树的度：所有结点中最大的度称为该树的度(宽度）。图中树的度为3。,寿光现代中学,4、树的深度（高度）树是分层次的。结点所在的

11、层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图中树的深度为5。,寿光现代中学,二、树的表示方法和存储结构1、树的表示方法 树的表示方法一般有两种：自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。,寿光现代中学,括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下

12、形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）,寿光现代中学,2、树的存储结构树的存储结构一般有两种静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n 为树的度)的数组，分别存储该结点的每一个儿子的下标Const n=树的度；max=结点数的上限；Type node=record 结点类型 data：datatype；数据域 ch：array1n of integer；指向各儿子的下标 end；treetype=array1.maxof node；Var tree：treetype；树数组,寿光现代中学,例如图的树，

13、其记录数组如下。由于未规定同层结点的次序，因此每个结点儿子的下标序列（Treei.ch）任意。其中Treei.chj=0说明结点i的第j个儿子不存在。(编号按层编号),寿光现代中学,三、二叉树的概念 二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。1、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；？二叉树是不是树？二叉树树？,寿光现代中学,由上述定义可以看出，二叉树和树是

14、两个不同的概念树的每一个结点可以有任意多个，而二叉树中每个结点的后继不能超过2；树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。,寿光现代中学,前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态：,寿光现代中学,2、二叉树的两个特殊形态满二叉树：如果一棵深度为K的二叉树，共有2K-1个结点，即第I层有2I-1的结点，称为满二叉树。(a)完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）,寿光现代中

15、学,3、二叉树的三个主要性质性质1：在二叉树的第i（1）层上，最多有2i-1个结点,证明 数学归纳法证明归纳基础 i=1时，有2i-1=20=1,因为第一层只有一个根结点，所以命题成立。归纳假设 假设对于所有的j（1=ji）命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。归纳步骤 根据归纳假设，第i-1层的结点数至多是第2i-2个结点。由于二叉树的每个结点至多有2个孩子，故第i层上至多有2*2i-2=2i-1个结点。,寿光现代中学,性质2：在深度为k(k1)的二叉树中最多有2k-1个结点。,证明：根据性质1，深度为k的二叉树最多有：20+21+.+2k-1=2k-1（等比数列

16、求和乘2做减法）,寿光现代中学,性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+1设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然所有结点数目 n=n0+n1+n2（1）所有这些分支同时又为度为1和度为2的结点发出的。再加上根结点，因此又有 n=1+n1+2n2(2)由上两个等式求得：n0=1+n2,寿光现代中学,例题：如果一棵m度的树中有N1个度为1的顶点，N2个度为2的顶点，N3个度为3的顶点，Nm个度为m的顶点，求该树中叶子顶点个数。,分析：设叶子结点数为N0 所有结点数为n，边数(分支）为b，则有：n=b+1(1)又b=N1

17、+2N2+3N3+.+M*NM(2)又：n=N0+N1+N2+.+NM(3)(2),(3)代入（1）得出：N0=N2+2N3+3N4+.+(M-1)NM+1,寿光现代中学,四、二叉树的存储结构二叉树的存储结构有两种形式顺序存储结构链式存储结构,寿光现代中学,1、顺序存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括一个数据域（data）；三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。满二叉树和完全二叉树一般采用顺序存储结构 Const m=树中结点数上限；Ty

18、pe node=record 结点类型 data：datatype；数据值 prt，lch，rch：0m；父结点、左儿子、右儿子编号 end；treetype=array1m of node；二叉树的顺序表类型 Var Tree：treetype；二叉树,寿光现代中学,例如，采用数组tree存储二叉树（如下图）,寿光现代中学,五、二叉树的遍历 二叉树的遍历是不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，或对结点作其它的处理。如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，限定先左后右的次序，三种组合 DLR、LDR、LRD这三种遍历规则分别称为先（前）

19、序遍历、中序遍历和后序遍历（以根为标准）。二叉树的存储采用动态的二重链表形式。,寿光现代中学,为了方便叙述，我们以下图为例解释三种遍历规则，我们在写遍历子过程前先定义树结构如下：program shudebianli;type asdf=record name:char;结点名字 father:integer;父结点信息 left:integer;左孩子信息 right:integer;右孩子信息 end;var l,i,h,a:longint;s:string;t:array1.100 of asdf;,寿光现代中学,前序遍历前序遍历的规则如下：若二叉树为空，则退出。否则 访问处理根结点；前

20、序遍历左子树；前序遍历右子树；a b d e h i c f g,寿光现代中学,procedure front(i:integer);begin if ti.name#then begin write(ti.name);if ti.left0 then front(ti.left);if ti.right0 then front(ti.right);end;end;,寿光现代中学,中序遍历中序遍历的规则如下：若二叉树为空，则退出；否则 中序遍历左子树；访问处理根结点；中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：d b h e i a f c g,寿光现代中学,proced

21、ure mid(i:integer);begin if ti.name#then begin if ti.left0 then mid(ti.left);write(ti.name);if ti.right0 then mid(ti.right);end;end;,寿光现代中学,后序遍历后序遍历的规则如下：若二叉树为空，则退出；否则 后序遍历左子树；后序遍历右子树；访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a,寿光现代中学,procedure back(i:integer);begin if ti.name#then begin if t

22、i.left0 then back(ti.left);if ti.right0 then back(ti.right);write(ti.name);end;end;,寿光现代中学,六、由二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则：前序遍历：根左子树右子树；中序遍历：左子树根右子树；后序遍历：左子树右子树根；,寿光现代中学,【例题1】根据两种遍历顺序确定树结构输入：二叉树的前序遍历顺序与中序遍历顺序输出：二叉树的后序遍历顺序样例：输入：abcdefgcbdafeg输出：cdbfgea,寿光现代中学,var sx,sz:string;算法procedure work(sx,sz

23、:string);sx:先序序列;sz：中序序列 var l,k:integer;begin if sx then begin l:=length(sx);k:=pos(sx1,sz);根在中序序列中的位置 work(copy(sx,2,k-1),copy(sz,1,k-1);递归调用左子树 work(copy(sx,k+1,l-k),copy(sz,k+1,l-k);递归调用右子树 write(sx1);后序输出根结点 end;end;begin readln(sx);readln(sz);work(sx,sz);writeln;end.,寿光现代中学,数据结构,图,寿光现代中学,一、图的基

24、本概念,二、图的存储结构,三、图的遍历,寿光现代中学,图是由一个顶点的集合V和一个顶点间关系的集合E组成：记 G=（V，E）V：顶点的有限非空集合。E：顶点间关系的有限集合（边集）。存在一个结点v，可能含有多个前驱结点和后继结点。,一、图的基本概念,图2,图3,图1,1、图的的定义,寿光现代中学,无向图：在图G=（V，E）中，如果对于任意的顶点a，bV，当(a，b)E时，必有（b，a）E（即关系R对称），此图称为无向图。无向图中用不带箭头的边表示顶点的关系 V=1,2,3,4,5 E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5),2、无向图和有向图,寿光现

25、代中学,有向图：如果对于任意的顶点a，bV，当(a，b)E时，(b，a)E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点。V=1,2,3,4,5 E=,寿光现代中学,在无向图中：顶点v的度是指与顶点v相连的边的数目D(v)。D(2)=3,3、顶点的度、入度和出度,在有向图中：入度以该顶点为终点的边的数目和.ID(3)=2 出度以该顶点为起点的边的数目和.OD(3)=1度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。度：等于该顶点的入度与出度之和。D(5)=ID(5)+OD(5)=1+2=3,结论：图中所有顶点的度=边数的两倍,图1:无向图,图2：有向图,无向完全

26、图,寿光现代中学,在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1xk(k1)x1=a，xk=b(xi，xi+1)E i=1k-1则称结点序列x1=a，x2，xk=b为结点a到结点b的一条路径，而路径上边的数目（k-1）称为该路径的长度。,图1,图2,图1:1、(1,2,3,5)长度=3 2、(1,2,3,5,2)长度=4 3、(1,2,5,4,1)长度=4,图2:(1,2,5,4)长度=3,（1）、如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。（2）、x1=xk的简单路径称为回路（也称为环）,4、路径、简单路径、回路,

27、寿光现代中学,5、连通、连通图、连通分量(无向图),连通：“连成一片”。连通图：“能连成一片的图”。,图一：连通图,图二：非连通图,定义：连通：如果存在一条从顶点u到v有路径，则称u和v是连通的。连通图：图中任意的两个顶点u和v都是连通的，称为连通图。否则称为非连通图。,连通分量：无向图中的极大连通子图。,图二中有3个连通分量：1 2 4 5 3 6 7 8,求连通分量数，最大连通分量等。,有向图：强连通、强连通图、强连通分量,寿光现代中学,6、带权图,图中的边可以加上表示某种含义的数值，数值称为边的权，此图称为带权图。也称为网。,一般的图边上没有数字，边仅表示两个顶点的相连接关系。,寿光现代

28、中学,二、图的存储结构,顶点：数组或记录,边：邻接矩阵/邻接表,G=(V,E),寿光现代中学,邻接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的邻接矩阵是如下定义的二维数组 a1.n,1.n。,1、图的邻接矩阵表示法,寿光现代中学,对角线为0：自身不相连。无向图：是对称矩阵。有向图一般不是。第i行非0 的个数是结点i的度,寿光现代中学,具体到题目时，数据的给出格式多种多样：1）、直接给出邻接矩阵，直接读即可。如：输入文件内容：50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0,maxn=100a:array1.maxn,

29、1.maxn of integerfillchar(a,sizeof(a),0);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);,寿光现代中学,2）、给出边的顶点。如输入文件：两个顶点及权值571 2 21 3 21 4 32 3 12 5 33 5 24 5 4,readln(n);readln(m);for k:=1 to m do begin readln(i,j,x);ai,j:=x;aj,i:=x;end,寿光现代中学,62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 5,3)、给出每个

30、顶点的邻接点,readln(n);for i:=1 to n do begin read(k);for j:=1 to k do begin read(x);ai,x:=1;ax,i:=1;end;end;,寿光现代中学,无权图:设置结点指针,2、邻接表:,寿光现代中学,type point=node;node=record v:integer;next:point;end;var a:array1.maxvof point;,readln(n1,n2);new(p);p.v:=n2;p.next:=an1;an1:=p;new(p);p.v:=n1;p.next:=an2;an2:=p;,寿

31、光现代中学,头指针,邻接点指针,有权图：,寿光现代中学,type edge=node;node=record v:integer;weight:integer;next:edge;end;vpoint=record v:integer;link:edge;end;var a:array1.maxn of vpoint;,寿光现代中学,邻接矩阵和邻接表的优缺点：,邻接表,邻接矩阵,寿光现代中学,邻接矩阵：代码书写简单，找邻接点慢邻接表：代码书写较复杂，找邻接点快,一般采用邻接矩阵,寿光现代中学,0 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0

32、0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 00 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 00 0 0 0 1 0 0 0 0,邻接表,邻接矩阵,寿光现代中学,稀疏图：边表,type node=record w:integer;/边权 u,v:integer;/两个结点 end;var e:array1.maxn*(maxn-1)div 2 of node;/边,寿光现代中学,三、图的遍历 给出一个图G，从某一个初始点出发，按照一定的搜索方法对图中的每一个结点访问仅且访问一次的过程。访问结点：处理结点的过程。如输出、

33、查找结点的信息。按照搜索方法的不同，通常有两种遍历方法：1、深度优先搜索dfs 2、广度优先搜索bfs,寿光现代中学,1、深度优先搜索DFS遍历算法（递归过程）：1)从某一初始出发点i开始访问：输出该点编号；并对该点作被访问标志（以免被重复访问）。2)再从i的其中一个未被访问的邻接点j作为初始点出发继续深搜。当i的所有邻接点都被访问完，则退回到i的父结点的另一个邻接点k再继续深搜。直到全部结点访问完毕,寿光现代中学,实现:,a1.maxn,1.maxn:边的邻接矩阵。1：有边；0：无边f1.maxn:boolean 标记是否被访问过。True:已访问；flase：没访问。初始值：false,1

34、0121 41 51 64 8 5 34 35 76 27 102 93 77 2,Procedure init;/初始化 begin readln(n);readln(m);for i:=1 to m do begin readln(x,y);ax,y:=1;ay,x:=1;end;end;,寿光现代中学,procedure dfs(k:integer);/从k点出发遍历 var j:integer;/局部变量？begin write(k,);fk:=true;for j:=1 to n do if(fj=false)and(ak,j=1)then dfs(j);end;,上图的遍历结果：,

35、Dfs(1)?,寿光现代中学,主程序begin fillchar(f,sizeof(f),false);for i:=1 to n do if not fi then dfs(i);end;,寿光现代中学,求无向的连通分量,sum:=0;for i:=1 to n do if not fi then begin inc(sum);dfs(i);end;writeln(sum);,寿光现代中学,2、广度优先搜索(宽度优先搜索）BFS 按层次遍历：从图中某结点i出发，在访问了i之后依次访问i的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访

36、问到。,寿光现代中学,实现：队列：q1.maxn f1.n:boolean:判重,head,tail,寿光现代中学,procedure bfs(i:integer);/bfs.pas var j,k:integer;begin fillchar(q,sizeof(q),0);head:=0;tail:=1;q1:=i;fi:=true;while headtail do/队列非空 begin inc(head);/出队 k:=qhead;write(k,);for j:=1 to n do if(ak,j=1)and(fj=false)then begin inc(tail);/进队 qtai

37、l:=j;fj:=true;end;end;end;,寿光现代中学,3、图的遍历的简单应用,1、犯罪团伙【问题描述】警察抓到了n个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但通过警察的审讯，知道其中的一些罪犯之间相互认识，已知同一犯罪团伙的成员之间直接或间接认识，有可能一个犯罪团伙只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。已知罪犯的编号从1至n。【输入】第一行：n（1000,罪犯数量）。第二行：m（5000，关系数量）。以下m行，每行两个数：i 和j，中间一个空格隔开，表示罪犯i和罪犯j相互认识。【输出】一个整数，犯罪团伙的数量。,寿光现代中学,【

38、样例输入】118 1 24 53 41 35 67 105 108 9,【样例输出】3样例说明：共三个集团。,寿光现代中学,把n个人看成图的n个顶点；相互认识的连一无向条边。相互认识的所有人构成一个极大连通子图。问题转化为：求无向图的连通分量（有多少个极大连通子图）,寿光现代中学,建图 fillchar(f,sizeof(f),false);/访问标志 sum:=0;for i:=1 to n do if not fi then begin inc(sum);dfs(i);end;writeln(sum);,算法：,寿光现代中学,常见图论算法,最短路径,最小生成树,拓扑排序,寿光现代中学,数据

39、结构简单总结,寿光现代中学,对于程序设计来说：编程语言是工具；数据结构是基础；算法设计是方法。,程序=数据结构+算法,寿光现代中学,数据结构专门研究各种数据的表示、数据的类型以及它们之间关系的集合，其研究范围主要包括各种数据结构的性质，即它们的逻辑结构、物理结构以及施于其上的操作。,寿光现代中学,从数据元素的值在使用时具有不可分割的性质或者是它可以由更基本的成份组成的角度划分，数据结构可以分成简单类型和构造类型两大类；如果从数据所占据的内存空间在程序执行期间是否发生变化的角度划分，数据结构可以分成静态结构和动态结构两大类；如果从数据结点后继关系的多少和是否具有层次性的角度划分，数据结构可以分成

40、线性结构和非线性结构两大类。,寿光现代中学,寿光现代中学,逻辑结构,前述“关系”即结构(sructure)，指数据之间的逻辑关系，又称逻辑结构。,寿光现代中学,物理结构,1 顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中相邻。2 链式结构：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中不一定相邻。用高级语言中的数据类型(数组、动态变量)来描述逻辑结构、物理结构密切相关算法的设计取决于所选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。,寿光现代中学,数据结构上的基本操作,插入删除更新查找排序(线性结构)遍历,寿光现代中学,顺序存储与链式存储操作的对比,寿光现代中学,线性结构,栈队列,定义存储操作应用,寿光现代中学,非线性结构,树图,定义存储操作应用,寿光现代中学,作业,课本例题,寿光现代中学,Thank You!,