鏈?zhǔn)酱鎯?chǔ)的定義

鏈?zhǔn)酱鎯?chǔ)為了表示數(shù)據(jù)元素與其直接后繼元素間的邏輯關(guān)系，數(shù)據(jù)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)直接后繼的信息。相連的數(shù)據(jù)元素之間在存儲(chǔ)空間中不要求連續(xù)。

鏈?zhǔn)酱鎯?chǔ)的邏輯結(jié)構(gòu)
基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，每個(gè)節(jié)點(diǎn)都包含數(shù)據(jù)域和指針域。數(shù)據(jù)域用于存儲(chǔ)數(shù)據(jù)元素本身，指針域用于存儲(chǔ)相鄰節(jié)點(diǎn)的地址。

image.png

一個(gè)完整的鏈表需要由以下幾部分構(gòu)成：

• 頭指針：
  一個(gè)普通的指針，它的特點(diǎn)是永遠(yuǎn)指向鏈表第一個(gè)節(jié)點(diǎn)的位置。很明顯，頭指針用于指明鏈表的位置，便于后期找到鏈表并使用表中的數(shù)據(jù)；
• 節(jié)點(diǎn)：
  鏈表中的節(jié)點(diǎn)又細(xì)分為頭節(jié)點(diǎn)、首元節(jié)點(diǎn)和其他節(jié)點(diǎn)：
  頭節(jié)點(diǎn)：
  其實(shí)就是一個(gè)不存任何數(shù)據(jù)的空節(jié)點(diǎn)，通常作為鏈表的第一個(gè)節(jié)點(diǎn)。對(duì)于鏈表來(lái)說(shuō)，頭節(jié)點(diǎn)不是必須的，它的作用只是為了方便解決某些實(shí)際問(wèn)題；

完整的鏈表示意圖

線性表的基本操作方式

        LinkList();                                             //構(gòu)造函數(shù)，初始化線性表
        virtual ~LinkList();                                    //析構(gòu)函數(shù)。銷毀線性表
        void ClearList();                                       //清空線性表
        bool listisEmpty();                                     //判斷線性表是否為空
        int ListLength();                                       //獲取線性表的長(zhǎng)度
        bool GetElem(int i,Node *pNode);                        //獲取指定元素
        int LocateElem(Node *pNode);                            //尋找第一個(gè)滿足的數(shù)據(jù)元素的位序
        bool PriorElem(Node *pcurrentNode,Node *pPreNode);      //獲取指定節(jié)點(diǎn)的前驅(qū)
        bool NextElem(Node *pcurrentNode,Node *pNextNode);      //后去指定節(jié)點(diǎn)的后驅(qū)
        bool ListInsert(int i,Node *pNode);                     //在指定位置插入節(jié)點(diǎn)
        bool ListDelete(int i,Node *pNode);                     //刪除指定位置的節(jié)點(diǎn)
        bool ListInsertHead(Node *pNode);                       //在頭節(jié)點(diǎn)插入新的節(jié)點(diǎn)
        bool ListInsrtTail(Node *pNode);                        //在尾節(jié)點(diǎn)插入新的節(jié)點(diǎn)
        void ListTraverse();

在頭節(jié)點(diǎn)插入新的節(jié)點(diǎn)操作

在鏈表頭節(jié)點(diǎn)插入新節(jié)點(diǎn)存在兩種情況
1、鏈表本身是空表

• 即鏈表的新節(jié)點(diǎn)的next指針會(huì)指向null，然后操作LinkedList對(duì)象的頭指針指向新的節(jié)點(diǎn)，完成鏈表頭節(jié)點(diǎn)插入新節(jié)點(diǎn)動(dòng)作。

2、鏈表本身已含其他節(jié)點(diǎn)

• 即鏈表的新節(jié)點(diǎn)的next指針會(huì)指向LinkedList對(duì)象的頭指針指向的節(jié)點(diǎn)，然后操作LinkedList對(duì)象的頭指針指向新的節(jié)點(diǎn)，完成鏈表頭節(jié)點(diǎn)插入新節(jié)點(diǎn)動(dòng)作。

//在鏈表的頭部插入結(jié)點(diǎn)
bool LinkList::ListInsertHead(Node *pNode)
{
    Node *temp = m_pList->next;         //將頭節(jié)點(diǎn)保存一個(gè)新的臨時(shí)節(jié)點(diǎn)中
    
    Node *newNode = new Node;               //堆中申請(qǐng)內(nèi)存
    if(newNode == NULL)
    {
        return false;
    }
    newNode->data = pNode->data;
    m_pList->next = newNode;            //頭節(jié)點(diǎn)指向新申請(qǐng)的節(jié)點(diǎn)
    newNode->next = temp;               //新申請(qǐng)的節(jié)點(diǎn)指針域
    m_iLength++;
    return true;
}

在末端插入元素操作

將要插入的節(jié)點(diǎn)放在鏈表中最后一個(gè)節(jié)點(diǎn)，因此該節(jié)點(diǎn)的next指針需要指向NULL

//在鏈表的尾部插入結(jié)點(diǎn)
bool LinkList::ListInsrtTail(Node *pNode)
{
    Node *currentNode = m_pList;
    while(currentNode ->next != NULL)     //遍歷最后一個(gè)節(jié)點(diǎn)
    {
        currentNode = currentNode->next;
    }
    Node *newNode = new Node;               //堆中申請(qǐng)內(nèi)存
    if(newNode == NULL)
    {
        return false;
    }
    //最后一個(gè)節(jié)點(diǎn)的next指向新創(chuàng)建的節(jié)點(diǎn)。
    newNode->data = pNode->data;            //
    newNode->next = NULL;                   //指向空作為最后一個(gè)節(jié)點(diǎn)
    currentNode->next = newNode;
    m_iLength++;                                    //鏈表長(zhǎng)度加一
    return true;
}

往鏈表中的任意位置插入新節(jié)點(diǎn)操作

插入新節(jié)點(diǎn)操作需遍歷到第i-1個(gè)節(jié)點(diǎn),插入前需要將一個(gè)臨時(shí)指針副本偏移到指定索引的位置，第i-1個(gè)位置的節(jié)點(diǎn)的next指針需要指向新的節(jié)點(diǎn)，新的節(jié)點(diǎn)的next指針需要指向原來(lái)第i-1個(gè)位置的節(jié)點(diǎn)的next指針

//往鏈表中任意位置插入節(jié)點(diǎn)
bool LinkList::ListInsert(int i,Node *pNode)
{
    if(i < 0 || i > m_iLength) return false;

    Node *currentNode = m_pList;//找到頭結(jié)點(diǎn)并保存到currentNode

    for(int j = 0;j<i;j++)      //遍歷到第i-1個(gè)節(jié)點(diǎn),因?yàn)椴迦肭靶枰獙⒁粋€(gè)臨時(shí)指針副本偏移到指定索引的位置,需要注意的
    {
        currentNode = currentNode->next;
    }
    Node *newNode = new Node;
    if(newNode == NULL)
    {
        return false;
    }
    newNode->data = pNode->data;            //賦值
    newNode->next = currentNode->next;      //原來(lái)currentNode的下一個(gè)節(jié)點(diǎn)變成了newNode的下一個(gè)節(jié)點(diǎn)
    currentNode->next = newNode;            //再把newNode成為urrentNode的下一個(gè)節(jié)點(diǎn)
    m_iLength++;
    return true;
}

鏈表中刪除節(jié)點(diǎn)

此時(shí)與插入節(jié)點(diǎn)操作不同的最大不同的是遍歷到第i個(gè)節(jié)點(diǎn)，因?yàn)閷?duì)于單向鏈表來(lái)說(shuō),一但我們的遍歷的指針位于第i個(gè)節(jié)點(diǎn)時(shí)已經(jīng)無(wú)法返回到位于i-1位置的節(jié)點(diǎn)，此時(shí)我們將位于第i個(gè)位置的節(jié)點(diǎn)執(zhí)行delete操作，那么第i-1個(gè)位置的節(jié)點(diǎn)與第k+1個(gè)位置的節(jié)點(diǎn)本應(yīng)要建立的鏈接關(guān)系已經(jīng)無(wú)法建立，那么從第k+1個(gè)位置的節(jié)點(diǎn)算起的部分與鏈表就“斷鏈”，造成鏈表內(nèi)存泄漏。

bool LinkList::ListDelete(int i,Node *pNode)
 {
    if(i < 0 || i >= m_iLength) return false;

    Node *currentNode = m_pList;//找到頭結(jié)點(diǎn)并保存到currentNode
    Node *currentNodeBefore = NULL;
    for(int j = 0;j<=i;j++)     //遍歷到第i個(gè)節(jié)點(diǎn)
    {
        currentNodeBefore = currentNode;  //臨時(shí)指針副本偏移到指定索引的第i個(gè)位置
        currentNode = currentNode->next;   //遍歷操作
    }
    currentNodeBefore->next = currentNode->next;
    pNode->data = currentNode->data;
    delete currentNode;
    currentNode = NULL;
    m_iLength--;
     return true;
 }

清空鏈表操作

清空鏈表，我們從頭鏈表的頭部元素一直遍歷到鏈表的末端,遍歷過(guò)程中,在每次循環(huán)偏移鏈表的頭指針時(shí),我們需要一個(gè)臨時(shí)指針變量來(lái)緩存前一個(gè)節(jié)點(diǎn)然后對(duì)其執(zhí)行內(nèi)存釋放操作。

//清空鏈表操作
void LinkList::ClearList()
{
    //刪除節(jié)點(diǎn)
   Node *currentNode =  m_pList->next ;
   while( currentNode != NULL)
   {
     Node *temp = currentNode->next;
     delete currentNode;
     currentNode = temp;
   }
   m_pList ->next =NULL;
}