C语言面向对象编程（五）：单链表实现
生活随笔
收集整理的這篇文章主要介紹了
C语言面向对象编程（五）：单链表实现
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
前面我們介紹了如何在 C 語言中引入面向對象語言的一些特性來進行面向對象編程，從本篇開始，我們使用前面提到的技巧，陸續實現幾個例子，最后呢，會提供一個基本的 http server 實現（使用 libevent ）。在這篇文章里，我們實現一個通用的數據結構：單鏈表。
#ifndef?SLIST_H?? #define?SLIST_H?? ?? #ifdef?__cplusplus?? extern?"C"?{?? #endif?? ?? #define?NODE_T(ptr,?type)?((type*)ptr)?? ?? struct?slist_node?{?? ????struct?slist_node?*?next;?? };?? ?? typedef?void?(*list_op_free_node)(struct?slist_node?*node);?? /*? ?*?return?0?on?hit?key,?else?return?none?zero? ?*/?? typedef?int?(*list_op_key_hit_test)(struct?slist_node?*node,?void?*key);?? ?? struct?single_list?{?? ????/*?all?the?members?must?not?be?changed?manually?by?callee?*/?? ????struct?slist_node?*?head;?? ????struct?slist_node?*?tail;?? ????int?size;?/*?length?of?the?list,?do?not?change?it?manually*/?? ?? ????/*?free?method?to?delete?the?node? ?????*/?? ????void?(*free_node)(struct?slist_node?*node);?? ????/*? ?????*?should?be?set?by?callee,?used?to?locate?node?by?key(*_by_key()?method)? ?????*?return?0?on?hit?key,?else?return?none?zero? ?????*/?? ????int?(*key_hit_test)(struct?slist_node?*node,?void?*key);?? ?? ????struct?single_list?*(*add)(struct?single_list?*?list,?struct?slist_node?*?node);?? ????struct?single_list?*(*insert)(struct?single_list?*?list,?int?pos,?struct?slist_node?*node);?? ????/*?NOTE:?the?original?node?at?the?pos?will?be?freed?by?free_node?*/?? ????struct?single_list?*(*replace)(struct?single_list?*list,?int?pos,?struct?slist_node?*node);?? ????struct?slist_node?*(*find_by_key)(struct?single_list?*,?void?*?key);?? ????struct?slist_node?*(*first)(struct?single_list*?list);?? ????struct?slist_node?*(*last)(struct?single_list*?list);?? ????struct?slist_node?*(*at)(struct?single_list?*?list,?int?pos);?? ????struct?slist_node?*(*take_at)(struct?single_list?*?list,?int?pos);?? ????struct?slist_node?*(*take_by_key)(struct?single_list?*?list,?void?*key);?? ????struct?single_list?*(*remove)(struct?single_list?*?list,?struct?slist_node?*?node);?? ????struct?single_list?*(*remove_at)(struct?single_list?*list,?int?pos);?? ????struct?single_list?*(*remove_by_key)(struct?single_list?*list,?void?*key);?? ????int?(*length)(struct?single_list?*?list);?? ????void?(*clear)(struct?single_list?*?list);?? ????void?(*deletor)(struct?single_list?*list);?? };?? ?? struct?single_list?*?new_single_list(list_op_free_node?op_free,?list_op_key_hit_test?op_cmp);?? ?? #ifdef?__cplusplus?? }?? #endif?? ?? #endif?//?SLIST_H??
#ifndef SLIST_H
#define SLIST_H#ifdef __cplusplus
extern "C" {
#endif#define NODE_T(ptr, type) ((type*)ptr)struct slist_node {struct slist_node * next;
};typedef void (*list_op_free_node)(struct slist_node *node);
/** return 0 on hit key, else return none zero*/
typedef int (*list_op_key_hit_test)(struct slist_node *node, void *key);struct single_list {/* all the members must not be changed manually by callee */struct slist_node * head;struct slist_node * tail;int size; /* length of the list, do not change it manually*//* free method to delete the node*/void (*free_node)(struct slist_node *node);/** should be set by callee, used to locate node by key(*_by_key() method)* return 0 on hit key, else return none zero*/int (*key_hit_test)(struct slist_node *node, void *key);struct single_list *(*add)(struct single_list * list, struct slist_node * node);struct single_list *(*insert)(struct single_list * list, int pos, struct slist_node *node);/* NOTE: the original node at the pos will be freed by free_node */struct single_list *(*replace)(struct single_list *list, int pos, struct slist_node *node);struct slist_node *(*find_by_key)(struct single_list *, void * key);struct slist_node *(*first)(struct single_list* list);struct slist_node *(*last)(struct single_list* list);struct slist_node *(*at)(struct single_list * list, int pos);struct slist_node *(*take_at)(struct single_list * list, int pos);struct slist_node *(*take_by_key)(struct single_list * list, void *key);struct single_list *(*remove)(struct single_list * list, struct slist_node * node);struct single_list *(*remove_at)(struct single_list *list, int pos);struct single_list *(*remove_by_key)(struct single_list *list, void *key);int (*length)(struct single_list * list);void (*clear)(struct single_list * list);void (*deletor)(struct single_list *list);
};struct single_list * new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp);#ifdef __cplusplus
}
#endif#endif // SLIST_H
? ? struct single_list 這個類，遵循我們前面介紹的基本原則，不再一一細說。有幾點需要提一下：#include?"slist.h"?? #include?<malloc.h>?? ?? static?struct?single_list?*?_add_node(struct?single_list?*list,?struct?slist_node?*node)?? {?? ?? ????if(list->tail)?? ????{?? ????????list->tail->next?=?node;?? ????????node->next?=?0;?? ????????list->tail?=?node;?? ????????list->size++;?? ????}?? ????else?? ????{?? ????????list->head?=?node;?? ????????list->tail?=?node;?? ????????node->next?=?0;?? ????????list->size?=?1;?? ????}?? ?? ????return?list;?? }?? ?? static?struct?single_list?*?_insert_node(struct?single_list?*?list,?int?pos,?struct?slist_node?*node)?? {?? ????if(pos?<?list->size)?? ????{?? ????????int?i?=?0;?? ????????struct?slist_node?*?p?=?list->head;?? ????????struct?slist_node?*?prev?=?list->head;?? ????????for(;?i?<?pos;?i++)?? ????????{?? ????????????prev?=?p;?? ????????????p?=?p->next;?? ????????}?? ????????if(p?==?list->head)?? ????????{?? ????????????/*?insert?at?head?*/?? ????????????node->next?=?list->head;?? ????????????list->head?=?node;?? ????????}?? ????????else?? ????????{?? ????????????prev->next?=?node;?? ????????????node->next?=?p;?? ????????}?? ?? ????????if(node->next?==?0)?list->tail?=?node;?? ????????list->size++;?? ????}?? ????else?? ????{?? ????????list->add(list,?node);?? ????}?? ?? ????return?list;?? }?? ?? static?struct?single_list?*?_replace(struct?single_list?*?list,?int?pos,?struct?slist_node?*node)?? {?? ????if(pos?<?list->size)?? ????{?? ????????int?i?=?0;?? ????????struct?slist_node?*?p?=?list->head;?? ????????struct?slist_node?*?prev?=?list->head;?? ????????for(;?i?<?pos;?i++)?? ????????{?? ????????????prev?=?p;?? ????????????p?=?p->next;?? ????????}?? ????????if(p?==?list->head)?? ????????{?? ????????????/*?replace?at?head?*/?? ????????????node->next?=?list->head->next;?? ????????????list->head?=?node;?? ????????}?? ????????else?? ????????{?? ????????????prev->next?=?node;?? ????????????node->next?=?p->next;?? ????????}?? ?? ????????if(node->next?==?0)?list->tail?=?node;?? ?? ????????if(list->free_node)?list->free_node(p);?? ????????else?free(p);?? ????}?? ?? ????return?list;?? }?? ?? static?struct?slist_node?*?_find_by_key(struct?single_list?*list,?void?*?key)?? {?? ????if(list->key_hit_test)?? ????{?? ????????struct?slist_node?*?p?=?list->head;?? ????????while(p)?? ????????{?? ????????????if(list->key_hit_test(p,?key)?==?0)?return?p;?? ????????????p?=?p->next;?? ????????}?? ????}?? ????return?0;?? }?? ?? static?struct?slist_node?*_first_of(struct?single_list*?list)?? {?? ????return?list->head;?? }?? ?? static?struct?slist_node?*_last_of(struct?single_list*?list)?? {?? ????return?list->tail;?? }?? ?? static?struct?slist_node?*_node_at(struct?single_list?*?list,?int?pos)?? {?? ????if(pos?<?list->size)?? ????{?? ????????int?i?=?0;?? ????????struct?slist_node?*?p?=?list->head;?? ????????for(;?i?<?pos;?i++)?? ????????{?? ????????????p?=?p->next;?? ????????}?? ????????return?p;?? ????}?? ?? ????return?0;?? }?? ?? static?struct?slist_node?*?_take_at(struct?single_list?*?list,?int?pos)?? {?? ????if(pos?<?list->size)?? ????{?? ????????int?i?=?0;?? ????????struct?slist_node?*?p?=?list->head;?? ????????struct?slist_node?*?prev?=?p;?? ????????for(;?i?<?pos?;?i++)?? ????????{?? ????????????prev?=?p;?? ????????????p?=?p->next;?? ????????}?? ????????if(p?==?list->head)?? ????????{?? ????????????list->head?=?p->next;?? ????????????if(list->head?==?0)?list->tail?=?0;?? ????????}?? ????????else?if(p?==?list->tail)?? ????????{?? ????????????list->tail?=?prev;?? ????????????prev->next?=?0;?? ????????}?? ????????else?? ????????{?? ????????????prev->next?=?p->next;?? ????????}?? ?? ????????list->size--;?? ?? ????????p->next?=?0;?? ????????return?p;?? ????}?? ?? ????return?0;?? }?? ?? static?struct?slist_node?*?_take_by_key(struct?single_list?*?list,?void?*key)?? {?? ????if(list->key_hit_test)?? ????{?? ????????struct?slist_node?*?p?=?list->head;?? ????????struct?slist_node?*?prev?=?p;?? ????????while(p)?? ????????{?? ????????????if(list->key_hit_test(p,?key)?==?0)?break;?? ????????????prev?=?p;?? ????????????p?=?p->next;?? ????????}?? ?? ????????if(p)?? ????????{?? ????????????if(p?==?list->head)?? ????????????{?? ????????????????list->head?=?p->next;?? ????????????????if(list->head?==?0)?list->tail?=?0;?? ????????????}?? ????????????else?if(p?==?list->tail)?? ????????????{?? ????????????????list->tail?=?prev;?? ????????????????prev->next?=?0;?? ????????????}?? ????????????else?? ????????????{?? ????????????????prev->next?=?p->next;?? ????????????}?? ?? ????????????list->size--;?? ?? ????????????p->next?=?0;?? ????????????return?p;?? ????????}?? ????}?? ????return?0;?? }?? ?? static?struct?single_list?*_remove_node(struct?single_list?*?list,?struct?slist_node?*?node)?? {?? ????struct?slist_node?*?p?=?list->head;?? ????struct?slist_node?*?prev?=?p;?? ????while(p)?? ????{?? ????????if(p?==?node)?break;?? ????????prev?=?p;?? ????????p?=?p->next;?? ????}?? ?? ????if(p)?? ????{?? ????????if(p?==?list->head)?? ????????{?? ????????????list->head?=?list->head->next;?? ????????????if(list->head?==?0)?list->tail?=?0;?? ????????}?? ????????else?if(p?==?list->tail)?? ????????{?? ????????????prev->next?=?0;?? ????????????list->tail?=?prev;?? ????????}?? ????????else?? ????????{?? ????????????prev->next?=?p->next;?? ????????}?? ?? ????????if(list->free_node)?list->free_node(p);?? ????????else?free(p);?? ?? ????????list->size--;?? ????}?? ????return?list;?? }?? ?? static?struct?single_list?*_remove_at(struct?single_list?*list,?int?pos)?? {?? ????if(pos?<?list->size)?? ????{?? ????????int?i?=?0;?? ????????struct?slist_node?*?p?=?list->head;?? ????????struct?slist_node?*?prev?=?p;?? ????????for(;?i?<?pos?;?i++)?? ????????{?? ????????????prev?=?p;?? ????????????p?=?p->next;?? ????????}?? ????????if(p?==?list->head)?? ????????{?? ????????????list->head?=?p->next;?? ????????????if(list->head?==?0)?list->tail?=?0;?? ????????}?? ????????else?if(p?==?list->tail)?? ????????{?? ????????????list->tail?=?prev;?? ????????????prev->next?=?0;?? ????????}?? ????????else?? ????????{?? ????????????prev->next?=?p->next;?? ????????}?? ?? ????????if(list->free_node)?list->free_node(p);?? ????????else?free(p);?? ?? ????????list->size--;?? ????}?? ?? ????return?list;?? }?? ?? static?struct?single_list?*_remove_by_key(struct?single_list?*list,?void?*key)?? {?? ????if(list->key_hit_test)?? ????{?? ????????struct?slist_node?*?p?=?list->head;?? ????????struct?slist_node?*?prev?=?p;?? ????????while(p)?? ????????{?? ????????????if(list->key_hit_test(p,?key)?==?0)?break;?? ????????????prev?=?p;?? ????????????p?=?p->next;?? ????????}?? ?? ????????if(p)?? ????????{?? ????????????if(p?==?list->head)?? ????????????{?? ????????????????list->head?=?list->head->next;?? ????????????????if(list->head?==?0)?list->tail?=?0;?? ????????????}?? ????????????else?if(p?==?list->tail)?? ????????????{?? ????????????????prev->next?=?0;?? ????????????????list->tail?=?prev;?? ????????????}?? ????????????else?? ????????????{?? ????????????????prev->next?=?p->next;?? ????????????}?? ?? ????????????if(list->free_node)?list->free_node(p);?? ????????????else?free(p);?? ?? ????????????list->size--;?? ????????}?? ????}?? ?? ????return?list;?? }?? ?? static?int?_length_of(struct?single_list?*?list)?? {?? ????return?list->size;?? }?? ?? static?void?_clear_list(struct?single_list?*?list)?? {?? ????struct?slist_node?*?p?=?list->head;?? ????struct?slist_node?*?p2;?? ????while(p)?? ????{?? ????????p2?=?p;?? ????????p?=?p->next;?? ?? ????????if(list->free_node)?list->free_node(p2);?? ????????else?free(p2);?? ????}?? ?? ????list->head?=?0;?? ????list->tail?=?0;?? ????list->size?=?0;?? }?? ?? static?void?_delete_single_list(struct?single_list?*list)?? {?? ????list->clear(list);?? ????free(list);?? }?? ?? struct?single_list?*?new_single_list(list_op_free_node?op_free,?list_op_key_hit_test?op_cmp)?? {?? ????struct?single_list?*list?=?(struct?single_list?*)malloc(sizeof(struct?single_list));?? ????list->head?=?0;?? ????list->tail?=?0;?? ????list->size?=?0;?? ????list->free_node?=?op_free;?? ????list->key_hit_test?=?op_cmp;?? ?? ????list->add?=?_add_node;?? ????list->insert?=?_insert_node;?? ????list->replace?=?_replace;?? ????list->find_by_key?=?_find_by_key;?? ????list->first?=?_first_of;?? ????list->last?=?_last_of;?? ????list->at?=?_node_at;?? ????list->take_at?=?_take_at;?? ????list->take_by_key?=?_take_by_key;?? ????list->remove?=?_remove_node;?? ????list->remove_at?=?_remove_at;?? ????list->remove_by_key?=?_remove_by_key;?? ????list->length?=?_length_of;?? ????list->clear?=?_clear_list;?? ????list->deletor?=?_delete_single_list;?? ?? ????return?list;?? }??
#include "slist.h"
#include <malloc.h>static struct single_list * _add_node(struct single_list *list, struct slist_node *node)
{if(list->tail){list->tail->next = node;node->next = 0;list->tail = node;list->size++;}else{list->head = node;list->tail = node;node->next = 0;list->size = 1;}return list;
}static struct single_list * _insert_node(struct single_list * list, int pos, struct slist_node *node)
{if(pos < list->size){int i = 0;struct slist_node * p = list->head;struct slist_node * prev = list->head;for(; i < pos; i++){prev = p;p = p->next;}if(p == list->head){/* insert at head */node->next = list->head;list->head = node;}else{prev->next = node;node->next = p;}if(node->next == 0) list->tail = node;list->size++;}else{list->add(list, node);}return list;
}static struct single_list * _replace(struct single_list * list, int pos, struct slist_node *node)
{if(pos < list->size){int i = 0;struct slist_node * p = list->head;struct slist_node * prev = list->head;for(; i < pos; i++){prev = p;p = p->next;}if(p == list->head){/* replace at head */node->next = list->head->next;list->head = node;}else{prev->next = node;node->next = p->next;}if(node->next == 0) list->tail = node;if(list->free_node) list->free_node(p);else free(p);}return list;
}static struct slist_node * _find_by_key(struct single_list *list, void * key)
{if(list->key_hit_test){struct slist_node * p = list->head;while(p){if(list->key_hit_test(p, key) == 0) return p;p = p->next;}}return 0;
}static struct slist_node *_first_of(struct single_list* list)
{return list->head;
}static struct slist_node *_last_of(struct single_list* list)
{return list->tail;
}static struct slist_node *_node_at(struct single_list * list, int pos)
{if(pos < list->size){int i = 0;struct slist_node * p = list->head;for(; i < pos; i++){p = p->next;}return p;}return 0;
}static struct slist_node * _take_at(struct single_list * list, int pos)
{if(pos < list->size){int i = 0;struct slist_node * p = list->head;struct slist_node * prev = p;for(; i < pos ; i++){prev = p;p = p->next;}if(p == list->head){list->head = p->next;if(list->head == 0) list->tail = 0;}else if(p == list->tail){list->tail = prev;prev->next = 0;}else{prev->next = p->next;}list->size--;p->next = 0;return p;}return 0;
}static struct slist_node * _take_by_key(struct single_list * list, void *key)
{if(list->key_hit_test){struct slist_node * p = list->head;struct slist_node * prev = p;while(p){if(list->key_hit_test(p, key) == 0) break;prev = p;p = p->next;}if(p){if(p == list->head){list->head = p->next;if(list->head == 0) list->tail = 0;}else if(p == list->tail){list->tail = prev;prev->next = 0;}else{prev->next = p->next;}list->size--;p->next = 0;return p;}}return 0;
}static struct single_list *_remove_node(struct single_list * list, struct slist_node * node)
{struct slist_node * p = list->head;struct slist_node * prev = p;while(p){if(p == node) break;prev = p;p = p->next;}if(p){if(p == list->head){list->head = list->head->next;if(list->head == 0) list->tail = 0;}else if(p == list->tail){prev->next = 0;list->tail = prev;}else{prev->next = p->next;}if(list->free_node) list->free_node(p);else free(p);list->size--;}return list;
}static struct single_list *_remove_at(struct single_list *list, int pos)
{if(pos < list->size){int i = 0;struct slist_node * p = list->head;struct slist_node * prev = p;for(; i < pos ; i++){prev = p;p = p->next;}if(p == list->head){list->head = p->next;if(list->head == 0) list->tail = 0;}else if(p == list->tail){list->tail = prev;prev->next = 0;}else{prev->next = p->next;}if(list->free_node) list->free_node(p);else free(p);list->size--;}return list;
}static struct single_list *_remove_by_key(struct single_list *list, void *key)
{if(list->key_hit_test){struct slist_node * p = list->head;struct slist_node * prev = p;while(p){if(list->key_hit_test(p, key) == 0) break;prev = p;p = p->next;}if(p){if(p == list->head){list->head = list->head->next;if(list->head == 0) list->tail = 0;}else if(p == list->tail){prev->next = 0;list->tail = prev;}else{prev->next = p->next;}if(list->free_node) list->free_node(p);else free(p);list->size--;}}return list;
}static int _length_of(struct single_list * list)
{return list->size;
}static void _clear_list(struct single_list * list)
{struct slist_node * p = list->head;struct slist_node * p2;while(p){p2 = p;p = p->next;if(list->free_node) list->free_node(p2);else free(p2);}list->head = 0;list->tail = 0;list->size = 0;
}static void _delete_single_list(struct single_list *list)
{list->clear(list);free(list);
}struct single_list * new_single_list(list_op_free_node op_free, list_op_key_hit_test op_cmp)
{struct single_list *list = (struct single_list *)malloc(sizeof(struct single_list));list->head = 0;list->tail = 0;list->size = 0;list->free_node = op_free;list->key_hit_test = op_cmp;list->add = _add_node;list->insert = _insert_node;list->replace = _replace;list->find_by_key = _find_by_key;list->first = _first_of;list->last = _last_of;list->at = _node_at;list->take_at = _take_at;list->take_by_key = _take_by_key;list->remove = _remove_node;list->remove_at = _remove_at;list->remove_by_key = _remove_by_key;list->length = _length_of;list->clear = _clear_list;list->deletor = _delete_single_list;return list;
}
? ? 上面的代碼就不一一細說了，下面是測試代碼： [cpp] view plaincopy print?/*?call?1?or?N?arguments?function?of?struct?*/?? #define?ST_CALL(THIS,func,args...)?((THIS)->func(THIS,args))?? ?? /*?call?none-arguments?function?of?struct?*/?? #define?ST_CALL_0(THIS,func)?((THIS)->func(THIS))?? ?? struct?int_node?{?? ????struct?slist_node?node;?? ????int?id;?? };?? ?? struct?string_node?{?? ????struct?slist_node?node;?? ????char?name[16];?? };?? ?? ?? static?int?int_free_flag?=?0;?? static?void?_int_child_free(struct?slist_node?*node)?? {?? ????free(node);?? ????if(!int_free_flag)?? ????{?? ????????int_free_flag?=?1;?? ????????printf("int?node?free\n");?? ????}?? }?? ?? static?int?_int_slist_hittest(struct?slist_node?*?node,?void?*key)?? {?? ????struct?int_node?*?inode?=?NODE_T(node,?struct?int_node);?? ????int?ikey?=?(int)key;?? ????return?(inode->id?==?ikey???0?:?1);?? }?? ?? static?int?string_free_flag?=?0;?? static?void?_string_child_free(struct?slist_node?*node)?? {?? ????free(node);?? ????if(!string_free_flag)?? ????{?? ????????string_free_flag?=?1;?? ????????printf("string?node?free\n");?? ????}?? }?? ?? static?int?_string_slist_hittest(struct?slist_node?*?node,?void?*key)?? {?? ????struct?string_node?*?sn?=?(struct?string_node*)node;?? ????return?strcmp(sn->name,?(char*)key);?? }?? ?? void?int_slist_test()?? {?? ????struct?single_list?*?list?=?new_single_list(_int_child_free,?_int_slist_hittest);?? ????struct?int_node?*?node?=?0;?? ????struct?slist_node?*?bn?=?0;?? ????int?i?=?0;?? ?? ????printf("create?list?&&?nodes:\n");?? ????for(;?i?<?100;?i++)?? ????{?? ????????node?=?(struct?int_node*)malloc(sizeof(struct?int_node));?? ????????node->id?=?i;?? ????????if(i%10)?? ????????{?? ????????????list->add(list,?node);?? ????????}?? ????????else?? ????????{?? ????????????list->insert(list,?1,?node);?? ????????}?? ????}?? ????printf("create?100?nodes?end\n----\n");?? ????printf("first?is?:?%d,?last?is:?%d\n----\n",?? ???????????NODE_T(?ST_CALL_0(list,?first),?struct?int_node?)->id,?? ???????????NODE_T(?ST_CALL_0(list,?last?),?struct?int_node?)->id);?? ?? ????assert(list->size?==?100);?? ?? ????printf("list?traverse:\n");?? ????for(i?=?0;?i?<?100;?i++)?? ????{?? ????????if(i%10?==?0)?printf("\n");?? ????????bn?=?list->at(list,?i);?? ????????node?=?NODE_T(bn,?struct?int_node);?? ????????printf("?%d",?node->id);?? ????}?? ????printf("\n-----\n");?? ?? ????printf("find?by?key?test,?key=42:\n");?? ????bn?=?list->find_by_key(list,?(void*)42);?? ????assert(bn?!=?0);?? ????node?=?NODE_T(bn,?struct?int_node);?? ????printf("find?node(key=42),?%d\n------\n",?node->id);?? ?? ????printf("remove?node?test,?remove?the?10th?node:\n");?? ????bn?=?list->at(list,?10);?? ????node?=?NODE_T(bn,?struct?int_node);?? ????printf("??node?10?is:?%d\n",?node->id);?? ????printf("??now?remove?node?10\n");?? ????list->remove_at(list,?10);?? ????printf("?node?10?was?removed,?check?node?10?again:\n");?? ????bn?=?list->at(list,?10);?? ????node?=?NODE_T(bn,?struct?int_node);?? ????printf("??now?node?10?is:?%d\n------\n",?node->id);?? ?? ????printf("replace?test,?replace?node?12?with?id?1200:\n");?? ????bn?=?list->at(list,?12);?? ????node?=?NODE_T(bn,?struct?int_node);?? ????printf("??now?node?12?is?:?%d\n",?node->id);?? ????node?=?(struct?int_node*)malloc(sizeof(struct?int_node));?? ????node->id?=?1200;?? ????list->replace(list,?12,?node);?? ????bn?=?list->at(list,?12);?? ????node?=?NODE_T(bn,?struct?int_node);?? ????printf("??replaced,?now?node?12?is?:?%d\n----\n",?node->id);?? ?? ????printf("test?remove:\n");?? ????ST_CALL(list,?remove,?bn);?? ????bn?=?ST_CALL(list,?find_by_key,?(void*)1200);?? ????assert(bn?==?0);?? ????printf("test?remove?ok\n----\n");?? ????printf("test?remove_by_key(90):\n");?? ????ST_CALL(list,?remove_by_key,?(void*)90);?? ????bn?=?ST_CALL(list,?find_by_key,?(void*)90);?? ????assert(bn?==?0);?? ????printf("test?remove_by_key(90)?end\n----\n");?? ????printf("test?take_at(80):\n");?? ????bn?=?ST_CALL(list,?take_at,?80);?? ????printf("??node?80?is:?%d\n",?NODE_T(bn,?struct?int_node)->id);?? ????free(bn);?? ????printf("test?take_at(80)?end\n");?? ?? ????int_free_flag?=?0;?? ????printf("delete?list?&&?nodes:\n");?? ????list->deletor(list);?? ????printf("delete?list?&&?nodes?end\n");?? ????printf("\n?test?add/insert/remove/delete/find_by_key/replace...\n");?? }?? ?? void?string_slist_test()?? {?? ????struct?single_list?*?list?=?new_single_list(_string_child_free,?_string_slist_hittest);?? }?? ?? void?slist_test()?? {?? ????int_slist_test();?? ????string_slist_test();?? }??
/* call 1 or N arguments function of struct */
#define ST_CALL(THIS,func,args...) ((THIS)->func(THIS,args))/* call none-arguments function of struct */
#define ST_CALL_0(THIS,func) ((THIS)->func(THIS))struct int_node {struct slist_node node;int id;
};struct string_node {struct slist_node node;char name[16];
};static int int_free_flag = 0;
static void _int_child_free(struct slist_node *node)
{free(node);if(!int_free_flag){int_free_flag = 1;printf("int node free\n");}
}static int _int_slist_hittest(struct slist_node * node, void *key)
{struct int_node * inode = NODE_T(node, struct int_node);int ikey = (int)key;return (inode->id == ikey ? 0 : 1);
}static int string_free_flag = 0;
static void _string_child_free(struct slist_node *node)
{free(node);if(!string_free_flag){string_free_flag = 1;printf("string node free\n");}
}static int _string_slist_hittest(struct slist_node * node, void *key)
{struct string_node * sn = (struct string_node*)node;return strcmp(sn->name, (char*)key);
}void int_slist_test()
{struct single_list * list = new_single_list(_int_child_free, _int_slist_hittest);struct int_node * node = 0;struct slist_node * bn = 0;int i = 0;printf("create list && nodes:\n");for(; i < 100; i++){node = (struct int_node*)malloc(sizeof(struct int_node));node->id = i;if(i%10){list->add(list, node);}else{list->insert(list, 1, node);}}printf("create 100 nodes end\n----\n");printf("first is : %d, last is: %d\n----\n",NODE_T( ST_CALL_0(list, first), struct int_node )->id,NODE_T( ST_CALL_0(list, last ), struct int_node )->id);assert(list->size == 100);printf("list traverse:\n");for(i = 0; i < 100; i++){if(i%10 == 0) printf("\n");bn = list->at(list, i);node = NODE_T(bn, struct int_node);printf(" %d", node->id);}printf("\n-----\n");printf("find by key test, key=42:\n");bn = list->find_by_key(list, (void*)42);assert(bn != 0);node = NODE_T(bn, struct int_node);printf("find node(key=42), %d\n------\n", node->id);printf("remove node test, remove the 10th node:\n");bn = list->at(list, 10);node = NODE_T(bn, struct int_node);printf(" node 10 is: %d\n", node->id);printf(" now remove node 10\n");list->remove_at(list, 10);printf(" node 10 was removed, check node 10 again:\n");bn = list->at(list, 10);node = NODE_T(bn, struct int_node);printf(" now node 10 is: %d\n------\n", node->id);printf("replace test, replace node 12 with id 1200:\n");bn = list->at(list, 12);node = NODE_T(bn, struct int_node);printf(" now node 12 is : %d\n", node->id);node = (struct int_node*)malloc(sizeof(struct int_node));node->id = 1200;list->replace(list, 12, node);bn = list->at(list, 12);node = NODE_T(bn, struct int_node);printf(" replaced, now node 12 is : %d\n----\n", node->id);printf("test remove:\n");ST_CALL(list, remove, bn);bn = ST_CALL(list, find_by_key, (void*)1200);assert(bn == 0);printf("test remove ok\n----\n");printf("test remove_by_key(90):\n");ST_CALL(list, remove_by_key, (void*)90);bn = ST_CALL(list, find_by_key, (void*)90);assert(bn == 0);printf("test remove_by_key(90) end\n----\n");printf("test take_at(80):\n");bn = ST_CALL(list, take_at, 80);printf(" node 80 is: %d\n", NODE_T(bn, struct int_node)->id);free(bn);printf("test take_at(80) end\n");int_free_flag = 0;printf("delete list && nodes:\n");list->deletor(list);printf("delete list && nodes end\n");printf("\n test add/insert/remove/delete/find_by_key/replace...\n");
}void string_slist_test()
{struct single_list * list = new_single_list(_string_child_free, _string_slist_hittest);
}void slist_test()
{int_slist_test();string_slist_test();
}
? ? 測試代碼里主要演示了：
? ? 這里實現的單鏈表，可以存儲任意數據類型，支持增、刪、改、查找、插入等基本操作。（本文提供的是完整代碼，可能有些長。）
? ? 下面是頭文件：
[cpp] view plaincopy print?? ? struct single_list 這個類，遵循我們前面介紹的基本原則，不再一一細說。有幾點需要提一下：
- 我們定義了 slist_node 作為鏈表節點的基類，用戶自定義的節點，都必須從 slist_node 繼承
- 為了支持節點（ node ）的釋放，我們引入一個回調函數 list_op_free_node?，這個回調需要在創建鏈表時傳入
- 為了支持查找，引入另外一個回調函數?list_op_key_hit_test?
? ? 好了，下面看實現文件：
[cpp] view plaincopy print?? ? 上面的代碼就不一一細說了，下面是測試代碼： [cpp] view plaincopy print?
? ? 測試代碼里主要演示了：
- 自定義鏈表節點類型
- 定義釋放回調
- 定義用于查找的 hit test 回調
- 如何創建鏈表
- 如何使用（ add 、remove 、 take 、find 、 insert 等）
? ? 相信到這里，單鏈表的使用已經不成問題了。
? ? 以單鏈表為基礎，可以進一步實現很多數據結構，比如樹（兄弟孩子表示法），比如 key-value 鏈表等等。接下來根據例子的需要，會擇機進行展示。
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的C语言面向对象编程（五）：单链表实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C语言面向对象编程（四）：面向接口编程
- 下一篇： em算法怎么对应原有分类_机器学习基础-