資料結構›Ch4 鏈結串列第 10 題/共 22 題
10. Doubly Linked List、Debugging
#DS-04-010中Doubly Linked ListDebugging
- [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 鏈結串列