数据布局进修(C++)之单链表

副标题#e#

节点类

#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

【说明】因为数据布局里用到这个布局的处所太多了，假如用《数据布局》那种声明友元的做法，那声明不知道要比这个类的自己长几多。不如开放成员，事实上，这种布局只是C中的struct，除了为了利便初始化一下，不需要任何的要领，原书那是多此一举。下面可以看到，链表的public部门没有返回Node可能Node*的函数，所以，此外类不行能用这个开放的接口对链表中的节点操纵。

【重要修改】原书的缺省结构函数是这样的Node() : data(NULL), link(NULL) {} 。我本来也是照着写的，功效当我做扩充时发明这样是差池的。当Type为布局而不是简朴范例（int、……），不能简朴赋NULL值。这样做使得界说的模板只能用于很少的简朴范例。显然，这里应该挪用Type的缺省结构函数。 这也要求，用在这里的类必然要有缺省结构函数。在下面可以看到结构链表时，利用了这个缺省结构函数。虽然，这里是约定带表头节点的链表，不带头节点的环境请各人本身思考。

【闲话】请不要对int *p = new int(1);这种语法有什么猜疑，实际上int也可以当作一种class。

单链表类界说与实现

#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 &current->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 &current->link->data;
　　　else return NULL;
　　}
　　Type *Next()//移动current到下一个节点，返回节点数据域的地点
　　{
　　　if (current != NULL && current->link != NULL)
　　　{
　　　　prior = current;
　　　　current = current->link;
　　　　return &current->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

#p#分页标题#e#

【说明】我将原书的游标类Iterator的成果放在了链表类中，屏蔽掉了返回值为Node以及Node*范例的接口，这样的链表简朴、实用，扩充机能也很好。

#p#副标题#e#
#p#分页标题#e#

在完成书后功课的时候，我发明白原书做法的长处，也就是我的做法的不敷。假如利用原书的界说，在完成一个成果时，只需要写出对应的函数实现。而在我的界说中，必需先派生一个类，然后把这个成果作为成员可能友元。可是这种较量并不说明书上的界说比我的要公道。首先，利用到原位操纵的环境并不多，书后功课只是一种非凡环境；换句话说，书上的界说只是对完成书后功课更实用些。其次，在利用到链表的时候，凡是只会用到插入、删除、取数据、搜索等很少的几个成果，我的界说足够用了。而在完成一个软件时，对链表的扩充成果在设计阶段就很清晰了，这时可以派生一个新类在整个软件中利用，对整体的筹划更为有利。而对付单个链表的操纵，把它作为成员函数更好领略一些。也就是说我的界说机动性不差。

单链表应用

有人曾经发起最好把链表和链表位置这两个分隔，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;

pa, pb, p 毕竟指向什么？你说这很清楚，ListNode<Term>这样的节点呗。但凭据原书的界说，ListIterator::First()等等函数返回是指向data域的指针，他们怎么能直接赋值？到了下面更乱了，pb指向的区域直接解析出了Term的数据成员，也就是说是指向Term布局的；然后让ListNode<Term>范例的指针p指向这个Term布局，最后，居然把这个布局delete了，天啊，ListNode<Term>这样的节点的data域被delete了！

#p#副标题#e#

在下面将会有些重载运算符的例子，我们的事情将是使多项式的运算看起来更切合书写习惯。完成这些是我以为我擅自将原书的“＋”改成了PolyAdd()，总要给个交待吧。

下面将完成单链表的赋值运算的重载，请把这部门加到List类的public部门。简直，这部门也可以放在多项式类里实现；可是，复制一个多项式实际上就是复制一个单链表，与其单单做一个多项式赋值，还不如完成单链表的赋值，让派生类都能共享。

operator = (const List<Type> &l)
{
　MakeEmpty();
　for (Node<Type> *p = l.first->link; p != NULL; p = p->link) LastInsert(p->data);
}

还记得List类的private内里的这个List(const List<Type> &l)吗？当初怕它惹祸，直接将它禁用了，既然此刻=都能用了，为了这种语法List<Type> b = a;顺便也把它完成了吧。此刻可以把它从private放到public了。

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);
}

终于可以这样写了a = b + c * d

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;
}
#p#分页标题#e#

【跋文】很显然，在“＋”的处理惩罚上我偷懒了，但这是最利便的。乘法部门只要参照手工运算，照旧很简朴的，我就不表明白。对付“－”，可以先完成（－a）这样的算法，然后就可以用加法完成了，而你要是象我一样懒很大概就会做这种事－a＝－1×a，真的不倡导，超低的效率。对付除法，假如你会用汇编写多字节除法（跟手工计较很像），依样画葫芦也能弄出来，但首先要完成“－”。假如要写又得好长，留给你完成吧。到这里你大白原位加法的重要了吧，这些运算实际上都是靠它实现的。