c-当我运行下面的代码时，我得到了分段错误/错误

Question

我是C的新手。当我在在线C编译器中运行下面的图遍历算法程序时，我遇到了一个分段错误。我知道错误是由于访问未初始化或不可访问的内存造成的，但我不知道错误发生在哪里。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define max 5
struct vertex{
char name;
bool isVisited;
};
int queue[max];
int rear = -1, front = 0, queueCount = 0, vertexCount = 0;
struct vertex* adjList[max];
int adjMat[max][max];
void insert(int data){
queue[++rear] = data;
queueCount++;
}
int delete(){
queueCount--;
return queue[front++];
}
bool isEmpty(){
return queueCount == 0;
}
void addVertex(char name){
struct vertex* v = (struct vertex*)malloc(sizeof(struct vertex));
v->name = name;
v->isVisited = false;
adjList[vertexCount++] = v;
}
void addEdge(int start, int end){
adjMat[end][start] = 1;
adjMat[start][end] = 1;
}
void display(int vertexIndex){
printf("%c", adjList[vertexIndex]->name);
}
int getAdjUnvisitedVertices(int vertexIndex){
for (int i = 0; i < vertexCount; i++){
if (adjMat[vertexIndex][i] == 1 && adjList[i]->isVisited == false){
return i;
}
}
return -1;
}
void BFS(){
adjList[0]->isVisited = true;
display(0);
insert(0);
int unvisitedVertex;
while (!isEmpty()){
int tempVertex = delete();
while (unvisitedVertex = getAdjUnvisitedVertices(tempVertex) != -1){
adjList[unvisitedVertex]->isVisited = true;
display(unvisitedVertex);
insert(unvisitedVertex);
}
}
for (int i = 0; i < vertexCount; i++){
adjList[i]->isVisited = false;
}
}
void main(){
for (int i = 0; i < max; i++){
for (int j = 0; j < max; j++){
adjMat[i][j] = 0;
}
}
addVertex('S');
addVertex('A');
addVertex('B');
addVertex('C');
addVertex('D');
addEdge(0,1);
addEdge(0,2);
addEdge(0,3);
addEdge(1,4);
addEdge(2,4);
addEdge(3,4);
printf("Breadth First Traversal : ");
BFS();
}

Answer 1

使用gcc -g -fsanitize=address a.c && ./a.out会导致：

=================================================================
==2590725==ERROR: AddressSanitizer: global-buffer-overflow on address 0x563fc7b38394 at pc 0x563fc7b35262 bp 0x7ffe7e7fd600 sp 0x7ffe7e7fd5f8
WRITE of size 4 at 0x563fc7b38394 thread T0
#0 0x563fc7b35261 in insert /tmp/a.c:14
#1 0x563fc7b35839 in BFS /tmp/a.c:55
#2 0x563fc7b35a89 in main /tmp/a.c:80
#3 0x7fe91f032e49 in __libc_start_main ../csu/libc-start.c:314
#4 0x563fc7b35139 in _start (/tmp/a.out+0x1139)
0x563fc7b38394 is located 0 bytes to the right of global variable 'queue' defined in 'a.c:9:5' (0x563fc7b38380) of size 20
0x563fc7b38394 is located 44 bytes to the left of global variable 'front' defined in 'a.c:10:16' (0x563fc7b383c0) of size 4

第14行是：

queue[++rear] = data;

因此，在问题点上，rear指数超过了5。

Answer 2

此处发生无限循环，导致数组边界异常。原因是未执行赋值语句。

while (unvisitedVertex = getAdjUnvisitedVertices(tempVertex) != -1)

为了确保赋值操作与条件运算符一起进行，它需要加括号。

while ((unvisitedVertex = getAdjUnvisitedVertices(tempVertex)) != -1)

通过此更改，结果是宽度优先遍历：SABCD