数据结构算法集---C++语言实现

这是我学数据结构编写的算法，我把他整理出来，都是基本算法，供大家学习。我使用c++面向对象形式编写，各种算法都封装在各自的类里，假如想增加功能，在相应的类里增加函数即可。我对树和图的构造也做了一些人性化设计，输入更加形象化，你可能看不懂，没关系漫漫来。各种类都使用模版设计，可以对各种数据类型操作（整形，字符，浮点）

　　///////////////////////////

　　// //

　　// 堆栈数据结构 stack.h //

　　// //

　　//////////////////////////

　　#include

　　templateclass Stack;

　　template

　　class StackNode

　　{

　　 friend class Stack;

　　 private:

　　 Type data;

　　 StackNode *link;

　　 StackNode(Type D=0,StackNode *L=NULL):link(L),data(D){}

　　};

　　template

　　class Stack

　　{

　　 public:

　　 Stack():top(NULL),NumItem(0){}

　　 void Push(Type item);

　　 Type Pop();

　　 Type GetTop();

　　 void MakeEmpty();

　　 bool ISEmpty();

　　 int GetNum();

　　 private:

　　 int NumItem;

　　 StackNode *top;

　　};

　　template

　　void Stack::Push(Type item)

　　{

　　 top=new StackNode(item,top);

　　 NumItem++;

　　}

　　template

　　Type Stack::Pop()

　　{

　　 StackNode *p;

　　 Type temp;

　　 temp=top->data;

　　 p=top;

　　 top=top->link;

　　 delete p;

　　 NumItem--;

　　 return temp;

　　}

　　template

　　Type Stack::GetTop()

　　{

　　 return top->data;

　　}

　　template

　　bool Stack::ISEmpty()

　　{

　　 return top==NULL;

　　}

　　template

　　void Stack::MakeEmpty()

　　{

　　 delete top;

　　}

　　template

　　int Stack::GetNum()

　　{

　　 return NumItem;

　　}

　　///////////////////////////

　　// //

　　// 队列数据结构 Queue.h //

　　// //

　　//////////////////////////

　　#include

　　template class Queue;

　　template class QueueNode

　　{

　　 friend class Queue;

　　 private:

　　 Type data;

　　 QueueNode *link;

　　 QueueNode(Type d=0,QueueNode *l=NULL):data(d),link(l){}

　　};

　　template class Queue

　　{

　　 public:

　　 Queue():rear(NULL),front(NULL){}

　　 ~Queue();

　　 void EnQueue(Type item);

　　 Type DelQueue();

　　 Type GetFront();

　　 void MakeEmpty();

　　 bool ISEmpty() { return front==NULL; }

　　 private:

　　 QueueNode *front,*rear;

　　};

　　template

　　Queue::~Queue()

　　{

　　 QueueNode *p;

　　 while(front!=NULL)

　　 {

　　 p=front;

　　 front=front->link;

　　 delete p;

　　 }

　　}

　　template

　　void Queue::EnQueue(Type item)

　　{

　　 if(front==NULL)

　　 front=rear=new QueueNode (item,NULL);

　　 else

　　 rear=rear->link=new QueueNode (item,NULL);

　　}

　　template

　　Type Queue::DelQueue()

　　{

　　 QueueNode *p=front;

　　 Type temp=p->data;;

　　 front=front->link;

　　 delete p;

　　 return temp;

　　}

　　template

　　Type Queue::GetFront()

　　{

　　 return front->data;

　　}

　　template

　　void Queue::MakeEmpty()

　　{

　　 QueueNode *p;

　　 while(front!=NULL)

　　 {

　　 p=front;

　　 front=front->link;

　　 delete p;

　　 }

　　}

　　///////////////////////////

　　// //

　　// 链表数据结构 list.h //

　　// //

　　//////////////////////////

　　#include

　　template

　　class list;

　　template

　　class listnode

　　{

　　 public:

　　 friend class list;

　　 private:

　　 type data;

　　 listnode * next;

　　};

　　template

　　class list

　　{

　　 public:

　　 list();

　　 ~list();

　　 void insertend(type); //向链表尾部插入元素

　　 bool insert(type,int); //向链表任意位置插入元素

　　 void delnode(int i); //删除元素

　　 int find(type T); //查找元素

　　 void makeempty(); //销毁链表

　　 bool print(); //打印链表

　　 int getlen(); //得到链表长度

　　 private:

　　 listnode *first,*last;

　　 int length;

　　};

　　template

　　void initlist(type &tmp);

　　template

　　void list_exit(list &L,type tmp);

　　void initation();

　　template

　　void list_insertend(list &L,type tmp);

　　template int list::getlen()

　　{

　　 return length;

　　}

　　template void list::makeempty()

　　{

　　 listnode *p1,*p2;

　　 p1=first->next;

　　 first->next=NULL;

　　 while(p1!=NULL)

　　 {

　　 p2=p1;

　　 p1=p1->next;

　　 delete p2;

　　 }

　　 length=0;

　　}

　　template void list::insertend(type t)

　　{

　　 listnode *p;

　　 p=new listnode;

　　 p->data=t;

　　 p->next=NULL;

　　 last->next=p;

　　 last=p;

　　 length++;

　　}

　　template bool list::insert(type t,int i)

　　{

　　 listnode *p;

　　 p=first;

　　 int k=1;

　　 while(p!=NULL&&k

　　 {

　　 p=p->next;

　　 k++;

　　 }

　　 if(p==NULL&&k!=i)

　　 return false;

　　 else

　　 {

　　 listnode *tp;

　　 tp=new listnode;

　　 tp->data=t;

　　 tp->next=p->next;

　　 p->next=tp;

　　 length++;

　　 return true;

　　 }

　　}

　　template void list::delnode(int i)

　　{

　　 int k=1;

　　 listnode *p,*t;

　　 p=first;

　　 while(p->next!=NULL&&k!=i)

　　 {

　　 p=p->next;

　　 k++;

　　 }

　　 t=p->next;

　　 cout<<"你已经将数据项 "<data<<"删除"<

　　 p->next=p