ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——单链表应用(一元多项式【1】) (转)

数据结构学习(C++)——单链表应用(一元多项式【1】) (转)

原创 IT综合 作者:amyz 时间:2007-11-07 17:51:52 0 删除 编辑
数据结构学习(C++)——单链表应用(一元多项式【1】) (转)[@more@]

总算到了这里,这时,你会很得意的说,辛辛苦苦学的单链表总算知道能干点什么了。但是很不幸,如果你和我一样看的是那本书,到这里,你可能比学双向链表时还要痛苦。如果你是按照书上的介绍一步一步做到这里,你能把书上的多项式加法函数调试出来,我对你致以十二分的敬意。XML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

说到这里,我想起来我发单链表的时候,有人给我建议说:最好把链表和链表位置这两个分开。没错,C++标准库是这么做的,而我也不是什么专家,也不能证明什么优劣;但是,对于初学者来说,一个类总比两个类好操作。我不清楚原书这部分的程序究竟调没调试,但这种语句我是绝对看不懂的:

ListNode *pa, *pb, *pc, *p;

ListIterator Aiter(ah.poly);

ListIterator Biter(ah.poly);

pa = pc = Aiter.First(); pb = p = Biter.First();

………………………..

pa->coef = pa->coef + pb->coef;

p = pb; pb = Biter.Next(); delete p;

如果你没有原书,我来解释一下。pa, pb, p 究竟指向什么?你说这很清楚,ListNode这样的节点呗。但按照原书的定义,ListIterator::First()等等函数返回是指向data域的指针,他们怎么能直接赋值?到了下面更乱了,pb指向的区域直接分解出了Term的数据成员,也就是说是指向Term结构的;然后让ListNode类型的指针p指向这个Term结构,最后,居然把这个结构delete了,天啊,ListNode这样的节点的data域被delete了!

如果从基本的节点操作入手,谁也不会弄的这么乱。但正因为又多了一个类,很多事就疏忽了。所以,我并不怀疑标准库的做法,只是对于初学者,同一时间最好只对一个类操作。我以我的定义为基础,重新完成了这段程序。我并不欣赏原位操作的多项式加法(+),PolyA+PolyB,然后B就嗖的一下没了,A就多了一堆(也可能少了一堆);你作intJ+intK的时候怎么没见J和K有什么变化。与其这样,重载“+”还不如写成PolyA.Add(PolyB)或者PolyAdd(PolyA,PolyB)。

一元多项式类定义与实现

#ifndef Polynomial_H

#define Polynomial_H

 

#include "List.h"

 

class Term

{

public:

  int coef;

  int exp;

  Term() : coef(0), exp(0) {}

  Term(int c, int e) : coef(c), exp(e) {}

  Term(int c) : coef(c), exp(0) {}

};

 

class Polynomial : List

{

public:

  void Input()

  {

  cout << endl << "输入多项式的各项系数和指数";

  cout << endl << "注意:请按降序输入各项,输入系数0表示结束" << endl;

  int coef, exp;

  for(int i = 1; ; i++)

  {

    cout << "第" << i << "项的系数:";

    cin >> coef;

  if (coef)

  {

    cout << "指数:";

    cin >> exp;

    TeRM term(coef, exp);

    Insert(term);

  }

    else break;

  }

  }

 

  void Print()

  {

  cout << endl;

    First();

  if (!IsEmpty())

  {

    Term *p = Next();

    cout << p->coef;

  if (p->exp)

  {

    cout << "x";

    if (p->exp != 1) cout << "^" << p->exp;

  }

 

    while (Next() != NULL)

  {

    p = Get();

    if (p->coef > 0) cout << "+";

    cout << p->coef;

    if (p->exp)

    {

    cout << "x";

    if (p->exp != 1) cout << "^" << p->exp;

    }

  }

  }

  cout << endl;

  }

 

 

 

friend void PolyAdd (Polynomial &polyA, Polynomial &polyB)

{

  Node *pA, *pB;

  polyA.First();polyB.First();

  pA = polyA.pNext();pB = polyB.pNext();

 

  while (pA != NULL && pB !=NULL)

  {

  if (pA->data.exp == pB->data.exp)

  {

    pA->data.coef = pA->data.coef + pB->data.coef;

    polyB.Remove();

  if (!pA->data.coef) polyA.Remove();

    else polyA.pNext();

  }

 

  else

  {

  if (pA->data.exp > pB->data.exp)

  {

    polyB.pRemove();

    polyA.InsertBefore(pB);

  }

 

    else if (pA->data.exp < pB->data.exp) polyA.pNext(); 

  }

  pA = polyA.pGet();pB = polyB.pGet();

  }

 

  if (pA == NULL)

  {

    polyA.pGetPrior()->link = pB;

    polyB.pGetPrior()->link = NULL;

  }

 

 

};

 

#endif

【说明】对于多项式,通常我们都是降序书写的,于是我就要求降序输入。但是对于做加法来说,确实升序的要方便一些,于是,实际上到了内部,就变成升序的了。对于输出格式(从C的时候我就不喜欢做这个),尽量照顾习惯,但是当非常数项系数为1的时候还是会输出系数的,我实在不想把一个实际应用中根本拿不出台的输出函数搞的很复杂。为我编起来方便,输出变成了升序的,请多包含。测试程序就不给了,很简单。在续篇中,我将完成一元多项式“+”“-”“×”“=”的重载——为什么没有“÷”,这种运算我拿笔算都不麻利,编起来就更闹心了,我还清楚的记得拿汇编写多字节除法程序时的痛苦。到了下一篇,你就可以这样写了a=b+c*d;a.Print();


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-981198/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7338477