合肥学院
计算机科学与技术系
课程设计报告
2008 ～2009 学年第 二 学期
课程
        数据结构与算法
课程设计名称
广义表的运算
学生姓名
汪阳
学号
0704032047
专业班级
07网络工程（2）班
指导教师
李红
2009 年 5 月
题目：
广义表的运算。本设计要求实现广义表的建立、查、输出、取表尾、以及求深度、求逆表等。
一、问题分析与任务定义：
此程序需要完成以下几个任务：首先要将输入的用数组存储的广义表转化成以广义表的存储结构存储的广义表，这个过程也就是生成广义表；查广义表，查广义表要返回一个值mark，当mark=1时，程序查到待查的元素，当mark=0时，程序没有到待查元素；输出广义表，遍历广义表，输出广义表的遍历结果；取表尾，将广义表从第二个元素开始复制到另一个广义表中；求广义表的深度，遍历每一层广义表，将广义表内每层广义表深度最大的广义表相加为同一层所求过的子表中深度的最大值；求逆表，将广义表逆向输出。
实现本程序需要解决以下问题：
1、 如何根据广义表的特点建立广义表。
2、 用什么方法才能查到广义表中每一个元素，如何标志是否到待查元素。
3、 建立广义表，如何根据广义表的存储结构的特点建立广义表。
4、 求广义表的深度的依据是什么。
5、 运用什么方法才能将广义表逆序。
二、概要设计和数据结构选择：
1、广义表的存储结构：
由于广义表中的元素本身又可以具有结构，是一种带有层次的非线性结构，因此难以用顺序存储的结构表示。通常采用链式存储结构，每个元素可用一个结点表示，结点结构如图1、图2所示：
tag=0
atom
*tp
       
                          图1原子结点的存储结构
tag=1
*hp
*tp
                          图2结点的存储结构
每个结点由三个域构成。其中tag是一个标志位，用来区分当前结点是原子结点还是子表。当tag为1时，该结点是子表，第二个域为hp，用以存放子表的地址；当tag为0时，该结点是原子结点，第二个域为atom，用以存放元素值。tp域是用来存放与本元素同一层的下一个元素对应结点的地址，当该元素是所在层的最后一个元素时，tp的值为NULL。广义表及结点类型描述如下：
typedef char ElemType;
typedef struct GLode//广义表结构体的定义
考研步骤流程图
{    
        int tag;                    /*结点类型标识*/
        union
        {
            ElemType atom;            /*原子值*/
            struct GLode *hp;    /*指向子表的指针*/
        } val;
        struct GLode *tp;            /*指向下一个元素*/
} GList;
例如：建立广义表：（a，b（c，d），e） ，如图3
1
^
               
0
a
0
b
1
^
                         
         
0
c
0
d
1
^
0
e
1
^
^
                    图3 广义表的存储图示
2、求广义表的逆表需要用堆栈存储广义表的元素，栈的数据类型如下：
typedef char ElemType;
typedef struct
{
      ElemType data[maxlen] ;
      int top;
}SeqStack;
3、程序流程图如图4。
            创建一个新结点；         
                          图4 程序流程图
三、详细设计与编码
1、建立广义表CreateGL(char *&s)。在生成广义表之前，用一个数组存储广义表，并用指针s指向数组，通过数组中的元素生成广义表。基本思想是：在广义表表达式中，遇到左括号”(”时递归构造子表，否则构造原子结点；遇到逗号时递归构造后续广义表，直到字符串数组结束，以"\0"作为结束标志。实现过程如下：
GList *CreateGL(char *&s)       
{   
        读入广义表的一个字符给ch；
        if (ch!=空格')                   
        {
      if (ch=='(') 
{   
            递归构造子表；
}
    else if (ch==')')
          遇到')'字符,子表为空
        else
        {   
            构造原子结点；
        }
    }
    else
      串结束,子表为空
读入广义表的一个字符给ch；
        if (ch==',')                 
            递归构造后续子表；
        else                         
              处理表的最后一个元素
        返回广义表指针
}
2、遍历广义表DispGL(GList *g)。输出广义表采用的算法思想是：若遇到tag=1的结点，这是一个子表的开始，先打印输出一个左括号”(”。如果该子表为空，则输出一个空格符；否则递归调用输出该子表。子表打印输出完后，再打印一个右括号”)”。若遇到tag=0的结点，则
直接输出其数据域的值。若还有后续元素，则递归调用打印后续每个元素，直到遇到tp=NULL。其实现过程如下：
void DispGL(GList *g)       
{
    if (g!=NULL)                   
    {
        if (g->tag==1)             
        {
            输出左括号'('；
            if (g->val.hp==NULL)     
                输出一个空格；
            else
                    递归调用子表；
        }
        else
            输出数据域；
        if (g->tag==1)
            打印有括号“）”；
        if (g->tp!=NULL)
            输出逗号“，”，递归调用输出下一个结点。
    }
}
3、广义表的查：FindGListX()
在给定的广义表种查数据域为x的结点，采用的算法思想是：若遇到tag=0的原子结点，如果是要查的结点，则查成功1；否则，若还有后续元素，则递归调用本过程在孩子表中查，若还有后续元素，则递归调用本过程查后续每个元素，直到遇到hp域为NULL的元素。
设置mark标志查结果；mark=1；表示查成功，否则查失败。
本函数实现过程如下：
FindGListX(GList *g,char x,int &mark)
{
    if(g!=NULL){
        if (g->tag == 0 && g->val.atom ==x)