2024年5月21日发(作者：)

电脑编程技巧与维护　

递归数据结构的数学定义　

付勇　

（新疆大学数学与系统科学学院，乌鲁木齐８３００４４）　

摘要：分析了数据结构的构成，并在此基础上提出了诸如树型结构和广义表结构等递归的数据结构的数学定义。　

关键词：数据结构；数学定义；树形结构；广义表结构　

Ｍａｔｈｅｍａｔｉｃａｌ　Ｄｅｆｉｎｉｔｉｏｎｓ　ｆｏｒ　Ｒｅｃｕｒｓｉｖｅ　Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅｓ　

ＦＵ　Ｙｏｎｇ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ＆Ｓｙｓｔｅｍ　Ｓｃｉｅｎｃｅｓ，Ｘｉｎｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｕｒｕｍｑｉ　８３００４４）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ａｎａｌｙｓｉｓ　ａｎ　ａｒｇｕｍｅｎｔａｔｉｏｎ　ａｂｏｕｔ　ｃｏｎｓｔｉｔｕｅｎｔｓ　ｏｆ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｗｏｒｋ　ｏｕｔ　ｍａｔｈｅｍａｔｉｃａｌ　ｄｅｆｉｎｉｔｉｏｎｓ　

ｆｏｒ　Ｒｅｃｕｍｉｖｅ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅｓ　ｓｕｃｈ　ａｓ　ｔｒｅｅｓ　ａｎｄ　Ｇｅｎｅｒａｌ　ｌｉｓｔｓ．　

Ｋｅｙ　ｗｏｒｄｓ：Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅｓ；Ｍａｔｈｅｍａｔｉｃａｌ　Ｄｅｆｉｎｉｔｉｏｎ；Ｔｒｅｅ　Ｓｔｕｃｔｕｒｅｓ；Ｇｅｎｅｒａｌｒ　ｌｉｓｔ　Ｓｔｒｕｃｔｕｒｅｓ　

１　引言　

在许多数据结构教材中，对于一些简单的数据结构的逻　

辑表示，通常，除了采用自然语言的描述外，还可以给出确　

切的用数学语言描述的形式定义。　

线性表结构是由一组性质相同的数据元素的集合Ｄ和Ｄ　

上二元关系的集合Ｒ所组成，其形式定义为：　

ＬｉｎｅａｒＬｉｓｔ＝（Ｄ．Ｒ）　

用二元组给出树的定义：　

ｔｒｅｅ＝ｆＫ．　１　

Ｋ＝｛　，ｌ　ｌ　≤　．ｔ７　０。　，∈ＥｌｅｍＴ）ｐ　｝　

其中，”为树中的结点数，ｎ＝Ｏ则为空树，ｒ／　Ｏ则为非空　

树。对于一棵非空树，关系Ｒ应满足下列条件。　

（１）有且仅有一个结点没有前驱，该结点被称为树的根。　

（２）除根结点外，其余每个结点有且仅有一个前驱结点。　

（３）包括树根结点在内的每个结点，可以有任意多个　

（含０个）后继。　

其中　

Ｄ＝ｉ　｝Ｉ　≤”．，７≥０｛　

Ｒ＝｛＜　，．（，卜Ｉ＞ｌ　ｌ　ｉ≤＂～１，／７≥０｝　

上述形式定义用数学语言很好地描述了线性表结构是由　

一

这是一个对树的结点的集合采用了数学语言，而关系采　

用了文字描述的定义。　

同样，参考文献Ｉ３除了也有类似参考文献［１３Ｊ】的说明　

外，在树的抽象数据类型定义中对树形结构还给出了如下的　

描述：　

组数据元素Ｄ组成，且元素之间的线性关系用刚青确地描述　

了出来。任何一个具体的线性表都可以用上述数学语言加以　

描述，并且，采用数学语言描述，更为精确全面，不会产生　

二义性。　

数据对象Ｄ：Ｄ是具有相同特性的数据元素的集合。　

数据关系Ｒ：若Ｄ为空集，则称为空树。　

若Ｄ仅含有一个元素，则Ｒ为空集，否则Ｒ＝｛Ｈ｝，Ｈ是　

如下二元关系：　

然而，一些递归的数据结构诸如树型结构、广义表结构　

等似乎很难给出一个完全用数学语言描述的定义来，大多采　

用的是文字描述的形式，或者部分采用数学语言，部分采用　

文字描述。下面从参考文献中列举几个典型的对树的定义来　

说明这种情况。　

（１）在Ｄ中存在惟一的称为根的数据元素ｒｏｏｔ，它在关系　

Ｈ下无前驱；　

（２）若Ｄ一｛ｒｏｏｔｌ≠　，则存在Ｄ一｛ｒｏｏｔ｝的一个划分Ｄ１，　

例如，参考文献【１】对树形结构的定义是：　

树是由／７（，７≥０）个结点组成的有限集合。如果ｎ＝０，称　

为空树；如果１７≥０，则　

（１）有一个特定的称之为根（，。。ｆ）的结点，它只有直接　

Ｄ２，…，Ｄｍ（ｍ＞０），对任意Ｊ≠ｋ（１≤ｊ，ｋ≤ｍ）有ＤｊｎＤｋ＝　

，

且对任意的ｉ（１≤ｉ≤ｍ），唯一存在数据元素ｘｉ∈Ｄｉ，有＜　

（３）对应于Ｄ一｛ｒｏｏｔ】的划分，Ｈ一｛＜ｒｏｏｔ，ｘｌ＞，…，＜ｒｏｏｔ，　

ｒｏｏｔ，ｘｉ＞ＥＨ；　

后继，没有直接前驱。　

（２）除根以外的其他结点划分为ｍ（ｍ≥０）个互不相交　

的有限集合　．　，…，　小每个集合又是一棵树，并且称之　

为根的子树（ｓｕｂ　ｅ）。每个子树的根结点有且仅有一个直　

接前驱，但可以有０个或多个直接后继。　

ｘｍ＞｝有惟一存在的一个划分Ｈ１，Ｈ２，…，Ｈｍ（ｍ＞０），对任意　

ｊ≠ｋ（１≤ｊ，ｋ≤ｍ）有ＨｊｎＨｋ＝中，且对任意的ｉ（１≤ｉ≤ｍ），　

Ｈｉ是Ｄｉ上的一个二元关系，　（Ｄｉ，｛Ｈｉ｝）是一棵符合本定义　

的树，称为根ｒｏｏｔ的子树。　

这是一个完全用文字进行描述的定义。　

参考文献【２】除了有类似参考文献【１］的说明外，对树　

这个描述尝试对树的关系的定义给出一种数学语言的描　

述。　

形结构还给出了如下的定义：　

在一棵树中，每个结点被定义为它的每个子树的根结点　

的前驱，而它的每个子树的根结点就成为它的后继。由此可　

树是一个有限的、非空的结点集。　

收稿日期：２０１１－０４—１１　

３２≯　２∥　０语１　１．１瞄２与壤　与壤　

Ｓ０ｎ　ＷＡＲＥ　ＤＥＶＥＬ０ＰＭＥＮＴ　ＡＮＤ　ＤＥＳＩＧＮ　

Ｔ　ｌ，　｝ｕ　ｕ　ｕ…ｕ　

它具有下列性质：　

软件开发与设计　

Ｄ　｛ｄ，Ｉ１　，≤＂，＂≥【】ｊ　

Ｒ＝｛ｒＩ　Ｊ１≤　≤＂７　，　≥Ｏｌ　

（１）集合指定的结点ｒ，ｑ做树的根结点。　

存储结构则是逻辑结构在计算机存储器中的映像。　

这个定义与原有定义的区别有两点。第一，它明确地说　

明了数据结构是一组数据元素及数据元素之间相互关系的静　

态结构，是其逻辑结构和存储结构的统称。其中，描述为一　

（２）其余的结点可以划分成，７个子集，　，　，…，　

≥０），其中每一个子集都是一棵树。　

为方便起见，用符号　＝　，　，　，…，　｝来表示树１１０　

该定义对结点的集合给出了一种非常简洁的定义，虽然　

组数据元素，而不是一组性质相同的数据元素，是对这一部　

已经表明了树定义的递归特性，但没有直接给出树中结点之　

间的关系。　

２　对现有数据结构形式定义的分析　

为什么会出现前面所述现象呢？其基本原因是什么呢？　

下面从现有的数据结构形式定义的分析来找出造成这种现象　

的原因所在。　

数据结构的形式定义是对一组关联的数据元素以及这些　

数据元素之间关系的一种逻辑表示形式。通常采用的是二元　

组的描述形式，即数据结构是由两部分构成的，其一是一组　

数据元素的集合（或称为聚集可能更为合适）；其二是数据元　

素之间的关系的集合。数据结构的逻辑表示通常采用如下的　

形式定义：　

Ｄａｔａ

—　

“ｃ，ｚ打　＝（Ｄ，Ｒ）　

其中，Ｄ是一组性质相同的数据元素的有限集合，Ｒ是Ｄ　

上关系的有限集合。Ｄ和兄可表示为：　

Ｄ＝｛ｃ　ｌｌ　，７　０ｊ　

＝

｛ｒ｝ｌ１　Ｊ≤　．ｍ≥０）　

这个形式定义应该普遍适用于各种数据结构的定义，包　

括线性表、树、图以及广义表等数据结构。在表示线性这样　

简单结构甚至图这样的复杂结构，无论是形式定义还是一个　

具体线性表或者图，都能够很好地表示出来。对于树这样的　

具有递归特性的数据结构，如果是一个具体的树，可以用这　

样的定义表示出来，然而要给出一个普遍适用的形式定义，　

却出现了困难，似乎很难用数学语言的形式定义全面地描述　

出来。　

通常认为，在数据结构中Ｄ是一组性质相同的数据元素　

的有限集合。那么，在树这样的数据结构中，Ｄ则是由代表数　

据元素的结点的集合所构成。在这种情况下，对于一棵具体　

的树，可以用有序偶的集合来表示结点之间的关系　。但是，　

在进行树的形式定义时，就出现了问题，很难给出一种用数　

学语言描述的完整形式。问题的根源是认为Ｄ是一组性质相　

同的数据元素的有限集合，而树的基本关系是树的根结点与　

子树间的关系，这样，用树的结点之间的有序偶就无法表示　

这种关系了。　

３　新的数据结构的定义　

【定义】数据结构是一组数据元素及数据元素之间相互关　

系的静态结构，是数据的逻辑结构和存储结构的统称。　

其逻辑结构的形式定义为：　

Ｄａ，　Ｓｔｒｌｔｃｔｕｒｅ＝（Ｄ，Ｒ）　

其中，Ｄ是数据元素的聚集，ＪＲ是Ｄ上关系的集合。Ｄ和　

可表示为：　

分泛化的描述。例如，广义表是一种数据结构，但是，广义　

表中的数据元素有原子元素和子表元素两种性质不同的元素。　

作为形式定义的数据结构应该包括这种情况。第二，它指出　

形式定义中Ｄ是数据元素的聚集（Ｃｏｌｌｅｃｔｉｏｎ）。聚集的限制要　

更加宽松一些，允许聚集中元素的性质可以不同，也允许聚　

集中存在元素值相同（但被看作是不同）的元素。要比说明　

为集合（Ｓｅｔ）更为准确和贴切一些。显然，集合是聚集的特　

例。同时，Ｄ的表示采用的是圆括号，以示区别。　，是关系集　

合Ｒ中的一个关系，　，在原来的定义中通常是采用元素之间关　

系的序偶（有序的或无序的）集来表示。例如一个有ａ，ｂ，ｃ，ｄ　４　

个元素的线性表，通常表示为，’＝：＜“　ｂ＞，＜６．ｃ＞，＜ｃ。ｄ＞：，　

在新的定义中，为了使表示更为简洁，采用元素之间关系的　

序列（有序的或无序的）来表示，例如表示ａ，ｂ，ｃ，ｄ　４个　

元素的有序序列时用尖括号加元素的序列表示，如　

ｒ＝｛＜以，ｂ，Ｃ，ｄ＞｝，而表示无序序列时用圆括号加元素的序　

列表示：ｒ：｛（臼，ｂ，ｃ，　）｝。当需要表示两个元素之间的关系　

时，自然就成为有序偶或无序偶。　

在这个基础上，递归的数据结构的定义就可以迎刃而解　

了。　

４递归的数据结构的定义　

对于具有递归特性的数据结构的定义，文献［４】的定义　

给出了一个非常好的启示。下而将对树和广义表这两种具有　

递归特性的数据结构加以分析，并给出相应的用数学语言描　

述的形式定义。　

４．１树结构的形式定义　

４．１．１一般树　

对于一棵最多具有ｋ个分支的ｋ叉树而言，每个结点的性　

质是相同的，Ｄ应该表示为这些结点的集合。在Ｄ中，除了　

根结点外，其余结点可以按子树　的结点划分为ｋ个互不相交　

的子集，我们可以把这些子集看成是一种特殊的元素，这样，　

Ｄ就可以被认为是由一个根结点元素和ｋ个互不相交的子集元　

素构成的聚集。即　

Ｄ＝（“　，，　，　，…，　ｆ　ｌａｒ，，ｏ，　＋ｋ＝　？，，７ｚ≥０，ｋ　０）　

在这里，Ｄ不再是性质相同的元素的集合，而是不同性质　

¨　Ｉｌ　

的数据元素的聚集，ｍ是聚集中元素的个数，Ｉｌａ　。。ｒｌＩ是树的根　

结点元素的个数，只有０或１两种值，ｋ是结点　ｍｏ，的子树的　

Ｉ｝　Ｉ１　

个数。这样，当ｍ＝０则为空树，Ｉｌａ　ｉＩ＝ｏ，ｍ＞Ｏ则为非空树，　

ｌ＇　｛Ｉ　

ｌａ，　。ｆＩＩ＝ｌ，若ｋ＝ｏ时，树中则只有一个根结点。　

另外，子树相对于根结点，子树的地位是相同的，它们　

‘稿　２技０巧１１写．曩１２护￣ｆ　３

３　

电脑编程技巧与维护　

之间是并列的，且没有顺序之分，为＿ｒ简化表达式，约定子　

，●●●　●●●●‘●，●，●

ｌ　

树集用如下符号表示：　

（Ｔ｝：　２：…：７ｎ＾）　

其中，冒号表示子树之间是并列的，且互不相交，圆括　

号表示相互问无序。　

在这个基础上，就可以很容易地给出树的递归的形式定　

义：　

＝

（Ｄ　Ｒ）　

其中，　

Ｄ＝（　，，　７　，…，７　Ｉ　ｌ　Ｉ，　，Ｉｆ＋膏＝ｎｌ，ｉｉ１　０，ｋ　０）　

｝　

Ｉ１１　ｏＨ，Ｊ‘　

＝　

（７　埘，ｊ　

，，７＝Ｉ时　

＜　…，（７　

）＞Ｉ　ｋ＝，７卜Ｉ｝Ｉｌｌ＞ｌ时　

在这里，　是树Ｔ的根结点，　（１≤　皮）是树Ｔ的一　

棵子树，子树也是一棵树。＜（，　｛　：　：…：　）＞是有序偶，　

表示树　的根结点与子树集的二元关系，也同时表示了树Ｔ　

的根结点与每棵子树　之间的二元关系。　

这个定义清晰、简沽，并且很好地反映ｒ树的递归特性。　

４．１．２二叉树　

对于一棵二叉树，除ｒ一般树的特性外，左右子树又是　

有序的，定义中还要反映左右之别，其递归的形式定义为：　

ＢＴ＝（Ｄ．Ｒ）　

其中，　

Ｄ：（“　。　．Ｂ　．Ｂ　１　０≤｛　。，ｌ　５＋　８　５　＋｛ｌＢ　ｌｌ＝Ⅲ）　

＂　刚、ｊ　

ｆ‘『Ｉ　；　

ｔｎ＝１１１０　

ｆ＜　…　．＜Ｂ　＞＞ｉ　

ｌ叫１　１．　ｔｒｏｔ，Ｉ＝ｌＩＩ　

：＜（｝　，　＜：Ｂ　＞＞；　

，　ｌＩ１　＿＝ｏ　ＩＢｒ，Ｉｌ＝ｌ　

：＜“　，＜　：＞＞ｊ　

，”＞ｌＩ　Ｊ１ｆ，；　＝ｌ，ＩＩ：￣ｒ　一）州‘　

在这里，‘　ｒ　是二叉树ＢＴ的根结点，口　是的ＢＴ左子　

树，艿　是ＢＴ的右子树，子树也是一棵二叉树，＜疗　：曰　＞　

表示左右子树是并列的且左右有序。有序偶　

＜　…　＜Ｂｒ，：Ｂ　＞＞是二叉树Ｂ了１的根结点与子树　・，：，，，’）　

之间的二元关系。特别需要说明的是，南于二叉树左右子树　

是有序的，因此，在只有左子树或只有右子树的情况下，子　

树中间的冒号不能省略。　

４．Ｉ３二叉树表示示例　

给定一棵二叉树如图１所示。　

按照上述二叉树的形式定义，这棵二叉树的可表示为：　

ＢＴ＝（Ｄ．Ｒ）　

其中，　

Ｄ：（甜．６　ｄ　Ｐ．ｇ　／）　

Ｒ：｛＜　＜ｂ　＜ｄ：　．＜ｇ：＞＞：Ｃ．＜：，　＞＞＞：　

在具体描述一棵树时，Ｄ只需将其中的元素依次展开用结　

点元素表示即可。上述描述中，Ｄ中的元素展开的结果显然是　

按先序遍历结点的顺序表示的结点元素的序列，由于Ｄ是元　

３４，　

２Ｏ１１．１２　

，　

毫脯壤程技巧与　罐　

图Ｉ一棵二叉树举例　

素的聚集，与展开的顺序无关，因此，按层序遍历的顺序展　

开也是可以的。　则需要表现二叉树的层次和左右之别，有序　

偶是按递归的顺序以嵌套方式展开的，且左右有别，完整地　

反映了二叉树结点之间的层次和左右关系。　

４．２广义表结构的形式定义　

广义表也是一种递归的数据结构，是南原子元素（Ａｔｏｍ　

Ｅｌｅｍｅｎｔｓ）和子表元素（Ｓｕｂ　Ｇｅｎｅｒａｌ　Ｌｉｓｔｓ）组成的。子表元素　

也是一个广义表。　

４．２．１广义表的形式定义　

虽然广义表是一种递归的数据结构，但是其递归只是体　

现在子表中，而表中的元素与树中元素的层次关系不同，是　

一

种线性关系，因此，其形式定义也有差异。参考树形结构　

的形式定义，广义表的形式定义如下所示：　

ＧＬ＝（Ｄ，Ｒ）　

其中，Ｊ）是一组原子元素和子表元素构成的有限聚集，是　

Ｄ上关系的有限集合。Ｄ和Ｒ可表示为：　

Ｄ＝（　，Ｉ　ｌ　ｉ　ｎｌ，ｎｌ　０，ｅ　∈　４ｌＯｍＳ或　，∈ＧｅｎｅｒａｌＬＪｓｔｓ）　

Ｊ｛｝　ｎｌ＝０时　

Ｒ＝｛｛ｅｌ｝　ｎｌ＝ｌ时　

Ｉ｛＜　，　２　…　＞｝　Ｉ１１　２Ｈ，７　

在这里，＜（，ｌ，　２，…　Ⅲ＞是广义表元素的有序序列，　

这种表示方法要比采用有序偶的序列要更为简洁清晰。　

４．２－２广义表表示示例　

给定一个广义表如图２所示。　

按照上述广义表的形式定义，这个广义表的可表示为：　

ＧＬ＝（Ｄ，只）　

其中，　

Ｄ　（　ｈ，￡‘　ｄ　

Ｒ＝｛＜“．（＜“，　，ｃ，（＜ｄ，ｅ＞）＞），（＜ｄ，　＞）　（Ｊ＞｝　

在具体描述一个广义表时，Ｄ只需将其中的元素依次展开　

（　Ｉ　

图２一个广义表举例　（下转到ｌ２６页）　

电脑编程技巧与维护　

Ｆｕｎｃｔｉｏｎ　ｄｅｌ

ｃｏｄｅ（ｉｎＣＨａｒ）　Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“ｃｈａｒ（３７）”，“＆ｇｔ”）　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“”“”，“＆ｑｕｏｔ；”）　

ｃＲｅｔｕｒｅ＝’’”　

ａｒｒ＝ｓｐｌｉｔ（ｉｎＣＨａｒ，”％”）　

ｆｏｒ　ｅａｃｈ　ｌ　ｉｎ　ａｒｒ　

ｉｆ　ｉ＜＞””ｔｈｅｎ　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“；“，“；；”）　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“一一”，“一”）　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“　”，“”）　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“％”，“”）　

Ｆｉｌｔｅｒ＝ｎｓｔ　

ｃＲｅｔｕｒｅ＝ｃＲｅｔｕｒｅ＆ｃｈｒＷ（ｅｖａｌ（ｄｅｌｃｏｄｅ（ｉ）））　

ｅｎｄｉｆ　

ｎｅｘｔ　

Ｅｎｄ　ｆｏｕｎｔｉｏｎ　

ｄｅｌ

ｃｏｄｅ＝ｃＲｅｔｕｒｅ　

１）利用过滤函数ｆｉｌｔｅｒ　０过滤录入用户名与密码中的危　

险符号的实现方法如下：　

Ｓｅｓｓｉｏｎ（“ｕｓｅｒｎａｎｍｅ”）＝ｆｉｌｔｅｒ（ｒｅｑｕｅｓｔ．ｆｏｒｍ（“ｕｓｅｒｎａｎｍｅ”））　

Ｓｅｓｓｉｏｎ（“ｐａｓｓｗｏｒｄ”）＝ｆｉｌｔｅｒ（ｒｅｑｕｅｓｔ．ｏｆｍ（ｒ“ｐａｓｓｗｏｒｄ”））　

ｅｎｄ　ｆｕｎｃｔｉｏｎ　

２　应用　

（１）在用户注册页而中，当对用户信息保存时，需应用　

ａｄｄ

—

ｃｏｄｅ　０函数对用户密码进行加密。实现过程如下：　

１）读取表单中用户的注册信息，主要包括用户名、密　

２）当系统读取用户信息确定用户是合法用户后，再对用　

户登录密码与解密后的密码进行比较，关键语句如下：　

Ｉｆ　ｄｅｌ

ｃｏｄｅ（ｒｓ（“ｐａｓｓｗｏｒｄ”）＝ｓｅｓｓｉｏｎ（“ｐａｓｓｗｏｒｄ”）ｔｈｅｎ　

＿

码、权限３项信息，在读取密码时利用ａｄｄ＿ｅｏｄｅ函数对密码　

加密，关键代码如下：　

Ｐａｓｓｗｏｒｄ＝ａｄｄ

ｃｏｄｅ（ｒｅｑｕｅｓｔ．ｆｏｒｍ（“ｐａｓｓｗｏｒｄ”）　

Ｗｉｎｄｏｗ．１ｏｃａｔｉｏｎ．ｈｒｅｆ＝‘ｍａｉｎ．ａｓｐ’；　

３　结语　

在当今计算机应用已日益普及社会中，人们在生活和工　

２）检测用户信息，如该用户名信息存在，则禁止用户注　

册，否则将该注册用户信息添加到密码表中。　

（２）在用户登录页而中，首先利用自定义函数ｆｉｌｔｅｒ　０过　

滤录入用户名与密码中的危险符号，然后检测用户名与密码　

是否正确，如正确，再对用户密码进行判断是否使用自定义　

函数ｄｅｌ＿ｃｏｄｅ　０进行解密。　

过滤函数ｆｉｌｔｅｒ　０如下：　

Ｆｕｎｃｔｉｏｎ　ｆｌｉｔｅｒ（ｉｎｓｔｒｉｎｇ）　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｉｎｓｔｒｉｎｇ，“”，“”）　

作过程中越来越离不开计算机，借助计算机技术在提高工作　

效率并给我们带来巨大经济效益的同时，一些“黑客”的出　

现给计算机用户带来了很大的麻烦。虽然针对ＡＳＰ技术介绍　

加密与解密的算法，依据该算法同样在其他技术中也能很好　

地将“黑客”拒之门外。　

参考文献　

【１］吕继迪，等．ＡＳＰ程序开发范例宝典．人民邮电出版社，　

２００９．　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“＜”，“＆Ｉｔ”）　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“＞”，“＆ｇｔ”）　

［２】罗耀军．数据库应用技术．中国铁道出版丰十，２００８．　

Ｎｓｔ＝ｒｅｐｌａｃｅ（ｎｓｔ，“ｃｈａｒ（６０）”，“＆ｌｔ”）　

［３】王晓东．算法设计与分析．清华大学出版社，２００８．　

（上接第３４页）　

用原子元素表示即可。Ｒ则需要表现广义表的层次和同层元素　广义表结构可以表示为：　

的顺序之别。同一层次用尖括号表示其顺序性，其中的原子元　

ＧＬ＝｛（＜Ｕ１，ｃ　，・・・　＞）ｌ　∈Ａｔｏｍ．，　ｊｃ　∈ＧｅｎｅｒａｌＬｉｓｔｓ，　

１　ｉ≤　７　，　０｝　

素用元素值表示，子表则用网括号表示，子表同样用上述方式　

递推的表示，从而完整地表示了广义表的层次和顺序关系。　

图结构可以表示为：　

５　结语　

采用Ｄ和Ｒ所作的数据结构的形式定义的描述，有过度　

概念化之嫌。Ｒ本身已经包含有Ｄ中所表示的数据元素，没　

有必要把Ｄ刻意分离出来，因此，数据结构的形式定义完全　

可以将Ｄ和只的描述合二为一，即采用如下所述的更为简洁　

的方式。例如：　

线性表结构可以表示为：　

Ｇｒａｐｈ＝｛／Ｖ　，’，　／Ｉ　ｉ≠．／．１≤　，．，　ｎｌ，ｎｌ≥０｝　

其中，／　，Ｖ，／表示图中由两个顶点构成的序偶，若有　

序，／Ｖｉ，Ｖ，／表示为＜１’，，Ｖ，＞，若无序，／ｖ，，Ｖ，／表示为　

（　，ｒ，）。　参考文献　

［１】殷人昆，等．数据结构（用面向对象方法与Ｃ＋＋描述）　

【Ｍ】．北京：清华大学出版社，１９９９，７：１６３．　

［２］徐孝凯．数据结构实用教程［Ｍ］．２版．北京：清华大学　

出版社，２００６，９：１７８．　

Ｌ＝｛＜　Ｊ，　２，…，　＞ｌ，？≥０｝　

集合结构可以表示为：　

Ｓ＝｛（口１，　：，…，　）ｌ　１７≥０】　

普通树结构可以表示为：　

【３］严蔚敏，吴伟民．数据结构（Ｃ语言版）【Ｍ】．北京：清华　

，．’＝｛＜口　，，（　７　－・・７：）＞ｌＩ　

二叉树结构可以表示为：　

＋ｋ＝ｎｌ，　＝，，　—ｌ，，｝，≥０；　

大学出版社，１９７９．４：１　１８．　

【４¨美】Ｂｒｕｎｏ　Ｒ．Ｐｒｅｉｓｓ，Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅｓ　ａｎｄ　Ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　

Ｏｂｊｅｃｔ—Ｏｒｉｅｎｔｅｄ　Ｄｅｓｉｇｎ　Ｐａｔｔｅｒｎｓ　ｉｎ　Ｃ＋＋【Ｍ】．北京：电子工　

业出版社，２０００，４：１９７—１９８．　

Ｔ＝｛　，　：Ｔ　ｌＩ“ｌ　ｌｊ＋Ｉｌ曰　Ｉｌ＋ｌＩＢＴ；ｌｌ＝　，　”，≥０｝　

１　２０　１１瞄．１２与壤