PS: 上一篇说了线性表的顺序表和链式表表达, 该片就写一下应用到现实数学中去, 一元多项式的加减.
一元多项式我们在本子上可以说是手到拈来, 但是在电脑上用语言敲出来, 估计这会让很多人头疼, 比如下面的多项式
- y1 = 9x^1 + 4x^3 + 6x^4
- y2 = 2x^3 + 4x^4 + 3x^7 + 3x^8
- yz = y1 + y2 ;
效果图
思路:
创建一个结构体, 里面只存连个数, 一个是系数 data, 一个是次幂, 至于 x 就不用存了, 只在打印的时候写上就 OK 了,
然后写插入操作, 注意一定要是有序的, 方便在后期相加
两个多项式相加就是合并, 我们可以按照顺序两两比较, 先拿 y1 的第一个数和 y2 第一个比较, 如果 y1>y2, 则把 y2 添加到 yz, 相反之, 如果 y1=y2 则相加系数, 按照 y1(也可 y2) 加入 yz, 等全都比较过后, 如果 y1(y2) 还有项的话, 就把剩下的全都加载到 yz 中, 其实就是直接把 next 指向 y1(y2) 即可.
1: 结构体
定义一个结构体类型
在 SlinkOnez 调用变量是, 都是
L->data;L->next; 的形式
- typedef struct SlinkOne {
- int data;
- int cimi;
- struct SlinkOne *next;
- } SlinkOne, *SlinkOnez;
2: 初始化
- /**c
- * 初始化
- * */
- SlinkOnez initLink() {
- SlinkOnez L = (SlinkOnez) malloc(sizeof(SlinkOne));
- if (!L) {
- exit(-1);
- }
- L->next = NULL;
- return L;
- }
3: 插入操作
- /**
- * 插入
- * */
- int insertLink(SlinkOnez &L, int pos, int e, int cimi) {
- SlinkOnez p = L;
- int i = 0;
- while (p && i <pos-1) {
- p = p->next;
- i++;
- }
- if (!p || i> pos-1) {
- printf("单链表未被创建 \ n");
- return -1;
- }
- // 创建一个新的结点, 并赋值
- SlinkOnez s = (SlinkOnez) malloc(sizeof(SlinkOne));
- s->data = e;
- s->cimi = cimi;
- s->next = p->next;
- p->next = s;
- printf("插入成功 \ n");
- return 0;
- }
- /**
- * 打印全部数据
- * */
- void printL(SlinkOnez L) {
- SlinkOnez p = L->next;
- if (!p) {
- printf("单链表不成立或者为 NULL");
- return;
- }
- while (p) {
- if (p->next == NULL) {
- printf("%dX^%d", p->data, p->cimi);
- } else {
- if (p->cimi == 0) {
- printf("%d +", p->data);
- } else {
- printf("%dX^%d +", p->data, p->cimi);
- }
- }
- p = p->next;
- }
- printf("\n");
- }
- /**
- * 合并
- * */
- SlinkOnez mergeLink(SlinkOnez &Lz, SlinkOnez &L1, SlinkOnez &L2) {
- Lz->next=NULL;
- SlinkOnez pz = Lz;
- SlinkOnez p1 = L1->next;
- SlinkOnez p2 = L2->next;
- while (p1 && p2) {
- if (p1->cimi <p2->cimi) {
- pz->next = p1;
- pz = p1;// 往下走一个
- p1 = p1->next;
- } else if (p1->cimi> p2->cimi) {
- pz->next = p2;
- pz = p2;// 往下走一个
- p2 = p2->next;
- }else{
- if(0 !=(p1->data + p2->data)){
- p1->data = (p1->data+p2->data);// 注意此处, 重点, 不能写成 pz->data, 否则会把当前 p 的值给替换掉, 而不是赋值给下一个指针的值
- pz->next = p1;
- pz = p1;// 往下走一个
- }
- p1=p1->next;
- p2=p2->next;
- }
- }
- if (p1!=NULL){
- pz->next=p1;
- }
- if (p2!=NULL){
- pz->next=p2;
- }
- return Lz;
- }
- int main() {
- // 第一个多项式
- SlinkOnez L;
- L = initLink();
- insertLink(L, 1, 9, 1);
- insertLink(L, 2, 4, 3);
- insertLink(L, 3, 6, 4);
- printL(L);
- // 第二个多项式
- SlinkOnez L2;
- L2 = initLink();
- insertLink(L2, 1, 2, 3);
- insertLink(L2, 2, 4, 4);
- insertLink(L2, 3, 3, 7);
- insertLink(L2, 4, 3, 8);
- printL(L2);
- // 合并后多项式
- SlinkOnez L3;
- L3=initLink();
- L3=mergeLink(L3,L,L2);
- printL(L3);
- return 0;
- }
来源: https://www.cnblogs.com/cmusketeer/p/9741680.html