一、广义表的表示
广义表可以看成是属性表的一种扩充。在线性表中,每一个节点都是一个数据节点,而广义表中每一个节点可以是数据节点,也可以是另一张广义表。我们通常把用于存放数据的节点称作原子节点,而把用于存放另一张广义表的节点称作子表。可见广义表的定义是递归的。下面来看一下广义表的数据结构:
//数据节点,原子节点 typedef struct s_node { //用于存放数据的通用指针 void *data; } s_node; //广义表 typedef struct s_list { /* * 标志用于区分当前节点是原子节点还是子表 * 0原子节点,1子表 */ int tag; //共用体用于存放原子数据或子表地址 union { //原子节点 struct s_node* data; //子表节点 struct s_list* child; }; } s_list;
广义表的数据结构相对简单,但对其的相关操作却比较复杂。下面我们就来编写一个广义表的应用例子。
二、M元多项式
现有一个M元多项式:
我们知道任何一个M元多项式都可以转化成一元系数形式:
于是我们就可以认为多项式中每一个变元的一项就是一个子表,每一个子表都是另一个变元的子表。我们来看一下M元多项式的数据结构:
typedef struct s_list { //0表示原子,1表示子表 int tag; //指数 int exp; //共用体 union { //系数 int coe; //子表 struct s_list* child; }; //下一个结点 struct s_list* next; } s_list;
再来实现几个必要的函数:
//销毁广义表 void list_destory(s_list *list) { if (list == null) { return; } //如果下一节点不为空 if (list->next != null) { //递归销毁下一节点 list_destory(list->next); } //如果当前节点是子表 if (list->tag) { //递归销毁子表 list_destory(list->child); } free(list); } //追加节点 bool list_append(s_list *list, s_list* nlist) { if (list == null) { return false; } if (nlist == null) { return false; } while (list->next != null) { list = list->next; } list->next = nlist; return true; } //初始化表节点 bool list_init(s_list *list) { list->tag = 0; list->coe = 0; list->child = null; list->next = null; return true; } //插入原子节点或子表 bool list_insert_value(s_list *list, int tag, int exp, int val) { if (list == null) { return false; } list->tag = tag; list->exp = exp; list->coe = val; return true; } //显示多项式 void list_display(s_list *list, char ch) { if (list == null) { return; } //如果当前节点是子表 if (list->tag) { printf("("); //递归显示子表 list_display(list->child, ch - 1); printf(")%c^%d", ch, list->exp); } //如果当前节点是原子节点 else { //显示原子内容 printf("%+d%c^%d", list->coe, ch, list->exp); } //如果下一节点不为空 if (list->next != null) { printf("+"); //递归显示下一节点 list_display(list->next, ch); } }
其中需要注意的是void list_display(s_list *list, char ch)函数,它是一个递归函数,用于显示广义表中所有节点的数据内容。如果当前节点是一个子表则递归调用显示子表;如果当前结节是一个原子结节则显示原子内容数据;最后判断下一节点是不是也是一个广义表节点,如果是则递归调用显示其内容。
最后来写一个冗长的main函数构建上述的M元多项式:
#include <stdlib.h> #include "list.h" int main(int argc, char **args) { //list1 x^10 s_list *list1 = (s_list *) malloc(sizeof(s_list)); list_init(list1); list_insert_value(list1, 0, 10, 1); //list2 2x^6 s_list *list2 = (s_list *) malloc(sizeof(s_list)); list_init(list2); list_insert_value(list2, 0, 6, 2); //list1 (x^10 + 2x^6) list_append(list1, list2); //list3 (x^10 + 2x^6)y^3 s_list *list3 = (s_list *) malloc(sizeof(s_list)); list_init(list3); list_insert_value(list3, 1, 3, (int) list1); //list4 3x^5 s_list *list4 = (s_list *) malloc(sizeof(s_list)); list_init(list4); list_insert_value(list4, 0, 5, 3); //list5 (3x^5)y^2 s_list *list5 = (s_list *) malloc(sizeof(s_list)); list_init(list5); list_insert_value(list5, 1, 2, (int) list4); //list3 ((x^10 + 2x^6)y^3 + (3x^5)y^2) list_append(list3, list5); //list6 ((x^10 + 2x^6)y^3 + (3x^5)y^2)z^2 s_list *list6 = (s_list *) malloc(sizeof(s_list)); list_init(list6); list_insert_value(list6, 1, 2, (int) list3); //list7 x^4 s_list *list7 = (s_list *) malloc(sizeof(s_list)); list_init(list7); list_insert_value(list7, 0, 4, 1); //list8 6x^3 s_list *list8 = (s_list *) malloc(sizeof(s_list)); list_init(list8); list_insert_value(list8, 0, 3, 6); //list8 (x^4 + 6x^3) list_append(list7, list8); //list9 (x^4 + 6x^3)y^4 s_list *list9 = (s_list *) malloc(sizeof(s_list)); list_init(list9); list_insert_value(list9, 1, 4, (int) list7); //list10 2y s_list *list10 = (s_list *) malloc(sizeof(s_list)); list_init(list10); list_insert_value(list10, 0, 1, 2); //list9 ((x^4 + 6x^3)y^4 + 2y) list_append(list9, list10); //list11 ((x^4 + 6x^3)y^4 + 2y)z s_list *list11 = (s_list *) malloc(sizeof(s_list)); list_init(list11); list_insert_value(list11, 1, 1, (int) list9); //list6 ((x^10 + 2x^6)y^3 + (3x^5)y^2)z^2 + ((x^4 + 6x^3)y^4 + 2y)z list_append(list6, list11); //list12 15 s_list *list12 = (s_list *) malloc(sizeof(s_list)); list_init(list12); list_insert_value(list12, 0, 0, 15); //list6 ((x^10 + 2x^6)y^3 + (3x^5)y^2)z^2 + ((x^4 + 6x^3)y^4 + 2y)z + 15 list_append(list6, list12); list_display(list6, 'z'); //销毁广义表,释放内存 list_destory(list6); return 0; }
运行结果:
((+1x^10++2x^6)y^3+(+3x^5)y^2)z^2+((+1x^4++6x^3)y^4++2y^1)z^1++15z^0
显示内容格式上不是很友好,但结果是正确的。也说明这个数据结构可以表示任意多元的多项式。
本例代码:
code path chapter.04/e.g.4.3/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号