搜索内容

包含标签:链表 的文章
  • leetcode-146. LRU 缓存机制
    其他

    leetcode-146. LRU 缓存机制

    leetcode-146. LRU 缓存机制 题目: 代码: #include #include #include using namespace std; struct DLinkedNode{ int key,value; DLinkedNode *prev,*next; }; unordered_mapcache; DLinkedNode* head,*tail; int size; int capacity; LRUCache(int _capacity):capacity(_capacity),size(0) { head = new DLinkedNode; tail = new DLinkedNode; head->next = tail; tail->prev = head; }
    admin 今天
  • 数据结构学习方法
    其他

    数据结构学习方法

     
    admin 今天
  • 19. 删除链表的倒数第 N 个结点
    其他

    19. 删除链表的倒数第 N 个结点

    给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2: 输入:head = [1], n = 1 输出:[] 示例 3: 输入:head = [1,2], n = 1 输出:[1] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0),
    admin 今天
  • 复合型数据结构:(双向循环)链表_第2部分
    其他

    复合型数据结构:(双向循环)链表_第2部分

    本部分实现双向循环链表的: 统计链表中结点个数删除某个结点 (根据结构体中某个成员的值、根据处于链表中的位置) (有头节点、无头结点的处理区别)链表的销毁及野指针处理 双向循环链表_第2部分 1 统计链表中的结点个数1.1 带头结点1.2 不带头结点 2 查找链表中的数据2.1 查找带头结点的链表2.2 查找不带头节点的链表 3 根据位置删除某个节点3.1 带头结点3.1.1 正数第k个位置3.1.2 倒数第k个位置3.1.3 合二为一:过程的抽象 3.2 不带头结点3.2.1 正数第k个位置3.2.2 倒数第k个位置3.2.3 能合二为一吗? 4 销毁链表野指针问题 1 统计链表中的结点个数 1.1 带头结点 int CountingNodesOfListWithHead(node *list){ if(list == NULL){ // Defensi
    admin 今天
  • 习题整理12.02
    其他

    习题整理12.02

    假设 A 类有如下定义,设 a 是 A 类的一个实例,下列语句调用哪个是错误的?() 解析:静态方法可以通过类名调用,非静态的需要实例化对象来调用已知一颗二叉树中没有重复值,知道这颗树的前序,中序和后序遍历中的哪些不可以唯一确定这颗二叉树: 解析:已知先序和后序,不能唯一确定二叉树 已知先序或后序,而又知中序,则能唯一确定二叉树 先序、中序相同时,二叉树没有左子树 后序、中序相同时,二叉树没有右子树 后序、先序相同时,只有一个根节点 6.有向图 G 中有 n 个顶点,e 条边,采用邻接表存储,若采用 BFS 方式遍历其时间复杂度为( ) 解析:BFS和DFS都是: 邻接矩阵-O(n^2) 邻接表-O(n+e) 7 .删除非空线性链表中由指针p所指链结点的直接后继结点的过程是依次执行动作()。 解析:link§ 表示读取 p 结点中指针 link 内存储的地址,那么 link§ 读取到的就是 p 结点的直接
    admin 今天
  • 力扣题解:剑指 Offer 28. 对称的二叉树
    其他

    力扣题解:剑指 Offer 28. 对称的二叉树

    题目 请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。 示例 1: 输入:root = [1,2,2,3,4,4,3] 输出:true 解题思路 递归判断left节点和right节点值是否相等 代码 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if (root
    admin 今天
  • 数据结构学习——链表的简易功能实现
    其他

    数据结构学习——链表的简易功能实现

    引入头文件 #include #include #include 结构体定义 typedef struct Node { int data; struct Node *pNext; }NODE,* PNODE; 创建链表 PNODE creat_list(void){ //不存放有效数字的头结点 PNODE pHead = (PNODE)malloc(sizeof(NODE)); if(pHead==NULL){ printf("分配失败"); exit(-1); } //创建尾节点 PNODE pTail = pHead; pTail->pNext = NULL; //动态创建 需要指定有效节点个数 int len; int val;//临时存放用户输入的值 printf("请输入该链
    admin 今天
  • 2021ICPC上海G Edge Groups(树上DP)
    其他

    2021ICPC上海G Edge Groups(树上DP)

    考虑一个菊花图:1号点为中心,其他n-1个点都与1号点直接相连。 计算两个边分成一组,有多少分组方法: 答案是1*3*5*7*…*n 证明过程 现在来考虑一个普通图: 假设A点是B点的父亲 B点有N个儿子(不包含父亲),假设全部都是叶子节点 1:如果N是偶数,那么将这些连接叶子节点的边两两分组,它有1 * 3*5*7 … * N (1-N中的奇数相乘)种分组方法 2:如果N是奇数,它同样有1 * 3 * 5 * … * N(1到N中的奇数相乘)种分组方法,而且必定会剩下一个边无法配对,所以这个剩下的边只好与B点与父亲相连的那条边配对 当A点在进行统计时,假设统计到了A1个奇数节点(N为奇数的B点),统计到了A2个偶数节点(N为偶数的B点),奇数节点已经把连接父亲节点的边给用掉了,所以A点可用于自由组合的边只有连接偶数节点的那些边(即1-A2中的奇数相乘)。 所以,答案就是所有点的自由分配方案的乘积 #pragm
    admin 今天
  • 链表及常见面试题
    其他

    链表及常见面试题

    链表 单链表 特点: 逻辑上顺序存储,物理上无序存储 头指针根据情况而定,不保存数据,很多操作需要头指针,比如原地反转链表。 每个节点包含 data, Node next保存下个Node public class LinkList { public Node header=new Node(); add{} query{} .... } public class Node{ String data; Node next; Node(Sring data){ this.data=data; } } ​ 常见操作:增删改查。 单链表面试题 1 求链表中的有效节点数? 思路 1:while(true)遍历该链表 直到next==null break,否则Count++ 思路 2:设置两个节点,Fir 走一步,Se
    admin 今天
  • 力扣题解:面试题 02.03. 删除中间节点
    其他

    力扣题解:面试题 02.03. 删除中间节点

    题目 若链表中的某个节点,既不是链表头节点,也不是链表尾节点,则称其为该链表的「中间节点」。 假定已知链表的某一个中间节点,请实现一种算法,将该节点从链表中删除。 例如,传入节点 c(位于单向链表 a->b->c->d->e->f 中),将其删除后,剩余链表为 a->b->d->e->f 示例: 输入:节点 5 (位于单向链表 4->5->1->9 中) 输出:不返回任何数据,从链表中删除传入的节点 5,使链表变为 4->1->9 解题思路 一道抖机灵的题,脑筋急转弯将下一个节点值赋值给当前节点将当前节点的next指针指向下下个节点 代码 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x)
    admin 今天
  • 力扣题解:面试题 02.02. 返回倒数第 k 个节点
    其他

    力扣题解:面试题 02.02. 返回倒数第 k 个节点

    题目 实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。 示例: 输入: 1->2->3->4->5 和 k = 2 输出: 4 说明: 给定的 k 保证是有效的。 解题思路 方法1:快慢指针 快慢指针相差k个节点的距离当快指针到达链表末尾,慢指针指向倒数第k个节点 方法2:2次遍历(不提供代码)第一次遍历计算出链表长度length,第(length-k+1)个节点即为倒数第k个节点第二次遍历,找到第(length-k+1)个节点 代码 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { pu
    admin 今天
  • " alt="TCP为什么三次握手">
    其他

    TCP为什么三次握手

    先搞一个简单的生活中的例子打电话: 模拟场景:client要打电话给server 在一个不可靠的信道上建立一个可靠的通话,从理论上来讲至少需要四步。 
    admin 今天
  • C++链表
    其他

    C++链表

    #pragma once #include using namespace std; typedef int DataType; class DataNode { public: DataType data; DataNode* next; }; class DataLink { private: DataNode* head; int linksize; public: DataLink(); virtual ~DataLink() { delete head; } DataNode* CreateNode(); //增 void AddNodeToLinkAtHead(DataNode* newnode); void AddNodeToLinkAtBack(DataNode* newnode); //删 void DelNode(DataType data); //改 void ModNode(DataType data,DataType newdata); //查 int Find
    admin 今天
  • mvc六种方法的总结
    其他

    mvc六种方法的总结

    @Controller @ResponseBody public class UserController { //http:localhost:8080/hello @RequestMapping("/hello") public String hello(){ return "您好"; } /* * URL: http://localhost:8080/findUserByNA?name=tomcat&age=18 */ @RequestMapping("/findUserByNA") public String findUserByNA(String name,int age){ return name+":"+age; } /* URL: http://localhost:8080/findUserByNA2?name=tomcat&age=18 1.通过url中的key获取数据. * 2.如果参数
    admin 今天
  • 题目(二叉树)
    其他

    题目(二叉树)

    1、把一棵二叉树转换为它的镜像树 // 转换成镜像树 void mirror_tree(TreeNode* root) { if(NULL == root) return; TreeNode* temp = root->left; root->left = root->right; root->right = temp; mirror_tree(root->left); mirror_tree(root->right); } 2、输入两棵二叉树A、B,判断B是不是A的子结构(我们约定空树不是任意一棵树的子结构) // 判断两棵树 bool treecmp(TreeNode* r1,TreeNode* r2) { if(NULL == r1 && NULL == r2) return true; if(NULL != r1 && NULL == r2) return true;
    admin 今天
  • 环形缓冲区的实现
    其他

    环形缓冲区的实现

    环形缓冲区 //缓存区大小 #define PM_BUF_SIZE 1024 //获取当前缓冲区的数据个数 #define circ_cnt(head, tail, size) (((head) > (tail)) ? \ ((head) - (tail)) : \ ((head) - (tail)) & ((size) - 1)) //计算缓冲区的可写大小 #define circ_space(head, tail, size) circ_cnt((tail), ((head) + 1), (size)) //把指针n移动1个位置 #define circ_inc(n, s) (((n) + 1) % (s)) //把指针n移动v个位置 #define circ_add(n, v, s) (((n) + (v)) % (s)) //返回小的数 #define min(a, b) \ ({ \ typeof(a) __a
    admin 今天
  • 数据结构代码题—排序<选择排序顺序和链式实现>
    其他

    数据结构代码题—排序<选择排序顺序和链式实现>

    选择排序顺序和链式实现 概述 选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置知道未排序元素个数为0。 上述说法比较笼统,下面是其执行步骤: 设置一个min指向每次循环的第一个元素;对于后续的元素,依次将其初始最小值与后续元素比较,比较完成后若min更新,则进行初始最小值与更新最小值进行交换。 此处引用网上一张比较经典的gif来展示选择排序的整个过程: 其详细的设计单步执行,这里以网上看到的详细执行图为介绍: 上述的两张图看明白后,相信对选择排序已经基本了解了其算法的实现思路,下面是对选择排序的顺序表存储实现。 顺序存储实现 static void SelectedSort(int[] arr){ int min;//初始化最小值
    admin 昨天
  • Java环形链表
    其他

    Java环形链表

    给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。 如果链表中存在环,则返回 true 。 否则,返回 false 。 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public clas
    admin 昨天
  • 厚积薄发打卡Day103:链表(一)<删除倒数第k个节点>
    其他

    厚积薄发打卡Day103:链表(一)<删除倒数第k个节点>

    删除节点 题目:如果给定一个链表,请问如何删除链表中的倒数第K个节点?假设链表中的节点总数为N,那么1≤K≤N。要求只能遍历链表一次 举例:输入如下链表a,删除倒数第2个节点之后得到链表b 链表a: 1-->2-->3-->4-->5-->6 链表b: 1-->2-->3-->4-->6 思路 如果可以遍历两次,那么这个问题就会变得简单不少: 第一次遍历获取链表总结点数n(题目为例:n = 6)第二次遍历直接找出链表的第n-k个节点(题目为例:n-k = 6-2 = 4),并把该节点(倒数k+1)的next指向其next.next(倒数k-1)节点,即可删除倒数第k个节点 可以通过设置快慢双指针实现 快指针先走k步,慢指针保持不动当快指针从k+1步继续往后走时,慢指针开始移动当快指针到达链表末尾时,慢指针此时会到达倒数k+1个节点此时删除第k个节点即可(参考第1.2步) 实现
    admin 昨天
  • 力扣 1446. 连续字符
    其他

    力扣 1446. 连续字符

    题目 给你一个字符串 s ,字符串的「能量」定义为:只包含一种字符的最长非空子字符串的长度。 请你返回字符串的能量。 示例 输入:s = “leetcode” 输出:2 解释:子字符串 “ee” 长度为 2 ,只包含字符 ‘e’ 。 输入:s = “abbcccddddeeeeedcba” 输出:5 解释:子字符串 “eeeee” 长度为 5 ,只包含字符 ‘e’ 。 输入:s = “triplepillooooow” 输出:5 输入:s = “hooraaaaaaaaaaay” 输出:11 示例 5: 输入:s = “tourist” 输出:1 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/consecutive-characters 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 方法1:双指针遍历 Java
    admin 昨天
  • 12张海旭
    其他

    12张海旭

    #include #include #include #include #include #include //#include #include #include //服务器和客户端间发送的内容结构体 struct msg_t { char name[32]; char text[256]; }; struct client_t//双向链表 { int fd; struct client_t *next; struct client_t **prev;//前驱 }; //全局变量 struct client_t *head=NULL; void *child_proc (void
    admin 昨天
  • java实现链表创建和链表递归反转
    其他

    java实现链表创建和链表递归反转

    链表用非递归实现反转如图: 首先指针H迭代到底如下图所示,并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数,所以整个过程NewH指针一直指向存放5的地址空间。 然后H指针逐层返回的时候依次做下图的处理,将H指向的地址赋值给H->next->next指针,并且一定要记得让H->next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层H->next->next赋值的时候会覆盖后续的值 继续返回操作:上图第一次如果没有将存放4空间的next指针赋值指向NULL,第二次H->next->next=H,就会将存放5的地址空间覆盖为3,这样链表一切都大乱了。接着逐层返回下去,直到对存放1的地址空间处理。返回到头 //递归实现链表反转 public class Node { int data; Node next; static Node re
    admin 昨天
  • 不带头结点的双向链表
    其他

    不带头结点的双向链表

    文章目录 前言讲正事准备工作——各种结构体的定义结点专用于储存链表信息的结构体 初始化增删改逆置遍历并输出链表 特别栏目——总结 前言 经过两个多星期的链表学习(别问为什么学了这么久,问就是前段时间一不小心走进舒适圈效率极低),发了超多篇相关博客,链表的学习也差不多到尾声啦,于是在十二月的第一天,有了这篇双向链表。 因为其实带不带头结点循不循环差别不是很大,再加上本人犯懒,所以双向链表不会有带头结点和循环篇了(嘻~) 讲正事 其实双向链表在处理上和单链表最大的不同就是要兼顾一个结点里的两个指针,但是最常见的错误方式,就是在处理的时候会很自然地忘记处理指向前一个结点的指针。 准备工作——各种结构体的定义 结点 typedef struct node { struct node* pre; int num; struct node* next; }Node; 专用于储
    admin 昨天
  • 尝试证明快慢指针可以相遇问题 以及 证明入环点问题
    其他

    尝试证明快慢指针可以相遇问题 以及 证明入环点问题

    预热 引用题目:环形链表 快慢指针解法: class Solution { public boolean hasCycle(ListNode head) { if(head == null) { return false; } ListNode slow = head; ListNode fast = head.next; boolean flag = false; while(slow != fast) { if(fast == null || fast.next == null) { return false; } fast = fast.next.next; slow = slow.next; } return true; } } 执行用时:0 ms, 在所有 J
    admin 昨天
  • 数据结构基础笔记 — 第三章 栈与队列
    其他

    数据结构基础笔记 — 第三章 栈与队列

    第三章 栈和队列 目录 第三章 栈和队列3.1 栈3.1.1 栈的逻辑结构3.1.2 栈的顺序存储结构及实现3.1.3 栈的链式存储结构及实现3.1.4 栈的应用举例 3.2 队列3.4.1 队列的逻辑结构3.4.2 队列的链式存储结构及实现3.4.3 队列的顺序存储结构及实现3.4.4 循环队列和链队列的比较 两种特殊的线性表——栈、队列 ➢从数据结构角度看,栈和队列是操作受限的线性表,他们的逻辑结构相同 3.1 栈 3.1.1 栈的逻辑结构 栈:限定仅在 表尾进行插入和删除操作的线性表 空栈:不含任何数据元素的栈 允许插入和删除的一端称为栈顶(表尾),另一端称为栈底 栈只是对表插入和删除操作的位置进行了限制,并没有限定何时进行插入和删除操作 3.1.2 栈的顺序存储结构及实现 顺序栈——栈的顺序存储结构 如何改造数组实现栈的顺序存
    admin 昨天
  • LeetCode160相交链表
    其他

    LeetCode160相交链表

    题目描述 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中不存在环。 注意,函数返回结果后,链表必须 保持其原始结构 。 自定义评测: 评测系统 的输入如下(你设计的程序 不适用 此输入): intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数 skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8
    admin 昨天
  • 如何判断链表是否有环
    其他

    如何判断链表是否有环

    问题引入: 怎么辨别下面两个链表的区别?,他们的结点数都相同 方法:快慢指针 什么是快慢指针? 顾名思义,使用两个指针,一个的位移距离比另一个要大 怎么使用快慢指针判断链表是否有环? 令两个指针都位于链表头结点,处于头指针的位置,快指针每次向后移动两个结点的位置,慢指针每次移动一个结点的位置,如果两个指针相遇了,证明有环 区分:头结点,首结点 头结点是为了操作链表方便而设立的结点,里面一般不存放数据首结点才是第一个数据的存放点 下图是每一步的执行过程,在第七步,两个指针指向了同一个结点,证明了这个链表有环 当链表没有环的时候,快指针必然会指向NULL,因为尾结点的指针指向的就是NULL NULL 表示空 问题拓展: 1.怎么求出环的长度? 增加一个变量记录下指针的移动次数当快指针和慢指针相遇的时候,快指针比慢指针多走了一个环的长度,相当于数学中的追及问题,快的一
    admin 昨天
  • " alt="队列及其功能实现两种方法–顺序表和链表">
    其他

    队列及其功能实现两种方法–顺序表和链表

    1.队列的概念 只允许在一端插入数据操作,在另一端进行删除数据操作的特殊线性表;进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列);队列具有先进先出(FIFO)的特性。 2.顺序队列 (1)队头不动,出队列时队头后的所有元素向前移动 缺陷:操作是如果出队列比较多,要搬移大量元素。   (2)队头移动,出队列时队头向后移动一个位置   如果还有新元素进行入队列容易造成假溢出。 假溢出:顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。 真溢出:顺序队列的最大存储空间已经存满二又要求进行入队列操作所引起的溢出。 我们可以用顺序表或者链表实现 1.顺序表源代码如下: #include #include #define MAX 4 typedef struct{ int *base; int front; // 队头 int rear; // 队尾 }SqQueue; void initQueue(SqQueue &
    admin 昨天
  • 中国大学MOOC-陈越、何钦铭-数据结构-起步能力自测题 自测-4 Have Fun with Numbers (20 分)
    其他

    中国大学MOOC-陈越、何钦铭-数据结构-起步能力自测题 自测-4 Have Fun with Numbers (20 分)

    请注意,数字123456789是一个9位数字,完全由1到9的数字组成,没有重复。将其加倍,我们将获得246913578,这恰好是另一个9位数字,正好由1到9的数字组成,只是在不同的排列中。如果我们再翻倍,请查看结果! 现在,假设您检查是否有更多具有此属性的数字。也就是说,用k个数字将给定的数字加倍,你要知道结果数字是否只由原始数字中的数字排列组成。 输入规格: 每个输入包含一个测试用例。每个大小写包含一个不超过20位的正整数。 输出规格: 对于每个测试用例,如果输入数字加倍,则首先打印一行“是”,给出一个仅由原始数字中的数字排列组成的数字,如果不是,则打印“否”。然后在下一行中,打印加倍的数字。 Sample Input: 1234567899 结尾无空行 Sample Output: Yes 2469135798 结尾无空行 #include #include char a[50],b[50]; //a用于记录输入的数字 b用来记录需要进位的数字 当a+b时为*2后的数 i
    admin 昨天
  • " alt="Jav剑指 Offer II 086. 分割回文子字符串(击败85.86%用户)">
    其他

    Jav剑指 Offer II 086. 分割回文子字符串(击败85.86%用户)

    题目: 给定一个字符串 s ,请将 s 分割成一些子串,使每个子串都是 回文串 ,返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 : 输入:s = "google" 输出:[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]] 思路: 先有回溯这个树的结构  节点表示没有并扫描到的字符,递归用来纵向遍历,for循环用来横向遍历。 复杂度: 时间: 动态规划预处理的复杂度为 O(n^2);爆搜过程中每个字符都可以作为分割点,并且有分割与不分割两种选择,方案数量为 2^{n - 1},每个字符都需要往后检查剩余字符的分割情况,复杂度为 O(n)O(n)。整体复杂度为 O(n * 2^n) 空间:O(n * 2^n) 代码: public String[][] partition(String s) { //已经写过很多遍了开头模板 List
    admin 昨天
  • leetcode:14.相交链表 简单
    其他

    leetcode:14.相交链表 简单

    public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode A = headA, B = headB; // 当没有相交时循环 while (A != B) { // 链表A到达末尾时,使链表A指向headB的头结点,否则前移 A = A == null ? headB : A.next; // 链表B到达末尾时,使链表B指向headA的头结点,否则前移 B = B == null ? h
    admin 昨天
  • 数据结构和算法-07.链表概述
    其他

    数据结构和算法-07.链表概述

    # CY3761 | 2021-12-01 09:37 ## 有没有一种数据结构, 在扩容缩容或者新增删除的时候只处理一个, 不需要改变原有数据区 # 一组数据 100, 200, 300, 400 # 如果是顺序表 容量可能是 8 元素个数就只有 4 可能出现浪费情况 # 希望是存一个数据, 就申请扩容一个, 删除一个, 就申请缩容一个, 不影响其他内存地址 # 100(0x12345678) -> 200(0x23455678 地址不连续) -> 300(0x34565678) # 一个节点 2个格子 一个存数据(数据域) 一个存内存地址(指针域) # 第1个节点 (第1个数据, 第2个内存地址) # 第2个节点 (第2个数据, 第3个内存地址) # 节点与节点就是链表 # 链表是一种物理存储单元上非连续、非顺序的存储结构 # 数据元素的逻辑顺序通过链表中的指针链接次序实现. # 链表又分为单向和双
    admin 昨天
  • 傻瓜式贪吃蛇源码,稍微有点基础就能看懂
    其他

    傻瓜式贪吃蛇源码,稍微有点基础就能看懂

    前言: 本人C语言并不好(大一新生),只是刚好学到链表时发现它很符合贪吃蛇的设定,所以突发奇想写了这个贪吃蛇。代码有点呆,发这篇文章仅仅是因为第一次写了一个算是有点可玩性的游戏很高兴想分享给大家而已。(虽然说这是个被玩烂了的、写烂了的游戏。) 再次声明:代码很拙劣,大佬勿喷。不过应该属于容易看懂的类型吧。。。。 基本原理: 因为蛇的身体所带数据结构都是相同的,又有顺序(从头到尾),所以可以使用链表来表示蛇。所以我写了个body结构包含{蛇的位置x,y坐标,这一部分的方向,下一个部分的地址,上一个部分的地址(在更新蛇的下一个状态时使用)},然后再不停的画蛇头蛇尾、清除蛇头蛇尾、画下一个状态的蛇头蛇尾。实现动态的效果。 源码: #include "stdio.h" #include "windows.h" #include "conio.h" #include "time.h"//Only use it to srand #define CHANDLE (GetStdHandle(STD_OUTPUT_HANDLE)) #define
    admin 昨天
  • [NOIP2021] 报数
    其他

    [NOIP2021] 报数

    Solution 以预处理出来所有合法的数,用链表保存,每次询问答案就是O(1)的。预处理的时候可以先把带七的无重复的找出来,具体来说最大为为i的含有七的数字一定由第i位为7的所有数字和前i-1位含有7的所有数字在第i位拼任意数组成,然后根据这些晒掉所有倍数。 Code #include #include using namespace std; bool isok[10000005]; int sevens[10000005],cnt,nx[10000005]; void shai() { sevens[++cnt]=7; int pw = 10; for(int i=1;i<=6;i++) { int cnt0 = cnt; for(int j=1;j<=9;j++) { if(j!=7) { for(int k=1;k<=cn
    admin 昨天
  • 07_JavaScript数据结构与算法(七)双向链表
    其他

    07_JavaScript数据结构与算法(七)双向链表

    JavaScript 数据结构与算法(七)双向链表 单向链表和双向链表 单向链表 只能从头遍历到尾或者从尾遍历到头(一般从头到尾)。链表相连的过程是单向的,实现原理是上一个节点中有指向下一个节点的引用。单向链表有一个比较明显的缺点:可以轻松到达下一个节点,但回到前一个节点很难,在实际开发中, 经常会遇到需要回到上一个节点的情况。 双向链表 既可以从头遍历到尾,也可以从尾遍历到头。链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用,也有一个向后连接的引用。双向链表可以有效的解决单向链表存在的问题。双向链表缺点: 每次在插入或删除某个节点时,都需要处理四个引用,而不是两个,实现起来会困难些。相对于单向链表,所占内存空间更大一些。但是,相对于双向链表的便利性而言,这些缺点微不足道。 双向链表结构 双向链表不仅有 head 指针指向第一个节点,而且有 tail 指针指向最后一个节点。每
    admin 昨天
  • " alt="第五章 树和二叉树">
    其他

    第五章 树和二叉树

    第五章 树和二叉树 5.1 树和二叉树的定义 5.1.1 树的定义 树(Tree)是n(n>=0)个结点的有限集。 ​ 若n=0,称为空树; ​ 若n > 0 ,则它满足如下两个条件: ​ (1)有且仅有一个特定的称为根(root)的结点; ​ (2)其余结点可分为m(m>=0)个互不相交的有限集 T1,T2,T3…,Tm ​ 其中每一个集合本身又是一棵树,并称为根的子树(SubTree) 5.1.2 树的基本术语 结点的度:分支的个数 树的度:树内分支的度的最大值 树的深度:树中结点的最大层次 有序树:树种结点的各子树从左至右有次序(最左边的为第一个孩子) 无序树:树种结点的各子树无次序 森林:是m(m>=0)棵互不相交的树的集合 树结构和线性结构比较 5.1.3 二叉树的定义 ​ 二叉树是n(n>=0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两
    admin 昨天
  • " alt="第四章 串、数组、广义表">
    其他

    第四章 串、数组、广义表

    第四章 串、数组、广义表 4.1 串的定义(string) 定义 术语 子串:一个串中任意个连续字符组成的子序列(含空串)称为该串的子串 例如: 真子串是指不包含自身的所有子串 主串:包含子串的串相应地称为主串 字符位置:字符在序列中的序号为该字符在串中的位置 子串位置:子串第一个字符在主串中的位置 空格串:有一个或多个空格组成的串,与空串不同 串相等:当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的 所有空串是相等的 4.2 案例引入 病毒检测 4.3 串的类型定义、存储结构及其运算 https://i.loli.net/2021/11/01/ZV2jRlNrcK4qwX6.png https://i.loli.net/2021/11/01/cTVZrCEuSq7MNRo.png https://i.loli.net/2021/11/0
    admin 昨天
  • 02双链表
    其他

    02双链表

    双链表 实现一个双链表,双链表初始为空,支持 5 种操作: 在最左侧插入一个数;在最右侧插入一个数;将第 k 个插入的数删除;在第 k 个插入的数左侧插入一个数;在第 k 个插入的数右侧插入一个数 现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。 思路 用三个数组模拟双链表操作,e存储值,l存储指向左边的下标(指针),r存储指向右边的下标。 #include using namespace std; const int N = 1e5 + 10; // e存储值,idx表示当前可分配的空间下标,l表示指向左边的下标,r表示指向右边的下标 int e[N], l[N], r[N], idx; void init() { // 0下标表示左端点,1表示右端点 r[0] = 1; l[1] = 0;
    admin 昨天
  • " alt="第三章 栈和队列">
    其他

    第三章 栈和队列

    第三章 栈和队列 栈和队列是限定插入和删除只能在表的“端点”(末尾)进行的线性表 即:栈和队列是线性表的子集(插入和删除位置受限制的线性表) 栈的特性:先进后出 队列的特性:先进先出 3.1 栈和队列的定义和特点 3.1.1栈的定义和特点 1.定义 只能在栈顶操作 2.逻辑结构 一对一 3.存储结构 顺序栈或链栈,顺序栈更常见 4.运算规则 只能在栈顶运算,且访问节点时按照"后进先出"的原则 5.实现方式 关键是编写入栈和出栈函数,具体实现按照存储结构不同 而不同 栈的操作示意图 栈和一般线性表的区别:仅在于运算规则不同 3.1.2 队列的定义和特点 1.定义 表的一端插入,另一端删除(头删尾插) 2.逻辑结构 一对一 3.存储结构 顺序队或链队,循环顺序队更常见 4.运算规则 只能在栈顶运算,且访问节点时按照"后进先出"的原则 5.实现方式 关键是掌握入队和出队操作
    admin 昨天
  • Leetcode206 反转链表(迭代+递归)
    其他

    Leetcode206 反转链表(迭代+递归)

    迭代思想: 记录当前节点 curr 和上一个节点 prev。 遍历链表,不断将 curr->next 指向 prev。 把当前节点放到上一节点的前面。 递归思想: 递归函数返回的已经排序的链表有特点: out -> node1-> node2 -> ... -> nodex -> nullptr head -> nodex -> nullptr 因此,不需要遍历返回的链表找到最后一个节点,head 的指向就是最后一个节点。 注意:head -> next = nullptr 不能省略。否则会报错 “head use after free” 链表的结尾一定要指向 nullptr 附上代码: 迭代 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* curr = head;
    admin 昨天
  • 01单链表
    其他

    01单链表

    单链表 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数;删除第 k 个插入的数后面的数;在第 k 个插入的数后插入一个数。 现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。 思路 数组模拟链表操作 #include using namespace std; const int N = 1e5 + 10; // e存储值,ne存储下一个值的下标,idx为当前待分配的空间下标,head为头节点 int e[N], ne[N], idx, head; void init() { head = -1; idx = 0; } // 在头节点后面插入x void insert_to_head(int x) { e[idx] = x; ne[idx] = head; head =
    admin 昨天
  • 38. 外观数列
    其他

    38. 外观数列

    class Solution { public: string countAndSay(int n) { if(1==n) return "1"; string ret="11"; for(int i=2; i
    admin 昨天
  • 数据结构学习笔记(8)链式队列
    其他

    数据结构学习笔记(8)链式队列

    完整代码+打印任务管理+打印任务模拟 目录 ChainQueue.h ChainQueue.c PrintManage.h PrintSimulate.c ChainQueue.h #pragma once #include #include #include typedef int DataType; //定义结点中的结构体 typedef struct qnode { DataType data; struct qnode* next; }QNode; //定义链式队列队头和队尾指针结构体 typedef struct { QNode *front; QNode *rear; }LQueue; //初始化队列 void QueueInitiate(LQueue* Q); //非空否 int QueueNotEmpty(LQueue Q); //入队列 void QueueAppend(LQueue *Q, DataType x); //出队列 int
    admin 昨天
  • 字节阿里高频50题:41. 缺失的第一个正数 440. 字典序的第K小数字(树的变体,经典)
    其他

    字节阿里高频50题:41. 缺失的第一个正数 440. 字典序的第K小数字(树的变体,经典)

    /** 解题思路:思路是剑指Offer的的3题:数组中重复的数字,最小正整数,也就是本来应该nums.length个个数 */ class Solution { public int firstMissingPositive(int[] nums) { int n= nums.length; for(int i=0 ; i 0 && nums[i] <= n && nums[nums[i]-1]!=nums[i]){ int tmp = nums[nums[i]-1]; nums[nums[i]-1] = nums[i]; nums[i] = tmp; } }
    admin 昨天
  • C语言8种基本排序算法之计数排序
    其他

    C语言8种基本排序算法之计数排序

    小白一天学一个算法系列,从逻辑、关键、算法动画、完整示例代码四个方面进行学习。 (注:冒泡排序示例代码有更详细的注解,共用代码后续算法示例代码中不再注释。) 类似于整理扑克牌,将相同数字的扑克牌放在一起,然后按顺序叠放,这样就和刚拆封的扑克牌顺序一样。 逻辑:统计有限范围内的相同元素的出现次数并依序填入到数组序列中。 关键:统计次数,依序按次数填入序列。 动画:  完整示例代码:  #include #include #include #define N 300000000 //元素个数 #define M 100 //元素区间 //数组打印 void arr_print(int* arr) { int i; for(i=0;i
    admin 昨天
  • 【C语言入门】数据结构-链队列的代码实现
    其他

    【C语言入门】数据结构-链队列的代码实现

    链队列的代码实现 前言代码部分节点定义初始化队列销毁队列入队列出队列 总结 前言 由于是给朋友们入门这里的实现是依据严蔚敏版《数据结构》一书中的伪代码进行实现的。主要目的是让朋友 们知道伪代码实现成为正式代码的流程 代码部分 节点定义 //书上代码 typedef struct QNode { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; /* 代码解读: 这里面有两个地方需要注意,首先是QElemType 这个是一个代指,这个部分可以是任意数据类型 例如int; 第二点就是QueuePtr 这个可以理解程QNode*; 所以实际上应该生成的代码就是 */ // 实现 typede
    admin 昨天
  • 数据结构 Java数据结构 集合框架及背后的数据结构
    其他

    数据结构 Java数据结构 集合框架及背后的数据结构

    文章目录 集合框架及背后的数据结构1.介绍类和接口总览 2.接口 interfaces2.1基本的关系解释:2.2Collection 常用方法说明2.3 Collection 示例2.4 Map 常用方法说明2.5 Map 示例 3.实现 classes 集合框架及背后的数据结构 1.介绍 Java 集合框架 Java Collection Framework, 又被称为容器 container ,是定义在 java.util 包下的一组接口 interfaces 和其他类 classes . 类和接口总览 2.接口 interfaces 2.1基本的关系解释: Collection :用来存储管理一组对象 objects ,这些对象一般被成为元素elementsSet : 元素不能重复,背后隐含着查找/搜索的语义SortedSet : 一组有序的不能重复的元素L
    admin 昨天
  • 一文搞懂MySQL索引数据结构
    其他

    一文搞懂MySQL索引数据结构

    前言 当我们在查询数据慢的情况下第一个想到的会是添加索引,索引在数据库的实际应用场景中十分常见,数据库的优化也离不开对索引的优化。而且索引相关的知识也是面试频率非常高的点之一,因此,本文将从基础理论出发,介绍MySQL按照逻辑角度的索引分类和实现。通过索引数据结构的实现原理阐述不同结构对建立索引带来的优劣势,希望通过这篇文章能给大家带来收获。 SQL执行慢的原因分析 磁盘空间不足、内存不足、I/O吞吐量小或者网络差等原因。表没有创建索引或者索引已经失效。分库分表也会带来SQL慢的原因服务器调优及各个参数设置 # 定位原因的步骤 开启慢查询日志,并且设置多长时间的阈值就是慢查询,执行SQL语句,查看慢查询日志有哪些SQL是比较慢的。定位到慢日志以后,使用Explain对SQL分析,看是否语句写得不合理,没有添加索引,或者关联查询太多等原因。使用Show Profile(5.0开始支持),Show Pro
    admin 昨天
  • 线性表结构(2)
    其他

    线性表结构(2)

    文章目录 一、单列表的定义二、建立单链表2.1 头插法2.2 尾插法 三、查找结点值3.1 按值查找3.2 按序号查找 一、单列表的定义 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; 为了方便操作,我们一般引入头结点,头结点的指针域指向单链表的第一个元素的结点。 引入头节点后,可以带来两个优点: 由于开始节点的位置被存放在头节点的指针域中,所以在链表的第一个位置上操作与表其他位置上的操作一致,无需进行特殊处理。无论链表是否为空,其头指针都是指向头节点的非空指针(在空表中,头节点的指针域为空),因此也使得空表和非空表的处理方式变得统一。 二、建立单链表 2.1 头插法 typedef int ElemType; LinkList CreateLink(LNode *he
    admin 昨天
  • (图)的简单创建和理解
    其他

    (图)的简单创建和理解

            这里只给大家简单的介绍一下图,什么是图?  大家所熟悉的链表和树 其实也都是图的一种特殊变体,既然是链表,那么就一定有节点和指针了             这就是图,有很多节点,互相连接,带箭头的线是单向的,俩个箭头的是双向的,这些线条就是他们的关系的代表称为边,可问题又来了,那么这么做有什么用呢?         其实各个节点都可以看作一个地点,比如北京到上海,需要经过很多站,但是你能保证从北京到上海只有一条路吗?那当然不可能了,所以图的作用也就凸显出来了,从各个路径中找到最合适的路径,再例如,我们常用的手机导航,每个地点就是节点,每次都会显示多条路线,我们可以自由选择其中的一条路线,每条路线就是图的边,这也是图         图的表示有两种,一种是 邻接列表 还有一个是邻接矩阵,本文主要围绕着邻接列表讲,下面就是邻接列表的图         邻接列表主要记录了每个顶点(顶点其实就是结点,一个意思)的能通向哪些顶点,并用链表记录下来,所以他的抽象数据结构分配
    admin 昨天