主要参考书是《数据结构(用面向对象方法与C++描述)》殷人昆等编著，清华大学出版社
说句心里话，这本书不好，但是没办法，清华把这本书作为考研参考书，去年因此败下阵来……所以，发奋苦读中。写到这，大家就会很清楚了，我是个C++的初学者，只是有点C的底子。请诸位高手不吝指正，如果你也和我一样不得不学这本书，大家一起共勉。现在刚刚修订完链表、栈、队列，书里写的真是很让人费解，错误也有一些，开始看的时候，没觉得什么，一敲进机器才知道哪错了。这方面我就不多说了。只做了这几个类，是因为这几个最常用。顺序表事实上直接操作数组更直接也更方便；而栈更应该用链式结构，应为禁止随即存取，顺序栈的容量定死的致命缺点换来的只是省了指针域的空间；顺序结构的循环队列不仅操作复杂，容量也是死的，相对而言链式队列更常用。我照着原书的类名和对应的函数名，写下了如下的类的定义，部分代码采用了原书的。把成员函数的实现写在类定义里，完全是为了将就VC++6的ClassView，不然一双击一个成员函数，就蹦出来“我找不到它的实现”，而实际上，一般我们都看的是ClassView显示的类的接口，很少去看类的定义。我只测试了int类型各个成员函数的正确性，并且也没做什么“极端测试”，欢迎测试。另外，欢迎反映这样的定义是否好看些，容易懂些。真是很奇怪，我粘贴过来后，原来那些缩进都不见了，希望不会影响大家的阅读。
////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef Node_H #define Node_H template <class Type> class Node//单链节点类 { public: Type data; Node<Type> *link; Node() : data(NULL), link(NULL) {} Node(const Type &item) : data(item), link(NULL) {} };
#endif
#ifndef List_H #define List_H
#include "Node.h"
enum BOOL { FALSE, TURE};
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 Initialize() { current = last = first; prior = NULL; }
void MakeEmpty()//置空表 { Node<Type> *q; while (first->link != NULL) { q = first->link; first->link = q->link; delete q; } current = first; }
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; }
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; } }
BOOL Insert(const Type &value)//在当前节点的后面插入节点，不改变current { Node<Type> *p = new Node<Type>(value); if (p != NULL) { p->link = current->link; current->link = p; return TURE; } else return FALSE; }
BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior { Node<Type> *p = new Node<Type>(value); if (p != NULL && 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; }
}
BOOL Find(const Type &value)//移动current到数据等于value的节点 { for (current = 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; }
void Travel() { //由于使用了cout，在不支持cout的情况下请改写 First(); while (current->link != NULL) cout << *Next() << " " ; cout << endl; First(); }
protected: /*为了高效的入队算法所添加的 因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last 所以这个算法如果在public里除非不使用这些，否则不正确 但是last除了在队列中有用外，其他的时候没什么用 没有必要为了这个用途而降低Insert()，Remove()的效率 所以把这部分放到protected，实际上只是为了给队列继承*/ BOOL LastInsert(const Type &value) { Node<Type> *p = new Node<Type>(value); if (p != NULL) { last->link = p; last = p; return TURE; } else return FALSE; }
private: Node<Type> *first, *current, *prior, *last;//不要使用last，如果非要使用用End()定位代替 };
#endif
////////////////////////////////////////////////////////////////////////////////////////////////
template <class Type> class Stack : List<Type> { public: /*私有继承List类的方法 List类初始化时current = first，所以栈顶指针top = current->link； 因此,入栈操作就是在current位置后插一节点； 出栈操作就是先返回current后面元素，然后在current位置后删一节点； 置空栈操作同置空表操作； 判空栈操作同判空表操作；*/
BOOL Push(Type value) { return Insert(value); }
Type Pop() { //不须执行判空操作，因为连续执行Pop时前面必定执行判空， //而GetNext()和RemoveAfter()没有副作用，顶多返回NULL和FALSE Type p = *GetNext(); RemoveAfter(); return p; }
Type GetTop() { return *GetNext(); }
List<Type> ::MakeEmpty;
List<Type> ::IsEmpty;
};
#endif
////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef Queue_H #define Queue_H #include "List.h"
template <class Type> class Queue : List<Type> { /* 私有继承List类的方法，初始化时current = first 因此，队列的头指针指向current->link，尾指针为last 入队时，执行LastInsert()，连带修改last，只在这里使用，这个算法就是正确的 出队时，先返回current后面的元素，然后删除current后面的节点*/ public: BOOL EnQueue(const Type &value) { return LastInsert(value); }
Type DeQueue() { //不须执行判空操作，因为连续执行DeQueue时前面必定执行判空， //而GetNext()和RemoveAfter()没有副作用，顶多返回NULL和FALSE Type p = *GetNext(); if (!RemoveAfter()) Initialize(); return p; }
Type GetFront() { return *GetNext(); }
List<Type> ::MakeEmpty;
List<Type> ::IsEmpty; };
#endif
////////////////////////////////////////////////////////////////////////////////////////////////
测试程序 #include <iostream.h> #include "List.h" #include "Stack.h" #include "Queue.h" void ListTest(); void StackTest(); void QueueTest();
void main() { ListTest(); StackTest(); QueueTest(); }
void ListTest() { cout << "链表测试" << endl; cout << "下面构造一个链表" << endl; List<int> a; cout << "链表是空的吗?" << a.IsEmpty() << endl; cout << "执行后插入操作" << endl; for (int i = 0; i < 20; i++) a.Insert(i); cout << "链表当前内容:" << endl; a.Travel(); cout << "表长是" << a.Length() << endl; a.Locate(4); a.Remove(); cout << "删除第4个元素后:" << endl; a.Travel(); a.Find(3); a.Remove(); cout << "删除元素3后:" << endl; a.Travel(); a.Find(7); cout << "在元素7前插入24后:" << endl; a.InsertBefore(24); a.Travel(); cout << "在元素9后插入25后:" << endl; a.Find(9); a.Insert(25); a.Travel(); cout << "第7个元素是:" << endl; a.Locate(7); cout << *a.Get(); cout << "接下来是:" << *a.GetNext() << endl; cout << "删掉它后:" << endl; a.RemoveAfter(); a.Travel(); cout << "在表尾后面插入元素78" << endl; a.End(); a.Insert(78); a.Travel(); cout << "置空表后表的内容为" << endl; a.MakeEmpty(); a.Travel(); cout << endl; }
void StackTest() { cout << "栈测试" << endl; cout << "下面构造一个栈" << endl; Stack<int> a; cout << "栈现在是空的吗?" << a.IsEmpty() << endl; cout << "将0～19入栈" << endl; for (int i = 0; i < 20; i++) a.Push(i); cout << "栈现在是空的吗?" << a.IsEmpty() << endl; cout << "全部出栈" << endl; while (!a.IsEmpty()) cout << a.Pop() << " "; cout << endl; cout << "栈现在是空的吗?" << a.IsEmpty() << endl; cout << "将0～19入栈" << endl; for (i = 0; i < 20; i++) a.Push(i); cout << "栈顶元素是：" << a.GetTop() << endl; cout << "置空栈" << endl; a.MakeEmpty(); cout << "栈现在是空的吗?" << a.IsEmpty() << endl; cout << endl; }
void QueueTest() { cout << "队列测试" << endl; cout << "从下面构造一个队列" << endl; Queue<int> a; cout << "队列现在是空的吗?" << a.IsEmpty() << endl; cout << "将0～19入队" << endl; for (int i = 0; i < 20; i++) a.EnQueue(i); cout << "队列现在是空的吗?" << a.IsEmpty() << endl; cout << "全部出队" << endl; while (!a.IsEmpty()) cout << a.DeQueue() << " "; cout << endl; cout << "队列现在是空的吗?" << a.IsEmpty() << endl; cout << "将0～19入队" << endl; for (i = 0; i < 20; i++) a.EnQueue(i); cout << "队头元素是：" << a.GetFront() << endl; cout << "置空队" << endl; a.MakeEmpty(); cout << "队列现在是空的吗?" << a.IsEmpty() << endl; }
////////////////////////////////////////////////////////////////////////////////////////////////
为了完成教科书上的题目，也为了灵活性，加入这部分接口，这样，书上所有题目都可以不涉及Node内部结构完成了。一般的链表操作是不会用到这些的，如果需要这些接口时，可以派生一个新类，在派生类中完成新的功能。如果需要同时操作两个派生类实例的保护接口，可以声明这个操作为友元。 protected: //这部分函数返回类型为Node<Type>指针,是扩展List功能的接口 Node<Type> *pGet() { return current; } Node<Type> *pNext() { current = current->link; return current; }
Node<Type> *pGetNext() { return current->link; } //这部分插入删除函数不建立或删除节点，是原位操作的接口 void Insert(Node<Type> *p) { p->link = current->link; current->link = p; }
void InsertBefore(Node<Type> *p) { p->link = current; prior->link = p; piror = 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; }
