主要参考书是《数据结构（用面向对象方法与C++描述）》殷人昆等编著，清华大学出版社。原书看起来很费事，显而易见的把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。但是，这是清华的考研参考书目，一定有许多人和我一样在研读此书。我把我重新定义的类和实现发表出来，就是希望和我一样的人，或者是打算学习数据结构而选择了这本书的人，能更好的理解和学习。当然，如果你想使用这些数据结构，又不想学STL，这些类也能帮你达成目的。 我照着原书的类名和对应的函数名，写下了如下的类的定义，部分代码采用了原书的。把成员函数的实现写在类定义里，完全是为了将就VC++6的ClassView，不然一双击一个成员函数，就蹦出来“我找不到它的实现”，而实际上，一般我们都看的是ClassView显示的类的接口，很少去看类的定义。这是第一部分，马上我会完成树等结构。我只测试了int类型各个成员函数的正确性，并且也没做什么“极端测试”，欢迎测试。另外，欢迎反映这样的定义是否好看些，容易懂些。 #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) {}}; #endif说明：因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。 一点重要的修改：原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {}  。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。   下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。 #ifndef List_H#define List_H #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; }  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);  p->link = 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到表尾，同时使last真正指向表尾 {  if (last->link != NULL)  {   for ( ;current->link != NULL; current = current->link)   prior = current;  }   last = 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; } friend ostream & operator << (ostream & strm, List<Type> &l){  l.First();  while (l.current->link != NULL) strm << *l.Next() << " " ;  strm << endl;  return strm;  l.First();} protected: void Initialize()//当表为空表时使指针复位 {  current = last = first;  prior = NULL; }  /*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/  void LastInsert(const Type &value) {  Node<Type> *p = new Node<Type>(value);  last->link = p;  last = p; } //这部分函数返回类型为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; }   private:  List(const List<Type> &l); Node<Type> *first, *current, *prior, *last;//尽量不要使用last，如果非要使用用先用End()确保正确 }; #endif 说明：我在iostream.h加了enum BOOL { FALSE, TURE};如果报告BOOL没有定义，自己加上。protected是功能扩展的接口，实际上，除了完成书上的作业，可能根本用不到这部分。将复制构造函数声明为private，是采用了林锐的方法，防止乱用。写完这个有点感受，就是为什么要加上存取限制：能在编译阶段找出错误总比运行起来莫名其妙的错误解决起来容易。 #ifndef Stack_H#define Stack_H #include "List.h" template <class Type> class Stack : List<Type>//栈类定义{ public: /*私有继承List类的方法 List类初始化时current = first，所以栈顶指针top = current->link； 因此,入栈操作就是在current位置后插一节点； 出栈操作就是先返回current后面元素，然后在current位置后删一节点； 置空栈操作同置空表操作； 判空栈操作同判空表操作；*/  void Push(Type value) {  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: void EnQueue(const Type &value) {  LastInsert(value); }  Type DeQueue() {   //不须执行判空操作，因为连续执行DeQueue时前面必定执行判空，  //而GetNext()和RemoveAfter()没有副作用，顶多返回NULL和FALSE  Type p = *GetNext();  RemoveAfter();  IsEmpty();//出队后如果变成空队要复位last指针  return p; }  Type GetFront() {  return *GetNext(); }  List<Type> ::MakeEmpty;  List<Type> ::IsEmpty;}; #endif 说明：很显然，从链表继承省掉了大量代码和构思，原书虽然想用面向对象的方法描述，但忽视了继承。做了大量重复建设，而且让人理解起来也很艰辛。 只是简单测试了int类型各个函数能否工作，欢迎多提意见。 #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; cout << a; cout << "表长是" << a.Length() << endl; a.Locate(4); a.Remove(); cout << "删除第4个元素后:" << endl; cout << a; a.Find(3); a.Remove(); cout << "删除元素3后:" << endl; cout << a; a.Find(7); cout << "在元素7前插入24后:" << endl; a.InsertBefore(24); cout << a; cout << "在元素9后插入25后:" << endl; a.Find(9); a.Insert(25); cout << a; cout << "第7个元素是:" << endl; a.Locate(7); cout << *a.Get(); cout << "接下来是:" << *a.GetNext() << endl; cout << "删掉它后:" << endl; a.RemoveAfter(); cout << a; cout << "在表尾后面插入元素78" << endl; a.End(); a.Insert(78); cout << a; cout << "置空表后表的内容为" << endl; a.MakeEmpty(); cout << a; 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;}

评论