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