鏈表的基本操作

// struct.cpp : 定義控制臺應用程序的入口點。
//

#include "stdafx.h"

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define RETURN_OK 0
#define RETURN_ERROR 1
#define MAX_LEN 11
#define MY_RAND_MAX 26

typedef struct tag_Info_S
{
    int a;
    int b;
    int c;
    char name[MAX_LEN];
}Info_S;

typedef struct tag_MyList_S
{
    Info_S stInfo;

    struct tag_MyList_S *next;
}MyList_S;

MyList_S *g_pHead;

int AllocOneNode(MyList_S **ppNewNode);
void InitOneNode(MyList_S *pNode);
int InitList(MyList_S **ppHead);
int DelList(MyList_S **ppHead);

int AllocOneNode(MyList_S **ppNewNode)
{
    MyList_S *pTemp = (MyList_S *)malloc(sizeof(MyList_S));
    if (NULL == pTemp)
    {
        *ppNewNode = NULL;
        return RETURN_ERROR;
    }

    *ppNewNode = pTemp;
    return RETURN_OK;
}

void InitOneNode(MyList_S *pNode)
{
    int i = 0;
    int len = 0;
    pNode->stInfo.a = rand() % MY_RAND_MAX; //rand的使用不規范
    pNode->stInfo.b = rand() % MY_RAND_MAX;
    pNode->stInfo.c = rand() % MY_RAND_MAX;
    len = (rand() % (MAX_LEN - 2)) + 1; //1---10

    for (i = 0; i < len; i++)
    {
        pNode->stInfo.name[i] = rand() % MY_RAND_MAX + 'A';
    }
    pNode->stInfo.name[len] = '\0';
    pNode->next = NULL;

    return;
}

int InitList(MyList_S **ppHead)
{
    int ret = RETURN_ERROR;

    MyList_S *pNew = NULL;
    if (NULL != *ppHead)  //需要先銷毀
    {
        DelList(ppHead);
    }

    ret = AllocOneNode(&pNew);
    if (RETURN_OK != ret)
    {
        return RETURN_ERROR;
    }

    memset(pNew, 0, sizeof(MyList_S));
    pNew->next = NULL;

    *ppHead = pNew;
    return RETURN_OK;
}

int DelList(MyList_S **ppHead)
{
    MyList_S *pFreeNode = NULL;
    MyList_S *pTmpNode = NULL;

    if (NULL == *ppHead)
    {
        return RETURN_ERROR;
    }

    pTmpNode = *ppHead;
    while (pTmpNode)
    {
        pFreeNode = pTmpNode;
        pTmpNode = pTmpNode->next;

        free(pFreeNode);
    }

    *ppHead = NULL;
    return RETURN_OK;
}

int GetListLen(MyList_S *pHead, int *ListLen)
{
    int len = 0;
    if (NULL == pHead)
    {
        return RETURN_ERROR;
    }

    pHead = pHead->next;
    while (pHead)
    {
        len++;
        pHead = pHead->next;
    }

    *ListLen = len;
    return RETURN_OK;
}

int AddNodeAtListTrail(MyList_S **ppHead, MyList_S *pNewNode)
{
    MyList_S *pTemp = NULL;

    if (NULL == *ppHead)
    {
        return RETURN_ERROR;
    }

    //當前鏈表為空時，頭節點的后面插入
    if (NULL == (*ppHead)->next)
    {
        (*ppHead)->next = pNewNode;
        return RETURN_OK;
    }

    pTemp = (*ppHead)->next;
    while (pTemp->next)
    {
        pTemp = pTemp->next;
    }
    pTemp->next = pNewNode;
    pNewNode->next = NULL;

    return RETURN_OK;
}

int AddNodeAtListHead(MyList_S **ppHead, MyList_S *pNewNode)
{
    if (NULL == *ppHead)
    {
        return RETURN_ERROR;
    }

    pNewNode->next = (*ppHead)->next;
    (*ppHead)->next = pNewNode;

    return RETURN_OK;
}

//鏈表從0開始編號，pNewNode插入后在第iLocal位置
int AddNodeAtListLocal(MyList_S **ppHead, MyList_S *pNewNode, int iLocal)
{
    int len = 0;
    int i = 0;
    MyList_S *pTemp = NULL;

    if (NULL == *ppHead)
    {
        return RETURN_ERROR;
    }

    if (iLocal == 0)
    {
        AddNodeAtListHead(ppHead, pNewNode);
        return RETURN_OK;

    }

    GetListLen(*ppHead, &len);
    if (iLocal > len) //由于從0開始編號，所以iLocal最大為len
    {
        return RETURN_ERROR;
    }

    //查找第編號為ilocal - 1的有效節點的位置
    pTemp = (*ppHead);
    while (i < iLocal)
    {
        pTemp = pTemp->next;
        i++;
    }

    pNewNode->next = pTemp->next;
    pTemp->next = pNewNode;

    return RETURN_OK;
}

int DelOneNodeAtListTrail(MyList_S **ppHead, MyList_S *pDelNode)
{
    MyList_S *pPre = NULL;
    MyList_S *pCur = NULL;

    if (NULL == *ppHead || NULL == (*ppHead)->next)
    {
        return RETURN_ERROR;
    }

    pCur = (*ppHead)->next;
    if (NULL == pCur->next) //如果只有一個節點,可以使用DelOneNodeAtListHead刪除
    {
        memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pCur->stInfo), sizeof(Info_S));

        (*ppHead)->next = NULL;
        free(pCur);
        pCur = NULL;
    }

    while (pCur->next) //pCur->next = NULL，pCur為最后一個有效節點
    {
        pPre = pCur;
        pCur = pCur->next;
    }

    pPre->next = NULL;
    memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pCur->stInfo), sizeof(Info_S));
    free(pCur);
    pCur = NULL;

    return RETURN_OK;
}

int DelOneNodeAtListHead(MyList_S **ppHead, MyList_S *pDelNode)
{
    MyList_S *pCur = NULL;

    if (NULL == *ppHead || NULL == (*ppHead)->next)
    {
        return RETURN_ERROR;
    }

    pCur = (*ppHead)->next;
    (*ppHead)->next = pCur->next;
    memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pCur->stInfo), sizeof(Info_S));
    free(pCur);

    return RETURN_OK;
}

int DelNodeAtListLocal(MyList_S **ppHead, MyList_S *pDelNode, int iLocal)
{
    int i = 0;
    int len = 0;
    MyList_S *pTemp = NULL;
    MyList_S *pFreeNode = NULL;

    if (NULL == *ppHead || NULL == (*ppHead)->next)
    {
        return RETURN_ERROR;
    }

    if (iLocal == 0)
    {
        DelOneNodeAtListHead(ppHead, pDelNode);
        return RETURN_OK;
    }

    (void)GetListLen(*ppHead, &len); //不用判斷返回值了，此處是內部調用，前面的判斷可以保證此處可以獲取到長度
    if (iLocal >= len)
    {
        return RETURN_ERROR;  //最大到len - 1
    }
    pTemp = *ppHead;
    while (i < iLocal)
    {
        pTemp = pTemp->next;
        i++;
    }

    pFreeNode = pTemp->next;
    memcpy_s(&(pDelNode->stInfo), sizeof(Info_S), &(pFreeNode->stInfo), sizeof(Info_S));
    pTemp->next = pFreeNode->next;
    free(pFreeNode);
    pFreeNode = NULL;

    return RETURN_OK;
}

int RevertList(MyList_S *pHead) //頭指針的指向不發生變化，變化的是pHead->next
{
    MyList_S *pPre = NULL;
    MyList_S *pCur = NULL;

    if (NULL == pHead || NULL == pHead->next)
    {
        return RETURN_ERROR;
    }

    pPre = pHead->next;
    pHead->next = NULL;

    while (pPre)
    {
        pCur = pPre->next;
        pPre->next = NULL;
        AddNodeAtListHead(&pHead, pPre);
        pPre = pCur;
    }

    return RETURN_OK;
}

/*
排序，先按a排序，a相同按照b排序，b相同按照c排序，c相同按照name排序
*/
int SrcCopyInfoToDst(void *dst, void *src)
{
    if (NULL == dst || NULL == src)
    {
        return RETURN_ERROR;
    }

    memcpy_s(dst, sizeof(Info_S), src, sizeof(Info_S));
    return RETURN_OK;
}

int sort(MyList_S *pHead)
{
    MyList_S *pCur = NULL;
    MyList_S *pNext = NULL;
    Info_S stInfo = { 0 };

    if (NULL == pHead || NULL == pHead->next)
    {
        return RETURN_ERROR;
    }

    pCur = pHead->next;
    if (NULL == pCur)
    {
        return RETURN_OK;
    }

    //排序，比較搓考慮優化
    while (pCur)
    {
        pNext = pCur;
        while (pNext)
        {
            if (pNext->stInfo.a > pCur->stInfo.a)
            {
                SrcCopyInfoToDst(&stInfo, &(pCur->stInfo));
                SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo));
                SrcCopyInfoToDst(&(pNext->stInfo), &stInfo);
            }
            else if (pNext->stInfo.a == pCur->stInfo.a)
            {
                if (pNext->stInfo.b > pCur->stInfo.b)
                {
                    SrcCopyInfoToDst(&stInfo, &(pCur->stInfo));
                    SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo));
                    SrcCopyInfoToDst(&(pNext->stInfo), &stInfo);
                }
                else if (pNext->stInfo.b == pCur->stInfo.b)
                {
                    if (pNext->stInfo.c > pCur->stInfo.c)
                    {
                        SrcCopyInfoToDst(&stInfo, &(pCur->stInfo));
                        SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo));
                        SrcCopyInfoToDst(&(pNext->stInfo), &stInfo);
                    }
                    else if (pNext->stInfo.c == pCur->stInfo.c)
                    {
                        if (strcmp(pCur->stInfo.name, pNext->stInfo.name) > 0)
                        {
                            SrcCopyInfoToDst(&stInfo, &(pCur->stInfo));
                            SrcCopyInfoToDst(&(pCur->stInfo), &(pNext->stInfo));
                            SrcCopyInfoToDst(&(pNext->stInfo), &stInfo);
                        }
                    }
                }
            }
            pNext = pNext->next;
        }
        pCur = pCur->next;
    }

    return RETURN_OK;
}

void printList(MyList_S *pHead)
{
    if (NULL == pHead)
    {
        return;
    }

    pHead = pHead->next;
    while (pHead)
    {
        printf("a = %d, b = %d, c = %d, name = %s\n", pHead->stInfo.a, pHead->stInfo.b, pHead->stInfo.c, pHead->stInfo.name);
        pHead = pHead->next;
    }

    printf("-----------------------------------------------------------------------------------\n");
    return;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int i = 0;
    int len = 0;
    int ret = RETURN_ERROR;
    MyList_S *pTemp = NULL;

    InitList(&g_pHead);
    for (i = 0; i < 10; i++)
    {
        ret = AllocOneNode(&pTemp);
        if (RETURN_OK != ret)
        {
            printf("alloc node failed!\n");
            return RETURN_ERROR;
        }
        InitOneNode(pTemp);

        if (i % 2)
        {
            AddNodeAtListTrail(&g_pHead, pTemp);
        }
        else
        {
            AddNodeAtListHead(&g_pHead, pTemp);
        }
    }
    GetListLen(g_pHead, &len);
    printf("len = %d\n", len);
    printList(g_pHead);

    ret = AllocOneNode(&pTemp);
    if (RETURN_OK != ret)
    {
        printf("alloc node failed!\n");
        return RETURN_ERROR;
    }
    InitOneNode(pTemp);

    AddNodeAtListLocal(&g_pHead, pTemp, 10);
    GetListLen(g_pHead, &len);
    printf("len = %d\n", len);
    printList(g_pHead);

    DelNodeAtListLocal(&g_pHead, pTemp, 10);
    GetListLen(g_pHead, &len);
    printf("len = %d\n", len);
    printList(g_pHead);

    RevertList(g_pHead);
    printList(g_pHead);

    sort(g_pHead);
    printList(g_pHead);

    return 0;
}