双向循环链表，C语言实现 |
您所在的位置：网站首页 › 实现双向循环链表倒置的程序 › 双向循环链表，C语言实现 |
双向循环链表，C语言实现
|
今天某家公司笔试题，遇到了一个双向循环链表。
调试后成功解决。文末附上完整程序。 定义结点是如下结构： struct node{ int val; struct node * next; struct node * prev; };next指针指向后一个结点，prev指向前一个结点 定义双向循环链表的结构如下 struct list{ int len; NODE* head; NODE* tail; };head指针指向虚拟头节点，tail指向虚拟尾结点，这两个结点用于标识头尾。这样当初始化一个链表后，链表示意图如下：
排序算法用基础的冒泡排序，基础操作是链表结点n1和n2交换，这里我使用四个指针变量，简化了编程中可能的复杂逻辑思考， 这四个变量存储两个待交换结点的前一个和后一个结点，交换即使得这两个结点的前一个和后一个结点变成对应的节点，即n1结点的前一个和后一个结点变成n2对应的前一个和后一个结点；n2如是。这里注意特殊情况是，待交换n1和n2结点相邻。通过简化可使得程序精简，这里为了便于理解不做简化。交换程序如下： void swap_element( NODE* n1 , NODE* n2 ){ NODE* n1_prev = n1->prev, *n1_next = n1->next; NODE* n2_prev = n2->prev, *n2_next = n2->next; if (n1_next != n2 && n1_prev!= n2 ){ //place n1 to n2 n1->next = n2_next; n2_next->prev = n1; n1->prev = n2_prev; n2_prev->next = n1; //place n2 to n1 n2->next = n1_next; n1_next->prev = n2; n2->prev = n1_prev; n1_prev->next = n2; } else{ if (n1_next == n2){ n1_prev->next = n2; n2->prev = n1_prev; n2->next = n1; n1->prev = n2; n1->next = n2_next; n2_next->prev = n1; }else{ n2_prev->next = n1; n1->prev = n2_prev; n1->next = n2; n2->prev = n1; n2->next = n1_next; n1_next->prev = n2; } } return; } 完整的程序如下： #include #include #define OK 0 #define ERR -1 #define status int struct node { int val; struct node* next; struct node* prev; }; typedef struct node NODE; struct list { int len; NODE* head; NODE* tail; }; typedef struct list LIST; //create list status list_create(LIST* ptr_list) { //create virtual head node NODE* dummy_head = (NODE*)malloc(sizeof(NODE)); //handle err if (dummy_head == NULL) { return ERR; } //create virtual tail node NODE* dummy_tail = (NODE*)malloc(sizeof(NODE)); //handle err if (dummy_tail == NULL) { free(dummy_head); return ERR; } //assign to ptr_list ptr_list->len = 0; ptr_list->head = dummy_head; ptr_list->tail = dummy_tail; //make loop ptr_list->head->next = ptr_list->tail; ptr_list->tail->prev = ptr_list->head; ptr_list->head->prev = ptr_list->tail; ptr_list->tail->next = ptr_list->head; return OK; } //add to list status list_insert(LIST* ptr_list, int val) { //create new node NODE* new_node = (NODE*)malloc(sizeof(NODE)); //handle err if (new_node == NULL) { return ERR; } //assign val to new node new_node->val = val; //make loop new_node->next = ptr_list->head->next; ptr_list->head->next->prev = new_node; ptr_list->head->next = new_node; new_node->prev = ptr_list->head; //adding nums ++ptr_list->len; return OK; } void swap_element(NODE* n1, NODE* n2) { NODE* n1_prev = n1->prev, * n1_next = n1->next; NODE* n2_prev = n2->prev, * n2_next = n2->next; if (n1_next != n2 && n1_prev != n2) { //place n1 to n2 n1->next = n2_next; n2_next->prev = n1; n1->prev = n2_prev; n2_prev->next = n1; //place n2 to n1 n2->next = n1_next; n1_next->prev = n2; n2->prev = n1_prev; n1_prev->next = n2; } else { if (n1_next == n2) { n1_prev->next = n2; n2->prev = n1_prev; n2->next = n1; n1->prev = n2; n1->next = n2_next; n2_next->prev = n1; } else { n2_prev->next = n1; n1->prev = n2_prev; n1->next = n2; n2->prev = n1; n2->next = n1_next; n1_next->prev = n2; } } return; } //sort list status list_sort(LIST* ptr_list) { if (ptr_list->head->next == ptr_list->tail || ptr_list->len == 1) { return OK; //null list or just one element; } //bubble sort for (NODE* j = ptr_list->tail->prev, *E = ptr_list->head; j->prev != E; j = j->prev) for (NODE* i = ptr_list->head->next; i != j; i = i->next) if (i->val > i->next->val) { if (i->next == j) { j = i; } swap_element(i, i->next); i = i->prev; } return OK; } //show list void show_list(LIST* ptr_list) { if (ptr_list->head->next == ptr_list->tail) { printf(" empty list ! \n"); return; } for (NODE* i = ptr_list->head->next; i != ptr_list->tail; i = i->next) printf(" %d", i->val); printf("\n"); return; } int main() { LIST test; if (list_create(&test) == ERR) { printf("crated failed\n"); return -1; } printf("list:"); show_list(&test); list_insert(&test, -2); list_insert(&test, 0); list_insert(&test, 2); list_insert(&test, 3); list_insert(&test, 1); list_insert(&test, 2); list_insert(&test, 1); list_insert(&test, 3); printf("list:"); show_list(&test); printf("sort list:\n"); list_sort(&test); //swap_element(test.tail->prev , test.tail->prev->prev); printf("list:"); show_list(&test); return 0; } 运行效果如下： |
【本文地址】
今日新闻 |
推荐新闻 |