单链表

single_list.c

/** @file single_list.c
  * @brief 单链表
  * @author [email protected]
  * @date 2010-7-30
  * @version 0.1
  * @note 单链表的源文件
  */
#include <stdlib.h>
#include "single_list.h"


int single_list_create(single_list_node_t **l, 
                      const single_list_node_data_t data[], int n)
{
    int i;
    single_list_node_t *ph;

    // 分配头节点
    *l = (single_list_node_t*)malloc(sizeof(single_list_node_t));
    (*l)->next = NULL;
    ph = *l;
    
    /* 插入数据*/
    for(i = 0; i < n; i++){
        single_list_node_t *p = (single_list_node_t*)malloc(sizeof(
            single_list_node_t));
        p->data = data[i];
        p->next = ph->next;
        ph->next = p;
    }
    return 0;
}

single_list_node_t* single_list_find(const single_list_node_t *l, int k)
{
    const single_list_node_t* p = l;
    int i =0;

    while(p != NULL && i < k) {
        p = p->next;
        i++;
    }
    return (single_list_node_t*)p;
}

int single_list_insert(single_list_node_t *l, int k, 
                        single_list_node_data_t elem)
{
    single_list_node_t *p, *q;

    p = single_list_find(l, k -1);
    if(p == NULL) return ERR_NULL_POINTER;

    q = (single_list_node_t *) malloc(sizeof(single_list_node_t));
    if(q == NULL) return ERR_MALLOC_FAILED;

    q->data = elem;
    
    q->next = p->next;
    p->next = q;
    return SUCCESS;
}

single_list_node_t* single_list_remove(single_list_node_t *l, int k)
{
    single_list_node_t *p, *q;

    p = single_list_find(l, k -1);
    if(p == NULL) {
        return NULL;
    }

    q = p->next;
    p->next = q->next;
	
    return q;
}

single_list.h

/** @file single_list.h
  * @brief 单链表
  * @author [email protected]
  * @date 2010-7-30
  * @version 0.1
  * @note 单链表的头文件
 */
#ifndef _SINGLE_LIST_H_
#define _SINGLE_LIST_H_

#ifdef __cplusplus
extern "C"
{
#endif


#include "config.h"

/** 链表结点所带的数据，这里用int仅作演示. */
typedef int single_list_node_data_t;
/** 单链表结点. */
typedef struct single_list_node_t single_list_node_t;


/**
  *@struct
  *@brief 单链表节点
  *@author [email protected]
  *@note 无
  */
struct single_list_node_t {
    /* 节点中存放实际数据*/
    single_list_node_data_t data;
    /* 指向下一个节点*/
    single_list_node_t *next; 
};


/** 
  * @brief 建立单链表，头插法
  * @author [email protected]
  * @param[out] l 带头节点的单链表的头指针的指针
  * @param[in] data 原始数据
  * @param[in] n 元素个数
  * @return 成功返回0，失败返回错误码。
  * @remarks 无
  */
extern int single_list_create(single_list_node_t **l, 
                     const single_list_node_data_t data[], int n);

/** 
  * @brief 查找
  * @author [email protected]
  * @param[in] l 带头节点的单链表的头指针
  * @param[in] k 查找第k个元素
  * @return 返回指向第k个元素的地址，失败则返回NULL
  * @note k是从开始而不是
  * @remarks 无
  */
extern single_list_node_t* single_list_find(
const single_list_node_t *l,int k);

/** 
  * @brief 插入
  * @author [email protected]
  * @param[in] l 带头节点的点链表的头指针
  * @param[in] k 将新元素插入到第k个位置
  * @param[in] elem 要插入的元素
  * @return 成功返回SUCCESS，失败返回错误码
  * @note k是从开始而不是
  * @remarks 无
  */
int single_list_insert(single_list_node_t *l, int k, 
single_list_node_data_t elem);
/** 
  * @brief 删除
  * @author [email protected]
  * @param[in] l 带头节点的点链表的头指针
  * @param[in] k 查找第k个元素
  * @return 成功返回被删节点的地址，失败返回NULL
  * @note 无
  * @remarks 无
  */
extern single_list_node_t* single_list_remove(single_list_node_t *l, 
int k);


#ifdef __cplusplus
}
#endif

#endif /* end of _SINGLE_LIST_H_ */