資料結構›Ch4 鏈結串列
第 10 題/共 22 題
◀ DS 10/22
10. Doubly Linked List、Debugging
#DS-04-010中Doubly Linked ListDebugging
  1. [10%] Binary Search Tree (原題標題如此印刷,惟本題實際內容為doubly linked list而非binary search tree) There are TWO BUGS in the following doubly linked list program. For each bug, please provide:
  • The line number where the bug occurs, and
  • The corrected solution in C.
1  #include <stdio.h>
2  #include <stdlib.h>
3  // Define the structure for a doubly linked list node
4  struct Node {
5      int data;                 // Data stored in the node
6      struct Node* prev;        // Pointer to the previous node
7      struct Node* next;        // Pointer to the next node
8  };
9  // Function to create a new node
10 struct Node* createNode(int data) {
11     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
12     newNode->data = data;
13     newNode->prev = NULL;
14     newNode->next = NULL;
15     return newNode;
16 }
17 void insertEnd(struct Node** head, int data) {
18     struct Node* newNode = createNode(data);
19     if (*head == NULL) {
20         *head = newNode; // If list is empty, new node becomes head
21         return;
22     }
23     struct Node* temp = *head;
24     while (temp->next != NULL) {
25         temp = temp->next; // Traverse to the last node
26     }
27     temp->next = newNode;
28 }
29 void deleteNode(struct Node** head, int key) {
30     struct Node* temp = *head;
31     // Traverse the list to find the node with the given key
32     while (temp != NULL && temp->data != key) {
33         temp = temp->next;
34     }
35     if (temp == NULL) {
36         printf("Node with value %d not found.\n", key);
37         return;
38     }
39     free(temp);
40     if (temp->prev == NULL) {
41         *head = temp->next;
42         if (*head != NULL) {
43             (*head)->prev = NULL;
44         }
45     } else {
46         temp->prev->next = temp->next;
47     }
48     if (temp->next != NULL) {
49         temp->next->prev = temp->prev;
50     }
51     printf("Node with value %d deleted.\n", key);
52 }
53 // Main function to test the doubly linked list
54 int main() {
55     struct Node* head = NULL;
56     // Insert nodes
57     insertEnd(&head, 10);
58     insertEnd(&head, 20);
59     // Delete a node
60     deleteNode(&head, 20);
61     return 0;
62 }
📄 交大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch4 鏈結串列
本章題號 · 1–20 / 22