超多注释助你手撕指针与链表

2023-10-27 14:48
文章标签 指针 链表 注释 超多

本文主要是介绍超多注释助你手撕指针与链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

结构体也叫做更复杂的结构类型，只要类型能够做的事情，结构体也能做

struct person{char name[20];int age;char gender;float height;
}
struct person Yu; 
struct person *p;
p = &Yu;
  • 直接引用：Yu.name
  • 间接引用：p->name
  • 所以复杂结构体能够用指针间接访问，可以用变量直接访问
  • 结构体以所占空间最大的作为对齐，比如float占4字节是最大的，那么申请的内存会是4的整数倍。
// 匿名结构体只能用一次
struct node{double a;char b;int c;
}
// 结构体内存占用图如下

共用体用法

使用共用体实现ip转整数的功能

  • xxx.xxx.xxx.xxx -> 每个xxx都是0-255
#include <stdio.h>
union IP{// 共用体共用一片内存！！！// ip和四个char型变量共用一片内存空间struct{unsigned char a1;unsigned char a2;unsigned char a3;unsigned char a4;}ip;unsigned int num;
};
// 判定电脑是大端机还是小端机
int is_little(){int num = 1;return ((char*)(&num))[0];
}
//小端机会输出0int main(){union IP p;char str[100] = {0};int arr[4];// 判断是不是小端机printf("%d\n",is_little());while(~scanf("%s",str)){sscanf(str,"%d.%d.%d.%d",arr,arr+1,arr+2,arr+3);// 数据是小的存在低位，如果存储变成1234，数据会变化p.ip.a1 = arr[3];p.ip.a2 = arr[2];p.ip.a3 = arr[1];p.ip.a4 = arr[0];printf("%u\n",p.num);}return 0;
}
  • 在网络传输的时候要看主机字节序，网络字节序和主机字节序可能会不一样，所以需要进行一定的转码。

##指针和地址

  • 什么是地址？相当于生活中的家庭地址。64位操作系统地址标号是0- 2 64 − 1 2^{64}-1 264−1， 32位操作系统地址标号是0- 2 32 − 1 2^{32}-1 232−1 。在32位操作系统中，最多只能给4GB的内存进行标记。64位基本没有上限。
  • 变量是用来存储值的，不同类型的变量存储不同的值，指针变量也是变量。指针变量能够接收的值是地址。
  • 指针变量能够接收到的地址是一个指向某种数据类型的地址int *p= &a 定义指针变量，定义完之后进行*p 可以取值。假设a = 123 打印输出*p = 123
  • **一个指针变量占几个字节呢？**在32位操作系统中占4字节，64位操作系统中占8字节。 现在默认是64位操作系统的字节。int ** q = &p q是指向指针p的指针，就是指向指针的指针。浮点数和int都是8byte，其实是可以用指针进行互相表示的，int的指针也能存储float的地址。精度不会有变
  • 一个指针变量占几个字节，一定要严谨！
  • 指针的等价转换：*p = a* （从数组上说）p + 1==&p[1]（从结构体上说） p->filed = (*p).filed = a.filed
  • int *f(int) 这是返回值是一个指针的函数 int(*f)(int) 是一个函数指针
#include <stdio.h> 
struct Data{int x,y;
};
// a[2]是用结构体定义的数组
#define P(func){\printf("%s = %d\n",#func,func);\
}int main(){struct Data a[2], *p = a;a[0].x = 0, a[0].y = 1;a[1].x = 2, a[1].y = 3;// 不想多说，但还可以更多P(a[1].x);P(p[1].x);P((*(p+1)).x);P((p+1)->x);P((&a[1])->x);P((&p[1])->x);P(((&a[0])+1)->x);P(((&p[0])+1)->x);P((*((&a[0])+1)).x);P((*((&p[0])+1)).x);
}

##链表

  • C语言地址能够唯一地标记某个对象。数组下标其实本质上也是一种地址。下标是一种相对地址的概念，或者是用引用实现搜索链表下一个的东西，表示数组元素距离第一个元素的距离。我们已经知道指针相当于是某个数据的引用int*p = &a，就是一种引用。

  • 只要在结构中添加了指针域，就可以把所有的东西串成一链。

  • 链表包含数据域和指针域。链表中的每个节点，通过指针域的值，形成一个线性结构。查找节点O(n), 插入和删除是O(1) 不适合快速的定位数据，适合动态地插入和删除数据的应用。单向链表只有一个指针域，可以一直向后，不能向前查找。双向链表可以前后查找，每个节点有两个指针。链表就是链表，虽然说链表加了一个指针域变成两个指针域可以是双向链表，也可以是二叉树，但是在思维逻辑上说，数和链表其实不太沾边，差很多，只是在实现的时候比较像。Java中没有指针，但是有引用。

  • 几种经典的链表实现方法：

    // 第一种
struct Node{// 构造函数，构造Node函数对象的时候希望传入一个data数据Node(int data) :data(data),next(NULL) {}int data;//指针域  Node* next;
};int main(){Node *head =NULL;// 通过这些构造链表， 不纠结语法// new 能够返回对象的一个地址head = new Node(1);head->next = new Node(2);head->next->next= new Node(3);head->next->next->next= new Node(4);Node *p = head;while(p !=NULL){printf("%d->",p->data);p = p->next;}printf("\n");return 0;
}

  • // 第二种
// 分别实现的是数据域和指针域
int data[10];
// 指针域，对应的data[1]存储1节点的值，next[1]存储它指向下一个节点的地址（在这里是数组的相对地址）
int next[10];// 在index节点处添加地址（数组下标）为p的节点,地址为p的节点存储的是value
void add(int ind, int p,int value){// 以下这句话保证链表能够在中间被插入，没有下面这句话就没有办法在链表中间插入// 只能在末尾插入，或者是插入之后，这个元素就是最后的值，它之后的元素都消失了next[p] = next[ind];// p是这阵next[ind] = p;data[p] = value;return ;
}int main1(){int head = 3;// 构造链表data[3] = 0;add(3,5,1);add(5,2,2);add(2,7,3);add(7,9,100);add(5,6,7);int p = head;while (p!=0){printf("%d->",data[p]);p = next[p];   }printf("\n");return 0;
// 语言其实并不重要，实现方式思维的理解才重要
}

链表应用的经典场景（leetcode除外哈哈哈）

链表的应用场景1：

  • 操作系统内的动态内存分配。操作系统是把不同的内存碎片串成了一个链表，碎片与碎片之间通过指针连接。底层的动态内存分配是用链表进行管理的。

  • 缓存算法：缓存是高速设备对低速设备的一种称呼。缓存就是容硬盘上读取东西，方便进行使用，是优化读取数据的一种方法。内存中建立缓存空间。CPU在取数据的时候有两种方法，最原始的就是从硬盘取，但是速度很慢。如果把cpu经常用的数据存储到内存中之后，就变成了缓存空间，这样读取数据会快很多。cpu在读取数据的时候先到缓存中取一下，之后再到硬盘中取数据。这样比较快。

  • 缓存中的数据是如何存储的呢？就是哈希链表，或者说是链表的方法。单链表并不是底层实现的方式。新加数据就是直接用链表插入，删除就直接指针去除就可以了。就像下面的图所示
    - [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-26cg88j4-1615825757227)(C:\Users\sakura\Desktop\奋斗吧cv\门徒\week1链表\Snipaste_2021-03-04_21-12-04.png)]

  • LRU缓存淘汰算法：如果查找到了，就是缓存命中。如果查不到的话，就会淘汰掉最早放在缓存中的数，让要查找的数组。

Leetcode链表

  • 链表一直都是一种绵里藏针的东西，不要看它就是一个铁索连环，但是指针的移动真的会让人头大。下面终于开始leetcode的学习了。
LeetCode #141 环状链表
  • 采用双指针做法，使用使用快慢指针，快指针一次向前2个节点，慢指针一次向前1个节点。主要基于以下重要结论。
    有环的链表中 快指针和慢指针最终一定会在环中相遇
    无环的链表中 快指针会率先访问到链表尾 从而终结检测过程
class Solution {
public:bool hasCycle(ListNode *head) {// 如果只有一个节点以下，就直接返回了，没有环if(head == NULL || head->next == NULL) return false;// 快慢指针定义ListNode *p = head,*q = head;do{// p每次走一步，q每次走两步p = p->next;q = q->next->next;}while(p != q && q && q->next);// 用下面两句话会超时// 不可以用两个if语句一起写return 否则会出现编译不过的情况if ((q==nullptr) || (q->next ==nullptr)) return 0;else return 1;// 或者可以返回下面的这句话，下面这句话意思是，如果q和q->next都不是空地址，就直接返回1// return q && q->next;}
};
LeetCode #142 环状链表II

  • 双指针同上，具体解题方法如下图：

  • 考虑快慢指针第一次相遇的情况（设此时慢指针走的路程为x）-> 指定一个指针p放置在链表头部（p每次向前1个节点）-> 再走一个路程为x的长度-> 慢指针到达了2x的位置->指针p到达了x的位置->慢指针和p相遇了->往前回放一下 在环的入口开始一起向前直到相遇
    在这里插入图片描述


class Solution {public:ListNode *detectCycle(ListNode *head) {// 如果没有环，返回空地址if (head == nullptr) return nullptr;// 这一行也可以让p从头开始，q从头指针的下一个节点开始ListNode *p = head, *q = head;// 返回空节点if (q->next == nullptr) return nullptr;// 因为第一步的时候两个节点是一个位置do {p = p->next;q = q->next->next;// 判断所有的东西都不是空，也不是相等} while (p != q && q && q->next);// 如果都是空了，就返回空节点，说明没有环if (q == nullptr || q->next == nullptr) return nullptr;p = head;// 相遇在环的起始位置，q还需要再走a步。while (p != q) p = p->next, q = q->next;return q;}
};
LeetCode #202 快乐数

  • 思路：转化为判断链表是否有环的问题
    收敛性的证明
    32位int的表示正整数大概是21亿( 2 31 − 1 2^{31}-1 231−1)

    • 在这个范围内 各位数字平方和最大的数是1999999999 和为730
    • 根据鸽巢原理（pigeonhole’s principle，也译作抽屉原理）在730次循环后必定出现重复

    从收敛性性质可以知道，这个快乐书是有环的。那么只要找到它能不能到1，或者说

class Solution {public:int getNext(int x) {int z = 0;// 把所有的值进行每一位相乘while (x) {z += (x % 10) * (x % 10);x /= 10;}return z;}bool isHappy(int n) {// p只当前数字int p = n, q = n;do {// p，q进行快慢行进p = getNext(p);q = getNext(getNext(q));// 链表判定是不是空} while (p != q && q != 1);// 如果出现循环又没有1，就返回false了	return q == 1;}
};
LeetCode #206 翻转链表
  • 使用虚拟头结点来进行头插法
  • 进行递归翻转
// 递归翻转
class Solution {public:ListNode *reverseList(ListNode *head) {// 如果头指针是空或者只有一个节点，直接返回头指针if (head == nullptr || head->next == nullptr) return head;// 先记录后一个节点的地址，翻转head和nextListNode *tail = head->next, *p = reverseList(head->next);// 链表头尾翻转head->next = tail->next;// 接过去了tail->next = head;// p是用来记录翻转之后链表的头结点,返回之后就不动了,一直都是返回同样的值return p;}
};

class Solution {
public:ListNode* reverseList(ListNode* head) {// 只有一个节点，直接返回头结点if(head==nullptr || head->next==nullptr) return head;// 定义前一个节点，要翻转的节点还有翻转节点的下一位ListNode *pre = nullptr, *cur = head,*p = head->next;// 如果现在要翻转的节点不是空的话，空的节点说明到了最底了while(cur ){cur->next= pre;pre = cur;// && 的短路做用(cur=p) && (p = p= p->next);// 等价与上面那句话// if(cur=p){//     p= p->next;// }// p= p->next);     }return pre;}
};
LeetCode #92 反转链表II
  • 使用虚拟头结点，防止头结点因为链表的翻转而改变
// 先找到要翻转的头一位,之后调用翻转头n个节点的函数,翻转之后再让一节点指针指向被翻转之后的链表的头结点
class Solution {public:
// 前面的这个定义符号相当于int,是一种struct类型
// 递归翻转节点之后的n个元素ListNode *reverseN(ListNode *head, int n) {// 递归出口if (n == 1) return head;// 调用递归，把翻转的尾节点定义一下ListNode *tail = head->next, *p = reverseN(head->next, n - 1);// 链表翻转head->next = tail->next;tail->next = head;return p;}ListNode *reverseBetween(ListNode *head, int m, int n) {// 定义一个链表,这个是通过line_10 定义的,传入一个变量x=0,之后定义头结点的指针// 把p指向头结点的地址,方便返回ListNode ret(0, head), *p = &ret;// 翻转之后的节点int cnt = n - m + 1;// 先跑到要应该翻转的链表的前一个位置,这个是虚头// 注意是--m,就是跑到要翻转的节点的前一个位置while (--m) p = p->next;// 进行后n位置的链表翻转p->next = reverseN(p->next, cnt);return ret.next;}
};
LeetCode #25 K个一组翻转链表
  • 先判断是否有K个元素 然后对这K个节点进行反转 最后拆装一下首尾部分
  • 三段论解题法：
    • 首先完成翻转n个链表的函数
    • 之后完成判定链表能不能翻转的函数，并把能够翻转的链表翻转了
    • 最后完成不断循环翻转的函数
class Solution {public:ListNode *__reverseN(ListNode *head, int n) {if (n == 1) return head;// p是用来记录头结点的指针变量,就是翻转之后的头结点ListNode *tail = head->next, *p = __reverseN(head->next, n - 1);head->next = tail->next;tail->next = head;return p;}// 这个是定义这个函数?ListNode *reverseN(ListNode *head, int n) {ListNode *p = head;int cnt = n;// 判断是不是足够n个节点while (--n && p) p = p->next;// 要返回头结点if (p == nullptr) return head;return __reverseN(head, cnt);}ListNode *reverseKGroup(ListNode *head, int k) {// p是要翻转的数组的前一位，q是要翻转数组的第一位// 下面这一句话是初始化ListNode ret(0, head), *p = &ret, *q = p->next;// 这个翻转的表达式不是空的时候,等于q表示没有发生翻转,因为只有翻转之后量表的两个指针才会有位置不同的变化// 最骚最骚的while ((p->next = reverseN(q, k)) != q) {p = q;q = p->next;}return ret.next;}
};
LeetCode #61 旋转链表

  • 先让指针走到链表的最后一位，并计算出链表的长度。

  • 计算出链表要向右移动多少位。链表在右移的时候需要进行一下计算

    • k%= cnt; k = cnt-k;

  • 将头指针向右移动k位，之后，把k-1位的那个节点断开，变成空。这样就起到右移节点的目的了。

class Solution {public:
//  先找到最后一个节点,把链表形成环,之后找到要断掉的指针,断掉就变成了一个链表ListNode *rotateRight(ListNode *head, int k) {// 处理一下空链表if (head == nullptr) return nullptr;int n = 1;ListNode *p = head;// 先走到最后一位// n用来记录链表长度while (p->next) p = p->next, n += 1;// 把头尾连起来p->next = head;// k需要处理,原地转圈得去掉k %= n;// 这个是剩余的要走的步数,这个是循环右移动k = n - k;// 循环左移就是kwhile (k--) p = p->next;head = p->next;// 断开指针p->next = nullptr;return head;}
};
LeetCode #24旋转链表
  • 这道题我现在还是有点懵逼，尽力画了，理解了原理，但是自己要写还是不太会
class Solution {
public:ListNode* swapPairs(ListNode* head) {// 递归出口if (head == nullptr || head->next == nullptr) {return head;}ListNode* newHead = head->next;// 调换的是newhead后面的那两个节点head->next = swapPairs(newHead->next);newHead->next = head;return newHead;}
};

在这里插入图片描述

LeetCode #19 删除链表的倒数第N个节点
  • 思路，定义两个指针，一个指针先超前走n步，之后另一个指针向前走，
    当前一个指针走到null的时候，后面的指针就到了倒数第n个节点
  • 要特别注意一下几个代码
  • n-- 是代表向前走了n步，之后p是走到要删除节点的前一位才可以
class Solution {
public:
// 思路，定义两个指针，一个指针先超前走n步，之后另一个指针向前走，
// 当前一个指针走到null的时候，后面的指针就到了倒数第n个节点ListNode* removeNthFromEnd(ListNode* head, int n) {// 头结点有可能变化，要变一下虚拟头结点ListNode ret(0,head);ListNode *p= &ret,*q= head;// 向前走了n步while(n--) q = q->next;// 走到了要删除节点的前一位while(q) p = p->next,q = q->next;// 删除节点p->next = p->next->next;// 返回虚拟头结点return ret.next;}
};
LeetCode #83 删除排序链表中的重复节点
  • 先判断链表是不是空！！！！！！！！！！！！！！！！！！！！！
  • 定义一个指针p，如果p和p->next指向的值是一样的话，就把p指向下一位的下一位
  • 如果值不一样，就直接向后走一步
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {// 头结点不删，也不变，直接保留// 第一句空的要保留，不然又会报错了。在写题目的时候一定要保证// 空指针的判断！！！！！！！！！！！！！if (head==nullptr) return nullptr;ListNode* p = head;while(p->next) {if(p->val == p->next->val){p->next = p->next->next;}else{p = p->next;}}return head;}
};
LeetCode #82 删除排序链表中的重复节点II
  • 首先头结点可能会变，需要设置一个虚拟头结点
  • 在进行节点删除的时候，要注意p从虚拟头结点开始出发
  • 剩下的请自行看代码
class Solution {public:
//  穿进去的是头地址
// 虚拟头结点要用在链表头地址可能改变的情况
// 多了它之后会少了很多边界条件的判断ListNode *deleteDuplicates(ListNode *head) {// 首先设置虚拟头结点,p指向虚拟头ListNode ret(0, head), *p = &ret, *q;// 有下一个节点的时候,先判断是否产生了重复while (p->next) {// 这两个判定的顺序是不能更改的if (p->next->next && p->next->val == p->next->next->val) {q = p->next->next;// 出现值重复的情况,就是q下一个值和下一个下一个的值相等,除去多余的指针while (q && q->val == p->next->val) q = q->next;// p->next = q;} else {// 没有出现重复的情况p = p->next;}}return ret.next;}
};

这篇关于超多注释助你手撕指针与链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/286367。

相关文章

csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...
vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

vscode中文乱码问题，注释，终端，调试乱码一劳永逸版

忘记咋回事突然出现了乱码问题，很多方法都试了，注释乱码解决了，终端又乱码，调试窗口也乱码，最后经过本人不懈努力，终于全部解决了，现在分享给大家我的方法。 乱码的原因是各个地方用的编码格式不统一，所以把他们设成统一的utf8. 1.电脑的编码格式 开始-设置-时间和语言-语言和区域 管理语言设置-更改系统区域设置-勾选Bata版：使用utf8-确定-然后按指示重启 2.vscode
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
【C++学习笔记 20】C++中的智能指针

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别，使用new关键字创建变量时，需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时，不必自己去调用delete，甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针，是一种作用域指针，意思是当指针超出该作用域时，会自动调用delete。它名为unique的原因是这个
阅读更多...
C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员，我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书，我不敢乱推荐，尤其是国内作者写的书，往往七拼八凑，漏洞百出。 但是，李忠老师的《C语言非常道》值得一读。对了，李老师有个官网，网址是： 李忠老师官网 最棒的是，有配套的教学视频，可以试看。 试看点这里 接下来言归正传，讲解指针。以下内容很多都参考了李忠老师的《C语言非
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
C和指针：字符串

C和指针：字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符，并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string)，指向的string是常量不能修改。size_t是无符号数，定义在stddef.h。 #include <stddef.h>
阅读更多...
【C++】作用域指针、智能指针、共享指针、弱指针

【C++】作用域指针、智能指针、共享指针、弱指针

十、智能指针、共享指针 从上篇文章 【C++】如何用C++创建对象，理解作用域、堆栈、内存分配-CSDN博客 中我们知道，你的对象是创建在栈上还是在堆上，最大的区别就是对象的作用域不一样。所以在C++中，一旦程序进入另外一个作用域，那其他作用域的对象就自动销毁了。这种机制有好有坏。我们可以利用这个机制，比如可以自动化我们的代码，像智能指针、作用域锁(scoped_lock)等都是利用了这种机制。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2