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
接下就是求广义表的深度,深度的定义为广义表中括弧的重数,是广义表的一种量度。例如,多元多项式广义表的深度为多项式中变元的个数。设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结点详细如下图:
完整代码如下:
由于广义表的应用多在于数学领域的公式推导和演算上,这里就不再详解了。
这里补充一下广义表的长度和深度算法:
广义表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相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
当前名称:JavaScript数据结构之广义表的定义与表示方法详解
转载来源:http://scyanting.com/article/jeopco.html