雙向鏈表和動態數組

最近在看李先靜先生的《系統程序員成長計劃》，正好復習一下自己的C語言基礎。李先生所認為的雙向鏈表和動態數組是真實項目中最常見的應用我很贊同，還記得我第一個SIP TRUNK項目裡電話請求就是用鏈表實現的隊列。不過李先生講的更加抽象，可能是因為他站在一個跨平台的思想高度來思考問題的，所以書中要求實現的雙向鏈表和動態數組都是不限數據類型，我沒有那麼高的思想水平，就實現了一個整數的雙向鏈表和動態數組，主要是練習練習，畢竟好久沒有使用C語言編程了。

寫著寫著，我發現原來把它們寫成通用的並不難，希望大家參考了我的後可以自己實現，把接口改為通用類型，當然雖然我自己測試過了但程序中的bug肯定還是不少的，我盡量改正吧！如果大家發現了新的bug可以馬上告訴我，我立馬修改，謝謝！

雙向鏈表：

Line.h

#ifdef _cplusplus  
extern "C" {  
#endif  
 
#define EMPTY  0  
#define HEAD   0  
#define TRUE   0  
#define FALSE  1  
#define ERRNUM 5  
#define LINEISNULL     0  
#define LOCALUPNODENUM 1  
#define MEMORYEMPTY    2  
#define NOLINE         3  
 
typedef struct _lineNode {  
    int data;  
    struct _lineNode *prep;  
    struct _lineNode *next;  
}LineNode;  
 
typedef struct _lineHead {  
    LineNode *head;  
    int NodeNum;  
}LineHead;  
 
LineHead *CreateLine();  
void DeleteLine(LineHead *linehead);  
LineNode *CreateNode(int data);  
void PushNode(LineHead *linehead, LineNode *linenode);  
//調用者保障鏈表不為空  
LineNode *PopNode(LineHead *linehead);  
//調用者保障local小於linehead->NodeNum  
void InsertNode(LineHead *linehead, LineNode *linenode, int local);  
//調用者保障local小於linehead->NodeNum  
LineNode *GetNode(LineHead *linehead, int local);  
//調用者保障local小於linehead->NodeNum  
int GetNodeData(LineHead *linehead, int local);  
//回調函數由調用者完成  
//int ListForEach(LineHead *linehead, Callbcak visit, void *ctx);  
void ShowLine(LineHead *linehead);  
 
#ifdef _cplusplus  
}  
#endif 

Line.c

#include <stdio.h>  
#include <stdlib.h>  
#include "Line_1_1.h"  
 
char *errorstring[ERRNUM] = {"The line is null!", "local is upper than line's node number!",   
                             "Memory can't be alloced!", "Line has not created!"};  
 
LineHead *CreateLine()  
{  
    LineHead *temp;  
 
    temp = (LineHead *)malloc(sizeof(LineHead));  
    if (NULL == temp)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[MEMORYEMPTY]);  
        exit(0);  
    }  
    temp->head = NULL;  
    temp->NodeNum = 0;  
 
    return temp;  
}  
 
void DeleteLine(LineHead *linehead)  
{  
    LineNode *temp;  
      
    temp = linehead->head;  
    while (NULL != temp)  
    {  
        linehead->head = linehead->head->next;  
        linehead->NodeNum--;  
        free(temp);  
        temp = linehead->head;  
    }  
    free(linehead);  
}  
 
LineNode *CreateNode(int data)  
{  
    LineNode *p;  
 
    p = (LineNode *)malloc(sizeof(LineNode));  
    if (NULL == p)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[MEMORYEMPTY]);  
        exit(0);  
    }  
    p->data = data;  
    p->next = p->prep = NULL;  
      
    return p;  
}  
 
void PushNode(LineHead *linehead, LineNode *linenode)  
{  
    LineNode *p, *prep = NULL;  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == linehead)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NOLINE]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    p = linehead->head;  
    for (i = 0; i < linehead->NodeNum; i++)  
    {  
        prep = p;  
        p = p->next;  
    }  
 
    p = (LineNode *)malloc(sizeof(LineNode));  
    if (NULL == p)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[MEMORYEMPTY]);  
        exit(0);  
    }  
    if (EMPTY == linehead->NodeNum)  
    {  
        linehead->head = p;  
        p->prep = NULL;  
    }  
    else 
    {  
        p->prep = prep;  
        prep->next = p;  
    }  
    p->data = linenode->data;  
    p->next = NULL;  
    linehead->NodeNum++;  
}  
 
 
//調用者保障鏈表不為空  
LineNode *PopNode(LineHead *linehead)  
{  
    LineNode *p;  
    //改為斷言  
    //######################  
    if (NULL == linehead)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NOLINE]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
    //改為斷言  
    //######################  
    if (NULL == linehead->head)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LINEISNULL]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
      
    p = linehead->head;  
    while (NULL != p->next)  
    {  
        p = p->next;  
    }  
    if (p == linehead->head)  
    {  
        linehead->head = NULL;  
    }  
    else 
    {  
        p->prep->next = NULL;  
    }  
    linehead->NodeNum--;  
    //保障傳出參數使用不會出現越權訪問  
    p->next = p->prep = NULL;  
 
    return p;  
}  
 
//調用者保障local小於linehead->NodeNum  
void InsertNode(LineHead *linehead, LineNode *linenode, int local)  
{  
    LineNode *p, *temp, *prep = NULL;  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == linehead)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LINEISNULL]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
    //改為斷言  
    //######################  
    if (local >= linehead->NodeNum)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LOCALUPNODENUM]);  
        //return ERROR;  
        exit(0);  
    }  
    //######################  
 
    p = linehead->head;  
    for (i = 0; i < local; i++)  
    {  
        prep = p;  
        p = p->next;  
    }  
    temp = (LineNode *)malloc(sizeof(LineNode));  
    if (NULL == temp)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[MEMORYEMPTY]);  
        exit(0);  
    }  
    temp->data = linenode->data;  
    if (HEAD == local)  
    {  
        linehead->head = temp;  
        temp->prep = NULL;  
    }  
    else 
    {  
        prep->next = temp;  
        temp->prep = prep;  
    }  
    p->prep = temp;  
    temp->next = p;  
    linehead->NodeNum++;  
    //return TRUE;  
}  
 
//調用者保障local小於linehead->NodeNum  
LineNode *GetNode(LineHead *linehead, int local)  
{  
    LineNode *p;  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == linehead)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LINEISNULL]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
    //改為斷言  
    //######################  
    if (local >= linehead->NodeNum)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LOCALUPNODENUM]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    p = linehead->head;  
    for (i = 0; i < local; i++)  
    {  
        p = p->next;  
    }  
 
    if (p == linehead->head)  
    {  
        linehead->head = p->next;  
        if (NULL != p->next)  
        {  
            p->next->prep = NULL;  
        }  
    }  
    else 
    {  
        p->prep->next = p->next;  
        if (NULL != p->next)  
        {  
            p->next->prep = p->prep;  
        }  
    }  
    linehead->NodeNum--;  
    //保障傳出參數使用不會出現越權訪問  
    p->next = p->prep = NULL;  
 
    return p;  
}  
 
//調用者保障local小於linehead->NodeNum  
int GetNodeData(LineHead *linehead, int local)  
{  
    LineNode *p;  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == linehead)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LINEISNULL]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
    //改為斷言  
    //######################  
    if (local >= linehead->NodeNum)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LOCALUPNODENUM]);  
        //return ERROR;  
        exit(0);  
    }  
    //######################  
 
    p = linehead->head;  
    for (i = 0; i < local; i++)  
    {  
        p = p->next;  
    }  
 
    return p->data;  
}  
 
/*  
int ListForEach(LineHead *linehead, Callbcak visit, void *ctx)  
{  
    int ret = HEAD;  
    ListNode *iter;  
 
    iter = linehead->head;  
    while ((NULL != iter) && ((linehead->NodeNum - 1) != ret))  
    {  
        ret = visit(ctx, iter->data);  
        iter = iter->next;  
    }  
 
    return ret;  
}  
*/ 
 
void ShowLine(LineHead *linehead)  
{  
    LineNode *p;  
    //改為斷言  
    //######################  
    if (NULL == linehead)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[LINEISNULL]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    p = linehead->head;  
    printf("\nLine:\n");  
    printf("##############################\n");  
    while (NULL != p)  
    {  
        printf("%d ", p->data);  
        p = p->next;  
    }  
    printf("\n##############################\n");  
} 

動態數組：

DArray.h

#ifdef _cplusplus  
extern "C" {  
#endif  
 
#define OK     0  
#define FAIL   1  
#define ERRNUM 6  
#define MEMORYEMPTY    0  
#define NODARRAY       1  
#define NODATATOSORT   2  
#define FUNCISNULL     3  
#define SORTFUNCISNULL 4  
 
struct _darray;  
typedef struct _darray DArray;  
typedef int (*DataCompareFunc)(int data1, int data2);  
typedef int (*SortFunc)(int *array, int size, DataCompareFunc cmp);  
 
DArray *DArray_Create();  
void DArray_Destory(DArray *darray);  
//插入在local前，當local大於數組size時插入在最後  
int DArray_Insert(DArray *darray, int data, int local);  
int DArray_Delete(DArray *darray, int local);  
int DArray_GetData(DArray *darray, int local);  
int DArray_SetData(DArray *darray, int data, int local);  
int DArray_Length(DArray *darray);  
//int DArray_Find(DArray *darray, CallBack compare, void *ctx);  
void DArray_Show(DArray *darray);  
/* 提供排序函數供調用者參考  
//通過回調函數實現升序或是降序排列，比較函數由調用者實現  
int Bubble_Sort(int *array, int size, DataCompareFunc cmp);  
int Quick_Sort(int *array, int size, DataCompareFunc cmp);  
int Merge_Sort(int *array, int size, DataCompareFunc cmp);  
*/ 
//提供動態數組排序接口函數，排序、比較函數都由調用者實現  
int DArray_Sort(DArray *darray, SortFunc sort, DataCompareFunc cmp);  
 
#ifdef _cplusplus  
}  
#endif 

DArray.c

#include <stdio.h>  
#include <stdlib.h>  
#include "Darray.h"  
 
#define MIN_PRE_ALLOCATE_NR 10  
 
struct _darray {  
    int *data;  
    int size;  
    int alloc_size;  
};  
 
char *errorstring[ERRNUM] = {"Memory can't be alloced!", "The darray has not created!",   
                             "There is no data to sort!", "The compare function is null!",  
                             "The sort function is null!"};  
 
static int DArray_Expend(DArray *darray, int need)  
{  
    int *data;  
    int alloc_size;  
 
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
    if ((darray->size + need) > darray->alloc_size)  
    {  
        //避免darray->alloc_size為0的情況在分配1.5倍的空間基礎上加上一個10  
        alloc_size = darray->alloc_size + (darray->alloc_size >> 1) + MIN_PRE_ALLOCATE_NR;  
        data = (int *)realloc(darray->data, sizeof(int) * darray->alloc_size);  
        if (NULL == data)  
        {  
            printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[MEMORYEMPTY]);  
            exit(0);  
        }  
        darray->data = data;  
        darray->alloc_size = alloc_size;  
    }  
 
    return ((darray->size + need) <= darray->alloc_size) ? OK : FAIL;  
}  
 
DArray *DArray_Create()  
{  
    DArray *darray;  
 
    darray = (DArray *)malloc(sizeof(DArray));  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[MEMORYEMPTY]);  
        exit(0);  
    }  
    darray->data = NULL;  
    darray->alloc_size = darray->size = 0;  
 
    return darray;  
}  
 
void DArray_Destory(DArray *darray)  
{  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
      
    if (NULL != darray->data)  
    {  
        free(darray->data);  
    }  
    free(darray);  
}  
 
//插入在local前，當local大於數組size時插入在最後  
int DArray_Insert(DArray *darray, int data, int local)  
{  
    int cursor;  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    cursor = (local < darray->size) ? local : darray->size;  
    if (OK == DArray_Expend(darray, 1))  
    {  
        for (i = darray->size; i > cursor; i--)  
        {  
            darray->data[i] = darray->data[i-1];  
        }  
        darray->data[cursor] = data;  
        darray->size++;  
    }  
 
    return OK;  
}  
 
//當數組的元素個數小於分配空間的一半時進行重新分配空間  
static int DArray_Shrink(DArray *darray)  
{  
    int *data;  
    int alloc_size;  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    //當數組已分配空間小於最小限額值時不做重新分配  
    if ((darray->size < (darray->alloc_size >> 1)) &&   
        (darray->alloc_size > MIN_PRE_ALLOCATE_NR))  
    {  
        alloc_size = darray->size + (darray->size >> 1);  
        data = (int *)realloc(darray->data, sizeof(int) * alloc_size);  
        if (NULL != data)  
        {  
            darray->data = data;  
            darray->alloc_size = alloc_size;  
        }  
    }  
      
    return OK;  
}  
 
int DArray_Delete(DArray *darray, int local)  
{  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    if (local >= darray->size)  
    {  
        printf("\nWrong location!\n");  
        return FAIL;  
    }  
    for (i = local; i < (darray->size - 1); i++)  
    {  
        darray->data[i] = darray->data[i+1];  
    }  
    darray->size--;  
    DArray_Shrink(darray);  
 
    return OK;  
}  
 
int DArray_GetData(DArray *darray, int local)  
{  
    int data;  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    if (local >= darray->size)  
    {  
        printf("\nWrong location!\n");  
        return FAIL;  
    }  
    data = darray->data[local];  
 
    return data;  
}  
 
int DArray_SetData(DArray *darray, int data, int local)  
{  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    if (local >= darray->size)  
    {  
        printf("\nWrong location!\n");  
        return FAIL;  
    }  
    darray->data[local] = data;  
 
    return OK;  
}  
 
int DArray_Length(DArray *darray)  
{  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    return darray->size;  
}  
 
//int DArray_Find(DArray *darray, CallBack compare, void *ctx);  
 
void DArray_Show(DArray *darray)  
{  
    int i;  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    printf("\nDArray:\n");  
    printf("##############################\n");  
    for (i = 0; i < darray->size; i++)  
    {  
        printf("%d ", darray->data[i]);  
    }  
    printf("\n##############################\n");  
}  
 
//下面兩個排序函數只是給調用者參考  
/* 升序排列  
static int int_cmp(int a, int b)  
{  
    return a - b;  
}  
*/ 
 
/* 降序排列  
static int int_cmp_invert(int a, int b)  
{  
    return b - a;  
}  
*/ 
 
//冒泡排序，最簡單實用的  
//通過回調函數實現升序或是降序排列，比較函數由調用者實現  
int Bubble_Sort(int *array, int size, DataCompareFunc cmp)  
{  
    int i, j, k;  
    int data;  
 
    if (NULL == array)  
    {  
        printf("\nERROR : %s\n", errorstring[NODATATOSORT]);  
        return FAIL;  
    }  
 
    if (size < 2)  
    {  
        return OK;  
    }  
    for (k = size - 1; k > 0; k--)  
    {  
        for (i = 1, j = 0; i < k; i++)  
        {  
            if (cmp(array[i], array[j]) > 0)  
            {  
                j = i;  
            }  
        }  
        if (cmp(array[j], array[k]) > 0)  
        {  
            data = array[k];  
            array[k] = array[j];  
            array[j] = data;  
        }  
    }  
 
    return OK;  
}  
 
//快排，當所有數據都可以放在內存中最快速實用的  
static void quick_sort_impl(int *array, int left, int right, DataCompareFunc cmp)  
{  
    int save_left = left;  
    int save_right = right;  
    int x = array[left];  
 
    //將小於x的值放在左邊，大於x的值放右邊  
    while (left < right)  
    {  
        while ((cmp(array[right], x) >= 0) && (left < right))  
        {  
            right--;  
        }  
        if (left != right)  
        {  
            array[left] = array[right];  
            left++;  
        }  
 
        while ((cmp(array[left], x) <= 0) && (left < right))  
        {  
            left++;  
        }  
        if (left != right)  
        {  
            array[right] = array[left];  
            right--;  
        }  
    }  
    array[left] = x;  
    //對左半部分排序  
    if (save_left < left)  
    {  
        quick_sort_impl(array, save_left, left-1, cmp);  
    }  
    //對右半部分排序  
    if (save_right > left)  
    {  
        quick_sort_impl(array, left+1, save_right, cmp);  
    }  
 
    //return;  
}  
 
int Quick_Sort(int *array, int size, DataCompareFunc cmp)  
{  
    if (NULL == array)  
    {  
        printf("\nERROR : %s\n", errorstring[NODATATOSORT]);  
        return FAIL;  
    }  
    if (NULL == cmp)  
    {  
        printf("\nERROR : %s\n", errorstring[FUNCISNULL]);  
        return FAIL;  
    }  
 
    if (size > 1)  
    {  
        quick_sort_impl(array, 0, size-1, cmp);  
    }  
 
    return OK;  
}  
 
//二路歸並排序，當數據無法一次性放在內存中時最好的  
static void merge_sort_impl(int *storage, int *array,   
                           int low, int mid, int high,   
                           DataCompareFunc cmp)  
{  
    int x;  
    int i = low;  
    int j = mid;  
    int k = high;  
 
    //對左半部分排序  
    if ((low + 1) < mid)  
    {  
        x = low + ((mid - low) >> 1);  
        merge_sort_impl(storage, array, low, x, mid, cmp);  
    }  
    //對右半部分排序  
    if ((mid + 1) < high)  
    {  
        x = mid + ((high - mid) >> 1);  
        merge_sort_impl(storage, array, mid, x, high, cmp);  
    }  
 
    //合並兩個有序數組  
    while ((j < mid) && (k < high))  
    {  
        if (cmp(array[j], array[k]) <= 0)  
        {  
            storage[i++] = array[j++];  
        }  
        else 
        {  
            storage[i++] = array[k++];  
        }  
    }  
    while (j < mid)  
    {  
        storage[i++] = array[j++];  
    }  
    while (k < high)  
    {  
        storage[i++] = array[k++];  
    }  
    for (i = low; i < high; i++)  
    {  
        array[i] = storage[i];  
    }  
}  
 
int Merge_Sort(int *array, int size, DataCompareFunc cmp)  
{  
    int *storage = NULL;  
 
    if (NULL == array)  
    {  
        printf("\nERROR : %s\n", errorstring[NODATATOSORT]);  
        return FAIL;  
    }  
    if (NULL == cmp)  
    {  
        printf("\nERROR : %s\n", errorstring[FUNCISNULL]);  
        return FAIL;  
    }  
 
    if (size > 1)  
    {  
        storage = (int *)malloc(sizeof(int) * size);  
        if (NULL != storage)  
        {  
            merge_sort_impl(storage, array, 0, size>>1, size, cmp);  
            free(storage);  
        }  
    }  
 
    return OK;  
}  
 
//排序接口  
int DArray_Sort(DArray *darray, SortFunc sort, DataCompareFunc cmp)  
{  
    //改為斷言  
    //######################  
    if (NULL == darray)  
    {  
        printf("\n%s %d\nERROR : %s\n", __FILE__, __LINE__, errorstring[NODARRAY]);  
        //return NULL;  
        exit(0);  
    }  
    //######################  
 
    if (NULL == sort)  
    {  
        printf("\nERROR : %s\n", errorstring[SORTFUNCISNULL]);  
        return FAIL;      
    }  
    if (NULL == cmp)  
    {  
        printf("\nERROR : %s\n", errorstring[FUNCISNULL]);  
        return FAIL;  
    }  
 
    sort(darray->data, darray->size, cmp);  
 
    return OK;  
} 

寫的倉促，沒有仔細推敲，經不起考驗～～呵呵！就當是有個念想吧～～大家湊合著看吧！

本文出自 “菜鳥浮出水” 博客，請務必保留此出處http://rangercyh.blog.51cto.com/1444712/490297