辽宁建网站,海东高端网站建设,同wordpress,佛山注册公司无需地址数据结构----结构–线性结构–链式存储–链表
1.链表的特点
空间可以不连续#xff0c;长度不固定#xff0c;相对于数组灵活自由
搜索#xff1a;
时间复杂度O(n)
增删:
头增头删时间复杂度O(1)
其他时间复杂度为O(n)
扩展#xff1a;单向循环链表的特性
从任意节…数据结构----结构–线性结构–链式存储–链表
1.链表的特点
空间可以不连续长度不固定相对于数组灵活自由
搜索
时间复杂度O(n)
增删:
头增头删时间复杂度O(1)
其他时间复杂度为O(n)
扩展单向循环链表的特性
从任意节点出发皆可遍历整个链表
2.链表的组成
链表由数据域和指针域组成
3.链表及其功能的实现
1.创建一个链表并查看每一个链表中所存的值
//在Visual Studio 2022编译器下的用c语言的写法
#include stdio.h
#includestdlib.htypedef struct Node {int nValue;struct Node* pNext;}List;List* list() {List* m_phead NULL;List* m_tail NULL;int len;printf(请输入链表长度\n);scanf_s(%d, len);while (len) {List* PTemp(List*)malloc(sizeof(List));printf(请输入数据\n);int value;scanf_s(%d, value);PTemp-nValue value;PTemp-pNext NULL;if (m_phead) {//不是空节点m_tail-pNext PTemp;}else {//是空节点m_phead PTemp;}m_tail PTemp;len--;}return m_phead;
}void ShowList(List* m_phead) {while (m_phead) {printf(%d , m_phead-nValue);m_phead m_phead-pNext;}
}int main() {List* list1list();ShowList(list1);printf(\n);ShowList(list1);return 0;
}思考如何将链表反向打印不破环原有链表结构
方法
1.暴力 时间复杂度O(n的平方) 空间复杂度O(1)
2.交换 时间复杂度O(n的平方) 空间复杂度O(看怎么使用交换来确定)
3.栈 时间复杂度O(n) 空间复杂度O(n)
4.头插法造新链表 时间复杂度O(n) 空间复杂度O(n)
5.数组 时间复杂度O(n) 空间复杂度O(n)
6.递归 时间复杂度O(n) 空间复杂度O(n)
这里用递归进行实现
//此函数的定义及其实现依赖于上面的链表代码
void ReserveList(List* head) {if (head-pNext NULL) {//如果到了最后一个节点printf(%d , head-nValue);//打印该节点return;//返回}ReserveList(head-pNext);//先处理下一个printf(%d , head-nValue);//打印当前节点
}
2.将链表进行反转用不消耗空间的方法
消耗空间的方法
1.栈
2.数组
3.递归
4.头插法创建一个新链表
不消耗空间的方法
用三个指针来实现
1.分别记三个指针为头拿断
2.处理1插入 将拿的指针所指的节点的下一个节点改为头指针所指向的节点
2改变标记:头的指针所指向的节点变为拿的指针所指向的节点
拿的指针所指向的节点变为断的指针所指向的节点
断的指针所指向的节点为断的指针所指向的节点的下一个节点
代码实现
//此函数的定义及其实现依赖于上面的链表代码
List* FanZhuan(List* P_head) {if (P_head NULL || P_head-pNext NULL) return P_head;List* NewHead NULL;List* Na P_head;List* Duan P_head-pNext;while (Duan) {Na-pNext NewHead;NewHead Na;Na Duan;Duan Duan-pNext;}Na-pNext NewHead;return Na;
}3.将两个链表进行合并且按照链表中数据的大小进行排序
方法
1.定义两个指针一个确定新表头之后指向新表头后续会对这个指针进行操作一个指向新表头之后进行返回
2.处理用传入的两个指针比较两链表之后在新链表进行尾添加然后相应的指针移到下一个节点直到两个指针中的其中一个指针指向为空结束循环
3.将有剩余链表与新链表的尾部进行连接
代码实现
//此函数的定义及其实现依赖于上面的链表代码
List* HeBing(List* list1_head, List* list2_head) {if (!list1_head) {return list2_head;}if (!list2_head) {return list1_head;}List* newHead NULL;List* HEAD NULL;if (list1_head-nValue list2_head-nValue) {//确定表头newHead list1_head;HEAD newHead;list1_headlist1_head-pNext;}else {newHead list2_head;HEAD newHead;list2_head list2_head-pNext;}while (list1_head list2_head) {//循环判断拼接链表if (list1_head-nValue list2_head-nValue) {newHead-pNext list1_head;newHead newHead-pNext;list1_head list1_head-pNext;}else {newHead-pNext list2_head;newHead newHead-pNext;list2_head list2_head-pNext;}}if (list1_head) {newHead-pNext list1_head;}if (list2_head) {newHead-pNext list2_head;}return HEAD;
}4.链表题目的练习
第一题网址为https://leetcode.cn/problems/LGjMqU/
题目
给定一个单链表 L 的头节点 head 单链表 L 表示为
L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。
解决
方法一
暴力不用这个
方法二
第一步将这个链表从中间拆成两个链表如果不是偶数长度则前一个链表比后一个长一个节点
第二步翻转第二个链表
第三步将两个链表进行合并合并的方法为先第一个链表的节点再第二个链表的节点以此类推
代码如下
//这里的代码是c语言下的
class Solution {
public:void reorderList(ListNode* head) {if(head-nextnullptr) return;int listsize0;ListNode* headsizehead;while(headsize){//判断链表长度listsize;headsizeheadsize-next;}if(listsize2){//如果链表长度为2结束return;}headsizenullptr;//将链表分成两个 int listsize2listsize/2; //链表2长度int listsize1listsize-listsize2;//链表1长度ListNode* Tempnullptr;ListNode* head1head;//链表一头节点ListNode* head2head;//链表二if(listsize11){//将链表一与链表二断开 1Temphead1;}while(listsize1--){//遍历获得链表二头节点head2head2-next;if(listsize11){Temphead2;//记录链表一的尾节点 }}Temp-nextnullptr;//将链表一与链表二断开 2Tempnullptr;ListNode* Temp1nullptr;ListNode* Temp2nullptr;//将链表二进行翻转//链表长度大于1进行翻转if(listsize21){ListNode*NewlistHeadnullptr;ListNode*Nahead2;ListNode*Duanhead2-next;while(Duan){Na-nextNewlistHead;NewlistHeadNa;NaDuan;DuanDuan-next;}Na-nextNewlistHead;//将两链表进行拼接 第一种Temp1head1;Temp2Na;}else{//不大于1//将两链表进行拼接 第二种Temp1head1;Temp2head2;}while(1){ListNode* Temp3Temp1-next;Temp1-nextTemp2;Temp1Temp3;if(Temp2nullptr||Temp1nullptr){break;}ListNode* Temp4Temp2-next;Temp2-nextTemp1;Temp2Temp4;}}
};第二题网址为https://leetcode.cn/problems/3u1WK4/
题目
给定两个单链表的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。
解决
方法一
暴力不用这个 用的时间和空间太多了
方法二
栈 两个链表出栈时进行比较看是否有相同的
方法三
差值法
第一步遍历两个链表获得两个链表的长度
第二步进行相减获得长度差
第三步长的那个先走长度差的距离之后两个指向链表的指针一起走
如果两个指针指向相同的节点时结束找到了。
如果两个链表指向空地址了还没找到结束没找到。
这里用方法三来写方法三的代码如下
//这里的代码是c语言下的
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int headAsize0;int headBsize0;ListNode*headA1headA;ListNode*headB1headB;int x0;while(headA1){headAsize;headA1headA1-next;}while(headB1){headBsize;headB1headB1-next;}headA1headA;headB1headB;if(headAsizeheadBsize){xheadAsize-headBsize;while(x--){headA1headA1-next;}}else{xheadBsize-headAsize;while(x--){headB1headB1-next;}}while(1){if(headA1headB1) return headA1;if(headA1nullptr||headB1nullptr) return 0;headA1headA1-next;headB1headB1-next;}}
};第三题网址为https://leetcode.cn/problems/c32eOV/
题目
给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。
为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 仅仅是用于标识环的情况并不会作为参数传递到函数中。
**说明**不允许修改给定的链表。
解决
方法一
快慢指针 第一步用快慢指针找到交点如果找不到节点就是无环
第二步将交点断开之后要还原
第三步定义从交点和起始点开始的两个指针遍历获得长度
第四步进行相减获得长度差
第五步长的那个先走长度差的距离之后两个指向链表的指针一起走
两个指针指向相同的节点时返回该节点。
方法二
将链表进行翻转将链表每一次要翻转的链表进行一个存储用指针数组存之后在存储的这个指针数组中数组的头和尾一起往中间遍历当第一次找到不一样的节点时返回上一次的节点就是入环点
方法三
数学推导法 经过推导得 a(R-1)(bc)c
所以得出只要用两个指针指向A点和C点并且同时同速度出发最后就会在B点相遇可得入环点
这里用方法一来写方法一的代码如下
//这里的代码是c语言下的
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(headnullptr){//如果没节点返回空无环return head;}if(head-nextnullptr){//如果只有一个节点返回空无环return 0;}//定义快慢指针ListNode *Fasthead;ListNode *Slowhead;//定义一个指针指向交点ListNode *JiaoDiannullptr;ListNode *JiaoDian2nullptr;//快慢指针进行遍历找到交点while(1){if(Fast-nextnullptr){//如果快指针会指向为空无环return Fast-next;}else if(Fast-next-nextnullptr){return Fast-next-next;}FastFast-next-next;SlowSlow-next;if(FastSlow){//找到交点JiaoDianFast;JiaoDian2SlowSlow-next;//断点的下一个Fast-nextnullptr;//将交点断开一会要还原break;}}//定义从交点和起始点开始的指针ListNode *StartJiaoSlow;ListNode *Starthead;//遍历两个指针获得长度int StartJiaolen0;int Startlen0;while(StartJiao){//起点开始的长度StartJiaolen;StartJiaoStartJiao-next;}while(Start){//断点开始的长度Startlen;StartStart-next;}StartJiaoSlow;//回到起点Starthead;int chalen0;//相差长度if(StartJiaolenStartlen){chalenStartJiaolen-Startlen;while(chalen--){//移动交点指针StartJiaoStartJiao-next;}}else{chalenStartlen-StartJiaolen;while(chalen--){//移动开始指针StartStart-next;}}while(1){//移动找到入口点if(StartStartJiao){JiaoDian-nextJiaoDian2;return Start;}if(Start-nextnullptr||StartJiao-nextnullptr){return 0;}StartStart-next;StartJiaoStartJiao-next;}}
};第四题网址为https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/
题目
请实现 copyRandomList 函数复制一个复杂链表。在复杂链表中每个节点除了有一个 next 指针指向下一个节点还有一个 random 指针指向链表中的任意节点或者 null。
解决
方法一
暴力 时间复杂度为O(n的平方) 时间太久不用此方法
方法二
第一步创建一个新链表实现了next指针
第二步将两个链表交叉合并
第三步实现random指针
第四步将两个链表分开还原
第五步返回新链表
时间复杂度为O(n) 空间复杂度为O(1)
代码如下
//这里的代码是c语言下的
class Solution {
public:Node* copyRandomList(Node* head) {if(headnullptr){return head;}Node* BianLihead;//用于遍历原来链表的指针Node* NewHeadnullptr;//新链表Node* Tempnullptr;//用来指向新链表的表头//添加完成新链表random指针还没有实现NewHeadTempNewNode(*BianLi);//表头BianLiBianLi-next;while(BianLi){Node* Temp2NewNode(*BianLi);BianLiBianLi-next;Temp-nextTemp2;TempTemp-next;}//将两个链表相交连接TempNewHead;//重置 用于遍历新链表的指针BianLihead;//重置 用于遍历原来链表的指针while(1){Node* LinShi1BianLi-next;//临时变量BianLi-nextTemp;BianLiLinShi1;if(BianLinullptr){break;}Node* LinShi2Temp-next;//临时变量Temp-nextBianLi;Temp LinShi2;}//将random指针实现Node* Temp3head;//用于遍历合并后两个链表的指针int bool11;//判断是不是原有链表的节点while(1){//循环将复制的节点的复杂指针实现if(bool1%21){if(Temp3nullptr){//结束条件break;}if(Temp3-randomnullptr){//如果指向为空那对应的就给空这里是因为我合并的那个链表只有一个nullptrTemp3-next-randomnullptr;}else{Temp3-next-randomTemp3-random-next;}}Temp3Temp3-next;bool11;}//将两个链表进行拆分Temp3head;//重置 用于遍历合并后两个链表的指针while(1){if(Temp3nullptr){//终止条件break;}Node* LinShi1Temp3-next;//临时变量if(Temp3-nextnullptr||Temp3-next-nextnullptr){//最后两个数据的处理Temp3-nextnullptr;}else{Temp3-nextTemp3-next-next;}Temp3LinShi1;}return NewHead;}//造新节点Node* NewNode(Node node){Node*newnode(Node*)malloc(sizeof(Node));newnode-valnode.val;newnode-nextnullptr;newnode-randomnullptr;return newnode;}
};5.如何判断一个数字是不是2的整数次幂此题与链表无关
整数为n 用n(n-1)看是否等于0等于0就是2的整数次幂
6.找到一个数二进制是1的一位随机的找是1的一位此题与链表无关
整数为n 用n(-n)就可以找到了
7.跳跃列表SkipList并不是一个链表结构
跳跃列表基于有序链表
1.跳表查找的实现
1.根据链表的长度判断有几层 层数log2的链表长度
2.每一层有哪些元素是根据概率来定的每一个元素是否有的概率都是二分之一
3.然后找数是从高层往低层找 在每一层跟链表中的元素做比较大于就取右边小于就取左边等于就是找到了这一步和二分类似
4.到最后一层看是否找到
2.跳表添加的实现
1.根据链表的长度判断有几层 层数log2的链表长度
2.每一层有哪些元素是根据概率来定的每一个元素是否有的概率都是二分之一
3.然后从高层往低层 依次找到要添加的元素在每层该插入的地方并存起来
4.根据概率判断每一层是否都有这个元素概率是二分之一
5.进行插入
8.哈希表散列表hashTable
1.确定分组
用求整取余法 公式为Pkey%M(M是个数) 会产生哈希冲突问题
2.定哈希冲突解决方案
1.开放定址法
1.线性探测
2.二次探测
2.拉链法
第一步定义一个链表结构体
第二步申请指针数组数组中每个元素初值为空
第三步元素入组头插法
第四步查找
用拉链法实现简单哈希表代码如下此代码是用c语言写的
#include stdio.h
#includestdlib.h
#includewindows.h
typedef struct Node {int nValue;struct Node* pNext;}List;List* list() {List* m_phead NULL;int len 1;int date;printf(请输入数据\n);scanf_s(%d, date);m_phead (List*)malloc(sizeof(List));m_phead-nValue date;m_phead-pNext NULL;return m_phead;
}//申请指针数组
List** Array(int n) {List** array_head (List**)(malloc(sizeof(List*) * n));memset(array_head, 0, (sizeof(List*) * n));return array_head;
}
//头插法
void pushhead(List* lst, List** arr) {lst-pNext (*arr);*arr lst;
}//元素入组
void TianJia(int x,int n, List* lst, List** arr) {int weiyi x % n;List** temp arr;while (weiyi--) {temp;}if (*temp) {pushhead(lst, temp);}else {*temp lst;}
}void ShowList(List* m_phead, int x) {while (m_phead) {if (m_phead-nValue x) {printf(找到了);printf(%d, x);return;}m_phead m_phead-pNext;}printf(没找到);
}
//查找
void find(int x, int n, List** arr) {int y x % n;arr y;ShowList(*arr, x);
}int main() {int n 5;//申请指针数组List** arrArray(n);List* lsti1 list();TianJia(lsti1-nValue,n, lsti1, arr);//元素入组List* lsti2 list();TianJia(lsti2-nValue, n, lsti2, arr);//元素入组List* lsti3 list();TianJia(lsti3-nValue, n, lsti3, arr);//元素入组List* lsti4 list();TianJia(lsti4-nValue, n, lsti4, arr);//元素入组List* lsti5 list();TianJia(lsti5-nValue, n, lsti5, arr);//元素入组find(2, n, arr);//查找元素return 0;
}3.线性探测的优化
装载因子 α元素/表长 0.8 越趋近于0.8冲突的可能性越高
优化的方法就是申请的空间大些尽量让装载因子小于0.8
4.拉链法与线性探测优化各自的优势
拉链法
1.处理冲突简单
2.删除数据容易
3.适用于未知元素个数的情况
4.处理元素所占空间大且多的情况用的空间少
线性探测优化
处理元素所占空间小且少的情况用的空间少 文章转载自： http://www.morning.qgfy.cn.gov.cn.qgfy.cn http://www.morning.mxhcf.cn.gov.cn.mxhcf.cn http://www.morning.yjtnc.cn.gov.cn.yjtnc.cn http://www.morning.hdqqr.cn.gov.cn.hdqqr.cn http://www.morning.a3e2r.com.gov.cn.a3e2r.com http://www.morning.qwbls.cn.gov.cn.qwbls.cn http://www.morning.dqrpz.cn.gov.cn.dqrpz.cn http://www.morning.plchy.cn.gov.cn.plchy.cn http://www.morning.tqbqb.cn.gov.cn.tqbqb.cn http://www.morning.wbxbj.cn.gov.cn.wbxbj.cn http://www.morning.dmlgq.cn.gov.cn.dmlgq.cn http://www.morning.ftzll.cn.gov.cn.ftzll.cn http://www.morning.kghhl.cn.gov.cn.kghhl.cn http://www.morning.pycpt.cn.gov.cn.pycpt.cn http://www.morning.nbnq.cn.gov.cn.nbnq.cn http://www.morning.qnbzs.cn.gov.cn.qnbzs.cn http://www.morning.fhrt.cn.gov.cn.fhrt.cn http://www.morning.rmtxp.cn.gov.cn.rmtxp.cn http://www.morning.wdnkp.cn.gov.cn.wdnkp.cn http://www.morning.hdnd.cn.gov.cn.hdnd.cn http://www.morning.dfmjm.cn.gov.cn.dfmjm.cn http://www.morning.ccdyc.cn.gov.cn.ccdyc.cn http://www.morning.rycd.cn.gov.cn.rycd.cn http://www.morning.tqpnf.cn.gov.cn.tqpnf.cn http://www.morning.fgsqz.cn.gov.cn.fgsqz.cn http://www.morning.kyfrl.cn.gov.cn.kyfrl.cn http://www.morning.tqjwx.cn.gov.cn.tqjwx.cn http://www.morning.rcgzg.cn.gov.cn.rcgzg.cn http://www.morning.xnnxp.cn.gov.cn.xnnxp.cn http://www.morning.yqfdl.cn.gov.cn.yqfdl.cn http://www.morning.knmby.cn.gov.cn.knmby.cn http://www.morning.httpm.cn.gov.cn.httpm.cn http://www.morning.jgnjl.cn.gov.cn.jgnjl.cn http://www.morning.mqbsm.cn.gov.cn.mqbsm.cn http://www.morning.nyfyq.cn.gov.cn.nyfyq.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.kynf.cn.gov.cn.kynf.cn http://www.morning.tgxrm.cn.gov.cn.tgxrm.cn http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.lywys.cn.gov.cn.lywys.cn http://www.morning.mgbsp.cn.gov.cn.mgbsp.cn http://www.morning.lwtfx.cn.gov.cn.lwtfx.cn http://www.morning.mxtjl.cn.gov.cn.mxtjl.cn http://www.morning.rksnk.cn.gov.cn.rksnk.cn http://www.morning.rtpw.cn.gov.cn.rtpw.cn http://www.morning.tbplf.cn.gov.cn.tbplf.cn http://www.morning.synkr.cn.gov.cn.synkr.cn http://www.morning.mxnfh.cn.gov.cn.mxnfh.cn http://www.morning.nlwrg.cn.gov.cn.nlwrg.cn http://www.morning.mjctt.cn.gov.cn.mjctt.cn http://www.morning.rsxw.cn.gov.cn.rsxw.cn http://www.morning.bpmnx.cn.gov.cn.bpmnx.cn http://www.morning.rkkpr.cn.gov.cn.rkkpr.cn http://www.morning.swyr.cn.gov.cn.swyr.cn http://www.morning.rhpy.cn.gov.cn.rhpy.cn http://www.morning.hqllj.cn.gov.cn.hqllj.cn http://www.morning.qcdtzk.cn.gov.cn.qcdtzk.cn http://www.morning.qqhersx.com.gov.cn.qqhersx.com http://www.morning.pccqr.cn.gov.cn.pccqr.cn http://www.morning.cprbp.cn.gov.cn.cprbp.cn http://www.morning.lsbjj.cn.gov.cn.lsbjj.cn http://www.morning.drrt.cn.gov.cn.drrt.cn http://www.morning.xcdph.cn.gov.cn.xcdph.cn http://www.morning.hhboyus.cn.gov.cn.hhboyus.cn http://www.morning.nmngq.cn.gov.cn.nmngq.cn http://www.morning.bmsqq.cn.gov.cn.bmsqq.cn http://www.morning.lhyhx.cn.gov.cn.lhyhx.cn http://www.morning.xppj.cn.gov.cn.xppj.cn http://www.morning.ppghc.cn.gov.cn.ppghc.cn http://www.morning.xfyjn.cn.gov.cn.xfyjn.cn http://www.morning.hpggl.cn.gov.cn.hpggl.cn http://www.morning.ngdkn.cn.gov.cn.ngdkn.cn http://www.morning.qrqg.cn.gov.cn.qrqg.cn http://www.morning.gfhng.cn.gov.cn.gfhng.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.dwfzm.cn.gov.cn.dwfzm.cn http://www.morning.bqmhm.cn.gov.cn.bqmhm.cn http://www.morning.nmtyx.cn.gov.cn.nmtyx.cn http://www.morning.lkjzz.cn.gov.cn.lkjzz.cn http://www.morning.lwmxk.cn.gov.cn.lwmxk.cn
