성형 도면 의 깊이 와 넓이
22503 단어 c-c++데이터 구조그림 의 넓이 와 깊이
#include
#include
#include
using namespace std;
struct Node
{
int data;
Node *next;
Node(){next=NULL;}
Node(int item,Node *link=NULL)
{
data=item;
next=link;
}
};
class LinkQueue
{
protected:
Node *front,*rear;
int count;
public:
LinkQueue(){rear=front=new Node();count=0;}
virtual ~LinkQueue();
int length()const{return count;}
bool Empty()const{return count==0;}
void Clear();
void Traverse()const;
bool OutQueue(int &e);
bool GetHead(int &e)const;
bool InQueue(const int &e);
LinkQueue(const LinkQueue ©);
LinkQueue&operator=(const LinkQueue ©);
};
LinkQueue::~LinkQueue()
{
Clear();
}
void LinkQueue::Clear()
{
int tmp;
while(!Empty())
OutQueue(tmp);
}
void LinkQueue::Traverse()const
{
for(Node *tmp=front->next;tmp!=NULL;tmp=tmp->next)
cout<data<<' ';
}
bool LinkQueue::OutQueue(int &e)
{
if(!Empty())
{
Node *tmp=front->next;
e=tmp->data;
front->next=tmp->next;
if(rear==tmp)
rear=front;
delete tmp;
count--;
return true;
}
else
return false;
}
bool LinkQueue::GetHead(int &e)const
{
if(!Empty())
{
Node *tmp=front->next;
e=tmp->data;
return true;
}
else
return false;
}
bool LinkQueue::InQueue(const int &e)
{
Node *tmp=new Node(e);
rear->next=tmp;
rear=tmp;
count++;
return true;
}
LinkQueue::LinkQueue(const LinkQueue©)
{
rear=front=new Node();
count=0;
for(Node *tmp=copy.front->next;tmp!=NULL;tmp=tmp->next)
InQueue(tmp->data);
}
LinkQueue&LinkQueue::operator=(const LinkQueue©)
{
if(©!=this)
{
Clear();
for(Node *tmp=copy.front->next;tmp!=NULL;tmp=tmp->next)
InQueue(tmp->data);
}
return *this;
}
class AdjMatrixDirGraph
{
protected:
int vexNum,edgeNum; //
int **Matrix; //
int *elems; //
mutable bool *tag; //
void DestroyHelp(); //
void DFS(int v)const; // v
void BFS(int v)const; // v
public:
AdjMatrixDirGraph(int es[],int vertexNum=10); // es, vertexNum, 0
AdjMatrixDirGraph(int vertexNum=10); // vertexNum 0
~AdjMatrixDirGraph(); //
void DFSTraverse()const; //
void BFSTraverse()const; //
bool GetElem(int v,int &e)const; //
bool SetElem(int v,const int &e); //
int GetVexNum()const{return vexNum;} //
int GetEdgeNum()const{return edgeNum;} //
int FirstAdjVex(int v)const; // v
int NextAdjVex(int v1,int v2)const; // v1 v2
void InsertEdge(int v1,int v2); // v1 v2
void DeleteEdge(int v1,int v2); // v1 v2
bool GetTag(int v)const; // v
void SetTag(int v,bool val)const; // v1 val
void Display()const; //
};
void AdjMatrixDirGraph::DestroyHelp()
{
delete[] elems;
delete[] tag;
for(int i=0;idelete []Matrix[i];
delete []Matrix;
}
void AdjMatrixDirGraph::DFS(int v)const
{
SetTag(v,true);
int e;
GetElem(v,e);
cout<' ';
for(int w=FirstAdjVex(v);w>=0;w=NextAdjVex(v,w))
if(!GetTag(w))
DFS(w);
}
void AdjMatrixDirGraph::DFSTraverse()const
{
int v;
for(v=0;vfalse);
cout<<" :";
for(v=0;vif(!GetTag(v))
DFS(v);
}
void AdjMatrixDirGraph::BFS(int v)const
{
SetTag(v,true);
int e;
GetElem(v,e);
cout<' ';
LinkQueue q;
q.InQueue(v);
while(!q.Empty())
{
int u,w;
q.OutQueue(u);
for(w=FirstAdjVex(u);w>=0;w=NextAdjVex(u,w))
{
if(!GetTag(w))
{
SetTag(w,true);
GetElem(w,e);
cout<' ';
q.InQueue(w);
}
}
}
}
void AdjMatrixDirGraph::BFSTraverse()const
{
int v;
for(v=0;vfalse);
cout<<" :";
for(v=0;vif(!GetTag(v))
BFS(v);
}
AdjMatrixDirGraph::AdjMatrixDirGraph(int es[],int vetexNum)
{
if(vetexNum<=0)
throw runtime_error(" 0");
vexNum=vetexNum,edgeNum=0;
Matrix=new int*[vexNum];
elems=new int[vexNum];
tag=new bool[vexNum];
for(int i=0;inew int[vexNum];
for (int u = 0; u < vexNum; u++)
for (int v = 0; v < vexNum; v++)
Matrix[u][v] = 0;
for(int i=0;ifor(int i=0;ifalse;
}
AdjMatrixDirGraph::AdjMatrixDirGraph(int vetexNum)
{
if(vetexNum<0)
throw runtime_error(" 0");
vexNum=vetexNum,edgeNum=0;
Matrix=new int*[vexNum];
elems=new int[vexNum];
tag=new bool[vexNum];
for(int i=0;inew int[vexNum];
for (int u = 0; u < vexNum; u++)
for (int v = 0; v < vexNum; v++)
Matrix[u][v] = 0;
for(int i=0;ifalse;
}
AdjMatrixDirGraph::~AdjMatrixDirGraph()
{
DestroyHelp();
}
bool AdjMatrixDirGraph::GetElem(int v,int &e)const
{
if(v<0||v>=vexNum)
return false;
else
{
e=elems[v];
return true;
}
}
bool AdjMatrixDirGraph::SetElem(int v,const int &e)
{
if(v<0||v>=vexNum)
return false;
else
{
elems[v]=e;
return true;
}
}
int AdjMatrixDirGraph::FirstAdjVex(int v)const
{
int i=0;
while(Matrix[v][i]==0&&iif(Matrix[v][i]==1)
return i;
return -1;
}
int AdjMatrixDirGraph::NextAdjVex(int v1,int v2)const
{
while(Matrix[v1][++v2]==0&&v2if(Matrix[v1][v2]==1)
return v2;
return -1;
}
void AdjMatrixDirGraph::InsertEdge(int v1,int v2)
{
if(v1<0||v1>=vexNum) throw runtime_error("v1 ");
if(v2<0||v2>=vexNum) throw runtime_error("v2 !");
if(v1==v2) throw runtime_error("v1 v2!");
if(Matrix[v1][v2]==0&&Matrix[v2][v1]==0)
edgeNum++;
Matrix[v1][v2]=1;
Matrix[v2][v1]=1;
}
void AdjMatrixDirGraph::DeleteEdge(int v1,int v2)
{
if(v1<0||v1>=vexNum) throw runtime_error("v1 !");
if(v2<0||v2>=vexNum) throw runtime_error("v2 !");
if(v1==v2) throw runtime_error("v1 v2!");
if(Matrix[v1][v2]==1&&Matrix[v2][v1]==1)
edgeNum--;
Matrix[v1][v2]=0;
Matrix[v2][v1]=0;
}
bool AdjMatrixDirGraph::GetTag(int v)const
{
if(v<0||v>=vexNum)
throw runtime_error("v ");
else
return tag[v];
}
void AdjMatrixDirGraph::SetTag(int v,bool val)const
{
if(v<0||v>=vexNum)
throw runtime_error("v ");
else
tag[v]=val;
}
void AdjMatrixDirGraph::Display()const
{
for(int i=0;ifor(int j=0;jcout<' ';
cout<int main()
{
int vetexNum,edgeNum,v1,v2;
cout<<" :";
cin>>vetexNum;
int es[vetexNum];
for(int i=0;icout<<" "<" :";
cin>>es[i];
}
AdjMatrixDirGraph g(es,vetexNum);
cout<<" :";
cin>>edgeNum;
for(int i=0;icout<<" "<1<<" ( ):";
scanf("%d %d",&v1,&v2);
g.InsertEdge(v1,v2);
}
g.Display();
g.DFSTraverse();
g.BFSTraverse();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
성형 도면 의 깊이 와 넓이텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.