下面是有关链式存储的线性表ADT抽象数据类型的C语言实现方法。
共3个文件，头文件，函数实现，测试程序。
/* *********************************************************************** * Name: link.h * Desc: C语言ADT(抽象数据类型)的实现 * 本结构为线性表, 以链式存储方式组织 * 实现的操作有: * 结构初始化/销毁与空间释放/向头部或尾部加入记录/在指定位置加入记录 * /在有序表中根据给定条件寻找合适位置加入记录/删除指定位置的记录 * /删除符合条件的记录/读取指定位置记录/查找符合条件的记录 * /按给定的条件排序(可自定义排序依据的字段及排序方向) * Author: Joshua Chan * Date: 2011-11-03 * ***********************************************************************/ #ifndef _LINK_H_ #define _LINK_H_ #include /* 数据类型, 用户不可见 */ structnode_st{ void*datap; structnode_st*prev,*next; }; structlist_st{ structnode_st head; intelmsize; intelmnr; }; /* 接口声明 */ typedefvoidproc_func_t(void*); typedefintcomp_func_t(void*,void*); typedefvoid* LIST_T; LIST_T list_init(constintelmsize); intlist_release(LIST_T ptr); intlist_putif(LIST_T ptr,comp_func_t comp,void*datap,constboolord); intlist_putpos(LIST_T ptr,void*datap,constintpos); intlist_append(LIST_T ptr,void*datap); intlist_prepend(LIST_T ptr,void*datap); intlist_delete_pos(LIST_T ptr,constintpos); intlist_delete(LIST_T ptr,comp_func_t comp,void*key); intlist_travel(LIST_T ptr,proc_func_tproc); void*list_getpos(LIST_T ptr,constintpos); void*list_find(LIST_T ptr,comp_func_t comp,void*key); intlist_sort(LIST_T ptr,comp_func_t comp,constboolord); #endif
/* *********************************************************************** * Name: link.c * Desc: C语言ADT(抽象数据类型)的实现 * 本结构为线性表, 以链式存储方式组织 * 实现的操作有: * 结构初始化/销毁与空间释放/向头部或尾部加入记录/在指定位置加入记录 * /自动在有序表中寻找合适位置加入记录/删除指定位置的记录 * /删除符合条件的记录/读取指定位置记录/查找符合条件的记录 * /按给定的条件排序(可自定义排序依据的字段及排序方向) * Author: Joshua Chan * Date: 2011-11-03 * ***********************************************************************/ #include #include #include #include\ /* 判断要获取的位置是否有效 */ staticinlineboolgetpos_invalid(LIST_T ptr,constintpos) { return(pos>(((structlist_st*)ptr)->elmnr-1)||pos<0)?true:false; } /* 判断要加入记录的位置是否有效 */ staticinlineboolputpos_invalid(LIST_T ptr,constintpos) { return(pos>(((structlist_st*)ptr)->elmnr)||pos<0)?true:false; } /* 判断记录非空 */ staticinlineboollist_empty(LIST_T ptr) { return((structlist_st*)ptr)->elmnr==0?true:false; } /* 结构初始化 */ LIST_T list_init(constintelmsize) { structlist_st*newlist; newlist=malloc(sizeof(structlist_st)); if(newlist== NULL) return NULL; newlist->elmsize=elmsize; newlist->elmnr=0; newlist->head.datap= NULL; newlist->head.prev=&newlist->head; newlist->head.next=&newlist->head; return(LIST_T)newlist; } /* 结构销毁, 空间释放 */ intlist_release(LIST_T ptr) { structlist_st*me =ptr; structnode_st*cur,*save; for(cur = me->head.next; cur !=&me->head; cur = save){ save = cur->next; free(cur->datap); free(cur); } free(me); return0; } /* 预分配空间 */ staticstructnode_st*node_alloc(LIST_T ptr,void*datap) { structlist_st*me =ptr; structnode_st*newnode; newnode=malloc(sizeof(structnode_st)); if(newnode== NULL) return NULL; newnode->datap=malloc(me->elmsize); if(newnode->datap== NULL){ free(newnode); return NULL; } memcpy(newnode->datap,datap, me->elmsize); returnnewnode; } /* 根据给定条件选择合适位置加入记录, 适用于有序表 */ intlist_putif(LIST_T ptr,comp_func_t comp,void*datap,constboolord) { structlist_st*me =ptr; structnode_st*cur,*newnode; bool sig; if(list_empty(me)) return-1; newnode=node_alloc(ptr,datap); if(newnode== NULL) return-1; for(cur = me->head.next; cur !=&me->head; cur = cur->next){ sig = comp(cur->datap,datap)>0?true:false; if(!(sig ^ord)) break; } newnode->prev= cur->prev; newnode->next= cur; cur->prev->next=newnode; cur->prev=newnode; me->elmnr++; return0;