代码面试之广义表-阿里云开发者社区

开发者社区> 人工智能> 正文

代码面试之广义表

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

广义表的基本概念

广义表(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. typedef enum {ATOM,LIST } ElemTag;  //ATOM==0:表示原子,LIST==1:表示子表  
  2. typedef struct GLNode {  
  3.     ElemTag  tag;  //公共部分,用以区分原子部分和表结点  
  4.     union {       //原子部分和表结点的联合部分  
  5.       AtomType  atom; //atom是原子结点的值域,AtomType由用户定义  
  6.       struct { struct GLNode *hp, *tp;} ptr;  
  7.              // ptr是表结点的指针域,ptr.hp 和ptr.tp分别指向表头和表尾  
  8.     };  
  9. } *Glist;  //广义表类型  


示例如图:

 

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

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

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

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

 

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

 

其类型定义如下:

扩展线性链表存储表示

  1. Typedef enum { ATOM,LIST} ElemTag;                                
  2.     //ATOM==0:表示原子,LIST==1:表示子表  
  3. Typedef struct GLNode {  
  4.     ElemTag    tag;  //公共部分,用以区分原子部分和表结点  
  5.     union {  //原子部分和表结点的联合部分  
  6.         AtomType    atom;  //原子结点的值域  
  7.         struct GLNode  *hp;  //表结点的表头指针  
  8.         };  
  9.         struct GLNode    *tp;    
  10.                 //相当于线性链表的next,指向下一个元素结点  
  11. } *Glist;  //广义表类型Glist 是一种扩展的线性链表  


示例如图:

 

 

广义表基本操作的实现

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

⒈广义表的取头、取尾

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");
 
 
}

  编译运行之后:

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章