JavaScript數(shù)據(jù)結(jié)構(gòu)之廣義表的定義與表示方法詳解
本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)之廣義表的定義與表示方法。分享給大家供大家參考，具體如下：
廣義表是線性表的推廣，也有人稱其為列表。 那么它和線性表有什么區(qū)別呢？線性表中每個(gè)成員只能是單個(gè)元素，而廣義表中的成員可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表的原子和子表。下面舉幾個(gè)廣義表的例子。
A=();
B=(e);
C=(a,(b,c,d));
D=((),(e),(a,(b,c,d)));
E=(a,E);
由于廣義表中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)（原子或列表），因此難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。由于列表中的元素可以是原子也可以是列表，所以需要兩種結(jié)構(gòu)的節(jié)點(diǎn)，一種是表節(jié)點(diǎn)，一種是原子節(jié)點(diǎn)。
一個(gè)表節(jié)點(diǎn)由三個(gè)域組成，標(biāo)志域、指向表頭的指針域、指向表尾的指針域。而原子節(jié)點(diǎn)只需要兩個(gè)域，標(biāo)志域和值域。如下圖：
上面講到的五個(gè)列表的存儲(chǔ)結(jié)構(gòu)如下圖：
我們用JavaScript來實(shí)現(xiàn)廣義表及其基本操作吧。
首先需要定義廣義表的存儲(chǔ)結(jié)構(gòu)：
var ATOM=0;
var LIST=1;
//廣義表的存儲(chǔ)結(jié)構(gòu)
function ListNode(){
//標(biāo)識(shí)位
this.tag=undefined;
//原子結(jié)點(diǎn)的值域
this.atom=null;
//列表結(jié)點(diǎn)的值域
this.ptr={
hp:null,
tp:null
};
}
然后是創(chuàng)建廣義表的過程：
//創(chuàng)建廣義表
ListNode.prototype.createList=function(string){
string=string.trim();
//創(chuàng)建單原子廣義表
var q;
if(/^[\w-]+$/.test(string)){//含有單字符
this;tag=ATOM;
this.atom=string;
}else{
this.tag=LIST;
var p =this;
//去掉最外層括號(hào)（和）
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為第一個(gè)逗號(hào)分隔索引
if(i<n){
h=sub.substr(0,i-1);//每次遍歷取出第一個(gè)結(jié)點(diǎn)，無論是原子還是列表
sub=sub.substr(i,n-i);
}else{//最后一組
h=sub;
sub='';
}
if(h==='()'){//空子表無表頭結(jié)點(diǎn)
p.ptr.hp=null;
}else{//創(chuàng)建表頭結(jié)點(diǎn)
this.createList.call((p.ptr.hp=new ListNode()),h);
}
q=p;
//創(chuàng)建表尾結(jié)點(diǎn)
if(sub){
p=new ListNode();
p.tag=LIST;
q.ptr.tp=p;
}
}while(sub);
q.ptr.tp=null;
}
};
接下就是求廣義表的深度，深度的定義為廣義表中括弧的重?cái)?shù)，是廣義表的一種量度。例如，多元多項(xiàng)式廣義表的深度為多項(xiàng)式中變?cè)膫€(gè)數(shù)。設(shè)LS=（a1,a2,a3,…,an），求LS的深度可以分解為n個(gè)之問題，每個(gè)子問題為求ai的深度。如果ai是原子，則定義其深度為0，如果ai是廣義表，則LS的深度為最大ai的深度+1?？毡硪彩菑V義表，所以深度為1。實(shí)現(xiàn)代碼如下：
//求廣義表的深度
ListNode.prototype.depth=function(){
return getDepth(this);
}
function getDepth(list){//深度為括號(hào)的重?cái)?shù)，也可理解為左括號(hào)出現(xiàn)的個(gè)數(shù)
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;
}
}
最后我們創(chuàng)建測試案例：
var node=new ListNode();
node.createList('((),(a),(b,(c,d,e)))');
alert(node.depth());//5
node結(jié)點(diǎn)詳細(xì)如下圖：
完整代碼如下：
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<script type="text/javascript">
var ATOM=0;
var LIST=1;
//廣義表的存儲(chǔ)結(jié)構(gòu)
function ListNode(){
//標(biāo)識(shí)位
this.tag=undefined;
//原子結(jié)點(diǎn)的值域
this.atom=null;
//列表結(jié)點(diǎn)的值域
this.ptr={
hp:null,
tp:null
};
}
//創(chuàng)建廣義表
ListNode.prototype.createList=function(string){
string=string.trim();
//創(chuàng)建單原子廣義表
var q;
if(/^[\w-]+$/.test(string)){//含有單字符
this.tag=ATOM;
this.atom=string;
}else{
this.tag=LIST;
var p =this;
//去掉最外層括號(hào)（和）
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為第一個(gè)逗號(hào)分隔索引
if(i<n){
h=sub.substr(0,i-1);//每次遍歷取出第一個(gè)結(jié)點(diǎn)，無論是原子還是列表
sub=sub.substr(i,n-i);
}else{//最后一組
h=sub;
sub='';
}
if(h==='()'){//空子表無表頭結(jié)點(diǎn)
p.ptr.hp=null;
}else{//創(chuàng)建表頭結(jié)點(diǎn)
this.createList.call((p.ptr.hp=new ListNode()),h);
}
q=p;
//創(chuàng)建表尾結(jié)點(diǎn)
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){//深度為括號(hào)的重?cái)?shù)，也可理解為左括號(hào)出現(xiàn)的個(gè)數(shù)
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>
由于廣義表的應(yīng)用多在于數(shù)學(xué)領(lǐng)域的公式推導(dǎo)和演算上，這里就不再詳解了。
這里補(bǔ)充一下廣義表的長度和深度算法：
廣義表LS=(f,(),(e),(a,(b,c,d)))的長度是多少,深度是多少
例如上表、長度為4、深度為3、為什么呢
長度的求法為最大括號(hào)中的逗號(hào)數(shù)加一、LS最大括號(hào)內(nèi)有
1. f 元素后邊有個(gè)逗號(hào)、
2.（）元素后有個(gè)逗號(hào)、
3.（e）元素后有個(gè)逗號(hào)
4. （a，（b，c，d））后邊沒有逗號(hào) ----把這個(gè)看成是一個(gè)元素
也就是三個(gè)逗號(hào) 同樣被分成四組、長度就為四了
深度的求法為上面每個(gè)元素的括號(hào)匹配數(shù)加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
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
- JS實(shí)現(xiàn)的二叉樹算法完整實(shí)例
- JS二叉樹的簡單實(shí)現(xiàn)方法示例
- JS中的二叉樹遍歷詳解
- javascript數(shù)據(jù)結(jié)構(gòu)之二叉搜索樹實(shí)現(xiàn)方法
- JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹詳解
- JavaScript數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)組的表示方法示例
- javascript數(shù)據(jù)結(jié)構(gòu)之串的概念與用法分析
- javascript編程實(shí)現(xiàn)棧的方法詳解【經(jīng)典數(shù)據(jù)結(jié)構(gòu)】
- JS實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎痉椒ㄊ纠窘?jīng)典數(shù)據(jù)結(jié)構(gòu)】
- JS實(shí)現(xiàn)線性表的順序表示方法示例【經(jīng)典數(shù)據(jù)結(jié)構(gòu)】
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實(shí)現(xiàn)
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉查找樹的定義與表示方法
相關(guān)文章
JavaScript 開發(fā)工具webstrom使用指南
本文給大家推薦了一款非常熱門的javascript開發(fā)工具webstrom,著重介紹了webstrom的特色功能、設(shè)置技巧、使用心得以及快捷鍵匯總，非常的全面。2014-12-12
基于Javascript實(shí)現(xiàn)返回頂部按鈕
這篇文章主要為大家詳細(xì)介紹了基于Javascript實(shí)現(xiàn)返回頂部按鈕，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-02-02
基于JS實(shí)現(xiàn)操作成功之后自動(dòng)跳轉(zhuǎn)頁面
這篇文章主要介紹了基于JS實(shí)現(xiàn)操作成功之后自動(dòng)跳轉(zhuǎn)頁面的相關(guān)知識(shí)，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-09-09
js數(shù)據(jù)類型轉(zhuǎn)換與流程控制操作實(shí)例分析
這篇文章主要介紹了js數(shù)據(jù)類型轉(zhuǎn)換與流程控制操作,結(jié)合實(shí)例形式分析了JavaScript數(shù)據(jù)類型轉(zhuǎn)換與流程控制相關(guān)原理、操作技巧與使用注意事項(xiàng),需要的朋友可以參考下2019-12-12
JS監(jiān)聽微信、支付寶等移動(dòng)app及瀏覽器的返回、后退、上一頁按鈕的事件方法
JS如何實(shí)現(xiàn)頁面截屏功能實(shí)例代碼
JS腳本加載后執(zhí)行相應(yīng)回調(diào)函數(shù)的操作方法
