理解广义表：
1535611398021.png
完整代码：
glist.h
#pragma once
// 进行一些基本的定义
# define ok 1
#define error 1
#define true 1
#define false 0
#define overflow -2
#define MAXSIZE 100
//------自定义类型----//
typedef int Status;
typedef char AtomType;
typedef enum {ATOM,LIST}ElemTag;//ATOM==0，LIST==1
typedef char* SString;
//-----------广义表的存储方式之一-------------//
typedef struct GLNode {//自定义广义表结点类型
ElemTag tag;
union {
AtomType atom;
struct {
struct GLNode *hp, *tp;//表头指针和表尾指针
}ptr;
};
} *GList;
建立广义表：
//以第二种存储方式进行
#include <stdlib.h>
#include <stdio.h>
#include "glist.h"
#include <string.h>
//-----------外部函数声明---------//
extern void PrtGlist(GList G);
extern void subPrtGlist(GList G);
extern int GlistD(GList L);
//---------基本操作函数声明----------//
int StrLength(SString S);
//获得字符串的长度
Status SubStr(SString &sub,SString S,int i,int StrL);
//从括号后的第i个字符开始，查阅长度为StrL
Status StrCopy(SString &Sub, SString S);
//将S前长度len的字符复制到Sub
//void ClearStr(SString S);
Status StrEmpty(SString S);
//判断表尾是否为空
//-------------复合函数声明----------//
//----------采用头尾链表存储结构，由广义表的书写方式形式串建立广义表L，设emp="()"
Status CreateGList(GList &L, SString S);
//-----------------基本操作函数定义-------------//
int StrLength(SString S) {
return strlen(S);
}
Status StrCopy(SString &Sub,SString S) {
strcpy(Sub, S);
return ok;
}
Status SubStr(SString &sub, SString S, int Start, int StrL) {//去括号
int j;
/* if (S[0] == '('&&S[1] == ')');sub[0] = '\0';//如果输入的为空表，对sub操作为空
else {*/
for (j = 1; j < Start; S++, j++);//将S增至Start位置
for (j = 0; j < StrL; j++) {
sub[j] = S[j];
}
sub[StrL] = '\0';
//}//加入终止符!!!
return ok;
}
Status StrEmpty(SString S) {
if (*S == '\0') return true;///又不小心写成了=
else return false;
}
//---------------复合函数---------//
//------------分割函数-----------//
Status sever(SString &str, SString &hstr) {
//将非空串str分割成两部分：hstr为第一个'，'之前的子串，str为之后的子串
int n,i,k;
char a = NULL;
n = StrLength(str); i = 0; k = 0;//k为为配对的左括号个数,n为字符串长度
do{ //判断头串的长度
if (str[i] == '(') ++k; //如果为发现一个（，k++
else if (str[i] == ')') --k;
++i;
} while (i < n &&(k != 0 || str[i] != ',')); //i小于n，k不为0或未遇到','
//理解上述语句：只要有一个不等于为真，都相等为假，即括号匹配完，并且遇到
//第一个逗号，循环结束
if (i < n) { //i小于串长度时，即存在小于Sub的子表
SubStr(hstr, str, 1, i); //表头
SubStr(str, str,i+2, n-i-1); //表尾
}
else { //即i=n，可以认为表尾为空表
StrCopy(hstr, str);
str[0] = '\0';
}
return ok;
}
/*Status CreateGList0(GList &L,SString S) {//母表去括号
int len;
len = strlen(S);
SubStr(S, S, 2, len - 2);
CreateGList(L, S);
return ok;
}
*/
Status CreateGList(GList &L, SString S) {
int LEN;
GList p, q;
LEN = StrLength(S);
char *sub;//建立一个子表结点
sub = (char *)malloc(LEN * sizeof(char));
char *hsub;//建立子表尾表结点
hsub = (char *)malloc(LEN * sizeof(char));
bool a = S[0]== '('&&S[1]==')';//判断输入的是否为空表
if (a) L = NULL; //如果为空串，建立空表,需要注意的是也有可能为空表
else {
if (!(L = (GList)malloc(sizeof(GLNode)))) exit(overflow);//建表结点
if (StrLength(S) == 1) {
L->tag = ATOM; L->atom = *S;
}
else {
L->tag = LIST; p = L; //p为母表地址
SubStr(sub, S, 2, StrLength(S) - 2); //去掉表括号
do { //当表尾不为空时
sever(sub, hsub); //将母表的分离成表头hsub和表尾sub
CreateGList(p->ptr.hp, hsub); //将剥离的表头串hsub新建表
q = p; //用q代替p作为表头
if (!StrEmpty(sub)) { //判断表尾是否为空，若不为空，为表尾新建结点
if (!(p = (GLNode *)malloc(sizeof(GLNode)))) exit(overflow);
p->tag = LIST; q->ptr.tp = p; //表尾标签，表尾指针指向表尾
}
else q->ptr.tp = NULL; //否则q指向空
} while (!StrEmpty(sub)); //表尾不为空，将表尾进入下一个循环
}
}
return ok;
}
//----------主函数--------//
int main() {
SString Glist;
int i=0;
Glist = (SString)malloc(50 * sizeof(char));
GList L;
for (; (Glist[i] =getchar()) !='\n'; i++);//使用fgets会把\n算进去，使得字符长度加一
Glist[i] = '\0';
CreateGList(L, Glist);
PrtGlist(L);
printf("%d",GlistD(L));
return ok;
}
/*
1.在这次练习中，适当使用do-while语句可以使思维更清晰
2.另见第59行的代码，不要混用==和=
3.善于在纸上使用流程图理解循环，可以提高思维效率
4.书中或查阅的代码有可能有错误，因此要学会判断
*/
其他操作：
#include <stdlib.h>
#include <stdio.h>
#include "glist.h"
#include <string.h>
//--------函数定义-------//
//-------求深度
int GlistD(GList L) {
int max,dep;
GList p;
//采用头尾链表存储结构，求广义表深度
if (!L) return 1; //空表深度为1
if (L->tag == ATOM) return 0; //原子深度为0
for (max = 0, p = L; p; p = p->ptr.tp) {//遍历母表元素
dep = GlistD(p->ptr.hp); //获得各子表深度，将最大深度返回
if (dep > max) max = dep;
}
return max + 1;
}
//--------------打印
void subPrtGlist(GList G)
{
if (!G) printf("");
else {
if (!G->ptr.hp) { printf("()"); }//如果头为空表
else{
if (!G->ptr.hp->tag) {//判断头是不是表，如果头为空表，无法获取tag标签
printf("%c", G->ptr.hp->atom);//头是原子
}
else { //头是表
//头是空表，判断头是不是空表
printf("("); //头不是空表
subPrtGlist(G->ptr.hp);
printf(")");
}
}
if (G->ptr.tp) {//尾不是空表
printf(",");
subPrtGlist(G->ptr.tp);
}
}
}
void PrtGlist(GList G) {//为母表添加括号
printf("(");
subPrtGlist(G);
printf(")\n");
}
输出结果：
image.png
网友评论