抽象类,就是有纯虚函数的类,一般做为基类用,
摸板还不会用!!!
差点把你忘了...
例如~~~~~~~
#include "String.h" template <class T> class BaseObject { public: virtual T Add(T A, T B) = 0; }; template <class T> class MyInt : public BaseObject<T> { public: T Add(T A, T B) { return A+B; } }; void main() { MyInt <int> m_myInt; int nCount = m_myInt.Add(2, 3); cout<<nCount<<endl; }
但是复杂点,就不知道怎样实例化了~~~~~~~~
例如~~~~~~~
#include "String.h" template <class T> class BaseObject { public: virtual T Add(T A, T B) = 0; }; template <class T> class MyInt : public BaseObject<T> { public: T Add(T A, T B) { return A+B; } }; void main() { MyInt <int> m_myInt; int nCount = m_myInt.Add(2, 3); cout<<nCount<<endl; }
但是复杂点,就不知道怎样实例化了~~~~~~~~
这个例子好,简单易懂,偶喜欢~
主要参考书是《数据结构(用面向对象方法与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; }