7. 广义表反序(中文班，10分)
逆置广义表的递归模型如下：
F(LS) = null 若 LS 为空
F(LS) = LS 若 LS 为原子，且 tail(LS) 为空
F(LS) = append( F(tail(LS)), head(LS) ) 若 LS->tag=0 ，且 LS->tp!=null
F(LS) = append( F(tail(LS), F(head(LS)) ) 若 LS->tag=1
其中 append(a,b) 的功能是将广义表 a 和 b 作为元素的广义表连接起来。
请根据以上定义和给定的程序框架，编写函数：GLNode * reverse( GLNode * )。
特别说明：以下的预设代码并不是一个好的程序，大家先凑合吧。
预设代码前置代码
view plainprint?
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ #include "stdio.h" #include "string.h" #include "stdlib.h" typedef enum { ATOM, LIST } ListTag; typedef struct node { ListTag tag; union { char data; struct node *hp; } ptr; struct node *tp; } GLNode; GLNode * reverse( GLNode * ); int count; void Substring( char *sub, char *s, int pos, int len ) { s = s + pos; while ( len > 0 ) { *sub = *s; sub++; s++; len--; } *sub = ' '; } void sever( char *str, char *hstr ) { int n, i, k; char ch[50]; n = strlen(str); i = k = 0; do { Substring( ch, str, i++, 1 ); if ( *ch=='(' ) k ++; else if ( *ch==')' ) k --; } while ( i<n && ( *ch!=',' || k!=0 ) ); if ( i<n ) { Substring( hstr, str, 0, i-1 ); Substring( str, str, i, n-i ); } else { strcpy( hstr, str ); str[0] = ' '; } } /* sever */ int PrintGList( GLNode * T ) { GLNode *p=T, *q; if ( p==NULL ) printf( ")" ); else { if ( p->tag==ATOM ) { if ( count > 0 ) printf( "," ); printf( "%c", p->ptr.data ); count ++; } else { q = p->ptr.hp; if ( q == NULL ) { if ( count > 0 ) printf(","); printf("("); } else if ( q->tag == LIST ) { if ( count > 0 ) printf( "," ); printf( "(" ); count = 0; } PrintGList( q ); PrintGList( p->tp ); } } return 1; } void print( GLNode * L ) { if ( L == NULL ) printf( "()" ); else { if ( L->tag == LIST ) printf( "(" ); if ( L->ptr.hp != NULL ) PrintGList( L ); else { printf( "()" ); if ( L->tp == NULL ) printf( ")" ); } } printf( "n" ); } int CreateGList( GLNode **L, char *s ) { GLNode *p, *q; char sub[100], hsub[100]; p = *L; if ( strcmp(s, "()" )==0 ) *L = NULL; /* 创建空表 */ else { *L = ( GLNode * ) malloc( sizeof( GLNode ) ); if ( strlen(s)==1 ) { (*L)->tag = ATOM; (*L)->ptr.data = s[0]; } else { (*L)->tag = LIST; p = *L; Substring( sub, s, 1, strlen(s)-2 ); do { sever( sub, hsub ); CreateGList( &p->ptr.hp, hsub ); q = p; if ( strlen(sub) > 0 ) { p = (GLNode *) malloc( sizeof(GLNode) ); p->tag = LIST; q->tp = p; } } while ( strlen(sub)>0 ); q->tp = NULL; } /* else */ } /* else */ return 1; } /********** 这是你要实现的函数。 ***********/ GLNode * reverse( GLNode *p ); /*******************/ int main( ) { char list[100]; GLNode *L, *G; int d; count = 0; scanf("%s", list); CreateGList( &L, list ); /* print( L ); */ G = reverse( L ); count = 0; print( G ); return 0; } /* PRESET CODE END - NEVER TOUCH CODE ABOVE */#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef enum
{
ATOM,
LIST
} ListTag;
typedef struct node
{
ListTag tag;
union {
char data;
struct node *hp;
} ptr;
struct node *tp;
} GLNode;
GLNode *reverse(GLNode *);
int count;
void Substring(char *sub, char *s, int pos, int len)
{
s = s + pos;
while (len > 0)
{
*sub = *s;
sub++;
s++;
len--;
}
*sub = ' ';
}
void sever(char *str, char *hstr)
{
int n, i, k;
char ch[50];
n = strlen(str);
i = k = 0;
do
{
Substring(ch, str, i++, 1);
if (*ch == '(')
k++;
else if (*ch == ')')
k--;
} while (i < n && (*ch != ',' || k != 0));
if (i < n)
{
Substring(hstr, str, 0, i - 1);
Substring(str, str, i, n - i);
}
else
{
strcpy(hstr, str);
str[0] = ' ';
}
}
int PrintGList(GLNode *p)
{
GLNode *FL = p, *q;
if (FL == NULL)
printf(")");
else
{
if (FL->tag == ATOM)
{
if (count > 0)
printf(",");
printf("%c", FL->ptr.data);
count++;
}
else
{
q = FL->ptr.hp;
if (q == NULL)
{
if (count > 0)
printf(",");
printf("(");
}
else if (q->tag == LIST)
{
if (count > 0)
printf(",");
printf("(");
count = 0;
}
PrintGList(q);
PrintGList(FL->tp);
}
}
return 1;
}
void print(GLNode *L)
{
if (L == NULL)
printf("()");
else
{
if (L->tag == LIST)
printf("(");
if (L->ptr.hp != NULL)
PrintGList(L);
else
{
printf("()");
if (L->tp == NULL)
printf(")");
}
}
printf("n");
}
int CreateGList(GLNode **L, char *s)
{
GLNode *p, *q;
char sub[100], hsub[100];
p = *L;
if (strcmp(s, "()") == 0)
*L = NULL;
else
{
*L = (GLNode *)malloc(sizeof(GLNode));
if (strlen(s) == 1)
{
(*L)->tag = ATOM;
(*L)->ptr.data = s[0];
}
else
{
(*L)->tag = LIST;
p = *L;
Substring(sub, s, 1, strlen(s) - 2);
do
{
sever(sub, hsub);
CreateGList(&p->ptr.hp, hsub);
q = p;
if (strlen(sub) > 0)
{
p = (GLNode *)malloc(sizeof(GLNode));
p->tag = LIST;
q->tp = p;
}
} while (strlen(sub) > 0);
q->tp = NULL;
}
}
return 1;
}
GLNode *reverse(GLNode *p)
{
GLNode *FL = p;
if (p != NULL && p->tag == LIST)
{
for (p->tp = reverse(p->tp); p->tp != NULL; p = p->tp)
;
p->tp = (GLNode *)malloc(sizeof(GLNode));
GLNode *q = p->tp;
q->tp = NULL;
q->tag = FL->tag;
q->ptr.hp = reverse(FL->ptr.hp);
p->tp = q;
FL = FL->tp;
}
else return FL;
return FL;
}
int main()
{
char list[100];
GLNode *L, *G;
int d;
count = 0;
scanf("%s", list);
CreateGList(&L, list);
G = reverse(L);
count = 0;
print(G);
return 0;
}
相关知识
7. 广义表反序(中文班，10分)
宠物的广义范畴？
朗诵比赛评分细则及标准有哪些？如何设计打分表；打分结果如何使用打分软件自动统计？
乌龟相关介绍，广义上是指龟鳖目的统称
7. 好处≠价格，证据=价格
中国的CLHLS数据库发表一区文章 | 广义估计方程模型+亚组分析+敏感性分析
宠环积分奖励表
(10分)[环境保护](鸟类、猎、犬等)宽物发出的
mysql创建表、加载数据到表中
纯种极品纯种比格幼犬出售 纯种健康的幼犬宝宝=============[朋友们10分诚意来买狗]
网址: 7. 广义表反序(中文班，10分) https://m.mcbbbk.com/newsview1100851.html
| 上一篇: 程序基本算法习题解析 动态规划 |
下一篇: 为什么要使用href=”java |
