数据�l�构�W�五章算法设计题[11]_跨考网

       1. 试编写徏立广义表存储�l�构的算法，要求在输入广义表的同时实现判断、徏立。设�q�义表按如下形式输入�Q?/span>a1,a2,a3,�?/span>,an�Q?/span> n>=0�Q�其�?/span>ai或�ؓ(f��)单字母表�C�的原子或�ؓ(f��)�q�义表，n=0时�ؓ(f��)只含�I�格字符的空表�?/span>(�?/span>:���法可用�c?/span>pascal 或类c书写) �?a target="_blank">北京工业大学 1998 �?/span> (15�?/span>)�?/span>

　　【参考答案�?/span>

　　[题目分析] �q�义表的元素有原子和表。在��d���q�义表“表辑ּ�”时�Q�遇到左括号‘（’就递归的构造子表，否则若是原子�Q�就建立原子�l�点�Q�若��d��逗号‘，’，���递归构造后�l�子表；�?/span>n=0�Q�则构造含�I�格字符的空表，直到���到输入�l�束�W�号�Q��?/span>#’）。设�q�义表的形式定义如下�Q?/span>

　　typedef struct node

　　{int tag; //tag=0为原子，tag=1为子�?/span>

　　struct node *link; //指向后���l�点的指�?/span>

　　union {struct node *slink; //指向子表的指�?/span>

　　char data; //原子

　　}element;

　　}Glist;

　　Glist *creat ()

　　//建立�q�义表的存储�l�构

　　{char ch; Glist *gh;

　　scanf(�?/span>%c�?/span>,&ch);

　　if(ch==’�?/span>) gh=null;

　　else {gh=(Glist*)malloc(sizeof(Glist));

　　if(ch==�?/span>(�?/span>){gh->tag=1; //子表

　　gh->element.slink=creat(); } //递归构造子�?/span>

　　else {gh->tag=0;gh->element.data=ch;} //原子�l�点

　　}

　　scanf(�?/span>%c�?/span>,&ch);

　　if(gh!=null) if(ch==�?/span>,�?/span>) gh->link=creat()�Q?/span> //递归构造后�l�广义表

　　else gh->link=null;

　　return(gh);

　　}

　　}���法�l�束