首页 > 其他分享 >数据结构的练习day1

数据结构的练习day1

时间：2024-04-22 21:14:09浏览次数：21  
标签：Head copy 练习 结点 next 链表 LList 数据结构 day1

image

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

image

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

image

/********************************************************************************************************
 *
 *
 *
 *
 *
 *
 * Copyright (c)  2023-2024   [email protected]    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   [email protected]   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);
}

标签：Head,copy,练习,结点,next,链表,LList,数据结构,day1
From： https://www.cnblogs.com/DengJian111222/p/18151538

相关文章

  • 34.c语言数组练习题(牛客网)
    先打个广告哈哈哈牛客网练编程题不错不错哦冒泡排序必须必须必须会#include<stdio.h>voidsort(intarr[],intn){//外层循环for(inti=0;i<n-1;++i){intflag=1;//假设flag=1就是已经排序好的//内层循环for(intj=0;......
  • rhce练习题容易错的地方
    rhce练习题里容易错的地方使用导航器的时候，ssh连接因为导航器是一个工具，生成一个容器，在容器里面运行playbook安装软件包的时候，多个软件包使用循环looploop的格式-hosts:NODE1tasks:-name:installphpansible.builtin.yum:name:"{{ite......
  • 前端【uniapp】03-uniapp【练习项目 · 神领物流】
    uni-app（神领物流）项目实战学习目标：能够对Pinia进行初始化操作掌握创建Store及数据操作的步骤能够对Pinia数据进行持久化的处理掌握uniForm表单验证的使用方法能够根据业务需求配置请求/响应拦截器一、【神领物流】项目启动本节的主要任务是获取项......
  • 数据结构
    顺序表的特点物理存储上元素空间连续：顺序表在内存中占据一块连续的内存空间，便于通过下标快速访问元素。随机访问：由于元素连续存储，顺序表支持根据下标直接访问任意位置的元素，时间复杂度为O(1)。插入和删除操作可能涉及元素移动：在顺序表中插入或删除元素，可能需要移动大量元素以......
  • 数据结构笔试题 Day 1
    笔试题1已知一个顺序表L，其中的元素递增有序排列，设计一个算法，插入一个元素x(x为int型)后保持该顺序表仍然递增有序排列(假设插入操作总能成功)./递增排序12304055voidSeqList_Insert(SeqList*L,intx){inttemp=-1;//记录待插入元素的下标//遍历......
  • 持续性学习-Day15（前端基础CSS3）
    参考教学视频：秦疆1.什么是CSSCascadingStyleSheet层叠样式表CSS3圆角、阴影、动画...浏览器兼容性CSS优势：内容和表现分离网页结构表现统一，可以实现复用样式十分的丰富建议使用独立html的css文件利用SEO，容易被搜索引擎收录2.入门<linkrel="styleshee......
  • day19-并发编程（上）
    1.进程和线程先来了解下进程和线程。类比：一个工厂，至少有一个车间，一个车间中至少有一个工人，最终是工人在工作。一个程序，至少有一个进程，一个进程中至少有一个线程，最终是线程在工作。上述串行的代码示例就是一个程序，在使用pythonxx.py运行时，内部就创建一个进程（主进程），在进......
  • day18_我的Java学习笔记 (Logback日志框架、阶段项目--详见视频教程)
    1.日志框架1.1日志技术的概述1.2日志技术体系结构1.3Logback概述需要3个文件：1.4Logback快速入门1.4.1在项目下新建lib文件夹，导入Logback的相关jar包，并全选右键添加到项目依赖库中新建工程：logback-app将3个jar包拷贝到lib目录下全选，右键，选择......
  • day18-网络编程（下）
    1.OSI7层模型OSI的7层模型对于大家来说可能不太好理解，所以我们通过一个案例来讲解：假设，你在浏览器上输入了一些关键字，内部通过DNS找到对应的IP后，再发送数据时内部会做如下的事：应用层：规定数据的格式。"GET/s?wd=你好HTTP/1.1\r\nHost:www.baidu.com\r\n\r\n"表示层......
  • redis list数据结构操作学习
    转自：https://zhuanlan.zhihu.com/p/765785471.插入元素>rpushmylistA#从右侧插入(integer)1>rpushmylistB(integer)2>lpushmylistfirst(integer)3>lrangemylist0-1//这里使用0-1表示显示所有元素，注意是：0空格-1，0代表第一个元素，-1代表最后......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99