您的位置: 首页  >  IT文章  >  单链表实现多项式相加~求指教,该怎么处理

单链表实现多项式相加~求指教,该怎么处理

分类: IT文章 • 2023-12-21 20:48:01
单链表实现多项式相加~求指教
#include<stdio.h>
#include<malloc.h>
#include<process.h> // exit()
#define ERROR 0
#define OVERFLOW -2


typedef struct LNode{
  float coef; // 系数 
  int expn; // 指数 
  struct LNode *next;
}*LinkList;


void InitList(LinkList &L)
{ // 操作结果：构造一个空的线性表L
  L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
  if(!L) // 存储分配失败
  exit(OVERFLOW);
  L->next=NULL; // 指针域为空
}


typedef LinkList Polyn;

void CreatePolyn(Polyn &P,int m){
//InitList(P);
LinkList s=P,L;
P->coef=0.0; P->expn=-1;
for(int i=1;i<=m;i++){
L=(LinkList)malloc(sizeof(LNode)); // 生成新结点
scanf("%f,%d",&L->coef,&L->expn);
s->next=L;
s=s->next;
}
s->next=NULL;
}

int compare(Polyn p1,Polyn p2){
if(p1->expn < p2->expn)
return -1;
else
return (p1->expn > p2->expn?
1:0);
}

void ListDelete(LinkList &L,int i) // 算法2.10。不改变L
 { // 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值
  int j=0;
  LinkList p=L,q;
  while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋
  {
  p=p->next;
  j++;
  }
  if(!p->next||j>i-1) // 删除位置不合理
  exit(ERROR);
  q=p->next; // 删除并释放结点
  p->next=q->next;
  free(q);
}

 void ListTraverse(LinkList L)
 // vi的形参类型为ElemType，与bo2-1.cpp中相应函数的形参类型ElemType&不同
{ // 初始条件：线性表L已存在
  // 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败
  LinkList p=L->next;
  while(p)
  {
printf("%f*x^%d",L->coef,L->expn);
while(p->next)
printf("+");
p=p->next;
  printf("\n");
}
}


void AddPolyn(Polyn &P1,Polyn &P2){
LinkList h1,h2,q1,q2;
h1=P1,h2=P2; //h1,h2分别为指向P1,P2的头节点
q1=h1->next; q2=h2->next; //q1,q2分别指向P1,P2的当前节点

for(int i=1; q1 && q2 ;i++){
switch(compare(q1,q2)){
case -1:
q1=q1->next;
break;
case 0:
q1->coef += q2->coef;
q2=q2->next;
if(!q1->coef)
ListDelete(P1,i);
break;
case 1:
h2->next=q2->next;
h1->next=q2;
q2->next=q1;
q2=h2->next;
break;
}//switch
}//for
if(q2)
q1->next=q2;
free(P2);
}




void main()
{
Polyn P1,P2;
int m,n;
InitList(P1);
InitList(P2);

//创建两个多项式的链表
printf("输入m项的系数及指数\n");
printf("m=");
scanf("%d",&m);
CreatePolyn(P1,m);
printf("P1=");
ListTraverse(P1);

/* printf("输入n项的系数及指数\n");
printf("n=");
scanf("%d",&n);
CreatePolyn(P2,m);
printf("P2=");
ListTraverse(P2);
*/
//实现多项式相加
AddPolyn(P1,P2);
printf("P1+P2=");
ListTraverse(P1);
}

------解决方案--------------------
给你一个我很早时候写的
C/C++ code

#ifndef LINKLIST_H
#define LINKLIST_H

/******************* 线性表的单链表存储结构 ********************/

template <typename ElemType> class LinkList;

template <typename ElemType> class LNode  // 结点类
{
    friend class LinkList<ElemType>;
protected:
    ElemType data;  // 数据域
    LNode<ElemType> *next;  // 指针域

public:
    LNode<ElemType>() { }
    LNode<ElemType>(const ElemType &dt, LNode *nx) { data = dt; next = nx; }
    ~LNode<ElemType>() { }
    ElemType GetData() const { return data; }
    LNode *GetNext() const { return next; }
    void SetData(const ElemType &dt) { data = dt; }
    void SetNext(LNode *nx) { next = nx; }
};

template <typename ElemType> class LinkList
{
protected:
    LNode<ElemType> *head;  // 头指针

public:
    LinkList<ElemType>() { InitList(); }
    LinkList<ElemType>(const LinkList<ElemType> &list);  // 拷贝构造函数
    ~LinkList<ElemType>() { DestroyList(); }
    LNode<ElemType> *GetHead() const { return head; }
    void SetHead(LNode<ElemType> *ph) { head = ph; }
    void InitList();  // 构造一个空的单链表
    void DestroyList();  // 销毁单链表
    void ClearList();  // 将单链表置空
    bool ListEmpty() const { return (head->next == NULL); }  // 探空
    int ListLength() const;  // 返回单链表中数据元素的个数
    bool GetElem(int i, ElemType &e);  // 用e返回单链表第i个元素的值（算法2.8）
    int LocateElem(const ElemType &e);  // 返回单链表中第1个与e相等的值所在的位置
    bool PriorElem(const ElemType &cur, ElemType &pre);  // 用pre返回cur的前驱
    bool NextElem(const ElemType &cur, ElemType &nxt);  // 用nxt返回cur的后继
    bool ListInsert(int i, const ElemType &e);  // 插入（算法2.9）
    bool ListDelete(int i, ElemType *e = NULL);  // 删除（算法2.10）
    void ListTraverse(void (*visit)(const ElemType &e));  // 遍历
};

// 构造一个空的单链表
template <typename ElemType> void LinkList<ElemType>::InitList()
{
    head = new LNode<ElemType>;
    head->next = NULL;
}

// 销毁单链表
template <typename ElemType> void LinkList<ElemType>::DestroyList()
{
    LNode<ElemType> *p = head, *q;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        delete q;
    }
}

// 拷贝构造函数
template <typename ElemType>
LinkList<ElemType>::LinkList<ElemType>(const LinkList<ElemType> &list)
{
    LNode<ElemType> *pt, *pl, *pn;
    this->head = new LNode<ElemType>;
    this->head->next = NULL;
    pt = this->head;
    for (pl = list.head->next; pl != NULL; pl = pl->next)
    {
        pn = new LNode<ElemType>(pl->data, NULL);
        pt->next = pn;
        pt = pn;
    }
}

 // 将单链表置空
template <typename ElemType> void LinkList<ElemType>::ClearList()
{
    LNode<ElemType> *p = head->next, *q;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        delete q;
    }
    head->next = NULL;
}

// 返回单链表中数据元素的个数
template <typename ElemType> int LinkList<ElemType>::ListLength() const
{
    int length = 0;
    LNode<ElemType> *p;
    for (p = head->next; p != NULL; p = p->next)
        ++length;
    return length;
}

// 返回单链表中第1个与e相等的值所在的位置
template <typename ElemType>
int LinkList<ElemType>::LocateElem(const ElemType &e)
{
    int cnt = 0;
    LNode<ElemType> *p;
    for (p = head->next; p != NULL; p = p->next)
    {
        if (p->data == e)
            return cnt;
        else
            ++cnt;
    }
    return -1;
}

// 用pre返回cur的前驱
template <typename ElemType>
bool LinkList<ElemType>::PriorElem(const ElemType &cur, ElemType &pre)
{
    LNode<ElemType> *p;
    for (p = head; p->next != NULL; p = p->next)
    {
        if (p->next->data == cur)
        {
            if (p != head)
            {
                pre = p->data;
                return true;
            }
            else
                return false;
        }
    }
    return false;
}

// 用next返回cur的后继
template <typename ElemType>
bool LinkList<ElemType>::NextElem(const ElemType &cur, ElemType &nxt)
{
    LNode<ElemType> *p;
    for (p = head->next; p->next != NULL; p = p->next)
    {
        if (p->data == cur)
        {
            if (p != head)
            {
                nxt = p->next->data;
                return true;
            }
            else
                return false;
        }
    }
    return false;
}

template <typename ElemType>
void LinkList<ElemType>::ListTraverse(void (*visit)(const ElemType &e))
{
    LNode<ElemType> *p;
    for (p = head->next; p != NULL; p = p->next)
        visit(p->data);
}

// 算法2.8
// 用e返回单链表第i个元素的值
// 当第i元素存在时，其值赋给e，并返回true，否则返回false
template <typename ElemType>
bool LinkList<ElemType>::GetElem(int i, ElemType &e)
{
    int cnt = 0;
    LNode<ElemType> *p = head->next;  // 指向第1个结点
    while (p != NULL && cnt < i)
    {
        p = p->next;
        ++cnt;
    }
    if (p == NULL || cnt > i)  // 第i个元素不存在
        return false;
    e = p->data;  // 取第i个元素
    return true;
}

// 算法2.9
// 在带头结点的单链表中第i个元素之前插入元素e
// i的合法值为1 <= i <= length+1
template <typename ElemType>
bool LinkList<ElemType>::ListInsert(int i, const ElemType &e)
{
    LNode<ElemType> *p = head, *q;
    int j = -1;
    while (p != NULL && j < i - 1)  // 寻找第i-1个结点
    {
        p = p->next;
        ++j;
    }
    if (p == NULL || j > i - 1)  // i小于1或者大于表长加1
        return false;
    q = new LNode<ElemType>(e, p->next);  // 生成新结点
    p->next = q;  // 插入链表中
    return true;
}

// 算法2.10
// 在带头结点的单链表中，删除第i个元素之前元素，并由pe返回其值
// i的合法值为1 <= i <= length
template <typename ElemType>
bool LinkList<ElemType>::ListDelete(int i, ElemType *pe)
{
    LNode<ElemType> *p = head, *q;
    int j = -1;
    while (p->next != NULL && j < i - 1)  // 寻找第i个结点，并令p指向其前驱
    {
        p = p->next;
        ++j;
    }
    if (p->next == NULL || j > i - 1)  // 删除位置不合理
        return false;
    q = p->next;
    if (pe != NULL)
        *pe = q->data;
    p->next = q->next;  // 删除结点
    delete q;  // 释放结点
    return true;
}

#endif

相关推荐