Tôi đang thực hiện một nhiệm vụ liên quan đến việc triển khai các hàng đợi chứa con trỏ null để chúng có thể được khái quát hóa cho bất kỳ loại dữ liệu nào. Tôi hiện đang gặp phải một sự cố lạ khi việc xếp hàng các nút làm giảm kích thước của danh sách nhưng không trả về các nút mà tôi mong đợi. Việc bỏ lệnh gọi free() trong thao tác dequeue sẽ khắc phục được điều này, nhưng vì tôi muốn giải phóng nút dequeue nên điều này là không nên. Có gợi ý gì không?

Chạy thử: thường lệ.c

#include 
#include 
#include 
#include "queue.h"

int chính() {
  kiểm tra hàng đợi = make_queue();
  enqueue("Một", kiểm tra);
  enqueue("Hai", test);
  printf("Mục là %s!\n", (char *)dequeue(test));
  printf("Mục là %s!\n", (char *)dequeue(test));
  return 0;
}

hàng đợi.h

#include 
#include 
#include 
/* Hàng đợi được triển khai dưới dạng con trỏ tới cấu trúc không được chỉ định ở đây */

typedef struct queue_structure *queue;

nút cấu trúc {
  nút cấu trúc * tiếp theo;
  làm mất hiệu lực dữ liệu *;
};

cấu trúc hàng_cấu trúc {
  nút cấu trúc * đầu;
  nút cấu trúc * đuôi;
};

/* Danh sách các giao thức chức năng */
bool is_empty_queue(hàng q);

/* Hàm make_queue trả về một hàng đợi mới được tạo không có giá trị
   được lưu trữ trong đó.
*/

xếp hàng make_queue() {
  xếp hàng newQueue = malloc(sizeof(struct queue_structure));
  trả về hàng đợi mới;
}

/* Hàm enqueue thêm một giá trị vào hàng đợi.
   không thay đổi con trỏ q, các trường của cấu trúc mà q
   điểm có thể được sửa đổi trong quá trình gọi hàm này.
*/

void enqueue(void *value, queue q) {
  nút cấu trúc * newNode = (nút cấu trúc *)malloc(sizeof(nút cấu trúc));
  newNode->data = value;    
  if(is_empty_queue(q))
    q->tail = newNode;
  newNode->next = q->head;
  q->head = newNode;
}

/* Hàm dequeue loại bỏ một giá trị khỏi hàng đợi và trả về giá trị đó.
   Mặc dù hàm này không thay đổi con trỏ q, nhưng các trường của
   cấu trúc mà q điểm có thể được sửa đổi trong quá trình gọi tới
   chức năng này.

   Điều kiện tiên quyết của hàm này là ít nhất một giá trị được lưu trữ
   trong hàng đợi.
*/

void *dequeue(queue q) {
  if(!q->head->next) { // Chỉ có một mục duy nhất trong hàng đợi.
    printf("Chỉ có một mục trong hàng đợi!\n");
    nút cấu trúc * to_dequeue = q->tail;
    void * data = q->head->data;
    miễn phí(to_dequeue);
    q->đầu = NULL;
    q->đuôi = NULL;
    trả về dữ liệu;
  }
  else { // Nhiều mục trong hàng đợi.
    printf("Một số mục trong hàng đợi!\n");
    nút cấu trúc * to_dequeue = q->tail;
    void * data = q->tail->data;
    nút cấu trúc * trace = q->head;
    while(trace->next && trace->next != q->tail)
      dấu vết = dấu vết->tiếp theo;
    miễn phí(to_dequeue);
    q->đuôi = dấu vết;
    q->tail->next = NULL;
    trả về dữ liệu;
  }
}

/* Hàm front_of_queue trả về giá trị ở đầu hàng đợi
   (nghĩa là cái ít được thêm vào hàng đợi gần đây nhất) mà không xóa
   giá trị đó từ hàng đợi Nó không có tác dụng phụ.

   Điều kiện tiên quyết của hàm này là ít nhất một giá trị được lưu trữ
   trong hàng đợi.
*/

void *front_of_queue(queue q) {
  trả về q->head->dữ liệu;
}

/* Hàm is_empty_queue xác định xem hàng đợi có trống không,
   trả về giá trị Boolean thực nếu không có giá trị nào được lưu trong hàng đợi
   và giá trị Boolean sai nếu một hoặc nhiều giá trị được lưu trữ trong
   xếp hàng.
*/

bool is_empty_queue(queue q) {
  nếu(q->đầu)
    return 1;
  return 0;
}

câu trả lời hay nhất

bạn không ở trong make_queue trung tướng head Và tail khởi tạo thành NULL và bạn đã thực hiện sai phép thử vô hiệu,

bool is_empty_queue(queue q) {
  nếu(q->đầu)
    return 1;
  return 0;
}

Điều này làm cho xếp hàng Hành vi bất thường.

void enqueue(void *value, queue q) {
  nút cấu trúc * newNode = (nút cấu trúc *)malloc(sizeof(nút cấu trúc));
  newNode->data = value;    
  if(is_empty_queue(q))
    q->tail = newNode;
  newNode->next = q->head;
  q->head = newNode;
}

Trường hợp 1, có thể head Và tail Ban đầu nó là NULL

đầu -> 0; đuôi -> 0 // bây giờ xếp hàng 1
is_empty_queue(q) trả về 0 vì q->head == NULL, vì vậy q->tail vẫn trỏ đến 0
n(1)->tiếp theo = 0
đầu = n(1)

kết quả là
đầu -> n(1) -> 0; đuôi -> 0 // dãy tiếp theo 2
is_empty_queue(q) trả về 1 vì q->head = n(1) != 0, vì vậy
q->đuôi = n(2)
n(2)->tiếp theo = n(1)
q->đầu = n(2)

kết quả:
đầu -> n(2) -> n(1) -> 0; đuôi -> n(2)

tất cả hơn nữaTham gia vào độiHoạt động sẽ rời điđầu == đuôi. Tuy nhiên, nếu bây giờ bạn xếp hàng:

nút cấu trúc * to_dequeue = q->tail; // n(2)
void * data = q->tail->data;
nút cấu trúc * trace = q->head; // n(2)
while(trace->next && trace->next != q->tail) // n(2) -> n(1) -> 0
  dấu vết = dấu vết->tiếp theo; // dấu vết = n(1)
miễn phí(to_dequeue); // miễn phí n(2)
q->đuôi = dấu vết; // đuôi -> n(1)
q->tail->next = NULL // đã có cái đó rồi

head là một con trỏ lơ lửng.

Kịch bản 2, có thể xảy ra head Không phải ban đầu NULL.

đầu -> x; đuôi -> y // enqueue 1
is_empty_queue(q) trả về 1 vì q->head == x != 0
q->đuôi = n(1)
n(1)->tiếp theo = x
q->đầu = n(1)

đầu -> n(1) -> x; đuôi -> n(1) // bây giờ xếp hàng 2
is_empty_queue(q) trả về 1 vì q->head == n(1)
q->đuôi = n(2)
n(2)->tiếp theo = n(1)
q->đầu = n(2)

đầu -> n(2) -> n(1) -> x; đuôi -> n(2)

Sự khác biệt duy nhất là bây giờ n(1)->tiếp theo != 0, và sau đó nếu bạn hủy hàng đợi,dấu vết sẽ được đặt thành "con trỏ" hoang dãx sau đó kiểm tra x-> tiếp theo, nhưng bởi vì x là mẫu bit không xác định, thường dẫn đến lỗi phân tách.

Trừ khi tôi đang xem xét điều gì đó, hãy khởi tạo khi xây dựng head Và tail,Sửa chữa is_empty_queue 并检查 xếp hàng Nếu trống > sẽ cung cấp cho bạn một kế hoạch làm việc.

Nhưng nếu hàng đợi dài thì thao tác dequeue sẽ chậm vì phải duyệt toàn bộ hàng đợi để tìm phần tử thứ hai đến cuối cùng để cập nhậttail. bạn có thể có cả haixếp hàngVàxếp hàng, nếu bạn làtailVị trí hàng đợi vàxếp hàng, thao tác O(1) > từ head.

Về c - xếp hàng/xếp hàng kỳ lạ? , chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/9029323/