十六、广义表的建立与基本操作

文章目录

• 十六、广义表的建立与基本操作
• • 题目描述
  • 解题思路
  • 上机代码
  • 补充说明

题目描述

采用"头尾法存储广义表，实现以下广义表的操作：
1．Status CreateGList( GList &L, char *S ) // 根据字符串 S 表示的广义表内容建立广义表数据结构；
2．GList GetHead( GList L) // 取表头运算
3．GList GetTail( GList L) // 取表尾运算
4．void DestroyGList( GList &L) // 销毁广义表 L
5．void PrintGList( GList L) // 显示广义表 L 内容

程序运行时，首先输入一个广义表，表中的原子是小写字母。随后可以交替输入取表头或取表尾指令（分别用 1 和 2 表示），取的结果替代当前广义表，并释放相应的资源（需将释放资源信息输出）。当广义表是空或是原子时，程序停止运行。

例：（下面的黑体为输入）

((a,()),c,d)

generic list: ((a,()),c,d)

1

destroy tail
free list node
generic list: (a,())

2

free head node
free list node
generic list: (())

1

destroy tail
free list node
generic list: ()

测试输入期待的输出时间限制内存限制额外进程

测试用例 1	(a,(b,(c,d)),e,f) 2 1 2 1 1	generic list: (a,(b,(c,d)),e,f) free head node free list node generic list: ((b,(c,d)),e,f) destroy tail free list node generic list: (b,(c,d)) free head node free list node generic list: ((c,d)) destroy tail free list node generic list: (c,d) destroy tail free list node generic list: c	1秒	64M	0
测试用例 2	(a,(b,(c,(d,())),e)) 2 1 2 1 2 1 2 1	generic list: (a,(b,(c,(d,())),e)) free head node free list node generic list: ((b,(c,(d,())),e)) destroy tail free list node generic list: (b,(c,(d,())),e) free head node free list node generic list: ((c,(d,())),e) destroy tail free list node generic list: (c,(d,())) free head node free list node generic list: ((d,())) destroy tail free list node generic list: (d,()) free head node free list node generic list: (()) destroy tail free list node generic list: ()	1秒	64M	0
测试用例 3	((a,s,(w,e)),q,c) 1 2 2 2	generic list: ((a,s,(w,e)),q,c) destroy tail free list node generic list: (a,s,(w,e)) free head node free list node generic list: (s,(w,e)) free head node free list node generic list: ((w,e)) free head node free list node generic list: ()	1秒	64M	0

解题思路

教材上虽然定义了广义表的存储结构，但是建立广义表的 createList 有些过于复杂，而且其余关键运算也没有给出具体算法。仔细分析题目发现，题目重点要实现的是取表头和取表尾的过程。相比之下，与其大费周章建立广义表，还不如用字符串直接操作来得更快。

用字符串直接存取待操作的广义表，根据输入的数字 1 或 2 进行去表头或取表尾操作即可。

• 表中第一个逗号之前的，都是表头
• 表中第一个逗号之后的，都是表尾

取表头其实在逗号之前也可以判断，找到第一个左括号后的第一对括号，这就是表头。例如 ((a,b),c,(d,e)) 这个广义表，第一对括号(a,b)就是表头。

当然，这个判断与找第一个逗号的差距仅仅是 O(1) 的时间，聊胜于无。我在下面的代码中进行了书写，方便大家理解。

上机代码

#include<cstdio> #include<cstring> #include<cstdlib> char s[1010]; int len1 = 0, len2 = -1; //len1——len2表示每次需要取的区间长度 void gethead(); //取表头 void gettail(); //取表尾int main() {int n = 0, m = 0;memset(s, 0, sizeof(s));scanf("%s", s);printf("generic list: %s\n", s);len2 = strlen(s) - 1;int ans = 0;while (~scanf("%d", &ans)){if (ans == 1) //取表头gethead();else //取表尾gettail();}return 0; } void gethead() {printf("destroy tail\nfree list node\ngeneric list: ");int temp = -1;int i = len1; //每次从上一次的位置开始取while (s[i]!='\0'){if (s[i] == '('){temp++;if (temp == 0)len1 = i + 1;i++;continue;}if (s[i] == ')'){temp--;//if (temp == 0) //第一个左括号后面的第一对括号就是表头//{// len2 = i;// break;//}i++;continue;}if (s[i] == ','&&temp == 0) //表中第一个逗号之前的，都是表头{len2 = i - 1;break;}i++;}//输出表头for (int j = len1; j <= len2; j++){printf("%c", s[j]);}printf("\n"); } void gettail() {printf("free head node\nfree list node\ngeneric list: ");int temp = -1;int vis = 0;int i = len1;while (s[i] != '\0'){if (i == len2) //空表{vis = 1;break;}if (s[i] == '(')temp++;if (s[i] == ')')temp--;if (s[i] == ','&& temp == 0) //表中的第一个逗号之后的，都是表尾{s[i] = '(';len1 = i;break;}i++;}if (vis==1) //空表直接输出{printf("()\n");return;}//输出表尾for (int j = len1; j <= len2; j++){printf("%c", s[j]);}printf("\n"); }

补充说明

相信细心的同学已经发现了上面算法的问题所在

就是当广义表为 ((a,b)) 时，广义表中没有逗号，这时输入 1 ，进行取表头的操作。通过逗号判断的方法就失效了，还是需要我们刚才说的对于第一对括号的判断。

另外，如果广义表为 (a) ，即仅有一个原子时，再输入 1 取表头。这时连括号判断都失效了。对于这样的问题，有一个解决办法是扫描字符串给 len1 赋值时，同时也给 len2 赋相同的值。

• 如果广义表只有单个原子，那么此时的 len2 就是唯一取值，可以直接输出表头
• 如果广义表还有别的元素，len2 在后面必然会更改，不会影响到 len2 的取值

输入数字的 while 循环结尾，判断 len1 是否等于 len2 ，如果二者相等则证明此时广义表仅有原子，程序应该停止运行。二者不等则广义表中仍有元素，还可以进行取表头操作。

至于上面代码中把第一对括号判断进行了注释但是对结果不影响，是因为测试用例里没有针对这种情况的测试，所以代码可以顺序通过学校的 OJ。

刚才列出来的两种缺陷，有兴趣的同学可以在此基础上加点代码将问题解决掉。

下面给出我的示例代码：

#include<cstdio> #include<cstring> #include<cstdlib> char s[1010]; int len1 = 0, len2 = -1; //len1——len2表示每次需要取的区间长度 void gethead(); //取表头 void gettail(); //取表尾int main() {int n = 0, m = 0;memset(s, 0, sizeof(s));scanf("%s", s);printf("generic list: %s\n", s);len2 = strlen(s) - 1;int ans = 0;while (~scanf("%d", &ans)){if (ans == 1) //取表头gethead();else //取表尾gettail();if(len1 == len2) //广义表仅剩原子，停止运行break;}return 0; } void gethead() {printf("destroy tail\nfree list node\ngeneric list: ");int temp = -1;int i = len1; //每次从上一次的位置开始取while (s[i]!='\0'){if (s[i] == '('){temp++;if (temp == 0)len2 = len1 = i + 1;i++;continue;}if (s[i] == ')'){temp--;if (temp == 0) //第一个左括号后面的第一对括号就是表头{len2 = i;break;}i++;continue;}if (s[i] == ','&&temp == 0) //表中第一个逗号之前的，都是表头{len2 = i - 1;break;}i++;}//输出表头for (int j = len1; j <= len2; j++){printf("%c", s[j]);}printf("\n"); } void gettail() {printf("free head node\nfree list node\ngeneric list: ");int temp = -1;int vis = 0;int i = len1;while (s[i] != '\0'){if (i == len2) //空表{vis = 1;break;}if (s[i] == '(')temp++;if (s[i] == ')')temp--;if (s[i] == ','&& temp == 0) //表中的第一个逗号之后的，都是表尾{s[i] = '(';len1 = i;break;}i++;}if (vis==1) //空表直接输出{printf("()\n");return;}//输出表尾for (int j = len1; j <= len2; j++){printf("%c", s[j]);}printf("\n"); }

总结

以上是生活随笔为你收集整理的十六、广义表的建立与基本操作的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。