（可编）数据结构_广义表的运算.docx

文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持 .《数据结构》课程设计题目：广义表的运算广义表是线性表的推广线性表的元素仅限于原子项广义表的元素或者是原子，或者是一个广义表，有其自身结构广义表通常用圆括号括起来，用逗号分隔其中的元素 为了区分原子和广义表， 书写时用大写字母表示广义表， 用小写字母表示原子 LS=(a1,a2, ,an),LS 是广义表的名字， n 为它的长度， 若 ai 是广义表，则称它为 LS 的子表若广义表非空 (n>=1) ，则 a1 是 LS 的表头，其余元素组成的表 (a2, ,an) 称为 LS 的表尾一个表展开后所含括号的层数称为广义表的深度本设计要求实现广义表的建立、查找、输出、取表头、取表尾及求深度等运算选择合适的存储结构表示广义表，并能实现下列运算要求：(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 个域组成： 标志域， 指针表头的指针域和指针表尾的指针域；而原子结点只需两个域：标志域和值域2. 假设以字符串 L=(a1,a2, ,an) 的形式定义广义表 L，建立相应的存储结构 对广义表进行的操作下递归定义时， 可以有两种方法 一种是把广义表分解成表头和表尾两部分； 另一种是把广义表堪称含有 n 个并列子表（假设原子也视作子表）的表在讨论建立广义表的存储结构时，这两种分析方法均可3. 实现查找，即实现广义表的遍历4. 取表头和表尾：广义表一般记做 LS=（α 1，α 2 ， α n ）其中， LS 是广义表LS=（α 1，α2 ， αn ）的名称，n 是它的长度性表的定义中， α（i 1<=i<=n ）只限于单个元素，而在广义表的定义中，α i 可以是单个元素，也可以是广义表， 分别称为广义表 LS 的原子和子表。

当广义表非空时，称第一个元素α i 为 LS 的表头，称其余的元素组成的表（α 2，α 3， α n）为 LS 的表尾5. 由广义表的字符串形式到广义表转换函数：由于 S 中的每个子串 i 定义 L 的10文档来源为 :从网络收集整理.word 版本可编辑 .欢迎下载支持 .一个子表，从而产生 n 个子问题，即分别由这 n 个子串 ( 递归) 建立 n 个子表， 再组合成一个广义表其中：可以直接求解的两种简单情况为：以串‘（）’建立的广义表是空表，由单字符建立的广义表只是一个原子结点若是其他情况， 因为第一个子表的标志域为一， 代表指向广义表的头指针 指示表头的指针域指向第一个子表的头指针 相邻子表之间用表结点相连接 综上：若 S = ( ) 则L = NIL ；否则，构造第一个表结点 *L ，并从串 S中分解出第一个子串 1 ，对应创建第 一个 子广义表 L->ptr.hp; 若剩余串 非空 ， 则 构造 第二 个表结点L->ptr.tp ，并从串 S 中分解出第二个字串 2，对应创建第二个子广义表 以 此类推直至剩余串为空串止6. 由广义表到广义表的字符串形式7. 求深度：广义表深度定义为广义表中括弧的重数， 是广义表的一种量度。

例如， 多元多项式广义表的深度为多项式中变元的个数 设非空广义表为 LS=（α 1，α 2， α n ）其中α i （i=1 ，2，3 ）或为原子或为 LS 的子表，则求 LS 的深度可分解为 n 个子问题，每个子问题为求α i 的深度，若α i 是原子，则由定义其深度为零，若α i 是广义表，则和上述一样处理，而 LS 的深度为各α i（i=1 ，2，3 ） 的深度中最大值加一空表也是广义表，并由定义可知空表的深度为 1由此可见， 求广义表的深度递归算法有两个终结态： 空表和原子， 且只要求得α i （i=1 ，2，3， ）的深度，广义表的深度就容易求得了显然，它应比子表深 度的最大值多 1.广义表 LS= （α 1，α 2， α n ）的深度 DEPTH（LS）的递归定义为基本项：ＤＥＰＴＨ（ＬＳ）＝１ 当ＬＳ为空表时ＤＥＰＴＨ（ＬＳ）＝０ 当ＬＳ为原子时归纳项：ＤＥＰＴＨ（ＬＳ）＝１＋Ｍａｘ｛ＤＥＰＴＨ（α ｉ）｝ ｎ＞＝１由此定义容易写出求深度的递归函数 假设Ｌ是ＧＬｉｓｔ型的变量则Ｌ＝ＮＵ ＬＬ表明广义表为空表，Ｌ－＞ｔａｇ＝０表明是原子反之，Ｌ指向表结点， 该结点中的ｈｐ指针指向表头， 即为Ｌ的第一个子表， 而结点中的ｔｐ指针所指表尾结点中的ｈｐ指针指向Ｌ的第二个子表。

在第一层中由ｔｐ相连的所有尾结点中的ｈｐ指针均指向Ｌ的子表由此可得广义表深度的递归算法2 程序实现上机实现算法时由于具体问题牵涉到各种方面， 难以综合实现， 可以分为几个小的模块将程序先进行初步整合具 体 程 序 ： #include #include #include class GenListNode{friend class GenList;public:int utype; //0,1,2,3 union{int intinfo;char charinfo;GenListNode* hlink;}value; GenListNode* tlink; GenListNode(){}};class GenList{ public:GenListNode * first;int Sever( char* &hstr,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,GenListNode* 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)<=2 ){ls->tlink=NULL;}else{char* sub;while( strlen(s)>2 ){ls = ls->tlink = new GenListNode(); ls->utype=Sever(sub,s);switch( ls->utype ){case 1:ls->value.intinfo=atoi(sub);break; case 2:ls->value.charinfo=sub[0];break;case 3:ls->value.hlink=CreatList( sub );break;}}ls->tlink=NULL;}return head;}int GenList::Sever( char* &hstr,char* &s ){char ch=s[0]; int n=strlen( s );int i=0,k=0,comma=-1; int x=0,y=0;while( i=3 ){return 3;} else{if( hstr[0]<='9' && hstr[0]>='0' ){return 1;}if( hstr[0]<='z' && hstr[0]>='a' ){return 2;}}return 1;}void GenList::strncpy1 (char* &hstr,char* &s,int comma ){ int n=strlen(s);hstr=new char[n];for( int t=0,i=1;iutype==0){ while( ls!=NULL ){switch( ls->utype ){case 0:s[i]='(';i++;cout<<"( "; break; case1:s[i]='0'+(ls->value.intinfo-0);i++;cout<value.intinfo;if(ls->t link!=NULL){s[i]=',';i++;cout<<" , ";} break;case2:s[i]=ls->value.charinfo;i++;cout<value.charinfo;if(ls->tlink!= NULL){s[i]=',';i++;cout<<" , ";} break;case3:show( ls->value.hlink );if(ls->tlink!=NULL){s[i]=',';i++;cout<<" , ";}。