AS3.0学习笔记(1)

即日起我们推出一部新的连载系列——《AS3.0》,原有的“假期系列”改为周末仍以假期形式不间断放出。

ActionScript是针对Adobe Flash Player运行时环境的编程语言。它实现了Flash在动画制作、图像处理、数据处理以及人机交互等方面的众多功能。ActionScript是由Flash Player中的ActionScript虚拟机AVM来执行的,与Java类似,AS的程序代码通常被IDE内嵌的编译器编译成“字节码格式”并放入swf最终文件中,最后由Flash Player统一执行。

自ActionScript的第一个完整版v1.0与Flash 5共同发布以来,AS就随着Flash的不断更新而变得越来越强大,从MX时代起AS就被Macromedia确立为RIA战略的重要工具。 AS3.0是随着Flash 9的发布而正式亮相的,我们今后连载所使用的编程环境也是Flash CS3(v9),但我们更多的只是关注语言本身,并不会过于脱离主题。内容也是严格依据adobe官方manual和livedocs编写,如果对本文有任何疑问的话,可以直接前往adobe.com查阅相关文章。

尽管adobe宣称AS3.0同样适合无程序设计语言基础者学习,但为了能够更效率地写出有用的程序,请至少拥有一种语言基础,例如C语言。当然,如果你在此基础上还拥有Javascript基础那么学习起来将感到一些似曾相识,如果你还系统学习过Java—那么看半个小时manual你就可以直接上手AS3.0了!

 

请再次注意,由于作者本人几乎没有接触过AS3.0以前的版本,因此本文的版本衔接并不能满足一些读者的需要。另外对于RIA的另一个重要工具Flex我们暂时还不会涉及,因此以后的例解程序并不会出现关于AS3.0在Flex中的应用。

 

一、构建自己的AS应用程序

 

现在讨论如何利用Adobe Flash CS3 professional创建一个应用程序,通常我们会有两种做法:

1、将代码存储在时间轴中的帧中;

2、将代码存储在ActionScript文件中;

前一种方法较为简单,在代码复杂度不高、没有重用需求的情况下经常使用。首先开启Adobe Flash CS3 Professional应用程序,在引导界面中选择“Flash文件(ActionScript 3.0)”,如果没有引导界面,可以选择菜单“文件-新建”,随后直接点击“确定”。

现在点击图层中某一帧,例如当前flash文档“图层1”的第一帧,按“F9”,此时会弹出脚本编辑器,在编辑窗口中填入相关代码即可(如图1-1)。 1-1

在创建大型应用程序时,为了方便代码维护,或者希望代码能够在其他程序中得到重用,此时采取前文所说的第二种方法:选择菜单“文件-新建”,选择“常规”选项卡中的“ActionScript文件选项”,点击“确定”就可以进入脚本编辑页面了。

图1-1

 

在了解了上述内容后,让我们来制作一个简单的应用程序,本程序将采用第二种代码存储方式进行构建,其中涉及到了关于IDE本身的一些基本操作,以及面向对象程序设计的一些知识。当然,本文的重点并不在这些方面,该程序段仅仅起到演示作用。

程序例1-1

步骤1、首先启动Flash并新建一个ActionScript文件,选择一个指定文件夹并将其保存为HelloWorld.as文件。

步骤2、在编辑区内输入以下代码,并保存。

package //定义一个”包”,我们会在今后详细讨论 

{

    public class HelloWorld //声明一个类HelloWorld

    {

private var sthSaved:String; //声明一个String类型变量sthSaved

public function HelloWorld() //类的构造方法

        {

            sthSaved = ”Hello World!by hanyi.name!”;

        }

        public function getSaved():String  //使对象返回sthSaved值的方法

        {

            return sthSaved;

        }

    }

}

步骤3、新建一个Flash文件(ActionScript3.0),保存至与.as文件相同的文件夹中,并取名为HelloWorld.fla。

步骤4、现在在一个传统的Flash工作界面中,首先点击界面左侧工具栏的“文本工具”(快捷键为“T”),用鼠标点击拖动在舞台中创建一个文本字段,并在下方“属性”标签栏(ctrl+F3)内选择“动态文本”,并调整其“宽”、“高”分别为300、50,并设定实例名称为“textOutput”,如图1-2。

1-2

步骤5、单击时间轴第一帧,并按“F9”,在脚本编辑框内写入如下代码。

var object:HelloWorld=new HelloWorld(); //定义对象object

textOutput.text=object.getSaved(); //设置文本框显示的内容

步骤6、ctrl+c保存文档,此时文档创建结束。按下ctrl+enter即可测试影片。此时测试舞台上应出现“Hello World!by hanyi.name!”。

 

在上述程序中,有一些其他语言程序员值得注意的地方。其中package包的概念和用法,与Java类似,在后面的部分中会详细介绍。注意变量的声明方式:var 变量名:类型这样的用法,这在声明类的方法时同样适用。尽管以上程序中的效果可能在Flash中仅仅用两个简单操作就能实现,但是比较完整地体现出了AS运行的方式。下面我们对上述程序作出一些改进,这些改进主要体现在交互功能方面。

 

程序例1-1改进版

 

步骤1、打开HelloWorld.as文件,对源文件做以下修改。

package //定义一个”包”,我们会在今后详细讨论 

{

    public class HelloWorld  //声明一个类HelloWorld

    {

private var sthSaved:String; //声明一个String类型变量sthSaved

private var exam:ShortTest;

public function HelloWorld()  //类的构造方法

        {

            sthSaved = ”Hello World!by hanyi.name!”;

        }

public function getSaved():String  //使对象返回sthSaved值的方法

        {

            return sthSaved;

        }

public function startAnswer():String //声明ShortTest类对象,并初始化显示器

{

exam = new ShortTest();

return exam.showQuestion();

}

public function input(answer:int):String //返回结果

{

if(exam.updateResult(answer))

return ”Congratulations!”;

else

return ”Sorry,Try again!”;

}

 

    }

}

class ShortTest //包外类

{

public function updateResult(finalResult:int):Boolean //接收传入的答案,并判断正误

{

if(finalResult == 18)

{

return true;

}

else

return false;

}

public function showQuestion():String //显示题目

{

var question:String = ”2*9=?”;

return question;

}

}

 

步骤2、打开HelloWorld.fla文件,对第一帧上的脚本作以下修改。

var object:HelloWorld=new HelloWorld();

var flag:Boolean;

textOutput.border=true;

textInput.border=true;

textOutput.text=object.getSaved();

textInput.text=”continue…”;

 

textInput.addEventListener(KeyboardEvent.KEY_UP, keyPressed); //监听键盘事件

 

function keyPressed(keyevent:KeyboardEvent):void //委托事件处理

{

    if (keyevent.keyCode == Keyboard.ENTER)

    {

if(flag==false)

{

textInput.replaceText(0,textOutput.length,”“);

         textOutput.text = object.startAnswer(); //进入答题

flag=true;

}

else

{

textOutput.text = object.input(int(textInput.text)); //显示答案

textInput.replaceText(0,textOutput.length,”“);

}

    }

}

 

步骤3、在textOutput下方重新插入一个文本工具,属性选择“输入文本”,实例名称为“textInput”,其他选项与textOutput相同。

 

步骤4、测试影片,首先选定下面的“continue…”框并按enter,此时出现题目,在下方文本框中输入答案,并按enter,检查结果。

 

本例作为例1-1的改进版本,功能上主要体现在交互性的增强。另外需要注意HelloWorld.as文件内包外类ShortTest,这表示ShortTest仅具备被.as文件内其他类访问的权限,并不能被包外数据访问。另一方面,AS3.0的事件委托机制与Java是极其类似的,该程序最终结果显示如下图。 

1-3

1-4

1-5

Comments

百篇总结

确切的说本文已经是blog建立以来第一百零三篇了,原本想在第100篇写,后来发现需要赶工做完一些尚未完成的工作,于是竟推后了这么多,就像前几天错过重建周年一样其实看看url的记录,p值已经接近150,这是因为wp在文章备份时欠虑周全的结果使得在后台不得不强删了许多bak

关于假期连载,开始考虑回学校以后是否该换个名字了,后来发现届时恐怕依然不会改变发布的时间,因此就会沿用这一名称。连载之外还是仿照去年的做法发布一些好玩有用的东西出来。

首页又要颠覆了原因是现在的功能性太差,不符合我们的风格,况且完全基于web我们也已经能做的够好不过鉴于美观性还是要依赖一定的Flash,我不是搞外观设计的

Comments

假期连载之十四

(图—图的遍历、应用)

 

    图是我们在简单数据结构部分中讨论的最后一篇,其重点主要包括离散数学中关于图论的一些理论介绍,各种性质图的存储表示优缺点分析,图的遍历算法以及部分基于遍历算法的一些实际应用问题等。可以说在图之前,数据结构所利用到的一些简单算法依然属于“入门级”,而从图开始,就要建立在较为复杂的算法分析基础上进行算法设计了。

    但今后当我们接触到高级数据结构部分的内容时,恐怕又会对图这一部分稍带不屑了。

 

    图的遍历

 

    图的遍历从大的方向来看与树形结构类似,分深度优先和广度优先两种类型。但图有其极其特殊的一面,使它和树的算法设计上有着根本区别。

    一是图不同于树的一对多的关系,而是多对多的关系,在这些关系中可能是非连通图,也有可能含有回路存在。这有点类似于我们曾提到的迷宫解法,但事实上用图来解迷宫问题有点杀鸡用牛刀的感觉,且在一些情况中甚至还无法用图来构建。

总之图的遍历一般情况下需要回溯,为了防止重复访问结点,需要额外设置一个访问标志数组visited[n],用于记录已访问过的结点。

1、 深度优先搜索

图的深度优先搜索是从树的先根遍历算法推广而来的,其原则是按深度方向搜索。其算法思想是:

1)  从图中某个顶点v0出发,首先访问v0

2)  找出刚访问过的顶点的第一个未被访问的邻接点,然后访问该结点。以该结点为新结点,重复此步骤,直到刚访问过的顶点没有未被访问的邻接点为止;

3)  返回前一个访问过的且仍有未被访问的邻接点的顶点,找出该顶点的下一个未被访问的邻接点,访问该顶点,然后执行步骤2

我们用深度优先顺序模拟遍历图,在算法前进的方向所连成的结点序列构成以A为根的树,称为深度优先搜索树

下面给出C语言描述的深度优先搜索—邻接矩阵法表示。

void DepthFirstSearch(AdjMatrix g,int v0)

{

    visit(v0);

    visited[v0]=True;

    for(vj=0;vj<g.vexnum;vj++)

        if(!visited[vj]&&g.arcs[v0][vj].adj==1)

            DepthFirstSearch(g,vj);

}//如果读者有兴趣,可以自己写出工作栈条件下的非递归算法,两种同样重要

2、 广度优先搜索

广度优先搜索即是从树和森林的广度优先遍历算法推广而来的。其算法的基本思想是:

1)从图中某个顶点v0出发,首先访问v0

2)依次访问v0的各个未被访问的邻接点;

3)分别从这些邻接点出发,依次访问它们的各个未被访问的邻接点。在访问时应保证以下规则:如果vivk为当前端接点,且vivk之前被访问,则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前被访问

由于广度优先搜索实质上是按层次顺序搜索,因此算法不涉及回溯,借鉴树的经验,我们依然采用队列一次存储一层结点的方式组织算法,便于确保访问该层所有结点。

 

图的应用

 

图的应用是广泛且复杂的。在介绍其具体应用之前,需要了解几个关于图应用的几个前置概念。

1、连通分量

当无向图为非连通图时,从图中某一个顶点出发,利用深度或广度优先搜索算法无法遍历所有顶点,而只能访问到该结点所在的最大连通子图中的所有顶点,这些顶点构成一个连通分量connected component。在这种情况下,对图的遍历应以连通分量为单位进行,才能确保遍历全部顶点。

以此作为推广,在无向连通图中,顶点v被称为关节点articulation point,当且仅当删去v及依附于v的所有边之后,G被分割为至少两个连通分量。我们把没有关节点的图称为重连通图biconnected graph

 

2、简单路径

简单路径是指图中顶点u到顶点v的一条路径中,其顶点均不相同的路径。通过简单分析可知,两顶点间可能存在多条简单路径,我们可以对遍历算法进行适当改进,使求得的解为简单路径。

 

3、生成树

一个连通图的生成树是指一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。如果在生成树上添加一条边,则必然形成一个环。一个有n个顶点的生成树仅有n-1条边,如果多余n-1则必然有回路,但是含有n-1条边的土并非是连通图,就不一定存在生成树,如果一个图的边数少于n-1,则其必然是非连通图。

在一个连通网的所有生成树中,各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树Minimum Cost Spanning Tree,简称为最小生成树MST

最小生成树具有一条重要性质:N={V,{E}}是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u属于Uv属于V-U,则存在一棵包含边(u,v)的最小生成树

利用MST的上述性质,我们可以生成一个连通网的最小生成树。其中Kruskal算法和Prim算法是最为经典的。

1Kruskal

假设N=(V,{E})是连通网,将N中的边按权值从小到大的顺序排列。

    a)将n个结点看成n个集合;

    b)按权值从小到大的顺序选择边,所选边应满足两个顶点不在同一个顶点集合内,将该边放到生成树边的集合中,同时将该边的两个顶点所在的顶点集合合并。

    c)重复b直到所有的顶点都在同一个顶点集合内。

2Prim

假设N=(V,{E})是连通网,TE为最小生成树中边的集合。

    a)初始U={u0|u0属于VTE为空}

    b)在所有u属于Uv属于V-U的边种选择一条代价最小的边(u0,v0)并入集合TE,同时将v0并入U

    c)重复b直到U=V为止,此时TE中必含有n-1条边,则T=( V,{TE})N的最小生成树。

 

4、拓扑排序

有向无环图Directed Acyclic Graph是指一个无环的有向图,简称DAG。我们一般用顶点表示活动,用弧表示活动间的优先关系的有向无环图,称为顶点表示活动的网Activity On Vertex Network,简称AOV-网。

在有向图G=(V,{E})中,V中顶点的线性序列(v1,v2,…,vn)称为拓扑序列。如果此序列中任意两个顶点vivj,在G中有一条从vivj的路径,则在序列中vi必排在vj之前。

现已知AOV-网的特性如下:

1、  AOV-网中不能存在回路,否则回路中的活动就会互为前驱,从而无法执行。

2、  AOV-网的拓扑序列是不唯一的。

为求有向无环图的拓扑序列,就是拓扑排序问题Topological Sort。其基本思想为:

1、  从有向图中选一个无前驱的结点数出。

2、  将此结点和以它为起点的弧删除。

3、  重复12,直到不存在无前驱的结点。

4、  若此时输出的结点数小于有向图中的结点数,则说明有向图存在回路,否则输出的顶点顺序即为一个拓扑序列。

 

5、 关键路径

有向图通常被用来表示工程计划时有两种方法:

1、  用顶点表示活动,即AOV-网;

2、  用顶点表示事件,用弧表示活动,弧的权值表示活动所需要的时间。

把第二种方法构造的有向无环图称为边表示活动的网Activity On Edge Network。简称AOE-网。

    AOE-网中存在唯一的、入度为0的顶点,叫做源点。存在唯一的,出度为0的点,叫做汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需要的时间,该路径叫做关键路径,关键路径上的活动称为关键活动。

    求关键路径的基本步骤如下:

1、  对图中顶点进行拓扑排序,在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)

2、  按逆拓扑序列求每个事件的最晚发生时间vl(i)

3、  求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)

4、  找出e(i)=l(i)的活动ai,即为关键活动。

 

6、 最短路径问题

 

所谓最短路径Shortest Path问题是指:从在带权图的某一个顶点(称为源点)出发,找出一条通往另一顶点(称为终点)的最短路径。所谓“最短”,也就是沿路径各边的权值达到最小。

最短路径问题分为以下三种情况表示:

1、  非负权值的单源最短路径

求此类型的最短路径,经典算法是由计算机大拿Dijkstra提出的按路径长度的递增次序确定最短路径的Dijkstra算法。

2、  任意权值的单源最短路径

假设有向带权图某条边的长度为负,那么根据Dijkstra算法,结果并不正确。为了求解这种情况下的最短路径问题,BellmanFord提出了从源点逐次绕过其他顶点,以缩短到达终点的最短路径长度算法。该方法有一个限制条件,即有向图中不能包含带有负值边的回路。

3、  所有顶点之间的最短路径

对于一个各边权值均大于0的有向带权图,求出所有顶点之间的最短路径和最短路径长度,一个办法是轮流以每个顶点为源点,重复执行Dijkstra算法n次,就可求得每一对顶点之间的最短路径和最短路径长度。

为了使算法结构更为清晰,Floyd算法实现了这一要求,尽管其时间复杂度上与前者相当。

Floyd算法使用图的邻接矩阵Edge[n][n]来表示有向带权图。算法的基本思想是,设置一个n阶方阵A,其中除对角线的矩阵元素为0外,其他元素a[i][j]表示从点vivj的有向路径长度。在vivj间插入v0v1直到n-1次,每步比较前者和后者的长度,并取较短的路径作为中间顶点号不大于0的最短路径。最终得到的必是vivj的最短路径。事实证明Floyd算法在逻辑上更符合题设的要求。

 

在今后的连载中,我们会特别针对图的六个核心应用问题进行专题讨论,并且陆续放出相关算法的最终代码。

至此,简单数据结构部分的内容就全部讨论完毕。这些结构都是被经常用在各种程序设计当中,并被作为程序设计的核心问题之一。

    接下来的连载,除了开辟必要的两篇来丰富和总结前面的不足之外,我们会进入简单算法设计部分的讨论,这些算法都是基于上述十四篇连载的内容而来,使数据结构的实际应用更加深入了一步。

 

(未完待续)

Comments

假期连载之十三

(图—图的基本概念、ADT、存储结构表示)

 

    graph部分涉及到了许多离散数学方面的理论知识,因此本节需要读者具备一定的离散数学背景—当然,重要的概念和性质我们会附带说明。图是一种更为灵活复杂的非线性结构,理论上讲它比树的实用性更强,但算法设计的复杂度上也存在很大提升。图最典型的应用领域有电路分析、寻找最短路线、项目规划、鉴别化合物、统计力学、遗传学、控制论、语言学以及一些社会科学。

 

    图的基本概念

 

    图是一种网状数据结构,其形式定义如下:

    Graph=(V,R);

    V={x|x属于DataObject};

    R={VR};

    VR={<x,y>|P(x,y)(x,y属于V)};

    其中DataObject是一个数据集合,其中所有的元素都具有相同的特性。V中的数据元素通常称为顶点VertexVR是两个顶点之间的关系的集合,P(x,y)表示xy之间有特定的关联属性P

    若有VR内的元素<x,y>,则其表示从顶点x到顶点y的一条Arc,并称x弧尾Tail或起始点,称y弧头Head或终端点,此时图中的边是有方向的,称这样的图为有向图

若有VR内的元素<x,y>,必有<y,x>,即VR是对称关系,这时用无序对的表示方法来代替两个有序对(x,y),表示xy之间的一条边,此时的图称为无向图。

 

n表示图中的顶点个数,用e表示图中边或弧的数目,且不考虑图中每个顶点到其自身的边或弧。对于无向图而言,如果e=n(n-1)/2,则称其为无向完全图,对应的有向图被称为有向完全图。对于e<nlogn的图称为稀疏图,否则称稠密图

子图是指一个图的顶点结构和关联不发生改变,只存在其中一部分的图。在无向图G=(V,{E})中,如果边(v1,v2)属于E,则称v1v2互为邻接点,并且边(v1,v2)依附于顶点v1v2,或者说边与v1v2相关联。而对于有向图而言,如果存在弧<v1,v2>属于A,则称顶点v1邻接到顶点v2,顶点v2邻接自顶点v1,或者说弧<v1,v2>与顶点v1v2相关联。

是指与顶点v关联的边数,记作deg(v)。在有向图中顶点为弧头则称其为入度ID(v),为弧尾则称其为出度OD(v),顶点的入度的数目必然和出度相等。

在实际应用中,往往赋给边或弧一定的数值,成为。这种带权信息的图被称为赋权图

路径是指任意两个顶点之间沿边或弧方向的顶点序列。如果G是有向图,则其路径也是有向的。在一个路径中,如果第一个顶点和最后一个顶点相同,则称该路径为一个回路。若表示路径的顶点序列中的顶点各不相同,则称这样的路径为简单路径。除第一个和最后一个顶点外,其余个顶点均不重复出现的回路称为简单回路

在无向图G中,如果从vivj有路径相通,则称其是连通的。如果对于任意两个顶点均是连通的,则图被称为连通图。无向图的极大连通子图被称为无向图的连通分量。而对有向图而言,如果对于每对顶点,都有互相连通的路径,则称其为强连通图,它的极大连通子图被称为强连通分量

现在给出图的抽象数据类型定义:

ADT Graph

{

    数据对象V:一个集合,集合中所有元素有相同的特性

    数据关系R:R={VR};

    基本操作:

    CreateGraph(G);         //创建图G

    DestoryGraph(G);        //销毁图G

    LocateVertex(G,v);      //若存在顶点v,则返回v的位置,否则返回NULL

    GetVertex(G,i);         //返回G中顶点v的第i个顶点的值

    FirstAdjVertex(G,v);    //返回G中顶点v的第i个邻接点的值

    NextAdjVertex(G,v,w);   //返回返回G中顶点v的下一个(w个后面)邻接点的值,如果w为最后一个邻接点,则返回NULL

    InsertVertex(G,u);      //添加一个点u

    DeleteVertex(G,v);      //删除图中的顶点v以及相关联的弧

    InsertArc(G,v,w);       //向图中添加一条从v指向w的弧

    DeleteArc(G,v,w);       //删除图中从v指向w的弧

    TraverseGraph(G);       //遍历图G

}

 

图的基本存储结构

 

现在,我们按照图的性质,介绍四种常用的存储表示法。大体上来说依然为顺序存储和链式存储两种类型。

1、 图的邻接矩阵表示

邻接矩阵adjacency matrix表示法实际上就是数组表示法。它采用两个数组来表示图:一个是用于存储顶点信息的一维数组,另一个是用于存储图中顶点之间关联关系的二维数组,这个关联关系数组被称为邻接矩阵

在储存关联关系的二维数组中,1代表了无权图中两顶点间路径连通,0则反之,其阶为顶点个数。

邻接矩阵表示的特点如下:

a)存储空间方面,对无向图而言,其邻接矩阵为对称矩阵,因而可采用相关的压缩存储法。但对于有向图而言,由于顶点间不一定互相连通,因此需要n^2个存储空间。

b)便于计算,由于采用了数组表示,关于图中顶点的基本运算就相对简便。综合而言,邻接矩阵不适合存储稀疏图。

    2、邻接表表示法

    邻接表adjacency matrix吸取了邻接矩阵的优点,同时凭借链式结构的特点对上述方法做出改进,在节省存储空间上起到了很大作用。邻接表对图中每个顶点建立一个带头结点的边链表。

表头结点有两部分构成:数据域vexdata以及链域firstarc,用于指向链表中第一个顶点。对于边表,由表示图中顶点间邻接关系的n个边链表构成。因而结点在包括了上述两个结点域之外,还附带一个邻接点域adjvex,用于存放与该点相邻的顶点在图中的位置。

邻接表虽然进一步节省了存储空间,但在一些基本运算过程中,例如求某个顶点的入度,则必须遍历整个邻接表,在时间复杂度上并不如邻接矩阵优异。

为了解决一些计算上的问题,还可以另外设置一个逆邻接表,就可以满足一些常用运算的需要。

3、正交链表(十字链表)

正交链表Orthogonal Lists有向图的另一种存储结构,它在邻接表表示法所不擅长的有向图运算领域做到了很好的效果。其实质是将邻接表和逆邻接表结合起来形成的一种链表。

正交链表的弧结点结构包括了tailvex弧尾顶点位置、headvex弧头顶点位置、hlink指向与此弧的弧头相同的下一条弧、tlink指向与此弧的弧尾相同的下一条弧、info该弧的相关信息。

其顶点结点包括了data数据域、firstin指向该顶点作为弧头的第一个弧结点、firstout指向该顶点作为弧尾的第一个弧结点。

4、 邻接多重表

邻接多重表Adjacency Multi_list无向图的另外一种存储结构。这种结构相较于邻接表来说结构复杂,运算算法难度较高,但在处理无向图的边信息时却大大节省了算法时间,是一种高效的无向图存储表示。

其边结点的结构包括了mark标记该条边是否已被搜索、ivex/jvex为该边依附的两个顶点在图中的位置、ilink指向下一条依附于顶点ivex的边、jlink指向下一条依附于顶点jvex的边、info边信息。

顶点结点结构包括了data数据域、firstedge指向第一条依附于该顶点的边。

以上四种存储策略分别适用于不同的需求环境,具体应采取何种存储结构应按照实际情况而定。为统一起见今后我们涉及到图的基本运算时,一般以邻接矩阵和邻接表这两个基本结构为例。

 

(未完待续)

Comments

假期连载之十二(100)

(树形结构—树和森林、哈夫曼树)

 

    本篇为12号的第三篇连载,基于时间、理论连贯性上的考虑,我们利用下午的时间完成了前两篇关于树的基本概念及其ADT,二叉树及其相关等内容,现在我们介绍树形结构对基础概念的扩展—一般树,以及森林。最后我们会研究一种特殊的二叉树结构,它通常被人称为最优二叉树,是信息传输、数据压缩领域的重要工具。

   

    树、森林和二叉树的关系

 

    在一般树的条件下,分支个数是不定的,因此会出现所谓的多叉树。对于这种一般的树,我们就需要采用一种不同于二叉树二叉链表的存储表示。

1、 广义表表示法

广义表表示树是一种非常有效的方法,树中结点可以分三种:叶结点、根结点以及除根结点之外的其它非叶结点(也称分支结点)。因此在广义表中也可以有三种结点与之对应:原子结点、表头结点、子表结点。

在子表结点内部,我们同样使用从上至下、从左至右的顺序对结点进行排序。其运算也是基于广义表的基本运算进行的。

我们在前面的连载中介绍了广义表的头尾链表和扩展线性链表等存储表示方法,并附加了相关基础运算,但必须注意的是,广义表在一些高级语言中能够特别方便地使用,这也是这种数据结构诞生的初衷,因此在其它高级语言中应尽量在实际应用中避免采用这种并不擅长的方式进行运算。

2、 父指针表示法

利用一组连续的空间来存储树中的结点,在保存每个结点的同时附设一个指示器来指示其父结点在表中的位置。这种结构易于求指定结点的父结点,但当求某结点的子女结点时需遍历结构数组。

3、 子女表示法

这种方法通常是把每个结点的子女结点排列起来,构成一个单链表,称其为子女链表。n个结点共有n个子女链表,其中叶子结点的子女链表为空。而n个结点的数据和n个子女链表的头指针又组成一个顺序表。这种结构适合需要频繁寻找子女结点的应用,并可以和父指针表示法结合,使寻找父结点或子女结点都很方便。

4、 子女-兄弟表示法

这种方法是一种二叉树表示法,也被称为二叉链表表示法。其链表结点中包含三个结点域,分别指向该结点的第一个子女结点指针,指向下一个兄弟结点指针以及数据域。这种存储结构首先比较清晰地描绘了树形结构的容貌,同时非常方便实现树的各类操作。与以上三种表示法相比,子女兄弟表示法既在操作上容易实现了许多,且在空间和时间的效能上也具有一定优势。

 

根据子女兄弟表示法的启示,我们发现一般树和二叉树均可以用二叉链表进行表示,换一个角度说,我们可以通过一定转换,将一般树按原二叉链表表示的序列转化为二叉树形式,且并不影响对树进行的各种基本运算的结果。

1、 树转换为二叉树

将一棵树转换为二叉树的方法是,将树中的所有兄弟结点之间加一条连线,对树中的每个结点,只保留其与第一个子女结点之间的连线,删去其与其它子女结点之间的连线。最后以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构层次分明。

可以证明,通过这种方法树转换成的二叉树是唯一的。而且此时二叉树的链表表示与树本身的子女-兄弟表示法所生成的二叉链表完全一致,这时就可以展开对树的各种基本操作。

2、 森林转换为二叉树

森林是若干树的集合。那么采用如下方法可以将森林转换为二叉树表示:首先将森林中的每棵树转换成相应的二叉树,第一棵二叉树不动,从第二棵二叉树开始依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右子结点,当所有二叉树连在一起后,得到的二叉树即是由森林转换得到的二叉树。

3、 二叉树还原为树或森林

树转换成的二叉树,其特点是必无右子结点,而森林转换成的二叉树,其必含右子结点。根据以上特征区分还原的对象。然后按照以下方法还原二叉树:若某结点是其父结点的左子结点,则把该结点的右子结点、右子结点的右子结点、均与该结点的父结点用线连接起来。此时删除掉原二叉树中所有父结点与右子结点的连线,并加以整理即可。

 

树与森林的遍历

 

基于前面建立的子女兄弟存储表示,我们可以得出树和森林的一般遍历算法,它们与二叉树的相关遍历算法有很深厚的联系。

从大方面看,树与森林的遍历分为深度优先遍历和广度优先遍历两种。

1、  深度优先遍历是一种与二叉树遍历类似的遍历算法

a)       树的先根遍历算法,类似于二叉树遍历的先序顺序。其结果与直接用先序遍历算法所演示的结果是相一致的。

b)       后根遍历,实际上类似于二叉树遍历的后序顺序。

我们以树的递归先根次序遍历算法为例,给出具体编程实现先根的两种方法:

if(root!=NULL)

{

    Visit(root->data);

    p=root->FirstChild;

    while(p!=NULL)

    {

        RootFirst(p);       //访问以p为根的子树

        p=p->nextSibling;

}

 

}//以上是方法一

if(root!=NULL)

{

    Visit(root->data);

    RootFirst(root->FirstChild);

    RootFirst(root->NextSibling);

}//方法二消除了循环,也以递归的方式呈现

    对于森林的遍历,一般也分先序遍历、中序遍历以及后序遍历,值得注意的是在森林的后序遍历中第一棵树的根结点应放在最后访问,以后其它各树的根结点依次倒数访问,这点需特别留意。

    2广度优先遍历是一种新的遍历方法,它是以结点的序号排列为顺序直接遍历的。在这种算法中并不存在递归结构,通常使用队列的方法,扫描至每一层时,将该层的所有结点入队,然后依次访问。

   

    哈夫曼树

 

    哈夫曼树Huffman Tree又称最优二叉树,是一类加权路径长度最短的二叉树。其在编码设计、决策和算法设计等领域有着广泛的应用。我们大家现今经常使用的图像格式JPEG,就是一种基于DCT(离散余弦变换)和哈夫曼编码的有损高压缩比编码标准。

   

    我们首先给出哈夫曼树的一些概念。

    路径path,指从树中一个结点到另一个结点之间的分支构成该两点之间的路径。

    路径长度path length,指路径上的分支条数。树的路径长度一般指树的根结点到每个结点的路径长度之和。

    由树的定义可知,从根结点到达树中的每一个结点有且仅有一条路径。若设树的根结点位于第1层,某结点处于第k层,则其路径上的分支条数为k-1,因此从根结点到其它各个结点的路径长度等于该结点所处的层次k-1

    一般来说,当结点数相同时,越接近完全二叉树的结构其路径长度越短。

 

    定义一个带权路径长度Weighted Path Length(WPL),假设有n个权值的集合中,若T是一棵有n个叶结点的二叉树,且将集合中的权值分别赋给Tn个叶结点,此时我们称T是权值为相关值的扩充二叉树。带权结点被称为外结点,其余结点被称做内结点。外结点的带权路径长度为从T的根到该结点的路径长度与该结点上权值的乘积。此时将整个扩充二叉树的带权路径长度定义为WPL,就是每个外结点带权路径长度之和。

    我们把WPL最小的扩充二叉树称为最优二叉树。在这种情况里,最小带权路径长度的扩充二叉树就不再一定是完全二叉树。从直观上看,最优二叉树应该是权值大的外结点离根结点越近的扩充二叉树,就是Huffman树。

   

    构造哈夫曼树

 

    构造哈夫曼树的算法是由Huffman提出的,其基本思路为:

1、  根据给定的n个权值,构造具有n棵扩充二叉树的森林,其中每一棵二叉树都有一只权值为相关值的根结点,其左右子树为空。

2、  找最小树,在森林中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左右子树,标记新二叉树的根结点权值为其左右子树的根结点权值之和。

3、  删除与加入,从森林中删除被选中的那两棵二叉树,同时把新构成的二叉树加入到森林中。

4、  判断,重复23步骤,直到森林中只含有一棵二叉树时为止。

 

程序构建哈夫曼树,首先须确定一个静态三叉链表的结点结构,这种结点由四个域构成:分别是权值域、父结点序号、左子结点序号以及右子结点序号。为了计算方便,0号单元不用,从1号开始使用,程序也按照静态链表的构建方法进行。

 

哈夫曼编码

 

构造哈夫曼树的实质还是为了求哈夫曼编码。通常计算机中存储的图形符号是以二进制码进行处理的。例如ASCII码就是一种8位二进制编码,且还是一种定长编码。为了压缩数据存储空间,有必要采用不定长编码的方式进行编码。首先介绍几个概念:

1前缀码,如果在一个编码系统中,任一个编码都不是其它任何编码的前缀(即最左子串),则成该编码系统中的编码是前缀码。例如一组编码01001010100110就不是前缀码,因为01010的前缀,去掉其中之一后即为前缀码。

如果采用前缀码,我们就可以在各字符对应的编码之间不需要分隔符。如果非前缀码,不使用分隔符则会产生二义性。

2哈夫曼编码,对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的通路上,各分支的赋值分别构成一个二进制串,该二进制串即位哈夫曼编码。

 

求解哈夫曼编码的方法也有很多,一般而言,我们首先根据带权结点构建哈夫曼树,此时将哈夫曼树的左分支标记为0,右分支标记为1,根结点不计,我们从根结点出发,把抵达相关叶结点的路径按先后顺序编码,则就构成了哈夫曼编码。

在实际编程中,对01的赋值是在求编码的算法中直接进行判断的。

 

 

(未完待续)

Comments

假期连载之十一

(树形结构—二叉树)

 

    这是12号发布的第二篇连载,为了突出树形结构的重要性,以及方便对该部分内容的整理工作,故将本节内容分段进行发布。同时为了突出树的应用性,我们可能会在这两天进行一个关于前阵时间讨论过的迷宫问题扩展的研究,由于时间制约不一定会准时放出。

 

二叉树

 

二叉树Binary tree是一类特殊且重要的树形结构,其原因在于:

1、  二叉树是树形结构中相对最简单的一种结构;

2、  其它非二叉树结构的树均可以转化为二叉树进行处理;

3、  二叉树是最方便于计算机进行处理的树形结构。

一般地,二叉树是指满足下列两个条件的树形结构:

1、  每个结点的度都不大于2

2、  每个结点的子女结点的次序不能任意颠倒。

由此可以看出,一个二叉树中的每个结点只能含有012个子结点,同时每个子结点有左右之分,且左右子结点的次序不能颠倒。

根据二叉树的定义,我们可以给出二叉树的五种基本形态,包括空二叉树、只有根结点的二叉树、只有做子树的二叉树、只有右子树的二叉树、左右子树均非空的二叉树。综上我们得出二叉树具有以下5种性质:

1、  在二叉树的第i层上至多有2^(i-1)个结点,其中i>=1

2、  深度为k的二叉树至多有2^k-1个结点,其中k>=1

3、  对于任意二叉树T,若终端结点数为n0,而其度数为2的结点数为n2,则n0=n2+1

下面两条性质是针对某些特殊二叉树的,它们定义为:

满二叉树full binary tree,深度为k的满二叉树是有2^k-1个结点的二叉树,在每一层中其结点数都达到了最大个数。

完全二叉树complete binary tree,如果一棵具有n个结点的深度为k的二叉树,它的每一结点都与高度为k的满二叉树中编号为1n的结点一一对应,则称这棵二叉树为完全二叉树。

完全二叉树所不同的是,1n必须是连续对应的,但允许尾部并不完整,这说明满二叉树一定是完全二叉树,但完全二叉树并不一定是满二叉树。

4、  具有n个结点的完全二叉树的深度为log2(n)+1

5、  对于具有n个结点的完全二叉树,如果按照从上至下、从左至右的顺序对二叉树中所有结点从1开始顺序编号,则对于任意序号为i的结点有:

a)       i=1,则序号为i的结点是根结点;

b)       如果2*i>n,则序号为i的结点无左子结点;

c)       如果2*i+1>n,则序号为i的结点无右子结点。

 

二叉树的存储结构

 

二叉树同样可以分别用顺序存取结构和链式存储结构来表示,但其优缺点是非常明显的。

在顺序存储结构中,假设二叉树T为完全二叉树,则其结点编号对于满二叉树来说是连续的,因此可以依据其结点编号作为一维数组下标,这是一种既简单又节省空间的存储方式。

但大多数情况下T可能并不会处于上述特殊状态中,仅仅是一般定义上的二叉树结构。此时如果需要使用顺序存储结构,依然根据结点编号进行存储,但在缺少子结点或兄弟结点的地方必须按照完全二叉树进行处理,并将空缺的元素留空。这就造成了存储空间上的浪费,且无法进行有效的压缩存储。

    这时链式存储就显示出了极大的优势。二叉树的结点包括了三个域:leftChild左子结点指针、data数据域、rightChild右子结点指针。同时为了能使二叉树进行逆序操作,还可以再添加一个parent父结点指针,这就是二叉树的三叉链表表示。

    这里给出二叉链表的结点结构C语言描述:

    typedef struct Node

{

    DataType data;

    struct Node *LChild;

    struct Node *RChild;

    //struct Node *Parent;  父结点指针要看实际需要或改变为三叉链表

}BiTNode,*BiTree;

 

二叉树的遍历与应用

 

二叉树的遍历是二叉树中进行查询、修改、增删等众多运算的基础,其实质上是将二叉树中结点按一定规律线性化的操作,目的在于将非线性化结构变为线性化的访问队列。

我们令LRV分别表示一个结点的左子树、右子树和访问该结点的操作,据此可以总结出六种遍历顺序:LRVLVRRLVRVLVRLVLR,我们一般规定按照先左后右的顺序,以访问结点操作为标准得出以下三种基本规则:VLR先序遍历、LVR中序遍历、LRV后序遍历。

这里仅给出二叉树中序遍历算法的C++泛型应用:

template<class T>

void BinaryTree<T>::InOrder(BinTreeNode<T> *subTree,void(*visit)

(BinTreeNode<T> *p)){

        if(subTree!=NULL)

        {

            InOrder(subTree->leftChild,visit);

            visit(subTree);

            InOrder(subTree->rightChild,visit);

}

};

可以看出,以上二叉树的遍历运算都是基于递归的方式来进行的,而其它两种运算和上面仅仅存在递归顺序的差异。

    利用二叉树的递归遍历,我们可以进行很多相关基本运算。例如扩展先序遍历序列来创建二叉链表达到存储二叉树的目的:

    void CreateBiTree(BiTree *bt)

    {

        char ch;

        ch=getchar();

        if(ch==’.’)

            *bt=NULL;

        else

        {

            *bt=(BiTree)malloc(sizeof(BiTNode));

            (*bt)->data=ch;

            CreateBiTree(&((*bt)->LChild));

            CreateBiTree(&((*bt)->RChild));

}

}

    现在我们以后序遍历举例,求二叉树深度的递归算法:

    int PostTreeDepth(BiTree bt)

    {

        //需要注意根结点的高度算1,若二叉树为空则其高度为0

        int hl,hr,max;

        if(bt!=NULL)

        {

            hl=PostTreeDepth(bt->LChild);

            hr=PostTreeDepth(bt->RChild);

            max=hl>hr?hl:hr;    //按定义深度为所有结点层次的最大值

            return max+1;

}

else

return 0;

}

 

二叉树遍历的非递归算法

 

二叉树遍历要消除递归,则需采用工作栈的方式保持其回溯的能力。同时根据三种遍历顺序的不同,结点入栈的顺序也不尽相同。但参考连载五迷宫A中我们给出的递归消除方案,二叉树遍历的递归消除其实是较为简单的了。

这里给出中序遍历二叉树的非递归算法,这里使用了具有栈定义的简单SDK,其结点定义为BiTNode

void InOrder(BiTree root)

{

    BiTNode *p;

    InitStack(&S);

    p=root;

    while(p!=NULL||IsEmpty(S))

    {

        if(p!=NULL)

        {

            Push(&S,p);

            p=p->LChild;

        }

        else

{

    Pop(&S,&p);

    Visit(p->data);

    p=p->Rchild;

}

}

}

这里需要额外注意,在使用后序遍历的非递归运算时,会发现由于根结点无论如何也是最后被访问,因而判断何种情况下访问栈顶根结点也会成为一道障碍。我们按照以下步骤进行操作:

从根结点开始若当前结点存在,且栈不为空,则重复以下操作:

1、  从当前结点开始,入栈并走左子树,直到左子树为空;

2、  如果栈顶结点的右子树为空,或者栈顶结点的右子结点为刚访问过的结点,则退栈并访问该结点,然后将当前结点指针置空;

3、  否则走右子树,并重复上述步骤。

 

线索二叉树

 

我们知道,对于二叉链表作为二叉树的存储结构,假设有n个结点的二叉链表中共有2n个链域,但有用的非空链域仅为n-1个,其它n+1个链域均为空,这些空间是被浪费的。

同时在遍历二叉链表时,我们如果要求一个结点的前驱和后继,就必须不断调用遍历函数,其效率上也存在一些问题。因而我们需要一种方案一次解决上述两种问题,事实证明这是可行且有效的。

LChildRchilddata域之外,再给二叉链表结点添加两个整形标志域LtagRtag,它们的具体用法如下:当结点有左子树,则LChild指向左子结点,且Ltag0,当结点不含左子树,则LChild指向其前驱结点,此时Ltag1;相对于结点的右子树有同样定义,不过Rchild会指向结点的后继结点。

具体的前驱/后继仍然会按照三种基本的遍历顺序进行区分,这就是线索二叉树。其中标志域为1时的LChildRchild指针被称为线索,该链表结构也被称为线索链表,对普通二叉树进行遍历并添加线索的过程称为线索化二叉树。线索化了的二叉树称为线索二叉树。

 

    现在我们以二叉树中序线索化为例,说明二叉树线索化的一般算法:

    void Inthread(BiTree root)

    {   //pre始终保证指向刚访问过的结点,其初值为NULL

        if(root!=NULL)

        {

            Inthread(root->LChild);

            //以下为加线索操作

            if(root->LChild==NULL)

            {

                root->Ltag=1;

                root->LChild=pre;

}

if(pre!=NULL&&pre->Rchild==NULL)

{

    pre->Rchild=root;

    pre->Rtag=1;

}

pre=root;

Inthread(root->RChild);

}

}

线索二叉树非常有利于寻找指定结点p的前驱或后继结点,例如在中序线索树中,寻找前驱的一般方法是当Ltag==0,则返回左子树最后一个访问的结点。

同时对于线索树的遍历,也有不同于一般二叉树遍历算法的方法:首先须求出某种遍历次序下第一个被访问的结点,然后连续求出刚访问结点的后继结点,直至所有结点均被访问。我们以中序遍历中序线索树为例:

BitNode *InFirst(BiTree Bt)

{

    //这是被调用的寻找中序遍历的第一个结点函数

    BiTNode *p=Bt;

    if(!p)

        return NULL;

    while(p->Ltag==0)

        p=p->LChild;

    return p;

}

遍历中序线索二叉树:

void TinOrder(BiTree Bt)

{

    BiTNode *p;

    p=InFirst(Bt);

    while(p)

    {

        Visit(p);

    p=InNext(p);    //InNext()实质上是寻找中序线索树的结点后继的函数

}

}

 

现在我们讨论线索二叉树的最后一个问题,即当对线索树进行插入、删除操作时,可能会破坏原有树的线索,因此其难点就不言而明:如何在结点个数发生变化时保持正确的线索。

在插入结点运算中,有插入左子结点和插入右子结点的区别,但后者明显比前者复杂,因此我们仅提供后者插入运算的分析。

当执行插入线索二叉树某结点的右子结点时也分两种情况:

1、结点的右子结点本身为空,此时插入新结点的过程很简单,且对前驱后继的关系没有任何影响。

2、若其右子结点不为空,则插入后新结点为原右子结点的父结点,此时需要修改原来父结点右子树中最左下端结点的左指针值,使其指向新结点,从而满足前驱后继关系。

当进行删除操作时,其原理和插入结点是互逆的,例如在中序线索树中删除结点右子结点,则需将父结点右子树的最左下端结点的左指针重新指向父结点。

 

(未完待续)

Comments

假期连载之十

(树形结构—树的基本概念及抽象数据类型)

 

    树形结构的亮点在于其应用广泛。尽管本节仅介绍概念以及理论上的内容,但无论如何都不能忽视对实际应用的渗入,否则将失去其本身研究的意义。

 

    树的基本概念

 

    在计算机科学中,树作为组织信息的重要形式之一,代表了非线性数据结构的一般特征。这里有两种基本的树,一种被称为自由树free tree

    自由树指定义一个二元组Tf=(V,E),其中V={v1,v2,…,vn}是由n个结点构成的优先集合(n>=0),称为顶点集合vertexvi称为顶点,其中1<=i<=nE={(vi,vj)|vi,vj属于V,且i>=1,j<=n}是由n-1个元素组成的序对集合,称为边集合。E中的元素(vi,vj)为边edge的分支branchE使得Tf成为一个连通图。综上可知,自由树的概念类似于图,且对其讨论的范围仅限于图论部分的内容,本文不作涉及。

    另一种树称为有根树rooted tree。一棵有根树T,简称为树,它是由n>=0个结点的有限集合。当n=0时,T称为空树,否则T是非空树,记作:

       Φ,          n=0

T={r,T1,…,Tn},n>0

其中rT的一个特殊结点,称为根rootT1,…,Tn是除r之外其它结点构成的互不相交的m>=0个子集合。每个子集合也是一棵树,称为根的子树subtree

每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继,m称为r的分支数。

 

    在计算机系统和其它领域中,树的表示方法不尽相同。基本上有以下几种方法:

1、  倒置树结构,即最常用的树形表示方法。

2、  文氏图表示法,使用嵌套集合的形式。

3、  广义表形式,即嵌套括号的表示方法。

4、  凹入表示法,用位置的缩进表示其层次,如目录表的编排格式。

 

树的一些基本术语

 

结点node,包含一个数据元素及若干指向其它结点的分支信息。

结点的度degree,是一个结点所拥有的子树的棵数。

叶结点leaf,指度为0的结点,也称为终端结点。

分支结点branch,除叶结点以外的其它结点,也称为非终端结点。

结点层次level,从根结点开始,根结点层次为1,根结点的直接后继层次为2,依次类推。

结点的层序编号No.of node,是指按从上层到下层,同层从左至右的顺序对结点以自然数编号。

树的度degree,树中所有结点度的最大值。

树的高度height,树中所有结点层次的最大值。

有序树ordered tree,在树T中,若各子树Ti之间是有先后次序的,称为有序树。

森林forest,指m>=0棵不相交的树的集合。

同构isomorphism,对于两棵树,通过对结点适当地重命名,就可以使两棵树完全相等,则称这两棵树同构。

为了描述结点之间层次关系,我们还借助人类家族术语进行定义:

子女结点child,一个结点的直接后继称为这个结点的child

父结点parent,一个结点的直接前驱称为这个结点的parent

兄弟结点sibling,同一双亲结点的子女结点之间互称为sibling

祖先结点ancestor,一个结点的祖先结点是指从根结点到该结点路径上的所有结点。

子孙结点descendant,一个结点的直接后继和间接后继称为该结点的子孙结点。

另外,按照结点序号的大小,结点又可以前辈、后辈表示,父结点为兄弟结点的子女结点之间互称为堂兄弟结点。

 

树的抽象数据类型

 

ADT Tree

{

数据对象D:一个集合,该集合中的所有元素具有相同特性

    数据关系R:见树的定义

    基本操作:

    InitTree(Tree);             //初始化Tree为空树

    DestoryTree(Tree);          //销毁树

    CreateTree(Tree);           //创建树Tree

    TreeEmpty(Tree);            //Tree为空,返回TRUE,否则返回FALSE

    Root(Tree);                 //返回树Tree的根

    Parent(Tree,x);             //Tree存在,xTree中的某个结点,若x为非根结点,则返回其父结点,否则返回空

    FirstChild(Tree,x);         //Tree存在,xTree中的某个结点,若x为非叶结点,则返回其第一个孩子结点,否则返回空

    NextSibling(Tree,x);        //Tree存在,xTree中的某个结点,若x为不是父结点的最后一个子女结点,则返回其下一个兄弟结点,否则返回空

    InsertChild(Tree,p,Child);  //Tree存在,p指向Tree中的某个结点,非空树ChildTree不相交,将Child插入Tree中,其中p是该子树的根结点

DeleteChild(Tree,p,i);      //Tree存在,p指向Tree中的某个结点1<=i<=ddp所指向结点的度,删除Treep所指向结点的第i棵子树

TraverseTree(Tree,Visit()); //Tree存在,Visit()是对结点进行访问的函数,按照某种次序对Tree的每个结点调用Visit()函数最多访问一次,若Visit()失败,则操作失败

}

鉴于树结构重要性,我们将本块内容分成多个连载分别进行讨论,方便读者进行整理。

 

(未完待续)

Comments

假期连载之九

(数组和广义表)

 

    本节介绍线性表的两个推广结构—数组和广义表,这也是线性结构和表结构部分最后两个重要内容。

 

    数组

 

    我们在介绍线性表基本存储结构时曾提到数组,这是因为在大多数高级程序设计语言中,数组即被用来表示一段连续的存储空间,它对一般线性表的概念和原理起到了很好的诠释作用。但是,在很多工程领域中,数组并不单以一维数组的形态出现,我们大量接触到了二维甚至是三维数组,它们通常是计算机图形学、工业设计、医疗等领域的计算工具。

    本部分内容重点介绍多维数组的计算及其内部存储实现。

    数组是由下标index和值value组成的序对的集合。在数组中,每个有定义的下标都有一个值对应,这个值被称作数组元素。前面的讲解中曾介绍过C++独特的静态数组和动态数组,在其它一些高级语言中数组的定义也是大同小异,例如在Visual Basic中还可以定义变长的数组。

    二维数组,其数学模型实际上就是矩阵。相对于一维数组给定下标值即可唯一确定一个元素,以及该元素的直接前驱和直接后继,二维数组需要同时给定两个下标值,且其直接前驱分为x向和y向两类。例如对于二维数组a[m][n],元素a[j][k]的直接前驱分别为a[j-1][k]a[j][k-1],其直接后继分别为a[j+1][k]a[j][k+1]。因此可以把二维数组可以看作最简单的非线性结构。

    对于任意三维数组a[m][n][o],我们先将a看作一维数组a[m],其中任意元素a[j]中还存在一个二维数组,相应地,其直接前驱和直接后继就有三个。上述结论推广至n维数组,其直接前驱与后继个数即为n

   

    多维数组的存储表示

 

    多维数组之所以复杂,是因为在计算机存储内部并没有真正涉及到多维数组存储,其存储表示是基于一维数组来实现的。

    一般地对于一维数组a[n],若设它的第一个数组元素的存储起始地址为a,每一个数组元素的存储大小为l,则任一数组元素的存储地址LOC(i)可以用如下的递推公式计算:

            a       ,i=0

    LOC(i)={LOC(i-1),i>1

    因此有:LOC(i)=LOC(i-1)+l=a+i*l

    对于二维数组a[n][m],为能根据它们的数组元素的下标计算出在相应一维数组种对应的下标,需要区分两种存储方式,即行优先顺序和列优先顺序。

    按照行优先顺序,所有数组元素按行向量排列,第i+1个行向量紧跟在第i个行向量后面,这样得到数组元素存于一维数组的一种线性序列。这种行优先策略被使用在如ALGOLPASCALC/C++BASICAda等多数高级语言中。

相应地,存在一种按列优先的顺序,所有数组元素按列向量依次排列。FORTRAN语言即是以此为策略实现二维数组的。

现在我们以行优先顺序为例,讨论二维数组地址的映射方法。

设二维数组a[n][m]的第一个元素a[0][0]存于相应一维数组的第一个位置,其地址为a,每个元素占1大小的空间,根据一维数组元素a[j][k]地址计算公式:

LOC(j,k)=LOC(j,0)+k

        =LOC(j-1)+m+k

       

        =LOC(0,0)+j*m+k

        =a+j*m+k

以上就是二维数组对一维数组元素地址的映射公式。

对于三维数组a[m][n][o],其优先顺序就不简单地判定为“谁优先”的问题,而是分优先级别。假设m为页号,no分别为页内二维数组的行列号,则有页最优先,其次为行优先的策略,同样可能共有六种不同的顺序。我们先以第一种策略为例计算其对一维数组元素地址的映射公式:

LOC(i,j,k)=LOC(i,0,0)+j*o+k

          =LOC(i-1,0,0)+n*o+j*o+k

         

          =LOC(0,0,0)+i*m*o+j*o+k

          =a+i*m*o+j*o+k

推广至n维数组a[m1]…[mn]来说,设其第一个数组元素a[0]…[0]在相应一维数组中也是第一个位置,其下标为a,优先顺序随着下标维数增大而逐渐变小,则一个数组元素a[i1]…[in]在相应一维数组中的存储地址为:

LOC(i1,i2,…,in)

=LOC(0,0,…,0)+i1*m2*m3…*mn+i2*m3*m4…*mn+…+in

 

    特殊矩阵

 

    矩阵操作是多维数组最广泛的应用。矩阵的知识最初介绍于大学理工类科目基础课程线性代数中,它是科学计算、工程数学,尤其是数值分析经常研究的对象。而在一些高级矩阵中,存在大量0元素,使得非零元素极少(远小于m*n),如果仍然根据普通数组存储顺序存放,将造成存储空间的很大浪费。基于节省存储空间的考虑,我们进一步讨论特殊矩阵的内部规律,以及利用这些规律制定策略,实现压缩存储,达到提高存储空间利用率的目的。

    1、对称矩阵

    对于特殊矩阵的研究通常基于两点,一是矩阵内部元素的分布有明显规律,二是矩阵内部非零元素个数远小于m*n。对称矩阵即属于第一种情况。

    在一个n阶方阵A中,对A中任意元素a[i][j]i<j时,aij=c(通常c=0),则称其为下三角矩阵,相反地为上三角矩阵。对于三角阵其元素包括了对角线以及对角线一边的元素,其个数共有n+(n-1)+…2+1=n(n-1)/2。要压缩存储矩阵,即只要存储三角阵中非零一边的元素即可,其核心实际上为三角阵对一维数组元素地址的映射问题。

    同样以行优先为顺序,当只存储下三角部分时,对于i>j时的任意元素aij,其前方有i行的元素及i+1行的前j个元素,则其地址事实上可以转换为简单的求和公式:

    LOC(i,j)=1+2+3+…+i+j=i*(i+1)/2+j

    对于对称矩阵,可以据此求出未被实际存储的元素aji的值:

    LOC(i,j)=LOC(j,i)=(j+1)*j/2+i

    当存储上三角矩阵时,第0行存放n个元素,第i+1行从aii算起,aij前共有j-i个元素,则其地址映射公式为:

    LOC(i,j)=n+n-1+…+n-i+1+j-i=(2n-i+1)*i/2+j-i=(2n-i-1)*i/2+j

    则当i>j时的对称矩阵元素aji的值可由以下公式求得:

    LOC(i,j)=LOC(j,i)=(2n-j-1)*j/2+i

    2、带状矩阵

    带状矩阵实际上是一种特殊的稀疏矩阵,其元素一般分布在主对角线为中心的带状区域内。其中最常见的是三对角带状矩阵。

    三对角线矩阵中,除了主对角线及其左右两条对角线的元素外,其余元素值均为0。对于三对角线矩阵的压缩存储,其实质和三角矩阵相比并无太大区别。依然以行优先为顺序,三对角线矩阵的非零元素个数为3n-2由此推广至多对角线矩阵存储,假设主对角线一侧分别有b条次对角线包含非零元素,据此求得多对角线矩阵的非零元素个数为n+2(n-1+n-2+…+n-b)=n+b(2n-b-1)=(2b+1)n-b-b*b。对于求带状矩阵对一维数组元素地址的映射公式,我们要基于以下三种情况分别考虑:

    1<=i<=b时,此时元素属于矩阵的上部区域。则元素aij的定位:

    LOC(i,j)=b+1+b+2+b+3+…+b+i-1+j-1=(2b+i)(i-1)/2+j-1

    b<i<n-b+1时,元素处于矩阵的中部区域。

    LOC(i,j)=(b+1)+(b+2)+(b+3)+…+(b+b)+(i-b-1)(2b+1)+j-i+b=(3b+1)b/2+(i-b-1)(2b+1)+j-i+b

    n-b+1<=i<=n时,元素处于矩阵的下部区域,则:

    LOC(i,j)=(3b+1)/2+(n-2b)(2b+1)+(3b-i+n+2)(i-n+b-1)/2+j-i+b

    综上即可求出各种情况下按行优先的带状矩阵对一维数组元素的映射地址。

    特殊地,对于三对角线矩阵,公式简化为:

    LOC(i,j)=2(i-1)+j-1

    3、稀疏矩阵

    稀疏矩阵Sparse Matrix是非零元素个数远小于零元素个数的一类矩阵的统称。大多数的稀疏矩阵其非零元素分布上一般无规律可循。

    一般在n*m矩阵中定义一个稀疏因子δ,其非零元素个数为t,有δ=t/(m+n),当δ<0.05时可以认为该矩阵为稀疏矩阵。

    为了合理表示和存储稀疏矩阵,一般采取三元组表的方法。对于稀疏矩阵只存储非零元素,则先定义一个三元组结构:

    #define MaxSize 1000        //非零元素的个数最多为1000

    typedef struct

    {

        int row,col;            //记录了非零元素在原矩阵中的行号、列号

        ElementType e;          //

}Triple;

再根据此结构建立三元组表

typedef struct

{

    Triple data[MaxSize+1]; //设定三元组表,data[0]未用

    int m,n,len;            //记录矩阵的行数、列数以及非零元素的个数

}

 

稀疏矩阵的转置运算

 

矩阵转置是指变换元素位置,使位于(row,col)上的元素与(col,row)上的元素进行互换,即行列互换运算。这是矩阵的一种基本运算形式。

稀疏矩阵由于其特殊的存储结构,转置操作就与普通矩阵转置有很大不同。我们先来看一般矩阵的经典转置算法:

TransMatrix(ElementType source[m][n]ElementType dest[n][m])

{

    int i,j;

    for(i=0;i<m;i++)

        for(j=0;j<n;j++)

            dest[j][i]=source[i][j];

}

显然稀疏矩阵的三元组表形式无法使用经典算法转置。

有一种简单的转置方法,首先把三元组表中元素的rowcol值互换,然后按新row值递增序列重新排序。此方法理论上达到了转置的目的,但排序效率较低,并不是合适的转置算法。

一般来说三元组表的转置有两种普遍算法:

1、“列序”递增转置法

算法开始按照col列序为1,行序递增的顺序从头到尾找出转置后的第一行元素,行列值互换后存入dest,然后再从头到尾按列序位2,行序递增的顺序重复操作……直到找出第k行全部元素,其中1<=k<=n。程序主体为双循环结构:

for(k=1;k<=A.n;k++)

    for(i=1;i<A.len;i++)

        //互换

        j++;//j值储存的是dest中下一个转置后元素的位置下标

该算法的时间复杂度为O(A.n*A.len),最坏情况时A.n*A.m=A.len,即全部为非零元素,则时间复杂度为O(A.m*A.n*A.n0),反而远高于经典算法的O(A.m*A.n),因此此算法仅适用于三元组表转置。

2、“一次定位快速转置”法

现在对第一种算法进行性能优化,突破点在消除双重循环上。我们从前几节的连载中得到一种经验,在类似于将一种结构按一定规律转化为另一种结构的过程中,如果要进行性能优化,就必须深入探究原有结构内部的规律,凭借此规律取得的一部分资源,恰可以替代外层循环的作用。例如连载七中对字符串简单模式匹配算法的改进算法KMP

现在我们分析三元组表,根据此表的分析我们可以得出两个有益的信息:一是转置后每行非零元素的个数,二是转置后每行第一个非零元素的位置。这两个信息足以达到消除一层循环的目的。

num[col]记录三元组表col=1,2,…,n中元素的个数,position[col]记录三元组表col=1,2,…,n中第一个元素在表中的下标值。算法程序主体为单循环结构(我们省略了计算两个辅助数组的部分):

for(p=1;p<=A.len;p++)

{

    //该方法的原理是,由于转置后每列第一个非零元素必然在三元组表中优先出现,因此直接与position在相应列的位置配对,算法结束后相应位置加1以便放入该列内的剩余元素

    col=A.data[p].col;

    q=position[col];

    //dest[q]A.data[p]互换数值

    position[col]++;

}

实际程序中由于数组初始化等因素,共用到四个单循环,总的时间复杂度为O(A.n+A.len),较第一种方法而言在性能上有了很大提高,但也必须看到,由于所需存储空间增加,事实上说明算法在时间上的节省是以更多的存储空间为代价

 

稀疏矩阵的正交链表存储

 

这里我们忽略了三元组表中对于稀疏矩阵四则运算操作的实现,这是因为矩阵加减法较为简单,而乘法虽然规则清晰,但由于依然涉及到遍历的问题,有时甚至需要三重循环来实现运算,较为复杂,且不符合本次系列连载的目的。

但矩阵运算所带来的问题却不容忽视,尤其是其对三元组表可能发生元素值的修改、元素个数的增减等等复杂运算。为了更有利于实际应用,有时候稀疏矩阵使用正交链表的存储形式,也称“十字链表”。

稀疏矩阵的正交链表结点共有六个域,分别为rowcoldown(链接列链表中下一个结点)right(链接行链表中下一个结点)head(是否为附加头结点)、value。因此正交链表其实就是将矩阵的每一行与每一列分别建立链表,逻辑上是“十字交叉”状的。

 

广义表

 

广义表同样作为线性表的一种推广,但更准确地讲,广义表才能真正意义上被称为“表”,线性表可以被当作一种特殊的表,但在实际中往往可能特殊的结构反而更容易被广泛使用。

广义表generalized list长期以来主要用于人工智能领域的研究,向前继承了离散数学的部分内容。在List processor语言LISP中,其表达式就是用表的形式来实现的。

广义表的显著特点是允许表中有表,广义表也是一组有限的序列,表中第一个元素被称为广义表表头head,除此之外的其它元素所组成的表称作表尾tail。下面给出一些广义表的实例:

D=(),空表,长度为0

A=(a,(b,c)),表长度为2,表头为a,表尾为((b,c))

B=(A,A,D),长度为3,表头为A,第三个元素为空表D

C=(a,C),表长为2的递归定义的广义表,C相当于无穷表。

由上可得出广义表的五个性质:

1、  有次序性,因为表中元素是按线性排列的,其前驱、后继关系依然存在。

2、  有长度,广义表元素的个数是一定的,不能是无限长,且可以为空。

3、  有深度,广义表的元素可以是原表的子表,子表的元素还可以是子表……从而形成多层次结构。

4、  可递归的,广义表本身可以是自己的子表。

5、  可共享的,广义表可以被其它表共享。

 

广义表存储结构的实现

 

由于广义表本身结构的不确定性,因此凭借顺序结构很难对其进行表示,因此一般使用链式存储结构来表示。

1、 广义表的头尾链表存储结构

广义表链式存储的结点分为两类,一类是单个元素结点,其结点由标志域和值域构成;另一类是子表结点,其结点由标志域、指向标头的指针域和指向表尾的指针域构成。

现在给出C语言描述的广义表头尾链表存储结构的类型定义:

typedef enum{ATOM,LIST} ElemTag;

typedef stuct GLNode

{

    ElemTag tag;

    union

{

    AtomType atom;

    struct

{

                struct GLNode *hp,*tp;

}htp;

}atom_htp;

}GLNode,*Glist;

2、 广义表的扩展线性链表存储结构

扩展线性链表存储结构的特点是,其子表结点和元素结点均由三个域构成:标志域、表头指针/值域、表尾指针。在两种表示形式中需要注意,标志域虽然为enum型,但实际默认ATOM0LIST1,在绘制结构图时需要特别注意。

 

广义表的递归运算

 

由于广义表的递归性,因此很多关于广义表的基本运算也是递归的。我们省略了取表头、表尾、长度等几个较简单的运算,直接举例求解广义表深度的C语言算法描述:

int Depth(Glist L)

{

    int d,max;

    GLNode *x;

    if(L==NULL)         //为空表,默认为深度为1

        return 1;

    if(L->tag==ATOM)

        return 0;       //元素结点深度为0

    s=L;

    max=0;              //初始化表/子表深度值

    while(s!=NULL)      //求每个子表的最大深度值,回溯结束后即为最深子表的深度

    {

        d=Depth(s->atom_htp.htp.hp);

        if(d>max)

            max=d;

        s=s->atom_htp.htp.tp;

}

    return max+1;       //最终深度等于最深子表的深度加1

}

 

现在,我们已经介绍了简单数据结构线性表部分的全部内容,按照计划,后面的几期连载将继续介绍几种简单的数据结构。近期会制定总结出返校后本连载的内容方向,以及其它一些内容。

 

(未完待续)

Comments

假期连载之八

       本篇为连载七未完成内容的后续补充部分。我们继续讨论关于字符串的一些问题,最后将对STL中关于String的部分进行一些说明。

 

       字符串的模式匹配

 

       字符串的模式匹配问题描述如下:设有两个字符串patT,若打算在串T中查找是否有与串pat相等的字串,则称串T为目标Targetpat为模式Pattern,并称查找模式串在目标串中位置的运算成为模式匹配Pattern Matching

1 朴素(简单)的模式匹配

  这种被称为B-F的模式匹配算法是由BruteForce共同提出的一种基于简单穷举算法。该算法的思想是用pat的字符依次与T中的字符做比较,如果对应元素均相同,则匹配成功,返回模式串第0个字符P0在目标串T中的位置;如果其中某个位置i中有Ti=Pi,则比较不等,此时将模式串pat右移一位,并用pat中的字符从头开始与T中的字符依次比较,反复执行上述过程,直到出现下列两种情况之一时结束算法:

  执行过程中发现存在与模式串匹配的目标串子串,即匹配成功;

  当模式串已经移到最后可能与T比较的位置,但并不能保证每个字符均可与T匹配,此时匹配失败,返回-1

  下面给出B-F算法的C++描述:

  int Find(Astring& pat,int k) const

  {     //Astring是默认定义的一个String类,k为在目标串中开始匹配的位置,const声明为常成员函数,这里有两重意义:首先常成员函数不能修改数据成员,也不能调用非const成员;其次在被声明为const的常对象中只能调用常成员函数。

         int i,j;

         for(i=k;i<=curLength-pat.Length;i++)

         {//利用到了回溯的方法进行逐次匹配

                for(j=0;j<pat.Length;j++)

                       if(ch[i+j]!=pat.ch[j])

                              break;

                if(j==pat.Length)

                       return i;

              }

         return -1;

}

由上述算法可知,在最坏情况下,算法最多将比较n-m+1次,假设模式串长度远小于目标串,则算法运行时间为O(n*m)

2、模式匹配的改进算法

       为了改进B-F算法的性能,需消除其自带的回溯因素,因此需要对串本身进行进一步分析。

       D.E.KnuthJ.H.MprrisV.R.Pratt同时提出了基于简单模式匹配的改进算法—KMP算法,这种算法大大降低了字符串模式匹配算法的时间复杂度。

       KMP算法本身可使用详细的图表进行说明,限于篇幅原因本文仅提供文字叙述,由于KMP算法的普遍性,众多文献均有丰富讲解,有兴趣的读者可以额外查阅。

       在简单模式匹配中我们发现,由于P串一旦与T串发生“失配”,则无条件直接回溯至T串的k+1个位置重新匹配,其中浪费了很多P串内部规律的资源。理由如下:假设我们在Pj处发现“失配”,此时并不求助于T串,而是寻求一个非负整数k<j-1,使得P0…Pk=Pj-k-1…pj-1,由于P0…Pk肯定和T串对应于Pj-k-1…Pj-1的元素一一对应且相等,则将模式串第k位与目标串失配位置对齐,并从模式串的第k位开始比较即可。如果不能找到k值,则将模式串第0位与目标串失配位置对齐,并从模式串的第0位开始比较。

       为了易于编程,一般我们先计算出P串对j=0,1,2,…,n的所有k值,据此求出下一次匹配模式串中与目标串上次失配位置对齐的相应位置。此距离使用数组next[]表示,我们先给出其数学规律:

                     -1        j=0;

next[j]={k+1      0<=k<j-1且使得P0P1…Pk=Pj-k-1…Pj-1的最大整数;

0,                  其他所有情况;

j=0的情况,即模式串的第0位元素与目标串位置失配,此时将第0位与目标串失配位置的下一位置对齐即可。

例如对于字符串P=”abaabcac”,有next[]如下:

       j      0     1     2     3     4     5     6     7

       P     a      b     a      a      b     c     a      c

next(j)     -1    0     0     1     1     2     0     1

我们对其中j=2j=5的情况进行简短分析。当j=2时,得知k可能为0,当k=0时,有P0!=P1,因此k不存在,next(2)=0;当j=5时,k可能在0-3之间,由大到小比较,P0…P3!=P1…P4,故k!=3P0P1P2!=P2P3P4,故k!=2,有P0P1=P3P4,故k=1,因此next(5)=k+1=2

据此我们给出计算next[]的一般方法:

getNext(int next[])

{

       int j=0,k=-1,lengthP=curLength;   //curLength为模式串长度

       next[0]=-1;

       while(j<lengthP)

       {

              if(k==-1||ch[j]==ch[k])

              {

j++;

                     k++;

                     next[j]=k;

       }

       else

              k=next[k];

}

}

在求出next[]后,我们可以根据以下KMP算法实现快速匹配:

int fastFind(Astring& pat,int k,int next[])const

{     //此程序段的有关疑问请参考B-F程序段

       int posP=0,posT=k;

       int lengthP=pat.curLength;

       int length=curLength;

       while(posP<lengthP&&posT<lengthT)

       {

              if(posP==-1||pat.ch[posP]==ch[posT])

              {

                     posP++;

                     posT++;

}

else

       posP=next[posP];

}

if(posP<lengthP)

       return -1;

else

       return posT-lengthP;

}

易知整个算法的时间复杂度为O(lengthP+lengthT)

 

字符串的模式匹配是一个应用极其广泛、重要的一种计算机算法问题。在普通的文本编辑器中随处可见模式匹配的功能用例,在目前流行的各种信息检索中模式匹配算法也是核心研究之一。数十年来不断有科研人员在寻找更加智能、更加高效的算法中取得成果,并不断产生革新。

在实际应用中,我们并不一定必须自己定义原始的模式匹配算法。例如正则表达式Regular Expression,就是一种建立在元字符基础上描述文本规则的强大工具。目前正则表达式被制作成了众多库,广泛支持各种高级语言,许多主流高级语言也已经内嵌了正则表达式。

 

STL String

 

STL中对于String的操作有了进一步规范,其在运算符重载、串查找函数的实现方面均有很大提高。以下为STL String中所定义的函数列表:

begin  得到指向字符串开头的Iterator 

end  得到指向字符串结尾的Iterator 

rbegin  得到指向反向字符串开头的Iterator 

rend  得到指向反向字符串结尾的Iterator 

size  得到字符串的大小 

length  size函数功能相同 

max_size  字符串可能的最大大小 

capacity  在不重新分配内存的情况下,字符串可能的大小 

empty  判断是否为空 

operator[]  取第几个元素,相当于数组 

c_str  取得C风格的const char* 字符串 

data  取得字符串内容地址 

operator=  赋值操作符 

reserve  预留空间 

swap  交换函数 

insert  插入字符 

append  追加字符 

push_back  追加字符 

operator+=  += 操作符 

erase  删除字符串 

clear  清空字符容器中所有内容 

resize  重新分配空间 

assign  和赋值操作符一样 

replace  替代 

copy  字符串到空间 

find  查找 

rfind  反向查找 

find_first_of  查找包含子串中的任何字符,返回第一个位置 

find_first_not_of  查找不包含子串中的任何字符,返回第一个位置 

find_last_of  查找包含子串中的任何字符,返回最后一个位置 

find_last_not_of  查找不包含子串中的任何字符,返回最后一个位置 

substr  得到字串 

compare  比较字符串 

operator+  字符串链接 

operator==  判断是否相等 

operator!=  判断是否不等于 

operator<  判断是否小于 

operator>>  从输入流中读入字符串 

operator<<  字符串写入输出流 

getline  从输入流中读入一行

 

由于多数读者从C开始接触到一些字符串操作的库函数,因此在学习C++后对同类型的部分容易发生混淆,唯一的办法只能是多实践,并经常总结相关内容,才能逐步熟练掌握。

 

(未完待续)

 

Comments

假期连载之七

(串,串在C/C++中的应用—上)

 

       前记:本篇的前半部分事实上在上周末即已完成,原本无意分为两个部分来写,不过身体突发小恙,卧床了两天,为不至于拖延太长时间故先把已完成的发布出来,下不为例。就这样了。

 

本节我们介绍字符串—一般简称为串,它在计算机数据类型中具有非常重要的地位。无论从汇编语言、C/C++还是到Java,串操作都是语言本身必不可少的一部分内容。尽管每种语言在串的存储形式上存在一些差异,但对其本身的定义和操作却完全一致。最后我们会以C++String容器为例,综合介绍字符串操作的规则及原理。

      

       字符串

 

       字符串是指由零个或多个字符组成的有限序列。每个字符可以是字母、数字或其他字符,串中字符的个数称为字符串长度,当长度为0时称为空串。

       学习过C语言的都知道,字符一般用单引号括起来,而字符串则使用双引号。事实上在一般数据结构描述中串默认代表了单个字符的情况,因此都使用单引号表示。

       子串是指任意个连续的字符组成的子序列。

       主串指包含子串的串,字串是主串的一部分。

       字串在主串中的位置,是指字串的第一个字符在主串中的位置。

       串相等的条件是两个串的长度相等,并且每个对应位置的字符也都相等。

      

       现在,我们可以认识到,串也是一种特定的线性表,其特性主要体现在数据元素的类型为字符

       事实上,在C/C++中,所谓的字符串其实是以字符串数组char[]的形式来进行操作的,这一点与Javalang.String的实现有所区别,一般而言JavaString类更符合字符串的存储形式。

      

       串的抽象数据类型的C语言描述表示如下:

       ADT String

{

       数据对象:D={a1,a2,…,an},其中anchar类型

       基本操作:

       ……

}

这里省略了字符串的基本运算函数,主要是因为在C/C++中既有从C语言继承而来的标准库函数,又有C++独立具备的STL中的String容器,Java中的String类也自成体系。对于众多运算必须明确地加以区别,否则会在实际编程中引起很多困难。

借助于Internet,我们收集了C/C++库函数中关于字符串操作的函数集:

 

void *memccpy (void *dest, const void *src, int c, size_t n);

src所指向的对象复制n个字符到dest所指向的对象中。如果复制过程中遇到了字符c则停止复制,返回指针指向dest中字符c的下一个位置;否则返回NULL

 

void *memcpy (void *dest, const void *src, size_t n);

src所指向的对象复制n个字符到dest所指向的对象中。返回指针为dest的值

 

void *memchr (const void *s, int c, size_t n);

s所指向的对象的前n个字符中搜索字符c。如果搜索到,返回指针指向字符c第一次出现的位置;否则返回NULL

 

int memcmp (const void *s1, const void *s2, size_t n);

比较s1所指向的对象和s2所指向的对象的前n个字符。返回值是s1s2第一个不同的字符差值。

 

int memicmp (const void *s1, const void *s2, size_t n);

比较s1所指向的对象和s2所指向的对象的前n个字符,忽略大小写。返回值是s1s2第一个不同的字符差值。

 

void *memmove (void *dest, const void *src, size_t n);

src所指向的对象复制n个字符到dest所指向的对象中。返回指针为dest的值。不会发生内存重叠。

 

char *stpcpy (char *dest, const char *src);

复制字符串srcdest中。返回指针为dest + len(src)的值。

 

char *strcpy (char *dest, const char *src);

复制字符串srcdest中。返回指针为dest的值。

 

char *strchr (const char *s, int c);

在字符串s中搜索字符c。如果搜索到,返回指针指向字符c第一次出现的位置;否则返回NULL

 

int strcmp (const char *s1, const char *s2);

比较字符串s1和字符串s2。返回值是s1s2第一个不同的字符差值。

 

int stricmp (const char *s1, const char *s2);

比较字符串s1和字符串s2,忽略大小写。返回值是s1s2第一个不同的字符差值。

 

size_t strcspn (const char *s1, const char *s2);

返回值是字符串s1的完全由不包含在字符串s2中的字符组成的初始串长度。

 

size_t strspn (const char *s1, const char *s2);

返回值是字符串s1的完全由包含在字符串s2中的字符组成的初始串长度。

 

char *strdup (const char *s);

得到一个字符串s的复制。返回指针指向复制后的字符串的首地址。

 

char *strerror(int errnum);

返回指针指向由errnum所关联的出错消息字符串的首地址。errnum的宏定义见errno.h

 

size_t strlen (const char *s);

返回值是字符串s的长度。不包括结束符’\0′。//计算长度len时不包括结束符’\0′,计算size时要包括结束符’\0′,亦即size=len+1

 

char *strlwr (char *s);

将字符串s全部转换成小写。返回指针为s的值。

 

char *strupr (char *s);

将字符串s全部转换成大写。返回指针为s的值。

 

char *strncat (char *dest, const char *src, size_t maxlen);

将字符串src添加到dest尾部,最多添加maxlen个字符。返回指针为dest的值。

 

char *strcat (char *dest, const char *src);

将字符串src添加到dest尾部。返回指针为dest的值。

 

int strncmp (const char *s1, const char *s2, size_t maxlen);

比较字符串s1和字符串s2,最多比较maxlen个字符。返回值是s1s2第一个不同的字符差值。

 

char *strncpy (char *dest, const char *src, size_t maxlen);

复制字符串srcdest中,最多复制maxlen个字符。返回指针为dest的值。

 

int strnicmp(const char *s1, const char *s2, size_t maxlen);

比较字符串s1和字符串s2,忽略大小写,最多比较maxlen个字符。返回值是s1s2第一个不同的字符差值。

 

char *strnset (char *s, int ch, size_t n);

设置字符串s中的前n个字符全为字符c。返回指针为s的值。

 

void *memset (void *s, int c, size_t n);

设置s所指向的对象的前n个字符为字符c。返回指针为s的值。

 

char *strset (char *s, int ch);

设置字符串s中的字符全为字符c。返回指针为s的值。

 

char *strpbrk (const char *s1, const char *s2);

返回指针指向字符串s1中字符串s2的任意字符第一次出现的位置;如果未出现返回NULL

 

char *strrchr (const char *s, int c);

在字符串s中搜索字符c。如果搜索到,返回指针指向字符c最后一次出现的位置;否则返回NULL

 

char *strrev (char *s);

将字符串全部翻转,返回指针指向翻转后的字符串。

 

char *strstr (const char *s1, const char *s2);

在字符串s1中搜索字符串s2。如果搜索到,返回指针指向字符串s2第一次出现的位置;否则返回NULL

 

char *strtok (char *s1, const char *s2);

用字符串s2中的字符做分隔符将字符串s1分割。返回指针指向分割后的字符串。第一次调用后需用NULLL替代s1作为第一个参数。

 

串的存储实现

 

       由于串是一种特定的线性表,因而其存储结构与普通线性表之间并无很大差异。

       最常用的即是前文已介绍的定长顺序串,其类型定义如下。

#define MAXLEN 40   

typedef struct

{

              char ch[MAXLEN];

              int len;                         //存储字符串实际长度

}SString;

      

       还有一种堆串,其串中的字符仍然存放在一组地址连续的存储单元中,但它们的存储空间是在程序执行过程中动态分配的。系统将一个地址连续、容量很大的存储空间作为字符串的可用空间,每当建立一个新串时,系统就会从这个空间中分配一个大小和字符串长度相同的空间存储新串的串值。其类型定义如下:

typedef struct

{

              char *ch;

              int len;                         //存储字符串实际长度

}HString;

       由于堆串在实际应用中可以动态分配存储空间,其较定长顺序串而言方便了许多。但由于其本质未能发生变化,故操作上要不断生成新串、销毁旧串。

 

       同时字符串还可以用链式存储结构表示。在这种结构中,结点值可以存放一个字符,也可以存放多个字符,故结点被称为块,链表相应被称为块链表。

       鉴于块链表的特殊结构,在实际应用中要考虑几个重要因素。

       结点大小:结点大小是指结点data域中存放的字符个数。由于存储密度=串值所占用的存储位/实际为串分配的存储位,得知当存储密度越小,块链表操作越容易,但需耗费更多的存储空间,这就需要根据实际情况来判断。

       结点大小大于1,为节约空间而采用结点大小大于1的方法,尽管存储密度得到了提高,但结点内部串的操作就变得较为复杂,尤其是在进行删除、合并操作时需要充分考虑到data域自身的运算。

 

(未完待续)

Comments