自己造轮子系列 ： 链表

复制

#ifndef SYS_LIST_H

#define SYS_LIST_H



#include        "stdint.h"

#include        "string.h"



#define list_entry(ptr, type, member)   \

    ( ( type * ) ( ( char * ) ( ptr ) - ( size_t ) ( & ( ( type * ) 0 )->member ) ) )



#define list_zero(ptr)                  \

    memset ( ptr, 0, sizeof ( struct list_node_t ) )



/*  

    struct demo_t

    {

        struct list_node_t  node ;

    } ;



    struct demo_t demo ;

    list_zero ( & demo.node ) ;



    void callback ( struct list_node_t * list )

    {

        struct demo_t * demo = list_entry ( list  , struct demo_t  , node ) ;

    }

*/



struct list_obj_t ;



struct list_node_t

{

    struct list_node_t  * prev ;

    struct list_node_t  * next ;

} ;



void list_initialize ( void * ( * malloc ) ( size_t size ), void ( * free ) ( void * p ) ) ;



struct list_obj_t * list_create ( void ) ;

void list_insert ( struct list_obj_t * obj, struct list_node_t * list ) ;

void list_delete ( struct list_obj_t * obj, struct list_node_t * list ) ;

int  list_number ( struct list_obj_t * obj ) ;

void list_poll ( struct list_obj_t * obj,  void ( * callback ) ( struct list_node_t * list ) ) ;

void list_printf ( struct list_obj_t * obj ) ;

void list_destory ( struct list_obj_t * obj ) ;



#endif

复制

#include        "list.h"

#include        "stdlib.h"

#include        "stdio.h"

#include        "string.h"



struct list_driver_t {

    void * ( * malloc ) ( size_t size ) ;

    void ( * free ) ( void * p ) ;

} ;



struct list_obj_t {

    struct list_node_t  node ;

} ;



static struct list_driver_t driver = { malloc, free } ;



void list_initialize ( void * ( * malloc ) ( size_t size ), void ( * free ) ( void * p ) ) {

    driver.malloc = malloc ;

    driver.free = free ;

}



struct list_obj_t * list_create ( void ) {

    struct list_obj_t       * obj ;



    obj = ( struct list_obj_t * ) driver.malloc ( sizeof ( struct list_obj_t ) ) ;

    list_zero ( & obj->node ) ;



    return obj ;

}



void list_destory ( struct list_obj_t * obj ) {

    driver.free ( obj ) ;

}



void list_insert ( struct list_obj_t  * obj, struct list_node_t * list ) {

    struct list_node_t      * curr = & obj->node ;



    while ( curr->next ) {

        if ( curr == list ) {

            return ;

        }

        curr = curr->next ;

    }



    curr->next = list ;

    list->prev = curr ;

}



int  list_number ( struct list_obj_t * obj ) {

    struct list_node_t      * curr = & obj->node ;

    int                     cnt = 0 ;



    do {

        if ( curr->prev ) {

            cnt += 1 ;

        }

        curr = curr->next ;

    } while ( curr ) ;



    return cnt ;

}



void list_delete ( struct list_obj_t * obj,  struct list_node_t * list ) {

    struct list_node_t      * curr = & obj->node ;



    do {

        if ( curr == list ) {

            list->prev->next = list->next ;

            if ( list->next ) {

                list->next->prev = list->prev ;

            }

            break ;

        }



        curr = curr->next ;

    } while ( curr ) ;

}





void list_poll ( struct list_obj_t * obj, void ( * callback ) ( struct list_node_t * list ) ) {

    struct list_node_t      * curr = & obj->node ;



    do {

        if ( curr->prev ) {

            callback ( curr ) ;

        }

        curr = curr->next ;

    } while ( curr ) ;

}



void list_printf ( struct list_obj_t  * obj ) {

    struct list_node_t      * curr = & obj->node ;

    int                     cnt = 0 ;



    do {



        printf ( "    %2d - node %08x : prev %08x , next %08x \r\n", cnt, curr, curr->prev, curr->next ) ;

        cnt ++ ;

        curr = curr->next ;

    } while ( curr ) ;

}

链表刚开始学的时候总是搞不懂，接触的多了也就会了。

链表网上例程挺多的，自己能实现一个也挺不错的。

当初面试也会问的一个问题，因为链表主要考C指针操作。