百度的网站收录怎么做,做网站设计公司,宽城网站制作,做响应式的网站有哪些目录 前言一、有序表的合并1.1 顺序表实现1.2 单链表实现 二、稀疏多项式的相加和相乘2.1 稀疏多项式的相加2.2 稀疏多项式的相乘 总结 前言
本篇文章介绍线性表的应用#xff0c;分别使用顺序表和单链表实现有序表的合并#xff0c;最后介绍如何使用单链表实现两个稀疏多项… 目录 前言一、有序表的合并1.1 顺序表实现1.2 单链表实现 二、稀疏多项式的相加和相乘2.1 稀疏多项式的相加2.2 稀疏多项式的相乘 总结 前言
本篇文章介绍线性表的应用分别使用顺序表和单链表实现有序表的合并最后介绍如何使用单链表实现两个稀疏多项式的相加和相乘。
一、有序表的合并
已知线性表La和Lb的数据元素按值非递减有序排列现要求将La和Lb合并为一个新的线性表Lc且Lc中的数据元素仍按值非递减有序排序。 非递减指可以有相同的值出现在同一个线性表中 L a ( a , b , c ) La(a,b,c) La(a,b,c) L b ( c , d , e , f ) Lb(c,d,e,f) Lb(c,d,e,f) L a La La和 L b Lb Lb合并后 L c ( a , b , c , c , d , e , f ) Lc(a,b,c,c,d,e,f) Lc(a,b,c,c,d,e,f)
1.1 顺序表实现 算法步骤 创建一个空表Lc依次从La或Lb中摘取元素值较小的结点插入到Lc表后直至其中一个表变为空为止继续将La或Lb其中一个表的剩余结点插图到Lc表的最后 代码实现如下
//定义返回值状态码
#define SUCCESS 1
#define ERROR 0//这里假设元素的数据类型为char
typedef char ElemType;//定义一个线性表
struct SeqList {int MAXNUM; //线性表中最大元素的个数int n; //线性表中实际的元素个数n MAXNUMElemType* element; //存放线性表元素,element[0],element[1]...element[n-1]
};//定义一个SeqList的指针类型
typedef struct SeqList* PSeqList;
//合并两个有序表
void mergeList_seq(PSeqList La, PSeqList Lb, PSeqList Lc)
{ElemType* pa La-element;ElemType* pb Lb-element; //指针pa和pb分别指向两个表的第一个元素Lc-n La-n Lb-n;Lc-MAXNUM Lc-n;Lc-element (ElemType*)malloc(sizeof(Lc-n)); //为合并的新表分配一个数组空间if (NULL Lc-element){printf(malloc fail!\n);exit(ERROR);}ElemType* pc Lc-element; //指针pc指向Lc表的第一个元素ElemType* pa_last La-element (La-n - 1); //指针pa_last指向La表的最后一个元素ElemType* pb_last Lb-element (Lb-n - 1); //指针pb_last指向Lb表的最后一个元素while (pa pa_last pb pb_last){if (*pa *pb)*pc *pa;else*pc *pb;}while (pa pa_last) *pc *pa; //Lb表到达表尾将La表中剩余元素加入Lcwhile (pb pb_last) *pc *pb; //La表到达表尾将Lb表中剩余元素加入Lc
}1.2 单链表实现
为了方便使用选择带头结点的单链表 算法步骤 pa和pb指针分别指向La和Lb的首元结点pc指向La的头结点用La的头结点作为Lc的头结点依次从La或Lb中摘取元素值较小的结点插入到Lc表后直至其中一个表变为空为止继续将La或Lb其中一个表的剩余结点插图到Lc表的最后 代码实现如下
//假设数据元素类型为char
typedef char ElemType;//定义结点类型
struct Node;
typedef struct Node* PNode; //假设作为结点指针类型
struct Node {ElemType data; //数据域PNode next; //指针域
};typedef struct Node* LinkList; //假设作为单链表类型//合并两个有序表
//带头结点
void mergeList_link(LinkList* La, LinkList* Lb, LinkList* Lc)
{PNode pa (*La)-next;PNode pb (*Lb)-next;PNode pc *La;*Lc *La; //用La的头结点作为Lc的头结点while (pa pb){if (pa-data pb-data){pc-next pa;pc pa;pa pa-next;}else{pc-next pb;pc pb;pb pb-next;}}pc-next pa ? pa : pb; //插入剩余元素free(*Lb); //释放Lb的头结点*Lb NULL;
}二、稀疏多项式的相加和相乘
假设有两个多项式 f 1 ( x ) 7 3 x 9 x 8 5 x 17 f_1(x)73x9x^85x^{17} f1(x)73x9x85x17 f 2 ( x ) 8 x 22 x 7 − 9 x 8 f_2(x)8x22x^7-9x^8 f2(x)8x22x7−9x8 多项式的通项公式为 P n ( x ) p 1 x e 1 p 2 x e 2 ⋯ p m x e m P_n(x)p_1x^{e_1}p_2x^{e_2}\cdotsp_mx^{e_m} Pn(x)p1xe1p2xe2⋯pmxem 利用线性表P表示则 线性表 P ( ( p 1 , e 1 ) , ( p 2 , e 2 ) , ⋯ , ( p m , e m ) ) 线性表P((p_1,e_1),(p_2,e_2),\cdots,(p_m,e_m)) 线性表P((p1,e1),(p2,e2),⋯,(pm,em)) 则 f 1 ( x ) 和 f 2 ( x ) 分别用线性表 A 和 B 表示 f_1(x)和f_2(x)分别用线性表A和B表示 f1(x)和f2(x)分别用线性表A和B表示 线性表 A ( ( 7 , 0 ) , ( 3 , 1 ) , ( 9 , 8 ) , ( 5 , 17 ) ) 线性表A((7,0),(3,1),(9,8),(5,17)) 线性表A((7,0),(3,1),(9,8),(5,17)) 线性表 B ( ( 8 , 1 ) , ( 22 , 7 ) , ( − 9 , 8 ) ) 线性表B((8,1),(22,7),(-9,8)) 线性表B((8,1),(22,7),(−9,8)) 假设使用顺序表实现多项式的相加 算法步骤 创建一个新数组c分别从头遍历比较a和b的每一项 指数相同对应系数相加若其和为零则比较两个表的下一项若其和不为零则在c中增加一个新项 指数不相同则将指数比较小的项复制到c中一个多项式遍历完毕时将另一个剩余项依次复制到c中 那么数组c的大小如何确定由于无法确定数组c的大小所以这里不使用顺序表实现而是用单链表实现。 定义多项式的结点及其结构
//定义多项式结点
struct PolyNode
{float coef; //系数int expn; //指数struct PolyNode* next;
};
//定义多项式结点指针类型
typedef struct PolyNode* PPolyNode;
//定义多项式类型
typedef struct PolyNode* PolyLinkList;2.1 稀疏多项式的相加 算法步骤 指针p1和p2初始化分别指向Pa和Pb的首元结点p3指向和多项式的当前结点初值为Pa的头结点当指针p1和p2均为到达表尾时则循环比较p1和p2所指结点的指数值p1-expn 与 p2-expn分3种情况 当p1-expn p2-expn是则将两个结点中的系数相加 若和不为零则修改p1所指结点的系数值同时删除p2所指结点 若和为零则删除p1和p2所指结点 当p1-expn p2-expn时则取p1所指结点插入到和多项式链表中 当p1-expn p2-expn时则取p2所指结点插入到和多项式链表中将非空表的剩余结点插入到p3所指结点的后面释放Pb的头结点 代码实现如下
void poly_add(PolyLinkList* Pa, PolyLinkList* Pb, PolyLinkList* Pc)
{PPolyNode p1 (*Pa)-next; //指向Pa链表的首元结点PPolyNode p2 (*Pb)-next; //指向Pb链表的首元结点PPolyNode p3 *Pa; //指向Pa的头结点作为和多项式链表 *Pc *Pa;PPolyNode q NULL; //指向要被删除的结点 while (p1 p2){if (p1-expn p2-expn) //p1指数等于p2指数{float coef p1-coef p2-coef;if (coef) //不为零{//修改p1所指结点的系数p1-coef coef;p3-next p1;p3 p1;p1 p1-next;}else //为零{//删除p1所指结点q p1;p1 p1-next;free(q);q NULL;}//删除p2所指结点q p2;p2 p2-next;free(q);q NULL;} else if (p1-expn p2-expn) //p1指数小于p2指数{//p1所指结点插入到和多项式链表p3-next p1;p3 p1;p1 p1-next;}else //p1指数大于p2指数{//p2所指结点插入到和多项式链表p3-next p2;p3 p2;p2 p2-next;}}p3-next p1 ? p1 : p2; //插入剩余数据元素free(*Pb); //释放Pb头结点*Pb NULL;
}2.2 稀疏多项式的相乘 指针p1和p2初始化分别指向Pa和Pb的首元结点指针p3初始化指向Pc的头结点,初化始时Pc只是一个空表用Pa的第一项与Pb的每一项相乘将每一项相乘结果插入到Pc中(有序)从Pa的第二项开始与Pb的每一项相乘将每一项结果插入到Pc中插入后有序 在Pc寻找插入位置 设coef p1-coef * p2-coef ,expn p1-expn p2-expn,表示当前p1和p2所指项的相乘结果 若p3-next-expn expn,则p3 p3-next直到p3-next-expn expn分两种情况 若存在p3-next-expn expn, 则新建一个结点插入到p3所指结点后 若不存在p3-next-expn expn,即p3-next NULL时则新建一个结点插入到p3所指结点后 若p3-next-expn expn,分两种情况 若p3-next-coef coef结果为零则删除p3-next所指结点 若p3-next-coef coef结果不为零则修改p3-next所指结点的系数 代码实现如下
//逐项插入法
void poly_mul(PolyLinkList* Pa, PolyLinkList* Pb, PolyLinkList* Pc)
{PPolyNode p1 (*Pa)-next;PPolyNode p2 (*Pb)-next; //p1,p2分别指向Pa和Pb的首元结点PPolyNode p3 *Pc; //p3分别指向Pc的头结点 PPolyNode temp NULL; //作为一个临时的结点指针if (p1)//将p1的第一项乘以Pb的每一项{while (p2){PPolyNode newNode (PPolyNode)malloc(sizeof(struct PolyNode));if (NULL newNode){printf(malloc fail!\n);exit(ERROR);}newNode-coef p1-coef * p2-coef; //p1,p2所指结点的系数相乘newNode-expn p1-expn p2-expn; //p1,p2所指结点的指数相加newNode-next NULL;p3-next newNode;p3 newNode;p2 p2-next;}}//从Pa的第二项开始与Pb的每一项相乘将每一项结果插入到Pc,直到p1到达Pa的表尾p1 p1-next;while (p1){p2 (*Pb)-next;p3 *Pc;while (p2){//在Pc寻找插入位置float coef p1-coef * p2-coef;int expn p1-expn p2-expn;while (p3-next p3-next-expn expn)p3 p3-next;if (p3-next p3-next-expn expn) //expn与p3-next-expn相同{if (p3-next-coef coef) //和不为零p3-next-coef coef;else //和为零{//删除p3-next所指结点temp p3-next;p3-next temp-next;free(temp);temp NULL;}}else //p3-next-expn expn 或p3-next NULL{//在p3-next前插入一个新结点temp (PPolyNode)malloc(sizeof(struct PolyNode));if (NULL temp){printf(malloc fail!\n);destoryPoly(Pc);}temp-coef coef;temp-expn expn;temp-next p3-next;p3-next temp;p3 p3-next;}p2 p2-next;}p1 p1-next;}
}总结
完整代码:https://gitee.com/PYSpring/data-structure/tree/master
