代码面试之广义表

广义表的基本概念

广义表（Lists，又称列表）是线性表的推广。线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。

广义表是n (n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。

抽象数据类型广义表的定义如下：

ADT Glist

{

数据对象： D={ei | i=1,2,..,n;n>=0 ;  eiÎAtomSet 或ei ÎGlist,

AtomSet为某个数据对象}

数据关系：R1={< ei-1, ei > | ei-1 , ei ÎD,2<=i<=n}

基本操作：

InitGList( &L);

操作结果：创建空的广义表L。

CreateGList(&L,S);

初始条件：S是广义表的书写形式串。

操作结果：由S创建广义表L。

DestroyGList(&L);

初始条件：广义表L存在。

操作结果：销毁广义表L。

CopyGList( &T,L);

初始条件：广义表L存在。

操作结果：由广义表L复制得到广义表T。

GListLength(L);

初始条件：广义表L存在。

操作结果：求广义表L的长度，即元素个数。

GListDepth(L);

初始条件：广义表L存在。

操作结果：求广义表L的深度。

GListEmpty (L);

初始条件：广义表L存在。

操作结果：判定广义表L是否为空。

GetHead(L);

初始条件：广义表L存在。

操作结果：取广义表L的头。

GetTail( &T,L);

初始条件：广义表L存在。

操作结果：取广义表L的尾。

InsertFirst_GL(&L,e);

初始条件：广义表L存在。

操作结果：插入元素e作为广义表L的第一元素。

DeleteFirst_GL(&L,&e);

初始条件：广义表L存在。

操作结果：删除广义表L的第一元素，并用e返回其值。

Traverse_GL (L,visit());

初始条件：广义表L存在。

操作结果：遍历广义表L，用函数visit处理每个元素。

｝

通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。

显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：

（1）A=（）——A是一个空表，其长度为零。

（2）B=（e）——表B只有一个原子e，B的长度为1。

（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别

为原子a和子表(b,c,d)。

（4）D=（A，B，C）——表D的长度为3，三个元素

都是广义表。显然，将子表的值代入后，

则有D=(( ),(e),(a,(b,c,d)))。

（5）E=（E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).

从上述定义和例子可推出广义表的三个重要结论：

（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108

（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。

（3）广义表的递归性。

综上所述，广义表不仅是线性表的推广，也是树的推广。

由表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是列表，而其表尾必定是列表。

gethead(B)=e         gettail(B)=(  )

gethead(D)=A        gettail(D)=(B,C)

由于（B，C）为非空广义表，则可继续分解得到：

gethead(B,C)=B         gettail(B,C)=(C)

注意广义表（ ）和( ( ) )不同。前者是长度为0的空表，

对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（ ）。

广义表的存储结构

由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常 采用链式存储结构 ，每个数据元素可用一个结点表示。

由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。

若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。

1、仅有表结点由三个域组成：

标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。

头尾链表存储表示

示例如图：

这种存储结构的三个特点：

1。除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头，tp域指向列表表尾（除非表尾为空，则指针为空，否则必为表结点）；

2。容易分清列表中原子和子表所在层次。如在列表D中，原子e和a在同一层次上，而b、c和d在同一层次且比e和a低一层，B和C是同一层的子表；

3。最高层的表结点个数即为列表的长度。

2、表结点和原子结点均由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域。

其类型定义如下：

扩展线性链表存储表示

示例如图：

广义表基本操作的实现

我们以头尾表示法存储广义表，讨论广义表的有关操作的实现。由于广义表的定义是递归的，因此相应的算法一般也都是递归的。

⒈广义表的取头、取尾

GList Head(GList ls) { if ls->tag = = 1 then p = ls->hp; return p; } 算法5.6  GList Tail(GList ls) { if ls->tag = = 1 then p = ls->tp; return p; } 算法5.7

⒉建立广义表的存储结构

int Create(GList *ls, char * S) { Glist p; char *sub; if StrEmpty(S) *ls = NULL; else { if (!(*ls = (GList)malloc(sizeof(GLNode)))) return 0; if (StrLength(S) = = 1) { (*ls)->tag = 0; (*ls)->data = S; } else { (*ls)->tag = 1; p = *ls; hsub =SubStr(S,2,StrLength(S)-2); do { sever(sub,hsub); Create(&(p->ptr.hp), sub); q = p; if (!StrEmpty(sub)){ if (!(p = (GList)malloc(sizeof(GLNode)))) return 0;; p->tag = 1; q->ptr.tp = p; } }while (!StrEmpty(sub)); q->ptr.tp = NULL; } } return 1; } 算法5.8  int sever(char *str, char *hstr) { int n = StrLength(str); i= 1; k = 0; for (i = 1, k = 0; i <= n || k != 0; ++i) { ch=SubStr(str,i,1); if (ch = = '(') ++k; else if (ch = = ')') --k; } if (i <= n) { hstr =SubStr(str,1,i-2); str= SubStr(str,i,n-i+1); } else { StrCopy(hstr,str); ClearStr(str); } }

⒊以表头、表尾建立广义表

int Merge(GList ls1,GList ls2, Glist *ls) { if (!(*ls = (GList)malloc(sizeof(GLNode)))) return 0; *ls->tag = 1; *ls->hp = ls1; *ls->tp = ls2; return 1; } 算法5.10

4.求广义表的深度

int Depth(GList ls) { if (!ls) return 1; /*空表深度为1*/ if (ls->tag = = 0) return 0; /*单元素深度为0*/ for (max = 0,p = ls; p; p = p->ptr.tp) { dep = Depth(p->ptr.hp); /*求以p->ptr.hp 尾头指针的子表深度*/ if (dep > max) max = dep; } return max+1; /*非空表的深度是各元素的深度的最大值加1*/ } 算法5.11

⒌复制广义表

int CopyGList(GList ls1, GList *ls2) { if (!ls1) *ls2 = NULL; /*复制空表*/ else { if (!(*ls2 = (Glist)malloc(sizeof(Glnode)))) return 0; /*建表结点*/ (*ls2)->tag = ls1->tag; if (ls1->tag = = 0) (*ls2)->data = ls1->data; /*复制单元素*/ else { CopyGList(&((*ls2)->ptr.hp), ls1->ptr.hp); /*复制广义表ls1->ptr.hp 的一个副本*/ CopyGList(&((*ls2)->ptr.tp) , ls1->ptr.tp); /*复制广义表ls1->ptr.tp 的一个副本*/ } } return 1; }

广义表的二叉树实现的形式

输入二叉树的广义表形式，将其转变为二叉树形式，至于怎样输入广义表需要程序规定。

定义包含头文件文件t11.h中

#include"stdio.h" #include"string.h" #include"ctype.h" #include"malloc.h" #include"stdlib.h"  //atoi(),exit(); #include"io.h"      //eof() #include"math.h"  #define  TRUE  1 #define  FALSE  0 #define  OK   1 #define  ERROR 0 typedef int Status; typedef int Boolean; 定义数据结构头文件gercs.h中 #define INIT_STACK 100 #define INIT_STACK_ADD  20 typedef struct node            //  二叉树的数据结构定义 {     char data;  struct node *lchild;  struct node *rchild; }*Bitree,pBitree; typedef struct  {     char *bottom;  char *top;  int stacksize; }Sqstack; struct Binode {  Bitree lp; }; struct Sqstack1 {  Binode *bottom;  Binode *top;  int stacksize; }; typedef struct {      Binode *front;   Binode *rear;   int queuesize; }*linkqueue,queue;    Sqstack W; 定义包含实现函数功能模块gercs.cpp中 void inittree(Bitree &T) {  T=NULL; } void initqueue(queue &Q) {  Q.front=(Binode*)malloc(INIT_STACK*sizeof(Binode));  Q.rear=Q.front;  Q.queuesize=INIT_STACK; } void initstack(Sqstack &L) {  L.bottom=(char*)malloc(INIT_STACK*sizeof(char));  if(!L.bottom)  {   printf("内存分配失败！！");   exit(0);  }  L.top=L.bottom;  L.stacksize=INIT_STACK;   } void initstack1(Sqstack1 &L) {  L.bottom=(Binode*)malloc(INIT_STACK*sizeof(Binode));  if(!L.bottom)  {   printf("内存分配失败！！");   exit(0);  }  L.top=L.bottom;  L.stacksize=INIT_STACK;   } void enqueue(queue &Q,Bitree T) {  if(Q.rear-Q.front > Q.queuesize)  {   Q.front=(Binode*)realloc(Q.front,(Q.queuesize,INIT_STACK_ADD)*sizeof(Binode));   Q.rear=Q.front+Q.queuesize;   Q.queuesize+=INIT_STACK_ADD;  }  (Q.rear++)->lp=T; } void push(Sqstack &L,char ch) {     if(L.top-L.bottom > L.stacksize)  {   L.bottom=(char*)realloc(L.bottom,(L.stacksize+INIT_STACK_ADD)*sizeof(char));   L.top=L.bottom+L.stacksize;   L.stacksize+=INIT_STACK_ADD;  }  *(L.top++)=ch; } void push1(Sqstack1 &L,Bitree ch) {     if(L.top-L.bottom > L.stacksize)  {   L.bottom=(Binode*)realloc(L.bottom,(L.stacksize+INIT_STACK_ADD)*sizeof(Binode));   L.top=L.bottom+L.stacksize;   L.stacksize+=INIT_STACK_ADD;  }  (L.top++)->lp=ch; } Status pop(Sqstack &L,char &e) {  if(L.bottom == L.top)   return ERROR;  else  {   e=*(--L.top);   return OK;  } } Status pop1(Sqstack1 &L,Bitree &e) {  if(L.bottom == L.top)   return ERROR;  else  {   e=(--L.top)->lp;   return OK;  } } Status emptystack(Sqstack L) {  if(L.bottom == L.top)   return OK;  else   return ERROR; } Status emptystack1(Sqstack1 L) {  if(L.bottom == L.top)   return OK;  else   return ERROR; } Sqstack shuru(Sqstack &S) {  Sqstack R;  initstack(R);  char ch,ch1;  printf("输入广义表二叉树形式:");  ch=getchar();  while(10 != ch)  {   if(ch >= 'a' && ch <= 'z')//|| ch >= 'A' && ch <='Z')   {    push(S,ch);    ch1=getchar();    if(')' == ch1)    {     push(S,10);     push(S,10);    }    ch=ch1;   }   else   {             ch1=getchar();    if(',' == ch && ',' == ch1)     push(S,10);    ch=ch1;   }  }    while(!emptystack(S))  {   pop(S,ch);   //printf("%-3c",ch);   push(R,ch);  }  return R; } void Createtree(Bitree &T)           // 先序创建二叉树 {  // printf("进入了！");  char ch;  pop(W,ch);  // printf("ch=%c  ",ch);  if(ch == 10)                           //  如果是回车键置为空   T=NULL;  else  {   T=(Bitree)malloc(sizeof(pBitree));   if(!T)   {    printf("分配失败！");    exit(0);   }   T->data=ch;   Createtree(T->lchild);   Createtree(T->rchild);   }  // getchar(); }                               // 创建二叉树结束 void xianxu(Bitree T,Sqstack1 &S)   //  先序非递归遍历，采用的是保存右孩子的地址通过栈实现 {  printf("先序非递归遍历输出:/n");     if(T)  {   if(T->rchild)    push1(S,T->rchild);    //  专门压入右孩子指针地址   printf("%-3c",T->data);   T=T->lchild;            //  更新指针  }else   exit(0);  while(T || !emptystack1(S))     //  循环终止条件  {   if(T!= NULL)             //  始终作为一个点存在加以判断，一种情况是一直指向左孩子，另一种就是出栈弹出的右孩子   {    printf("%-3c",T->data);    //  输出节点的数据域    if(T->rchild != NULL)    // 该节点存在右孩子，将右孩子入栈     push1(S,T->rchild);    T=T->lchild;       //  更新指针，始终往左走   }   else    pop1(S,T);    } } void cengci(Bitree T,queue &Q) {     if(!T)  {   printf("树为空！");   exit(0);  }  Binode *P,*S;  S=P=Q.front;  enqueue(Q,T);  while(P != Q.rear)  {   if(P->lp->lchild)    enqueue(Q,P->lp->lchild);   if(P->lp->rchild)    enqueue(Q,P->lp->rchild);   P++;  }  printf("层次遍历为:/n");  while(S < Q.rear)  {   printf("%-3c",S->lp->data);   S++;  } }   最后就是定义主函数函数调用了，包含于头文件main_gercs.cpp中 #include"t11.h" #include"gercs.h" #include"gercs.cpp" void main() {  // char ch;  Bitree S;     queue U;  Sqstack1 Q;     initstack(W);  initstack1(Q);  inittree(S);  initqueue(U);  W=shuru(W);  /* while(!emptystack(W))  {  pop(W,ch);  printf("%-3c",ch);       }*/  Createtree(S);  xianxu(S,Q);  printf("/n");  cengci(S,U);     printf("/n");     }

编译运行之后：