c/c++ 线性表之双向循环链表
程序员文章站
2022-06-17 08:21:46
c/c++ 线性表之双向循环链表 线性表之双向循环链表 不是存放在连续的内存空间,链表中的每个节点的next都指向下一个节点,每个节点的before都指向前一个节点,最后一个节点的下一个节点不是NULL,是头节点。 真实的第一个节点是头节点,头节点不存放数据,单纯为了编写程序方便。但是下面注释里写的 ......
c/c++ 线性表之双向循环链表
线性表之双向循环链表
不是存放在连续的内存空间,链表中的每个节点的next都指向下一个节点,每个节点的before都指向前一个节点,最后一个节点的下一个节点不是NULL,是头节点。
真实的第一个节点是头节点,头节点不存放数据,单纯为了编写程序方便。但是下面注释里写的【第一个节点】的含义是头节点的下一节点,也就是真实存放数据的第一个节点。
下面的代码实现了以下功能
函数 | 功能描述 |
---|---|
push_back | 从链表的最后插入节点 |
push_front | 从链表的起始插入节点 |
show_list | 打印出链表里每个节点的值 |
pop_back | 删除链表最后一个节点 |
pop_front | 删除链表起始节点 |
insert_val | 在合适的位置插入一个节点; 比如原来的链表:1->3->NULL,当要插入的节点的值为2的时候,就会在1和3之间插入这个节点,插入后的链表:1->2->3->NULL |
find | 查找指定的节点 |
length | 返回链表中节点的个数 |
delete_val | 删除指定的节点 |
sort | 排序,重新排列节点 |
resver | 按倒序,重新排列节点 |
clear | 释放除了头节点之外的所有节点所占用的内存空间 |
destroy | 释放所有节点的所占用的内存空间,包括头节点 |
whileshuangnode.h
#ifndef __WHILESHUANGNODE__ #define __WHILESHUANGNODE__ #include <stdio.h> #include <malloc.h> #include <assert.h> #include <memory.h> #include <stdbool.h> #define ElemType int typedef struct Node{ ElemType data; struct Node* before; struct Node* next; }Node; typedef struct NodeList{ Node* first; Node* last; size_t size; }NodeList; void init(NodeList*); void push_back(NodeList*, ElemType); void push_front(NodeList*, ElemType); void pop_back(NodeList*); void pop_front(NodeList*); void show_list(NodeList*); void insert_val(NodeList*, ElemType); Node* find(NodeList*, ElemType); void delete_val(NodeList*, ElemType); void sort(NodeList*); void sort1(NodeList*); void resver(NodeList*); void resver1(NodeList*); void resver2(NodeList*); void clear(NodeList*); void destroy(NodeList*); #endif
whileshuangnode.c
#include "whileshuangnode.h" void init(NodeList* list){ list->first = (Node*)malloc(sizeof(Node)); list->last = list->first; list->first->before = list->last; list->last->next = list->first; list->size = 0; } Node* create_node(ElemType val){ Node* node = (Node*)malloc(sizeof(Node)); assert(NULL != node); node->data = val; node->before = NULL; node->next = NULL; return node; } void push_back(NodeList* list, ElemType val){ Node* p = create_node(val); p->before = list->last; p->next = list->first; list->first->before = p; list->last->next = p; list->last = p; list->size++; } void push_front(NodeList* list, ElemType val){ Node* p = create_node(val); //设置p的before和next p->before = list->first; //第一次添加节点的时候要移动未指针,还要设置first的before if(list->first == list->first->next){ list->last = p; p->next = list->first; list->first->before = p; } //不是第一次添加节点的时候,要把原第一个节点的before指向,新添加的节点 else{ p->next = list->first->next; list->first->next->before = p; } //设置头指针的next节点 list->first->next = p; list->size++; } void show_list(NodeList* list){ Node* tmp = list->first->next; while(tmp != list->first){ printf("%d->", tmp->data); tmp = tmp->next; } printf("NULL\n"); } void pop_back(NodeList* list){ if(list->size == 0)return; free(list->last); //让尾指针的next指向NULL list->last->before->next = list->first; //让first的before指向新的尾节点 list->first->before = list->last->before; //让尾指针指向原尾节点的前一个节点 list->last = list->last->before; list->size--; } void pop_front(NodeList* list){ if(list->size == 0)return; free(list->first->next); //就剩一个节点的时候,要移动尾指针。 if(list->first->next == list->last){ list->last = list->first; list->last->next = list->first; list->first->before = list->last; list->size--; return; } //头指针的next指向第二个节点 list->first->next = list->first->next->next; //第二个节点的before指向头节点 list->first->next->before = list->first; list->size--; } void insert_val(NodeList* list, ElemType val){ Node* n = create_node(val);; Node* p = list->first; while(p->next != list->first && val > p->next->data){ p = p->next; } //第一次加节点,或者,最后一个节点的值也没有比给的值大的时候 if(list->first == p->next){ n->next = list->first; n->before = list->last; list->last->next = n; list->first->before = n; list->last = n; list->size++; return; } //新节点的next指向原节点的下一个节点 n->next = p->next; //原节点的next指向新节点,注意这句的位置必须在上句的下面 p->next = n; //新节点的下一个节点的before指向新节点 n->next->before = n; //新节点的before指向原节点 n->before = p; list->size++; } //寻找给定值的节点的位置 Node* find(NodeList* list, ElemType val){ if(list->size == 0)return NULL; Node* p = list->first; while(p->next != list->first && p->next->data != val){ p = p->next; } if(list->first == p->next){ return NULL; } printf("%d is found\n", p->next->data); return p->next; } void delete_val(NodeList* list, ElemType val){ Node* p = find(list, val); if(NULL == p) return; //删除的节点是尾节点的时候,要移动last if(p == list->last){ list->last = p->before; p->before->next = list->first; list->first->before = p->before; list->size--; return; } p->before->next = p->next; p->next->before = p->before; free(p); list->size--; } void sort(NodeList* list){ if(list->size == 1 || list->size == 0)return; //p为第一个节点 Node* p = list->first->next; //t是空白list,往t里加节点 Node* t = list->first; list->last = list->first; list->last->next = list->first; list->first->before = list->last; size_t sz = list->size; Node* tmp; while(sz-- > 0){ //p的next会被改变,所以提前保存 tmp = p->next; while(t->next != list->first && p->data > t->next->data){ t = t->next; } //t为first,或者t为last,都是尾插 if(t->next == list->first){ t->next = p; p->next = list->first; p->before = t; list->first->before = p; list->last = p; } else{ p->next = t->next; t->next->before = p; t->next = p; p->before = t; } p = tmp; t = list->first; } } void resver(NodeList* list){ if(list->size == 1 || list->size == 0)return; //第一个节点 Node* head = list->first->next; //第二个节点 Node* second = head->next; //head就是last,所以要head->next = NULL; list->last = head; list->last->next = list->first; list->first->before = list->last; Node* tmp; while(second != list->first){ //必须保存second的next,因为下面的代码,会改变second的next tmp = second->next; //头插 second->next = list->first->next; list->first->next->before = second; list->first->next = second; second->before = list->first; second = tmp; } } void clear(NodeList* list){ Node* p = list->first->next; while(p != list->last){ p = p->next; free(p); } list->last = list->first; list->last->next = list->first; list->first->before = list->last; list->size = 0; } void destroy(NodeList* list){ clear(list); free(list->first); }
whileshuangnodemain.c
#include "whileshuangnode.h" int main(){ NodeList list; init(&list); int select = 1; ElemType item; Node* node = NULL; while(select){ printf("*****************************************\n"); printf("*** [1] push_back [2] push_front ***\n"); printf("*** [3] show_list [4] pop_back ***\n"); printf("*** [5] pop_front [6] insert_val ***\n"); printf("*** [7] find [8] length ***\n"); printf("*** [9] delete_val [10] sort ***\n"); printf("*** [11] sort [12] resver ***\n"); printf("*** [13] [14] clear ***\n"); printf("*** [0] quit [15*]destroy ***\n"); printf("*****************************************\n"); printf("请选择:>"); scanf("%d", &select); if(0 == select) break; switch(select){ case 1: printf("请输入要插入的数据,以-1结束>\n"); while(scanf("%d",&item) && item != -1){ push_back(&list, item); } show_list(&list); break; case 2: printf("请输入要插入的数据,以-1结束>\n"); while(scanf("%d", &item) && item != -1){ push_front(&list, item); } show_list(&list); break; case 3: show_list(&list); break; case 4: pop_back(&list); show_list(&list); break; case 5: pop_front(&list); show_list(&list); break; case 6: printf("请输入要插入的数据>\n"); scanf("%d",&item); insert_val(&list, item); show_list(&list); break; case 7: printf("please enter what you shoule find out>\n"); scanf("%d",&item); node = find(&list, item); if(node == NULL){ printf("can not find %d\n", item); } break; case 8: printf("length is %ld\n", list.size); break; case 9: printf("please enter what you want to delete>\n"); scanf("%d",&item); delete_val(&list, item); show_list(&list); break; case 10: // sort(&list); //show_list(&list); break; case 11: sort(&list); show_list(&list); break; case 12: resver(&list); show_list(&list); break; case 13: resver(&list); show_list(&list); break; case 14: clear(&list); show_list(&list); break; case 15: destroy(&list); break; default: break; } } //destroy(&list); }
上一篇: css隐藏滚动条、移动端滚动卡顿的解决