用C语言写一个代码实现:用户从键盘输入描述广义表的字符串,系统实现创建广义表,求广义表的长度、深度,复制广义表,遍历广义表,取广义表的表头、表尾的操作。
时间: 2024-03-16 21:44:17 浏览: 21
下面是一个实现上述功能的C语言程序:
```C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 广义表节点的结构体定义
typedef struct GLNode{
int tag; // 标志域,0表示单元素,1表示子表
union{
char data; // 单元素值
struct GLNode *sublist; // 子表指针
}val;
struct GLNode *next; // 指向下一个节点的指针
}GLNode, *GList;
// 创建广义表
GList createGList(char *str){
GList L = NULL; // 初始化为空表
GLNode *p = NULL; // 工作指针
int k = 0; // k为1表示正在读取单元素,为0表示正在读取子表
int len = strlen(str); // 字符串长度
char ch;
for(int i = 0; i < len; i++){
ch = str[i];
switch(ch){
case '(': // 开始读取子表
k = 0;
GLNode *sublist = createGList(str + i + 1); // 递归创建子表
i += strlen(str + i) - strlen(str + i + 1); // 跳过子表所占的字符
if(L == NULL){ // 第一个节点
L = (GLNode *)malloc(sizeof(GLNode));
L->tag = 1;
L->val.sublist = sublist;
p = L;
}
else{ // 后续节点
GLNode *node = (GLNode *)malloc(sizeof(GLNode));
node->tag = 1;
node->val.sublist = sublist;
p->next = node;
p = node;
}
break;
case ')': // 子表读取结束
return L;
case ',': // 分隔符
k = 0;
break;
default: // 读取单元素
if(k == 0){ // 第一个节点
L = (GLNode *)malloc(sizeof(GLNode));
L->tag = 0;
L->val.data = ch;
p = L;
}
else{ // 后续节点
GLNode *node = (GLNode *)malloc(sizeof(GLNode));
node->tag = 0;
node->val.data = ch;
p->next = node;
p = node;
}
k = 1;
break;
}
}
return L;
}
// 求广义表的长度
int getGListLength(GList L){
if(L == NULL) return 0;
int len = 0;
GLNode *p = L;
while(p != NULL){
if(p->tag == 0) len++; // 单元素,长度+1
else len += getGListLength(p->val.sublist); // 子表,递归求长度
p = p->next;
}
return len;
}
// 求广义表的深度
int getGListDepth(GList L){
if(L == NULL) return 0;
int maxDepth = 0;
GLNode *p = L;
while(p != NULL){
if(p->tag == 1){ // 子表,递归求深度
int depth = getGListDepth(p->val.sublist);
if(depth > maxDepth) maxDepth = depth;
}
p = p->next;
}
return maxDepth + 1; // 当前节点的深度为子表深度+1
}
// 复制广义表
GList copyGList(GList L){
if(L == NULL) return NULL;
GList newL = NULL;
GLNode *p = L, *q = NULL;
while(p != NULL){
GLNode *node = (GLNode *)malloc(sizeof(GLNode));
node->tag = p->tag;
if(p->tag == 0) node->val.data = p->val.data; // 单元素,直接复制值
else node->val.sublist = copyGList(p->val.sublist); // 子表,递归复制
if(newL == NULL) newL = node; // 第一个节点
else q->next = node; // 后续节点
q = node;
p = p->next;
}
return newL;
}
// 遍历广义表
void traverseGList(GList L){
if(L == NULL) return;
GLNode *p = L;
putchar('(');
while(p != NULL){
if(p->tag == 0){ // 单元素,直接输出
putchar(p->val.data);
if(p->next != NULL) putchar(',');
}
else{ // 子表,递归输出
traverseGList(p->val.sublist);
if(p->next != NULL) putchar(',');
}
p = p->next;
}
putchar(')');
}
// 取广义表的表头
int getHead(GList L, char *head){
if(L == NULL || L->tag == 1) return 0; // 空表或者表头为子表,返回0
*head = L->val.data; // 取出表头元素
return 1;
}
// 取广义表的表尾
int getTail(GList L, GList *tail){
if(L == NULL) return 0; // 空表,返回0
*tail = L->next; // 取出表尾指针
return 1;
}
int main(){
char str[100];
printf("请输入广义表的字符串表示:");
scanf("%s", str);
GList L = createGList(str);
printf("广义表的长度为:%d\n", getGListLength(L));
printf("广义表的深度为:%d\n", getGListDepth(L));
GList newL = copyGList(L);
printf("复制后的广义表为:");
traverseGList(newL);
putchar('\n');
printf("遍历广义表:");
traverseGList(L);
putchar('\n');
char head;
if(getHead(L, &head)) printf("广义表的表头为:%c\n", head);
else printf("广义表为空或者表头为子表\n");
GList tail;
if(getTail(L, &tail)){
printf("广义表的表尾为:");
traverseGList(tail);
putchar('\n');
}
else printf("广义表为空\n");
return 0;
}
```
运行程序后,用户可以输入描述广义表的字符串,程序会根据该字符串创建广义表,并进行长度、深度、复制、遍历、取表头、取表尾等操作。