|
/*
* 我也遵循GPL协议
* A simple single list implementation.
*
* Copyright (C) 2007 Bob Zhang
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
*/
/* ===================================================================================
* 简单的实现一个单链表的功能
*
* CopyRight reserved by BobZhang bob.zhang2004@gmail.com bobzhang@mxic.com.cn
*
* 功能：
* 模拟struct list_head 的函数格式重新实现自己的单链表操作，全部重新实现
* 倒置list ， 比如 header -> a -> b -> c 执行convert函数后 变成 header->c->b->a
*
* 注意：
* 此库模仿struct list_head的实现(include/linux/list.h )，
* 但仅仅是函数名称和一些宏， 名称相同，实现并不相同
* ==================================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node_t {
void *data_p; //可以兼容所有的数据类型
struct node_t *next;
}node_t;
typedef struct list_t {
node_t *header;
// int size; //元素个数
}list_t;
//初始化一个节点
#define INIT_NODE(node,ptr) do { node->data_p = ptr; node->next = NULL; } while(0)
//声明一个节点
#define DECLARE_NODE(name,ptr) \
node_t *name = (node_t *)malloc(sizeof(node_t));\
name->data_p = ptr; \
name->next = NULL; \
//声明一个链表
#define DECLARE_LIST(list_name) \
list_t *list_name = (list_t *)malloc(sizeof(list_t)); \
INIT_LIST_HEAD(list_name); \
int INIT_LIST_HEAD(list_t *p);
int __list_add(node_t *new,node_t *prev,node_t *next); //中间插入一个新的节点
int list_add(node_t *new,node_t *head); //加在header的后面
int list_add_tail(node_t *new, node_t *head); //加在尾巴上
int __list_del(node_t *entry,node_t *prev,node_t *next);//删除单链表上的任意一个节点，当然要有这个节点指针
int list_del(node_t *entry,list_t *slist); //从单项链表中删除某个节点
int list_del_head(list_t *slist); //删除header后面的节点
int convert(list_t *list); //倒置list ， 比如 header -> a -> b -> c 执行convert函数后 变成 header->c->b->a
int free_list(list_t *slist); //释放链表
//初始化一个链表
int INIT_LIST_HEAD(list_t *p)
{
p->header = (node_t *)malloc(sizeof(node_t));
p->header->next = NULL;
return 0;
}
//加在prev和next之间
int __list_add(node_t *new,node_t *prev,node_t *next) //中间插入一个新的节点
{
new->next = next;
prev->next = new;
return 0;
}
//加在header的后面
int list_add(node_t *new,node_t *head)
{
__list_add(new,head,head->next);
return 0;
}
//加在尾巴上
int list_add_tail(node_t *new, node_t *head)
{
node_t *rear = NULL;
node_t *tmp = NULL;
//遍历到list的尾部
rear = head;
tmp = head->next;
while(tmp) {
rear = tmp;
tmp = tmp->next;
}
//到尾了rear 就是最后一个节点,rear->next=NULL
__list_add(new,rear,rear->next);
return 0;
}
//删除单链表上的任意一个节点，当然要有这个节点指针
int __list_del(node_t *entry,node_t *prev,node_t *next)
{
//三个参数的关系 prev->entry->next
prev->next = next;
entry->next = NULL;
entry->data_p = NULL;
free(entry);
return 0;
}
//从单项链表中删除某个节点
//肯定要遍历查找这个节点的前驱节点， 只需更改前驱节点的next指针即可
int list_del(node_t *entry,list_t *slist)
{
//先遍历一次找到他的前驱，因为slist没有prev指针
node_t *header = slist->header;
node_t * prev = NULL;
node_t *this_entry = NULL;
prev = header->next;
if(prev)
this_entry = prev->next;
else {
printf("list emtpry \n");
return -1;
}
while(this_entry)
{
if(this_entry == entry) //找到了,比较指针
break;
prev = this_entry;
this_entry = this_entry->next;
}
if(!this_entry) //最终没有找到
{
printf("no this node ,please check \n");
return -1;
}
__list_del(entry,prev,entry->next); //prev -> entry -> entry->next
return 0;
}
//删除header后面的节点
int list_del_head(list_t *slist)
{
int ret = 0;
ret = __list_del(slist->header->next,slist->header,slist->header->next->next);
return ret;
}
//倒置list ， 比如 header -> a -> b -> c 执行convert函数后 变成 header->c->b->a
int convert(list_t *list)
{
node_t *tmp = NULL;
node_t *new_header = NULL;
new_header = (node_t *)malloc(sizeof(node_t));
tmp = list->header->next;
if(!tmp) {
printf("list empty \n");
return -1;
}
//遍历链表
while(tmp)
{
node_t *next_node = tmp->next; //因为tmp在下行操作后 tmp->next 就等于NULL了，所以这里要记住tmp->next
list_add(tmp,new_header);
tmp = next_node;
}
free(list->header); //释放之前的header
list->header = new_header; //原来的链表的header更新一下，是现在新的头
return 0;
}
//释放链表
int free_list(list_t *slist)
{
node_t *header = slist->header;
while(header->next)
{
__list_del(header->next,header,header->next->next);
}
slist->header = NULL;
return 0;
}
int main(void)
{
node_t *p = NULL;
DECLARE_LIST(list);
DECLARE_NODE(p1,"zhanglinbao");
DECLARE_NODE(p2,"1234567890");
DECLARE_NODE(p3,"ABCDEFGHIJKLMN");
// ---------------------------------------------------------------
//下面的这些代码都用上面的4个宏来实现了， 看起来简练一些
// list_t *list = (list_t *)malloc(sizeof(list_t));
//用宏简化一下这种写法，更简洁
// node_t *p1 = (node_t *)malloc(sizeof(node_t));
// node_t *p2 = (node_t *)malloc(sizeof(node_t));
// node_t *p3 = (node_t *)malloc(sizeof(node_t));
//初始化链表
// INIT_LIST_HEAD(list);
// INIT_NODE(p1,"zhanglinbao");
// INIT_NODE(p2,"1234567890");
// INIT_NODE(p3,"ABCDEFGHIJKLMN");
//-----------------------------------------------------------------
list_add_tail(p1,list->header);
list_add_tail(p2,list->header);
list_add_tail(p3,list->header);
p = list->header->next;
while(p)
{
printf("%s\n",(char *)(p->data_p));
p=p->next;
}
printf("\n\n");
printf("I want to delete the node whose name is %s\n",(char*)(p2->data_p));
list_del(p2,list); //删除一个节点
p = list->header->next;
while(p)
{
printf("%s\n",(char *)(p->data_p));
p=p->next;
}
//开始倒置链表
convert(list);
printf("\n\nI have converted ok \n");
p = list->header->next;
while(p)
{
printf("%s\n",(char *)(p->data_p));
p=p->next;
}
free_list(list);
return 0;
}
|
