首页 > 其他分享 >13_链表

13_链表

时间：2023-09-05 13:34:00浏览次数：35  
标签：pb 13 head next 链表 STU num

链表

链表的概述

数组和链表的优缺点

静态数组: int arr[5]; 必须事先确定元素个数, 过多浪费, 过小溢出, 删除插入效率低

动态数组: 不需要知道元素个数, 在使用中动态申请, 删除插入数据效率低

数组优点: 遍历元素方便

链表: 不需要事先知道数据的个数, 在使用中动态申请, 插入删除不需要移动数据

链表概述

链表由一个个节点组成, 节点没有名字, 每个节点从堆区动态申请, 节点间物理空间是非连续的, 但是每个节点通过指针域, 保存下一个节点的位置, 达到逻辑上的连续

image-20230824174754269

静态链表

设计链表节点

struct stu
{
    //数据域
    int num;
    char name[32];
    //指针域
    struct stu *next;
};
int main(int argc, char const *argv[])
{
    struct stu node1 = {101, "lucy", NULL};
    struct stu node2 = {102, "bob", NULL};
    struct stu node3 = {103, "tom", NULL};
    struct stu node4 = {104, "tak", NULL};
    struct stu node5 = {105, "fub", NULL};
    //定义链表头
    struct stu *head = &node1;
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;
    //遍历
    struct stu *pb = head;
    while (pb != NULL)
    {
        //访问数据
        printf("%d %s\n", pb -> num, pb -> name);
        pb = pb->next;
    }
    return 0;
}

学生管理系统

结构体起别名

//第一种
typedef struct Data1
{
  int a;
  char b;
} data1, *D_POINTER; //类型名, 指针类型名
int main(int argc, char const *argv[])
{
    data1 d1 = {100, 'e'};
  	D_POINTER p = &d1;
    return 0;
}
//第二种
struct Data2
{
  int a;
  char b;
};
int main(int argc, char const *argv[])
{
    typedef struct Data2 data2;
  	data2 d2;
    return 0;
}

image-20230826135524777

工程的main函数的设计

#include<stdio.h>
#include<string.h>
#include"link.h"
STU *head = NULL; //一定要初始化为NULL
void help()
{
    printf("********************************\n");
    printf("*help:帮助信息                 *\n");
    printf("*insert:插入链表节点           *\n");
    printf("*print:遍历链表节点            *\n");
    printf("*search:查询链表某个节点       *\n");
    printf("*delete:删除链表某个节点       *\n");
    printf("*free:释放整个链表             *\n");
    printf("*quit:退出程序                 *\n");
    printf("********************************\n");
}
int main(int argc, char const *argv[])
{
    help();
    while (1)
    {
        char cmd[128] = "";
        printf("请输入操作命令:");
        scanf("%s", cmd);

        if (strcmp(cmd, "help") == 0)
        {
            help();
        }
        else if (strcmp(cmd, "insert") == 0)
        {
            printf("请输入需要插入的学生信息num name score: ");
            STU tmp;
            scanf("%d %s %f", &tmp.num, &tmp.name, &tmp.score);

            //将tmp插入到链表中
            head = insert_link(head, tmp);
        }
        else if (strcmp(cmd, "print") == 0)
        {
            printf("---------链表遍历----------\n");
        }
        else if (strcmp(cmd, "search") == 0)
        {
            printf("---------链表查询----------\n");
        }
        else if (strcmp(cmd, "delete") == 0)
        {
            printf("---------删除链表指定节点----------\n");
        }
        else if (strcmp(cmd, "free") == 0)
        {
            printf("---------释放链表----------\n");
        }
        else if (strcmp(cmd, "quit") == 0)
        {
            printf("---------退出程序----------\n");
            break;
        }             
    }
    return 0;
}

链表插入节点值---头部之前插入

如果链表不存在

image-20230826224232790

#include<stdio.h>
#include"link.h"
#include<stdlib.h>

//头部之前插入
STU* insert_link(STU *head, STU tmp)
{
    //为待插入的数据申请空间
    STU *pi = (STU *)calloc(1, sizeof(STU));
    if (pi == NULL)
    {
        perror("calloc");
        exit(-1); //结束进程
    }
    //将tmp数据赋值到*pi
    *pi = tmp;
    pi->next = NULL;
    
    //判断链表是否存在
    if (head == NULL) //不存在
    {
        head = pi;
    }
    else //存在
    {
        pi->next = head;
        head = pi;
    }
    return head;
    
}

尾部插入

//尾部插入
STU* insert_link(STU *head, STU tmp)
{
    //为待插入的数据申请空间
    STU *pi = (STU *)calloc(1, sizeof(STU));
    if (pi == NULL)
    {
        perror("calloc");
        exit(-1); //结束进程
    }
    //将tmp数据赋值到*pi
    *pi = tmp;
    pi->next = NULL;
    
    //判断链表是否存在
    if (head == NULL) //不存在
    {
        head = pi;
    }
    else //存在
    {
        STU *pb = head;
        while (pb->next != NULL)
        {
            pb = pb->next;
        }
        pb->next = pi;
        
    }
    return head;
    
}

有序 插入

// 有序插入
STU *insert_link(STU *head, STU tmp)
{
    // 为待插入的数据申请空间
    STU *pi = (STU *)calloc(1, sizeof(STU));
    if (pi == NULL)
    {
        perror("calloc");
        exit(-1); // 结束进程
    }
    // 将tmp数据赋值到*pi
    *pi = tmp;
    pi->next = NULL;

    // 判断链表是否存在
    if (head == NULL) // 不存在
    {
        head = pi;
    }
    else // 存在
    {
        // 寻找插入点位置
        STU *pb = head, *pf = head;
        while ((pi->num > pb->num) && (pb->next != NULL))
        {
            pf = pb;
            pb = pb->next;
        }
        if (pi->num > pb->num) // 尾部插入
        {
            pb->next = pi;
        }
        else // 头部或中部插入
        {
            if (head == pb) // 头部之前插入
            {
                pi->next = head;
                head = pi;
            }
            else // 中部插入
            {
                pf->next = pi;
                pi->next = pb;
            }
        }
    }
    return head;
}

遍历

// 遍历
void printf_link(STU *head)
{
    // 判断链表是否存在
    if (head == NULL)
    {
        printf("link not exits\n");
        return;
    }
    else
    {
        STU *pb = head;
        while (pb != NULL)
        {
            printf("%d %s %f\n", pb->num, pb->name, pb->score);
            pb = pb->next;
        }
    }
}

姓名查询

//姓名查询
STU *search_link(STU *head, char *name)
{
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("link not exits\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;
        }
        return NULL;
    }
}

删除指定节点

STU *delete_link(STU *head, int num) //删除节点
{
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("链表为空\n");
        return head;
    }
    // 查找删除点
    STU *pb = head, *pf = head;
    while ((pb->num != num) && (pb->next != NULL))
    {
        pf = pb;
        pb = pb->next;
    }
    if (pb->num == num) // 找到
    {
        if (pb == head) // 是头节点
        {
            head = head->next;
        }
        else //是中间或尾节点
        {
            pf->next = pb->next;
        }
        free(pb);
        printf("已成功删除num = %d的节点\n", num);
    }
    else // 未找到
    {
        printf("没找到该节点\n");
    }
    return head;
}

释放链表

STU* free_link(STU *head) //释放链表
{
    //判断链表是否存在
    if (head == NULL)
    {
        printf("link not exits\n");
    }
    else
    {
        STU *pb = head;
        while (pb != NULL)
        {
            head = pb->next;
            free(pb);
            pb = head;
        }
        printf("释放链表成功\n");
    }
    return NULL;
}

反转链表

STU *reverse_link(STU *head) // 反转链表
{
    // 判断链表是否存在
    if (NULL == head)
    {
        printf("link not exits\n");
    }
    else
    {
        STU *pb = head->next, *pf = head;
        pf->next = NULL;
        while (pb != NULL)
        {
            head = pb;
            pb = pb->next;
            head->next = pf;
            pf = head;
        }
        printf("链表反转成功!!");
    }
    return head;
}

链表排序

void sort_link(STU *head) // 排序
{
    if (NULL == head)
    {
        printf("link is not exits\n");
    }
    else
    {
        STU *p_i = head, *p_j, *min, temp;
        for (; p_i->next != NULL; p_i = p_i->next)
        {
            min = p_i;
            for (p_j = p_i->next; p_j != NULL; p_j = p_j->next)
            {
                if (p_j->num < p_i->num)
                {
                    min = p_j;
                }
            }
            if (min != p_i)
            {
                temp = *min;
                *min = *p_i;
                *p_i = temp;
                temp.next = min->next;
                min->next = p_i->next;
                p_i->next = temp.next;
            }  
        }
        printf("排序成功!\n");
    }
    return head;
}

双向链表

image-20230904091812466

typedef struct stu
{
    //数据域
    int num;
    char name[32];
    
    //指针域
    struct stu *pre;
    struct stu *next;
}STU;

尾插法

// 尾插法
void insert_link(STU **p_head, STU tmp)
{
    STU *head = *p_head;
    // 为插入的节点申请空间
    STU *pi = (STU *)calloc(1, sizeof(STU));
    *pi = tmp;
    pi->next = NULL;
    pi->pre = NULL;
    // 判断链表是否为空
    if (NULL == head)
    {
        head = pi;
        pi->next = pi;
        pi->pre = pi;
    }
    else
    {
        head->pre->next = pi;
        pi->pre = head->pre;
        head->pre = pi;
        pi->next = head;
    }
    // 更新外部的head
    *p_head = head;
}

双向遍历

// 双向遍历
void print_link(STU *head)
{
    if (NULL == head)
    {
        printf("The linked list does not exist.");
    }
    else
    {
        STU *pn = head;
        STU *pr = head->pre;
        while (1)
        {
            if (pn == pr) //链表节点为奇数个
            {
                printf("%d %s\n", pn->num, pn->name);
                break;
            }
            else if(pn->next == pr) //链表节点为偶数个
            {
                printf("%d %s\n", pn->num, pn->name);
                printf("%d %s\n", pr->num, pr->name);
                break;
            }
            printf("%d %s\n", pn->num, pn->name);
            printf("%d %s\n", pr->num, pr->name);
            pn = pn->next;
            pr = pr->pre;
        }
    }
}

双向查询

// 双向查询
STU *search_link(STU *head)
{
    if (NULL == head)
    {
        printf("The linked list does not exist.");
    }
    else
    {
        printf("请输入你要查询的学号: ");
        int num = 0;
        scanf("%d", &num);
        STU *ph = head;
        STU *pt = head->pre;
        while ((ph->num != num) && (pt->num != num) && (ph->next != pt) && (pt != ph))
        {
            ph = ph->next;
            pt = pt->pre;
        }
        if (ph->num == num)
        {
            return ph;
        }
        else if (pt->num == num)
        {
            return pt;
        }
        else
        {
            printf("没查到\n");
            
        }
    }
    return NULL;
}

双向删除

// 删除
void delete_link(STU **p_head, int num)
{
    STU *head = *p_head;
    if (NULL == head)
    {
        printf("link does not exits!");
    }
    else
    {
        STU *top = head;
        STU *tail = head->pre;
        while ((top->num != num) && (tail->num != num) && (top->next != tail) && (tail != top))
        {
            top = top->next;
            tail = tail->pre;
        }
        if (top->num == num)
        {
            if (top == head)
            {
                head = head->next;
            }
            top->pre->next = top->next;
            top->next->pre = top->pre;
            free(top);
        }
        else if (tail->num == num)
        {
            tail->pre->next = tail->next;
            tail->next->pre = tail->pre;
            free(tail);
        }
        else
        {
            printf("没找到num, 删除失败!\n");
        }
        *p_head = head;
    }
}

释放双向链表

// 释放整个链表
void free_link(STU **p_head)
{
    STU *head = *p_head;
    if (NULL == head)
    {
        printf("link does not exits.\n");
    }
    else
    {
        STU *pn = head;
        do
        {
            head = head->next;
            printf("释放%d\n", pn->num);
            free(pn);
            pn = head;
        } while (pn != *p_head);
        
        *p_head = NULL;
        printf("链表释放成功!\n");
    }
}

标签：pb,13,head,next,链表,STU,num
From： https://www.cnblogs.com/mzx233/p/17679344.html

相关文章

  • 链表
    #include<iostream>usingnamespacestd;#defineMaxSize10typedefstruct{intdata[MaxSize];intlength;}Sqlist;voidListInsert(Sqlist&L,inti;inte){for(intj=L.length;j>=i;j--)L.data[j]=L.data[j-1];L.data[i-1]=e;......
  • 复习知识，学习单链表数组实现 （9/4）
    双指针经典题目800.数组元素的目标和给定两个升序排序的有序数组 AA 和 BB，以及一个目标值 xx。数组下标从 00 开始。请你求出满足 A[i]+B[j]=xA[i]+B[j]=x 的数对 (i,j)(i,j)。数据保证有唯一解。输入格式第一行包含三个整数 n,m,xn,m,x，分别表示 AA 的长度，BB......
  • 203. 移除链表元素
    前些日子在翻译论文，检查语法润色啥的。然后跟导师一起修改，前几天终于投了出去，现在可以回到正常的节奏上来了。先看看题吧给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val==val 的节点，并返回新的头节点 。示例1：输入：head=[1,2,6,3,4,5,6],va......
  • 13.mysql数据修改操作
    以下是一些MySQL数据修改操作示例，包括单表查询和多表查询，以及相应的示例数据表。单表修改操作：假设我们有一个名为employees的表，用于存储员工信息：CREATETABLEemployees(employee_idINTPRIMARYKEY,first_nameVARCHAR(255),last_nameVARCHAR(255),......
  • 【 LeetCode题解 】203. 移除链表元素
    【LeetCode题解】203.移除链表元素题目链接:https://leetcode.cn/problems/remove-linked-list-elements/博客主页链接：DuckBro博客主页关注博主，后期持续更新系列文章***感谢观看，希望对你有所帮助***目录【LeetCode题解】203.移除链表元素......
  • 一口气用Python写了13个小游戏（附源码）
    今天给大家分享13个游戏源码，可以自己复现玩玩，研究下里面的编程逻辑，对学习编程（特别是初学者）应该会有很大帮助。1、吃金币源码分享：importosimportcfgimportsysimportpygameimportrandomfrommodulesimport*'''游戏初始化'''definitGame():#初始化pygame,设......
  • Ziya-LLaMA-13B 模型在GPU 上部署
    Ziya-LLaMA-13B模型在GPU上部署Ziya-LLaMA-13B是IDEA-CCNL基于LLaMa的130亿参数的大规模预训练模型，具备翻译，编程，文本分类，信息抽取，摘要，文案生成，常识问答和数学计算等能力。目前姜子牙通用大模型已完成大规模预训练、多任务有监督微调和人类反馈学习三阶段的训练过程。1.部署准......
  • 侵入式链表学习
    在408和常见教材里面，以普通的尾指针点单链表为例，一个链表节点包含数据部分和尾指针。首个节点称为头节点，不包含数据，它的尾指针指向下一个节点（首个节点设计成存数据的也行）。每个节点依次连接，直到最后一个节点，尾指针设为null，表示链表结束。如果设计一个节点内有首尾两个指针，那就可......
  • 剑指 Offer 06. 从尾到头打印链表
    剑指Offer06.从尾到头打印链表方法一顺序添加，再翻转。classSolution{publicint[]reversePrint(ListNodehead){ListNodeh=head;List<Integer>res=newArrayList<>();while(h!=null){res.add(h.val);h=......
  • 链表
    链表当需要插入或删除数据结构中某些元素时，用链表比数组方便得多，访问某一元素时则链表就是个dd。(链表可以用来秀指针操作注意：链表中的每个元素在使用前都要申请一个空间（new）并指向NULL(->next=NULL)，即初始化操作由于链表不能访问某一元素，所以每次操作前都要从头开始（p=h......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99