單鏈表基本操作總結

鏈表基本概念：
鏈表：線性表的鏈式存儲。
數據域：存儲數據信息。即數據。
指針域：存放下一節點的位置信息。即該指針指向下一節點。

單鏈表：每一個節點node：一個數據域 + 一個指針域。
頭節點：
1、數據域可以存放線性表長度等公共信息。
2、指針域，指向第一個節點（數據域）的位置。
3、頭結點不一定是鏈表的必須元素。不過有了頭結點，對第一個元素節點前插入和刪除元素，就和其它節點一致了。
4、頭結點是為了操作的同一和方便設立的，其數據域一般無意義，也可存放鏈表長度。
頭指針：指向第一個結點的指針。
最後一個節點：數據域存放數據；指針域為空，即NULL。
若線性表為空，則頭節點的指針域為空。
// 循環鏈表：將單鏈表中的終端節點的指針由空指針改為指向頭結點，就使整個單鏈表形成一個環，這種頭尾相接的單鏈表簡稱循環鏈表。
// 雙向鏈表：是在單鏈表的每個節點中，再設置一個指向其前驅節點的指針域。

單鏈表基本操作有：創建、輸出、測長、插入、刪除、逆置、排序等。

單鏈表結構定義代碼：

typedef struct Node{
    int data;
    struct Node *next;
}ListNode;

創建單鏈表操作：

/**創建鏈表*/
ListNode * Create_list(int n)     // 注意這裡函數返回值為一個指向Node的指針，n表示幾個節點
{
    int elem,i;
    i = 1;
    ListNode *head, *current, *temp;   /*current：代表一個當前節點，它的下一節點是你正要創建的；temp：代表你正要創建的節點。*/
    head = new ListNode;
    head->next = NULL;
    head->data = n;
    current = head;

    while(i <= n)   /*尾插法：即新節點放在尾部*/
    {
        cout << "please input elem: " << endl;
        cin >> elem;

        temp = new ListNode;
        temp->data = elem;
        temp->next = NULL;
        current->next = temp;
        current = temp;
        i++;
    }

    return head;
}

輸出操作：

/**輸出鏈表*/
int Output_list(ListNode *head)
{
    ListNode *p;
    p = head->next;
    if(p == NULL)
    {
        cout << "The List is NULL" << endl;
        return 0;
    }
    do{
        cout << p->data << ' ';
        p = p->next;
    }while(p != NULL);           // 這裡需要加“；”

    cout << endl;

    return 0;
}

測一個鏈表的節點數，即長度：

/**測長度*/
int Length_test(ListNode *head)
{
    ListNode *p;
    int i = 0;
    p = head->next;

    while(p != NULL)
    {
        i++;
        p = p->next;
    }
    cout << "The length of list is " << i << endl;
    return 0;
}

插入節點操作：

/**在第i個節點後插入一個節點，elem：表示你要插入的數據*/
ListNode * Insert_node(ListNode *head,int elem,int i)
{
    int j = 0;
    ListNode *p,*temp;
    temp = head->next;
    /*錯誤寫法
    while(NULL != temp) 在找到 j 後沒有跳出循環
    {
        j++;
        if(j <= i)
            temp = temp->next;
    }
    */
    while(NULL != temp)
    {
        j++;
        if(j >= i)   /**指針停在第i個節點之前*/
            break;
        temp = temp->next;
    }
    if(temp == NULL)
    {
        cout << "There is no i" << endl;
        return head;
    }
    p = new ListNode;
    p->data = elem;
    p->next = temp->next;
    temp->next = p;

    head->data = head->data + 1;   /**插入一個結點，頭結點數據保存的鏈表長加一*/

    return head;
}

刪除操作：

/**刪除第i個結點*/
ListNode * Delete_node(ListNode *head,int i)
{
    int j = 0;
    ListNode *temp,*pre_temp;
    temp = head->next;

    while(NULL != temp)
    {
        j++;
        if(j >= i)
            break;
        pre_temp = temp; /**保存之前節點*/
        temp = temp->next;
    }
    if(temp == NULL)
    {
        cout << "There is no i" << endl;
        return head;
    }
    pre_temp->next = temp->next;
    /**這裡不能寫成temp = temp->next; 因為下面有 delete temp;會將後面的節點刪掉*/

    delete temp;

    head->data -= 1;   /**刪掉一個結點，頭結點數據保存的鏈表長減一*/

    return head;
}

逆置操作：

/**單鏈表逆置，將頭結點後的節點一個個斷開，使用頭插法插入在頭結點後*/
ListNode * Reverse_list(ListNode *head)
{
    if(NULL == head)
        return head;
    if(NULL == head->next)
        return head;
    if(NULL == head->next->next)
        return head;
    /**要實現逆置，除了頭結點外，至少需要2個數據節點*/

    ListNode *curr, *temp;
    curr = head->next;    /**curr用來保存斷開後的那一串*/
    head->next = NULL;    /**頭結點與後面結點斷開*/

    while(NULL != curr)
    {
        temp = curr->next;         /**temp起臨時代替curr的作用*/
        curr->next = head->next;   /**頭插法*/
        head->next = curr;
        curr = temp;               /**temp將功能還給curr*/
    }
    return head;
}

單鏈表排序（使用冒泡排序法）：此排序算法，僅交換了數據，沒有交換結點

void Swap_data(int &a,int &b)   /**這裡必須要加引用符，不然交換沒效果*/
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
ListNode * Sort_list(ListNode *head)
{
    int i,len;
    ListNode *p;
    len = head->data;
    p = head->next;
    if(NULL == p)
        cout << "list is null" << endl;
    for(i = 1; i <= len; i++)
    {
        while(NULL != p->next)
        {
            if(p->data > p->next->data)
                Swap_data(p->data,p->next->data);
            p = p->next;
        }
        p = head->next;
    }
    return head;
}

一個特別的函數：用於找出單鏈表中間節點，在不知道節點總數的情況下

/**不知節點總數，只遍歷一次就可以求出中間結點*/
/**這個函數有問題，只能對節點為奇數的求解，節點為偶數時，會出現p->next->next無意義的情況，使程序發生錯誤*/
/*原理是：找兩個指針，一個每次走一步，另一個每次走兩步，當走兩步的指針到結尾時，走一步的指針剛好走到中間結點處*/
void Search_mid(ListNode *head)
{
    ListNode *p_1,*q_2;
    ListNode *mid;
    p_1 = head->next;
    q_2 = head->next;
    while(NULL != q_2->next)
    {
        p_1 = p_1->next;
        q_2 = q_2->next->next;
        mid = p_1;
    }
    cout << "中間值為: " << mid->data << endl;
}

測試主函數：

int main()
{
    ListNode *p;
    int a=3;
    int b = 4;
    p = Create_list(5);
    cout << "The list is:" << endl;
    Output_list(p);
    Length_test(p);

    p = Insert_node(p,6,5);
    cout << "插入節點後:" << endl;
    Output_list(p);
    cout << "New length: " << p->data << endl;

    p = Delete_node(p,3);
    cout << "刪除節點後:" << endl;
    Output_list(p);

    p = Reverse_list(p);
    cout << "逆置後:" << endl;
    Output_list(p);

    p = Sort_list(p);
    cout << "排序後（從小到大）:" << endl;
    Output_list(p);

    cout << "原ab: " << a << b << endl;
    Swap_data(a,b);
    cout << "交換後: " << a << b << endl;

    Search_mid(p);

    return 0;
}