阅读:0       作者:严长生

广义表及M元多项式的C语言代码实现

广义表,又称为列表记作:
LS = (a1,a2,…,an) ;( LS 为广义表的名称, an 表示广义表中的数据)。
广义表可以看作是线性表的推广。两者区别是:线性表中的数据元素只能表示单个数据元素;广义表中的单个数据元素 ai ,既可以是单个元素,也可以是广义表。

原子和子表

在广义表中,单个元素被称为 “原子”;包含的广义表被称为 “子表”

例如:
  1. A = ()  :A 表示一个广义表,只不过表是空的,广义表 A 的长度为 0。
  2. B = (e)  :广义表 B 中只有一个原子 e ,长度为 1。
  3. C = (a,(b,c,d)) :广义表 C 中有两个元素,原子 a 和子表 (b,c,d) ,广义表C的长度为 2。 
  4. D = (A,B,C) :广义表 D 中有三个元素:子表 A、B、C,长度为 3 ,这种表示方式等同于: D = ((),(e),(b,c,d)) 。
  5. E = (a,E)  :广义表 E 中有两个元素,原子 a 和它本身,长度为 2 。这是一个递归的表,等同于:E = (a,(a,(a,…)))。
A = () 和 A = (()) 是不一样的:前者是空表,长度为 0 ;后者表的长度为 1 ,包含的元素是一个子表,只不过这个子表是空表。

表头和表尾

当广义表不为空时,称表中的第一个元素为表的 “表头” ;剩余所有元素组成的表为 “表尾” 
任何一个非空广义表,表尾肯定是广义表。
例如:上边例子中的 D = (A,B,C) ,子表 A 为广义表 D 的表头;而 (B,C) 组成的表为 D 的表尾。

非空广义表是由表头和表尾构成,反过来说也对:给定一个表头和表尾,可以唯一确定一个广义表。

广义表中结点结构

由于广义表中的数据元素类型分为原子和子表,难以使用顺序存储结构表示,所以通常采用链式存储结构

根据原子和子表的不同,链式存储中的结点需要用两种不同的结构表示。对于原子来说,需要由两部分组成:标志位 + 值域(如图1(A));子表需要由三部分组成:标志位 + 指向表头的指针域 + 指向表尾的指针域(如图1(B))。
两者都有一个相同的标志位,作用是为了能够区分出原子和字表,一般标志位为1,表示子表;标志位为0,表示原子。


图1 广义表的链表结点结构
代码表示:
typedef struct GLNode{
    int tag;//标志域
    union{
        char atom;//原子结点的值域
        struct{
            struct GLNode * hp,*tp;
        }ptr;//子表结点的指针域,hp指向表头;tp指向表尾
    };
}*Glist;
例如,使用图1的链表结构表示广义表 C = (a,(b,c,d)),效果图为:


图2 广义表C的结构示意图
实现代码为:
Glist creatGlist(Glist C){
    //广义表C
    C=(Glist)malloc(sizeof(Glist));
    C->tag=1;
    //表头原子‘a’
    C->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.hp->tag=0;
    C->ptr.hp->atom='a';
    //表尾子表(b,c,d),是一个整体
    C->ptr.tp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.tp=NULL;
    //开始存放下一个数据元素(b,c,d),表头为‘b’,表尾为(c,d)
    C->ptr.tp->ptr.hp->tag=1;
    C->ptr.tp->ptr.hp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.hp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.hp->atom='b';
    C->ptr.tp->ptr.hp->ptr.tp=(Glist)malloc(sizeof(Glist));
    //存放子表(c,d),表头为c,表尾为d
    C->ptr.tp->ptr.hp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.hp->atom='c';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp=(Glist)malloc(sizeof(Glist));
    //存放表尾d
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->tag=1;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp=(Glist)malloc(sizeof(Glist));
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->tag=0;
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.hp->atom='d';
    C->ptr.tp->ptr.hp->ptr.tp->ptr.tp->ptr.tp=NULL;
    return C;
}

结点结构的另一种表示方式

除了上边的那种表示结点的方式,还可以采用另外一种表示形式,不同在于:表结点和原子结点都添加了一个指向下一个数据元素的指针;而子表结点中只保留了指向表头结点的指针,删除了指向表尾的指针。


图3 广义表的另一种结点结构
代码表示为:
typedef struct GLNode{
    int tag;//标志域
    union{
        int atom;//原子结点的值域
        struct GLNode *hp;//子表结点的指针域,hp指向表头
    };
    struct GLNode * tp;//这里的tp相当于链表的next指针,用于指向下一个数据元素
}*Glist;
例如,用这种结构结构表示C = (a,(b,c,d)),效果图为:


图4 广义表C的结构示意图
实现代码:
Glist creatGlist(Glist C){
    C=(Glist)malloc(sizeof(Glist));
    C->tag=1;
    C->hp=(Glist)malloc(sizeof(Glist));
    C->tp=NULL;
    //表头原子a
    C->hp->tag=0;
    C->atom='a';
    C->hp->tp=(Glist)malloc(sizeof(Glist));
    C->hp->tp->tag=1;
    C->hp->tp->hp=(Glist)malloc(sizeof(Glist));
    C->hp->tp->tp=NULL;
    //原子b
    C->hp->tp->hp->tag=0;
    C->hp->tp->hp->atom='b';
    C->hp->tp->hp->tp=(Glist)malloc(sizeof(Glist));
    //原子c
    C->hp->tp->hp->tp->tag=0;
    C->hp->tp->hp->tp->atom='c';
    C->hp->tp->hp->tp->tp=(Glist)malloc(sizeof(Glist));
    //原子d
    C->hp->tp->hp->tp->tp->tag=0;
    C->hp->tp->hp->tp->tp->atom='d';
    C->hp->tp->hp->tp->tp->tp=NULL;
    return C;
}

总结

在编写代码时,一定要注意不要破坏广义表中数据元素之间的关系,例如:C1 = (a,b,c,d)和 C2 = (a,(b,c),d),两个广义表中数据元素是一样的,但是数据元素之间的关系不同,在 C1 中,各原子之间是并列的,而 C2 中,原子 a 和子表 (b,c) 和 d 是并列的。

补:M元多项式的表示

例如:
P(x,y,z) = x10y3z2 + 2x6y3z2 + 3x5y2z2 + x4y4z + 6x3y4z + 2yz + 15
这是一个3元多项式(有3个变量:x,y,z),使用广义表表示M元多项式,首先需要对多项式做一下变形:
P(x,y,z)=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15
经过变形后,P(x,y,z)可以这样表示:
P(x,y,z)=Az2+Bz+15,其中:A=Cy3+Dy2,B=Ey4+Fy,C=x10+2x6,D=3x5,E=x4+6x3,F=2

经过两轮转化后,P这个 3 元多项式分解成了由 A 多项式和 B 多项式组成的一元多项式(只有一个变元 z ),而 A 也变成了由 C 多项式和 D 多项式组成的一元多项式,…。

当全部转化成能用一元多项式表示时,每一个一元多项式只需要存储各项的指数和系数就可以了。

广义表中每个结点的构成如图5所示:


图5 多项式结点构成
代码表示:
typedef struct MPNode{
    int tag;//区分原子结点和子表结点(0代表原子;1代表子表)
    int exp;//存放指数域
    union{
        int coef;//存放多项式的系数
        struct MPNode * hp;//当多项式系数为子表时,用它
    };
    struct MPNode * tp;//相当于线性链表的next,指向下一个数据元素
}*MPList;
注意:在表示多项式的时候,每一个一元多项式,都要额外添加一个表头结点,用于记录此一元多项式中的变元(是x,y还是z),而所有的变元可以预先存储在数组中,这样就可以利用每一个表头结点中的 exp 变量表示变元所在数组中的位置下标。

实现代码:
MPList initP(MPList P){
    char a[]="xyz";
    MPList F=(MPList)malloc(sizeof(MPList));
    F->tag=1;
    F->exp=0;//表示F这个一员多项式中的变元位a[0],也就是x
    F->hp=NULL;
   
    F->tp=(MPList)malloc(sizeof(MPList));
    F->tp->tag=0;
    F->tp->exp=0;//x的指数为0
    F->tp->coef=2;//系数为2
    F->tp->tp=NULL;//tp截止,说明F=2;
   
    MPList E=(MPList)malloc(sizeof(MPList));
    E->tag=1;
    E->exp=0;//E中变元位a[0],即x
    E->hp=NULL;
   
    E->tp=(MPList)malloc(sizeof(MPList));
    E->tp->tag=0;
    E->tp->exp=4;
    E->tp->coef=1;
    E->tp->tp=(MPList)malloc(sizeof(MPList));
    E->tp->tp->tag=0;
    E->tp->tp->exp=3;
    E->tp->tp->coef=6;
    E->tp->tp->tp=NULL;//截止,E=1*x4+6*x3(x后为它的指数)
   
    MPList D=(MPList)malloc(sizeof(MPList));
    D->tag=1;
    D->exp=0;//D中变元为a[0],即x
    D->hp=NULL;
   
    D->tp=(MPList)malloc(sizeof(MPList));
    D->tp->tag=0;
    D->tp->exp=5;
    D->tp->coef=3;
    D->tp->tp=NULL;//截止,D=3*x5(5是x的指数);
   
    MPList C=(MPList)malloc(sizeof(MPList));
    C->tag=1;
    C->exp=0;//C中变元为a[0]=x;
    C->hp=NULL;
   
    C->tp=(MPList)malloc(sizeof(MPList));
    C->tp->tag=0;
    C->tp->exp=10;
    C->tp->coef=1;
    C->tp->tp=(MPList)malloc(sizeof(MPList));
    C->tp->tp->tag=0;
    C->tp->tp->exp=6;
    C->tp->tp->coef=2;
    C->tp->tp->tp=NULL;//C=1*x10+2*x6
   
    MPList B=(MPList)malloc(sizeof(MPList));
    B->tag=1;
    B->exp=1;//B中变元为a[1]=y
    B->hp=NULL;
    B->tp=(MPList)malloc(sizeof(MPList));
    B->tp->tag=1;
    B->tp->exp=4;
    B->tp->hp=E;
    B->tp->tp=(MPList)malloc(sizeof(MPList));
    B->tp->tp->tag=1;
    B->tp->tp->exp=1;
    B->tp->tp->hp=F;
    B->tp->tp->tp=NULL;//B=E*y4+F*x1;
   
    MPList A=(MPList)malloc(sizeof(MPList));
    A->tag=1;
    A->exp=1;//A中变元为a[1]=y;
    A->hp=NULL;
    A->tp=(MPList)malloc(sizeof(MPList));
    A->tp->tag=1;
    A->tp->exp=3;
    A->tp->hp=C;
    A->tp->tp=(MPList)malloc(sizeof(MPList));
    A->tp->tp->tag=1;
    A->tp->tp->exp=2;
    A->tp->tp->hp=D;
    A->tp->tp->tp=NULL;//A=C*y3+D*y2;
   
    P=(MPList)malloc(sizeof(MPList));
    P->tag=1;
    P->exp=3;//表示表元的数量
    P->hp=(MPList)malloc(sizeof(MPList));
    P->tp=NULL;
   
    P->hp->tag=1;
    P->hp->exp=2;//P中变元为a[2]=z;
    P->hp->hp=NULL;
    P->hp->tp=(MPList)malloc(sizeof(MPList));
    P->hp->tp->tag=1;
    P->hp->tp->exp=2;
    P->hp->tp->hp=A;
    P->hp->tp->tp=(MPList)malloc(sizeof(MPList));
    P->hp->tp->tp->tag=1;
    P->hp->tp->tp->exp=1;
    P->hp->tp->tp->hp=B;
    P->hp->tp->tp->tp=(MPList)malloc(sizeof(MPList));
    P->hp->tp->tp->tp->tag=0;
    P->hp->tp->tp->tp->exp=0;
    P->hp->tp->tp->tp->coef=15;
    P->hp->tp->tp->tp->tp=NULL;//P=A*z2+B*z1+15
    return P;
}