数据结构基础——线性表的基本操作(纯基础）基本结构首先我们声明我们所使用的数据类型(也可不做此声明，后续的dataType换成你所用的类型即可)typedefintdataType;定义基本数据结构，数组or链表//数组表示typedefstruct{vectorval;//vector定义//或dataType*val;//指针形式定义intlength;}Array;//链表形式typedefstructnode{dataTypeval;structnode*next;}Node;typedefstruct{Node*head;intlength;}List;后续的基本操作中我们也会对两种
408数据结构Linear线性表Linklist链表一·Single_linked_list.cpp单链表1.单链表结构体typedefstructLNode{//单链表结构体Elemtypedata;structLNode*next;}LNode,*LinkList;2.初始化单链表boolInitList(LinkList&L){//初始化单链表L=(LNode*)malloc(sizeof(LNode));if(L==NULL)returnfalse;L->next=NULL;returntrue;}3.初始化循环单链表boolInitList(LinkList&L){//初始化循环单链
408数据结构Linear线性表Linklist链表一·Single_linked_list.cpp单链表1.单链表结构体typedefstructLNode{//单链表结构体Elemtypedata;structLNode*next;}LNode,*LinkList;2.初始化单链表boolInitList(LinkList&L){//初始化单链表L=(LNode*)malloc(sizeof(LNode));if(L==NULL)returnfalse;L->next=NULL;returntrue;}3.初始化循环单链表boolInitList(LinkList&L){//初始化循环单链
1、总结切记：书上过程是下标从1开始的。不要纠结next数组第一位为什么是0。（DP也不纠结边界为啥是0啊。。。）。 完整过程：求PM[]。（部分匹配表）求move[]。（要移动的位数）求next[]。（子串中移动后的下标）简化过程：求PM[]。右移1位加1（下标从1开始要加，下标从0开始不用加）优化后的KMP看程序，一步一步算。主串在后面，子串在前面。2、代码String数据结构//串的堆分配存储结构（malloc()占用的是堆空间）//下标为0的位置不用typedefstruct{char*ch;//若是非空串，则按串长分配存储区；否则ch为NULLintlength;//串长度}HStr
21.合并两个有序链表（MergeTwoSortedLists）将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1：输入：l1=[1,2,4],l2=[1,3,4]输出：[1,1,2,3,4,4]示例2：输入：l1=[],l2=[]输出：[]示例3：输入：l1=[],l2=[0]输出：[0]提示：两个链表的节点数目范围是[0,50]-100l1和l2均按非递减顺序排列方法1：递归思路与算法我们可以如下递归地定义两个链表里的merge操作（忽略边界情况，比如空链表等）：也就是说，两个链表头部值较小的一个节点与剩下元素的merge操作结果合并。我们直
相信不少人在学数据结构的时候都被KMP算法搞的迷迷糊糊的，原理看的似懂非懂，代码写不出来，或者写出来了也不知道为什么就可以这么写。本文力求尽可能通俗详细的讲解KMP算法，让你不再受到KMP算法的困扰。暴力匹配的痛点所谓暴力匹配，就是从文本串的首端开始依次检查子串是否与模式串匹配，如果不匹配就将模式串往后移一个位置，从头开始匹配，直到在某处成功匹配或匹配到末尾也没能成功匹配。如下图：设文本串为T，模式串为P，i为文本串中的下标，j为模式串中的下标，文本串的长度为m，模式串的长度为n，则代码如下：intbruteForce(std::stringt,std::stringp){inti=0,j=0
1、总结切记：书上过程是下标从1开始的。不要纠结next数组第一位为什么是0。（DP也不纠结边界为啥是0啊。。。）。 完整过程：求PM[]。（部分匹配表）求move[]。（要移动的位数）求next[]。（子串中移动后的下标）简化过程：求PM[]。右移1位加1（下标从1开始要加，下标从0开始不用加）优化后的KMP看程序，一步一步算。主串在后面，子串在前面。2、代码String数据结构//串的堆分配存储结构（malloc()占用的是堆空间）//下标为0的位置不用typedefstruct{char*ch;//若是非空串，则按串长分配存储区；否则ch为NULLintlength;//串长度}HStr
21.合并两个有序链表（MergeTwoSortedLists）将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例1：输入：l1=[1,2,4],l2=[1,3,4]输出：[1,1,2,3,4,4]示例2：输入：l1=[],l2=[]输出：[]示例3：输入：l1=[],l2=[0]输出：[0]提示：两个链表的节点数目范围是[0,50]-100l1和l2均按非递减顺序排列方法1：递归思路与算法我们可以如下递归地定义两个链表里的merge操作（忽略边界情况，比如空链表等）：也就是说，两个链表头部值较小的一个节点与剩下元素的merge操作结果合并。我们直
相信不少人在学数据结构的时候都被KMP算法搞的迷迷糊糊的，原理看的似懂非懂，代码写不出来，或者写出来了也不知道为什么就可以这么写。本文力求尽可能通俗详细的讲解KMP算法，让你不再受到KMP算法的困扰。暴力匹配的痛点所谓暴力匹配，就是从文本串的首端开始依次检查子串是否与模式串匹配，如果不匹配就将模式串往后移一个位置，从头开始匹配，直到在某处成功匹配或匹配到末尾也没能成功匹配。如下图：设文本串为T，模式串为P，i为文本串中的下标，j为模式串中的下标，文本串的长度为m，模式串的长度为n，则代码如下：intbruteForce(std::stringt,std::stringp){inti=0,j=0
最近集中刷了一批链表的题型，在这里总结一下解题技巧，以及对应题目的解题思路。解题思路并不会细致入微，主要是为了总结归类，并且希望用几句话来激发灵感，权当是没思路时的指引以及以后复习时的提纲了。还有一些重要或者总会绕晕的经典题目，也在这里记录一下代码的实现逻辑。一、解决链表题型的两个技巧遇到链表相关的题，无论问题是什么，先要想想是不是可以用上以下的两个技巧。哨兵节点双指针1、哨兵节点哨兵节点是一个非常常用的链表技巧，在处理链表边界问题的场景下，可以减少我们代码的复杂度。主要解决的问题如下：处理完一条链表后，需要返回这个链表的头结点。我们在一开始的时候使用哨兵节点（dummy），让它的next节点
