运行到广度优先遍历函数调用队列时就出问题

#include
using namespace std;
/*********************各类定义******************************/

class Node//基本抽象数据类型
{
public:
char ch; //记录名称,如果将这里改成数组,结点名称可以是多个字符
int flag;//记录结点是否被访问
};

class Graph //图类,此类中,封装了图的一些成员和一些必须的成员函数
{
private:
int getSub(char); //获取某名称的下标
Node* arrNode; //记录名称和是否访问的数组
int numVertex,numEdge;//记录图的顶点数和边数
int matrix; //用一个二维数组记录两点间是否相连,1相连,0断开
public:

void setCh(char,int); //将数组的arrNode的每一个单元设置一个结点名称
Graph(int);
~Graph();

int getNumVertex();//获得图的顶点数
char first(char ch);//获得相邻结点
char next(char ch1,char ch2);//获得隔着ch2,但与ch2相邻的结点
void setEdge(char,char,int w=1);//设置两顶点的边和权重(权重默认为1)
void eraserEdge(char,char);
void outPut();
int getMark(char);//获取是否被访问的记录,已访问返回1,未访问返回0
void setMark(char);//把已访问的结点,设置标记
};

template
class myQueue
{
private:
int theFront; // 1 counterclockwise from theFront element
int theBack; // position of theBack element
int arrayLength; // queue capacity
T queue; // element array
public:
myQueue(int initialCapacity = 10);
~myQueue() {delete [] queue;}
bool empty() const {return theFront == theBack;}
int size() const
{return (theBack - theFront + arrayLength) % arrayLength;}
T& front()
{// return front element
/*if (theFront == theBack)
throw queueEmpty();
/
return queue[(theFront + 1) % arrayLength];
}
T& back()
{// return theBack element
/*if (theFront == theBack)
throw queueEmpty();*/
return queue[theBack];
}
void pop()
{// remove theFront element
/*if (theFront == theBack)
throw queueEmpty();*/
theFront = (theFront + 1) % arrayLength;
queue[theFront].~T(); // destructor for T
}
void push(const T& theElement);
};
/
***********各函数的函数体*****************************/
Graph::Graph(int n)
{
int i,j;
arrNode=new Node[n];
numVertex=n;
numEdge=0;
for(i=0;i<numVertex;i++)

arrNode[i].flag=0;
matrix=new int*[numVertex];
for(i=0;i<numVertex;i++)

matrix[i]=new int[numVertex];
for(i=0;i<numVertex;i++)
for(j=0;j<numVertex;j++)

matrix[i][j]=matrix[j][i]=0;
}
Graph::~Graph()
{
delete [] arrNode;
for(int i=0;i<numVertex;i++)

delete [] matrix[i];

delete [] matrix;
}
int Graph::getSub(char ch) //获取下标
{
for(int i=0;i<numVertex;i++)

if(ch==arrNode[i].ch)

return i;
}
int Graph::getNumVertex() //获取顶点数
{
return numVertex;
}
char Graph::first(char ch) //获取相邻结点
{

for(int i=0;i<numVertex;i++)

if(matrix[getSub(ch)][i]!=0)

return arrNode[i].ch;
return ch;
}
char Graph::next(char ch1,char ch2) //获取与ch2相邻的结点
{

for(int i=getSub(ch2)+1;i<numVertex;i++)
if(matrix[getSub(ch1)][i]!=0)

return arrNode[i].ch;
return ch1;
}
void Graph::setEdge(char ch1,char ch2,int w) //设置边
{
if(matrix[getSub(ch1)][getSub(ch2)]==0)

{

numEdge++;
matrix[getSub(ch1)][getSub(ch2)]=matrix[getSub(ch2)][getSub(ch1)]=1;
}
}
void Graph::eraserEdge(char ch1,char ch2)
{
if(matrix[getSub(ch1)][getSub(ch2)]==1)

{

numEdge--;
matrix[getSub(ch1)][getSub(ch2)]=matrix[getSub(ch2)][getSub(ch1)]=0;
}
}
void Graph::outPut()
{
for(int i=0;i<numVertex;i++)
{

    for(int j=0;j<numVertex;j++)  
    {
        cout<<matrix[i][j]<<"    "; 

    }
    cout<<endl<<endl;;
}

}
int Graph::getMark(char ch)//获取访问信息
{

for(int i=0;i<numVertex;i++)

if(ch==arrNode[i].ch)

return arrNode[i].flag;
return -1;
}
void Graph::setMark(char ch) //设置标记
{
for(int i=0;i<numVertex;i++)

if(ch==arrNode[i].ch)

arrNode[i].flag=1;
}
void Graph::setCh(char ch,int n)//将结点名称设置在字符中
{
arrNode[n].ch=ch;
}

template
myQueue::myQueue(int initialCapacity)
{// Constructor.
/*if (initialCapacity < 1)
{ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}*/
arrayLength = initialCapacity;
queue = new T[arrayLength];
theFront = 0;
theBack = 0;
}
template
void myQueue::push(const T& theElement)
{// Add theElement to queue.

// increase array length if necessary
if ((theBack + 1) % arrayLength == theFront)
{// double array length
    // allocate a new array
    T* newQueue = new T[2 * arrayLength];

    // copy elements into new array
    int start = (theFront + 1) % arrayLength;
    if (start < 2)
        // no wrap around
        copy(queue + start, queue + start + arrayLength - 1, newQueue);
    else
    {  // queue wraps around
        copy(queue + start, queue + arrayLength, newQueue);
        copy(queue, queue + theBack + 1, newQueue + arrayLength - start);
    }

    // switch to newQueue and set theFront and theBack
    theFront = 2 * arrayLength - 1;
    theBack = arrayLength - 2;   // queue size arrayLength - 1
    arrayLength *= 2;
    queue = newQueue;
}

// put theElement at the theBack of the queue
theBack = (theBack + 1) % arrayLength;
queue[theBack] = theElement;

}

/***************主函数*********************/
void DFS(Graph*,char); //深度优先遍历函数声明
void BFS(Graph*,char,myQueue*); //广度优先遍历函数声明
int main()
{
char option;
int numVer,numE,i;
char temp1,temp2; //temp1,temp2作临时变量,记录输入的值
// myQueue* q=new myQueue;
cout << "输入定点数和弧数:";
cin >> numVer >> numE;
Graph myGraph1(numVer);
Graph myGraph2(numVer);
cout << "请输入" << numVer << "个顶点:\n";
for(i=0;i {
cout cin >> temp1;
myGraph1.setCh(temp1,i);
myGraph2.setCh(temp1,i);
}
cout << "请输入" << numE << "条弧:\n";
for(i=0;i {
cout cin >> temp1 >> temp2;
myGraph1.setEdge(temp1,temp2);
myGraph2.setEdge(temp1,temp2);
}

myGraph1.outPut();
while(1)
{

    cout<<"2:删除边 "<<endl;
    cout<<"3: 深度遍历"<<endl;
    cout<<"4: 广度遍历"<<endl;
    cout<<"0: 退出"<<endl;
    cout<<"\n请输入你的选择:";
    cin>>option;
    switch(option)
    {
    case'0':
        exit(0);
        break;

    case'2':
        {
            cout << "输入弧的顶点:"  << endl; 
            cin >> temp1 >> temp2; 
            myGraph1.eraserEdge(temp1,temp2); 
            myGraph2.eraserEdge(temp1,temp2); 
            myGraph1.outPut();
            break;
        }
    case'3':
        {
            cout << "深度优先结果:"; 
            DFS(&myGraph1,'a'); 
            cout<<endl;
            break;
        }
    case'4':
        {
            cout << "\n广度优先结果:";  
            //BFS(&myGraph2,'a',q); 
            cout<<endl;
            break;
        }
        cout<<endl;
    }

}cout<<endl;

}
void DFS(Graph* G,char ch) //深度优先遍历函数体
{

int i=0;
cout << ch << " ";
G->setMark(ch);
for(char w=G->first(ch);igetNumVertex();w=G->next(ch,w),i++)

if(G->getMark(w)==0)

DFS(G,w);
}
void BFS(Graph* G,char ch,myQueue* q) //广度优先遍历函数体
{
char v,w;
q->push(ch);
G->setMark(ch);
while(q->size()!=0)
{
q->pop(v);
cout << v << " ";

int i=0;
for(w=G->first(v);igetNumVertex();w=G->next(v,w),i++)

if(G->getMark(w)==0)

{

G->setMark(w);

q->push(w);
}
}
}

/*输入顶点数和弧数:8 9 输入8个顶点.

输入顶点0:a

输入顶点1:b

输入顶点2:c

输入顶点3:d

输入顶点4:e

输入顶点5:f

输入顶点6:g

输入顶点7:h

输入9条弧.

输入弧0:a b 1

输入弧1:b d 1

输入弧2:b e 1

输入弧3:d h 1

输入弧4:e h 1

输入弧5:a c 1

输入弧6:c f 1
输入弧7:c g 1

输入弧8:f g 1 */

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐