C++資料結構與演算法: 單向鏈結串列(下)

在上一篇簡單說明如何將標頭檔轉換成UML類別圖，而這篇將主要解釋有關鏈結串列的刪除，加入和顯示，如以下所示：

• showList()：顯示鏈結串列所有資料
• append(QString addData)：在鏈結串列的後面加入資料
• remove(QString delData)：刪除鏈結串列的某一筆資料

成員函數showList()

主要顯示鏈結串列內的字串內容，利用迴圈判斷curr的指標結構變數是否為NULL來走訪鏈結串列，這裡使用C函數printf印出串列資料

void dstringList::showList()
{
    curr=head;
    while(curr!=NULL)
    {
        printf("%S\n",curr->data.constData());
        curr=curr->next;
    }
}

成員函數append(QString addData)

圖二．在鏈結串列後面加入資料

如圖二所示，此函數主要在鏈結串列後面加入新結構變數資料．首先，我先宣告指標結構變數node，並且在資料成員的data要加入字串資料和指標變數next為NULL ．然後，走訪鏈結串列找到資料尾端後，將此尾端的資料成員next指向新加入的結構變數node．

void dstringList::append(QString addData)
{
    nodeptr node=new strNode;
    node->data=addData;
    node->next=NULL;

    if(head!=NULL)
    {
        curr=head;
        while(curr->next!=NULL)
        {
            curr=curr->next;
        }
        curr->next=node;
    }
    else head=node;
}

成員函數remove(QString delData)

圖三．刪除結構變數含有Taipei的資料

此函數主要刪除鏈結串列含有資料delData的結構變數strNode．假設要刪除串列中字串為Taipei，詳細流程如以下說明：

• 利用迴圈在確認指向下一個結構變數不為NULL和目前結構變數的資料不為Taipei下走訪鏈結串列.
• curr：紀錄目前的結構變數記憶體位址．
• temp：則紀錄上一個結構變數記憶體位址．
• 當找到所要刪除結構變數記憶體位址時，delPtr將記錄此位址後利用delete釋放此記憶體位址．換句話說，刪除在記憶體刪除含有Taipei的結構變數．
• 最後，curr將指向下一個含有Xinbei的結構變數，然後temp的結構變數指標將指向此結構變數，如圖三所示．

void dstringList::remove(QString delData)
{
    nodeptr delPtr=NULL;
    temp=head;
    curr=head;
    while(curr!=NULL&&curr->data!=delData)
    {
        temp=curr;
        curr=curr->next;
    }
    if(curr==NULL)
    {
        printf("%S was not in the List\n",delData.constData());
        delete delPtr;
    }
    else
    {
        delPtr=curr;
        curr=curr->next;
        temp->next=curr;
        if(temp==head)
        {
           head=head->next;
           temp=NULL;
        }
        delete delPtr;
    }
}