| #ifndef Node_H #define Node_H template <class Type> class Node //单链节点类 { public: Type data; Node<Type> *link; Node() : data(Type()), link(NULL) {} Node(const Type &item) : data(item), link(NULL) {} Node(const Type &item, Node<Type> *p) : data(item), link(p) {} }; #endif |
| #ifndef List_H #define List_H #ifndef TURE #define TURE 1 #endif #ifndef FALSE #define FALSE 0 #endif typedef int BOOL; #include "Node.h" template <class Type> class List //单链表定义 { //基本上无参数的成员函数操作的都是当前节点，即current指的节点 //认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点 public: List() { first = current = last = new Node<Type>; prior = NULL; } ~List() { MakeEmpty(); delete first; } void MakeEmpty() //置空表 { Node<Type> *q; while (first->link != NULL) { q = first->link; first->link = q->link; delete q; } Initialize(); } BOOL IsEmpty() { if (first->link == NULL) { Initialize(); return TURE; } else return FALSE; } int Length() const //计算带表头节点的单链表长度 { Node<Type> *p = first->link; int count = 0; while (p != NULL) { p = p->link; count++; } return count; } Type *Get()//返回当前节点的数据域的地址 { if (current != NULL) return ¤t->data; else return NULL; } BOOL Put(Type const &value)//改变当前节点的data，使其为value { if (current != NULL) { current->data = value; return TURE; } else return FALSE; } Type *GetNext()//返回当前节点的下一个节点的数据域的地址，不改变current { if (current->link != NULL) return ¤t->link->data; else return NULL; } Type *Next()//移动current到下一个节点，返回节点数据域的地址 { if (current != NULL && current->link != NULL) { prior = current; current = current->link; return ¤t->data; } else { return NULL; } } void Insert(const Type &value)//在当前节点的后面插入节点，不改变current { Node<Type> *p = new Node<Type>(value, current->link); current->link = p; } BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior { Node<Type> *p = new Node<Type>(value); if (prior != NULL) { p->link = current; prior->link = p; prior = p; return TURE; } else return FALSE; } BOOL Locate(int i)//移动current到第i个节点 { if (i <= -1) return FALSE; current = first->link; for (int j = 0; current != NULL && j < i; j++, current = current->link) prior = current; if (current != NULL) return TURE; else return FALSE; } void First()//移动current到表头 { current = first; prior = NULL; } void End()//移动current到表尾 { if (last->link != NULL) { for ( ;current->link != NULL; current = current->link) prior = current; last = current; } current = last; } BOOL Find(const Type &value)//移动current到数据等于value的节点 { if (IsEmpty()) return FALSE; for (current = first->link, prior = first; current != NULL && current->data != value; current = current->link) prior = current; if (current != NULL) return TURE; else return FALSE; } BOOL Remove()//删除当前节点，current指向下一个节点，如果current在表尾，执行后current = NULL { if (current != NULL && prior != NULL) { Node<Type> *p = current; prior->link = p->link; current = p->link; delete p; return TURE; } else return FALSE; } BOOL RemoveAfter()//删除当前节点的下一个节点，不改变current { if (current->link != NULL && current != NULL) { Node<Type> *p = current->link; current->link = p->link; delete p; return TURE; } else return FALSE; } friend ostream & operator << (ostream & strm, List<Type> &l) { l.First(); while (l.current->link != NULL) strm << *l.Next() << " " ; strm << endl; l.First(); return strm; } protected: /*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/ void LastInsert(const Type &value) { Node<Type> *p = new Node<Type>(value, last->link); last->link = p; last = p; } void Initialize()//当表为空表时使指针复位 { current = last = first; prior = NULL; } //这部分函数返回类型为Node<Type>指针,是扩展List功能的接口 Node<Type> *pGet() { return current; } Node<Type> *pNext() { prior = current; current = current->link; return current; } Node<Type> *pGetNext() { return current->link; } Node<Type> *pGetFirst() { return first; } Node<Type> *pGetLast() { return last; } Node<Type> *pGetPrior() { return prior; } void PutLast(Node<Type> *p) { last = p; } //这部分插入删除函数不建立或删除节点，是原位操作的接口 void Insert(Node<Type> *p) { p->link = current->link; current->link = p; } void InsertBefore(Node<Type> *p) { p->link = current; prior->link = p; prior = p; } void LastInsert(Node<Type> *p) { p->link = NULL; last->link = p; last = p; } Node<Type> *pRemove() { if (current != NULL && prior != NULL) { Node<Type> *p = current; prior->link = current->link; current = current->link; return p; } else return NULL; } Node<Type> *pRemoveAfter() { if (current->link != NULL && current != NULL) { Node<Type> *p = current->link; current->link = current->link->link; return p; } else return NULL; } private: List(const List<Type> &l); Node<Type> *first, *current, *prior, *last; //尽量不要使用last，如果非要使用先用End()使指针last正确 }; #endif |
【说明】我将原书的游标类Iterator的功能放在了链表类中，屏蔽掉了返回值为Node以及Node*类型的接口，这样的链表简单、实用，扩充性能也很好。
在完成书后作业的时候，我发现了原书做法的好处，也就是我的做法的不足。如果使用原书的定义，在完成一个功能时，只需要写出对应的函数实现。而在我的定义中，必须先派生一个类，然后把这个功能作为成员或者友元。但是这种比较并不说明书上的定义比我的要合理。首先，使用到原位操作的情况并不多，书后作业只是一种特殊情况；换句话说，书上的定义只是对完成书后作业更实用些。其次，在使用到链表的时候，通常只会用到插入、删除、取数据、搜索等很少的几个功能，我的定义足够用了。而在完成一个软件时，对链表的扩充功能在设计阶段就很清晰了，这时可以派生一个新类在整个软件中使用，对整体的规划更为有利。而对于单个链表的操作，把它作为成员函数更好理解一些。也就是说我的定义灵活性不差。
单链表应用
有人曾经建议最好把链表和链表位置这两个分开，C++标准库是这么做的；但对于初学者来说，一个类总比两个类好操作。我不清楚在书中这部分的程序究竟调没调试，但这种语句我是绝对看不懂的：
| ListNode<Term> *pa, *pb, *pc, *p; ListIterator<Term> Aiter(ah.poly); ListIterator<Term> Biter(ah.poly); pa = pc = Aiter.First(); pb = p = Biter.First(); ……………………….. pa->coef = pa->coef + pb->coef; p = pb; pb = Biter.Next(); delete p; |
| #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<Term> { 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<Term> *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 |
下面将完成单链表的赋值运算的重载，请把这部分加到List类的public部分。的确，这部分也可以放在多项式类里实现；但是，复制一个多项式实际上就是复制一个单链表，与其单单做一个多项式赋值，还不如完成单链表的赋值，让派生类都能共享。
| operator = (const List<Type> &l) { MakeEmpty(); for (Node<Type> *p = l.first->link; p != NULL; p = p->link) LastInsert(p->data); } |
| List(const List<Type> &l) { first = current = last = new Node<Type>; prior = NULL; for (Node<Type> *p = l.first->link; p != NULL; p = p->link) LastInsert(p->data); } |
| friend Polynomial operator + (Polynomial &polyA, Polynomial &polyB) { Polynomial tempA = polyA;Polynomial tempB = polyB; PolyAdd(tempA, tempB); return tempA; } friend Polynomial operator * (Polynomial &polyA, Polynomial &polyB) { Node<Term> *pA = polyA.pGetFirst()->link; Node<Term> *pB = polyB.pGetFirst()->link; Polynomial polyTempA, polyTempB; int coef, exp; if (pA == NULL || pB == NULL) return polyTempA; for (pA = polyA.pGetFirst()->link; pA != NULL; pA = pA->link) { for(pB = polyB.pGetFirst()->link; pB != NULL; pB = pB->link) { coef = pA->data.coef * pB->data.coef; exp = pA->data.exp + pB->data.exp; Term term(coef, exp); polyTempB.LastInsert(term); } PolyAdd(polyTempA, polyTempB); polyTempB.Initialize(); } return polyTempA; } |