数据结构---线性表的链式表示和实现（二）

数据结构---线性表的链式表示和实现（二）
16年2月27日22:02:02
这一篇是双向链表的一些操作函数，与单向链表相比，并没有太大的区别。
/**
 * This code is for duplex linked_list.
 */

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct DulNode{
    int data;
    struct DulNode *pNext, *pPrior;
}DULNODE, *PDULNODE;

/**
 * Initialise the linked_list.
 * @param  pHead [the linked_list head]
 * @return [return the address of the pHead]
 */
PDULNODE InitDulLink (PDULNODE pHead)
{
    pHead = (PDULNODE)malloc(sizeof(DULNODE));
    if (!pHead)
    {
        printf("Cannot malloc memory for pHead.\n");
        exit(-1);
    }

    pHead->pNext = pHead->pPrior = pHead;

    return pHead;
}

/**
 * Traverse the linked_list.
 * @param pHead [the head of this linked_list]
 */
void TraverseDulLink(PDULNODE pHead)
{
    PDULNODE pTmp = pHead->pNext;
    while (pTmp != pHead)
    {
        printf("%d ", pTmp->data);
        pTmp = pTmp->pNext;
    }
    printf("\n");
}

/**
 * Backward traverse this linked_list.
 * @param pHead [the head of this linked_list]
 */
void TraverseDulLinkBack(PDULNODE pHead)
{
    PDULNODE pTmp = pHead->pPrior;
    while (pTmp != pHead)
    {
        printf("%d ", pTmp->data);
        pTmp = pTmp->pPrior;
    }
    printf("\n");
}

/**
 * Judge the linked_list is empty or not.
 * @param  pHead [the head of this linked_list]
 * @return [if the linked_list is empty, return 1,else, return 0]
 */
int IsLinkEmpty(PDULNODE pHead)
{
    return (pHead->pNext == pHead && pHead->pPrior == pHead) ? 1 : 0;
}

/**
 * The length of the linked_list.
 * @param  pHead [the head of this linked_list]
 * @return [the length]
 */
int LinkLength(PDULNODE pHead)
{
    int i = 0;
    PDULNODE pTmp = pHead->pNext;

    while (pTmp != pHead)
    {
        i++;
        pTmp = pTmp->pNext;
    }

    return i;
}

/**
 * Get elem from the linked_list.
 * @param  pHead [the head of this linked_list]
 * @param  pos [position]
 * @return [the PDULNODE]
 */
PDULNODE GetElem(PDULNODE pHead, int pos)
{
    int i;
    PDULNODE pTmp = pHead;

    if (pos < 0 || pos > LinkLength(pHead))
    {
        printf("Error position for GetElem.\n");
        exit(-1);
    }

    for (i = 1; i <= pos; i++)
        pTmp = pTmp->pNext;

    return pTmp;
}

/**
 * Insert elem into the linked_list.
 * @param  pHead [the head of this linked_list]
 * @param  pos [position]
 * @param  val [the value of the insert elem]
 * @return [if success, return 1]
 */
int InsertDulLink(PDULNODE pHead, int pos, int val)
{
    PDULNODE pNew, pTmp;

    if (pos < 1 || pos > LinkLength(pHead) + 1)
    {
        printf("Error position for InsertDulLink!\n");
        exit(-1);
    }

    pTmp = GetElem(pHead, pos -1);
    if (!pTmp)
    {
        printf("InsertDulLink Error.\n");
        exit(-1);
    }

    pNew = (PDULNODE)malloc(sizeof(DULNODE));
    if (!pNew)
    {
        printf("Cannot malloc memory for pNew.\n");
        exit(-1);
    }

    pNew->data = val;
    pNew->pNext = pTmp->pNext;
    pNew->pPrior = pTmp;

    pTmp->pNext->pPrior = pNew;
    pTmp->pNext = pNew;

    return 1;
}

int DeleteDulLink(PDULNODE pHead, int pos, int *val)
{
    PDULNODE pTmp;
    int i = LinkLength(pHead);
    printf("The link length is %d.\n", i);

    if (pos < 1 || pos > LinkLength(pHead) + 1)
    {
        printf("Error position for DeleteDulLink.\n");
        exit(-1);
    }

    pTmp = GetElem(pHead, pos);
    if (!pTmp)
    {
        printf("Cannot Get elem for DeleteDulLink.\n");
        exit(-1);
    }

    *val = pTmp->data;
    pTmp->pPrior->pNext = pTmp->pNext;
    pTmp->pNext->pPrior = pTmp->pPrior;
    free(pTmp);

    return 1;
}

int main(int argc, char const *argv[])
{
    PDULNODE pHead;
    int val;

    pHead = InitDulLink(pHead);
    if (IsLinkEmpty(pHead))
    {
        printf("The link is empty.\n");
    }
    InsertDulLink(pHead, 1, 1);
    InsertDulLink(pHead, 1, 2);
    InsertDulLink(pHead, 1, 3);
    InsertDulLink(pHead, 1, 4);
    InsertDulLink(pHead, 1, 5);
    if (IsLinkEmpty(pHead))
    {
        printf("The link is empty.\n");
    }
    TraverseDulLink(pHead);
    //TraverseDulLinkBack(pHead);
    if (DeleteDulLink(pHead, 2, &val))
    {
        printf("The DeleteDulLink value is :%d. \n", val);
    }
    TraverseDulLink(pHead);

    return 0;
}

程序的运行结果如下所示：
The link is empty.
5 4 3 2 1
The link length is 5.
The DeleteDulLink value is :4.
5 3 2 1