C++深入分析講解鏈表

Posted on by

鏈表的概述

1、數組特點

1、空間連續、元素類型相同、通過下標快速訪問

2、靜態數組：空間一旦確定不能更改（動態數組除外）

3、靜態、動態數組 插入刪除元素 需要移動大量數據

2、鏈表的概述

鏈表是一種物理存儲上非連續，數據元素的邏輯連續通過鏈表節點中的指針變量保存下個節點的地址，實現的一種線性存儲結構。

3、鏈表的特點

鏈表由一系列節點（鏈表中每一個元素稱為節點）組成，節點在運行時動態生成（malloc，calloc），每個節點包 括兩個部分：

數據域：存放節點數據（核心）

指針域：結構體指針變量 保存下一個節點的地址

靜態鏈表

#include <stdio.h>
//設計節點類型
typedef struct stu
{
    //數據域
    int num;
    char name[32];
    float score;
    //指針域
    struct stu *next;
}STU;
int main(int argc, char const *argv[])
{
    //靜態鏈表的節點 不是從堆區申請
    STU node1={100, "lucy", 77.7f};
    STU node2={101, "bob", 66.7f};
    STU node3={102, "tom", 55.7f};
    STU node4={103, "hehe", 74.7f};
    STU node5={104, "xixi", 73.7f};
    //構建成鏈表
    STU *head = NULL;
    head = &node1;
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    node5.next = NULL;
    //遍歷鏈表(從頭節點  逐個節點遍歷)
    STU *pb = head;
    while(pb != NULL)
    {
        printf("%d %s %f\n", pb->num, pb->name, pb->score);
        //移動到下一個節點
        pb = pb->next;
    }
    return 0;
}

鏈表的操作

增、刪、改、查

學生管理系統 講解鏈表

1、鏈表插入節點

幫助信息函數：

void help(void)
{
    printf("******************************\n");
    printf("* insert:插入鏈表節點        *\n");
    printf("* printf:遍歷鏈表節點        *\n");
    printf("* search:查詢鏈表節點        *\n");
    printf("* delete:刪除鏈表節點        *\n");
    printf("* free:釋放鏈表節點          *\n");
    printf("* quit:遍歷鏈表節點          *\n");
    printf("******************************\n"); 
    return; 
}

頭部之前插入節點

STU* insert_link(STU *head, STU tmp)
{
    //為插入的節點申請空間
    STU *pi = (STU *)calloc(1,sizeof(STU));
    //給空間賦值
    *pi = tmp;
    pi->next = NULL;
    //判斷鏈表是否存在
    if(NULL == head)//空
    {
        head = pi;
        //return head;
    }
    else//非空
    {
        pi->next = head;
        head = pi;
        //return head;
    }
    return head;
}

尾部之後插入節點

//尾部插入節點
STU* insert_link(STU *head, STU tmp)
{
    //為插入的節點申請空間
    STU *pi = (STU *)calloc(1,sizeof(STU));
    //給空間賦值
    *pi = tmp;
    pi->next = NULL;
    //判斷鏈表是否存在
    if(NULL == head)
    {
        head = pi;
        return head;
    }
    else
    {
        //尋找尾部節點
        STU *pb = head;
        while(pb->next != NULL)
            pb = pb->next;
        //將pi插入到 尾節點後
        pb->next = pi;
        return head;
    }
    return head;
}

有序插入節點

//有序插入節點
STU* insert_link(STU *head, STU tmp)
{
    //為插入的節點申請空間
    STU *pi = (STU *)calloc(1,sizeof(STU));
    //給空間賦值
    *pi = tmp;
    pi->next = NULL;
    //判斷鏈表是否存在
    if(NULL == head)
    {
        head = pi;
        return head;
    }
    else
    {
        //尋找插入點
        STU *pf = NULL, *pb = NULL;
        pf = pb = head;
        //從小--->大排序
        while((pb->num < pi->num) && (pb->next != NULL))
        {
            pf = pb;
            pb = pb->next;
        }
        if(pb->num >= pi->num)//頭部插入、中部插入
        {
            if(pb == head)//頭部插入
            {
                pi->next = head;
                head = pi;
            }
            else//中部插入
            {
                pf->next = pi;
                pi->next = pb;
            }
        }
        else if(pb->next == NULL)//尾部插入
        {
            pb->next = pi;
        }
    }
    return head;
}

2、遍歷鏈表節點

void printf_link(STU *head)
{
    //1、判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return;
    }
    else//2、鏈表存在，逐個節點遍歷鏈表
    {
        STU *pb = head;
        while(pb != NULL)
        {
            printf("%d %s %f\n", pb->num, pb->name, pb->score);
            //pb指向下一個節點
            pb = pb->next;
        }
    }
    return;
}

3、查詢指定節點

STU *search_link(STU *head, char *name)
{
    //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return NULL;
    }
    else//鏈表存在
    {
        //逐個節點查詢
        STU *pb = head;
        while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
        {
            pb = pb->next;
        }
        if(strcmp(pb->name, name) == 0)//找到
            return pb;
        else
        {
            printf("未找到相關節點信息\n");
            return NULL;
        }
    }
    return NULL;
}

4、刪除指定節點

STU* delete_link(STU *head, char *name)
 {
     //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return head;
    }
    else
    {
        STU *pf =NULL, *pb=NULL;
        pf = pb = head;
        //尋找刪除點
        while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
        {
            pf = pb;
            pb = pb->next;
        }
        //找到刪除點
        if(strcmp(pb->name, name) == 0)
        {
            if(head == pb)//頭部刪除
            {
                head= head->next;
            }
            else//中尾部刪除
            {
                pf->next = pb->next;
            }
            //釋放pb
            if(pb != NULL)
            {
                free(pb);
                pb=NULL;
            }
        }
        else//未找到刪除點
        {
            printf("未找到刪除的相關節點信息\n");
        }
    }
    return head;
 }

5、釋放鏈表

STU* free_link(STU *head)
 {
    //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return head;
    }
    else//鏈表存在
    {
        STU *pb = head;
        while(pb != NULL)
        {
            //head紀錄下一個節點的位置
            head = head->next;
            //釋放pb指向的節點
            if(pb != NULL)
            {
                free(pb);
                pb = NULL;
            }
            //pb指向下一個節點
            pb=head;
        }
        printf("鏈表節點已經完全釋放\n");
    }
    return head;
 }

6、鏈表的翻轉

STU* reverse_link(STU *head)
 {
    //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return head;
    }
    else
    {
        STU *pb = head->next;
        STU *pn = NULL;
        //將頭結點指針域指向NULL
        head->next = NULL;
        //逐個節點翻轉
        while(pb != NULL)
        {
            //pn紀錄pb->next的節點
            pn = pb->next;
            //進行反向連接
            pb->next = head;
            //移動head到pb上
            head = pb;
            //pb指向pb的節點
            pb = pn;
        }  
    }
    return head;
 }

7、鏈表的排序

//選擇法對鏈表排序
 void sort_link(STU *head)
 {
    //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return;
    }
    else
    {
        STU *p_i = head, *p_j = head;//int i=0, j=0;
        while(p_i->next != NULL)//for(i=0;i<n-1; i++)
        {
            STU *p_min = p_i;//int min = i;
            p_j = p_min->next;//j=min+1
            while(p_j != NULL)//j<n
            {
                if(p_min->num > p_j->num)//if(arr[min] > arr[j])
                    p_min = p_j;//min = j;
                p_j = p_j->next;//j++
            }
            if(p_i != p_min)//if(i != min)
            {
                //整體交換
                STU tmp = *p_i;
                *p_i = *p_min;
                *p_min = tmp;
                //指針域交換
                tmp.next = p_i->next;
                p_i->next = p_min->next;
                p_min->next = tmp.next;
            }
            p_i = p_i->next;//i++
        }
    }
    return;
 }

到此這篇關於C++深入分析講解鏈表的文章就介紹到這瞭,更多相關C++鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：