数据结构_广义表的运算.doc

《数据结构》课程设计 题目：广义表的运算 广义表是线性表的推广。线性表的元素仅限于原子项。广义表的元素或者是原子，或者是一个广义表，有其自身结构。广义表通常用圆括号括起来，用逗号分隔其中的元素。为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。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 ）…αn ）…αn） 5.由广义表的字符串形式到广义表转换函数：由于S中的每个子串(i定义 L 的一个子表，从而产生 n 个子问题，即分别由这 n个子串 (递归)建立 n 个子表，再组合成一个广义表。其中：可以直接求解的两种简单情况为：以串‘（）’建立的广义表是空表，由单字符建立的广义表只是一个原子结点。若是其他情况，因为第一个子表的标志域为一，代表指向广义表的头指针。指示表头的指针域指向第一个子表的头指针。相邻子表之间用表结点相连接。综上：若 S = (( )( 则 L = NIL；否则，构造第一个表结点 *L，并从串S中分解出第一个子串(1，对应创建第一个子广义表 L-ptr.hp;若剩余串非空，则构造第二个表结点L-ptr.tp，并从串S中分解出第二个字串(2，对应创建第二个子广义表……以此类推直至剩余串为空串止。 7.求深度：广义表深度定义为广义表中括弧的重数，是广义表的一种量度。例如，多元多项式广义表的深度为多项式中变元的个数。设非空广义表为LS=（α1，α2，…αn ）…）…） 由此可见，求广义表的深度递归算法有两个终结态：空表和原子，且只要求得αi（i=1，2，3，…） 广义表 LS=（α1，α2，…αn ） 基本项：ＤＥＰＴＨ（ＬＳ）＝１　　当ＬＳ为空表时 　　　　　　ＤＥＰＴＨ（ＬＳ）＝０　　当ＬＳ为原子时 归纳项：ＤＥＰＴＨ（ＬＳ）＝１＋Ｍａｘ｛ＤＥＰＴＨ（αｉ）｝　ｎ＞＝１ 由此定义容易写出求深度的递归函数。假设Ｌ是ＧＬｉｓｔ型的变量则Ｌ＝ＮＵＬＬ表明广义表为空表，Ｌ－＞ｔａｇ＝０表明是原子。反之，Ｌ指向表结点，该结点中的ｈｐ指针指向表头，即为Ｌ的第一个子表，而结点中的ｔｐ指针所指表尾结点中的ｈｐ指针指向Ｌ的第二个子表。在第一层中由ｔｐ相连的所有尾结点中的ｈｐ指针均指向Ｌ的子表。由此可得广义表深度的递归算法。 2程序实现 上机实现算法时由于具体问题牵涉到各种方面，难以综合实现，可以分为几个小的模块将程序先进行初步整合 具体程序： #includeiostream.h #includestring.h #includecstdlib class GenListNode{ friend class GenList; public: int utype; //0,1,2,3 union{ int intinfo; char charinfo; GenListNode* hlink; }value; GenListNode* tlink; GenListNode(){} }