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-