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

rovol

1. /* priority_queue.h */
   
2. #ifndef PRIORITY_QUEUE_H
   
3. #define PRIORITY_QUEUE_H
   
4. 
   
5. #include <stdbool.h> /* Only C99 */
   
6. #include <stdint.h>  /* Only C99 */
   
7. 
   
8. // Numbers
   
9. #define PQUEUE_INIT_SIZE   10
   
10. #define PQUEUE_GROW_FACTOR 5
    
11. #define ERR_FLAG           -1
    
12. 
    
13. // Types and modifiers
    
14. #define PQUEUE_DATA_T      int
    
15. #define SUBSCRIPT_T        int
    
16. #define FLAG_T             int_least8_t
    
17. #define PUBLIC             /* There are not anything */
    
18. #define PRIVATE            static
    
19. 
    
20. typedef struct {
    
21.     size_t         cap;
    
22.     size_t         size;
    
23.     PQUEUE_DATA_T *node;
    
24. } pqueue_t;
    
25. 
    
26. /* heap:
    
27. *       1>0
    
28. *    2>1   3>2
    
29. * 4>3 5>4 6>5 7->6
    
30. * array subscript:
    
31. * [1, 2, 3, 4, 5, 6, 7] (up to down, right to left)
    
32. * parent: i, left son node: 2i + 1, right son node: 2i + 2
    
33. */
    
34. 
    
35. PUBLIC  bool          priority_queue_init(pqueue_t *pqueue);
    
36. PUBLIC  bool          priority_queue_ins(pqueue_t *pqueue, PQUEUE_DATA_T data);
    
37. PUBLIC  PQUEUE_DATA_T priority_queue_del(pqueue_t *pqueue);
    
38. PUBLIC  bool          priority_queue_des(pqueue_t *pqueue);
    
39. PRIVATE bool          is_empty(pqueue_t *pqueue);
    
40. PRIVATE bool          is_full(pqueue_t *pqueue);
    
41. 
    
42. #endif /* PRIORITY_QUEUE__H */
    

复制代码

1. 
   
2. /* priority_queue.c */
   
3. #include <stdlib.h>
   
4. #include <limits.h>
   
5. #include "priority_queue.h"
   
6. 
   
7. PUBLIC bool priority_queue_init(pqueue_t *pqueue) {
   
8.     pqueue->node = (PQUEUE_DATA_T *) malloc(PQUEUE_INIT_SIZE * sizeof (PQUEUE_DATA_T));
   
9.     if (pqueue->node == NULL)
   
10.         return false;
    
11.     pqueue->cap  = PQUEUE_INIT_SIZE;
    
12.     pqueue->size = 0;
    
13.     return true;
    
14. }
    
15. 
    
16. PUBLIC bool priority_queue_ins(pqueue_t *pqueue, PQUEUE_DATA_T data) {
    
17.     FLAG_T ret;
    
18.     int i;
    
19.     if (ret = is_full(pqueue)) {
    
20.         pqueue->cap *= PQUEUE_GROW_FACTOR;
    
21.         pqueue->node = (PQUEUE_DATA_T *) realloc(pqueue->node, pqueue->cap * sizeof (PQUEUE_DATA_T));
    
22.         if (pqueue->node == NULL)
    
23.             return false;
    
24.     }
    
25.     if (ret == ERR_FLAG)
    
26.         return false;
    
27.    
    
28.     i = pqueue->size++;
    
29.     while (i > 0) {
    
30.         int parent = (i - 2) / 2;
    
31.         if (data < pqueue->node[parent]) {
    
32.             pqueue->node[i] = pqueue->node[parent];
    
33.             i = parent;
    
34.         } else
    
35.             break;
    
36.     }
    
37.     /* i / 2 - 1 || i / 2 - 2: Compute parent node. */
    
38.     pqueue->node[i] = data;
    
39.     return true;
    
40. }
    
41. 
    
42. PUBLIC PQUEUE_DATA_T priority_queue_del(pqueue_t *pqueue) {
    
43.     if (is_empty(pqueue))
    
44.         return INT_MAX;
    
45.    
    
46.     PQUEUE_DATA_T root = pqueue->node[0];
    
47.     pqueue->node[0]    = pqueue->node[pqueue->size - 1];
    
48.     pqueue->size--;
    
49.    
    
50.     int i = 0;
    
51.     while (i * 2 + 1 < pqueue->size) {
    
52.         int minson = i * 2 + 1;
    
53.         if (minson + 1 < pqueue->size && pqueue->node[minson] > pqueue->node[minson + 1])
    
54.             minson++;
    
55.         if (pqueue->node[i] > pqueue->node[minson]) {
    
56.             pqueue->node[i] = pqueue->node[minson];
    
57.             i = minson;
    
58.         } else
    
59.             break;
    
60.     }
    
61.    
    
62.     return root;
    
63. }
    
64. 
    
65. PUBLIC bool priority_queue_des(pqueue_t *pqueue) {
    
66.     if (pqueue == NULL)
    
67.         return false;
    
68.         
    
69.     free(pqueue->node);
    
70.     pqueue->node = NULL;
    
71.     pqueue->cap  = 0;
    
72.     pqueue->size = 0;
    
73.     return true;
    
74. }
    
75. 
    
76. PRIVATE bool is_empty(pqueue_t *pqueue) {
    
77.     if (pqueue == NULL)
    
78.         return ERR_FLAG;
    
79.     else if (pqueue->size == 0)
    
80.         return true;
    
81.     else
    
82.         return false;
    
83. }
    
84. 
    
85. PRIVATE bool is_full(pqueue_t *pqueue) {
    
86.     if (pqueue == NULL)
    
87.         return ERR_FLAG;
    
88.     else if (pqueue->size == pqueue->cap)
    
89.         return true;
    
90.     else
    
91.         return false;
    
92. }
    

复制代码

1. 
   
2. /* priotity_queue_client.c */
   
3. #include <stdio.h>
   
4. #include "priority_queue.h"
   
5. 
   
6. int main(void) {
   
7.     pqueue_t *pqueue;
   
8.     priority_queue_init(pqueue);
   
9.    
   
10.     for (int i = 0; i < 100; i++)
    
11.         priority_queue_ins(pqueue, i);
    
12.     for (int i = 0; i < pqueue->size; i++)
    
13.         printf("%d\n", pqueue->node[i]);
    
14.    
    
15.     priority_queue_des(pqueue);
    
16.     return 0;
    
17. }
    

复制代码

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

环境：
Ubuntu 22.04.4 LTS
gcc：

1. 
   
2. Using built-in specs.
   
3. COLLECT_GCC=gcc
   
4. COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/11/lto-wrapper
   
5. OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa
   
6. OFFLOAD_TARGET_DEFAULT=1
   
7. Target: x86_64-linux-gnu
   
8. 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
   
9. Thread model: posix
   
10. Supported LTO compression algorithms: zlib zstd
    
11. 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`指针分配内存空间。可以改为使用如下代码：

1. pqueue_t pqueue;
   
2. priority_queue_init(&pqueue);

复制代码

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

1. pqueue->node = pqueue->node;

复制代码

应该将其改为：

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

复制代码

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

1. pqueue->node = data;

复制代码

改为：

1. pqueue->node[i] = data;

复制代码

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

1. pqueue->node = pqueue->node;

复制代码

应该将其改为：

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

复制代码

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

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

跳转到最佳答案楼层

FishC

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

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

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

1. pqueue_t pqueue;
   
2. priority_queue_init(&pqueue);

复制代码

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

1. pqueue->node = pqueue->node;

复制代码

应该将其改为：

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

复制代码

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

1. pqueue->node = data;

复制代码

改为：

1. pqueue->node[i] = data;

复制代码

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

1. pqueue->node = pqueue->node;

复制代码

应该将其改为：

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

复制代码

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

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