使用双向链表实现冒泡算法

### 双向链表实现冒泡排序 双向链表是一种每个节点不仅包含指向下一个节点的指针，还包含指向上一个节点的指针的数据结构。利用这种特性可以更方便地在链表中进行前后遍历操作。 以下是基于不带头结点的非循环双向链表实现冒泡排序的具体方法[^1]： #### 数据结构定义 首先定义双向链表的节点结构以及初始化函数： ```c typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; // 创建新节点 Node* create_node(int value) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = value; new_node->prev = NULL; new_node->next = NULL; return new_node; } ``` #### 插入节点 为了构建完整的双向链表，需要提供插入功能以便将多个节点连接起来形成列表。 ```c void insert_at_end(Node** head_ref, int new_data) { Node* new_node = create_node(new_data); if (*head_ref == NULL) { *head_ref = new_node; return; } Node* last = *head_ref; while (last->next != NULL) { last = last->next; } last->next = new_node; new_node->prev = last; } ``` #### 冒泡排序逻辑 通过比较相邻两个节点中的`data`字段大小来进行交换位置的操作直到整个序列有序为止。 ```c void bubble_sort_double_linked_list(Node** head_ref) { bool swapped; Node* current; Node* lptr = NULL; // Last pointer used to reduce the number of comparisons do { swapped = false; current = *head_ref; while (current->next != lptr) { // Traverse until one before last item sorted if (current->data > current->next->data) { swap_nodes(current, current->next); // Swap nodes' values or pointers as needed. swapped = true; } current = current->next; } lptr = current; // Move boundary forward after each pass } while (swapped); } // Helper function for swapping two adjacent nodes within a doubly linked list by their 'data'. void swap_nodes(Node* node1, Node* node2){ int temp = node1->data; node1->data = node2->data; node2->data = temp; } ``` 以上代码展示了如何使用C语言编写一个简单的双向链表并对其进行冒泡排序的过程[^1]。需要注意的是这里仅交换了节点内的数值而非实际改变链接关系；如果希望调整物理地址上的顺序，则需修改相应部分以重新分配前驱与后继的关系。 另外还可以考虑采用局部冒泡策略进一步优化效率，在每次发现逆序对时立即执行小范围内的整理动作从而减少总体迭代次数[^2]。 最后附上一段测试用例帮助理解整体流程： ```c int main() { Node* head = NULL; insert_at_end(&head, 5); insert_at_end(&head, 3); insert_at_end(&head, 8); insert_at_end(&head, 6); printf("Original List:\n"); print_list(head); bubble_sort_double_linked_list(&head); printf("\nSorted List:\n"); print_list(head); free_list(head); return 0; } ```