数据结构第五周作业（广义表的深度、长度、存储结构）

1.

请写出下列广义表的深度和长度。

广义表的长度就是广义表中第一层的元素个数。原子数据和子表都算作一个元素。

广义表的深度就是广义表中最大的嵌套次数，是广义表中所含括号的重数。是所有子表的最大深度加1。

（1）长度为0，深度为1.
（2）长度为1，深度为1.
（3）长度为3，深度为1.
（4）长度为4，深度为4.
（5）长度为3，深度为4.

2.

试画出上述广义表的存储结构示意图。

3.

编写一个算法，计算如下形式广义表的长度：

【注意】为简化操作，输入只包括字母、数字和“(”、“)”、“ ,”和空格，且任意多的空格不影响广义表的长度。

#include <stdio.h>
#include <stdlib.h>

struct Lists
{ int Flag;
union 
  {char Data;
   struct Lists *List;
  } Info; 
  struct Lists *Link;
};

void Setuplists(struct Lists **H, char *s)
{   struct Lists *p, *x;        struct Lists *(S1[10]);   //指针栈
    int top1 = 0, i=0;      char c;
    (*H) = (struct Lists *)malloc(sizeof(struct Lists));
    (*H)->Flag = 1;  (*H)->Info.List = 0;  (*H)->Link = 0;
    p=(*H);
    while (s[i]!='\0')
    { c = s[i++]; 
    switch (c) { 
    case '(' : x = (struct Lists *)malloc(sizeof(struct Lists));
        x->Flag = 0;  x->Info.List = 0;  x->Link = 0;
        p->Flag = 1; p->Info.List = x;
        S1[++top1] = p;  p=x;  break; 
    case ',':   x = (struct Lists *)malloc(sizeof(struct Lists));
        x->Flag = 0;  x->Info.List = 0;  x->Link = 0;
        p->Link = x;  p = x;  break;
    case ' ':  break;
    case ')':  p->Link = 0;  p=S1[top1--]; break;
    default : p->Flag = 0; p->Info.Data = c; p->Link = 0;
    }  }    }

void Printlists(struct Lists *H)
{   struct Lists *p;        
       struct Lists *(S1[10]);
    int top1 = 0;
    p = H;
    while (p!=0 || top1!=0)
    {    while (p!=0)
         {  if (p->Flag==1)   // 子表，进入下一层 //
                     { S1[++top1] = p; p=p->Info.List; printf("("); }
           else { printf("%c",p->Info.Data); p=p->Link;   // 原子元素
                        if (p!=0) printf(","); }
          } 
             printf(")"); // 一个子表遍历结束 //
             p = S1[top1--];     p = p->Link;     // 返回上一层，转后继 //
             if (p!=0) printf(","); 
    }
}

int Depthlists(struct Lists *H)
{ int dep=0, Maxdep=0, top1 = 0;
   struct Lists *(S1[10]), *p;
   p = H;
   while (p!=0 || top1!=0)
   {   while (p!=0)
       {  if (p->Flag==1) 
              { S1[++top1] = p; p=p->Info.List; dep++; }
           else p=p->Link; 
       }
       if (dep > Maxdep) Maxdep = dep;     
       p = S1[top1--];  dep--;  p = p->Link;  
   }
    return(Maxdep);
}

int Lenthlists(struct Lists *H)  // 长度 //
{  int n=0;
    struct Lists *p;
    p = H->Info.List;
    while (p!=0) { n++;  p = p->Link;  }
    return(n);
}

int main(){
    struct Lists *H;
    char a[100];
    char *s = gets(a);

    Setuplists(&H, s);
    Printlists(H);
    printf("\nlength  = %d",Lenthlists(H));

    return 0;
}

#include <stdio.h>

int main(){
    char a[100];
    char *s = gets(a);
    int max = 0,n = 0;

    while(*s){
        if(*s=='('){
            n++;
        }else if(*s==')'){
            n--;
        }
        if(max < n) max = n;
        s++;
    }
    printf("length  = %d",max);

    return 0;
}