C语言数据结构之双向链表

　　数据结构中双向链表的函数的实现。

　　主要实现的功能有，添加数据，删除数据，替换匹配数据，删除匹配数据，正向迭代，反向迭代，统计链表中数据的个数，链表中是否有数据的判定等。

　　有三个文件组成，头文件ls.h，链表实现函数ls.c，还有测试函数ls_test.c。

头文件ls.h

/*双向链表函数实现头文件*/

#ifndef _SL_H
#define _SL_H

#include<sys/types.h>
/*节点*/
typedef struct ListNode{
int data;
struct ListNode* prev;
struct ListNode* next;
} LIST_NODE;

typedef struct List{
LIST_NODE* head;
LIST_NODE* tail;
LIST_NODE* frwd;
LIST_NODE* bkwd;
} LIST;
/*初始化*/
void list_init(LIST* list);
/*清空剩余节点*/
void list_deinit(LIST* list);
/*判断链表是否为空*/
int list_empty(LIST* list);
/*追加*/
void list_append(LIST* list, int data);
/*伪随机访问*/
int* list_at(LIST* list,size_t pos);
/*前插*/
void list_insert(LIST* list, size_t pos, int data);
/*数据替换*/
void list_update(LIST* list, int Old,int New);
/*删除指定位置*/
void list_erase(LIST* list, size_t pos);
/*删除匹配数据*/
void list_remove(LIST* list, int data);
/*数据个数*/
int list_size(LIST* list);
/*正向迭代*/
void list_begin(LIST* list);
/*继续正向迭代*/
int* list_next(LIST* list);
/*返回当前值*/
int* list_current(LIST* list);
/*终止迭代*/
void list_end(LIST* list);
/*判断正向迭代是否终止*/
int list_done(LIST* list);
/*反向迭代*/
void list_rbegin(LIST* list);
/*继续反向迭代*/
int* list_rnext(LIST* list);
/*返回当前值*/
int* list_rcurrent(LIST* list);
/*终止反向迭代*/
void list_rend(LIST* list);
/*判断反向迭代是否终止*/
int list_rdone(LIST* list);

#endif /*_SL_H*/

ls.c文件

/*双向链表函数实现*/

#include<stdlib.h>
#include"ls.h"
/*创建节点*/
static LIST_NODE* create_node(int data,LIST_NODE* prev,LIST_NODE* next){
LIST_NODE* node = malloc(sizeof(LIST_NODE));
node->data = data;
node->prev = prev;
node->next = next;
return node;
}
/*销毁节点*/
static LIST_NODE* destroy_node(LIST_NODE* node,LIST_NODE** prev){
LIST_NODE* next = node->next;
if(prev)
  *prev = node->prev;
free(node);
return next;
}
/*初始化*/
void list_init(LIST* list){
list->head = NULL;
list->tail = NULL;
}
/*清空剩余节点*/
void list_deinit(LIST* list){
while(list->head)
   list->head = destroy_node(list->head,NULL);
list->tail = NULL;
}
/*判断链表是否为空*/
int list_empty(LIST* list){
return !list->head && !list->tail;
}
/*追加*/
void list_append(LIST* list, int data){
LIST_NODE* node = create_node(data,list->tail,NULL);
if(node->prev)
  node->prev->next = node;
else
   list->head = node;
list->tail = node;
}
/*伪随机访问*/
int *list_at(LIST* list,size_t pos){
LIST_NODE* find = NULL;
for(find = list->head; find; find = find->next)
   if(!pos--)
  break;
return &find->data;
}
/*前插*/
void list_insert(LIST* list, size_t pos, int data){
LIST_NODE* find = NULL;
for(find = list->head; find; find = find->next)
   if(!pos--){
    LIST_NODE* node = create_node(data,find->prev,find);
    if(node->prev)
   node->prev->next = node;
    else
   list->head = node;
    node->next->prev = node;
   }
}
/*数据替换*/
void list_update(LIST* list, int Old,int New){
LIST_NODE* find = NULL;
for(find = list->head; find; find = find->next)
   if(Old == find->data)
  find->data = New;
}
/*删除指定位置*/
void list_erase(LIST* list, size_t pos){
LIST_NODE* find = NULL;
for(find = list->head; find; find = find->next)
   if(!pos--){
    LIST_NODE* prev = NULL;
    LIST_NODE* next = destroy_node(find,&prev);
    if(prev)
   prev->next = next;
    else
   list->head = next;
    if(next)
   next->prev = prev;
    else
   list->tail = prev;
    break;
   }
}
/*删除匹配数据*/
void list_remove(LIST* list, int data){
LIST_NODE* find = NULL;
for(find = list->head; find; find = find->next)
   if(data == find->data){
    LIST_NODE* prev = NULL;
    LIST_NODE* next = destroy_node(find,&prev);
    if(prev)
   prev->next = next;
    else
   list->head = next;
    if(next)
   next->prev = prev;
    else
   list->tail = prev;
   }
}
/*数据个数*/
int list_size(LIST* list){
size_t size = 0;
LIST_NODE* node = NULL;
for(node = list->head;node;node = node->next)
   ++size;
return size;
}
/*正向迭代*/
void list_begin(LIST* list){
list->frwd = list->head;
}
/*继续正向迭代*/
int* list_next(LIST* list){
int* data = &list->frwd->data;
list->frwd = list->frwd->next;
return data;
}
/*返回当前值*/
int* list_current(LIST* list){
return &list->frwd->data;
}
/*终止迭代*/
void list_end(LIST* list){
list->frwd = list->tail->next;
}
/*判断正向迭代是否终止*/
int list_done(LIST* list){
return list->frwd == list->tail->next;
}
/*反向迭代*/
void list_rbegin(LIST* list){
list->bkwd = list->tail;
}
/*继续反向迭代*/
int* list_rnext(LIST* list){
int* data = &list->bkwd->data;
list->bkwd = list->bkwd->prev;
return data;
}
/*返回当前值*/
int* list_rcurrent(LIST* list){
return &list->bkwd->data;
}
/*终止反向迭代*/
void list_rend(LIST* list){
list->bkwd = list->head->prev;
}
/*判断反向迭代是否终止*/
int list_rdone(LIST* list){
return list->bkwd == list->head->prev;
}

ls_test.c测试文件

/*双向链表的测试函数*/

#include<stdio.h>
#include<stdlib.h>
#include"ls.h"

int main(void){
LIST list;
list_init(&list);
/*追加测试*/
int i;
int temp = 0;
for(i = 0; i < 5; ++i){
list_append(&list,temp += 10);
}
/*测试正向迭代*/
for(list_begin(&list); !list_done(&list);list_next(&list))
printf("%d ",*list_current(&list));
printf(" ");

/*测试空判断和数量判断*/
printf(list_empty(&list)?"空":"满"" ");
printf("size=%d ",list_size(&list));

/*测试伪随机访问*/
printf("%d ",*list_at(&list,1));
printf(" ");

/*测试逆向迭代*/
for(list_rbegin(&list); !list_rdone(&list);list_rnext(&list))
printf("%d ",*list_rcurrent(&list));
printf(" ");

/*测试前插*/
for(i=0;i<3;i++)
list_insert(&list,i,15);
for(list_begin(&list); !list_done(&list);list_next(&list))
printf("%d ",*list_current(&list));
printf(" ");

/*测试匹配数据更新*/
list_update(&list,15,55);
for(list_begin(&list); !list_done(&list);list_next(&list))
printf("%d ",*list_current(&list));
printf(" ");

/*测试匹配数据删除*/
list_remove(&list,55);
for(list_begin(&list); !list_done(&list);list_next(&list))
printf("%d ",*list_current(&list));
printf(" ");

/**/
}

C语言 数据结构之双向链表

C语言数据结构之双向链表