溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了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相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
