几个数据结构的知识点的实现,希望大家多提意见.
只写了几个,不全
:)


(2)图


#include "stdafx.h"
#include<iostream.h>
#include<stdlib.h>

template<class T>
class Stack
{
private:
T StackList[50];
int top;
public:
Stack(void);
void Push(const T& item);
T Pop(void);
void ClearStack(void);
T Peek(void) const;
int StackEmpty(void) const;
int StackFull(void) const;
int StackSize(void);
};

template<class T>
Stack<T>::Stack(void)
{
top=-1;
}

template<class T>
void Stack<T>::Push(const T& item)
{
if(top==49)
return;
top++;
StackList[top]=item;
return;
}

template<class T>
T Stack<T>::Pop(void)
{
T temp;
if(top==-1)
exit(1);
temp=StackList[top];
top--;
return temp;
}

template<class T>
T Stack<T>::Peek(void) const
{
if(top==-1)
exit(1);
return StackList[top];
return;
}

template<class T>
int Stack<T>::StackEmpty(void) const
{
return (top==-1);
}

template<class T>
int Stack<T>::StackFull(void) const
{
return(top==49);
}

template<class T>
void Stack<T>::ClearStack(void)
{
top=-1;
}

template<class T>
int Stack<T>::StackSize(void)
{
return 50;
}

template<class T>
class Queue
{
private:
T QList[50];
int front,rear,count;
public:
Queue(void);
void QInsert(const T & item);
T QDelete(void);
void ClearQueue(void);
T QFront(void) const;
int QLength(void) const;
int QEmpty(void) const;
int QFull(void) const;
};

template<class T>
Queue<T>::Queue(void)
{
front=0;
rear=0;
count=0;
}

template<class T>
void Queue<T>::QInsert(const T & item)
{
if(count==50)
return;
count++;
QList[rear]=item;
rear=(rear+1)%50;
return;
}

template<class T>
T Queue<T>::QDelete(void)
{
if(count==0)
exit(1);
T temp;
temp=QList[front];
count--;
front=(front+1)%50;
return temp;
}

template<class T>
void Queue<T>::ClearQueue(void)
{
front=0;
rear=0;
count=0;
return;
}

template<class T>
T Queue<T>::QFront(void) const
{
if(count==0)
return NULL;
T temp;
temp=QList[front];
return QList[front];
}

template<class T>
int Queue<T>::QLength(void) const
{
return count;
}

template<class T>
int Queue<T>::QEmpty(void) const
{
return (count==0);
}

template<class T>
int Queue<T>::QFull(void) const
{
return (count==50);
}

template<class T>
class Graph;

template<class T>
class Vertex;

template <class T>
class Edge
{
friend class Graph<T>;
private:
int VerAdj;
int cost;
Edge<T> * link;
public:
Edge(int d,int c) { VerAdj=d;cost=c;link=NULL;}
int operator!=(Edge & E) const { return(VerAdj==E.VerAdg);}
};

template <class T>
class Vertex
{
friend class Graph<T>;
public:
T VerName;
Edge<T> * adjacent;
};

template <class T>
class Graph
{
private:
Vertex<T> head[100];
int GraphSize;
//int MaxGraphSize=100;
int NumEdge;
//int MaxNumEdge=4950;
public:
int GetVertexPos(const T & vertex);
T GetName(int v) { return head[v].VerName;}
Graph();
~Graph();
int GraphEmpty(void) const { return (GraphSize==0);}
int GraphFull(void) const { return ((GraphSize==100)||(NumEdge==4950));}
int NumOfVertex(void) const { return GraphSize;}
int NumOfEdge(void) const { return NumEdge;}
int GetWeight(const T & vertex1,const T & vertex2);
Edge * GetNeighbors(T & vertex);
int GetFirstNeighbor(int v);
int GetNextNeighbor(int v1,int v2);
void InsertVertex(const T & vertex);
void InsertEdge(const T & vertex1,const T & vertex2,int weight);
void DeleteVertex(const T & vertex);
void DeleteEdge(const T & vertex1,const T & vertex2);
void Out();
T Head(int item);
void DepthFirst();
void DepthFirstSearch(int i,int * p);
void DepthFirst_Stack();
void LevelOrder_Queue();
void AOV();
};

template<class T>
Graph<T>::Graph()
{
GraphSize=0;
int n=0,e=0,weight;
T name,from,to;
cout<<"Begin to create a graph"<<endl;
cout<<"Input the number of vertex"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cout<<endl<<" name: ";
cin>>name;
InsertVertex(name);
}
cout<<endl<<"Input of vertex end ";
cout<<endl<<"The size of vertex is "<<n;
cout<<endl<<"Begin to input edge";
cout<<endl<<"Input the number of edge"<<endl;
cin>>e;
for(int j=0;j<e;j++)
{
cout<<endl<<" from: ";
cin>>from;
cout<<endl<<" to: ";
cin>>to;
cout<<endl<<" weight: ";
cin>>weight;
InsertEdge(from,to,weight);
}
cout<<endl<<"Input of edge end";
cout<<endl<<"The number of edge is "<<e;
}

template<class T>
Graph<T>::~Graph()
{
for(int i=0;i<GraphSize;i++)
{
Edge<T> * p=head[i].adjacent;
while(p!=NULL)
{
head[i].adjacent=p->link;
delete p;
p=head[i].adjacent;
}
}
cout<<endl<<"The graph deleted";
}

template<class T>
int Graph<T>::GetVertexPos(const T & vertex)
{
for(int i=0;i<GraphSize;i++)
if(head[i].VerName==vertex)
return i;
cout<<"No such vertex exist"<<endl;
return -1;
}

template<class T>
int Graph<T>::GetWeight(const T & vertex1,const T & vertex2)
{
int numbegin=GetVertexPos(vertex1);
int numend=GetVertexPos(vertex2);
Edge<T> * p=head[numbegin].adjacent;
if((numbegin!=-1)&&(numend!=-1))
{
while(p!=NULL)
{
if(p->VerAdj==b)
return p->cost;
p=p->link;
}
cout<<"No such edge exist"<<endl;
return 0;
}
}

template<class T>
Edge<T> * Graph<T>::GetNeighbors(T & vertex)
{
int i=GetVertexPos(vertex);
if(i!=-1)
return head[i].adjacent;
return NULL;
}

template<class T>
int Graph<T>::GetFirstNeighbor(int v)
{
if((v>=0)&&(v<GraphSize))
{
Edge<T> * p=head[v].adjacent;
if(p!=NULL)
{
int w=p->VerAdj;
return w;
}
}
return -1;
}

template<class T>
int Graph<T>::GetNextNeighbor(int v1,int v2)
{
if((v1>=0)&&(v1<GraphSize)&&(v2>=0)&&(v2<GraphSize))
{
Edge<T> * p=head[v1].adjacent;
while((p->VerAdj!=v2)&&(p!=NULL))
p=p->link;
if(p==NULL)
return -1;
p=p->link;
if(p==NULL)
return -1;
return p->VerAdj;
}
return -1;
}

template<class T>
void Graph<T>::InsertVertex(const T & vertex)
{
head[GraphSize].VerName=vertex;
head[GraphSize].adjacent=NULL;
GraphSize++;
cout<<"One vertex created with name "<<vertex;
return;
}

template<class T>
void Graph<T>::InsertEdge(const T & vertex1,const T & vertex2,int weight)
{
int numbegin=GetVertexPos(vertex1);
int numend=GetVertexPos(vertex2);
if(numbegin==-1)
return;
Edge<T> * p=head[numbegin].adjacent;
if(numend!=-1)
{
if(p==NULL)
{
head[numbegin].adjacent=new Edge<T>(numend,weight);
cout<<endl<<"One edge inserted from 1 ";
cout<<numbegin<<" to "<<vertex2<<" with weight "<<weight;
return;
}
int judge=0;
Edge<T> * q=NULL;
while(p!=NULL)
{
q=p;
if(p->VerAdj==numend)
judge=1;
p=p->link;
}
if(judge==1)
{
cout<<endl<<"Can not insert edge";
return;
}
q->link=new Edge<T>(numend,weight);
cout<<endl<<"One edge inserted from 2 "<<vertex1<<" to "<<vertex2;
cout<<" with weight "<<weight;
return;
}
cout<<"Can not insert edge"<<endl;
return;
}

template<class T>
void Graph<T>::DeleteVertex(const T & vertex)
{
int pos=GetVertexPos(vertex);
if(pos==-1)
{
cout<<"Can not delete such vertex"<<endl;
return;
}
Edge<T> * p=NULL;
Edge<T> * q=NULL;
int judge=0;
for(int i=0;i<GraphSize;i++)
{
judge=0;
p=head[i].adjacent;
while(p!=NULL)
{
if(p->VerAdj==pos)
{
judge=1;
if(q==NULL)
head[i].adjacent=p->link;
else
q->link=p->link;
}
if(p->VerAdj>pos)
p->VerAdj--;
q=p;
p=p->link;
}
}
while(pos!=(GraphSize-1))
{
judge=1;
head[pos].VerName=head[pos+1].VerName;
head[pos].adjacent=head[pos+1].adjacent;
pos++;
}
if(judge==1)
{
cout<<"One vertex deleted with name"<<vertex<<" with number";
cout<<GetVertexPos(vertex)<<endl;
GraphSize--;
}
return;
}

template<class T>
void Graph<T>::DeleteEdge(const T & vertex1,const T & vertex2)
{
int numbegin=GetVertexPos(vertex1);
int numend=GetVertexPos(vertex2);
Edge<T> * p=NULL;
Edge<T> * q=NULL;
int judge=0;
if((numbegin!=-1)&&(numend!=-1))
{
p=head[numbegin].adjacent;
if(p==NULL)
{ cout<<"p is null"<<endl;return;}
if(p->VerAdj==numend)
judge=1;
int k=0;
while((p!=NULL)&&(judge==0))
{
cout<<endl<<p->VerAdj<<numend<<endl;
k++;
q=p;
p=p->link;
if((p!=NULL)&&(p->VerAdj==numend))
{
cout<<"Find such edge";
judge=1;
}
}
if(judge==0)
{
cout<<"Can not delete such edge 1 "<<endl;
return;
}
else
{
cout<<"Delete a edge from "<<vertex1<<" to "<<p->VerAdj<<" with weight ";
cout<<p->cost<<endl;
NumEdge--;
if(q==NULL)
head[numbegin].adjacent=p->link;
else
q->link=p->link;
return;
}
}
else
{
cout<<"Can not delete such edge 2 "<<endl;
return;
}
}

template<class T>
void Graph<T>::Out()
{
for(int i=0;i<GraphSize;i++)
{
cout<<" name is "<<head[i].VerName;
cout<<" and its number is"<<GetVertexPos(head[i].VerName)<<endl;
Edge<char> * p=head[i].adjacent;
while(p!=NULL)
{
cout<<"One edge exist from "<<head[i].VerName;
cout<<" to "<<p->VerAdj<<" with value ";
cout<<p->cost<<endl;
p=p->link;
}
cout<<endl;
}
}

template<class T>
T Graph<T>::Head(int item)
{
return head[item].VerName;
}

template<class T>
void Graph<T>::DepthFirst()
{
int * visited=new int[GraphSize];
for(int i=0;i<GraphSize;i++)
visited[i]=0;
cout<<"Begin"<<endl;
DepthFirstSearch(0,visited);
delete[] visited;
}

template<class T>
void Graph<T>::DepthFirstSearch(int i,int * p)
{
if((i<0)||(i>=GraphSize))
return;
cout<<head[i].VerName;
p[i]=1;
int w=GetFirstNeighbor(i);
while(w!=-1)
{
if(!p[w])
DepthFirstSearch(w,p);
w=GetNextNeighbor(i,w);
}
}

template<class T>
void Graph<T>::DepthFirst_Stack()
{
if(GraphSize==0)
return;
int * visited=new int[GraphSize];
for(int i=0;i<GraphSize;i++)
visited[i]=0;
Stack<int> s;
s.Push(0);
int w,k;
while(!s.StackEmpty())
{
w=s.Pop();
if(!visited[w])
{
visited[w]=1;
cout<<head[w].VerName;
}
k=GetFirstNeighbor(w);
while(k!=-1)
{
if(!visited[k])
s.Push(k);
k=GetNextNeighbor(w,k);
}
}
return;
}

template<class T>
void Graph<T>::LevelOrder_Queue()
{
if(GraphSize==0)
return;
int * visited=new int[GraphSize];
for(int i=0;i<GraphSize;i++)
visited[i]=0;
Queue<int> q;
q.QInsert(0);
int w,k;
while(!q.QEmpty())
{
w=q.QDelete();
if(!visited[w])
{
visited[w]=1;
cout<<head[w].VerName;
}
k=GetFirstNeighbor(w);
while(k!=-1)
{
if(!visited[k])
q.QInsert(k);
k=GetNextNeighbor(w,k);
}
}
return;
}

template<class T>
void Graph<T>::AOV()
{
if(GraphSize==0)
return;
int top=-1;
int * count=new int[GraphSize];
for(int in=0;in<GraphSize;in++)
count[in]=0;
for(int i=0;i<GraphSize;i++)
{
Edge<T> * p=head[i].adjacent;
while(p!=NULL)
{
int num=p->VerAdj;
count[num]=count[num]+1;
p=p->link;
}
}
for(int j=0;j<GraphSize;j++)
{
if(count[j]==0)
{
count[j]=top;
top=j;
}
}
for(int k=0;k<GraphSize;k++)
{
if(top==-1)
{
cout<<"There is a cycle in network"<<endl;
return;
}
else
{
int l=top;
top=count[top];
cout<<head[l].VerName;
Edge<T> * r=head[k].adjacent;
while(r!=NULL)
{
int a=r->VerAdj;
count[a]--;
if(count[a]==0)
{
count[a]=top;
top=a;
}
r=r->link;
}
}
}
return;
}

int main()
{
Graph<char> gc;
gc.Out();
cout<<endl<<"Display the graph in depthfirst"<<endl;
gc.DepthFirst();
cout<<endl<<"Display the graph in depthfirst with the help of stack"<<endl;
gc.DepthFirst_Stack();
cout<<endl<<"Display the graph in levelorder with the help of queue"<<endl;
gc.LevelOrder_Queue();
cout<<endl<<"now display the graph(AOV)"<<endl;
gc.AOV();
return 1;
}

[此贴子已经被作者于2006-2-10 16:40:01编辑过]