今天有空，静下心来写了一下单向链表的实现，重点在于单向链表的反序遍历复杂度可以为o(n)，这在以前没有想过，甚至认为单向链表无法反序遍历。本次实现了2种反序遍历方法。第一种比较简单，但是改变了链表的方向，第2种用了while嵌套。其它的内容可以供初学者学习一下，纯属抛砖引玉，有错误之处敬请批评指正。
源码环境：linux
编译方法：gcc --std=c99 single-list.c
single-list.h:
/****************************************************
***功能 : 单向链表[无tail指针]
***作者 : yycode
***日期 : 2017/06/17
****************************************************/
#ifndef __SINGLE_LIST__
#define __SINGLE_LIST__
#include <stddef.h>
#include <stdlib.h>
#define FREE(p) do{ \
if(NULL != p){ \
free(p); \
p = NULL; \
} \
}while(0)
//node structure
typedef struct node{
int value;
struct node *next;
}t_node;
//list structure
typedef struct list{
struct node *head;
// struct node *tail;
uint32_t size;
}t_list;
t_list *create_list();
t_list *append_node(t_list *lst, int value);
t_node *back_node(t_list *lst);
t_node *find_node(t_list *lst, int value);
t_list *delete_node(t_list *lst, int value);
void traverse_list(t_list *lst);
void reverse_traverse1(t_list *lst);
void reverse_traverse2(t_list *lst);
void destroy_list(t_list **lst);
#endif
single-list.c
/****************************************************
***功能 : 单向链表[无tail指针]
***作者 : yycode
***日期 : 2017/06/17
****************************************************/
#include <time.h>
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdbool.h>
#include "single-list.h"
const uint32_t list_capacity = 10;
//创建
t_list *create_list(){
t_list *lst = (t_list*)malloc(sizeof(t_list));
assert(NULL != lst);
lst->head = NULL;
lst->size = 0;
return lst;
}
//附加节点:【o(n)】
t_list *append_node(t_list *lst, int value){
t_node *index = lst->head;
t_node *node = (t_node*)malloc(sizeof(t_node));
assert(NULL != lst);
node->value = value;
node->next = NULL;
if(NULL == index){
lst->head = node;
++lst->size;
return lst;
}
while(NULL != index->next){
index = index->next;
}
index->next = node;
++lst->size;
}
//获取末节点
t_node *back_node(t_list *lst){
if(NULL == lst){
return NULL;
}
t_node *find = lst->head;
while(NULL != find->next){
find = find->next;
}
return find;
}
//查找节点【o(n)】
t_node *find_node(t_list *lst, int value){
t_node *index = lst->head;
while(NULL != index && index->value != value){
index = index->next;
}
if(NULL != index && index->value == value){
return index;
}
return NULL;
}
//删除节点【o(n)】
t_list *delete_node(t_list *lst, int value){
if(NULL == lst->head){
return lst;
}
t_node *preindex = NULL;
t_node *index = lst->head;
while(NULL != index && index->value != value){
preindex = index;
index = index->next;
}
if(NULL != index && index->value == value){
preindex->next = index->next;
FREE(index);
--lst->size;
}
return lst;
}
//遍历
void traverse_list(t_list *lst){
t_node *index = lst->head;
while(NULL != index){
printf("traverse value = %d.\n", index->value);
index = index->next;
}
}
//反序遍历1:【2*o(n)】
void reverse_traverse1(t_list *lst){
if(NULL == lst->head){ //空表
printf("list content is empty!");
return;
}
t_node *index = lst->head; //当前node
t_node *front = NULL; //当前node前驱
t_node *next = index->next; //当前节点next
//[o(n)]
while(NULL != next){
index->next = front; //update index->next
front = index; //update front
index = next; //update current
next = index->next; //update next
}
index->next = front;
lst->head = index; //update list->head
//print list [o(n)]
t_node *index2 = lst->head;
while(NULL != index2){
printf("reverse traverse1 value= %d.\n", index2->value);
index2 = index2->next;
}
}
//反序遍历2:【o(n) + o(n2)】
void reverse_traverse2(t_list *lst){
if(NULL == lst->head){
printf("list is empty!");
return;
}
t_node *pretail = lst->head;
t_node *tail = back_node(lst); //找到末节点[o(n)]
while(tail != lst->head){ //【o(n2)】
printf("reverse traverse2 value = %d.\n", tail->value);
while(pretail->next != tail){
pretail = pretail->next;
}
tail = pretail;
pretail = lst->head;
}
printf("reverse traverse2 value = %d.\n", tail->value);
}
//销毁【o(n)】
void destroy_list(t_list **lst){
t_list *list = *lst;
if(NULL == list->head){ //链表为空
FREE(*lst);
return;
}
t_node *node = list->head;
t_node *index = NULL;
while(NULL != node){
index = node->next;
FREE(node);
node = index;
}
list->head = NULL;
list->size = 0;
FREE(*lst);
}
//测试入口
int main()
{
printf("=====<test single list>=====\n");
srand((unsigned)time(NULL)); //后面要用随机数
t_list *list = create_list();
printf("\ninit list:capacity = %d\n", list_capacity);
for(int i = 1; i <= list_capacity; ++i){
append_node(list, i);
}
printf("sizeof(list) = %u.\n", list->size);
unsigned rx = rand() % (list_capacity);
printf("\ndelete value = %d from list:\n", rx);
delete_node(list, rx);
printf("sizeof(list) = %u.\n", list->size);
printf("\ntraverse list:\n");
traverse_list(list);
printf("\nreverse1 traverse list:\n");
reverse_traverse1(list);
printf("\nreverse2 traverse list:\n");
reverse_traverse2(list);
printf("\nfind node from list:\n");
rx = rand() % (list_capacity << 1);
printf("find value = %d from list:", rx);
t_node *find = find_node(list, rx);
if(NULL != find)
printf ("OK.\n");
else
printf ("FAIL!\n");
rx = rand() % (list_capacity << 1);
printf("find value = %d from list:", rx);
find = find_node(list, rx);
if(NULL != find)
printf ("OK.\n");
else
printf ("FAIL!\n");
destroy_list(&list);
printf("\ndestroy list:\n");
return 0;
}
网友评论