數據結構算法集---C++語言實現

2019-11-17 05:31:44

字體：大中小

來源：轉載

供稿：網友

  這是我學數據結構編寫的算法，我把他整理出來，都是基本算法，供大家學習。我使用c++面向對象形式編寫，各種算法都封裝在各自的類里，假如想增加功能，在相應的類里增加函數即可。我對樹和圖的構造也做了一些人性化設計，輸入更加形象化，你可能看不懂，沒關系漫漫來。各種類都使用模版設計，可以對各種數據類型操作（整形，字符，浮點）

///////////////////////////
//    //
//   堆棧數據結構   stack.h         //
//    //
//////////////////////////

#include<iostream.h>

template<class Type>class Stack;

template<class Type>
class StackNode
{
friend class Stack<Type>;
PRivate:
Type data;
StackNode<Type> *link;
   StackNode(Type D=0,StackNode<Type> *L=NULL):link(L),data(D){}
};

template<class 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;
StackNode<Type> *top;
};

template<class Type>
void Stack<Type>::Push(Type item)
{
  top=new StackNode<Type>(item,top);
NumItem++;
}

template<class Type>
Type Stack<Type>::Pop()
{
StackNode<Type> *p;
Type temp;
temp=top->data;
p=top;
top=top->link;
delete p;
NumItem--;
return temp;

}

template<class Type>
Type Stack<Type>::GetTop()
{
return top->data;
}

template<class Type>
bool Stack<Type>::ISEmpty()
{
return top==NULL;
}

template<class Type>
void Stack<Type>::MakeEmpty()
{
delete top;
}

template<class Type>
int Stack<Type>::GetNum()
{
return NumItem;
}

///////////////////////////
//    //
//   隊列數據結構       Queue.h //
//    //
//////////////////////////
#include<iostream.h>

template<class Type> class Queue;

template<class Type> class QueueNode
{
friend class Queue<Type>;

private:
Type data;
QueueNode<Type> *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:
QueueNode<Type> *front,*rear;
};

template<class Type>
Queue<Type>::~Queue()
{
QueueNode<Type> *p;
while(front!=NULL)
{
p=front;
front=front->link;
delete p;
}
}

template<class Type>
void Queue<Type>::EnQueue(Type item)
{
if(front==NULL)
front=rear=new QueueNode<Type> (item,NULL);
else
rear=rear->link=new QueueNode<Type> (item,NULL);
}

template<class Type>
Type Queue<Type>::DelQueue()
{
QueueNode<Type> *p=front;
Type temp=p->data;;
front=front->link;
delete p;
return temp;
}

template<class Type>
Type Queue<Type>::GetFront()
{
return front->data;
}

template<class Type>
void Queue<Type>::MakeEmpty()
{
QueueNode<Type> *p;
while(front!=NULL)
{
p=front;
front=front->link;
delete p;
}
}

///////////////////////////
//    //
//   鏈表數據結構  list.h //
//    //
//////////////////////////

#include<iostream.h>

template<class type>
class list;

template<class type>
class listnode
{
public:
friend class list<type>;
private:
type data;
listnode<type> * next;
};

template<class 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:
listnode<type> *first,*last;
int length;
};

template<class type>
void initlist(type &tmp);

template<class type>
void list_exit(list<type> &L,type tmp);

void initation();

template<class type>
void list_insertend(list<type> &L,type tmp);

template<class type> int list<type>::getlen()
{
return length;
}

template<class type> void list<type>::makeempty()
{
listnode<type> *p1,*p2;

p1=first->next;
first->next=NULL;
while(p1!=NULL)
  {
p2=p1;
p1=p1->next;
delete p2;
}
length=0;
}

template<class type> void list<type>::insertend(type t)
{

listnode<type> *p;
p=new listnode<type>;
p->data=t;
p->next=NULL;
last->next=p;
last=p;

length++;
}

template<class type> bool list<type>::insert(type t,int i)
{
listnode<type> *p;
p=first;

int k=1;
while(p!=NULL&&k<i)
{
p=p->next;
k++;
}
if(p==NULL&&k!=i)
return false;
else
{
   listnode<type> *tp;
tp=new listnode<type>;
tp->data=t;
tp->next=p->next;
p->next=tp;
length++;

return true;
}
}

template<class type> void list<type>::delnode(int i)
{
int k=1;
listnode<type> *p,*t;
p=first;

while(p->next!=NULL&&k!=i)
{
p=p->next;
   k++;
}
  t=p->next;
cout<<"你已經將數據項 "<<t->data<<"刪除"<<endl;

p->next=p

上一篇：數據結構輔導---棧和隊列(2)

下一篇：數據結構題集--數組(二維數組)