|
/*
* 我也遵循GPL协议
* A simple single list implementation.
*
* Copyright (C) 2008 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));\
INIT_NODE(name,ptr);
//声明一个链表
#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,list_t *slist); //加在header的后面
int list_add_tail(node_t *new, list_t *slist); //加在尾巴上
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,list_t *slist)
{
__list_add(new,slist->header,slist->header->next);
return 0;
}
//加在尾巴上
int list_add_tail(node_t *new, list_t *slist)
{
//node_t *rear = NULL;
node_t *tmp = NULL;
//遍历到list的尾部
// rear = slist->header;
// tmp = slist->header->next;
// while(tmp) {
// rear = tmp;
// tmp = tmp->next;
// }
//到尾了rear 就是最后一个节点,rear->next=NULL
//不用rear指针
tmp = slist->header;
while(tmp->next)
tmp = tmp->next;
__list_add(new,tmp,tmp->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指针即可
#if 0
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;
this_entry = prev->next;
if(!this_entry) {
printf("list empty \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(this_entry,prev,this_entry->next); //prev -> entry -> entry->next
return 0;
}
#endif
int list_del(node_t *entry,list_t *slist)
{
//先遍历一次找到他的前驱，因为slist没有prev指针
node_t *tmp = slist->header;
if(!tmp->next) {
printf("empty list \n");
return -1;
}
while(tmp->next)
{
if(tmp->next == entry)
break;
tmp = tmp->next;
}
if(!tmp->next)
{
printf("no this node in this list\n");
return -1;
}
__list_del(entry,tmp,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;
DECLARE_LIST(tmp_list);
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,tmp_list);
tmp = next_node;
}
free(list->header); //释放之前的header
list->header = tmp_list->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;
//释放header节点和list本身
free(slist->header);
free(slist);
return 0;
}
node_t * copy_node(node_t * old_node)
{
node_t * new_node = (node_t *)malloc(sizeof(node_t));
if(!new_node)
{
printf("in copy_node : copy node failure\n");
return NULL;
}
printf("length = %d\n",sizeof(typeof(old_node->data_p)));
//data_p 由于是泛型指针， 我怎么来处理呢？ 如果是整数，直接赋值，如果是char * ,就memcpy即可
memcpy(new_node->data_p,old_node->data_p,sizeof(typeof(old_node->data_p)));
new_node->next = NULL;
return 0;
}
//复制一个链表
list_t * copy_list(list_t *src_list)
{
node_t *tmp = src_list->header->next;
DECLARE_LIST(new_list); //已经有header，是新malloc过来的
//现在要遍历src_list,然后依次插入到新的链表中
if(!tmp) {
printf("src list empty \n");
return NULL;
}
while(tmp)
{
node_t *node = copy_node(tmp);
if(!node)
{
printf("copy list failure\n");
//错误处理：
free(new_list);
return NULL;
}
list_add(node,new_list);
tmp = tmp->next;
}
return new_list;
}
int main(void)
{
node_t *p = NULL;
list_t *new_list = NULL;
DECLARE_LIST(list);
DECLARE_LIST(list_int);
DECLARE_LIST(list_dd_pointer);
DECLARE_NODE(p1,"zhanglinbao");
DECLARE_NODE(p2,"1234567890");
DECLARE_NODE(p3,"ABCDEFGHIJKLMN");
int a = 10;
int b = 20;
int c = 30;
char *s1 = "12344";
char *s2 = "abcdefg";
char *s3 = "xyz";
DECLARE_NODE(p4,&a);
DECLARE_NODE(p5,&b);
DECLARE_NODE(p6,&c);
DECLARE_NODE(S1,&s1);
DECLARE_NODE(S2,&s2);
DECLARE_NODE(S3,&s3);
// ---------------------------------------------------------------
//下面的这些代码都用上面的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);
list_add_tail(p2,list);
list_add_tail(p3,list);
list_add_tail(p4,list_int);
list_add_tail(p5,list_int);
list_add_tail(p6,list_int);
list_add_tail(S1,list_dd_pointer);
list_add_tail(S2,list_dd_pointer);
list_add_tail(S3,list_dd_pointer);
p = list->header->next;
while(p)
{
printf("%s\n",(char *)(p->data_p));
p=p->next;
}
p = list_int->header->next;
while(p)
{
printf("%d\n",*(int *)(p->data_p));
p = p->next;
}
p = list_int->header->next;
while(p)
{
printf("%p\n",*(char **)(p->data_p));
p = p->next;
}
printf("s1=%p\n",s1);
printf("s2=%p\n",s2);
printf("s3=%p\n",s3);
/* 测试copy list 函数 */
new_list = copy_list(list);
if(new_list==NULL)
{
printf("copy list failure \n");
return -1;
}
p = new_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*)(p1->data_p));
list_del(p1,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;
}
|
