c/c++ 线性表之双向循环链表

2022-11-12 09:50:47

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;

  //ｔ是空白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;

    }

    //ｔ为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);

}

码农公寓

c/c++ 线性表之双向循环链表

相关文章