程序员经验分享-hwhale

数据结构: 线性表(带头双向循环链表实现)

2023-10-29


之前一章学习了单链表的相关操作, 但是单链表的限制却很多, 比如不能倒序扫描链表, 解决方法是在数据结构上附加一个域, 使它包含指向前一个单元的指针即可.

那么怎么定义数据结构呢? 首先我们先了解以下链表的分类

1. 链表的分类

链表的结构非常多样, 以下情况组合起来就有 8 中链表结构

  • 单向或者双向
    在这里插入图片描述

  • 带头或者不带头
    在这里插入图片描述

  • 循环或者非循环
    在这里插入图片描述

虽然有这么多的链表的结构, 但是我们实际上最常用的还是两种结构:

在这里插入图片描述

无头单向非循环链表

结构简单,一般不会单独用来存放数据.实际上更多是作为其他数据结构的子结构, 如哈希桶, 图的邻接表等等. 另外这种结构在笔试面试中出现很多

带头双向循环链表

结构最复杂, 一般用于单独存储数据.实际上使用的链表数据结构, 都是带头双向循环链表. 虽然结构复杂, 但是实现相关功能比较简单.

严格来说只用实现 Insert 和 Erase 两个功能, 就可以实现 “二十分钟” 写完一个链表的任务.

2. 带头双向循环链表

2.1 带头双向循环链表的定义

typedef int LTDataType;     //LTDataType = int
typedef struct ListNode
{
  LTDataType data;          //数据域
  struct ListNode* prev;    //指向前一个结点
  struct ListNode* next;    //指向后一个结点
}ListNode;  //重命名为 ListNode
  1. 相比较单链表的数据结构, 只需要多一个域用来指向前面一个结点就可以了.
  2. 这里使用ListNode来命名这个数据结构, 方便后续学习 STL 进行知识迁移

2.2 接口函数

// 创建并返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestroy(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos);

3. 接口函数的实现

因为有虚拟结点的存在, 所以除了创建头结点的函数, 其余接口函数都不会修改结构体指针, 只是修改结构体.

为了统一接口形式, 统一使用一级指针作为函数的形参类型. 需要修改头结点的函数接口, 直接用返回值的方法达到修改头结点指针的目的.

3.1 创建并返回链表的头结点 (ListCreate)

在这里插入图片描述

创建链表即为创建头结点, 它是一个虚拟结点(dummy node), 实际的值没有意义.它的两个指针都指向自己.

  • ListList.h
#pragma once 

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

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;        //数据域
  struct ListNode* prev;  //指向前一个结点
  struct ListNode* next;  //指向后一个结点
}ListNode;

// 创建并返回链表的头结点
ListNode* ListCreate();

修改头结点指针, 使用返回值接受头结点的指针

  • ListList.c
// 创建返回链表的头结点
ListNode* ListCreate()
{
  // 动态开辟空间创建头结点, 如果开辟失败直接结束程序
  ListNode* head = BuyListNode(0);
  
  // 处理链表数据, 数据域随机值, 两个指针指向自己
  head->next = head;
  head->prev = head;

  return head;
}
  1. 这里的 BuyListNode() 是一个我自己定义的静态函数, 方便后续复用. 函数的功能是用来从堆中申请空间用来创建一个新结点.
// 创建一个新结点
static ListNode* BuyListNode(LTDataType x)
{
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  newNode->data = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}
  1. 创建头结点后, 使头结点指向自己
  • test.c
void LinkListTest1()
{
  ListNode* head = ListCreate();

  free(head);
}

测试调试结果如下:
在这里插入图片描述

头结点创建成功, 并且头结点两个指针都指向了自己

3.2 双向链表打印 (ListPrint)

从第一个结点开始遍历链表每个结点, 并且将结点的数据域打印出来, 直到遇到头结点结束
在这里插入图片描述

  • ListList.h
void ListPrint(ListNode* phead);
  • ListList.c
// 双向链表打印
void ListPrint(ListNode* phead)
{
  assert(phead);  //确保头结点存在

  printf("head <=> ");

  ListNode* cur = phead->next;  //从第一个结点开始遍历, 直到遇到头结点结束
  while (cur != phead)
  {
    printf("%d <=> ", cur->data);
    cur = cur->next;
  }

  printf("\n");
}
  1. 确保头结点存在
  1. cur第一次定位到头结点后面一个结点, 即第一个有效结点
  1. 顺序遍历并且打印
  • test.c

后续调试其他函数功能都会使用到 ListPrint 函数, 这里就先不调试了.

3.3 双向链表尾插 (ListPushBack)

先找到链表尾结点的位置, 在尾结点和头结点之间插入一个新结点

在这里插入图片描述

  • ListList.h
void ListPushBack(ListNode* phead, LTDataType x);
  • ListList.c
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保头结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点 
  ListNode* tail = phead->prev;       //找到尾结点
  
  //更改链接关系
  tail->next = newNode;
  newNode->prev = tail;
  phead->prev = newNode;
  newNode->next = phead;

}
  1. 确保头结点存在
  1. 更改链接关系, 需要修改一共四根指针的指向关系
  • test.c
void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);
}

测试结果如下:
在这里插入图片描述

3.4 双向链表尾删 (ListPopBack)

找到新的尾结点位置, 更改链接关系后将原尾结点删除
在这里插入图片描述

  • ListList.h
void ListPopBack(ListNode* phead);
  • ListList.c
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);                    //确保头结点存在
  assert(phead->next != phead);     //确保有结点可删

  ListNode* tail = phead->prev;     //找到要删除的尾结点
  ListNode* tailPrev = tail->prev;  //找到新的尾结点

  //更改链接关系
  tailPrev->next = phead;
  phead->prev = tailPrev;

  free(tail); //释放空间
}
  • test.c
void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPopBack(head);
  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPrint(head);
  
  ListDestroy(head);
}

测试结果如下:
在这里插入图片描述

3.5 双链表头插 (ListPushFront)

找到原第一个有效节点, 在头结点和这个结点之间插入一个新结点
在这里插入图片描述

  • ListList.h
void ListPushFront(ListNode* phead, LTDataType x);
  • ListList.c
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保头结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* first = phead->next;      //找到原来的第一个结点

  //更新链接关系
  phead->next = newNode;
  newNode->prev = phead;
  newNode->next = first;
  first->prev = newNode;
}
  1. 确保头结点存在
  1. 在头结点和第一个有效结点之间插入新结点
  • test.c
void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);
}

测试运行结果如下:
在这里插入图片描述

3.6 双链表头删 (ListPopFront)

先找到第一个和第二个有效结点, 更新头结点和第二个有效结点之间的链接关系后, 释放第一个结点的空间.
在这里插入图片描述

  • ListList.h
void ListPopFront(ListNode* phead);
  • ListList.c
// 双向链表头删
void ListPopFront(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在
  assert(phead->next != phead); //确保链表不为空

  ListNode* first = phead->next;  //找到头结点位置
  ListNode* second = first->next; //找到头结点后一个结点的位置

  //更新链接关系
  phead->next = second;
  second->prev = phead;

  free(first); //释放空间
}
  • test.c
void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);

  ListPrint(head);
  
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPrint(head);

  ListDestroy(head);
}

测试结果如下:
在这里插入图片描述

3.7 双链表查找 (ListFind)

从第一个有效结点开始向后遍历链表, 判断是否有想要查找的数据, 直到遇到头结点. 未查找到返回空指针, 查找到返回该结点的地址
在这里插入图片描述

  • ListList.h
ListNode* ListFind(ListNode* phead, LTDataType x);
  • ListList.c
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }

  return NULL;
}
  • test.c
void LinkListTest3()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;
  pos = ListFind(head, 2);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");

  pos = ListFind(head, 6);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");
}

测试运行结果如下:
在这里插入图片描述

3.8 双向链表在 pos 的前面进行插入 (LinkInsert)

先找到 pos 的前面一个结点的位置, 随后在这个结点和 pos 之间插入新结点
在这里插入图片描述

  • LinkList.h
void ListInsert(ListNode* pos, LTDataType x);
  • LinkList.c
// 双向链表在 pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);  //确保pos合法

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* posPrev = pos->prev;      //找到 pos 前一个结点的位置

  //更新链接方式
  posPrev->next = newNode;
  newNode->prev = posPrev;

  newNode->next = pos;
  pos->prev = newNode;
}
  • test.c
void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListInsert(pos, -1);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListInsert(pos, -4);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListInsert(pos, -6);
    ListPrint(head);
  }

  ListDestroy(head);
}

测试运行结果如下:
在这里插入图片描述

3.9 双向链表删除 pos 位置的结点 (ListErase)

先找到 pos 的前后两个结点的位置, 随后更新两个结点之间的链接关系, 最后删除 pos 结点
在这里插入图片描述

  • LinkList.h
void ListErase(ListNode* pos);
  • LinkList.c
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos)
{
  assert(pos);  //确保 pos 合法

  ListNode* posPrev = pos->prev;    //找到 pos 前一个结点的位置
  ListNode* posNext = pos->next;    //找到 pos 后一个结点的位置

  //更新链接方式
  posPrev->next = posNext;
  posNext->prev = posPrev;

  free(pos);  //释放空间
}
  • test.c
void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  ListDestroy(head);
}

测试运行结果如下:
在这里插入图片描述

3.10 双向链表销毁 (ListDestroy)

  • LinkList.h
void ListDestroy(ListNode* phead);
  • LinkList.c
// 双向链表销毁
void ListDestroy(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    ListNode* nextNode = cur->next;
    free(cur);
    cur = nextNode;
  }
  free(phead);
}

4. 总结

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续,但物理上不一定连续
随机访问 支持: O ( 1 ) O(1) O(1) 不支持: O ( N ) O(N) O(N)
任意位置插入或者删除元素 可能需要搬移元素, 效率低 O ( N ) O(N) O(N) 只需要修改指针指向
插入 动态顺序表, 空间不够时, 需要扩容 没有容量的概念
应用场景 元素高效存储 + 频繁访问 任意位置插入和删除频繁
缓存利用率 高 低

5. 完整代码

  • LinkList.h
#pragma once 

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

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;        //数据域
  struct ListNode* prev;  //指向前一个结点
  struct ListNode* next;  //指向后一个结点
}ListNode;

// 创建并返回链表的头结点
ListNode* ListCreate();
// 双向链表销毁
void ListDestroy(ListNode* phead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在 pos 的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos);
  • LinkList.c
#include "LinkList.h"

// 创建一个新结点
static ListNode* BuyListNode(LTDataType x)
{
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  newNode->data = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}

// 创建返回链表的头结点
ListNode* ListCreate()
{
  // 动态开辟空间创建头结点, 如果开辟失败直接结束程序
  ListNode* head = BuyListNode(0);
  
  // 处理链表数据, 数据域随机值, 两个指针指向自己
  head->next = head;
  head->prev = head;

  return head;
}

// 双向链表打印
void ListPrint(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在

  printf("head <=> ");

  ListNode* cur = phead->next;  //从头结点开始遍历, 直到遇到哨兵结点结束
  while (cur != phead)
  {
    printf("%d <=> ", cur->data);
    cur = cur->next;
  }

  printf("\n");
}

// 双向链表销毁
void ListDestroy(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    ListNode* nextNode = cur->next;
    free(cur);
    cur = nextNode;
  }
  free(phead);
}

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点 
  ListNode* tail = phead->prev;       //找到尾结点
  
  //更改链接关系
  tail->next = newNode;
  newNode->prev = tail;
  phead->prev = newNode;
  newNode->next = phead;

}

// 双向链表尾删
void ListPopBack(ListNode* phead)
{
  assert(phead);                    //确保哨兵结点存在
  assert(phead->next != phead);     //确保有结点可删

  ListNode* tail = phead->prev;     //找到要删除的尾结点
  ListNode* tailPrev = tail->prev;  //找到新的尾结点

  //更改链接关系
  tailPrev->next = phead;
  phead->prev = tailPrev;

  free(tail); //释放空间
}

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* first = phead->next;      //找到原来的头结点

  //更新链接关系
  phead->next = newNode;
  newNode->prev = phead;
  newNode->next = first;
  first->prev = newNode;

}

// 双向链表头删
void ListPopFront(ListNode* phead)
{
  assert(phead);  //确保哨兵结点存在
  assert(phead->next != phead); //确保链表不为空

  ListNode* first = phead->next;  //找到头结点位置
  ListNode* second = first->next; //找到头结点后一个结点的位置

  //更新链接关系
  phead->next = second;
  second->prev = phead;

  free(first); //释放空间
}

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);  //确保哨兵结点存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }

  return NULL;
}

// 双向链表在 pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);  //确保pos合法

  ListNode* newNode = BuyListNode(x); //创建新结点
  ListNode* posPrev = pos->prev;      //找到 pos 前一个结点的位置

  //更新链接方式
  posPrev->next = newNode;
  newNode->prev = posPrev;

  newNode->next = pos;
  pos->prev = newNode;
}
// 双向链表删除 pos 位置的结点
void ListErase(ListNode* pos)
{
  assert(pos);  //确保 pos 合法

  ListNode* posPrev = pos->prev;    //找到 pos 前一个结点的位置
  ListNode* posNext = pos->next;    //找到 pos 后一个结点的位置

  //更新链接方式
  posPrev->next = posNext;
  posNext->prev = posPrev;

  free(pos);  //释放空间
}
  • test.c
#include "LinkList.h"

void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPopBack(head);
  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPrint(head);
  
  ListDestroy(head);
}

void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);

  ListPrint(head);
  
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPrint(head);

  ListDestroy(head);
}

void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  ListInsert(pos, 0);
  ListErase(pos);
  ListPrint(head);

  pos = ListFind(head, 4);
  ListInsert(pos, 10);
  ListPrint(head);

  pos = ListFind(head, 11);
  ListInsert(pos, 12);
  ListPrint(head);

  ListDestroy(head);
}

void LinkListTest4()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);

  ListNode* pos;

  pos = ListFind(head, 2);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");

  pos = ListFind(head, 6);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");
}

void LinkListTest5()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListInsert(pos, -1);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListInsert(pos, -4);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListInsert(pos, -6);
    ListPrint(head);
  }

  ListDestroy(head);
}

void LinkListTest6()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  ListDestroy(head);
}

int main(void)
{
  //LinkListTest1();
  //LinkListTest2();
  //LinkListTest3();
  //LinkListTest4();
  //LinkListTest5();
  LinkListTest6();
  return 0;
}

本章完.

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

链表

数据结构: 线性表(带头双向循环链表实现) 的相关文章

  • 算法设计与实现--动态规划篇

    什么是动态规划算法 动态规划算法是一种求解复杂问题的方法 通过将原问题分解为相对简单的子问题来求解 其基本思想是将待求解的问题分解为若干个子问题 阶段 按顺序求解子阶段 前一子问题的解 为后一子问题的求解提供了有用的信息 在求解任一子问题时

  • 二叉树先中后序遍历-12.4(day12)

    二叉树三种基本遍历方式 先序遍历 从根节点开始 逐级向下遍历 中序遍历 从左子树最后一层的最左侧节点开始遍历 当遍历到根节点后在开始遍历右子树 后续遍历 先访问叶子节点 从左子树到右子树 最后到根节点 记忆方法 先 中 后可以理解为前 中

  • C语言，求取数组的序亏：已知一个整数数组，求出个数组中每个元素在整个 数组的排序。

    要求获取整数数组中每个元素的排序 可以使用以下方法 1 定义一个结构体数组 其中每个结构体包含数组元素的值和索引 2 遍历整数数组 将每个元素与其索引一起存储到结构体数组中 3 对结构体数组进行排序 按照元素的值进行升序排序 4 遍历排序后

  • 数组实现循环队列（增设队列大小size）

    目录 一 前言 1 如何实现循环 2 如何判断队列为空 3 如何判断队列为满 二 循环队列的结构定义 三 循环队列的创建及其初始化 四 入队 五 出队 六 取队头元素 七 取队尾元素 八 循环队列判空 九 循环队列判满 十 循环队列销毁 一

  • 不会做的题汇总

    摘苹果 题目描述 小红来到苹果园 帮园长摘苹果 园长请小红把摘完的苹果的最小的那个去掉 如果有 多个最小的苹果 那么都要去掉 剩余的苹果算一下平均一个苹果有多重 平均重 量请保留1位小数 输入 输入有2行 第一行 一个整数n代表小红摘的n个

  • DS八大排序之冒泡排序和快速排序

    前言 前两期我们已经对 插入排序 直接插入排序和希尔排序 和 选择排序 直接选择排序和堆排序 进行了详细的介绍 这一期我们再来详细介绍一组排序 交换排序 即耳熟能详的冒泡排序和赫赫有名的快速排序 本期内容介绍 冒泡排序 快速排序 Hoare

  • 数据结构 数组与字符串

    介绍 数组的基础 定义和声明 基本定义 在C语言中 数组可以被定义为一系列相同类型的元素的集合 每个元素在内存中连续排列 可以通过索引 通常是从0开始的整数 来访问 数组的声明 数组在C语言中的声明包括元素类型 数组名和大小 例如 声明一个

  • 华为OD机试 C++【最大载货量】

    描述 在火车站旁的货运站 小明负责调度2K辆中转车 其中K辆用于干货 K辆用于湿货 每批到站的货物来自不同的供货商 需要按照顺序装入中转车 注意 一个供货商的货物只能装在一辆车上 不能分开 但是 一辆车可以放多个供货商的货物 问题是 要让所

  • 回溯算法第零篇【递归、搜索与回溯】【回溯算法入门必看】

    本篇文章的目的 1 给小伙伴们对回溯算法中的名词进行解释 2 消除递归的恐惧 回溯是递归的一个分支 给小伙伴们一个建议 整篇文章都要看完 一字不漏 全是干货 注意 分析回溯的思想之前 我们得知道一个关系 递归包含搜索 搜索包含回溯 所以我们

  • 【数据结构和算法】 K 和数对的最大数目

    其他系列文章导航 Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一 题目描述 二 题解 2 1 方法一 双指针排序 三 代码 3 1 方法一 双指针排序 3

  • 数据结构算法-快速排序

    核心思路 快速排序算法核心思路 选择一个 基准 元素 将数组分为两个子数组 一个包含比基准小的元素 另一个包含比基准大的元素 然后对这两个子数组进行递归排序 基准数 初始化两个索引 i 和 j 分别子数组的开头和结尾 初始化基准元素 bas

  • 【数据结构和算法】 K 和数对的最大数目

    其他系列文章导航 Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一 题目描述 二 题解 2 1 方法一 双指针排序 三 代码 3 1 方法一 双指针排序 3

  • 数组对象排序 （arr.sort()）

    前端面试题库 面试必备 推荐 地址 前端面试题库 对象排序 arr sort 描述 方法sort 将在原数组上对 数组元素 进行排序 即排序时不创建新的数组副本 如果想按照别的顺序进行排序 就必须提供比较函数 该函数要比较两个值 然后返回一

  • 代码随想录算法训练营第42天| ● 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！ 滚动数组 ● 416. 分割等和子集

    416 分割等和子集 已解答 中等 相关标签 相关企业 给你一个 只包含正整数 的 非空 数组 nums 请你判断是否可以将这个数组分割成两个子集 使得两个子集的元素和相等 示例 1 输入 nums 1 5 11 5 输出 true 解释

  • 剑指 Offer（第2版）面试题 40：最小的 k 个数

    剑指 Offer 第2版 面试题 40 最小的 k 个数 剑指 Offer 第2版 面试题 40 最小的 k 个数 解法1 排序 解法2 快速选择 解法3 优先队列 剑指 Offer 第2版 面试题 40 最小的 k 个数 题目来源 53

  • 《LeetCode力扣练习》代码随想录——双指针法（反转链表---Java）

    LeetCode力扣练习 代码随想录 双指针法 反转链表 Java 刷题思路来源于 代码随想录 206 反转链表 双指针 Definition for singly linked list public class ListNode int

  • 冒泡排序/选择排序/插入排序/快速排序/归并排序/桶排序/堆排序/希尔排序/计数排序/基数排序/二分查找/广度优先搜索/深度优先搜索

    排序算法 冒泡排序 Bubble Sort 通过重复地比较相邻的元素并交换它们 使得最大 或最小 的元素逐渐移动到列表的一端 从而实现排序 选择排序 Selection Sort 在未排序的部分中 选择最小 或最大 的元素 并将其放置在已排

  • Leetcode 45 跳跃游戏 II

    题意理解 给定一个长度为 n 的 0 索引 整数数组 nums 初始位置为 nums 0 每个元素 nums i 表示从索引 i 向前跳转的最大长度 还是从初始坐标i 0的位置到达最后一个元素 但是问题不是能不能跳到 而是 最少几步能跳到最

  • 【每日一题】2397. 被列覆盖的最多行数-2024.1.4

    题目 2397 被列覆盖的最多行数 给你一个下标从 0 开始 大小为 m x n 的二进制矩阵 matrix 另给你一个整数 numSelect 表示你必须从 matrix 中选择的 不同 列的数量 如果一行中所有的 1 都被你选中的列所覆

  • 带头双向循环链表基础

    带头双向循环链表基础 销毁 销毁 void ListDestory ListNode phead void ListDestory ListNode phead assert phead ListNode cur phead gt next

随机推荐

  • [避坑指南]GD32F130系列TIMER14

    前言 本人在使用GD32F130F8P6时 使能PA3引脚输出PWM波 但是检查代码没有问题 就是不出PWM波 折磨了3天 最后发现是该款单片机没有TIMER14定时器 手册误导用户啊 代码部分 此代码驱动TIMER14是没有问题的 voi

  • 9道常见的java笔试选择题

    1 关于Java编译 下面哪一个正确 选择一项 A Java程序经编译后产生machine code B Java程序经编译后会生产byte code C Java程序经编译后会产生DLL D 以上都不正确 答案 B 分析 Java是解释型

  • 北京大学肖臻老师《区块链技术与应用》公开课笔记15——ETH概述篇

    北京大学肖臻老师 区块链技术与应用 公开课笔记 以太坊概述篇 对应肖老师视频 click here 全系列笔记请见 click here About Me 点击进入我的Personal Page BTC和ETH为最主要的两种加密货币 BTC

  • 山东大学项目实训开发日志——基于vue+springboot的医院耗材管理系统(16)

    今天我们解决了一个困扰了我们很久的问题 isqr值的获取与使用 功能的设想 通过isqr这个值来确定该耗材是否使用二维码管理 在新增耗材种类的时候加入该属性 选择是或否 并写入数据库 在显示库存数据的时候通过耗材的id查找该值 以此决定是否

  • 解决：Cannot deserialize value of type `java.util.Date` from String “xxx“: not a valid representation..

    一 问题 在做数据更新操作的时候 后台数据为Date时 前端把String类型数据传到后台时 Date类型无法识别这个String数据 所以会报错 二 错误描述 主要问题 Caused by com fasterxml jackson da

  • linux重启命令

    shutdown重启系统 usr sbin shutdown r now usr sbin 指定了命令的位置 路径 shutdown 是命令本身 r 是指示重新启动系统的选项 now 表示立即执行命令 不进行倒计时 也可以指定一个时间延迟

  • el-input校验，只能输入正整数

    一 表单校验方式 fileSort required true message 请输入排序 trigger blur pattern 1 9 d message 请输入正整数 trigger blur 二 el input的type设置为n

  • mybatis笔记（老杜版本）

    一 MyBatis概述 1 1框架 Java常 框架 SSM三 框架 Spring SpringMVC MyBatis SpringBoot SpringCloud 等 SSM三 框架的学习顺序 MyBatis Spring SpringM

  • mysql jdbc url utf8_Mysql JDBC Url参数与异常问题

    今天在写Java项目使用了 SELECT FROM plan WHERE isDelete isDelete AND nestId in open close separator gt nestId 但是很不幸 后台报异常 java sql

  • springboot整合七牛云对象存储

    目录 一 测试 二 整合 一 测试 注册七牛云账号 并进行邮箱绑定和实名认证 七牛云每个月送10G完全够我们开发 创建一个空间 存储区域哪里离你近选哪里 访问控制一定要公开 创建完成后 后期上传的静态资源 可以根据域名 文件名直接访问 自定

  • Java中正则表达式的使用

    Java中正则表达式的使用 在Java中 我们为了查找某个给定字符串中是否有需要查找的某个字符或者子字串 或者对字符串进行分割 或者对字符串一些字符进行替换 删除 一般会通过if else for 的配合使用来实现这些功能 如下所示 Jav

  • MMdetection之train_detector 源码解析

    目录 一 构建 data loaders mmdet datasets builder py 2 构建分布式处理对象 3 构建优化器 4 创建 EpochBasedRunner 并进行训练 一 构建 data loaders mmdet d

  • react hook+Typescript+一个ts项目

    说到Hook 少不了react16的新生命周期 https segmentfault com a 1190000018413163 关于getDerivedStateFromProps钩子 怎么在里面进行异步 判断是由state还是prop

  • 100天精通Python（可视化篇）——第89天：Bokeh库绘图可视化基础入门（参数说明+案例实战）

    文章目录 专栏导读 一 Bokeh是什么 二 安装与导入 三 Bokeh接口介绍 四 创建图表 五 添加自定义渲染器 切换主题 添加图例 图例位置 图例方向 图例背景和边界 图例文本的外观 行列布局 网格布局 书籍推荐 包邮送书5本 专栏导

  • Spring Cloud Nacos

    1 Spring Cloud Alibaba的功能 1 流控制和服务降级 支持WebServlet WebFlux OpenFeign RestTemplate Dubbo访问限制和降级流的功能 它可以在运行时通过控制台实时修改限制和降级流

  • Linux 安装 vmware workstation

    1 下载vmware workstation 下载地址 https my vmware com cn group vmware info slug desktop end user computing vmware workstation

  • iOS Xcode 7.2 以及各种版本Xcode工具下载地址

    https developer apple com download more 这里面有所有版本的Xcode dmg文件供大家下载

  • Anaconda学习

    Anaconda conda 创建 激活 退出 删除虚拟环境 Anaconda超详细教程2023 7 10 windows 网络连接错误 1 首先学习anaconda是什么 Anaconda 官方网站 就是可以便捷获取包且对包能够进行管理

  • 人人都是产品经理？

    产品经理顾名思义就是产品 经理 那么只要搞懂产品是什么 经理又什么什么 就明白了产品经理是什么 产品是什么 产品是满足需求的载体 能被市场 人们使用和消费 并能满足人们某种需求 创造价值 的任何东西 包括有形的实物和无形的服务 同时 产品也

  • 数据结构: 线性表(带头双向循环链表实现)

    文章目录 1 链表的分类 2 带头双向循环链表 2 1 带头双向循环链表的定义 2 2 接口函数 3 接口函数的实现 3 1 创建并返回链表的头结点 ListCreate 3 2 双向链表打印 ListPrint 3 3 双向链表尾插 Li

热门标签