鏈表學習--雙向鏈表實現

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

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

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

//定義鏈表的結構體。
struct MyList
{
    int nData;
    MyList* pPre;
    MyList* pNext;
};

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

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

//清空鏈表
int Clear()
{
    //刪除所有數據，并把頭指針指向為空
    MyList* pTemp = g_pHead;

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

    return 1;
}

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

    return 1;
}

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

        pTemp = pTemp->pNext;        //沒有找到，進入下一個節點
    }

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

//刪除數據。
bool Delete(int nData)
{
    //先找到數據，然后再刪除。
    MyList* pTemp = g_pHead;    //要刪除的節點指針。    

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

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

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

    return false;    //沒有找到數據，刪除失敗，返回false
}

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

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

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

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

    system("pause");
    return 0;
}

posted on 2009-04-30 20:25 shongbee2 閱讀(6114) 評論(2)  編輯 收藏 引用 所屬分類: 數據結構和算法