C++链表

时间:2022-06-05 Bright-SKY 人气:0

链表的概述

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;
 }

加载全部内容