欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++深入分析講解鏈表

 更新時(shí)間：2022年06月03日 09:30:23   作者：Bright-SKY  
當(dāng)我們?cè)趯懸欢未a時(shí)，如果要頻繁的在一塊區(qū)域進(jìn)行插入或者刪除操作時(shí)，會(huì)發(fā)現(xiàn)用數(shù)組實(shí)現(xiàn)會(huì)比較復(fù)雜，這時(shí)候我們就要用另一種數(shù)據(jù)結(jié)構(gòu)，鏈表來實(shí)現(xiàn)

鏈表的概述

1、數(shù)組特點(diǎn)

1、空間連續(xù)、元素類型相同、通過下標(biāo)快速訪問

2、靜態(tài)數(shù)組：空間一旦確定不能更改（動(dòng)態(tài)數(shù)組除外）

3、靜態(tài)、動(dòng)態(tài)數(shù)組 插入刪除元素 需要移動(dòng)大量數(shù)據(jù)

2、鏈表的概述

鏈表是一種物理存儲(chǔ)上非連續(xù)，數(shù)據(jù)元素的邏輯連續(xù)通過鏈表節(jié)點(diǎn)中的指針變量保存下個(gè)節(jié)點(diǎn)的地址，實(shí)現(xiàn)的一種線性存儲(chǔ)結(jié)構(gòu)。

3、鏈表的特點(diǎn)

鏈表由一系列節(jié)點(diǎn)（鏈表中每一個(gè)元素稱為節(jié)點(diǎn)）組成，節(jié)點(diǎn)在運(yùn)行時(shí)動(dòng)態(tài)生成（malloc，calloc），每個(gè)節(jié)點(diǎn)包 括兩個(gè)部分：

數(shù)據(jù)域：存放節(jié)點(diǎn)數(shù)據(jù)（核心）

指針域：結(jié)構(gòu)體指針變量 保存下一個(gè)節(jié)點(diǎn)的地址

靜態(tài)鏈表

#include <stdio.h>
//設(shè)計(jì)節(jié)點(diǎn)類型
typedef struct stu
{
    //數(shù)據(jù)域
    int num;
    char name[32];
    float score;
    //指針域
    struct stu *next;
}STU;
int main(int argc, char const *argv[])
{
    //靜態(tài)鏈表的節(jié)點(diǎn) 不是從堆區(qū)申請(qǐng)
    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};
    //構(gòu)建成鏈表
    STU *head = NULL;
    head = &node1;
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    node5.next = NULL;
    //遍歷鏈表(從頭節(jié)點(diǎn)  逐個(gè)節(jié)點(diǎn)遍歷)
    STU *pb = head;
    while(pb != NULL)
    {
        printf("%d %s %f\n", pb->num, pb->name, pb->score);
        //移動(dòng)到下一個(gè)節(jié)點(diǎn)
        pb = pb->next;
    }
    return 0;
}

鏈表的操作

增、刪、改、查

學(xué)生管理系統(tǒng) 講解鏈表

1、鏈表插入節(jié)點(diǎn)

幫助信息函數(shù)：

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

頭部之前插入節(jié)點(diǎn)

STU* insert_link(STU *head, STU tmp)
{
    //為插入的節(jié)點(diǎn)申請(qǐng)空間
    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;
}

尾部之后插入節(jié)點(diǎn)

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

有序插入節(jié)點(diǎn)

//有序插入節(jié)點(diǎn)
STU* insert_link(STU *head, STU tmp)
{
    //為插入的節(jié)點(diǎn)申請(qǐng)空間
    STU *pi = (STU *)calloc(1,sizeof(STU));
    //給空間賦值
    *pi = tmp;
    pi->next = NULL;
    //判斷鏈表是否存在
    if(NULL == head)
    {
        head = pi;
        return head;
    }
    else
    {
        //尋找插入點(diǎn)
        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、遍歷鏈表節(jié)點(diǎn)

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

3、查詢指定節(jié)點(diǎn)

STU *search_link(STU *head, char *name)
{
    //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return NULL;
    }
    else//鏈表存在
    {
        //逐個(gè)節(jié)點(diǎn)查詢
        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("未找到相關(guān)節(jié)點(diǎn)信息\n");
            return NULL;
        }
    }
    return NULL;
}

4、刪除指定節(jié)點(diǎn)

STU* delete_link(STU *head, char *name)
 {
     //判斷鏈表是否存在
    if(NULL == head)
    {
        printf("鏈表不存在\n");
        return head;
    }
    else
    {
        STU *pf =NULL, *pb=NULL;
        pf = pb = head;
        //尋找刪除點(diǎn)
        while((strcmp(pb->name, name) != 0) && (pb->next != NULL))
        {
            pf = pb;
            pb = pb->next;
        }
        //找到刪除點(diǎn)
        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//未找到刪除點(diǎn)
        {
            printf("未找到刪除的相關(guān)節(jié)點(diǎn)信息\n");
        }
    }
    return head;
 }

5、釋放鏈表

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

6、鏈表的翻轉(zhuǎn)

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

7、鏈表的排序

//選擇法對(duì)鏈表排序
 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;
 }

到此這篇關(guān)于C++深入分析講解鏈表的文章就介紹到這了,更多相關(guān)C++鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論