2020-10-24 将一个双向链多项式分解为两个多项式,一个仅含奇次项,一个仅含偶次项,且利用原来的链表空间

  • 时间:
  • 来源:互联网
  • 文章标签:

题目:
在这里插入图片描述

//将一个双向链多项式分解为两个多项式,一个仅含奇次项,一个仅含偶次项
//且利用原来的链表空间,不能新开辟空间
//为了1024勋章@.@
#include<iostream>
using namespace std;
typedef struct
{
    double coef;
    int exp;
}PElemType;

typedef struct PNode
{
    PElemType data;
    struct PNode* prior,* next;
}PNode,* PLink;

typedef struct
{
    PLink head,tail,tailji;//tailji作为奇次项的尾指针
    int length;
}PLinkList;

bool Init_PLinkList(PLinkList& P)//初始化
{
    P.head=new PNode;
    if(!P.head) return false;
    P.head->next=P.head->prior=nullptr;
    P.tail=P.head;
    P.length=0;
    return true;
}

istream& operator>>(istream& is,PElemType& e)//重载cin>>ElemType(ElemType为结构体类型)
{
    is>>e.coef>>e.exp;
    return is;
}

bool Input_PLinkList(PLinkList& P)//向多项式输入数据
{
    PElemType num;
    PLink p;
    while(cin>>num){
        p=new PNode;
        p->data=num;p->next=nullptr;
        P.tail->next=p;p->prior=P.tail;
        P.tail=p;
        P.length++;
    }
    if(!cin){
        cin.clear();
        cin.sync();
    }
    return true;
}

bool Insert1_Ptr(PLinkList& P,PLink p)//将p尾插到P.head->next带领的偶次项单链表中
{
    P.tail->next=p;
    P.tail=p;
    return true;
}

bool Insert2_Ptr(PLinkList& P,PLink p)//将p尾插到P.head->prior带领的奇次项单链表中
{
    P.tailji->prior=p;//注意p插入到P.tailji->prior之后
    P.tailji=p;
    return true;
}

bool GetTwoPoly(PLinkList& P)//头结点两个指针,想着 P.head带领偶次项 P.prior带领奇次项,弄成两个单链表
//偶次项通过next指针遍历 奇次项通过prior指针遍历
//而原先只有一个尾指针,现定义了一个tailtt指针,该指针是奇次项的尾指针
{
    PLink p=P.head->next,q;
    P.head->next=P.head->prior=nullptr;P.tail=P.tailji=P.head;
    while(p){
        q=p;p=p->next;
        if(q->data.exp%2==0){
            q->prior=q->next=nullptr;//将q指向的结点从原来的链中脱落
            if(!Insert1_Ptr(P,q)) return false;
        }
        else{
            q->next=q->prior=nullptr;//将q指向的结点从原来的链中脱落
            if(!Insert2_Ptr(P,q)) return false;
        }
    }
    return true;
}

void Output_PLinkList(PLinkList P)
{
    cout<<"---"<<endl;
    cout<<"长度:"<<P.length<<endl;
    cout<<"从头遍历\n";
    PLink p=P.head->next;
    while(p){
        cout<<"系数:"<<p->data.coef<<" 指数:"<<p->data.exp<<endl;
        p=p->next;
    }
    cout<<"从尾遍历\n";
    p=P.tail;
    while(p->prior){
        cout<<"系数:"<<p->data.coef<<" 指数:"<<p->data.exp<<endl;
        p=p->prior;
    }
    cout<<endl;
}

void ViewTwoPoly(PLinkList P)//遍历分解后的含两个单链表的P
{
    cout<<"偶次项:\n";
    cout<<"----"<<endl;
    PLink p=P.head->next;
    while(p){
        cout<<"系数:"<<p->data.coef<<" 指数:"<<p->data.exp<<endl;
        p=p->next;
    }
    cout<<"奇次项:\n";
    p=P.head->prior;
    while(p){
        cout<<"系数:"<<p->data.coef<<" 指数:"<<p->data.exp<<endl;
        p=p->prior;
    }
    cout<<"----"<<endl;
}

int main()
{
    PLinkList P;
    Init_PLinkList(P);
    Input_PLinkList(P);
    Output_PLinkList(P);
    GetTwoPoly(P);
    ViewTwoPoly(P);
    return 0;
}

4 -2
3 0
2.2 1
-9.9 3
8.8 4
1 6
-1 9
^Z
---
长度:7
从头遍历
系数:4 指数:-2
系数:3 指数:0
系数:2.2 指数:1
系数:-9.9 指数:3
系数:8.8 指数:4
系数:1 指数:6
系数:-1 指数:9
从尾遍历
系数:-1 指数:9
系数:1 指数:6
系数:8.8 指数:4
系数:-9.9 指数:3
系数:2.2 指数:1
系数:3 指数:0
系数:4 指数:-2

----
偶次项:
系数:4 指数:-2
系数:3 指数:0
系数:8.8 指数:4
系数:1 指数:6
奇次项:
系数:2.2 指数:1
系数:-9.9 指数:3
系数:-1 指数:9
----

Process returned 0 (0x0)   execution time : 1.459 s
Press any key to continue.

本文链接http://www.taodudu.cc/news/show-1782063.html