数据结构算法C语言实现（十九）--- 5.5&5.6&5.7广义表

一.简述

传说Lisp的基本数据结构就是广义表，广义表也是具有典型递归属性的数据结构，此外，由于建表要处理字符串，用C语言处理起来也是一脸懵逼…..最后自己还想写一个将广义表还原成字符串的函数，一是使其可视化，而是验证算法5.6。花了不少功夫才写出来（强烈建议自己动手写一写），最后是借助树形结构的角度才找到一个不错的解决办法。按照《数据结构编程实验》的分类，数据结构无非线性结构、树状结构、图结构，可以说树是特殊的图（图的最小生成树），线性表示特殊的树。。。。。扯远了！

二.头文件

补充版字符串处理头文件

  1 //4_2_part1.h
  2 /**
  3 author:zhaoyu
  4 */
  5 //2016-6-10
  6 //----串的定长顺序存储表示----
  7 #ifndef _4_2_PART1_H_
  8 #define _4_2_PART1_H_
  9 #include "head.h"
 10 #define MAXSTRLEN 255//用户可以在255以内定义最大串长
 11 //这语法还不是很熟悉
 12 typedef unsigned char SString[MAXSTRLEN+1];//0 号单元存放串的长度
 13 int StrLength(SString T)
 14 {
 15     for (int i = 1; i <= MAXSTRLEN; ++i)
 16     {
 17         if ('\0' == T[i])
 18         {
 19             return i-1;
 20         }
 21     }
 22     return MAXSTRLEN;
 23 }
 24
 25 /**
 26 algorithm 4.2
 27 */
 28 Status Concat(SString &T, SString S1, SString S2)
 29 {
 30     //用 T 返回由 S1 和 S2 连接而成的新串。
 31     //若未截断，则返回 TRUE，否则返回 FALSE
 32     Status uncut;
 33     if (S1[0] + S2[0] < MAXSTRLEN)
 34     {//未截断
 35         int i = 1;
 36         for (i = 1; i <= S1[0]; ++i)
 37         {
 38             T[i] = S1[i];
 39         }
 40         for (i = 1; i <= S2[0]; ++i)
 41         {
 42             T[S1[0]+i] = S2[i];
 43         }
 44         T[0] = S1[0] + S2[0];
 45         uncut = TRUE;
 46     }
 47     else if (S1[0] < MAXSTRLEN)
 48     {
 49         int i = 1;
 50         for (i = 1; i <= S1[0]; i++)
 51         {
 52             T[i] = S1[i];
 53         }
 54         for (i = S1[0]+1; i <= MAXSTRLEN; i++)
 55         {
 56             T[i] = S2[i-S1[0]];
 57         }
 58         T[0] = MAXSTRLEN;
 59         uncut = FALSE;
 60     }
 61     else
 62     {
 63         for (int i = 1; i <= MAXSTRLEN; i++)
 64         {
 65             T[i] = S1[i];
 66         }
 67         T[0] = S1[0] = MAXSTRLEN;
 68         uncut = FALSE;
 69     }
 70     return uncut;
 71 }
 72 /**
 73 algorithm 4.3
 74 */
 75 Status SubString(SString &Sub, SString S, int pos, int len)
 76 {
 77     //用 Sub 返回串 S 的第 pos 个字符起长度为 len 的字串
 78     //其中， 1<= pos <<= SreLength(S) 且 0 <= len <= StrLength(S)-pos+1
 79     if (pos < 1 || pos > S[0] || len < 0 || len > S[0]-pos+1)
 80     {
 81         return ERROR;
 82     }
 83     for (int i = 1; i <= len; i++)
 84     {
 85         Sub[i] = S[i+pos-1];
 86     }
 87     Sub[len+1] = '\0';
 88     Sub[0] = len;
 89     return OK;
 90 }
 91 /**
 92 add for chapter 5 / page 116.117
 93 */
 94 Status StrCompare(SString S, SString T)
 95 {
 96     for (int i = 1; i <= S[0] && i <=T[0]; i++)
 97     {
 98         if (S[i]-T[i] > 0){
 99             return 1;
100         }
101         if (S[i]-T[i] < 0)
102         {
103             return -1;
104         }
105     }
106     if (S[0] == T[0])
107     {
108         return 0;
109     }
110     return S[0]>T[0]?1:-1;
111 }
112 Status StrEmpty(SString S)
113 {
114     if (0 == StrLength(S))
115     {
116         return TRUE;
117     }
118     else
119     {
120         return FALSE;
121     }
122 }
123 Status StrCopy(SString &T, SString S)
124 {//健壮性并不够
125     for (int i = 0; i <= S[0]+1; i++)
126     {
127         T[i] = S[i];
128     }
129     return OK;
130 }
131 Status ClearString(SString S)
132 {
133     S[0] = 0;
134     S[1] = '\0';
135     return OK;
136 }
137 void PrintSString(SString T)
138 {
139     //if(T[])
140     for (int i = 1; i <= T[0]; ++i)
141     {
142         printf("%c", *(T+i));
143     }
144     printf("\n");
145 }
146 #endif

4_2_part1.h

  1 //5_5.h
  2 /**
  3 author:zhaoyu
  4 date；2016-6-16
  5 */
  6 //----广义表的头尾链表存储表示----
  7 #include "4_2_part1.h"
  8 #define AtomType char
  9 typedef enum {ATOM, LIST} ElemTag;//ATOM==0：原子，LIST==1子表
 10 typedef struct GLNode
 11 {
 12     ElemTag tag;//公共部分，用于区分原子结点和表节点
 13     union{//原子结点和表节点的公共部分
 14         AtomType atom;//atom 是原子结点的值域，AtomType由用户定义
 15         struct {struct GLNode *hp, *tp;}ptr;//ptr 是表结点
 16         //的指针域，ptr.hp 和 ptr.tp 分别指向表头和表尾
 17     };
 18 }*GList;//广义表类型
 19 /**
 20 algorithm 5.5
 21 */
 22 int GListDepth(GList L)
 23 {//采用头尾链表存储结构，求广义表 L 深度
 24     if (!L)
 25     {
 26         return 1;//空表深度为 1
 27     }
 28     if (L->tag == ATOM)
 29     {
 30         return 0;//原子深度为 0
 31     }
 32     int MAX = 0;
 33     for (GList pp = L; pp; pp = pp->ptr.tp)
 34     {
 35         int t = GListDepth(pp->ptr.hp);//求以 ptr.hp 为头指针的子表深度
 36         MAX = MAX>t?MAX:t;
 37     }
 38     return MAX+1;
 39 }
 40 /**
 41 algorithm 5.8
 42 */
 43 Status sever(SString &str, SString &hstr)
 44 {//将非空串 str 分割成两部分：hsub为第一个','之前的字串，str 为之后的子串
 45     int n = StrLength(str);
 46     int i = 0, k = 0;//k 记尚未配对的左括号的个数
 47     char ch;
 48     SString CH;
 49     do{
 50         ++i;
 51         SubString(CH, str, i, 1);
 52         ch = CH[1];
 53         if ('(' == ch)
 54         {
 55             ++k;
 56         }
 57         else if (')' == ch){
 58             --k;
 59         }
 60     }while (i < n && (',' != ch || 0 != k));
 61     if (i < n)
 62     {
 63         SubString(hstr, str, 1, i-1);
 64         SubString(str, str, i+1, n-i);
 65     }
 66     else
 67     {
 68         StrCopy(hstr, str);
 69         ClearString(str);
 70     }
 71 }
 72
 73 /**
 74 algorithm 5.7
 75 */
 76 Status CreateGList(GList &L, SString S)
 77 {//采用头尾链表存储结构，由广义表的书写形式串 S 创建广义表 L,设emp="()"
 78     GList q = NULL, p = NULL;
 79     SString emp = { 2, '(', ')', '\0'};
 80     SString sub, hsub;
 81     if ( 0 == StrCompare(S, emp))
 82     {//创建空表
 83         L = NULL;
 84     }
 85     else
 86     {
 87         if (!(L = (GList)malloc(sizeof(GLNode))))
 88         {
 89             exit(OVERFLOW);//建表结点
 90         }
 91         if (1 == StrLength(S))
 92         {//创建单原子广义表
 93             L->tag = ATOM;
 94             L->atom = S[1];
 95         }
 96         else
 97         {
 98             L->tag = LIST;
 99             p = L;
100             SubString(sub, S, 2, StrLength(S)-2);
101             do{//重复建 n 个子表
102                 sever(sub, hsub);//从 sub 中分离出表头串 hsub
103                 CreateGList(p->ptr.hp, hsub);
104                 q = p;
105                 if (!StrEmpty(sub))
106                 {//表尾不空
107                     if (!(p = (GList)malloc(sizeof(GLNode))))
108                     {
109                         exit(OVERFLOW);
110                     }
111                     p->tag = LIST;
112                     q->ptr.tp = p;
113                 }//if
114             }while (!StrEmpty(sub));
115             q->ptr.tp = NULL;
116         }//else
117     }
118 }
119 /**
120 algorithm 5.6
121 */
122 Status CopyGList(GList &T, GList L)
123 {//采用头尾链表存储结构，由广义表 L 复制得到广义表 T
124     if (!L)
125     {
126         T = NULL;
127     }
128     else
129     {
130         if (!(T = (GList)malloc(sizeof(GLNode))))
131         {
132             exit(OVERFLOW);
133         }
134         T->tag = L->tag;
135         if (ATOM == L->tag)
136         {
137             T->atom = L->atom;
138         }
139         else
140         {
141             CopyGList(T->ptr.hp, L->ptr.hp);
142             CopyGList(T->ptr.tp, L->ptr.tp);
143         }
144     }
145     return OK;
146 }
147
148 /**
149 my code
150 */
151 int cnt = 0;
152 void PrintGList(GList L)
153 {
154     if (NULL == L)
155     {
156         printf("()");
157     }
158     else
159     {
160         if (ATOM == L->tag)
161         {
162             printf("%c", L->atom);
163         }
164         else
165         {
166             if (NULL == L->ptr.hp)
167             {
168                 printf("(");
169             }
170             if (NULL != L->ptr.hp && LIST == L->ptr.hp->tag)
171             {
172                 printf("(");
173             }
174             PrintGList(L->ptr.hp);
175             if (NULL != L->ptr.tp && LIST == L->ptr.tp->tag)
176             {
177                 printf(",");
178             }
179             if (NULL == L->ptr.tp)
180             {
181                 printf(")");
182             }
183             else
184             {
185                 PrintGList(L->ptr.tp);
186             }
187
188
189         }
190     }
191 }

5_5.h

三.CPP文件

 1 #include "5_5.h"
 2 int main(int argc, char const *argv[])
 3 {
 4 //    freopen("out.txt", "w", stdout);
 5     //test function sever
 6
 7     SString s, t;
 8     scanf("%s", s+1);
 9     s[0] = StrLength(s);
10     sever(s, t);
11     printf("t:%s\n", t+1);
12     printf("s:%s\n", s+1);
13
14     GList L = NULL, T = NULL;
15     SString S;
16     scanf("%s", S+1);
17     S[0] = StrLength(S);
18     printf("len: %d\n", S[0]);
19     CreateGList(L, S);
20     printf("\nL--Depth\t%d\n", GListDepth(L));
21     CopyGList(T, L);
22     printf("\nT--Depth\t%d\n", GListDepth(T));
23     printf("T:\t");
24     PrintGList(T);
25     printf("\n");
26     return 0;
27 }

5_5.cpp

四.测试

测试用例是书上的一个例子，其结构图及对应二叉树如下