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

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);
}
上一篇:The destination folder does not exist or is not writeable


下一篇:wpf无法加载程序集的元数据 可能已从web下载