【word】 广义表的头尾链表表示及算法的实现

【word】 广义表的头尾链表表示及算法的实现 广义表的头尾链表表示及算法的实现 2009年第6期 中图分类号:TP311.12文献标识码:A文章编 号:1009—2552(2009)06—0157—02 广义表的头尾链表表示及算法的实现 钟治初 (嘉应学院计算机系,梅州514015) 摘要:讨论了广义表的头尾链表存储表示及相关算法的实现,包括广 义表的建立,输出,销 毁,复制,求表头,求表尾,计算深度等算法的实现. 关键词:广义表;数据结构;算法 Thegeneralizedlistusingheadandtaillinkand realizationofsomealgorithms ZHONG1j—chu (DepartmentofCoin~ter,JiayingUniversity,Meizhou514015,Olina) Abstract:Inthispaperthegeneralizedlistusingheadandtaillinkisdiscussed,a ndsomealgorithms, includingcreation,output,deletion,copy,gettinghead,gettingtail,calculatin gdepthofgeneralizedlist,alealso discussed. Keywords:generallist;datastructure;algorithm 0引言 广义表也称为列表,其形式为IS=(a,a2,…, an),其中每一凰可能是原子,也可能是广义表.这 一 点决定了广义表只能使用链表来存储表示.根据 不同的理解和需要,可以使用不同形式的链表来存 储表示.本文就将广义表按头尾链表来存储表示, 用C/C++语言来实现,并在此表示下来讨论广义表 的一些算法的实现,包括广义表的建立,输出,销毁, 复制,求表头,求表尾,计算深度等算法. 1存储表示及算法的实现 由于非空广义表LS=(a,a2,…,a|1),由表头 Head(IS)=a和表尾Tail(LS)=(a2,…,al1)完全决 定,因此,广义表的结点应该存储表头和表尾.为了 区分表结点和原子结点,增加一个标志tag,用0表 示原子结点,用1表示表结点.为了使二种结点有 比较统一的结构,规定原子结点的表尾指针域为空. 广义表的头尾链表存储表示如下: typedefcharElemType;//假定原子的数据类型 为字符; typedefstmctGLNode {inttag;//0表示原子结点,1表示子表结点; union{ElemTypedata; GLNode*hp; }val;//值或指向表头;若为原子,则存放值;若 为子表,则存放表头指针; GI_Node*tp;//指向表尾;若为原子,则tp为空. }GLNode,*GList; 1.1广义表的建立算法 假定建立广义表时,以广义表的书写形式为输 人,并且假定英文小写字母表示原子.则建立广义 表的算法如下: voidCreateGList(GList&L) {charch; cin>>ch: if(ch==)){L=0;retum;} elseif(ch>=at&&ch<=Z) {L=newGLNode;L—Iag=O;L—va1.data=ch; tp=0;} elseif(ch==() {L=newGLNode;L—tag=1;CreateGList(L— va1.hp); iva1.hp==0){tp=O;return;} GLNodeP; P=L;cin>>ch; 收稿日期:2oo9—01一l2 作者简介:钟治初(1964一),男,副教授,研究方向为算法分析与设计. ?__—— 157?--—— while(ch==,){ptp=newGLNode;P=p ;I)_tag=1;CreateGList(p-’~va1.hp);cin>>ch;} p—cp=0; }} 以上的算法采用递归算法,因为广义表本身是 递归定义的,因此,写成递归算法容易理解. 1.2广义表的输出算法 按照上述算法建立的广义表的存储表示,将广 义表按书写形式输出,算法如下: voidDisplayGList(GListL) {if(L==O)return; elseif(tag==O)cout<<va1.data; else{cout<<”(“;DisplayGList(L--~va1.hp); GLNodep;P=I『,p; while(p){cout<<”,”;DisplayGList(pva1.hp); P=I)_+tI);} cout<<”)”; }} 1.3广义表的销毁算法 由于广义表是用链表表示的,每一个结点都是 动态生成的,因此,广义表使用完毕后,应该将广义 表结构销毁.销毁算法如下: voidDestroyGList(GList&L) {if(L==0)return; elseif(t==0){deleteL;L=O;} elseif(tag==1&&卜Va1.hp==0&& tp==0){deleteL;L=0;} else{DestroyGList(L--~va1.hp);DestroyGList(L--~ tp);deleteL;L=0;} } 1.4广义表的复制算法 将广义表结构进行复制,得到一个相同结构的 广义表.注意到原来的广义表的特殊情况,包括空 表和原子等情形.当然,原子在严格意义下不是广 义表,但经过某些运算后可能会出现单个原子的情 形,例如求表头运算. GUstGListCopy(GListL) {GListT; iL==0)return0; else{T=newGLNode;卜tag=tag; tag==0){T—va1.data=L—va1.data; iL— 1L+tp=0;} else}T—va1.hp=GListCopy(L—va1.hp);T— tp=GListCopy(tp);} retumT: }}. 1.5求广义表的表头运算的算法 广义表的表头可能是空的,可能是原子,也可能 一 158一 是广义表. GListHead(GListL) fGUstH; if(L==0){cout,空表无表头!\n”;returnO;} .elseif(tag==0){cout<<”原子无表头!\ nt;l~tllnl0;} else{H=GListCopy(L—va1.hp);if(H==0) eout<<”空表无表头!\ntt;returnH;} } 1.6求广义表的表尾运算的算法 求广义表的表尾运算时,同样要注意到广义表 的特殊情况. GListTail(GUstL) {GUstT; if(L==0){cout<<”空表无表尾!\n”;return 0;} elseif(L—tag==0){cout<<”原子无表尾!\ n;retunl0;} else{T=GListCopy(L--”tp); if(T=:0){T=newGLNode;T—tag=1; tp=O;T-’va1.hp:0;} returnT;} } 1.7求广义表的深度运算算法 广义表的深度定义为广义表中括号的层数.算 法如下: intDepthGList(GListL) {if(L==0)returnO; elseif(tag=0)return0; elseif(+,.hp=:0)return1; else{intml,m2;ml=1+DepthGList(Lva1. hp);m2=DepthGList(L-~tp); if(ml>=m2)returnml;elseretumm2; }} 2结束语 广义表是一种比较复杂的数据结构,相当于二 叉树结构,目前大多数数据结构与算法的教材都没 有详细讨论其存储结构及相应的算法.根据教学实 践将广义表的相关算法 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf ,并对上面的算法进行 了完整的测试. 参考文献: [1]严蔚敏,吴伟民.数据结构:C语言版[M].北京:清华大学出版 社,2OO2. [2]李春保.数据结构 教程 人力资源管理pdf成真迷上我教程下载西门子数控教程protel99se入门教程fi6130z安装使用教程 [M].北京:清华大学出版社,2OO5. [3]张乃孝.算法与数据结构——c语言描述[M].2版.北京:高等 教育出版社.9.OO6. [4】徐孝凯.数据结构实用教程[M].2版.北京:清华大学出版社, 2OO6. 责任编辑:李光辉