c19.cpp

数据结构课程设计

#include <stdio.h>
#include <malloc.h>
#include<iostream.h>
#define  OK          0
#define  ERROR      -1
typedef struct{//结点中的数据域结构表示
    float   coef;//系数
    int     expn;//指数
}ElemType;
typedef struct LNode{//结点结构类型
    ElemType         data;//数据域
    struct LNode     *next;//指向下一个结点的指针
}*Link;
typedef struct{//链表类型
    Link  head,tail;//head:表示链表的头接结点，tail: 表示链表的尾结点
    int   len;//链表长度
}LinkList,polynomial;
class TString {
public:
	int InitList(LinkList &L);//构造空的线性链表
	bool ClearList(LinkList &L);//清空线性表L，只剩头结点
	int ListLength(LinkList L);//返回链表的长度
    void CreatPolyn(polynomial &P);//建立多项式
    void SortPolyn(polynomial &P);//先合并指数相同项，再删除系数为零的项，最后按指数由小到大排序
    void AddPolyn(polynomial &Pa,polynomial &Pb);//多项式加法
    void SubPolyn(polynomial &Pa,polynomial &Pb);//多项式减法
    void MulPolyn(polynomial &Pa,polynomial &Pb);//多项式乘法
};
int TString::InitList(LinkList &L){//构造空的线性链表
    L.head=(LNode *)malloc(sizeof(LNode));
    if(!L.head)
  return ERROR;
    else 
  L.head->next=NULL;
 return OK;
}
bool TString::ClearList(LinkList &L){//清空线性表L，只剩头结点
    while(L.head->next){
        Link p=L.head->next;
        L.head->next=p->next;
        free(p);
    }
    L.head->next=NULL;
    return OK;
}
int TString::ListLength(LinkList L){//返回链表的长度
    Link p=L.head->next;
      int k=0;
      while(p){
        k++;
        p=p->next;
      }
      return k;
}
void TString::CreatPolyn(polynomial &P){//建立多项式
    ElemType e;Link h,p;
    InitList(P);h=P.head;
    P.len=ListLength(P);
    P.tail=P.head;//找P的tail
    while(P.tail->next){
        P.tail=P.tail->next;
    }
    P.tail->next=NULL;
    e.coef=0;e.expn=-1;h->data=e;//设置头结点的数据元素
label1:    while(1){
        cin>>e.coef>>e.expn;
        if(e.coef==0){P.tail->next=NULL;break;}//如果系数为0输入结束
        p=(LNode *)malloc(sizeof(LNode));
        p->data=e;
        p->next=NULL;
        P.tail->next=p;//生成结点并插入链表
        P.tail=p;
        P.len++;
    }
    if(P.head->next==NULL){
        cout<<"多项式为空,请重新输入!"<<endl;
        goto label1;
    }
}
void TString::SortPolyn(polynomial &P)
{
 Link p1,p2,q1,q2;
    p1=P.head->next;
    if(p1){//如果P不为空
    q1=p1;
    q2=q1->next;
    while(p1->next&&p1->next->next){//合并指数相同项
        while(q2){
            if(p1->data.expn==q2->data.expn){
                p1->data.coef+=q2->data.coef;
                q1->next=q2->next;
                free(q2);
                }
            else{q1=q1->next;}
            q2=q1->next;
        }
        p1=p1->next;q1=p1;q2=q1->next;
    }//while
    if(p1->next){
        if(p1->data.expn==q2->data.expn){
            p1->data.coef+=q2->data.coef;
            p1->next=NULL;
            free(q2);
        }
        else{q2->next=NULL;}
    }
    else{p1->next=NULL;}
    p1=P.head;p2=p1->next;//删除系数为零的项
    while(p2){
        if(p2->data.coef==0){
            p1->next=p2->next;free(p2);
            p2=p1->next;
        }
        else{p1=p1->next;p2=p1->next;}
    }
    Link p3;
    p3=(LNode *)malloc(sizeof(LNode));
    for(int i=ListLength(P);i>1;i--){//按指数由小到大排序
        p1=P.head->next;p2=p1->next;
        for(int j=1;j<i;j++){
            if(p1->data.expn>p2->data.expn){
            p3->data=p2->data;
            p2->data=p1->data;
            p1->data=p3->data;
            }
        p1=p1->next;
        p2=p1->next;
        }
    }
    }//第一个if
    else P.head->next=NULL;
}
void TString::AddPolyn(polynomial &Pa,polynomial &Pb){//多项式加法
    Pa.tail=Pa.head;
    while(Pa.tail->next){
        Pa.tail=Pa.tail->next;
    }
    Pa.tail->next=Pb.head->next;//将pb头接到pa尾
    SortPolyn(Pa);
}
void TString::SubPolyn(polynomial &Pa,polynomial &Pb){//多项式减法
    Pa.tail=Pa.head;Link p;
    if(Pb.head->next){//如果Pb不空
        for(p=Pb.head->next;p;p=p->next){
        p->data.coef=-p->data.coef;//Pb各项加负号
        }
    while(Pa.tail->next){
        Pa.tail=Pa.tail->next;
    }
    Pa.tail->next=NULL;
    }//if
    else{//如果Pb空
        Pb.head->next=NULL;
    }
    Pa.tail->next=Pb.head->next;//将pb头接到pa尾
    SortPolyn(Pa);
}
void TString::MulPolyn(polynomial &Pa,polynomial &Pb){//多项式乘法
    polynomial Pc;Link p1,p2,p3,p;
    InitList(Pc);
    p3=Pc.head;
    for(p1=Pa.head->next;p1;p1=p1->next){//将Pa,Pb乘积放Pc中
        for(p2=Pb.head->next;p2;p2=p2->next){
            p=(LNode *)malloc(sizeof(LNode));
            p->data.coef=p1->data.coef*p2->data.coef;
            p->data.expn=p1->data.expn+p2->data.expn;
            p3->next=p;
            p3=p3->next;
        }
    }
    p3->next=NULL;
    ClearList(Pa);free(Pa.head);
    ClearList(Pb);free(Pb.head);
    Pa.head=Pc.head;//令Pa指向Pc
    SortPolyn(Pa);
}//MulPolyn
void PrintPolyn(polynomial P){//打印多项式
    Link q=P.head->next;
    if(q){//如果P不为空
        while(q&&q->next){
        cout<<q->data.coef<<"X^"<<q->data.expn<<"+";
        q=q->next;
        }
        cout<<q->data.coef<<"X^"<<q->data.expn;//末项输出
    }
    else cout<<endl;//如果P为空
}//PrintPolyn
void  optrea(){
	LinkList pa,pb;
    char a;
    cout<<"选择相加输入\"+\",相减输入\"-\",相乘输入\"*\""<<endl;
label2: cin>>a;
        if(a!='+'&&a!='-'&&a!='*'){
        cout<<"运算符错误!重新输入"<<endl;
        goto label2;
		}
		cout<<"输入多项式A"<<endl;
		TString string;
        string.CreatPolyn(pa);
        cout<<"A=";
		string.SortPolyn(pa);
		PrintPolyn(pa);
		cout<<endl;
        cout<<"输入多项式B"<<endl;
        string.CreatPolyn(pb);
        cout<<"B=";string.SortPolyn(pb);PrintPolyn(pb);cout<<endl;
        switch(a){//选择多项式的运算
		case '+':
			string.AddPolyn(pa,pb);
            printf("A+B=");
            PrintPolyn(pa);
            cout<<endl;
            break;
        case '-':
            string.SubPolyn(pa,pb);
            printf("A-B=");
            PrintPolyn(pa);
			cout<<endl;
            break;
        case '*':
            string.MulPolyn(pa,pb);
            printf("A*B=");
            PrintPolyn(pa);
            cout<<endl;
            break;
    }
}
void main(){
	optrea();
}