本文最后更新于 202 天前,其中的信息可能已经过时,如有错误请发送邮件到 1910452164@qq.com
题目要求如下:
记录一下此次学习过程:
代码:
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct GNode { int Tag; // 0表示原子,1表示列表 union { char atom; // 原子值 struct // 指针域 { struct GNode* hp, * tp; // hp连接当前表的子表,tp连接下一个子表 }ptr; }; }*General_List, GNode; void SubString(char sub[], char str[], int start, int len) // 将str中部分内容赋值给sub串 { int i = 0; for (; i < len; ++i) sub[i] = str[start + i - 1]; sub[i] = '\0'; // 结尾补串结束符 } void SeperateList(char* head, char* tail) // 将表tail分离成表头和表尾 { int i = 0, cnt = 0, len = strlen(tail); for (; i < len; ++i) { if (tail[i] == '(') cnt++; if (tail[i] == ')') cnt--; if (!cnt && tail[i] == ',') break; // 找到表头和表尾的分界点 } if (i < len) // 存在表尾 { SubString(head, tail, 1, i); // 分离出表头,赋值给head SubString(tail, tail, i + 2, len - i - 1); // 将自己更新为表尾 } else // 不存在表尾 { SubString(head, tail, 1, len); // 全部更新为表头 tail[0] = 0; } } void Create_General_List(General_List* L, char* str) { if (str == NULL) (*L) = NULL; // 传入了空字符串 else { (*L) = (General_List)malloc(sizeof(GNode)); if (strlen(str) == 1) // 传入字符,只能创建原子节点 { (*L)->Tag = 0; (*L)->atom = *str; } else // 传入字符串,创建list节点 { char head[100] = { '\0' }; SubString(str, str, 2, strlen(str) - 2); // 去除str最外层括号 General_List q, p = (*L); p->Tag = 1; do { SeperateList(head, str); // head变成表头,str变成表尾 Create_General_List(&(p->ptr.hp), head); // 递归创建表头 if ((*str)!=0) // 表尾非空,则下次循环继续将表尾分割成表头和表尾 { q = p; p = (General_List)malloc(sizeof(GNode)); p->Tag = 1; q->ptr.tp = p; // 在当前节点后连接子尾表 } } while ((*str) != 0); p->ptr.tp = NULL; } } } int Get_List_Deepth(General_List L) // 计算表深度 { if (!L) return 1; // 空表深度为1 if (L->Tag == 0) return 0; // 原子不算入深度 int max = 0, dep; for (General_List t = L; t != NULL; t = t->ptr.tp) // 每次循环让t指针指向下一个尾子表 { dep = Get_List_Deepth(t->ptr.hp); // 递归计算头子表深度 max = max < dep ? dep : max; // 更新深度 } return max + 1; } void Clear_List(General_List* L) // 为了删除表首节点,需传入GNode的二级指针 { if (!(*L)) return; // L是空节点 if (!((*L)->Tag)) // 是原子节点 { free((*L)); (*L) = NULL; return; } Clear_List(&((*L)->ptr.hp)); // 递归删除头子表 Clear_List(&((*L)->ptr.tp)); // 递归删除尾子表 free(*L); // 删除自身 *L = NULL; } int main() { General_List L; char buffer[100]; int num; printf("请输入广义表个数:"); scanf("%d", &num); for (int i = 1; i <= num; ++i) { printf("请输入广义表:"); scanf("%s", buffer); Create_General_List(&L, buffer); printf("第%d个广义表的深度为:%d\n", i, Get_List_Deepth(L)); Clear_List(&L); if (!L) printf("该广义表内存已释放\n\n"); else { printf("内存释放出错,已退出\n\n"); } } return 0; } // ((a,b,(c,(d,e),f)),g) // (a,(b,(c,(d,(e,(f),(g)))))) // (a) // ((((((a),b),c),d),e),f)
分析:
对于题目所要求的算法 Get_List_Deepth 来说,首先判断当前广义表是否为空表,若为空表,则记其深度为 1;其次判断当前广义表节点是否为原子,原子不计入深度。判断完特殊情况后,开始对传入节点进行循环,在每一轮循环中,首先对其头子表进行递归,计算以其为起点的子表深度,然后更新当前深度的最大值,循环结束后转向当前表的尾子表,开始下一轮循环。此循环结束后就可以得到当前表的子表的深度,最后将其 + 1 并返回即可。
你在干嘛?等待戈多。
戈多是谁?我不知道。
你在干嘛?等待戈多。
戈多是谁?我不知道。
我在干嘛?等待戈多。