删除指定位置的結點

任務描述

線性表的結點是有序号的，包含

n

（1<=n<=100）個結點（不包括頭結點）的線性表從鍊頭到鍊尾的結點序号分别為

1

、

2

、……

n

。本關要求按照資料輸入的順序建構一個線性表，然後輸入待删除結點編号i，删除第i個結點，并輸出删除結點後的線性表元素。

程式設計要求

本關的程式設計任務是補全

step4/deleteAt.h

檔案中

deleteAt

函數，以實作删除線性表指定位置結點的要求。

// 函數deleteAt：删除連結清單中序号為i的結點，如果i是非法序号(i<=0||i>n)則不做操作 // 參數：h-連結清單頭指針，i-要删除結點的序号 // 傳回值：删除結束後連結清單首結點位址 node* deleteAt(node* h, int i);

相關知識

結點的删除可以根據結點位置的需要注意3個問題：被删除結點位置合法性的檢查、被删除結點的空間的釋放、删除最後一個結點時的處理。

• 被删除頂點位置合法性的檢查：n個結點的合法删除位置為1~n，若超出該範圍，則連結清單保持不變。
• 被删除結點的空間的釋放：當删除第i個頂點的時候，除了需要修改第i-1個頂點的指針之外，還要釋放被删除頂點的存儲空間，是以在修改第i-1個結點的指針域之前，應該先利用一個指針變量指向第i個結點，并在修改完第i-1個結點的指針域後，釋放被删除頂點的存儲空間。
• 删除最後一個結點時的處理：針對非循環單連結清單，當删除的第i個頂點為最後一個結點時，應該修改第i-1個頂點的指針域為空指針域。

評測說明

本關中包含三個檔案分别是： step4/deleteAt.h ：此檔案為學員檔案，包含删除連結清單指定位置結點函數實作。 step4/linkList.h：此檔案包含連結清單常見操作的說明與實作，引用了deleteAt.h step4/test.cpp：此檔案為評測檔案（含main函數），引用“linkList.h”。 （上述三個檔案可通過點選在代碼取的右上角檔案夾中的step4檔案夾中檢視） (注意：本關所實作鍊式線性表為帶頭結點的單連結清單)

輸入輸出說明

輸入n(1<=n<=100),然後輸入n個整數，最後輸入位置i（1<=i<=n）,按元素輸入書順序删除第i個元素後，輸出剩餘元素，如下所示：（注意：連結清單的輸出函數已經實作，詳情請閱讀step4檔案夾中的檔案。）

測試輸入：

5

2 4 6 8 1

1

預期輸出：

List: 4 6 8 1

5

1 2 3 4 5

6

List: 1 2 3 4 5

test.cpp

#include "linkList.h"

int main()
{
    int n, i;
    node* t;
    node* head = new node;// 帶頭結點單連結清單,頭結點指針head
    head->next = NULL; // 頭結點head->next==NULL，連結清單為空
    //輸入結點數
    cin >> n;
    for (i = 0; i < n; i++)
    {
        //為新節點動态配置設定空間
        t = new node;
        cin >> t->data; //輸入結點資料
        t->next = NULL;  //結點指針域值為空
        //按輸入順序建構連結清單
        head = insertTail(head, t);
    }
    //輸入要删除結點的序号
    cin >> i;
    //在連結清單中删除序号為i的結點
    head = deleteAt(head, i);
    //輸對外連結表
    printList(head);
    //删除結點，釋放空間
    delList(head);

    return 0;
}      

linkList.h

#include <iostream>
using namespace std;

// 定義結點結構
struct node
{
    int data;  // 資料域
    node* next;  // 指針域,指向下一個結點
};

// 函數deleteAt：删除連結清單中序号為i的結點，如果i是非法序号則不做操作
// 參數：h-連結清單頭指針，i-要删除結點的序号
// 傳回值：删除結束後連結清單頭結點位址
node* deleteAt(node* h, int i);


// 函數insertTail：連結清單尾部插入
// 參數：h-連結清單頭指針，t-指向要插入的結點
// 傳回值：插入結點後連結清單的頭結點位址
node* insertTail(node* h, node* t);

// 函數printList：輸對外連結表，每個資料之間用一個空格隔開
// 參數：h-連結清單頭指針
void printList(node* h);

// 函數delList：删除連結清單，釋放空間
// 參數：h-連結清單頭指針
void delList(node* h);

#include "deleteAt.h"

//函數delList：删除連結清單，釋放空間
//參數：h-連結清單頭指針
void delList(node* h)
{
    node* p = h; //指針p指向頭結點，第一個要删除的結點
    while (p) //這個結點是存在的
    {
        h = h->next; //頭指針h指向下一個結點（下一個結點的位址存在目前結點的指針域中，即h->next中
        delete p; //删除p指向的結點
        p = h; //p指向目前的頭結點，即下一個要删除的結點
    }
}
//函數printList：輸對外連結表，每個資料之間用一個空格隔開
//參數：h-連結清單頭指針
void printList(node* h)
{
    cout << "List:";
    h = h->next;
    while (h)
    {// h為真，即h指向的結點存在，則輸出該結點的資料
        cout << " " << h->data;  // 輸出結點資料
        h = h->next;  // 将該結點的指針域指派給h，h就指向了下一個結點
    }
    cout << endl; // 輸出換行符
}


// 函數insertTail：連結清單尾部插入
// 參數：h-連結清單頭指針，t-指向要插入的結點
// 傳回值：插入結點後連結清單的頭結點位址
node* insertTail(node* h, node* t)
{
    // 請在此添加代碼，補全函數insertTail
    /********** Begin *********/

    node* p = h;
    // 讓p指向最後一個結點
    while (p->next)
        p = p->next;
    p->next = t; // 讓最後一個結點的指針域指向結點t
    t->next = NULL; // 連結清單尾指針置為NULL
    return h;  // 傳回第一個結點的位址（即連結清單頭指針）
    /********** End **********/
}      

// 函數deleteAt：删除連結清單中序号為i的結點，如果i是非法序号則不做操作
// 參數：h-連結清單頭指針，i-要删除結點的序号
// 傳回值：删除結束後連結清單頭結點位址
node* deleteAt (node* h, int i)
{
    // 請在此添加代碼，補全函數deleteHas
    /********** Begin *********/
    if(i<0)
    {
        return h;
    }
    node *p = NULL, *q = h; // 定位删除結點，試圖讓q指向要删除結點，p指向其前面的結點
    for(int k = 0; k < i; k++)
    {
        if(q->next == NULL) // 後面沒有結點了，序号非法
        {
            return h;
      }
        p = q;
        q = q->next;
    }
    if(p) // p指向的結點存在，不是删除首結點
    {
        // 删除q指向的結點，讓p指向結點的指針域指向q的後續結點
        p->next = q->next;
        // 釋放空間
        delete q;
        return h;
    }
    else // 删除首結點
    {
        h = q->next; // 下一個結點成了首結點
        // 釋放空間
        delete q;
        return h;
    }
    /********** End **********/
}