벡터의 크기에 대한 분할 오류

간단한 Dijkstra 문제를 시도하고 벡터의 배열로 내 인접 목록을 표현하기로했습니다. 각 배열은 한 쌍의 (정점, 거리)를 포함합니다. 나는 이것을 다음과 같이 선언했다. vector<pair<int, int> > G[MAXV]; 문제는, 주어진 꼭지점 (즉, 벡터의 크기)에 연결된 엣지의 수를 얻으려고하면 세그먼테이션 결함이 생기는 것이다. 이것은 오류가 발생하는 행입니다. vectorSize=G[currentVertex-1].size(); 대괄호 사이의 인수를 0 (즉, 첫 번째 벡터)으로 이미 변경했기 때문에 문제가 currentVertex라고 생각하지 않으며 여전히 seg 오류가 발생합니다. 모든 제안을 주셔서 감사합니다. 다음은 완전한 소스 코드입니다.벡터의 크기에 대한 분할 오류

#include <cstdio> 
#include <vector> 
#include <queue> 
#include <limits> 
#include <utility> 
#define MAXV 10000 
#define infinity std::numeric_limits<int>::max() 

using namespace std; 

int main() 
{ 
    vector<pair<int, int> > G[MAXV]; 
    int numCases; 
    int a, b, c; 
    int A, B; 
    int V, K; 
    bool vis[MAXV]; 
    pair<int, int> temp; 
    pair<int, int> vertexAndDistance[MAXV]; 
    priority_queue<pair<int, int>, vector< pair<int, int> >, greater<pair<int, int> > > heap; 
    pair<int, int> top; 
    int currentVertex; 
    int currentDistance; 
    int vectorSize; 

    for (int i=0; i<MAXV; i++) 
    { 
     vertexAndDistance[i].second=i+1; 
    } 

    scanf(" %d", &numCases); 
    for (int i=0; i<numCases; i++) 
    { 
     scanf(" %d %d", &V, &K); 
     for (int j=0; j<K; j++) 
     { 
      scanf("%d %d %d", &a, &b, &c); 
      temp.first=c; 
      temp.second=b; 
      G[a-1].push_back(temp); 
     } 
     scanf ("%d %d", &A, &B); 

     for (int k=0; k<V; k++) 
      vis[i]=false; 
     for (int k=0; k<V; k++) 
      vertexAndDistance[k].first=infinity; 
     vertexAndDistance[A-1].first=0; 
     heap.push(vertexAndDistance[A-1]); 

     while(true) 
     { 
      top = heap.top(); 
      currentDistance = top.first; 
      currentVertex = top.second; 
      heap.pop(); 
      if (infinity == currentDistance || B==currentVertex) break; 
//   vis[currentVertex-1]=true; 
      vectorSize=G[currentVertex-1].size(); 
      for (unsigned int k=0;!heap.empty() && k<vectorSize; k++) 
//   tr (G[currentVertex], it) 
      { 
       if (vertexAndDistance[G[currentVertex][k].second-1].first > vertexAndDistance[A-1].first + G[currentVertex][k].first) 
       { 
        vertexAndDistance[G[currentVertex][k].second-1].first = vertexAndDistance[A-1].first + G[currentVertex][k].first; 
        heap.push(vertexAndDistance[G[currentVertex][k].second]); 
       } 
      } 
     } 
     if (infinity > vertexAndDistance[B-1].first) 
      printf("%d", vertexAndDistance[B-1].first); 
     else 
      printf("NO"); 
    } 
return 0; 
}

출처

2013-11-24 rvcam

'벡터 <쌍 > G [MAXV];'지금까지 아무것도 포함하지 않은 초기화 된'std :: vector' 객체들의 배열을 선언 했습니까? –

@ g-makulik 예, 코드에서 OP가 알고있는 것 같습니다. 그러나 그러한 혼란스러운 선언은 종종 버그를 유발합니다. –

@ g-makulik 그 쌍의 배열입니다 :) –

일반적으로 seg 결함이있는 것은 잘못된 메모리 영역에 액세스하려고했기 때문입니다. G [currentVertex-1]이 존재하지 않으면 (currentVertex> max 또는 == 0) 또는 heap.top이 잘못된 값 (NULL 일 수도 있음)을 반환하면

출처

2013-11-24 17:19:02 Ice

벡터의 크기에 대한 분할 오류

답변

관련 문제