隨感而發(fā)

鏈表學習--雙向鏈表實現(xiàn)

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

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

#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()
{
    //刪除所有數(shù)據(jù)，并把頭指針指向為空
    MyList* pTemp = g_pHead;

    //遍歷鏈表的數(shù)據(jù)。如果有數(shù)據(jù)，刪除，然后進入下一個數(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();    //申請一個新的空間存放數(shù)據(jù)。
    pTemp->nData = nData;
    pTemp->pPre = NULL;            //他的上一個沒有
    pTemp->pNext = g_pHead;        //他的next指向頭節(jié)點，他作為頭節(jié)點的上一個成為新頭節(jié)點
    if (g_pHead)
    {
        g_pHead->pPre = pTemp;    //如果頭節(jié)點有數(shù)據(jù)，則把頭節(jié)點的上一個指向該節(jié)點。
    }
    g_pHead = pTemp;            //是頭節(jié)點指針指向他，他成為新的頭節(jié)點

    return 1;
}

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

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

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

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

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

            if (pTemp->pNext)    //處理他的下一個節(jié)點情況，和上節(jié)點類似
            {
                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 閱讀(6093) 評論(2)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結構和算法