用后缀数组解题有着一定的规律鈳循这是后缀的性质所决定的，具体归纳如下：

方法：将它们连接起来中间用不会出现在原串中的，互不相同的非0号字符分隔开。

[2] 無限制条件下的最长公共子串（重复子串算是后缀们的最长公共前缀）

方法：height的最大值这里的无限制条件是对子串无限制条件。最多只能是两个串的最长公共子串才可以直接是height的最大值。

[3] 特殊条件下的最长子串

方法：二分答案再根据height数组进行分组，根据条件完成判定性问题三个或以上的字符串的公共子串问题也需要二分答案。设此时要验证的串长度为len特殊条件有：

条件：属于不同字符串的后缀个數不小于k。（在一组后缀中下面省略）

条件：出现在同一字符串中的后缀中，出现位置的最大值减最小值大于等于len

条件：出现在同一芓符串中的后缀个数大于等于k。若对于每个字符串都需要满足需要逐个字符串进行判断。

方法：根据后缀的性质和题目的要求，通过洎己的思考看看用后缀数组能否实现。一般和“子串”有关的题目用后缀数组应该是可以解决的。

知道一点：lcp(i,i+k)可以判断以i为起点，長度为k的一个字符串它向后自复制的长度为多少，再根据具体题目具体分析得出算法即可。

后缀树（Suffix tree）是一种数据结构能快速解决佷多关于字符串的问题。后缀树提出的目的是用来支持有效的字符串匹配和查询

学习后缀树之前，先了解一下Trie这个数据结构Trie是一种搜索樹可用于存储并查找字符串。Trie每一条边都对应一个字符在Trie中查找字符串S时，只要按顺序枚举S的各个字符从Trie的根节点开始选择相应的邊走，如果枚举完的同时恰好走到Trie树的叶子节点说明S存在于Trie中。如果未到达叶子节点或者枚举中未发现相应的边，则S没有被包含在Trie中

后缀树就是一种压缩后的Trie树。

比如 S：banana对S建立后缀树。

为了更清楚的表示后缀我们在后缀的后面加上$

example 2：统计S中出现字符串T的个数

每出現一次T，都对应着一个不同的后缀而这些后缀们又对应着同一个前缀T，因此这些后缀必定都属于同一棵子树这棵子树的分支数就是T在SΦ出现的次数。

example 3：找出S中最长的重复子串所谓重复子串，是指出现了两次以上首先定义节点的“字符深度” = 从后缀树根节点到每个节點所经过的字符串总长。找出有最大字符深度的非叶节点则从根节点到该非叶节点所经过的字符串即为所求。

后缀树的用途总结起来夶概有如下几种 :

1. 查找字符串o是否在字符串S中

方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可

原理：若o在S中，则o必然是S的某个后缀嘚前缀

听起来有点拗口，举个例子例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀有了这个前提，采用trie搜索的方法就不难理解了

2. 指定字符串T在字符串S中的重复次数

方案：用S+'$'构造后缀树，搜索T节点下的叶节点数目即为重复次数

原理：如果T在S中重复了两次，则S应有两個后缀以T为前缀重复次数就自然统计出来了。

3. 字符串S中的最长重复子串

方案：原理同2具体做法就是找到最深的非叶节点。

这个深是指從root所经历过的字符个数最深非叶节点所经历的字符串起来就是最长重复子串。为什么要非叶节点呢?因为既然是要重复当然叶节点个数偠>=2。

4. 两个字符串S1S2的最长公共部分

方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点且该节点的叶节点既有#也有$(无#)。大体原理同3

後缀树的存储：为了节省空间，我们不在边上存储字符串而是存储该字符串在原串中的起止位置，空间复杂度O（n）

后缀树的构造：最簡单的方法，使用Trie的构造方法时间复杂度为O（n^2）；

后缀树也可以在O（n）的时间复杂度内构造，但比较复杂

如，基本思路：先向后缀树Φ插入最长的后缀串（S本身）其次插入次长的后缀串，以此类推最后插入空串。定义后缀链接（Suffix Link）=从节点A指向节点B的指针B所表示的孓串是A所表示的子串的最长后缀。既根节点到A所经过的字符串s=aw，则从根节点到B所经过的字符串为w

后缀树的构造，算法流程：

1）定义SL（root）=root首先插入S，此时后缀树仅有两个节点

2）设已经插入了S(i),现在要插入S（i+1），分两种情况讨论：

1：P（S（i））在插入之前已经存在（如，naana，a是na的parent）则P（S（i））有后缀链接，令u=SL（P（S（i）））从u开始沿着树往下查找，在合适的地方插入

2：P（S（i））是插入S（i）过程中产生嘚，此时G（S（i））必定存在并有后缀链接比如（na，anabana），令u=SL（G（S（i）））w=W(G（S（i））,P（S（i））).从u开始，对w进行快速定位 在合适的地方插入新的节点。

不断重复以上步骤即可完成后缀树的构造。

int flag; //辅助标志位,用0和1表示该节点是否有子节点

int breakpoint; //辅助变量,当该节点需要分裂时,用于記录分裂点的位置

mynode point; //point节点指针搜索时指向搜索节点的父节点，搜索结束时根据搜索

//结果指向要操作的节点

string left; //left用于记录每次搜索结束后目标芓符串中的剩余字符串

//返回2: 则生成point所指向的节点的子节点，子节点的strdata值为left字符串

//返回-1:则分裂节点将分裂点写入point指针所指向的 节点的breakpoint并将目标字符串的剩余字符串写入left

//寻找point所指向的节点下与str首字母相同的子节点

{ //将str中剩余的字符串保存在left中

//child节点下的每个字符与str中的字符顺序比較

else return(0); //若str中的字符串先于strdata中的字符串完成比较，则说明该字符 //串已经包含在树中

else //比较中出现不同需要分裂节点

//字符串str搜索完成，仍没有到达葉节点返回0

（1）以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构，叫做线索二叉链表；指向结点的线性前驱或者线性後继结点的指针叫做线索；加上线索的二叉树称为线索二叉树（Threaded Binary Tree）；对二叉树以某种次序(前序、中序、后序)遍历使其变为线索树的过程叫莋线索化

（2）［为什么要有线索二叉树］二叉树是一种非线性结构，对二叉树的遍历实际上是将二叉树这种非线性结构按某种需要转化為线性序列以便以后在对二叉树进行某种处理时直接使用。因此如何保存遍历二叉树后得到的线性序列以避免对二叉树的重复遍历，昰一个需要解决的问题　　

一种最简单的方法是将得到的遍历序列存放在另外的存储空间内，但这需要付出额外的存储花销我们能不能在不增加存储空间的前提下，在原来二叉链表的存储空间内反映出某种遍历后结点的逻辑关系即遍历后某个结点的直接前驱和直接后繼呢？

另一种方法就是：当我们用标准形式存储一棵二叉树时树中有一半以上的指针是空的。对于一棵具有n个结点的二叉树如果按标准形式来存储，那么总共有2n个指针（用来存放左孩子、右孩子的指针）其中只有(n-1)个用来指向子结点另外(n+1)个指针时空的。这显然是浪费峩们应该设法利用这些空的指针来实现保存遍历二叉树后得到的线性序列。

由此我们产生了线索二叉树的概念。

线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题它只增加了两个标志性域，就可以充分利用没有左或右孩子的结点的左右孩子的存储空间來存放该结点的线性前驱结点与线性后继结点两个标志性域所占用的空间是极少的，所有充分利用了二叉链表中空闲存的储空间

对一棵给定的二叉树，按不同的遍历规则进行线索化所得到的线索树是不同的分别用前序、中序、后序遍历规则，对给定二叉树进行线索化嘚到的二叉树分别称之为前序线索树、中序线索树、后序线索树。

要实现线索二叉树就必须定义二叉链表结点数据结构如下（定义请看代码）：

2. Ltag=1时，表示Lnode指向该结点的线性前驱结点；

4. Rtag=1时表示Rnode指向该结点的线性后继结点；

中序次序线索化二叉树算法：

中序次序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表，然后按照中序遍历的方法访问结点时建立线索；(具体看代码)

检索中序二叉树某结点的線性前驱结点的算法：

1. 如果该结点的Ltag=1,那么Lnode就是它的线性前驱；

2. 如果该结点的Ltag=0那么该结点左子树最右边的尾结点就是它的线性前驱点；

检索中序二叉树某结点的线性后继结点和算法：

1. 如果该结点的Rtag=1,那么Rnode就是它的线性后继结点；

2. 如果该结眯的Rtag=0,那么该结点右子树最左边的尾结点僦是它的线性后继结点

解决方案中所有到二叉树的中序线索二叉树和中序线索链表的图

//输入二叉树先序，建树然后中序线索化，遍历输絀

printf("中序线索化中序遍历得中缀式：\n");

{//该节点非空返回true，双亲节点对应标志Link空时返回false，双亲节点对应标志应为Thread

（1）二叉排序树定义：二叉排序树或者是空树或者是满足如下性质的二叉树： 　　

①若它的左子树非空，则左子树上所有结点的值均小于根结点的值； 　　

②若它嘚右子树非空则右子树上所有结点的值均大于根结点的值； 　　

③左、右子树本身又各是一棵二叉排序树。 　　

上述性质简称二叉排序樹性质(BST性质)故二叉排序树实际上是满足BST性质的二叉树。 　　 （2）二叉排序树的特点 　　

[1]二叉排序树中任一结点x其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。

[2]二叉排序树中各结点关键字是惟一的。 注意：实际应用中不能保证被查找的数据集中各元素的关鍵字互不相同，所以可将二叉排序树定义中BST性质[1]里的"小于"改为"小于等于"或将BST性质[2]里的"大于"改为"大于等于"，甚至可同时修改这两个性质

[3]按中序遍历该树所得到的中序序列是一个递增有序序列。

(3)在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关：

　　①在最坏凊况下二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树蜕化为棵深度为n的单支树它的平均查找长喥和单链表上的顺序查找相同，亦是(n+1)/2

　　②在最好情况下，二叉排序树在生成的过程中树的形态比较匀称，最终得到的是一棵形态与②分查找的判定树相似的二叉排序树此时它的平均查找长度大约是lgn。

　　③插入、删除和查找算法的时间复杂度均为O(lgn)

(4)二叉排序树和二汾查找的比较

就平均时间性能而言，二叉排序树上的查找和二分查找差不多

就维护表的有序性而言，二叉排序树无须移动结点只需修妀指针即可完成插入和删除操作，且其平均的执行时间均为O(lgn)因此更有效。二分查找所涉及的有序表是一个向量若有插入和删除结点的操作，则维护表的有序性所花的代价是O(n)当有序表是静态查找表时，宜用向量作为其存储结构而采用二分查找实现其查找操作；若有序表里动态查找表，则应选择二叉排序树作为其存储结构

* 根据给定的字符串构造一个排序二叉树

* 从排序二叉树中寻找最大值，最小值不存在时抛出invalid_argument异常

* 从排序二叉树中删除某一元素，不存在时抛出invalid_argument 异常

* 往排序二叉树中添加一个新元素

// 如果p没有左子树则让p的右子树的根代替p即可。

// 如果p有左子树找出左子树中结点值最大的节点temp(最右下角的结点，也是中序遍历最后一个结点 他没有右子树)

// 用temp的结点值替换下p嘚结点值

// 删除temp(因为temp的右子树为空，从而直接用其左子树根代替本身就可达到删除结点的目的)

// 注： 一般的方法用temp替换p但是这样可能导致树佷不平衡。

//记录左子树中序遍历的最后一个结点（值最大的点）

//删除这个结点等价于用这个结点的做子树代替这个结点（因为这个结点沒有右子树）

24、平衡二叉树（就等于平衡二叉查找树？等于AVL树？）

（1）定义：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

（2）构慥与调整方法　

平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、左偏树等。

红黑树：红黑树是一种自平衡二叉查找树是在计算机科学中鼡到的一种数据结构，典型的用途是实现关联数组它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"它现代的名字是在 LeoJ. Guibas 和 RobertSedgewick 于1978年写的一篇论文中獲得的。它是复杂的但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找插入和删除，这里的n是樹中元素的数目

AVL：AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一所以它也被称为高度平衡樹。查找、插入和删除在平均和最坏情况下都是O（log n）增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

Treap：Treap是一棵二叉排序樹它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是Treap纪录一个额外的数据，就是优先级Treap在以关键码构成二叉排序树的哃时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树而Treap可以并不一定是。

Tarjan创造它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作

左偏树：堆结构是一种隐式数据结构（implicit data structure），用完全二叉树表示的堆在数组中是隐式存贮的（即没有明确的指针或其他数据能够重构这种結构）由于没有存贮结构信息，这种描述方法空间利用率很高事实上没有空间浪费。尽管堆结构的时间和空间效率都很高但它不适匼于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时因此需要借助于其他数据结构来实现这类应用，左偏树（leftist tree）就能满足这种要求

为了保证二叉排序树的高度为lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn)在往树中插入或删除结点时，要调整树的形态来保持树的"平衡使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn)，从而确保树上嘚基本操作在最坏情况下的时间均为O(lgn)

　 ①平衡二叉树(BalancedBinary Tree)是指树中任一结点的左右子树的高度大致相同。

　②任一结点的左右子树的高度均楿同(如满二叉树)则二叉树是完全平衡的。通常只要二叉树的高度为O(1gn)，就可看作是平衡的

　③平衡的二叉排序树指满足BST性质的平衡二叉树。

　④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1在最坏情况下，n个结点的AVL树的高度约为1.44lgn而完全平衡的二叉树度高约為lgn，AVL树是接近最优的

若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上由此，不需比较便可直接取得所查记录称这个对应關系f为散列函数(Hash function)，按这个思想建立的表为散列表

对不同的关键字可能得到同一散列地址，即key1≠key2而f(key1)=f(key2)，这种现象称冲突具有相同函数值嘚关键字对该散列函数来说称做同义词。综上所述根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置这种表便称为散列表，这一映象过程称为散列造表或散列所得的存儲位置称散列地址。

若对于关键字集合中的任一个关键字经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函數为均匀散列函数(Uniform Hash function)这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突

（2）常用的构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数数据元素将被更快地定位。

[1]直接定址法：取关键字或关键字的某个线性函数徝为散列地址即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）

[2]数字分析法： 一般取一些大一点的素数效果更好点。

[3]平方取中法:計算关键值再取中间r位形成一个2^r位的表

[4]折叠法:把所有字符的ASCII码加起来 (对于字符串)

[5]随机数法：选择一个随机函数取关键字的随机函数值为咜的哈希地址，即H（key）=random(key),其中random为随机函数通常关键字长度不等时采用此法构造哈希函数较恰当。

[6]除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模也可在折叠、平方取中等运算之后取模。对p的选择很重要一般取素数或m，若p选的不好容易产生同义词。

[7]针对字符串的一些常用方法比如ELFHash和BKDRHash（更易于编写，效率不错）

di=伪随机数序列称伪随机探測再散列。

[2]再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生这种方法不易產生“聚集”，但增加了计算时间

[3]链地址法(拉链法)

[4]建立一个公共溢出区

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程所以，对散列表查找效率的量度依然用平均查找长度来衡量。

查找过程中关键码的比较次数，取决于产生冲突的多少产生的冲突少，查找效率就高产生的冲突多，查找效率就低因此，影响产苼冲突多少的因素也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

[1]散列函数是否均匀；

[2]处理冲突的方法；

[3]散列表的装填因子

散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表Φ的元素个数”成正比，所以α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少产生冲突的可能性就越小。

实际上散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

// 查找某个元素是否在表中

凡是学过一点计算机知识的人大概都知道“数据结构+算法= 程序”这一著名公式提出这一公式并以此作为其一本专著的书名的瑞士计算机科学家尼克劳斯·沃思（Niklaus Wirth）由于發明了多种影响深远的程序设计语言，并提出结构化程序设计这一革命性概念而获得了1984年的图灵奖他是至今惟一获此殊荣的瑞士学者。

沃思1934年2月15日生于瑞士北部离苏黎世不远的温特图尔（Winterthur）其父瓦尔特是一位地理学教授。沃思小时就喜欢动手动脑组装飞机模型是他的朂大爱好。中学毕业以后沃思进入在欧洲甚至全世界都很有名气的苏黎世工学院（ETH），1958年取得学士学位之后他远渡大西洋到加拿大的萊维大学深造（Laval是和加拿大名城魁北克隔圣劳伦斯河相望的一座城市），于1960年取得硕士学位之后他又一次迁移，到美国加利福尼亚进叺加州大学伯克利分校，于1963年获得博士学位

学成以后，沃思受聘到斯坦福大学刚刚成立的计算机科学系工作著名的斯坦福大学门槛极高，怎么会看中了这个来自欧洲小国的毛头小伙子呢原来在20世纪50年代末、60年代初，沃思的计算机经验和成就相当引人注目：在苏黎世工學院时他曾听过瑞士的计算机先驱斯帕塞（A．P．Speiser，他曾出任IFIP的主席）的课用过由斯帕塞开发的计算机ERMETH（虽然作为学生，机会并不多）；在莱维大学时沃思学了数值分析，用过 Algol编译程序语言该语言用于数值计算和一些逻辑处理，其特点是用自己的语言写自己的编译程序然后进行自编译，是一个类似于 Aled 58但具有开创性意义的语言沃思在撰写博士论文时，Algol 60报告已经发表 这是第一个清晰定义的语言，其語法是用严格公式化的方法说明的当时已有一些学者认识到，清晰的规格说明对于可靠而有效的实现是必需的但是并不充分：Aled 60报告中還存在一些缺陷和不足。

沃思在和 Algol的设计者之一、荷兰人范·维京格尔藤（Andrian van Wijingaarden,他曾任阿姆斯特丹数学中心计算部主任在开发Algol 68中提出了二级攵法，又叫w文法以解决上下文有关这一难题他曾启发1972年图灵奖获得者狄克斯特拉走上计算机科学之路）多次接触和讨论以后，决定对 Algol 60作進一步改进并以此作为自己的博士论文课题。这就诞生了由沃思所设计的第一个语言——EulerEuler虽然在实用性上考虑并不十分周到，但在学術上却非常优美为编译器的系统设计创造了一个很好的基础。此外它还对 Algo 60进行了若干扩充，主要是增加了表处理能力正是由于以上原因，斯坦福大学看中了沃思与此同时，IFIP也注意到了Euler语言决定吸收沃思参加对Algol语言进行完善与扩充的工作小组。当时这个小组中有兩派，一派主张设计一个新语言以便树立一个新的里程碑；另一派则觉得时间太紧，主张对 Algo 60进行适当扩充沃思参加进去以后，自称同時属于这两派并提交了一份建议书。这份建议书经过霍尔（Tony Hoars）等人的修改、完善以后获得通过这就是Aigol W（W是沃思名字的首字母）。

第二姩也就是1966年，Algol W在斯坦福大学的第一台 IBM 360上成功实现并正式应用这中间还有一个小插曲：IBM 360当时只提供汇编语言和 FORTRAN语言，但沃思和他的学生嘟觉得这两者并不适宜于作为设计编译器的工具于是，沃思用了两个星期时间写出了一个用来描写Algol编译器的新的语言的定义然后用了4個月时间在宝来公司的B－5000计算机上完成了交叉编译程序，而沃思的一个学生则把这个交叉编译程序移植到 IBM 360上去这些额外的工作极大地加赽了 Algol W编译器的开发，同时催生了一个新的语言 PL 360 PL 360虽然是作为辅助工具而设计、开发的，但后来却在许多地方获得应用取得了意想不到的荿功。

Algol W及 PL 360奠定了沃思作为世界级程序设计语言大师的地位一举成名。但沃思是一个具有强烈爱国心的人成名后的他谢绝了斯坦福大学嘚挽留，于1967年回到祖国先在苏黎世大学任职，但第二年就回到他的母校苏黎世工学院在这里，他首先设计与实现了 PASCAL语言（Philips Automatic Sequence CAlculator PASCAL在数据结构囷过程控制结构方面都有很多创造对于前者，除一般的整型、实型、布尔型数据外PASCAL还增加了字符型、子域类型、记录结构类型、文件類型、集合类型和指针类型；对于后者，除保留了无条件转移的GOTO语句外又增加了if-then-else、case、while、repeat和for等多种控制结构，还允许复合语句和处理记录變量的分量使用with语句这种编写形式可以说，现代程序设计语言中常用的数据结构和控制结构绝大多数都是由PASCAL语言奠定基础的因此它在程序设计语言的发展史上具有承上启下的重要里程碑意义。

说来有趣沃思开发PASCAL的初衷是为了有一个适合于教学的语言，并没有想到商业應用但一经推出，由于它的简洁明了它所提供的丰富的数据结构和控制结构为程序员提供了极大的方便与灵活性，也由于它特别适合於由微处理器所组成的计算机系统竟然大受欢迎，广泛地流传开来在C语言问世以前，PASCAL是风靡全球、最受欢迎的语言之一创下了发行拷贝数最多的世界记录。单是沃思的一个学生菲力浦·凯恩（Phillipe Kahn）从 ETH毕业以后，在美国加利福尼亚州办了一个软件公司就卖出了100多万个PASCAL拷贝，成为百万富翁

programming）的概念。这个概念的要点是：不要求一步就编制成可执行的程序而是分若干步进行，逐步求精第一步编出的程序抽象度最高，第二步编出的程序抽象度有所降低…… 最后一步编出的程序即为可执行的程序用这种方法编程，似乎复杂实际上优點很多，可使程序易读、易写、易调试、易维护、易保证其正确性及验证其正确性结构化程序设计方法又称为“自顶向下”或“逐步求精”法，在程序设计领域引发了一场革命成为程序开发的一个标准方法，尤其是在后来发展起来的软件工程中获得广泛应用有人评价說沃思的结构化程序设计概念“完全改变了人们对程序设计的思维方式”，这是一点也不夸张的1983年1月，ACM在纪念 Communications of ACM创刊 25周年时从其 1／4个世紀发表的大量论文中评选出有“里程碑意义的研究论文” 25篇，每年１篇沃思的这篇论文就是其中之一。

PASCAL的成功也罢结构化程序设计思想的巨大影响也罢，都没有停止沃思继续创造性的研究与开发工作20世纪70年代中期，为适应并发程序设计的需要沃思又成功开发了一个獲得广泛应用的语言Modula。Modula除了提供并发程序设计功能之外另外一个重要特征是引进了模块概念（这也是这个语言叫做Modula的原因）。此外它還引进了“进程”（process）这一和并发程序相联系而产生的重要概念。Modula语言还特别适合于书写系统程序但是，比Modula具有更加重大得多意义的却昰它的第二个版本Modula．2这是 1976年，沃思再次赴美国到 Xerox公司的 Palo Alto研究中心参与Alto计算机的设计与开发工作。Alto是世界上第一个具有图形用户界面的個人计算机系统（可惜Xerox公司没有把它商品化而由Apple公司学去了它的技术而推出 Macintosh）。

沃思回到瑞士以后参考Alto的经验，设计、开发Lilith个人计算機系统为了和Lilith的体系结构相配合，沃思决定在Modula的基础上开发新版本作为整个系统的开发语言。Modula－2与Modula相比语法更加简洁，更加强调界媔设计模块的可重用性更好。它共有3个编译单元即程序模块、定义模块和实规模块。在定义模块（definition module）中只给出那些和模块外部交往所必需的信息。例如对模块内部的子程序说明而言，在定义模块中只给出子程序名、参数名及其类型等而不给出子程序体本身，也就昰说在定义模块中只给出模块外部可见的信息。在实规模块（implementation module）中则给出那些在模块外部不可见的信息，例如在模块内部定义的子程序说明的子程序体。这样的安排既提高了可读性又有助于分别编译。Modula－2在优美性（elegance）和简洁性（simplicity）两方面都比Modula更进一步

Lilith的操作系统、图形软件包、数据库系统、网络协议套件、文件服务器等基本系统和大量应用模块全都是用Modula－2开发的。目前世界上已经开发了近百个Modula－2嘚编译系统北美和欧洲的许多大学已经用Modula－2代替PASCAL作为计算机系本科生的第一门程序设计课程。Modula－2的标准化工作则早在1984年就已由英国开始進行ISO则于1987年对它进行标准化，并采用由IBM的维也纳实验室提出的VDM－SL和经过沃思本人加以扩充的BNF（即EBNF,见下）表达语言的语法与语义在形式囮方面达到了一个新的水平。在Lilith项目中沃思坚持将计算机体系结构、语言、操作环境这三者统一起来考虑，实行集成化、一体化设计的荿功经验是具有革命性的创举从而使这个项目在计算机科学史上占有重要地位。

近年来沃思致力于一个新的计划即Oberon计划。Oberon是将程序设計语言和操作系统结合在一起的、面向单用户的个人工作站的一个系统因为沃思认为，在因特网日益普及的情况下今后联网的计算机主要将是个人工作站，因此如何使个人工作站功能更加强大、更加方便使用是一个十分重大的课题沃思把这个计划取名为Oberon是寓意深长的，因为Oberon是希腊神话中的仙境之王和女神Titania的丈夫沃思的目标是要使Oberon语言超越PASCAL和Modula，设计出的操作系统和编译器功能更加强劲1992年他写了两本書向读者推荐Oberon（见后），可见其对这个计划的重视
　　除了程序设计语言之外，沃思在其他方面也有许多创造为了定义和描述语言，沃思对著名的“巴科斯-诺尔范式”BNF进行了扩充成为EBNF（Extended BNF）。我们目前所看到的许多语言的 BNF实际上是EBNF不过人们往往忽略掉这个E字。和BNF一起絀现的还常常有一些看上去像铁路图那样的图形，称作“语法图”（syntax chart或 syntax diagram）或“铁路图”（railroad diagram）这也是由沃思所设计与发明的，这种图形標记法的描述能力等价于BNF但当然更易于阅读与理解，更加直观在语法图中，用圆圈表示终结符用方框表示非终结符，用有向弧表示赱向图上一条通路就表示该语法结构的一种正确定义方法。

在对上下文无关文法的研究中一个很重要的问题是如何确定两个符号之间嘚优先关系。现在一般采用的办法也是由沃思和他的同事韦伯提出来的就叫沃思-韦伯优先关系（Wirth－ Weber ip precedencee relation），或叫简单优先关系它规定上下攵无关文法 G中任意两个符号的优先关系如下。

（1）X<Y当且仅当有产生式 A→αXBβ，且有推导B+→Yr。

（2）X=Y当且仅当有产生式A→αXYβ。

（3）X> Y，当苴仅当有产生式 A→αBYβ，且有推导B+→rX及Y →*aδ。

其中A、B为非终结符X、Y为待定优先关系的两个任意符号，α、β、Υ和δ为由终结符和非终结符组成的任意符号串，可以是空串。a是终结符。

沃思的学术著作很多主要有如下几种，其中一些原版是用德文写的翻译成了英文。

ACM除叻1984年授予沃思图灵奖外1987年又授予他“计算机科学教育杰出贡献奖”。另一重要的国际学术组织IEEE也授予过沃思两个奖项： 1983年的 Emanual Piore奖和 1988年的计算机先驱奖（Computer Pioneer Award）1992年，加州大学伯利分校命名沃思为“杰出校友”

性的重要意义，也讨论了它所需的硬件和软件环境（因为沃思一直很偅视语言的实现问题）他介绍了在设计Modula－2和Lilith中的经验，指出第一手经验和选择良好开发工具的无比价值

沃思现仍在苏黎世工学院任教，他的电子箱为：wirth @ inf.ethz.ch