数据结构关于广义表部分的课程设计，高分！求高手！

2025-02-08 13:45:58

推荐回答（1个）

回答1：

给你一个我们的实验报告的程序用C编写的，有具体注释的。
主文件：
#include
#include
#include
typedef char DataType;
#include "GList.h"

void main()
{ char str1[]="(((a,b,c),(d)),e)";
char str2[]="(((a,b,c),(d)),e)";
char hstr[100];
GLNode *h, *p;
int depth, number, length;
h=CreatGList(str1);
printf("广义表str1=%s",str2);
DecomposeStr(str2, hstr);
printf("\n表头=%s",hstr);
printf(" 表尾=%s",str2);

depth=GListDepth(h);
printf("\n深度depth=%d",depth);
length=GListLength(h);
printf("\n深度length=%d", length);
number=GListAtomNum(h);
printf("\n原子元素个数number=%d", number);

p=GListSearch(h,'d');
if (p!=NULL)
printf("\n数据元素%c在广义表中", p->val.atom);
else
printf("\n广义表中不存在要查找的数据元素\n");
DestroyGList(h);

头文件：
typedef struct GListNode
{
int tag;
union
{ DataType atom; //原子元素域
struct subGL
{ struct GListNode *head; //头指针
struct GListNode *tail; //尾指针
}subList; //子表域
}val;
}GLNode;

void DecomposeStr(char str[], char hstr[])
{
int i, j, tag, n = strlen(str);
char ch; ch = str[0]; tag = 0;
for(i = 0; i <= n-1; i++)
{ if(str[i] == ',' && tag == 1 ) break;//搜索最外层的第一个逗号
ch = str[i];
if(ch == '(') tag++;
if(ch == ')') tag--;
}
if(i <= n-1 && str[i] == ',') //广义表表尾部分非空时
{ for(j = 0; j < i-1; j++) hstr[j] = str[j+1];//取表头字符串
hstr[j] = '\0'; //添加结束符
if(str[i] == ',') i++;
str[0] = '('; //添'('
for(j = 1; i <= n-2; i++, j++) str[j] = str[i]; //取表尾字符串
str[j] = ')'; //添')' str[++j] = '\0'; //添加结束符
}
else //广义表表尾部分空时

{ str++; //路过最左边的'('
strncpy(hstr,str, n-2);//不复制右边的')'
hstr[n-2] = '\0'; //添加结束符
str--; //恢复字符串指针位置
strcpy(str, "()"); //表尾部分为空
}
}
GLNode* CreatGList(char str[])
{ GLNode *h;
char hstr[200];
int len = strlen(str);
if(strcmp(str, "()") == 0) h = NULL;
else if(len == 1) //建立原子结点
{ h = (GLNode *)malloc(sizeof(GLNode));
h->tag = 0;
h->val.atom = str[0];
}
else //建立子表
{
h = (GLNode *)malloc(sizeof(GLNode));
h->tag = 1;
DecomposeStr(str, hstr);
h->val.subList.head = CreatGList(hstr);

if(strcmp(str, "()") != 0) //表尾非空时
h->val.subList.tail = CreatGList(str);
else
h->val.subList.tail = NULL; //赋值空指针
}
return h;
}
int GListDepth(GLNode *h)
{ int max, dep;
GLNode *pre;
if(h == NULL) return 1;//递归出口，空表深度为1
if(h->tag == 0) return 0; //递归出口，原子元素深度为0
//递归求广义表深度
pre = h;
for(max = 0; pre != NULL; pre = pre->val.subList.tail)
{ dep = GListDepth(pre->val.subList.head); //求表头深度
if(dep > max) max = dep;
}
return max + 1;
}
int GListLength(GLNode *h)
{
int number = 0;
GLNode *p;

for(p = h; p != NULL; p = p->val.subList.tail)
number++;
return number;
}
int GListAtomNum(GLNode *h)
{
if(h == NULL) return 0;
else
{
if(h->tag == 0) return 1; else return GListAtomNum(h->val.subList.head) +
GListAtomNum(h->val.subList.tail);
}
}

GLNode *GListSearch(GLNode *h, DataType x)
{
GLNode *p;
if(h==NULL) return NULL;//查找失败递归出口
if(h->tag==0&&h->val.atom==x) return h;//查找成功递归出口
if(h->tag==1&&h->val.subList.head!=NULL)
{ p=GListSearch(h->val.subList.head,x); //在头链中查找
if (p!=NULL)
return p;
}
if(h->tag==1&&h->val.subList.tail!=NULL)
{ p=GListSearch(h->val.subList.tail,x); //在尾链中查找
if (p!=NULL)
return p;
}
return NULL; //回溯至上一层
}

void DestroyGList(GLNode *h)
{
if(h==NULL) return ;
if(h->tag==1&&h->val.subList.head!=NULL)
DestroyGList(h->val.subList.head); //撤销head所指子表
if(h->tag==1&&h->val.subList.tail!=NULL)
DestroyGList(h->val.subList.tail); //撤销tail所指子表
free(h);
}

最新问答

现在从廊坊长途站到固安县城下午最晚一趟车是几点啊

分别滴加氯水,再加入少量四氯化碳,振荡,下层溶液为无色的是Cl-;下层溶液为橙红色

建筑内部装修纺织织物包括哪些部位的什么材料？

苹果手机QQ突然闪退怎么回事？

2011款别克君越2.4标配的车为什么热车没有急加速？起步的时候跳档慢，都达到两千多转以上？

我家在平原地带河南开封的，我就是想在家种两颗核桃树可以吗不是大面积种植