数据结构的练习day1
  mC4XcNdZWRiG 19天前 12 0

image

链表只能一个一个的遍历，不能通过随机访问来获取节点

image

链表的地址是不要求连续的，是通过内部的指针来进行联系的

image

/********************************************************************************************************
 *
 *
 *
 *
 *
 *
 * Copyright (c)  2023-2024      All right Reserved
 * ******************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
  DataType_t data;         // 结点的数据域
  struct LinkedList *next; // 结点的指针域

} LList_t;

// 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
LList_t *LList_Create(void)
{
  // 1.创建一个头结点并对头结点申请内存
  LList_t *Head = (LList_t *)calloc(1, sizeof(LList_t));
  if (NULL == Head)
  {
    perror("Calloc memory for Head is Failed");
    exit(-1);
  }

  // 2.对头结点进行初始化，头结点是不存储有效内容的！！！
  Head->next = NULL;

  // 3.把头结点的地址返回即可
  return Head;
}

// 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
LList_t *LList_NewNode(DataType_t data)
{
  // 1.创建一个新结点并对新结点申请内存
  LList_t *New = (LList_t *)calloc(1, sizeof(LList_t));
  if (NULL == New)
  {
    perror("Calloc memory for NewNode is Failed");
    return NULL;
  }

  // 2.对新结点的数据域和指针域进行初始化
  New->data = data;
  New->next = NULL;

  return New;
}

// 头插
bool LList_HeadInsert(LList_t *Head, DataType_t data)
{
  // 1.创建新的结点，并对新结点进行初始化
  LList_t *New = LList_NewNode(data);
  if (NULL == New)
  {
    printf("can not insert new node\n");
    return false;
  }

  // 2.判断链表是否为空，如果为空，则直接插入即可
  if (NULL == Head->next)
  {
    Head->next = New;
    return true;
  }

  // 3.如果链表为非空，则把新结点插入到链表的头部
  New->next = Head->next;
  Head->next = New;

  return true;
}

// 尾插
bool LList_TailInsert(LList_t *Head, DataType_t data)
{
  if (Head->next == NULL)
  {
    printf("链表尾空!\n");
    return false;
  }
  // 新建一个指针指向Head的next
  LList_t *copy_head = Head->next;
  // 创建一个新的节点
  LList_t *newNode = LList_NewNode(data);
  while (copy_head)
  {
    // 到了尾节点了
    if (copy_head->next == NULL)
    {
      // 尾插
      copy_head->next = newNode;
      // 退出循环
      break;
    }
    copy_head = copy_head->next;
  }
  return true;
}

// 插到目标节点的后面
bool LList_DestInsert(LList_t *Head, DataType_t dest, DataType_t data)
{
  if (Head->next == NULL)
  {
    printf("链表尾空!\n");
    return false;
  }
  // 新建一个指针指向Head的next
  LList_t *copy_head = Head->next;
  // 创建一个新的节点
  LList_t *newNode = LList_NewNode(data);
  while (copy_head)
  {
    // 找到了目标节点
    if (copy_head->data == dest)
    {
      // 指向目标节点的next
      newNode->next = copy_head->next;
      // 目标节点指向新节点
      copy_head->next = newNode;
      // 找到了，退出方法，放回true
      return true;
    }
    // 没找到,指针指向下个节点
    copy_head = copy_head->next;
  }
  // 没找到
  return false;
}

// 寻找链表的最小值
int Select_Min_Node(LList_t *Head)
{
  if (Head->next == NULL)
  {
    printf("链表尾空!\n");
    return -1;
  }
  // 新建一个指针指向Head的next
  LList_t *copy_head = Head->next;
  // 默认最小值是copy_head的data
  int min = copy_head->data;
  while (copy_head->next)
  {
    // 如果min大于下个节点的数值，min就发生交换
    if (min > copy_head->next->data)
    {
      min = copy_head->next->data;
    }
    // 进入下个节点
    copy_head = copy_head->next;
  }
  return min;
}

// 删除最小数据的节点
void DelectMinDataNode(LList_t *Head)
{
  if (Head->next == NULL)
  {
    printf("链表为空!\n");
    return;
  }
  // 新建一个指针指向Head的next
  LList_t *copy_head = Head;
  // 获取链表中的最小数据
  int delVal = Select_Min_Node(Head);
  while (copy_head->next)
  {
    if (copy_head->next->data == delVal)
    {
      // 创建一个指针保存要删除的节点的next
      LList_t *copy_del_next = copy_head->next->next;
      // 释放空间
      free(copy_head->next);
      // 指向要删除的节点的next
      copy_head->next = copy_del_next;
      // 退出循环
      break;
    }
    copy_head = copy_head->next;
  }
  return;
}

// 遍历
void LList_Print(LList_t *Head)
{
  // 对链表的头文件的地址进行备份
  LList_t *Phead = Head;

  // 首结点
  while (Phead->next)
  {
    // 把头的直接后继作为新的头结点
    Phead = Phead->next;

    // 输出头结点的直接后继的数据域
    printf("data = %d\n", Phead->data);
  }
}

int main(int argc, char const *argv[])
{
  // 创建链表头节点
  LList_t *Head = LList_Create();
  // 头插
  LList_HeadInsert(Head, 0);
  LList_HeadInsert(Head, 5);
  LList_HeadInsert(Head, 20);
  LList_HeadInsert(Head, 1);
  // 尾插
  LList_TailInsert(Head, 20);
  // 在目标后面插
  LList_DestInsert(Head, 5, 2);
  // 删除链表中数据最小的节点
  DelectMinDataNode(Head);
  // 遍历链表
  LList_Print(Head);
  return 0;
}

image

/********************************************************************************************************
 *
 *查找链表的倒数第k个节点的数据
 *思想: 可以根据链表的节点数-k来获取需要head的next的次数来获取节点
 *
 *
 *
 * Copyright (c)  2023-2024     All right Reserved
 * ******************************************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 指的是单向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct LinkedList
{
  DataType_t data;         // 结点的数据域
  struct LinkedList *next; // 结点的指针域

} LList_t;

// 创建一个空链表，空链表应该有一个头结点，对链表进行初始化
LList_t *LList_Create(void)
{
  // 1.创建一个头结点并对头结点申请内存
  LList_t *Head = (LList_t *)calloc(1, sizeof(LList_t));
  if (NULL == Head)
  {
    perror("Calloc memory for Head is Failed");
    exit(-1);
  }

  // 2.对头结点进行初始化，头结点是不存储有效内容的！！！
  Head->next = NULL;

  // 3.把头结点的地址返回即可
  return Head;
}

// 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
LList_t *LList_NewNode(DataType_t data)
{
  // 1.创建一个新结点并对新结点申请内存
  LList_t *New = (LList_t *)calloc(1, sizeof(LList_t));
  if (NULL == New)
  {
    perror("Calloc memory for NewNode is Failed");
    return NULL;
  }

  // 2.对新结点的数据域和指针域进行初始化
  New->data = data;
  New->next = NULL;

  return New;
}

// 头插
bool LList_HeadInsert(LList_t *Head, DataType_t data)
{
  // 1.创建新的结点，并对新结点进行初始化
  LList_t *New = LList_NewNode(data);
  if (NULL == New)
  {
    printf("can not insert new node\n");
    return false;
  }

  // 2.判断链表是否为空，如果为空，则直接插入即可
  if (NULL == Head->next)
  {
    Head->next = New;
    return true;
  }

  // 3.如果链表为非空，则把新结点插入到链表的头部
  New->next = Head->next;
  Head->next = New;

  return true;
}

// 遍历
void LList_Print(LList_t *Head)
{
  // 对链表的头文件的地址进行备份
  LList_t *Phead = Head;

  // 首结点
  while (Phead->next)
  {
    // 把头的直接后继作为新的头结点
    Phead = Phead->next;

    // 输出头结点的直接后继的数据域
    printf("data = %d\n", Phead->data);
  }
}
/********************************************************************************************************
 *
 * 查找链表中倒数第k个位置上的节点
 * ①先遍历链表记录链表的节点数
 * ②然后通过for循环链表来获取到链表中倒数第k个位置上的节点，并且返回其data
 * ③找到返回1，没找到返回0
 *
 *
 *
 * ******************************************************************************************************/
int SelectRecNode(LList_t *Head, DataType_t k)
{
  if (Head->next == NULL)
  {
    printf("链表为空!\n");
    return 0;
  }
  // 新建一个指针指向Head的next
  LList_t *copy_head = Head->next;
  // 记录其节点数
  int count = 0;
  // 通过while循环记录链表的节点数
  while (copy_head)
  {
    count++;
    copy_head = copy_head->next;
  }
  // 把copy_head重新指向Head的next
  copy_head = Head->next;
  // 通过节点数-k就是其节点在链表中的位置
  for (int i = 0; i < count - k; i++)
  {
    copy_head = copy_head->next;
  }
  printf("链表中倒数第%d个节点的数值是%d\n", k, copy_head->data);
  return 1;
}

int main()
{
  // 创建链表头节点
  LList_t *Head = LList_Create();
  // 头插
  LList_HeadInsert(Head, 1);
  LList_HeadInsert(Head, 2);
  LList_HeadInsert(Head, 3);
  LList_HeadInsert(Head, 4);
  LList_HeadInsert(Head, 5);
  LList_HeadInsert(Head, 6);
  LList_Print(Head);
  SelectRecNode(Head, 3);
}
【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载，内容版权归原作者所有。本网站的目的在于传递更多信息，不拥有版权，亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@moduyun.com
  1. 分享：
最后一次编辑于 19天前 0

暂无评论

推荐阅读
  VExS4Gg6g4KD   4天前   17   0   0 Linux
  UxvP3mLKJea9   4天前   15   0   0 Linux
  VExS4Gg6g4KD   4天前   12   0   0 Linux
  VExS4Gg6g4KD   4天前   18   0   0 Linux
  FJCVMCRMBw1f   4天前   14   0   0 Linux
  UxvP3mLKJea9   4天前   16   0   0 Linux
  YAWVsSrNsMIu   8天前   19   0   0 Linux
  X6z51Yzaj35p   4天前   13   0   0 Linux
  TYxRZSWk5DoI   8天前   23   0   0 Linux
  jEmNNF9D14iz   4天前   14   0   0 Linux
  T0lscH4Qgx5j   9天前   20   0   0 Linux
  u05qsPMWcUGd   9天前   22   0   0 Linux
  twB1ElkuRPCE   10天前   19   0   0 Linux
  VExS4Gg6g4KD   4天前   13   0   0 Linux
  j9WMFjfGMH91   4天前   12   0   0 Linux
  iNBin04WVNys   4天前   11   0   0 Linux
  QP84hQv41ZIv   4天前   12   0   0 Linux
  Sn6PyjtOLQui   9天前   22   0   0 Linux
  kZLEadpmxZsY   11天前   21   0   0 Linux
  cd70gs8BACeR   7天前   29   0   0 Linux
mC4XcNdZWRiG
mC4XcNdZWRiG
作者其他文章 更多
数据结构的练习day2(未完待续)

2024-04-24

数据结构的练习day1

2024-04-23

最新推荐 更多
冒泡排序

2024-05-08

知识扩展--FAT32 与 NTFS 的区别

2024-05-08

文件IO

2024-05-08

Linux常用命令

2024-05-08

linux安装fastdfs

2024-05-08

【Liunx】Docker安装

2024-05-08

安装 Ubuntu

2024-05-08

NTP/SSH 服务器

2024-05-08

DNS/DHCP 服务器

2024-05-08

Linux基础-02：Linux目录操作命令

2024-05-08

容器平台

2024-05-08

知识扩展--- MMU 将虚拟地址转换为物理地址

2024-05-08

文件IO

2024-05-08

Linux基础03-Linux文件操作命令

2024-05-08

hexo 博客插入本地图片时遇到的坑

2024-05-08

一篇教程搞定Windows系统中的Docker应用安装

2024-05-08

ubuntu_24.04 Noble LTS安装docker desktop启动无窗口及引擎启动失败的解决方法

2024-05-05

进程间通信

2024-05-04

VMware虚拟机安装Centos-7.9

2024-05-04

openstack完整的部署（最详细）

2024-05-04

常用标签
数据数据数据数据javalinuxlinuxpythonCentOSredisJava区块链技术python区块链信息系统字符串MySQL资讯项目管理mysql教程MySQL