鏈表學(xué)習(xí)--雙向鏈表實(shí)現(xiàn)

今天學(xué)習(xí)了鏈表的數(shù)據(jù)結(jié)構(gòu)。他的主要思路為:
1. 他訪問數(shù)據(jù)的方式不是數(shù)組的下標(biāo)，而是他的節(jié)點(diǎn)的指針來訪問。所以他可以更靈活的處理數(shù)據(jù)見得相關(guān)信息。不過他的速度肯定沒有數(shù)組下標(biāo)快的，空間也沒有數(shù)組利用率高，可他的靈活性給了我們很大的方便。我們用鏈表的時(shí)候還是很多的。
2. 鏈表是用指針的指向來訪問管理數(shù)據(jù)的，一個(gè)我們把數(shù)據(jù)存在一個(gè)節(jié)點(diǎn)里，一個(gè)節(jié)點(diǎn)包括：nData，節(jié)點(diǎn)的數(shù)據(jù)域，nNext，他指向的下一個(gè)指針，nPre他的上一個(gè)指針。如果他沒有下一個(gè)指針或上一個(gè)指針，我們指向空nil.
3. 一般一個(gè)鏈表有一個(gè)頭節(jié)點(diǎn)。以他開始訪問整個(gè)鏈表區(qū)域的數(shù)據(jù)。這樣我們就能更好的控制鏈表了，就像數(shù)組下標(biāo)為0的元素一樣。A[0]的地位。
截取書上的圖：

這就是一個(gè)鏈表的樣子了。呵呵 是不是很直觀呢？
鏈表主要的操作包括：
插入，刪除，查找，清空，等主要操作。
很重要的數(shù)據(jù)結(jié)構(gòu)，奉上源代碼：

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

//定義鏈表的結(jié)構(gòu)體。
struct MyList
{
    int nData;
    MyList* pPre;
    MyList* pNext;
};

//全局的變量，保存鏈表的頭
MyList* g_pHead = NULL;

//判斷鏈表是否為空
bool IsEmpty()
{
    //如果頭指針指向的是空，鏈表為空
    return g_pHead == NULL;
}

//清空鏈表
int Clear()
{
    //刪除所有數(shù)據(jù)，并把頭指針指向?yàn)榭?/span>
    MyList* pTemp = g_pHead;

    //遍歷鏈表的數(shù)據(jù)。如果有數(shù)據(jù)，刪除，然后進(jìn)入下一個(gè)數(shù)據(jù)
    while(g_pHead)
    {
        g_pHead = g_pHead->pNext;
        delete pTemp;
        pTemp = g_pHead;
    }

    return 1;
}

//插入數(shù)據(jù)到鏈表中
int Insert(int nData)
{
    //這里是插入到頭的位置，類似棧的操作。
    MyList* pTemp = new MyList();    //申請(qǐng)一個(gè)新的空間存放數(shù)據(jù)。
    pTemp->nData = nData;
    pTemp->pPre = NULL;            //他的上一個(gè)沒有
    pTemp->pNext = g_pHead;        //他的next指向頭節(jié)點(diǎn)，他作為頭節(jié)點(diǎn)的上一個(gè)成為新頭節(jié)點(diǎn)
    if (g_pHead)
    {
        g_pHead->pPre = pTemp;    //如果頭節(jié)點(diǎn)有數(shù)據(jù)，則把頭節(jié)點(diǎn)的上一個(gè)指向該節(jié)點(diǎn)。
    }
    g_pHead = pTemp;            //是頭節(jié)點(diǎn)指針指向他，他成為新的頭節(jié)點(diǎn)

    return 1;
}

//查找數(shù)據(jù)
bool Find(int nData)
{
    MyList* pTemp = g_pHead;        //從頭節(jié)點(diǎn)開始尋找。
    //遍歷數(shù)據(jù)
    while(pTemp)
    {
        if (pTemp->nData == nData)    //如果找到該數(shù)據(jù)，
        {
            return true;            //返回真。
        }

        pTemp = pTemp->pNext;        //沒有找到，進(jìn)入下一個(gè)節(jié)點(diǎn)
    }

    return false;            //遍歷之后沒有找到，則沒有該數(shù)據(jù)，返回false
}

//刪除數(shù)據(jù)。
bool Delete(int nData)
{
    //先找到數(shù)據(jù)，然后再刪除。
    MyList* pTemp = g_pHead;    //要?jiǎng)h除的節(jié)點(diǎn)指針。    

    //遍歷鏈表找到要?jiǎng)h除的節(jié)點(diǎn)
    while (pTemp)        
    {
        if (pTemp->nData == nData)    //找到了，刪除它
        {
            if (pTemp->pPre)    //如果他有前一個(gè)節(jié)點(diǎn)，則前一個(gè)節(jié)點(diǎn)的next指向他的下一個(gè)節(jié)點(diǎn)
            {                    //這樣就不會(huì)吊鏈了。
                pTemp->pPre->pNext = pTemp->pNext;
            }
            else        //沒有上一個(gè)節(jié)點(diǎn)，則他就是頭節(jié)點(diǎn)。
            {
                g_pHead = pTemp->pNext;    //頭節(jié)點(diǎn)指針指向他，他就可以安息了。
            }

            if (pTemp->pNext)    //處理他的下一個(gè)節(jié)點(diǎn)情況，和上節(jié)點(diǎn)類似
            {
                pTemp->pNext->pPre = pTemp->pPre;
            }

            delete pTemp;    //刪除它的數(shù)據(jù)空間
            return true;    //返回true,刪除成功
        }
    }

    return false;    //沒有找到數(shù)據(jù)，刪除失敗，返回false
}

int main()
{
    //測試，
    for (int i = 0; i < 10; ++i)
    {
        Insert(i);    //插入數(shù)據(jù)
    }

    if (Find(5)) //查找數(shù)據(jù)
    {
        printf("Yes!\n");
    }
    if (!Find(11))
    {
        printf("No!\n");
    }

    while(!IsEmpty())    //逐一刪除數(shù)據(jù)
    {
        printf("%d ", g_pHead->nData);
        Delete(g_pHead->nData);
    }
    printf("\n");
    for (int i = 0; i < 10; ++i)
    {
        Insert(i);
    }

    Clear();        //清空數(shù)據(jù)。
    if (IsEmpty())
    {
        printf("Empty!\n");
    }

    system("pause");
    return 0;
}

posted on 2009-04-30 20:25 shongbee2 閱讀(6114) 評(píng)論(2)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)和算法