[已解决]【C语言】优先队列 段错误

rovol

/* priority_queue.h */
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include <stdbool.h> /* Only C99 */
#include <stdint.h>  /* Only C99 */

// Numbers
#define PQUEUE_INIT_SIZE   10
#define PQUEUE_GROW_FACTOR 5
#define ERR_FLAG           -1

// Types and modifiers
#define PQUEUE_DATA_T      int
#define SUBSCRIPT_T        int
#define FLAG_T             int_least8_t
#define PUBLIC             /* There are not anything */
#define PRIVATE            static

typedef struct {
    size_t         cap;
    size_t         size;
    PQUEUE_DATA_T *node;
} pqueue_t;

/* heap:
 *       1>0
 *    2>1   3>2
 * 4>3 5>4 6>5 7->6
 * array subscript:
 * [1, 2, 3, 4, 5, 6, 7] (up to down, right to left)
 * parent: i, left son node: 2i + 1, right son node: 2i + 2
 */

PUBLIC  bool          priority_queue_init(pqueue_t *pqueue);
PUBLIC  bool          priority_queue_ins(pqueue_t *pqueue, PQUEUE_DATA_T data);
PUBLIC  PQUEUE_DATA_T priority_queue_del(pqueue_t *pqueue);
PUBLIC  bool          priority_queue_des(pqueue_t *pqueue);
PRIVATE bool          is_empty(pqueue_t *pqueue);
PRIVATE bool          is_full(pqueue_t *pqueue);

#endif /* PRIORITY_QUEUE__H */

/* priority_queue.c */
#include <stdlib.h>
#include <limits.h>
#include "priority_queue.h"

PUBLIC bool priority_queue_init(pqueue_t *pqueue) {
    pqueue->node = (PQUEUE_DATA_T *) malloc(PQUEUE_INIT_SIZE * sizeof (PQUEUE_DATA_T));
    if (pqueue->node == NULL)
        return false;
    pqueue->cap  = PQUEUE_INIT_SIZE;
    pqueue->size = 0;
    return true;
}

PUBLIC bool priority_queue_ins(pqueue_t *pqueue, PQUEUE_DATA_T data) {
    FLAG_T ret;
    int i;
    if (ret = is_full(pqueue)) {
        pqueue->cap *= PQUEUE_GROW_FACTOR;
        pqueue->node = (PQUEUE_DATA_T *) realloc(pqueue->node, pqueue->cap * sizeof (PQUEUE_DATA_T));
        if (pqueue->node == NULL)
            return false;
    }
    if (ret == ERR_FLAG)
        return false;
    
    i = pqueue->size++;
    while (i > 0) {
        int parent = (i - 2) / 2;
        if (data < pqueue->node[parent]) {
            pqueue->node[i] = pqueue->node[parent];
            i = parent;
        } else
            break;
    }
    /* i / 2 - 1 || i / 2 - 2: Compute parent node. */
    pqueue->node[i] = data;
    return true;
}

PUBLIC PQUEUE_DATA_T priority_queue_del(pqueue_t *pqueue) {
    if (is_empty(pqueue))
        return INT_MAX;
    
    PQUEUE_DATA_T root = pqueue->node[0];
    pqueue->node[0]    = pqueue->node[pqueue->size - 1];
    pqueue->size--;
    
    int i = 0;
    while (i * 2 + 1 < pqueue->size) {
        int minson = i * 2 + 1;
        if (minson + 1 < pqueue->size && pqueue->node[minson] > pqueue->node[minson + 1])
            minson++;
        if (pqueue->node[i] > pqueue->node[minson]) {
            pqueue->node[i] = pqueue->node[minson];
            i = minson;
        } else
            break;
    }
    
    return root;
}

PUBLIC bool priority_queue_des(pqueue_t *pqueue) {
    if (pqueue == NULL)
        return false;
        
    free(pqueue->node);
    pqueue->node = NULL;
    pqueue->cap  = 0;
    pqueue->size = 0;
    return true;
}

PRIVATE bool is_empty(pqueue_t *pqueue) {
    if (pqueue == NULL)
        return ERR_FLAG;
    else if (pqueue->size == 0)
        return true;
    else
        return false;
}

PRIVATE bool is_full(pqueue_t *pqueue) {
    if (pqueue == NULL)
        return ERR_FLAG;
    else if (pqueue->size == pqueue->cap)
        return true;
    else
        return false;
}

/* priotity_queue_client.c */
#include <stdio.h>
#include "priority_queue.h"

int main(void) {
    pqueue_t *pqueue;
    priority_queue_init(pqueue);
    
    for (int i = 0; i < 100; i++)
        priority_queue_ins(pqueue, i);
    for (int i = 0; i < pqueue->size; i++)
        printf("%d\n", pqueue->node[i]);
    
    priority_queue_des(pqueue);
    return 0;
}

输出：
段错误 (核心已转储)

环境：
Ubuntu 22.04.4 LTS
gcc：

Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/11/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 11.4.0-1ubuntu1~22.04' --with-bugurl=file:///usr/share/doc/gcc-11/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-11 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --enable-cet --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-11-XeT9lY/gcc-11-11.4.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-11-XeT9lY/gcc-11-11.4.0/debian/tmp-gcn/usr --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-serialization=2
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04)

有没有大佬帮忙看一下错在那啊ToT

最佳答案

月排行榜 / 总排行榜

FishC

2024-4-27 21:45:09

在您提供的代码中，存在几个问题导致段错误：

1. 在`priority_queue_client.c`文件中，您定义了一个指向`pqueue_t`类型的指针`pqueue`，但是没有为其分配内存空间。这导致在调用`priority_queue_init(pqueue)`函数时，会访问未初始化的指针，从而导致段错误。

解决方法：为`pqueue`指针分配内存空间。可以改为使用如下代码：

pqueue_t pqueue;
priority_queue_init(&pqueue);

2. 在`priority_queue_ins`函数中，存在一处错误的赋值操作。以下代码是有问题的：

pqueue->node = pqueue->node;

应该将其改为：

pqueue->node[i] = pqueue->node[parent];

另外，还需要修改以下代码：

pqueue->node = data;

改为：

pqueue->node[i] = data;

3. 在`priority_queue_del`函数中，存在一处错误的赋值操作。以下代码是有问题的：

pqueue->node = pqueue->node;

应该将其改为：

pqueue->node[i] = pqueue->node[minson];

修复以上问题后，您的代码应该能够正常运行。希望对您有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

在您提供的代码中，存在几个问题导致段错误：

1. 在`priority_queue_client.c`文件中，您定义了一个指向`pqueue_t`类型的指针`pqueue`，但是没有为其分配内存空间。这导致在调用`priority_queue_init(pqueue)`函数时，会访问未初始化的指针，从而导致段错误。

解决方法：为`pqueue`指针分配内存空间。可以改为使用如下代码：

pqueue_t pqueue;
priority_queue_init(&pqueue);

2. 在`priority_queue_ins`函数中，存在一处错误的赋值操作。以下代码是有问题的：

pqueue->node = pqueue->node;

应该将其改为：

pqueue->node[i] = pqueue->node[parent];

另外，还需要修改以下代码：

pqueue->node = data;

改为：

pqueue->node[i] = data;

3. 在`priority_queue_del`函数中，存在一处错误的赋值操作。以下代码是有问题的：

pqueue->node = pqueue->node;

应该将其改为：

pqueue->node[i] = pqueue->node[minson];

修复以上问题后，您的代码应该能够正常运行。希望对您有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。