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

【 tulaoshi.com - 编程语言 】

  这是我学数据结构编写的算法，我把他整理出来，都是基本算法，供大家学习。我使用c++面向对象形式编写，各种算法都封装在各自的类里，假如想增加功能，在相应的类里增加函数即可。我对树和图的构造也做了一些人性化设计，输入更加形象化，你可能看不懂，没关系漫漫来。各种类都使用模版设计，可以对各种数据类型操作（整形，字符，浮点）
　　
　　
　　///////////////////////////
　　//    //
　　//   堆栈数据结构   stack.h         //
　　//    //
　　//////////////////////////
　　
　　
　　#includeiostream.h
　　
　　templateclass Typeclass Stack;
　　
　　templateclass Type
　　class StackNode
　　{
　　 friend class StackType;
　　 private:
　　 Type data;
　　 StackNodeType *link;
　　   StackNode(Type D=0,StackNodeType *L=NULL):link(L),data(D){}
　　};
　　
　　templateclass Type
　　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;
　　 StackNodeType *top;
　　};
　　
　　templateclass Type
　　void StackType::Push(Type item)
　　{
　　  top=new StackNodeType(item,top);
　　 NumItem++;
　　}
　　
　　templateclass Type
　　Type StackType::Pop()
　　{
　　 StackNodeType *p;
　　 Type temp;
　　 temp=top-data;
　　 p=top;
　　 top=top-link;
　　 delete p;
　　 NumItem--;
　　 return temp;
　　
　　}
　　
　　templateclass Type
　　Type StackType::GetTop()
　　{
　　 return top-data;
　　}
　　
　　templateclass Type
　　bool StackType::ISEmpty()
　　{
　　 return top==NULL;
　　}
　　
　　templateclass Type
　　void StackType::MakeEmpty()
　　{
　　 delete top;
　　}
　　
　　templateclass Type
　　int StackType::GetNum()
　　{
　　 return NumItem;
　　}
　　
　　
　　
　　///////////////////////////
　　//    //
　　//   队列数据结构       Queue.h //
　　//    //
　　//////////////////////////
　　#includeiostream.h
　　
　　templateclass Type class Queue;
　　
　　templateclass Type class QueueNode
　　{
　　 friend class QueueType;
　　
　　 private:
　　 Type data;
　　 QueueNodeType *link;
　　 QueueNode(Type d=0,QueueNode *l=NULL):data(d),link(l){}
　　};
　　
　　template class Type 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:
　　 QueueNodeType *front,*rear;
　　};
　　
　　
　　templateclass Type
　　QueueType::~Queue()
　　{
　　 QueueNodeType *p;
　　 while(front!=NULL)
　　 {
　　 p=front;
　　 front=front-link;
　　 delete p;
　　 }
　　}
　　
　　templateclass Type
　　void QueueType::EnQueue(Type item)
　　{
　　 if(front==NULL)
　　 front=rear=new QueueNodeType (item,NULL);
　　 else
　　 rear=rear-link=new QueueNodeType (item,NULL);
　　}
　　
　　
　　templateclass Type
　　Type QueueType::DelQueue()
　　{
　　 QueueNodeType *p=front;
　　 Type temp=p-data;;
　　 front=front-link;
　　 delete p;
　　 return temp;
　　}
　　
　　
　　templateclass Type
　　Type QueueType::GetFront()
　　{
　　 return front-data;
　　}
　　
　　
　　templateclass Type
　　void QueueType::MakeEmpty()
　　{
　　 QueueNodeType *p;
　　 while(front!=NULL)
　　 {
　　 p=front;
　　 front=front-link;
　　 delete p;
　　 }
　　}
　　
　　
　　///////////////////////////
　　//    //
　　//   链表数据结构  list.h //
　　//    //
　　//////////////////////////
　　
　　
　　#includeiostream.h
　　
　　templateclass type
　　class list;
　　
　　templateclass type
　　class listnode
　　{
　　 public:
　　 friend class listtype;
　　 private:
　　 type data;
　　 listnodetype * next;
　　};
　　
　　
　　templateclass type
　　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:
　　 listnodetype *first,*last;
　　 int length;
　　};
　　
　　templateclass type
　　void initlist(type &tmp);
　　
　　templateclass type
　　void list_exit(listtype &L,type tmp);
　　
　　void initation();
　　
　　templateclass type
　　void list_insertend(listtype &L,type tmp);
　　
　　
　　templateclass type int listtype::getlen()
　　{
　　 return length;
　　}
　　
　　templateclass type void listtype::makeempty()
　　{
　　 listnodetype *p1,*p2;
　　
　　 p1=first-next;
　　 first-next=NULL;
　　 while(p1!=NULL)
　　  {
　　 p2=p1;
　　 p1=p1-next;
　　 delete p2;
　　 }
　　 length=0; 
　　}
　　
　　templateclass type void listtype::insertend(type t)
　　{
　　
　　 listnodetype *p;
　　 p=new listnodetype;
　　 p-data=t;
　　 p-next=NULL;
　　 last-next=p;
　　 last=p;
　　
　　 length++;
　　}
　　
　　templateclass type bool listtype::insert(type t,int i)
　　{
　　 listnodetype *p;
　　 p=first;
　　
　　 int k=1;
　　 while(p!=NULL&&ki)
　　 {
　　 p=p-next;
　　 k++;
　　 }
　　 if(p==NULL&&k!=i)
　　 return false;
　　 else
　　 {
　　   listnodetype *tp;
　　  tp=new listnodetype;
　　  tp-data=t;
　　  tp-next=p-next;
　　  p-next=tp;
　　  length++;
　　 
　　  return true;
　　 }
　　}
　　
　　templateclass type void listtype::delnode(int i)
　　{
　　 int k=1;
　　 listnodetype *p,*t;
　　 p=first;
　　
　　 while(p-next!=NULL&&k!=i)
　　 {
　　 p=p-next;
　　   k++;
　　 }
　　  t=p-next;
　　 cout"你已经将数据项 "t-data"删除"endl;
　　
　　 p-next=p