歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C語言單向鏈表的實現

采用VS2013編輯器編寫的C語言單向鏈表代碼:

#include <stdio.h>
#include <windows.h>

typedef  int TypeData;
#define  NODE_LENGTH sizeof(NODE)

/**定義鏈表的結構體*/
typedef struct tagNode
{
    TypeData tdData;
    struct tagNode *plNext;
}NODE;

/*******函數聲明****************************/
NODE* createList(TypeData tdInData);
int forEachList(NODE* pstInHead);
int insertListTail(NODE* pstInHead, TypeData tdInData);
int insertListHead(NODE* pstInHead, TypeData tdInData);
int getListLength(NODE* pstInHead);
int delListHead(NODE* pstInHead);
int delListTail(NODE* pstInHead);
int sortList(NODE* pstInHead, int nInFlag);
int clearList(NODE* pstInHead);

/*****************************************
函數功能:創建一個新的鏈表,帶頭節點
函數入參:tdInData 頭結點的值
 返回值: 非NULL 成功
        NULL 失敗
******************************************/
NODE* createList(TypeData tdInData)
{
    NODE* pstNewNode = (NODE*)malloc(NODE_LENGTH);
    if (NULL == pstNewNode)
    {
        printf("createList: malloc failed");
        return NULL;
    }
    pstNewNode->plNext = NULL;
    pstNewNode->tdData = tdInData;
    return pstNewNode;
}

/*****************************************
函數功能:遍歷整個鏈表,把鏈表的值都顯示出來,
函數入參:pstInHead 鏈表的頭結點
  返回值:0 成功
        1 失敗
******************************************/
int forEachList(NODE* pstInHead)
{
    if (NULL == pstInHead)
    {
        printf("forEachList: the parameter pstInHead is NULL");
        return 1;
    }
    while (NULL != pstInHead->plNext)
    {
        printf("%d-->", pstInHead->tdData);
        pstInHead = pstInHead->plNext;
    }
    printf("%d\n", pstInHead->tdData);
    return 0;
}
/*****************************************
函數功能:在鏈表的尾部插入數據
函數入參:pstInHead 鏈表的頭結點
        tdInData 在尾部插入數據的值
  返回值: 0 成功
        1 失敗
******************************************/
int insertListTail(NODE* pstInHead, TypeData tdInData)
{
    if (NULL == pstInHead)
    {
        printf("insertListTail: the parameter pstInHead is NULL");
        return 1;
    }
    while (NULL != pstInHead->plNext)
    {
        pstInHead = pstInHead->plNext;
    }
    NODE* pstNewNode = (NODE*)malloc(NODE_LENGTH);
    if (NULL == pstNewNode)
    {
        printf("insertListTail: malloc pstNewNode failed");
        return 1;
    }
    pstNewNode->plNext = NULL;
    pstNewNode->tdData = tdInData;
    pstInHead->plNext = pstNewNode;
    return 0;
}
/*****************************************
函數功能:在鏈表的首部插入數據,就是在頭結點的後面插入數據
函數入參:pstInHead 鏈表的頭結點
        tdInData 在尾部插入數據的值
返回值: 0 成功
      1 失敗
******************************************/
int insertListHead(NODE* pstInHead, TypeData tdInData)
{
    if (NULL == pstInHead)
    {
        printf("insertListHead: the parameter pstInHead is NULL");
        return 1;
    }
    NODE* pstNewNode = (NODE*)malloc(NODE_LENGTH);
    if (NULL == pstNewNode)
    {
        printf("insertListTail: malloc pstNewNode failed");
        return 1;
    }
    pstNewNode->tdData = tdInData;

    /**將該節點插入頭部*/
    pstNewNode->plNext = pstInHead->plNext;
    pstInHead->plNext = pstNewNode;
    return 0;
}
/*****************************************
函數功能:刪除頭結點
函數入參:pstInHead 鏈表的頭結點
返回值: 0 成功
      1 失敗
******************************************/
int delListHead(NODE* pstInHead)
{
    if (NULL == pstInHead)
    {
        printf("delListHead: the parameter pstInHead is NULL");
        return 1;
    }
    int nListLen = getListLength(pstInHead);
    NODE* pstTempNode = NULL;

    /**鏈表的長度至少為2的時候,才能刪除頭部*/
    if (nListLen >= 2)
    {
        pstTempNode = pstInHead->plNext;
        pstInHead->plNext = pstInHead->plNext->plNext;
        free(pstTempNode);
    }
    return 0;
}
/*****************************************
函數功能:獲得鏈表的長度,包括頭結點
函數入參:pstInHead 鏈表的頭結點
返回值: 0 成功
      1 失敗
******************************************/
int getListLength(NODE* pstInHead)
{
    int nLen = 0;
    if (NULL == pstInHead)
    {
        printf("getListLength: the parameter pstInHead is NULL");
        return 1;
    }
    while (NULL != pstInHead)
    {
        nLen++;
        pstInHead = pstInHead->plNext;
    }
    return nLen;
}
/*****************************************
函數功能:刪除鏈表的尾節點
函數入參:pstInHead 鏈表的頭結點
返回值: 0 成功
      1 失敗
******************************************/
int delListTail(NODE* pstInHead)
{
    if (NULL == pstInHead)
    {
        printf("delListTail: the parameter pstInHead is NULL");
        return 1;
    }
    int nListLen = getListLength(pstInHead);
    /**如果只有頭結點直接返回*/
    if (1 == nListLen)
    {
        return 0;
    }
    while (NULL != pstInHead->plNext->plNext)
    {
        pstInHead = pstInHead->plNext;
    }
    NODE* pstTempNode = pstInHead->plNext;
    pstInHead->plNext = NULL;
    free(pstTempNode);
    return 0;
}
/*****************************************
函數功能:對整個鏈表進行排序,頭結點不參與排序
函數入參:pstInHead 鏈表的頭結點
        nInFlag 0 降序,1升序
返回值: 0 成功
      1 失敗
******************************************/
int sortList(NODE* pstInHead, int nInFlag)
{
    if (NULL == pstInHead)
    {
        printf("sortList: the parameter pstInHead is NULL");
        return 1;
    }
    int nListLen = getListLength(pstInHead);
    /**如果只有頭結點,不用比較,直接返回*/
    if (1 == nListLen)
    {
        return 0;
    }
    NODE* pstTempNode = NULL;
    pstInHead = pstInHead->plNext;
    TypeData tdTempData = 0;
    /**如果是正序排列*/
    if (0 == nInFlag)
    {
        while (NULL != pstInHead->plNext)
        {
            pstTempNode = pstInHead->plNext;
            while (NULL != pstTempNode)
            {
                if (pstInHead->tdData > pstTempNode->tdData)
                {
                    tdTempData = pstInHead->tdData;
                    pstInHead->tdData = pstTempNode->tdData;
                    pstTempNode->tdData = tdTempData;
                }
                pstTempNode = pstTempNode->plNext;
            }
            pstInHead = pstInHead->plNext;
        }
    }
    /**如果是反序排列*/
    else if (1 == nInFlag)
    {
        while (NULL != pstInHead->plNext)
        {
            pstTempNode = pstInHead->plNext;
            while (NULL != pstTempNode)
            {
                if (pstInHead->tdData < pstTempNode->tdData)
                {
                    tdTempData = pstInHead->tdData;
                    pstInHead->tdData = pstTempNode->tdData;
                    pstTempNode->tdData = tdTempData;
                }
                pstTempNode = pstTempNode->plNext;
            }
            pstInHead = pstInHead->plNext;
        }
    }
    else
    {
        printf("You choice is wrong.Please input (0 | 1)\n");
    }

    return 0;
}
/*****************************************
函數功能:清空整個鏈表
函數入參:pstInHead 鏈表的頭結點
返回值: 0 成功
      1 失敗
******************************************/
int clearList(NODE* pstInHead)
{
    if (NULL == pstInHead)
    {
        printf("clearList: the parameter pstInHead is NULL");
        return 1;
    }
    int nListLen = getListLength(pstInHead);
    /**暫存鏈表的頭結點*/
    NODE* pstTempHead = pstInHead;

    /**如果只有頭結點直接返回*/
    if (1 == nListLen)
    {
        return 0;
    }
    NODE* pstTempNode = NULL;
    pstInHead = pstInHead->plNext;
    while (NULL != pstInHead)
    {
        pstTempNode = pstInHead;
        pstInHead = pstInHead->plNext;
        free(pstTempNode);
    }
    pstTempHead->plNext = NULL;
    return 0;
}
int main()
{
    NODE* pstListHead = createList(-1);

    /**測試插入頭部、尾部函數*/
    insertListTail(pstListHead, 11);
    insertListTail(pstListHead, 12);
    insertListTail(pstListHead, 13);
    insertListTail(pstListHead, 5);
    insertListHead(pstListHead, 22);
    /**遍歷整個鏈表*/
    forEachList(pstListHead);

    /**測試刪除頭部節點*/
    delListHead(pstListHead);
    forEachList(pstListHead);

    /**測試刪除尾部節點*/
    delListTail(pstListHead);
    forEachList(pstListHead);

    /**測試清空鏈表*/
    clearList(pstListHead);
    forEachList(pstListHead);

    /**測試插入頭部、尾部函數*/
    insertListTail(pstListHead, 101);
    insertListTail(pstListHead, 2);
    insertListTail(pstListHead, 76);
    insertListTail(pstListHead, 43);
    insertListHead(pstListHead, 22);
    insertListHead(pstListHead, 333);
    forEachList(pstListHead);

    /*測試正排序函數**/
    sortList(pstListHead, 0);
    forEachList(pstListHead);

    /*測試反排序函數**/
    sortList(pstListHead, 3);
    forEachList(pstListHead);

    system("PAUSE");
    return 0;

}

 

Copyright © Linux教程網 All Rights Reserved