|
///////////////////////////
// //
// 堆栈数据结构 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->next->next;
length--;
delete t;
}
template<class type> bool list<type>::print()
{
listnode<type> *p=first->next;
if(length==0)
return false;
else
{
cout<<"链表中有"<<length<<"项数据: "<<endl;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
}
cout<<endl;
return true;
}
template<class type> int list<type>::find(type T)
{
listnode<type> *p=first->next;
int i=1;
while(p&&p->data!=T)
{
p=p->next;
i ;
}
if(p)
return i;
else
return 0;
}
template<class type> list<type>::~list()
{
delete first;
cout<<"欢迎再次使用 (!^!) "<<endl;
}
template<class type> list<type>::list()
{
listnode<type> *node=new listnode<type>;
node->next=NULL;
first=last=node;
length=0;
}
///////////////////////////
// //
// 图数据结构 graph.h //
// //
//////////////////////////
#include<iostream.h>
#include"Queue.h"
template<class NameType,class DisType>class Graph;
template<class NameType,class DisType> struct Node
{
friend class Graph<NameType,DisType>;
int num;
DisType val;
Node<NameType,DisType> *next;
};
template<class NameType,class DisType> struct GpNode
{
friend class Graph<NameType,DisType>;
NameType data;
Node<NameType,DisType> *link;
};
template<class NameType,class DisType>
class Graph
{
public:
void Creat(); //创建图
void PrintNode(); //打印图中的各个数据项
void DFS(); //图的深度优先搜索,主过程
void DFS(int v,int visited[]); // 子过程
void BFS(); //图的广度优先搜索，主过程
void BFS(int v,int visited[]); //子过程
void ShortPath(); //求最短路径
private:
GpNode<NameType,DisType> *table;
Node<NameType,DisType> *p;
int NumNode; //节点个数
};
template<class NameType,class DisType>
void Graph<NameType,DisType>::Creat()
{
do
{
cout<<"请输入节点个数: ";
cin >> NumNode;
}while(NumNode<=0);
table=new GpNode<NameType,DisType>[NumNode];
cout<<"请输入各节点数据项"<<endl;
for(int i=0;i<NumNode;i )
{
cin>>table[i].data;
table[i].link=NULL;
}
cout<<"请输入各边的关系 (如: A B)"<<endl;
i=1;
NameType nodeA,nodeB;
bool findA,findB;
char ISExit;
int m,n;
do
{
findA=findB=false;
cout<<"请输入第"<<i<<"对边的关系"<<endl;
cin>>nodeA>>nodeB;
for(m=0,n=0;m<NumNode&&n<NumNode&&!(findA & findB);) //查找边的节点
{
if(nodeA!=table[m].data)
m ;
else
findA=true;
if(nodeB!=table[n].data)
n ;
else
findB=true;
}
if(!(findA & findB))
cout<<"输入的节点数据项有错误"<<endl;
else
{
p=new Node<NameType,DisType>;
p->next=table[m].link;
p->num=n;
table[m].link=p;
cout<<"请输入该对边的权值: ";
cin>>p->val;
i ;
}
cout<<"是否继续输入: y)继续,X)任意键退出 ";
cin>>ISExit;
if(ISExit!='y'&&ISExit!='Y')
break;
}while(true);
}
template<class NameType,class DisType>
void Graph<NameType,DisType>
[1] [2] [3] [4] 下一页
|
