《数据结构_广义表的运算》由会员分享，可在线阅读，更多相关《数据结构_广义表的运算（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计 题目：广义表的运算 广义表是线性表的推广。线性表的元素仅限于原子项。广义表的元素或者是原子，或者是一个广义表，有其自身结构。广义表通常用圆括号括起来，用逗号分隔其中的元素。为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。LS=(a1,a2,an),LS是广义表的名字，n为它的长度，若ai是广义表，则称它为LS的子表。若广义表非空(n=1)，则a1是LS的表头，其余元素组成的表(a2,an)称为LS的表尾。一个表展开后所含括号的层数称为广义表的深度。 本设计要求实现广义表的建立、查找、输出、取表头、取表尾及求深度等运算。选择合适的存储结构表示广义表，并能实
2、现下列运算要求：(1)用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。(2)取广义表L的表头和表尾的函数head(L)和tail(L)。(3)能用这两个函数的复合形式求出广义表中的指定元素。(4)由广义表的字符串形式到广义表的转换函数Lists Str_ToLists_(S)；例如Str_ToLists_(“ (a,(a,b),c)”)的值为一个广义表。(5)由广义表到广义表的字符串形式的转换函数char * Lists_To_Str(L)。(6)最好能设置多个广义表 。解：本题的解法如下：1算法设计1.由于广义表(a1,a2,an)中的数据元素可以具有不同的结构（或是原
3、子或是列表）因此难以用顺序存储结构表示，通常采取链式存储结构，每个元素都可以用一个结点表示。一个表结点可由3个域组成：标志域，指针表头的指针域和指针表尾的指针域；而原子结点只需两个域：标志域和值域。2.假设以字符串L=(a1,a2,an) 的形式定义广义表 L，建立相应的存储结构。对广义表进行的操作下递归定义时，可以有两种方法。一种是把广义表分解成表头和表尾两部分；另一种是把广义表堪称含有n个并列子表（假设原子也视作子表）的表。在讨论建立广义表的存储结构时，这两种分析方法均可。3.实现查找，即实现广义表的遍历。4.取表头和表尾：广义表一般记做LS=（1，2，n ）其中，LS是广义表LS=（1，
4、2，n ）的名称，n是它的长度。在线性表的定义中，i（1=iptr.hp;若剩余串非空，则构造第二个表结点L-ptr.tp，并从串S中分解出第二个字串a2，对应创建第二个子广义表以此类推直至剩余串为空串止。6.由广义表到广义表的字符串形式7.求深度：广义表深度定义为广义表中括弧的重数，是广义表的一种量度。例如，多元多项式广义表的深度为多项式中变元的个数。设非空广义表为LS=（1，2，n ）其中i（i=1，2，3）或为原子或为LS的子表，则求LS的深度可分解为n个子问题，每个子问题为求i的深度，若i是原子，则由定义其深度为零，若i是广义表，则和上述一样处理，而LS的深度为各i（i=1，2，3）的
5、深度中最大值加一。空表也是广义表，并由定义可知空表的深度为1。由此可见，求广义表的深度递归算法有两个终结态：空表和原子，且只要求得i（i=1，2，3，）的深度，广义表的深度就容易求得了。显然，它应比子表深度的最大值多1.广义表 LS=（1，2，n ）的深度DEPTH（LS）的递归定义为基本项：（）当为空表时（）当为原子时归纳项：（）（）由此定义容易写出求深度的递归函数。假设是型的变量则表明广义表为空表，表明是原子。反之，指向表结点，该结点中的指针指向表头，即为的第一个子表，而结点中的指针所指表尾结点中的指针指向的第二个子表。在第一层中由相连的所有尾结点中的指针均指向的子表。由此可得广义表深度的
6、递归算法。2程序实现上机实现算法时由于具体问题牵涉到各种方面，难以综合实现，可以分为几个小的模块将程序先进行初步整合具体程序：#include#include#includeclass GenListNodefriend class GenList;public:int utype; /0,1,2,3unionintintinfo;charcharinfo;GenListNode* hlink;value;GenListNode* tlink;GenListNode();class GenListpublic:GenListNode * first;int Sever( char* &hstr
7、,char * &s );void strncpy1( char* &hstr,char* &s,int comma );GenListNode* CreatList( char* s );void Creat( char* s );void Display( void );void Display( char * s ,GenListNode* ls);void show( GenListNode* ls );void head(GenListNode* &u);void tail(GenListNode* &u);int display(GenListNode* u1,GenListNod
8、e* u);void find(char* s,GenListNode* &u);void GenList:Creat( char* s )first=CreatList(s);GenListNode* GenList:CreatList( char* s )GenListNode *ls,*head;ls=new GenListNode();head=ls;ls-utype=0;if( strlen(s)tlink=NULL;elsechar* sub;while( strlen(s)2 )ls = ls-tlink = new GenListNode();ls-utype=Sever(su
9、b,s); switch( ls-utype )case 1:ls-value.intinfo=atoi(sub);break;case 2:ls-value.charinfo=sub0;break;case 3:ls-value.hlink=CreatList( sub );break;ls-tlink=NULL;return head;int GenList:Sever( char* &hstr,char* &s )char ch=s0;int n=strlen( s );int i=0,k=0,comma=-1;int x=0,y=0;while( in & (ch!=, | k!=0)
10、 )if( ch=( )k+;elseif( ch=) )k-;i+;ch=si;if(ch=, & x=0)x=10;comma=i;if(k=1 & x8)x+;if(x=2)comma=i;if( k!=0 )cout括号不配对! 退出程序!=3 )return 3;elseif( hstr0=0 )return 1;if( hstr0=a )return 2;return 1;void GenList:strncpy1 (char* &hstr,char* &s,int comma )int n=strlen(s);hstr=new charn;for( int t=0,i=1;ico
11、mma;i+ )hstrt=si;t+;hstrt=0;for( t=1,i=comma+1;iutype=0)while( ls!=NULL )switch( ls-utype )case 0:si=(;i+;coutvalue.intinfo-0);i+;coutvalue.intinfo;if(ls-tlink!=NULL)si=,;i+;coutvalue.charinfo;i+;coutvalue.charinfo;if(ls-tlink!=NULL)si=,;i+;coutvalue.hlink );if(ls-tlink!=NULL)si=,;i+;couttlink;si=);i+;
