c/c++ 线性表之双向链表
程序员文章站
2022-06-11 16:03:43
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 | 释放所有节点的所占用的内存空间,包括头节点 |
shuangnode.h
#ifndef __SHUANGNODE__ #define __SHUANGNODE__ #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
shuangnode.c
#include "shuangnode.h" void init(NodeList* list){ list->first = (Node*)malloc(sizeof(Node)); list->last = list->first; list->last->next = NULL; 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 = NULL; 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; p->next = list->first->next; //第一次添加节点的时候要移动未指针 if(NULL == list->first->next){ list->last = p; } //不是第一次添加节点的时候,要把原第一个节点的before指向,新添加的节点 else{ list->first->next->before = p; } //设置头指针的next节点 list->first->next = p; list->size++; } void show_list(NodeList* list){ Node* tmp = list->first->next; while(tmp != NULL){ 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 = NULL; //让尾指针指向原尾节点的前一个节点 list->last = list->last->before; list->size--; } void pop_front(NodeList* list){ if(list->size == 0)return; free(list->first->next); //就剩一个节点的时候,要移动尾指针。因为list->first->next已经为NULL,下面的list->first->next->before就会在执行时候崩掉,所以要return掉 if(list->first->next == list->last){ list->last = list->first; list->last->next = NULL; 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 != NULL && val > p->next->data){ p = p->next; } //第一次加节点,或者,最后一个节点也没有给的值大的时候 if(NULL == p->next){ n->next = NULL; n->before = list->last; list->last->next = 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 != NULL && p->next->data != val){ p = p->next; } if(NULL == p->next){ return NULL; } printf("%d is found\n", p->next->data); return p->next; } //寻找给定值的节点的前一个节点的位置 Node* find1(NodeList* list, ElemType val){ if(list->size == 0)return NULL; Node* p = list->first; while(p->next != NULL && p->next->data != val){ p = p->next; } if(NULL == p->next){ return NULL; } printf("%d is found\n", p->next->data); return p; } void delete_val(NodeList* list, ElemType val){ Node* p = find1(list, val); if(NULL == p) return; free(p->next); //删除的节点是尾节点的时候,要移动last if(p->next == list->last){ list->last = p; p->next = NULL; list->size--; return; } p->next->next->before = p; p->next = p->next->next; 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 = NULL; size_t sz = list->size; Node* tmp; while(sz-- > 0){ //p的next会被改变,所以提前保存 tmp = p->next; while(t->next != NULL && p->data > t->next->data){ t = t->next; } //t为first,或者t为last,都是尾插 if(t->next == NULL){ t->next = p; p->next = NULL; p->before = t; 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 = NULL; Node* tmp; while(second != NULL){ //必须保存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 != NULL){ free(p); p = p->next; } list->last = list->first; list->last->next = NULL; list->size = 0; } void destroy(NodeList* list){ Node* p = list->first; while(p != NULL){ free(p); p = p->next; } list->size = 0; }
shuangnodemain.c
#include "shuangnode.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); }
下一篇: java代理基础类1.0