C语言实现一个简单的单向链表list
cheungmine
用C语言实现一个简单实用的单向链表list,具有一定的实际意义。尤其我们不想使用STL里面的list<...>类的时候。我实现的这个list,结点存储任何调用者分配的任意类型的数据(void*)。这个list适用于一些简单的场合,消耗极少的资源。
头文件:
/*
*list.h
*Genericsequentiallinkedlistnodestructure--canholdanytypedata.
*cheungmine
*Sep.22,2007.Allrightsreserved.
*/
#ifndefLIST_H_INCLUDED
#defineLIST_H_INCLUDED
#include"unistd.h"
typedefstruct_listnode_t
{
struct_listnode_t*next;
union{
void*data;
struct_list_t*list;
constchar*str;
longkey;
};
}listnode_t;
typedefstruct_list_t
{
size_tsize;/*countofnodes*/
listnode_t*head;
listnode_t*tail;
}list_t,*list_p;
/*Aprototypeofcallbackedfunctioncalledbylist_destroy(),NULLfornouse.*/
typedefvoid(*pfcb_list_node_free)(listnode_t*node);
/*Anexampleoffreenodedatafunctionimplementedbycallee:
voidmy_list_node_free(listnode_t*node)
{
free(node->data);
}
*/
/*Appendsanodetoalist*/
externvoid
list_append_node(list_t*in_list,listnode_t*in_node);
/*Removesthefirstnodefromalistandreturnsit*/
externlistnode_t*
list_remove_head(list_t*in_list);
/*Removesallnodesbutforlistitself*/
externvoid
list_remove_all(list_t*in_list,pfcb_list_node_freepfunc/*NULLfornouseorakeynode*/);
/*Returnsacopyofalist_tfromheap*/
externlist_t*
list_copy(list_tin_list);
/*Concatenatestwolistsintofirstlist.NOTfreeingthesecond*/
externvoid
list_concat(list_t*first,list_t*second);
/*Allocatesanewlistnode_tfromheap.NOmemoryallocatedforinputnode_data*/
externlistnode_t*
list_node_create(void*node_data);
/*Allocatesanewlistnode_twithakeynodetype*/
externlistnode_t*
list_key_create(longnode_key);
/*Allocatesaemptylist_tfromheap*/
externlist_t*
list_create();
/*Freesin_list'sallnodesanddestroysin_listfromheap.
*thecalleeisresponsibleforfreeingnodedata.
*thenodefreed-function(pfunc)iscalledbylist_destroy.
*/
externvoid
list_destroy(list_t*in_list,pfcb_list_node_freepfunc/*NULLfornouseorakeynode*/);
/*Getscountofnodesinthelist*/
externsize_t
list_size(constlist_t*in_list);
/*Getsnodebyindex0-based.0ishead*/
externlistnode_t*
list_node_at(constlist_t*in_list,intindex);
#endif/*LIST_H_INCLUDED*/
实现文件:
/*
*list.c
*Genericlinkedlistimplementation.
*cheungmine
*Sep.22,2007.Allrightsreserved.
*/
#include"list.h"
/*Appendsanodetoalist*/
void
list_append_node(list_t*in_list,listnode_t*node)
{
node->next=NULL;
if(in_list->head)
{
in_list->tail->next=node;
in_list->tail=node;
}
else
in_list->head=in_list->tail=node;
in_list->size++;
}
/*Removesthefirstnodefromalistandreturnsit*/
listnode_t*
list_remove_head(list_t*in_list)
{
listnode_t*node=NULL;
if(in_list->head)
{
node=in_list->head;
in_list->head=in_list->head->next;
if(in_list->head==NULL)
in_list->tail=NULL;
node->next=NULL;
in_list->size--;
}
assert(in_list->size>=0);
returnnode;
}
/*Removesallnodesbutforlistitself*/
void
list_remove_all(list_t*in_list,pfcb_list_node_freepf)
{
listnode_t*node;
while((node=list_remove_head(in_list))){
if(pf)(*pf)(node);
free(node);
}
assert(in_list->size==0);
}
/*Returnsacopyofalist_tfromheap*/
list_t*
list_copy(list_tlist)
{
list_t*newlist=(list_t*)malloc(sizeof(list_t));
*newlist=list;
returnnewlist;
}
/*Concatenatestwolistsintofirstlist*/
void
list_concat(list_t*first,list_t*second)
{
if(first->head)
{
if(second->head)
{
first->tail->next=second->head;
first->tail=second->tail;
}
}
else
*first=*second;
second->head=second->tail=NULL;
first->size+=second->size;
}
/*Allocatesanewlistnode_tfromheap*/
listnode_t*
list_node_create(void*data)
{
listnode_t*node=(listnode_t*)malloc(sizeof(listnode_t));
node->next=NULL;
node->data=data;
returnnode;
}
listnode_t*
list_key_create(longkey)
{
listnode_t*node=(listnode_t*)malloc(sizeof(listnode_t));
node->next=NULL;
node->key=key;
returnnode;
}
/*Allocatesaemptylist_tfromheap*/
list_t*
list_create()
{
list_t*list=(list_t*)malloc(sizeof(list_t));
list->size=0;
list->head=list->tail=NULL;
returnlist;
}
/*Freesaemptylist_tfromheap*/
void
list_destroy(list_t*in_list,pfcb_list_node_freepf)
{
list_remove_all(in_list,pf);
free(in_list);
}
/*Getscountofnodesinthelist*/
size_t
list_size(constlist_t*in_list)
{
returnin_list->size;
}
/*Getsnodebyindex0-based.0ishead*/
listnode_t*
list_node_at(constlist_t*in_list,intindex)
{
inti=0;
listnode_t*node=in_list->head;
assert(index>=0&&index<(int)in_list->size);
while(i<index)
{
node=node->next;
i++;
}
returnnode;
}
公共头文件:
/*unistd.h
2008-09-15Lastcreatedbycheungmine.
Allrightsreservedbycheungmine.
*/
#ifndefUNISTD_H__
#defineUNISTD_H__
/*StandardCheaderfilesincluded*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
/*============================================================================*/
typedefunsignedcharuchar,byte,BYTE;
typedefunsignedshortuint16,word_t,ushort;
typedefunsigned__int32uint,uint32,dword_t,size_t;
typedefunsignedlongulong;
typedef__int16int16;
typedef__int32int32;
typedef__int64int64,longlong;
typedeflonglresult;
typedefunsigned__int64uint64,qword_t,ulonglong;
#ifndefBOOL
typedefintBOOL;
#defineTRUE1
#defineFALSE0
#endif
#ifndefRESULT
#defineRESULTlresult
#define_SUCCESS0
#define_ERROR-1
#endif
#ifndefIN
#defineIN
#endif
#ifndefOUT
#defineOUT
#endif
#ifndefINOUT
#defineINOUT
#endif
#ifndefOPTIONAL
#defineOPTIONAL
#endif
#defineSIZE_BYTE1
#defineSIZE_ACHAR1
#defineSIZE_WCHAR2
#defineSIZE_SHORT2
#defineSIZE_INT4
#defineSIZE_LONG4
#defineSIZE_FLT4
#defineSIZE_DBL8
#defineSIZE_WORD2
#defineSIZE_DWORD4
#defineSIZE_QWORD8
#defineSIZE_LINT8
#defineSIZE_INT648
#defineSIZE_UUID16
/*============================================================================*/
#endif/*UNISTD_H__*/
好了。是不是很简单啊。适合初学者学习,适合喜欢简单就是生活的人!
分享到:
相关推荐
1,单向链简洁。...根据示例代码中的例子,完成单向链表(single linked list)中的以字符串为数据的链表的插入、删除以及查找,并支持单向链表的反转; 3,代码实现。 #include #include <math.h>
Singly Linked List: 1. DestroyList 2. InsertList 3. DeleteList 4. TraverseList 5. SearchList 6. ReverseList 7. IsLoopList 8. ReverseEvenList 9. FindMidNode Double Linked List: 1. ...
为了可扩展使用,下面的结点结构中用TYPE指定数据类型,使用时请按照需要在list_def.h中把TYPE定义为合适的类型,并且提供三个原型函数,第一个用来为TYPE类型的数据赋值,第二个判断两个TYPE类型的数据是否相等,...
底层链表(单向链表)list.h,list.c; 菜单文件menu.h,menu.c; 功能模块student.h,student.c; main.c;in.c; Linux C,Ubuntu;make工具多文件编译,文件操作,用文件保存学生信息表(掉电保护,防丢失) ; 注释超全,...
C语言数据结构旋转链表的实现 实例: 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null 分析: 感觉很直观,直接把分割点找出来就行,记得k可能大于len,要取模 代码: /** * Definition for singly-...
双向链表(Doubly Linked List)是一种常见的数据结构,在单链表的基础上增加了向前遍历的功能。与单向链表不同,双向链表的每个节点除了包含指向下一个节点的指针外,还包含指向前一个节点的指针。
单向链表分为单向有头链表和单线无头链表,本文针对单向有头链表使用C语言来实现并进行封装。 实现 list_head.h文件 #ifndef _LIST_H_ #define _LIST_H_ typedef int datatype; #define SUCC #define MALLOC_FAIL 1...
CreateEmpty创建一个空表;Find返回关键字首次出现的位置;Insert和Delete从表的某个位置插入和删除某个关键字。 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现。链表(linked list)由...
数据结构:一种线性表(即数组)和四种链表(单向链表、单向环形链表、双向链表、双向环形链表) 实现编程语言:C语言
每一个成员可以是一个基本数据类型或者又是一个构造类型。 结构既是一种“构造”而成的数据类型, 那么在说明和使用之前必须先定义它,也就是构造它。如同在说明和调用函数之前要先定义函数一样。 一、结构的定义 ...
(4)同一个算法,实现语言的级别越高,执行效率就越低 A.(1) B.(1),(2) C.(1),(4) D.(3) 7.从逻辑上可以把数据结构分为(C )两大类。【武汉交通科技大学 1996 一 、4(2分)】 A.动态结构、静态结构 B.顺序...