JavaScript数据结构之广义表的定义与表示方法详解
发布于 2017-06-07 21:47:36 | 162 次阅读 | 评论: 0 | 来源: 网友投递
这里有新鲜出炉的Javascript教程，程序狗速度看过来！
JavaScript客户端脚本语言
Javascript 是一种由Netscape的LiveScript发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言，主要目的是为了解决服务器端语言，比如Perl，遗留的速度问题，为客户提供更流畅的浏览效果。
这篇文章主要介绍了JavaScript数据结构之广义表的定义与表示方法,简单讲述了广义表的原理与相关概念,并结合实例形式分析了javascript定义与使用广义表的相关操作技巧,需要的朋友可以参考下
本文实例讲述了JavaScript数据结构之广义表的定义与表示方法。分享给大家供大家参考，具体如下：
广义表是线性表的推广，也有人称其为列表。 那么它和线性表有什么区别呢？线性表中每个成员只能是单个元素，而广义表中的成员可以是单个元素，也可以是广义表，分别称为广义表的原子和子表。下面举几个广义表的例子。
A=();
B=(e);
C=(a,(b,c,d));
D=((),(e),(a,(b,c,d)));
E=(a,E);
由于广义表中的数据元素可以具有不同的结构（原子或列表），因此难以用顺序存储结构表示，通常采用链式存储结构。由于列表中的元素可以是原子也可以是列表，所以需要两种结构的节点，一种是表节点，一种是原子节点。
一个表节点由三个域组成，标志域、指向表头的指针域、指向表尾的指针域。而原子节点只需要两个域，标志域和值域。如下图：
上面讲到的五个列表的存储结构如下图：
我们用JavaScript来实现广义表及其基本操作吧。
首先需要定义广义表的存储结构：
var ATOM=0;
var LIST=1;
//广义表的存储结构
function ListNode(){
//标识位
this.tag=undefined;
//原子结点的值域
this.atom=null;
//列表结点的值域
this.ptr={
hp:null,
tp:null
};
}
然后是创建广义表的过程：
//创建广义表
ListNode.prototype.createList=function(string){
string=string.trim();
//创建单原子广义表
var q;
if(/^[\w-]+$/.test(string)){//含有单字符
this;tag=ATOM;
this.atom=string;
}else{
this.tag=LIST;
var p =this;
//去掉最外层括号（和）
var sub=string.substr(1,string.length-2);
do{
var h,
i=0,
k=0,
n=sub.length,
ch;
do{
ch=sub[i++];
if(ch=='('){
++k;
}else if(ch==')'){
--k;
}
}while(i<n&&(ch!=','||k!=0));
//i为第一个逗号分隔索引
if(i<n){
h=sub.substr(0,i-1);//每次遍历取出第一个结点，无论是原子还是列表
sub=sub.substr(i,n-i);
}else{//最后一组
h=sub;
sub='';
}
if(h==='()'){//空子表无表头结点
p.ptr.hp=null;
}else{//创建表头结点
this.createList.call((p.ptr.hp=new ListNode()),h);
}
q=p;
//创建表尾结点
if(sub){
p=new ListNode();
p.tag=LIST;
q.ptr.tp=p;
}
}while(sub);
q.ptr.tp=null;
}
};
接下就是求广义表的深度，深度的定义为广义表中括弧的重数，是广义表的一种量度。例如，多元多项式广义表的深度为多项式中变元的个数。设LS=（a1,a2,a3,…,an），求LS的深度可以分解为n个之问题，每个子问题为求ai的深度。如果ai是原子，则定义其深度为0，如果ai是广义表，则LS的深度为最大ai的深度+1。空表也是广义表，所以深度为1。实现代码如下：
//求广义表的深度
ListNode.prototype.depth=function(){
return getDepth(this);
}
function getDepth(list){//深度为括号的重数，也可理解为左括号出现的个数
if(!list){
return 1;
}else if(list.tag===ATOM){
return 0;
}else {
var m=getDepth(list.ptr.hp)+1;
var n=getDepth(list.ptr.tp);
return m>n?m:n;
}
}
最后我们创建测试案例：
var node=new ListNode();
node.createList('((),(a),(b,(c,d,e)))');
alert(node.depth());//5
node结点详细如下图：
完整代码如下：
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script type="text/javascript">
var ATOM=0;
var LIST=1;
//广义表的存储结构
function ListNode(){
//标识位
this.tag=undefined;
//原子结点的值域
this.atom=null;
//列表结点的值域
this.ptr={
hp:null,
tp:null
};
}
//创建广义表
ListNode.prototype.createList=function(string){
string=string.trim();
//创建单原子广义表
var q;
if(/^[\w-]+$/.test(string)){//含有单字符
this.tag=ATOM;
this.atom=string;
}else{
this.tag=LIST;
var p =this;
//去掉最外层括号（和）
var sub=string.substr(1,string.length-2);
do{
var h,
i=0,
k=0,
n=sub.length,
ch;
do{
ch=sub[i++];
if(ch=='('){
++k;
}else if(ch==')'){
--k;
}
}while(i<n&&(ch!=','||k!=0));
//i为第一个逗号分隔索引
if(i<n){
h=sub.substr(0,i-1);//每次遍历取出第一个结点，无论是原子还是列表
sub=sub.substr(i,n-i);
}else{//最后一组
h=sub;
sub='';
}
if(h==='()'){//空子表无表头结点
p.ptr.hp=null;
}else{//创建表头结点
this.createList.call((p.ptr.hp=new ListNode()),h);
}
q=p;
//创建表尾结点
if(sub){
p=new ListNode();
p.tag=LIST;
q.ptr.tp=p;
}
}while(sub);
q.ptr.tp=null;
}
};
//求广义表的深度
ListNode.prototype.depth=function(){
return getDepth(this);
}
function getDepth(list){//深度为括号的重数，也可理解为左括号出现的个数
if(!list){
return 1;
}else if(list.tag===ATOM){
return 0;
}else {
var m=getDepth(list.ptr.hp)+1;
var n=getDepth(list.ptr.tp);
return m>n?m:n;
}
}
var node=new ListNode();
node.createList('((),(a),(b,(c,d,e)))');
alert(node.depth());//5
</script>
</body>
</html>
由于广义表的应用多在于数学领域的公式推导和演算上，这里就不再详解了。
这里补充一下广义表的长度和深度算法：
广义表LS=(f,(),(e),(a,(b,c,d)))的长度是多少,深度是多少
例如上表、长度为4、深度为3、为什么呢
长度的求法为最大括号中的逗号数加一、LS最大括号内有
1. f 元素后边有个逗号、
2.（）元素后有个逗号、
3.（e）元素后有个逗号
4. （a，（b，c，d））后边没有逗号 ----把这个看成是一个元素
也就是三个逗号 同样被分成四组、长度就为四了
深度的求法为上面每个元素的括号匹配数加1
1. f元素的深度为0+1=1
2. （）元素深度为1+1=2
3. （e）元素深度为1+1=2
4 . （a，（b，c，d））元素的深度为2+1=3
所以深度为3
综上所诉、长度为4、深度为3
希望本文所述对大家JavaScript程序设计有所帮助。