明明使用了pop(),但是并不能删除头元素，大小不发生变化？为什么呢？

Question

在主函数写个小测试是没问题的呀。下面是源代码：#include<iostream>using namespace std;#include<queue>class Graph{public: Graph(int v)//创建一个包含v个顶点但不包含边的图 { this->adjacent = new queue<int>[v]; this->V = v; this->E = 0; } int Vnum()//获取顶点的数量 { return this->V; } int Enum()//获取边的数量 { return this->E; } void addEdge(int v, int w)//向图中增加一条边 v-w { this->adjacent[v].push(w); this->adjacent[w].push(v); this->E++; } queue<int> adj(int v)//获取和顶点v相邻的所有顶点 { return this->adjacent[v]; }private: int V;//顶点数量 int E;//顶点边数量 queue<int> *adjacent;};class DepthFirstSearch{public: DepthFirstSearch(Graph G, int s) {//构件深度优先搜索对象，利用深度优先搜索找出G图中s顶点的所有相同顶点 this->marked = new bool[G.Vnum()]; for (int i = 0; i < G.Vnum(); ++i) { marked[i] = false; } this->N = 0; dfs(G, s); } void dfs(Graph G, int v)//利用深度优先搜索找出G中v顶点的所有相通顶点 { marked[v] = true; int w = G.adj(v).front(); while(!G.adj(v).empty())//找到v队列里的内容 { if (!marked[w]) { dfs(G, w); } cout << "队列大小："<<G.adj(v).size() << endl; G.adj(v).pop(); cout << "队列删除后的大小："<<G.adj(v).size() << endl; if (G.adj(v).empty() == 1) { break; } w = G.adj(v).front(); } this ->N++;//N加1 的位置放在当前节点变true的时候 } bool mark(int w)//判断w与s是否相通 { return marked[w]; } int count() { return N; }private: bool* marked;//索引代表顶点，值表示当前顶点是否已经被搜索 int N;//记录有多少个顶点与s顶点相同};void main(){ Graph g(13); g.addEdge(0, 6); g.addEdge(0, 2); g.addEdge(0, 1); g.addEdge(0, 6); g.addEdge(5, 3); g.addEdge(5, 4); g.addEdge(3, 4); g.addEdge(4, 6); g.addEdge(7, 8); g.addEdge(9, 10); g.addEdge(9, 12); g.addEdge(11, 12); g.addEdge(9, 11); DepthFirstSearch *DFS=new DepthFirstSearch(g, 0); int num= DFS->count(); cout << num << endl; /*queue<int> q; for (int i = 0; i < 5; i++) { q.push(i + 1); } cout << q.size() << endl; cout << q.empty() << endl; for (int i = 0; !q.empty(); i++) { q.pop(); } cout << q.size() << endl; cout << q.empty() << endl;*/ system("pause"); return;}

• 
  

Answer 1

问题在于你的queue<int> adj(int v) 函数返回的是一个queue的拷贝，而不是queue本身。改成queue <int>& adj(int v) //获取和顶点v相邻的所有顶点{return adjacent[v];}全部源码如下：#include<iostream>#include<queue>using namespace std;class Graph {public:Graph(int v) //创建一个包含v个顶点但不包含边的图{this -> adjacent = new queue < int > [v];this -> V = v;this -> E = 0;}int Vnum() //获取顶点的数量&nbsp;{return this -> V;}int Enum() //获取边的数量&nbsp;{return this -> E;}void addEdge(int v, int w)//向图中增加一条边 v-w&nbsp;{this -> adjacent[v].push(w);this -> adjacent[w].push(v);this -> E++;}queue <int>& adj(int v) //获取和顶点v相邻的所有顶点{return adjacent[v];}private:int V; //顶点数量&nbsp;int E; //顶点边数量&nbsp;queue < int > * adjacent;};class DepthFirstSearch {public:&nbsp;DepthFirstSearch(Graph G, int s) { //构件深度优先搜索对象，利用深度优先搜索找出G图中s顶点的所有相同顶点&nbsp;this -> marked = new bool[G.Vnum()];for (int i = 0; i < G.Vnum();++i) {marked[i] = false;}this -> N = 0;dfs(G, s);}void dfs(Graph G, int v) //利用深度优先搜索找出G中v顶点的所有相通顶点&nbsp;{marked[v] = true;int w = G.adj(v).front();while (!G.adj(v).empty()) //找到v队列里的内容&nbsp;{if (!marked[w]) {dfs(G, w);}cout << "队列大小：" << G.adj(v).size() << endl;G.adj(v).pop();cout << "队列删除后的大小：" << G.adj(v).size() << endl;if (G.adj(v).empty() == 1) {break;}w = G.adj(v).front();}this -> N++;//N加1 的位置放在当前节点变true的时候&nbsp;}bool mark(int w) //判断w与s是否相通&nbsp;{return marked[w];}int count() {return N;}private: bool * marked; //索引代表顶点，值表示当前顶点是否已经被搜索&nbsp;int N; //记录有多少个顶点与s顶点相同};int main() {Graph g(13);g.addEdge(0, 6);g.addEdge(0, 2);g.addEdge(0, 1);g.addEdge(0, 6);g.addEdge(5, 3);g.addEdge(5, 4);g.addEdge(3, 4);g.addEdge(4, 6);g.addEdge(7, 8);g.addEdge(9, 10);g.addEdge(9, 12);g.addEdge(11, 12);g.addEdge(9, 11);DepthFirstSearch * DFS = new DepthFirstSearch(g, 0);int num = DFS -> count();cout << num << endl;return 0;}