数据结构-非循环单链表（多项式运算）

非循环单链表

/*coder:cyl   time: 2020.12.1*/

#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE  1000
#define ElemType int
#define Status   int
#define ERROR    -1
#define OK        1
int n;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
} LNode,*LinkList;

Status ListInit_L(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));//头结点申请地址
    if(!L){//if(L==NULL)
        printf("分配内存失败!\n");
        exit(OVERFLOW);
    }
    else
        L->next=NULL;
    return OK;
}

Status ListIn(LinkList &L, int n) {
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;//先建立一个带头结点的单链表
    LinkList p;
    srand(unsigned(time(0)));  //初始化随机数种子
    for(int i=n;i>0;--i)
    {
        p=(LinkList)malloc(sizeof(LNode));
        p->data=rand()%100+1; //随机生成100以内的数字，比scanf()操作简单些
        //插入到表头
        p->next=L->next;
        L->next=p; //将结点p连接在头结点L之后
    }
    return OK;
}

Status ListOut(LinkList L) {
    LinkList p = L->next;
    int k = 0;
    if (!p) {
        printf("这是一个空目录！\n");
        return ERROR;
    }
    printf("单链表:\n");
    while (p) {
        p = p->next;
        k++;
    }
    for (int j = 0; j < k; j++) {
        cout << "[" << j << "]" << "\t";
    }
    cout<<endl;
    p = L->next;
    while (p) {
        cout << p->data;
        if(p->next)cout<<"->\t";
        else cout<<"^";
        p = p->next;
    }
    cout<<endl;
    return OK;
}

Status ListInsert(LinkList &L, int i, ElemType e) {
    LinkList p,s;
    int j=0;
    p=L;
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p||j>i-1){
        cout<<"插入失败"<<endl;
        return ERROR;
    }
    s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    cout<<"插入完成"<<endl;
    return OK;
}

bool ListEmpty(LinkList L) {
    if (L->next==NULL)return true;
    else return false;
}

Status ListLength(LinkList L) {
    LinkList p;
    int k=0;
    p=L->next;
    while(p){
        k++;
        p=p->next;
    }
    return k;
}

Status GetElem(LinkList L, int i, ElemType &e) {
    int j;
    LinkList p;
    p= L->next;
    j=1;
    while(p&&j<i){
        p=p->next;
        j++;
    }
    if(!p||j>i)return ERROR;
    e=p->data;
    return e;
}

Status compare1(ElemType a, ElemType b) {
    if(a==b)return 1;
    else return 0;
}
Status compare2(ElemType a, ElemType b) {
    if(a>b)return 1;
    else return 0;
}
Status compare3(ElemType a, ElemType b) {
    if(a<b)return 1;
    else return 0;
}

Status LocateElem(LinkList L, ElemType e,Status (*compare)(ElemType,ElemType)) {
    LinkList p;
    int k=1;
    p=L->next;
    while(p){
        if(compare(p->data,e)){
            cout<<"第一个满足关系的结点序号是"<<k<<endl;
            return OK;
        }
        p=p->next;
        k++;
    }
    cout << "链表中没有该数据" << endl;
    return ERROR;
}

Status PriorElem(LinkList L, ElemType e, ElemType &pre_e) {
    LinkList p,q;
    q=L->next;
    p=q->next;
    while(p){
        if(p->data==e){
            pre_e=q->data;
            cout<<"元素" << e << "的前驱是:" << pre_e << endl;
            return OK;
        }
        q=p;
        p=q->next;
    }
    cout << "不存在此数据" << endl;
    return ERROR;
}

Status NextElem(LinkList L, ElemType e, ElemType &next_e) {
    LinkList p,q;
    q=L->next;
    p=q->next;
    while(p){
        if(q->data==e){
            next_e=p->data;
            cout<<"元素" << e << "的后驱是:" << next_e << endl;
            return OK;
        }
        q=p;
        p=q->next;
    }
    cout << "不存在此数据" << endl;
    return ERROR;
}

Status DeleteElem(LinkList &L,int i, ElemType &e) {
    LinkList p,q;
    int j=0;
    p=L;
    while(p->next&&j<i-1){
        p=p->next;
        j++;
    }
    if(!p->next||j>i-1)return ERROR;
    q=p->next;
    p->next=q->next;
    e=q->data;
    free(q);
    cout << "删除的元素是" << e << endl;
    return OK;
}

Status ClearList(LinkList &L) {
    L->next=NULL;
    return OK;
}

Status CleanList(LinkList &L){
    LNode *p,*s,*q;
    p=L->next;
    if(!p)    return ERROR;
    while(p->next)
    {
        q=p;
        while(q->next)                //固定p所指结点，向后遍历，寻找与之数据域相同的结点
        {
            if(q->next->data==p->data)    //在这里将q->next所指的结点存放数据与p作比较
            {
                s=q->next;
                q->next=s->next;
                free(s);
            }
            else q=q->next;
        }
        p=p->next;
    }
    return  OK;
}

Status converse(LinkList &L)
{
    LinkList p,q;
    p=L->next;
    L->next=NULL;
    while(p)
    {
        /*向后挪动一个位置*/
        q=p;
        p=p->next;
        /*头插*/
        q->next=L->next;
        L->next=q;
    }
    return OK;
}

Status Menus() {
    cout << "1.在第i个结点之前插入一个结点" << endl;
    cout << "2.判断链表是否为空" << endl;
    cout << "3.求链表中结点的个数" << endl;
    cout << "4.取第i个结点" << endl;
    cout << "5.查找第1个与某结点满足compare（）关系的结点的序号" << endl;
    cout << "6.返回某元素的前驱" << endl;
    cout << "7.返回某元素的后驱" << endl;
    cout << "8.删除第i个结点的数据域" << endl;
    cout << "9.把一个非循环单链表赋值给另一个非循环单链表表" << endl;
    cout << "10.顺序表置空" << endl;
    cout << "11.删除单链表中的重复值" << endl;
    cout << "12.非循环单链表的逆置" << endl;
    cout<<"13.多项式运算"<<endl;
    cout<<"14.随机生成单链表"<<endl;
    cout << "0.结束操作" << endl << endl;
    cout << "请输入你要执行操作的序号：" << endl;
    cin >> n;
    return n;
}

int main() {
    int num, problem;
    LinkList L;
    srand(time(0));
    num=rand()%10+5;
    ListInit_L(L);
    ListIn(L, num);
    ListOut(L);
    cout << endl;
    problem = Menus();
    while (problem != 0) {
        if (problem == 1) {
            int i, e;
            cout << "请输入插入结点的位置:i" << endl;
            cin >> i;
            cout << "请输入插入结点的值:e" << endl;
            cin >> e;
            ListInsert(L, i, e);
            ListOut(L);
        } else if (problem == 2) {
            if (ListEmpty(L))cout << "链表为空" << endl;
            else cout << "链表不为空" << endl << endl;
        } else if (problem == 3) {
            cout << "链表中结点的个数为：" << ListLength(L) << "个" << endl << endl;
        } else if (problem == 4) {
            int i, e;
            cout << "请输入取第结点的序号i" << endl;
            cin >> i;
            cout << "第"<<i<<"个结点为:" << GetElem(L, i, e) << endl << endl;
        } else if (problem == 5) {
            int e,k;
            cout << "请输入你要查找的结点e" << endl;
            cin >> e;
            cout<<"请选择你想要的关系：1（相等） 2（小于你输入的元素） 3（大于你输入的元素）"<<endl;
            cin>>k;
            if(k==1) {
                LocateElem(L, e, compare1);
                cout << endl;
            }
            else if(k==2){
                LocateElem(L, e, compare2);
                cout<<endl;
            }
            else {
                LocateElem(L, e, compare3);
                cout<<endl;
            }
            cout<<endl;
        } else if (problem == 6) {
            cout << "请输入结点数据e" << endl;
            int e, pre_e;
            cin >> e;
            PriorElem(L, e, pre_e);
            cout << endl;
        } else if (problem == 7) {
            cout << "请输入元素e" << endl;
            int e, next_e;
            cin >> e;
            NextElem(L, e, next_e);
            cout << endl;
        } else if (problem == 8) {
            cout << "请输入要删除结点的序号:i" << endl;
            int  i,e;
            cin >> i;
            DeleteElem(L, i,e);
            ListOut(L);
            cout << endl;
        } else if (problem == 9) {
            LinkList M,p,q,s;
            ListInit_L(M);
            q=(LinkList)malloc(sizeof(LNode));
            M->next=q;
            p=L->next;
            while(p){
                if(!p->next){
                    q->data=p->data;
                    p=p->next;
                }
                else {
                    q->data = p->data;
                    p = p->next;
                    s = (LinkList) malloc(sizeof(LNode));
                    q->next = s;
                    q = s;
                }
            }
            cout << "已经将单链表赋值给M单链表，下面打印M单链表" << endl;
            ListOut(M);
            cout << endl;
        } else if (problem == 10) {
            ClearList(L);
            cout << "已经清空，下面打印空表" << endl;
            ListOut(L);
            cout << endl;
        } else if (problem == 11) {
            CleanList(L);
            cout<<"重复值已经删除"<<"打印新的单链表"<<endl;
            ListOut(L);
        }
        else if(problem==12){
            cout<<"逆置单链表成功，打印逆置单链表"<<endl;
            converse(L);
            ListOut(L);
        }
        else if(problem==13){
            system("C:\\Users\\Woftc\\CLionProjects\\untitled22\\cmake-build-debug\\untitled22.exe");
        }
        else if(problem==14){
            srand(time(0));
            num=rand()%10+5;
            ListIn(L,num);
            ListOut(L);
        }
        problem = Menus();
    }
    return 0;
}

多项式运算

#include <stdio.h>
#include <malloc.h>
#include<iostream>
using namespace std;
#define MAX 2000            //多项式最多项数
typedef struct      //定义存放多项式的数组类型
{
    double coef;        //系数
    int exp;            //指数
} PolyArray;

typedef struct pnode    //定义单链表结点类型，保存多项式中的一项，链表构成多项式
{
    double coef;        //系数
    int exp;            //指数
    struct pnode *next;
} PolyNode;

void DispPoly(PolyNode *L)    //输出多项式
{
    bool first=true;        //first为true表示是第一项
    PolyNode *p=L->next;
    while (p!=NULL)
    {
        if (first)
            first=false;
        else if (p->coef>0)
            printf("+");
        if (p->exp==0)
            printf("%g",p->coef);
        else if (p->exp==1)
            printf("%gx",p->coef);
        else
            printf("%gx^%d",p->coef,p->exp);
        p=p->next;
    }
    printf("\n");
}

void DestroyList(PolyNode *&L)    //销毁单链表
{
    PolyNode *p=L,*q=p->next;
    while (q!=NULL)
    {
        free(p);
        p=q;
        q=p->next;
    }
    free(p);
}

void EmptyList(PolyNode *&L)
{
    PolyNode *p=L->next;
    if(p){
        cout<<"多项式不为空"<<endl;
    }
    else{
        cout<<"多项式为空"<<endl;
    }
}

void CreateListR(PolyNode *&L, PolyArray a[], int n) //尾插法建表
{
    PolyNode *s,*r;
    int i;
    L=(PolyNode *)malloc(sizeof(PolyNode));    //创建头结点
    L->next=NULL;
    r=L;                        //r始终指向终端结点,开始时指向头结点
    for (i=0; i<n; i++)
    {
        s=(PolyNode *)malloc(sizeof(PolyNode));//创建新结点
        s->coef=a[i].coef;
        s->exp=a[i].exp;
        r->next=s;                //将*s插入*r之后
        r=s;
    }
    r->next=NULL;                //终端结点next域置为NULL
}

void Sort(PolyNode *&head)        //按exp域递减排序
{
    PolyNode *p=head->next,*q,*r;
    if (p!=NULL)                //若原单链表中有一个或以上的数据结点
    {
        r=p->next;                //r保存*p结点后继结点的指针
        p->next=NULL;            //构造只含一个数据结点的有序表
        p=r;
        while (p!=NULL)
        {
            r=p->next;            //r保存*p结点后继结点的指针
            q=head;
            while (q->next!=NULL && q->next->exp>p->exp)
                q=q->next;        //在有序表中找插入*p的前驱结点*q
            p->next=q->next;    //将*p插入到*q之后
            q->next=p;
            p=r;
        }
    }
}

void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc)  //求两有序集合的并，完成加法
{
    PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;
    double c;
    hc=(PolyNode *)malloc(sizeof(PolyNode));        //创建头结点
    tc=hc;
    while (pa!=NULL && pb!=NULL)
    {
        if (pa->exp>pb->exp)
        {
            s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
            s->exp=pa->exp;
            s->coef=pa->coef;
            tc->next=s;
            tc=s;
            pa=pa->next;
        }
        else if (pa->exp<pb->exp)
        {
            s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
            s->exp=pb->exp;
            s->coef=pb->coef;
            tc->next=s;
            tc=s;
            pb=pb->next;
        }
        else                //pa->exp=pb->exp
        {
            c=pa->coef+pb->coef;
            if (c!=0)        //系数之和不为0时创建新结点
            {
                s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
                s->exp=pa->exp;
                s->coef=c;
                tc->next=s;
                tc=s;
            }
            pa=pa->next;
            pb=pb->next;
        }
    }
    if (pb!=NULL) pa=pb;    //复制余下的结点
    while (pa!=NULL)
    {
        s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
        s->exp=pa->exp;
        s->coef=pa->coef;
        tc->next=s;
        tc=s;
        pa=pa->next;
    }
    tc->next=NULL;
}

void SUB(PolyNode *ha,PolyNode *hb,PolyNode *&hc)  //求两有序集合的并，完成减法
{
    PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;
    double c;
    hc=(PolyNode *)malloc(sizeof(PolyNode));        //创建头结点
    tc=hc;
    while (pa!=NULL && pb!=NULL)
    {
        if (pa->exp>pb->exp)
        {
            s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
            s->exp=pa->exp;
            s->coef=pa->coef;
            tc->next=s;
            tc=s;
            pa=pa->next;
        }
        else if (pa->exp<pb->exp)
        {
            s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
            s->exp=pb->exp;
            s->coef=pb->coef;
            tc->next=s;
            tc=s;
            pb=pb->next;
        }
        else                //pa->exp=pb->exp
        {
            c=pa->coef-pb->coef;
            if (c!=0)        //系数之和不为0时创建新结点
            {
                s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
                s->exp=pa->exp;
                s->coef=c;
                tc->next=s;
                tc=s;
            }
            pa=pa->next;
            pb=pb->next;
        }
    }
    if (pb!=NULL) pa=pb;    //复制余下的结点
    while (pa!=NULL)
    {
        s=(PolyNode *)malloc(sizeof(PolyNode));    //复制结点
        s->exp=pa->exp;
        s->coef=pa->coef;
        tc->next=s;
        tc=s;
        pa=pa->next;
    }
    tc->next=NULL;
}

int Menus(){
    int n;
    cout<<"1.判断多项式是否为空"<<endl;
    cout<<"2.将多项式A赋值给多项式D"<<endl;
    cout<<"3.多项式A+多项式B"<<endl;
    cout<<"4.多项式A-多项式B"<<endl;
    cout<<"5.设置多项式A为空多项式"<<endl;
    cout<<"6.随机生成多项式"<<endl;
    cout<<"0.退出计算"<<endl;
    cout<<"请输入序号："<<endl;
    cin>>n;
    return n;
}
int main()
{
    int problem;
    cout<<"随机生成多项式a,b"<<endl;
    PolyNode *ha,*hb,*hc, *hd,*he ;
    PolyArray a[]= {{1.7,0},{2.9,1},{3.5,4},{-2.5,5}};
    PolyArray b[]= {{-1.2,0},{2.5,1},{3.2,3},{2.5,7},{5.4,10}};
    PolyArray e[]={{5.5,2},{3.7,3},{5.6,6},{8.9,8},{9.5,9},{8.6,10}};
    CreateListR(ha,a,4);
    CreateListR(hb,b,5);
    CreateListR(he,e,6);
    printf("原多项式A:   ");
    DispPoly(ha);
    printf("原多项式B:   ");
    DispPoly(hb);
    Sort(ha);
    Sort(hb);
    printf("有序多项式A: ");
    DispPoly(ha);
    printf("有序多项式B: ");
    DispPoly(hb);
    problem=Menus();
    while(problem){
        if(problem==1){
            EmptyList(ha);
        }
        else if(problem==2){
            hd=(PolyNode *)malloc(sizeof(PolyNode));
            hd->next=NULL;
            PolyNode *p=hd->next,*q=ha->next;
            while(q){
                p=(PolyNode *)malloc(sizeof(PolyNode));
                p->coef=q->coef;
                p->exp=q->exp;
                p=p->next;
                q=q->next;
            }
            cout<<"赋值完成，打印多项式D"<<endl<<endl;
            DispPoly(ha);
        }
        else if(problem==3){
            Add(ha,hb,hc);
            printf("多项式相加:  ");
            DispPoly(hc);
        }
        else if(problem==4){
            SUB(ha,hb,hc);
            printf("多项式相减:  ");
            DispPoly(hc);
        }
        else if(problem==5){
            cout<<"多项式A已经置空，打印多项式A"<<endl;
            ha->next=NULL;
            DispPoly(ha);
        }
        else if(problem==6){
            DispPoly(he);
            cout<<"排序后"<<endl;
            Sort(he);
            DispPoly(he);
        }
        problem=Menus();
    }
    DestroyList(ha);
    DestroyList(hb);
    DestroyList(hc);
    DestroyList(hd);
    return 0;
}