C语言-链表_基础

news/2024/7/24 11:34:35 标签: c语言, 链表

链表-基础

1. 数组

1.1 静态数组

例子:
    int nums[5] = {0};
    struct person ps[5];
缺点:
    1,无法修改地址
    2,无法动态定义长度
    3,占用内存过大或过小
    4,增删速度慢
优点
	数组的内存是连续开辟的,所以读取速度快

1.2 动态数组

例子:
    int *nums = (int *) calloc(5,sizeof(int));
    struct person *ps = (struct person *)calloc(5,sizeof(struct person));
缺点:
    增删速度慢
    编写代码较为复杂
优点:
	读取效率高

2. 常用数据结构

1、数组结构:内存连续开辟

2、链表结构:离散开辟

3、树

4、二叉树(均衡二叉树,非均衡二叉树)

5、图

3. 链表结构

分类：

单链表：

  • 一个节点只记录下一个节点的地址

双链表：

  • 一个节点即记录下一个节点的地址，也记录上一个节点的地址

4. 设计节点

需求：将多个学员信息设计为链表

单链表节点设计：

typedef struct student
{
	//数据域
	char name[50];
	char sex[5];
	int num;
	double score;
	
	//指针域
	struct student *next;
}Stu;

双链表节点设计：

typedef truct student
{
	//数据域
	char name[50];
	char sex[5];
	int num;
	double score;
	
	//指针域
	struct student *next;
	struct student *head;
}Stu;

总结：

typedef struct 结构体名称
{
	//数据域
	//指针域
}别名;

5. 静态单链表

#include <stdio.h>
typedef struct student
{
    //数据域
	char name[50];
	char sex[5];
	int num;
	double score;
	
	//指针域
	struct student *next;
}Stu;
int main(int argc, char const *argv[])
{
    Stu s01 = {"张三", "男", 1, 99, NULL};
    Stu s02 = {"李四", "男", 2, 96, NULL};
    Stu s03 = {"王五", "女", 3, 97, NULL};
    Stu s04 = {"钱七", "男", 4, 93, NULL};
    Stu s05 = {"赵八", "女", 5, 97, NULL};

    Stu *head = &s01;   //将s01作为首节点
    s01.next = &s02;    //将s02设置为s01的下一个节点   
    s02.next = &s03;
    s03.next = &s04;
    s04.next = &s05;

    //链表的遍历
    //pd:当前链表的节点
    Stu *pd = head;
    while(pd != NULL)
    {
        printf("%s %s %d %.2lf\n", pd->name, pd->sex, pd->num, pd->score);
        //下一个节点赋值给当前节点，为下一轮循环
        pd = pd->next;
    }
    return 0;
}

6. 动态单链表

动态开辟内存，存储结构体学生信息

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student
{
    //数据域
	char name[50];
	char sex[5];
	int age;
	
	//指针域
	struct student *next;
}Stu;
int main(int argc, char const *argv[])
{
    Stu *s01 = calloc(1,sizeof(Stu));
    strcpy(s01->name, "陈晴朗");
    strcpy(s01->sex, "男");
    s01->age = 18;
    Stu *s02 = calloc(1,sizeof(Stu));
    strcpy(s02->name, "李槐");
    strcpy(s02->sex, "男");
    s02->age = 8;
    Stu *s03 = calloc(1,sizeof(Stu));
    strcpy(s03->name, "李宝瓶");
    strcpy(s03->sex, "女");
    s03->age = 14;
    Stu *s04 = calloc(1,sizeof(Stu));
    strcpy(s04->name, "裴钱");
    strcpy(s04->sex, "女");
    s04->age = 12;
    Stu *s05 = calloc(1,sizeof(Stu));
    strcpy(s05->name, "崔东山");
    strcpy(s05->sex, "男");
    s05->age = 16;

    Stu *head = s01;   //将s01作为首节点
    s01->next = s02;    //将s02设置为s01的下一个节点   
    s02->next = s03;
    s03->next = s04;
    s04->next = s05;

    //链表的遍历
    //pd:当前链表的节点
    Stu *pd = head;
    while(pd != NULL)
    {
        printf("%s\t%s\t%d\n", pd->name, pd->sex, pd->age);
        //下一个节点赋值给当前节点，为下一轮循环
        pd = pd->next;
    }
    return 0;
}
// 陈晴朗  男      18
// 李槐    男      8
// 李宝瓶  女      14
// 裴钱    女      12
// 崔东山  男      16

练习：学员管理系统

需求：

选项有:
    1,查询所有学员信息
    2,添加学员信息
    3,插入学员信息
    4,删除学员信息
    5,修改学员信息(作业)
    6,查找指定位置的学员(作业)
    7,退出程序(释放内存)

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student
{
    //数据域
    char name[30];
    char sex[10];
    int num;
    //指针域
    struct student *next;
}STU;
//记录链表首节点
STU *head = NULL;

//查询函数(打印链表)
void print_link(STU *head)
{
    //定义一个节点作为当前节点
    STU *pd = head;
    while (pd != NULL)
    {
        printf("姓名:%s\t性别:%s\t学号:%d\n",pd->name,pd->sex,pd->num);
        //获取下一个节点赋值给当前节点
        pd = pd->next;
    }
    printf("\n");
}

//计算链表长度
int get_len(STU *head)
{
    int i = 0;
    STU *pd = head;
    while(pd != NULL)
    {
        i++;
        pd = pd->next;
    }
    return i;
}

//添加学员信息逻辑
/*
    添加新节点到连接尾部
    参数;
        head:链表的头节点
        stu:要添加的新节点
    返回值
        链表的头节点
*/
STU *add(STU *head, STU *stu)
{
    //如果传进来的学员信息为空，直接返回传进来的头结点
    if (stu == NULL)
    {
        return head;
    }

    //判断链表首节点是否为空,为空表示此时链表还没有节点，直接将数据赋值给首结点
    if (head == NULL)
    {
        head = stu;
        printf("添加成功\n\n");
        return head;
    }

    //查询最后一个节点，找到NULL的前一个节点
    //假设当前节点就是最后一个节点(即一个也没有)，此时首节点就是最后一个节点
    STU *lastNode = head;
    while(lastNode != NULL)
    {
        //进循环，表示这不是最后一个节点，就判断他的下一个节点是否为空，为空直接跳出循环
        if (lastNode->next == NULL)
        {
            break;
        }
        else
        {
            //此时表示他的下一个节点不是NULL，将它的下一个节点赋值给它
            lastNode = lastNode->next;
        }
    }
    //没有进循环表示lastNode就是当前链表的最后一个节点
    //此时就要将本次创建的节点添加到 原链表最后一个节点的后面
    lastNode->next = stu;
    printf("添加成功\n\n");
    return head;
}

//尾部添加学员信息
STU *add_student(STU *head)
{
    //开辟一块堆内存空间赋值 结构体指针变量，用来存储学员信息(即stu指向这片堆内存)
    STU *stu = calloc(1,sizeof(STU));
    printf("请输入学员姓名\n");
    scanf("%s", stu->name);
    printf("请输入学员性别\n");
    scanf("%s", stu->sex);
    printf("请输入学员学号\n");
    scanf("%d", &stu->num);
    head = add(head, stu);
    return head;

}

//插入学员
STU *inster_student(STU *head)
{
    STU *stu = calloc(1,sizeof(STU));
    printf("请输入学员姓名\n");
    scanf("%s", stu->name);
    printf("请输入学员性别\n");
    scanf("%s", stu->sex);
    printf("请输入学员学号\n");
    scanf("%d", &stu->num);

    printf("请输入要插入学员的位置(从0开始)\n");
    int index = 0;
    scanf("%d", &index);

    //排除错误
    int len = get_len(head);
    if (index > len)
    {
        //插入位置超过链表长度，插入链表末位
        head = add(head, stu);
        return head;
    }

    if (index < 0)
    {
        printf("输入位置有误\n");
        return head;
    }
    //为0表示插入第一个位置
    if (index == 0)
    {
        //将首节点位置变为下一个节点
        stu->next = head;
        //将新建的节点赋值给首节点
        head = stu;
        printf("添加成功\n");
        return head;
    }

    //寻找插入节点的前一个节点
    STU *pd = head;
    for (int i = 0; i < index - 1; i++)
    {
        pd = pd->next;
    }
    stu->next = pd->next; //将前一个节点的原后一个节点赋值给新节点的下一个节点
    pd->next = stu;
    printf("添加成功\n\n");
    return head;
}

//删除学员
STU *del_student(STU *head)
{
    printf("请输入要删除学员的位置(从0开始)\n");
    int index = 0;
    scanf("%d", &index);

    //排除错误
    int len = get_len(head);
    if (index > len || index < 0)
    {
        printf("输入位置有误\n");
        return head;
    }

    //为0表示删除第一个位置
    if (index == 0)
    {
        //将首节点的下一个节点变为首节点
        head = head->next;
        printf("删除成功\n");
        return head;
    }

    STU *pd1 = head, *pd2;
    int i = 0;
    while (i < index)
    {
        pd2 = pd1;
        pd1 = pd1->next;
        i++;
    }
    if (pd1 != NULL)
    {
        pd2->next = pd1->next;
    }
    printf("删除成功\n");
    return head;
}

//修改学员
STU *update_student(STU *head)
{
    STU *stu = calloc(1,sizeof(STU));
    printf("请输入要修改学员姓名\n");
    scanf("%s", stu->name);
    printf("请输入要修改学员性别\n");
    scanf("%s", stu->sex);
    printf("请输入要修改学员学号\n");
    scanf("%d", &stu->num);
    
    printf("请输入要修改学员的位置(从0开始)\n");
    int index = 0;
    scanf("%d", &index);
    //排除错误
    int len = get_len(head);
    if (index > len || index < 0)
    {
        printf("输入位置有误\n");
        return head;
    }

    //为0表示修改第一个位置
    if (index == 0)
    {
        //将新节点的next指向原首节点的下一个节点
        stu->next = head->next;
        printf("修改成功\n");
        return head;
    }
    //不为0
    int i = 0;
    //定义两个指针变量记录当前节点和上一个节点
    STU *pd1 = head, *pd2;
    while (i < index)
    {
        pd2 = pd1;
        pd1 = pd1->next;
        i++;
    }
    pd2->next = stu;
    stu->next = pd1->next;
    printf("修改成功\n");
    return head;
}

//查询指定学员位置
STU *find_student(STU *head)
{
    printf("请输入要查找学员的位置(从0开始)\n");
    int index = 0;
    scanf("%d", &index);
    //排除错误
    int len = get_len(head);
    if (index > len || index < 0)
    {
        printf("输入位置有误\n");
        return head;
    }

    STU *pd = head, *pd1;
    //为0表示查找的是第一个学员
    if (index == 0)
    {
        //直接打印首节点
        printf("姓名:%s\t性别:%s\t学号:%d\n\n",pd->name,pd->sex,pd->num);
        return head;
    }
    //不为0，寻找当前节点
    int i = 0;
    while (i < index)
    {
        pd1 = pd;
        pd = pd->next;
        i++;
    }
    printf("姓名:%s\t性别:%s\t学号:%d\n\n",pd->name,pd->sex,pd->num);
    return head;
}

//菜单函数
void my_menu(int tag)
{
    switch (tag)
    {
    case 1:
        print_link(head);
        break;
    case 2:
        head = add_student(head);
        break;
    case 3:
        head = inster_student(head);
        break;
    case 4:
        head = del_student(head);
        break;
    case 5:
        head = update_student(head);
        break;
    case 6:
        head = find_student(head);
        break;
    default:
        printf("输入有误, 请重新输入\n\n");
        break;
    }
}

//释放内存
void free_link(STU *head)
{
    STU *pd = head;
    while (pd != NULL)
    {
        //记录其下一个节点
        STU *next = pd->next;
        //释放当前节点
        free(pd);
        //更换当前节点
        pd = next;
    }
    
}

int main(int argc, char const *argv[])
{
    while (1)
    {
        printf("1,查询所有学员信息\n2,添加学员信息\n3,插入学员信息\n4,删除学员信息\n5,修改学员信息\n6,查找指定位置的学员\n7,退出程序\n\n");
        printf("请输入本次操作的选项（输入对应数字）\n");
        int tag = 0;
        scanf("%d", &tag);
        if (tag != 7)
        {
            my_menu(tag);
        }
        else
        {
            free_link(head);
            printf("欢迎下次光临!\n");
            break;
        }
    }
    return 0;
}

http://www.niftyadmin.cn/n/5254708.html

相关文章

数据结构之----逻辑结构、物理结构

数据结构之----逻辑结构、物理结构

数据结构之----逻辑结构、物理结构 目前我们常见的数据结构分别有&#xff1a; 数组、链表、栈、队列、哈希表、树、堆、图 而它们可以从 逻辑结构和物理结构两个维度进行分类。 什么是逻辑结构&#xff1f; 逻辑结构是指数据元素之间的逻辑关系&#xff0c;而逻辑结构又分为…
阅读更多...
Vue项目中WebSocket封装

Vue项目中WebSocket封装

WEBSOCKET 封装引入初始化使用 封装 utils下建立WebSocketManager.js class WebSocketManager {constructor() {this.url null;this.websocket null;this.isConnected false;this.listeners {onopen: [],onmessage: [],onclose: [],onerror: [],};this.reconnectionOptio…
阅读更多...
C语言 害死人不偿命的（3n+1)算法 挖掘机技术哪家强 选择排序 贪心算法

C语言 害死人不偿命的（3n+1)算法 挖掘机技术哪家强 选择排序 贪心算法

1.害死人不偿命的&#xff08;3n1)算法 卡拉兹( Calatz)猜想: 对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n1。卡拉兹在1950年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员…
阅读更多...
〖Python网络爬虫实战㊷〗- 极验滑块介绍（四）

〖Python网络爬虫实战㊷〗- 极验滑块介绍（四）

订阅&#xff1a;新手可以订阅我的其他专栏。免费阶段订阅量1000 python项目实战 Python编程基础教程系列&#xff08;零基础小白搬砖逆袭) 说明&#xff1a;本专栏持续更新中&#xff0c;订阅本专栏前必读关于专栏〖Python网络爬虫实战〗转为付费专栏的订阅说明作者&#xff1…
阅读更多...
内网穿透的应用-如何结合Cpolar内网穿透工具实现在IDEA中远程访问家里或者公司的数据库

内网穿透的应用-如何结合Cpolar内网穿透工具实现在IDEA中远程访问家里或者公司的数据库

文章目录 1. 本地连接测试2. Windows安装Cpolar3. 配置Mysql公网地址4. IDEA远程连接Mysql小结 5. 固定连接公网地址6. 固定地址连接测试 IDEA作为Java开发最主力的工具&#xff0c;在开发过程中需要经常用到数据库&#xff0c;如Mysql数据库&#xff0c;但是在IDEA中只能连接本…
阅读更多...
吴恩达深度学习L2W3作业

吴恩达深度学习L2W3作业

欢迎来到本周的编程作业。 到目前为止&#xff0c;你一直使用numpy来构建神经网络。现在&#xff0c;我们将引导你使用深度学习框架&#xff0c;该框架将使你可以更轻松地构建神经网络。TensorFlow&#xff0c;PaddlePaddle&#xff0c;Torch&#xff0c;Caffe&#xff0c;Kera…
阅读更多...
企业如何选择合适的信息化管理系统？

企业如何选择合适的信息化管理系统？

一、什么是信息化管理系统 信息化这个词在近年已经被说烂了&#xff0c;在信息化快速发展的时代&#xff0c;越来越多的企业开始意识到信息化管理系统的重要性。信息化管理系统是指一种能够帮助企业或组织有效管理信息资源&#xff0c;提高信息的可靠性、安全性和有效性的软件…
阅读更多...
docker创建镜像 Dockerfile

docker创建镜像 Dockerfile

创建镜像&#xff0c;创建自定义的镜像 包括配置文件&#xff0c;挂载点&#xff0c;对外暴露的端口&#xff0c;设置环境变量 docker的创建镜像的方式 1、基于已有的镜像进行创建&#xff0c;根据官方提供的镜像源&#xff0c;创建镜像&#xff0c;然后拉起容器&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023