一.线性表的基本运算 1.线性表的初始化 status InitList_sq(sqLIst &L) {     //构造一个空的顺序表L     L.elem=new ElemType[MAXSIZE] //为顺序表分配空间     if(!L.elem)  exit(OVERFLOW)  //存储失败     L.Length=0;    //空表长度为0     return ok; } 2.销毁链表L void DestroyList (sqList &L) {         if(L.elem)     delete L.elem; //释放存储空间 } 3.清空线性表L void ClearList(sqList L) {     L.lemgth=0; //将线性表的长度置为0； } 4.求线性表L的长度 int GetLength(sqList L) {       return (L.length); } 5.判断线性表L是否为空 int LsEmpty(Sqlist L) {     if(L.length==0)     return 1;     else     return 0; } 二.顺序表的基本运算 1.顺序表的取值（根据位置i获取相应位置数据元素的内容） int GetElem(sqLList L,int i,ElemType &e) {     if(i<1||i>L.Lemgth)     return ERROR; //判断i值是否合理，若不合理返回ERROR     e=L.elem[i-1];     //第i-1的单元存储着第i个元素     return ok; } 时间复杂度T(n)=O(1) 2.顺序表的查找 在线性表L中查找与指定值e相同的数据元素的位置。 从表的一端开始逐个进行记录的关键字和给定值的比较，找到返回该元素的位置序号，未找到返回。 int LocateElem(sqLlst,ElemType e) {     //在线性表L中查找值为e的数据元素，返回其序号     for(i=0;i    if(L.elem[i]==e)     return ok; } 2.平均查找长度ASL（Average Search Length）          为了确定记录在表中的位置，需要与给定元值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。          对含有n个记录的表查找时：   pi 第一个记录被查找的概率  ci 找到第i个记录需要比较的次数  3.顺序表的插入 插入位置在最后。顺序表必须用连续空间，只能插入到最后一个元素后面。  插入位置在中间： 从最后一个元素向后移动。  插入元素在最前面：从第一个元素开始向后移动。  算法：  status ListLnsert_sq(SqList &L,int i,ElemType e) {     if(i<1||i>L.length+1)     return ERROR;  //i的值不合法     if(L.length==MAXSIZE)     return ERROR;        //判断当前存储空间是否已满     for(j=L.length-1;j>=i-1;j--)     L.elem[j+1]=L.elem[j];   //插入位置及之后的元素后移     L.elem[i-1]=e;  //将新元素e放入第i个位置     L.length++;     //表长增加     return ok; }  时间复杂度T(n)=O(n)  4.顺序表的删除 删除位置在最后：直接删除 删除位置在中间 将后面的元素依次向前移 删除位置在前面 将后面的元素依次前移 status ListDelea_sq(sqList &L,int i){     if(i<1||i>L.length)     return ERROR;  //i值不合法     for(j=i;j<=L.length-1;j++)     L.elem[j-1]=L.elem[j];  //被删除元素之后元素后移     L.length--;    //表长减一     return ok; }  时间复杂度: T(n)=O(n)  空间复杂度：S(n)=O(1)  顺序表的优点：  存储密度大。（存储密度=结点本身所占存储量/结点结构所占存储量） 可以随机存取表中任意元素 顺序表的缺点：  插入，删除某一个元素时，需要移动大量元素 浪费存储空间 属于静态存储形式，数据元素的个数不能自由扩充  ———————————————— 版权声明：本文为CSDN博主「bit..」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/weixin_68773927/article/details/127365905 

 一、题目描述 给定一个字符串 s ，请你找出其中不含有重复字符的「最长子串」的长度。  二、测试样例 2.1 测试样例一 输入: s = "abcabcbb"  输出: 3  说明: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。  2.2 测试样例二 输入: s = "bbbbb"  输出: 1  说明: 因为无重复字符的最长子串是 "b"，所以其长度为 1。  2.3 测试样例三 输入: s = "pwwkew"  输出: 3  说明: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。  注意：答案必须是「子串 」的长度，"pwke" 是一个子序列，不是子串。  三、算法思路 本题要求计算的是子串，需要与子序列进行区分。子串是连续的，子序列可以不连续。  遍历整个数组，通过一个标记数组 vis 来标记字符最后出现的位置，使用一个变量 rt 记录最右边不重复的元素，每次计算最长的不重复子串的长度，记录最大值。  四、代码实现 代码实现如下所示：  #include  #include  #include  #include  using namespace std;   class Solution { public:     int lengthOfLongestSubstring(string s) {         int rt = -1;         int num = 0;         int ans = 0;         int vis[127];         memset(vis, -1, sizeof(vis));         for(int i = 0; i < s.size(); i++) {             if(vis[s[i]] != -1) {                 num = i - max(rt, vis[s[i]]);                 rt = max(rt, vis[s[i]]);             } else {                 num++;             }             ans = max(ans, num);             vis[s[i]] = i;         }         return ans;     } };   int main() {     Solution obj;     string str = "zwnigfunjwz";     cout<      return 0; }  五、复杂度分析 5.1 时间复杂度 时间复杂度：O(n)，其中，n 表示字符串 s 的长度，在上述算法中，只进行了一次 for 循环，所以时间复杂度为 O(n)。  5.2 空间复杂度 空间复杂度：为开辟的数组 vis[127]，用于标记字符的位置。  六、总结  本地主要考查对字符串的理解，需要理解子串和子序列的区别。 ———————————————— 版权声明：本文为CSDN博主「Linux猿」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/nyist_zxp/article/details/127157572 

 #include #include #include #define MAX 100   #define Error 0 #define True 1 typedef float Num;//为防止以后变换操作数类型需要  typedef struct {     Num data[MAX];     int top; }StackNum;//运算数栈  typedef struct {     char data[MAX];     int top; }StackChar;//运算符栈    void InitNum(StackNum* p) {     p->top = 0; } void InitChar(StackChar* p) {     p->top = 0; } void PushNum(StackNum* p, Num e) {     if (p->top == MAX)         printf("运算数栈满！\n");     else     {         p->data[p->top] = e;         p->top++;     } } void PushChar(StackChar* p, char e) {     if (p->top == MAX)         printf("运算符栈满！\n");     else     {         p->data[p->top] = e;         p->top++;     } } void PopNum(StackNum* p, Num* e) {     if (p->top == 0)         printf("运算数栈空！\n");     else     {         p->top--;         *e = p->data[p->top];     } } void PopChar(StackChar* p, char* e) {     if (p->top == 0)         printf("运算符栈空！\n");     else     {         p->top--;         *e = p->data[p->top];     } } void Fun(StackNum* p, char e) {     Num temp1, temp2;//存放两个临时操作数      PopNum(p, &temp2);     PopNum(p, &temp1);     switch (e)     {     case '+':PushNum(p, temp1 + temp2); break;     case '-':PushNum(p, temp1 - temp2); break;     case '*':PushNum(p, temp1 * temp2); break;     case '/':PushNum(p, temp1 / temp2); break;       } } Num GetNum(StackNum p) {     return p.data[p.top - 1]; }   void main() {     int i;//循环变量     Num temp;//存放一个临时转换数     char str[MAX], ch;//存放中缀表达式原式，临时运算符      //-----------     StackNum n1;     StackChar c1;     InitNum(&n1);     InitChar(&c1);     //------------       for (;;)     {         int j;//判断变量         j = 1;         printf("请输入中缀表达式：");         gets(str);         /*         注意字符串输入函数与scanf("%s",str) 的区别，scanf遇到空白字符，         包括空格，制表符，换行符时均会停止输入，所以不可取,而gets功能为读入一行，         并将换行符转换为字符串结束符。         */         for (i = 0;str[i] != '\0'; i++)//读完整字符串-----字符串结束标志'\0'          {             if (str[i] >= '0' && str[i] <= '9')//分岔点一：如果为数字              {                 temp = str[i] - '0';//-----将字符转换为数值                      while (str[i + 1] != '\0')//多位数值获取                  {                     if (str[i + 1] >= '0' && str[i + 1] <= '9')                     {                         temp = temp * 10 + str[i + 1] - '0';//------注意！                            i++;                     }                     else                         break;//如果不是多位数字，则跳出多位获取循环                  }                 PushNum(&n1, temp);//将获取来的数值入栈              }             else if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '(' || str[i] == ')')//分岔点二：如果为运算符              {                 switch (str[i])//表达式可为：整型/字符型/枚举型-----C语言中                  {                     //case 后可为 整型，字符型----C语言中                  case '+':                     if (c1.data[c1.top - 1] != '+' && c1.data[c1.top - 1] != '-' && c1.data[c1.top - 1] != '*' && c1.data[c1.top - 1] != '/')                     {                         PushChar(&c1, '+');                     }                     else//如果不然，则将之前的先都出栈并计算，然后再入栈                     {                         while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高                          {                             PopChar(&c1, &ch);                             Fun(&n1, ch);//计算，并压运算数栈                           }                         PushChar(&c1, '+');                     }                     ; break;                 case '-':                     if (c1.data[c1.top - 1] != '+' && c1.data[c1.top - 1] != '-' && c1.data[c1.top - 1] != '*' && c1.data[c1.top - 1] != '/')                     {                         PushChar(&c1, '-');                     }                     else//如果不然，则将之前的先都出栈并计算，然后再入栈                     {                         while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高                          {                             PopChar(&c1, &ch);                             Fun(&n1, ch);//计算，并压运算数栈                           }                         PushChar(&c1, '-');                     }                     ; break;                 case '*':                     if (c1.data[c1.top - 1] != '*' && c1.data[c1.top - 1] != '/')                     {                         PushChar(&c1, '*');                     }                     else//如果不然，则将之前的先都出栈并计算，然后再入栈                     {                         while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高                          {                             PopChar(&c1, &ch);                             Fun(&n1, ch);//计算，并压运算数栈                           }                         PushChar(&c1, '*');                     }                     ; break;                 case '/':                     if (c1.data[c1.top - 1] != '*' && c1.data[c1.top - 1] != '/')                     {                         PushChar(&c1, '/');                     }                     else//如果不然，则将之前的先都出栈并计算，然后再入栈                     {                         while (c1.top > 0 && c1.data[c1.top - 1] != '(')//将优先级高的运算符先输出计算，其中括号内的优先级最高                          {                             PopChar(&c1, &ch);                             Fun(&n1, ch);//计算，并压运算数栈                           }                         PushChar(&c1, '/');                     }                     ; break;                 case '(':                       PushChar(&c1, '(');                       ; break;                 case ')'://并没有将')'压入栈中，只是当作一种出栈信号                      while (c1.data[c1.top - 1] != '(')                     {                         PopChar(&c1, &ch);                         Fun(&n1, ch);//计算，并压运算数栈                     }                     PopChar(&c1, &ch);//将'('也出栈，但并不计算                      ; break;                 }             }             else//其余输入判定为错误             {                 printf("输入错误\n");                 j = 0;                 break;             }         }         while (c1.top > 0)//将剩余的运算符出栈并计算          {             PopChar(&c1, &ch);             Fun(&n1, ch);         }         if (j == 1)         {             printf("\t\t%s=%.2f", str, GetNum(n1));             printf("\n");         }         else {             printf("\n");         }         system("pause");     }   }  通过栈的各种基本操作求值中缀表达式，编写实现栈基本操作的程序，将中缀表达式化为后缀表达式，进而求出中缀表达式的值。  中缀表达式是一个通用的算法或逻辑表达式，形如（6+8）*9-1，较易被人类大脑理解并使用，是我们常用的算式表达方式。运算法则即为“先算乘除，后算加减，有括号先算括号里的”。而对于计算机来说，中缀表达式无法被识别，编程者需要通过程序代码的编写，将表达式转化分解为后缀表达式进行计算。所谓后缀表达式，即为运算数在前，运算符在后，有别于人类思维结构较易理解的中缀表达式，这种表达式更易被计算机语言理解。以该中缀表达式的转换为例可以直观看出后缀表达式的特点。  (a+b)*c-(a+b)/e的后缀表达式为：  (a+b)*c-(a+b)/e  →((a+b)*c)((a+b)/e)-  →((a+b)c*)((a+b)e/)-  →(ab+c*)(ab+e/)-  →ab+c*ab+e/-  后缀表达式运算符优先级：{ (, ) } > { *, / } > { +, - }。注意，同级运算中，先出现的（左侧）优先级高。  那我们在电脑上为什么可以按照我们的想法去运算中缀形式的运算式呢？原因在于计算机程序设计者为了方便我们使用，在电脑上已经预先封装好了相应的运算程序，而我们要做的就是将这个封装的程序进行再现。  程序实现主要依靠栈结构。需要创建数字栈和运算符栈两个栈，并以运算符栈作为程序进行控制的主导，比较压入栈中运算符的优先级，如果栈顶运算符优先级高于栈内其他运算符，就弹出数字进行相应计算，并将运算结果压入栈，继续运行。遇到“）”就将与“（”之间的符号及相应数字弹出运算，再将结果压入。核心概括来说就是利用栈结构，将中缀表达式分解为后缀表达式的分部形式进行运算。  （2）实现原理  Ⅰ 建立两个栈，其中左边的栈，暂存操作数（记为S1）；右边的栈，暂存运算符（记为S2）。从左到右，扫描中缀表达式。  Ⅱ 遇到操作数，则入S1栈；遇到左括号，则入S2栈；如遇到运算符，则准备入S2栈。入栈前须进行如下判断：  ①若S2栈为空或S2栈的栈顶为左括号，则运算符可直接入S2栈。  ②若当前运算符的优先级大于栈顶运算符，则可如S2栈。  ③若当前运算符的优先级小于等于栈顶运算符，则现将栈顶运算符出栈，直到当前运算符的优先级大于栈顶运算符，即可如S2栈。  ④若运算符为右括号，则将S2中从栈顶到左括号的所有运算符均出栈。  总结：S2栈每出栈一个运算符，则S1栈出栈两个操作数进行一次运算，其中先出栈的操作数位于运算符右边，后出栈的运算符位于运算符左边，计算出结果并入栈S1。当整个中缀表达式全部扫描完后，S2栈中依旧有运算符，则将所有运算符出栈，最后在S1栈顶的数即为整个表达式的求值结果。  （3）实验步骤  首先编写有关栈的各种操作的程序 操作数栈和运算符栈的初始化：  void InitNum(StackNum *p)  { p->top = 0;  }  运算符和操作数入栈：  void PushNum(StackNum *p, Num e)  { if (p->top == MAX)  printf("运算数栈满！\n");  else  { p->data[p->top] = e;  p->top++;  }  }  运算符和操作数出栈：  void PopNum(StackNum *p, Num *e)  { if (p->top == 0)  printf("运算数栈空！\n");  else  { p->top--;  *e = p->data[p->top];  }  }计算并压入运算数栈：  void Fun(StackNum *p, char e)  { Num temp1, temp2;//存放两个临时操作数  PopNum(p, &temp2);  PopNum(p, &temp1);  switch (e)  { case '+':PushNum(p, temp1 + temp2); break;  case '-':PushNum(p, temp1 - temp2); break;  case '*':PushNum(p, temp1*temp2); break;  case '/':PushNum(p, temp1 / temp2); break;  }  }取栈顶元素：  Num GetNum(StackNum p)  { return p.data[p.top - 1];  }  根据上述中缀表达式转换为后缀表达式的转换原理编写主程序 伪代码实现如下：  for(遍历所有字符){   if(数字) 输出；  else{ if(左括号)  入栈;  else if(右括号) 弹栈,一直弹到遇到一个左括号；  else{ 判断操作符优先级；  if(栈顶优先级小于当前优先级){ 压栈；  }else{ 将小于当前优先级的所有操作符出栈，然后入栈；  }  }  }  }  带入各种可能的测试数据进行测试，验证程序的运行情况、完整性和鲁棒性 在中缀表达式求值的具体实现中，我们定义了两个栈，分别是StackNum和StackChar，他们分别用来存储运算数和运算符，利用栈后进先出的特点进行计算。在构造的过程中，为了使代码更简洁可读，借助了C语言中的数组，本质上是运用了栈的顺序实现。使用运算数栈和运算符栈这两个栈实现中缀向后缀的转化并完成计算。  为了实现模块化编程，增加代码可读性，我们定义了一些函数。其中InitNum和InitChar分别用于运算数栈和运算符栈初始化，PushNum和PushChar分别用于将运算数压入栈和运算符压入栈，PopNum和PopChar分别用于将运算数和运算符压出栈。GetNum用于取栈顶元素，Fun用于计算并将结果压入运算数栈。  在主函数中，我们实现了中缀表达式向后缀表达式转换的过程，并完成了后缀表达式的计算，最终实现的是一个交互式的可持续输入中缀表达式并求值的程序，此外，我们的程序还能够处理各种输入错误。  主函数中，我们通过gets函数获得用户的中缀表达式输入。通过for循环我们逐个读取直到读完整个字符串，对每个字符进行如下处理。如果是运算数字符，我们将其转化为运算数，并且通过while循环可以实现对多位数值的获取，然后将单位运算数或多位运算数压入运算数栈。如果是运算符字符，通过switch函数分别对“+”“-”“*”“/”“(”“)”进行相应处理，此部分是本程序的核心代码部分，完成了中缀表达式向后缀表达式转化的过程和部分计算。以下是对“+”的处理，只有在空栈或最上面为“(”的时候，“+”才被压入，其他情况一概把运算符输出计算，直到全部出栈或遇到“(”才停止输出，才把“+”压入栈中。  实质上，是利用不同运算符的优先级进行处理。当运算符优先级大于栈顶运算符时，把它直接压入栈，当运算符的优先级小于或等于栈顶运算时，将栈顶运算符弹出并输出，再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压入栈中。对于左括号和右括号，将其看成特殊的运算符，左括号优先级最高直接压入运算符栈，当遇到右括号时，将栈顶的运算符弹出并输出，直到遇到左括号，将其出栈但不输出，这样处理可以实现对中缀表达式括号内算式的计算。当所有对象处理完以后，把运算符栈中剩余的运算符出栈输出完成最终计算，得出最终的结果。代码最后完成打印完整的中缀表达式求值算式。 ———————————————— 版权声明：本文为CSDN博主「ZZQHLA」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_63128704/article/details/127145589 

 1 基本算法 ​ 快速排序是一种分治的排序算法。它将一个数组分成2个子数组，将两部分独立排序。听起来和归并排序很像，那么有什么不一样呢？  ​ 快速排序和归并排序区别：  算法： 归并排序：归并排序将数组分成2个子数组分别排序，在将有序的子数组归并使整个数组有序 快速排序： 快速排序是把数组拆分为2个子数组，当2个子数组有序时，整个数组有序。 递归： 归并：递归调用发生在处理整个数组之前 快速：递归调用发生在处理整个数组之后 ​ 快速排序类Quick整体代码（初级）如下：  package com.gaogzhen.algorithms4.sort;  import edu.princeton.cs.algs4.StdRandom;  /**  * @author Administrator  * @version 1.0  * @description 快速排序  * @date 2022-09-30 21:42  */ public class Quick {     public static void sort(Comparable[] a) {         StdRandom.shuffle(a);         sort(a, 0, a.length - 1);     }      private static void sort(Comparable[] a, int lo, int hi) {         if (lo <= hi) return;         int j = partition(a, lo, hi);         sort(a, lo, j - 1);         sort(a, j + 1, hi);     }      private static int partition(Comparable[] a, int lo, int hi) {         // TODO         return 0;     } } ​ 简单说明：  StdRandom类：由算法第4版封装类 partition方法：为拆分方法，实现在下面。 partition方法关键在于切分，这个过程使得数组满足3个条件：  对于某个j，a[j]已经排定 a[lo]到a[j-1]中的所有元素都不大于a[j] a[j+1]到a[hi]中的所有元素都不小于a[j] 算法排序的证明：  因为每次切分总是能排定一个元素，用归纳法不难证明递归能够正确的将数组排序：如果左子数组和右子数组都是有序的，那么由左子数组（数组中的每个元素都不大于切分元素）、切分元素、右子数组（数组中的每个元素都不小于切分元素）组成的结果数组也一定是有序的。  切分方法具体步骤：  随意选取a[lo]为切分元素  从数组左端开始向右扫描直到找到一个大于等于切分元素的值  从数组右端开始向左扫描直到找到一个小于等于切分元素的值  交换步骤2,3找到的2个元素位置  循环执行步骤2~4  当两个指针相遇时，把切分元素和左子数组最右侧的元素交换  代码实现如下：  /**      * 拆分数组      * @param a     目标数组      * @param lo    数组左边界      * @param hi    数组有边界      * @return      切分元素索引      */     private static int partition(Comparable[] a, int lo, int hi) {         // 数组切分为a[lo..j-1],a[j],a[j+1..hi]         int i = lo, j = hi + 1;         Comparable v = a[lo];         while (true) {             // 左指针从左向右扫描，直到找到大于等于a[j]的元素或者数组最右侧             while (less(a[++i], v)) if (i == hi) break;             // 右指针从右向左扫描，直到找到小于等于a[j]的元素或者数组最左侧             while (less(v, a[--j])) if (j == lo) break;             // 如果左指针大于等于右指针，循环结束             if (i >= j) break;             // 交换a[i], a[j]2个元素位置             exch(a, i, j);         }         // 交换切分元素和a[lo]的位置，此时切分元素已排序         exch(a, lo, j);         return j;     } 完整源代码在下面代码仓库，下面有几个问题来讨论下：  1.1 原地切分 ​ 如果使用辅助数组，可以分容易实现切分，但将切分后的数组在复制会原数组开销很大。如果将空数组创建在递归方法中，那开销会更多。  1.2 边界 ​ 如果切分元素是数组中最大或者最小的元素，我们要注意指针别越界。partition()方法一般会添加检测，预防越界。其中，判断条件(j==lo)是冗余的，因为切分元素是a[lo],它不可能比自己小。数组右端也是相同情况，他们都可以去掉。  1.3 随机性 ​ StdRandom.shuffle(a)，目的就是打乱数组元素。因为算法对所有的子数组一视同仁，所以子数组也是随机的。这对于预测算法的运行时间很重要。保持随机性的另一种方法是在partition()中随机选择一个切分元素。  1.4 终止循环 ​ partition()方法中有3个循环，保证循环结束要格外小心。一个常见的错误是没有考虑数组中有包含和切分元素值相同的其他元素。  1.5 切分元素重复 ​ 如上面算法所示，左侧扫描最好是在遇到大于等于切分元素时停下，右侧扫描最好是遇到小于等于切分元素时停下。这样可能将一些等值的元素交换，但在某些应用中，可以避免算法的运行时间变为平方级别。  1.6 终止递归 ​ 保证递归正确终止，快排中一个很常见的错误不能保证将切分元素放入正确的位置，导致程序陷入无线递归或者得出错误结果。  2 备注 关于快速排序的性能和改进部分，因为涉及本人的一些盲点，暂时封存，等以后在学习，敢兴趣的可自行查阅相关书籍或者视频。  参考 书籍：[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法：第4版[M].北京：人民邮电出版社，2012.10 视频：[2]黑马程序员.Java数据结构与java算法[VD/OL].上海：B站,2022 视频地址：https://www.bilibili.com/video/BV1iJ411E7xW QQ:806797785  仓库地址：https://gitee.com/gaogzhen/algorithm ———————————————— 版权声明：本文为CSDN博主「gaog2zh」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/gaogzhen/article/details/127137845 

 B+树索引的管理 MySQL 5.5版本之前，索引的添加或者删除，MYSQL数据库的操作过程： 1.创建一张新的临时表，表结构为通过命令ALTER TABLE新定义的结构  2.把原表中的数据导入到临时表  3.删除原表  4.把临时表重命名为原来的表名  这个过程有一个明显的问题，如果是对于一张数据量很大的表进行索引的添加或者删除操作，那么会耗时很长，并且如果有大量事务需要访问正在被修改的表，此时数据库服务是不可用的。  Fast Index Creation（快速索引创建，只限于辅助索引） from InnoDB 1.0.x 对于辅助索引的创建，InnoDB存储引擎会对数据表加上一个S锁。在创建索引的过程中只能对该表进行读操作，如果有大量事务需要对表进行写操作，那么数据库服务同样不可用。  在索引创建过程中，不需要重建表，所以速度会比之前的方式有显著提升，并且创建索引期间数据库也可以提供服务。  删除索引的过程是，InnoDB存储引擎只需要更新内部视图，并将辅助索引的空间标记为可用，同时删除MySQL数据库内部视图山对该表的索引定义即可。  Online Schema Change OSC最早是由Facebook实现的一种在线执行DDL的方式，并广泛地应用于Facebook的MySQL数据库。所谓“在线”是指在事务的创建过程中，可以有读写事务对表进行操作，这提高了原有MySQL数据库在DDL操作时的并发性。  Facebook采用PHP脚本来实现OSC，而并不是通过修改InnoDB存储引擎源码的方式。  Online DDL（在线数据定义） from MySQL 5.6 其允许辅助索引创建的同时，还允许其他诸如INSERT、UPDATE、DELETE这类DML操作，这极大地提高了MySQL数据库在生产环境中的可用性。  通过新的ALTER TABLE语法，用户可以选择索引的创建方式：  ALTER TABLE table_name  | ADD {INDEX|KEY} [indexname] [indextype] (indexcolname,…) [indexoption] ...  ALGORITHM [=] {DEFAULT|INPLACE|COPY}  LOCK [=] {DEFAULT|NONE|SHARED|EXCLUSIVE}  ALGORITHM指定了创建或删除索引的算法： COPY：表示按照MySQL 5.1版本之前的工作模式，即创建临时表的方式。  INPLACE：表示索引创建或删除操作不需要创建临时表。  DEFAULT：表示根据参数oldalter_table来判断是通过INPLACE还是COPY算法，默认值是OFF，表示INPLACE。  LOCK部分为索引创建或删除时对表添加锁的情况： NONE：执行索引创建或删除操作时，对目标表不添加任何的锁，即事务仍然可以进行读写操作，不会收到阻塞。这种模式可以获得最大的并发度。  SHARE：和之前的FIC类似，执行索引创建或者删除操作时，对目标表加上一个S锁。读事务可以并发执行，写事务需要等待。  EXCLUSIVE：在该模式下，执行索引创建或删除操作时，对目标表加上一个X锁。读写事务都不行进行，即会阻塞所有的线程，这和COPY方式运行得到的状态类似，但是不需要像COPY方式那样创建一张临时表。  DEFAULT：该模式首先会判断当前操作是否可以使用NONE模式。如果不能，则判断是否可以使用SHARE模式，最后判断是否可以使用EXCLUSIVE模式。简而言之，DEFAULT会通过判断事务的最大并发性来判断执行DDL的模式。  InnoDB存储引擎实现Online DDL的原理 在执行创建或者删除操作的同时，将INSERT、UPDATE、DELETE这类DML操作日志写入到一个缓存中。待完成索引创建后再将重做应用到表上，以此达到数据的一致性。  需要特别注意的是，由于Online DDL在创建索引完成后再通过重做日志达到数据库的最终一致性，这意味着在索引创建过程中，SQL优化器不会选择正在创建中的索引。 ———————————————— 版权声明：本文为CSDN博主「lee_nacl」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/lee_nacl/article/details/126686963 

 题目链接：JZ7 重建二叉树 题目描述：给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。 前提条件： pre 和 vin 均无重复元素 vin出现的元素均出现在 pre里 只需要返回根结点，系统会自动输出整颗树做答案对比 要求：空间复杂度 O(n)，时间复杂度 O(n) 题目分析：已知前序遍历和中序遍历可以唯一确定一棵二叉树，前序遍历可以首先确定root结点，在中序遍历中找到root结点值的下标，就可以划分左右子树结点集合，以此类推，递归遍历。 递归函数功能：原函数功能（根据前序数组和中序数组重建二叉树） 递归出口：pre.length为0 或 vin.length为0 递归入口：在中序遍历数组中找到当前root值的索引，通过 Arrays.copyOfRange() 函数传pre数组和vin数组  public class Solution {     public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {         //重建二叉树         if(pre.length==0||vin.length==0){             return null;         }         TreeNode root = new TreeNode(pre[0]); //根节点         for(int i=0; i            if(vin[i]==pre[0]){                 //递归左子树                 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));                 //递归右子树                 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));             }         }         return root;     } } 题目链接：JZ54 二叉搜索树的第k个节点 题目描述：给定一棵结点数为n 二叉搜索树 ，请找出其中的第 k 小的TreeNode结点值。不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1。 题目分析： ①递归遍历。二叉搜索树左中右遍历值依次从小到大，所以我们在中序遍历的基础上，增加遍历结点个数count的限制，返回第k个最小结点。时间复杂度为O(n)， 空间复杂度为O(n)；  public class Solution {     //指向目标结点（第k个的结点）     TreeNode res = null;     //记录遍历过的结点（从最小的结点开始遍历）     private int count = 0;     //中序遍历     public void midOrder(TreeNode root, int k){         if(root==null || count>k){             return;         }         midOrder(root.left,k);         count++;         if(count==k){             res = root; //标记第k个结点         }         midOrder(root.right,k);     }     public int KthNode (TreeNode proot, int k) {         midOrder(proot, k);         if(res != null){             return res.val;         }         //二叉树为null,或第k个结点找不到         return -1;     } } ②非递归中序遍历，采用数据结构栈进行存储结点。  import java.util.*; public class Solution {     public int KthNode (TreeNode proot, int k) {         //非递归中序遍历         if(proot==null) return -1;         int count = 0;         TreeNode res = null;         Stack s = new Stack();         while(proot!=null || !s.isEmpty()){             while(proot!=null){                 s.push(proot);                 proot = proot.left;             }             TreeNode temp = s.pop();             count++;             if(count==k){                 res = temp;                 break;             }             proot = temp.right;                 }         if(res!=null){             return res.val;         }          return -1;     } } 题目链接：JZ26 树的子结构 题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构） 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}， 题目分析：采用递归比较方便，主要思路为： 1.先判断A/B任意一个根节点是否为空，边界条件。有null，直接返回false 2.两个根节点都不为空，则判断A B两棵树是否相同isSame()函数， ①递归条件：A B当前结点值相等，继续遍历其左右子树 ②终止条件：先判断B，如果B遍历到叶子结点，则遍历结束返回true；如果B遍历到不为null的结点，A为null了，则返回false 3.如果当前结点对应的两棵树不相同，则递归遍历判断A.left和A.right分别与B是否为A⊇B的关系。  public class Solution {     public boolean isSame(TreeNode root1, TreeNode root2){         //递归终止条件：先判断B，如果B遍历到叶子结点，则遍历结束返回true         if(root2==null) return true;         //如果B遍历到不为null的结点，A为null了，则返回false         if(root1==null) return false;         //A B当前结点值相等，继续遍历其左右子树         if(root1.val==root2.val){             return isSame(root1.left,root2.left) && isSame(root1.right, root2.right);         }         //没找到相同的子结构         return false;     }     public boolean HasSubtree(TreeNode root1,TreeNode root2) {         //根节点三种情况返回false：root1 root2为空,root1为空root2不为空，root1不为空root2为空         if(root1==null || root2==null){             return false;         }         return isSame(root1, root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);     } } 题目链接：JZ27 二叉树的镜像 题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。 数据范围：二叉树的节点数 0 ≤ \le≤ n ≤ \le≤ 1000， 二叉树每个节点的值 0≤ \le≤ val ≤ \le≤ 1000 要求： 空间复杂度 O(n) 。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n) 题目分析：①递归依次交换左右子树。 时间复杂度为O(n)，空间复杂度为O(1)。  public class Solution {     public TreeNode temp = null;     public TreeNode Mirror (TreeNode pRoot) {         if(pRoot==null) return pRoot;         //遍历到叶子节点的情况         if(pRoot.left==null && pRoot.right==null){             return pRoot;         }         //交换节点         temp = pRoot.left;         pRoot.left = pRoot.right;         pRoot.right = temp;         //递归遍历         Mirror(pRoot.left);         Mirror(pRoot.right);         return pRoot;     } } ②非递归遍历，交换左右子树。 时间复杂度为O(n)，空间复杂度为O(n)。  public class Solution {     public TreeNode Mirror (TreeNode pRoot) {         if(pRoot==null) return null;         Stack s = new Stack<>();         s.push(pRoot);         while(!s.isEmpty()){             TreeNode top = s.pop();             TreeNode temp = top.right;             top.right = top.left;             top.left = temp;             if(top.right!=null){                 s.push(top.right);             }             if(top.left!=null){                 s.push(top.left);             }         }         return pRoot;     } } 题目链接： JZ32 从上往下打印二叉树 题目描述：不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过) 题目分析： ①非递归实现二叉树层序遍历 (队列)  import java.util.*; public class Solution {     public ArrayList PrintFromTopToBottom(TreeNode root) {         //二叉树的层序遍历         ArrayList res = new ArrayList();         if(root==null) return res;         Deque q = new ArrayDeque();         q.offerLast(root);         res.add(root.val);         while(root!=null && !q.isEmpty()){             TreeNode top = q.pollFirst();             if(top.left!=null){                 q.offerLast(top.left);                 res.add(top.left.val);             }             if(top.right!=null){                 q.offerLast(top.right);                 res.add(top.right.val);             }         }         return res;     } }  ②递归实现二叉树层序遍历。采用二维列表数组记录每一层的结点值，最后再将值打印至一维列表中。 我们需要通过记录层数来建立二维列表中的每一行。具体代码如下：  public class Solution {     //递归调用函数     public void recursion(TreeNode root, ArrayList> list, int depth){         if(root!=null){             if(list.size() < depth){                 ArrayList row = new ArrayList<>();  //新的行                 row.add(root.val);  //添加每一行的第一个元素                 list.add(row);  //将该行添加至二维数组中             }else{                 //添加该行的其他元素                 ArrayList row = list.get(depth-1);                   row.add(root.val);             }         }else{             return;         }         recursion(root.left,list,depth+1);         recursion(root.right,list,depth+1);     }          public ArrayList PrintFromTopToBottom(TreeNode root) {         //DFS 递归实现         ArrayList res = new ArrayList<>();         //二维列表         ArrayList> list = new ArrayList>();         if(root==null){             return res;         }         recursion(root,list,1);                  for(int i=0; i            for(int j=0;j                res.add(list.get(i).get(j));             }         }         return res;     } }  ———————————————— 版权声明：本文为CSDN博主「可能是一只知更鸟」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/fxt579810/article/details/125052743 

 1、基本查找方法 基本查找核心：从0索引开始挨个往后查找  需求：定义一个方法，利用基本查找，查询某个元素是否存在  代码如下  /**  * @authorDesc  * @author  * @date   * @version 1.0.0  * @description 基本查找  * 核心：从0索引开始挨个往后查找  * 需求：定义一个方法，利用基本查找，查询某个元素是否存在  */   public class BasicSearch {     public static void main(String[] args) {         int[] numArray = {1,2,3,4,5,6,4,4};         int number = 4;         System.out.println(search(numArray,number));     }     /**      * @description      * @author       * @date       * @param numArray 数组      * @param number 要查找的数字      * @retur {@link int} 返回元素下表      */     public static int search(int[]numArray,int number){         for (int i = 0; i < numArray.length; i++) {             if (numArray[i] == number){                 return i;             }         }         return -1;     }  需求：定义一个方法，利用基本查找，查询某个元素是否存在，如果有重复的元素，把所有元素找出  /**      * @description      * @author       * @date       * @param numArray 数组      * @param number 要查找的数字      * @return {@link List} 返回元素下标集合      */     public static List search(int[]numArray,int number){         List listnum = new ArrayList<>();         for (int i = 0; i < numArray.length; i++) {             if (numArray[i] == number){                 listnum.add(i);             }         }         return listnum;     } }  2、二分查找 前提条件：数组中的数据必须是有序的  核心：每次排除一半的查找范围  代码如下  /**  * @authorDesc  * @author  * @date  * @version 1.0.0  * @description 二分查找  * 核心：每次排除一半的查找范围  * 需求：定义一个方法利用二分查找，查询某个元素是否在数组中  */   public class BinarySearch {     public static void main(String[] args) {         int [] numArray = {1,2,3,4,5,6};         int number = 3;         System.out.println(search(numArray,number));     }     /**      * @description      * @author      * @date      * @param numArray 数组      * @param number 查找的数字      * @return {@link int} 返回在数组中的下标      */     public static int search(int [] numArray, int number){         //定义两个变量记录要查找的范围 min数组第一个元素的索引，max 数组最后一个元素的索引         int min = 0;         int max = numArray.length - 1;         //利用循环查找         while (true){             if (min > max){                 return -1;             }             //找到min和max的中间值             int mid = (min + max) / 2;             // 用mid 指向的元素和要查找的元素进行比较             if (numArray[mid] > number){                 //要查找的数字在mid的左边                 //min不变， max = mid - 1                 max = mid - 1;             }else if (numArray[mid] < number){                 //要查找的数字在mid的右边                 //max不变，min = mid + 1                 min = mid + 1;             }else {                 //查找的元素和mid指向得到元素一样                 return mid;             }         }     } }  二分查找的优势：提高查找效率  二份查找条件：1、数据必须是有序的  2、如果数据是乱的，先排序再用二分法查找得到的索引没有意义，只能确定当前数字在数组中是否存在，因为排序后的数字位置发生了变化  二分查找的过程：min和max表示当前要查找的范围  mid是在min和max中间的数字  如果要查找的元素在mid左边，缩小范围时，min不变，max等于mid减1  如果要查找的元素在mid右边，缩小范围时，max不变，min等于mid减1  3、插值查找 //插值查找 int mid = min + (number - numArray[min]) /(numArray[max] - numArray[min]) * (max - min); 和二分查找相似，将中间值mid改为：  int mid = min + (number - numArray[min]) /(numArray[max] - numArray[min]) * (max - min);  4、分块查找 原则：1、前一块中的最大数据，小于后一块中的所有数据（块内无序，块间有序）  2、块数数量一般等于元素个数的开根号，比如16个数字一般分为4块  核心：先确定要查找的元素在哪一块，然后在挨个查找  代码如下  /**  * @authorDesc   * @author   * @date   * @version 1.0.0  * @description 使用分块查找数组中的元素  */   public class BlockSearch {     public static void main(String[] args) {          int[] numArray = {2,3,1,4,                         8,6,7,5,                         9,11,10,12,                         15,14,13,16};  ———————————————— 版权声明：本文为CSDN博主「qi3415」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qi341500/article/details/126688184 

 哈希值是负数的几种特殊情况 // 数组中的数据的哈希值是负数的特殊含义 static final int MOVED     = -1; // 数组正在扩容，并且当前位置的数据已经迁移到了新数组 static final int TREEBIN   = -2; // 当前索引位置上是红黑树 static final int RESERVED  = -3; // 当前索引位置已经被占了，但是值还没设置 sizeCtl // sizeCtl > 0：若当前数组没有初始化，代表初始化的长度；若数组已初始化，代表下次扩容的阈值 // sizeCtl = 0：数组数还没初始化 // sizeCtl = -1：数组正在初始化 // sizeCtl < -1：数组正在扩容  // 数组初始化和扩容的标识信息。 private transient volatile int sizeCtl; put // 若 key 已存在，则使用 value 覆盖 oldValue，并返回 oldValue public V put(K key, V value) {     return putVal(key, value, false);   }  // 若 key 已存在，什么都不做，并返回 oldValue // absent：缺席、不到场 public V putIfAbsent(K key, V value) {       return putVal(key, value, true);   } putVal put 时没有哈希冲突用 CAS，有哈希冲突用 synchronized。      final V putVal(K key, V value, boolean onlyIfAbsent) {         // key 和 value 不能为 null（HashMap key 和 value 可以为 null）         if (key == null || value == null) throw new NullPointerException();         // 根据 key 计算出 hashcode         int hash = spread(key.hashCode());         int binCount = 0;         // 死循环         for (Node[] tab = table;;) {             Node f; int n, i, fh;             // 初始化数组（HashMap 也是第一次 put 时初始化数组）             if (tab == null || (n = tab.length) == 0)                 tab = initTable();             // 下标为 i 的桶中的数据为 null 时，则以 CAS 的方式将 Node 放入桶中（不加锁）             // CAS 操作失败就再走一次循环             else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {                 if (casTabAt(tab, i, null,new Node(hash, key, value, null)))                     break;                                }             // static final int MOVED = -1;              // hashcode = -1，当前位置的数据已经迁移到了新数组             else if ((fh = f.hash) == MOVED)                 // 看看数组中是否还有没迁移的数据，帮助扩容                 tab = helpTransfer(tab, f);             else {                 // 如果以上情况都不满足，说明出现哈希冲突则利用 synchronized 写入数据                   V oldVal = null;                 // 锁住当前桶                 synchronized (f) {                     // 确认数据没有变化                     if (tabAt(tab, i) == f) {                         // 链表添加结点                         if (fh >= 0) {                             // 记录链表长度                             binCount = 1;                             // 死循环                             for (Node e = f;; ++binCount) {                                 K ek;                                 // 从桶中结点开始遍历链表校验 key 是否相同                                 if (e.hash == hash &&                                     ((ek = e.key) == key ||                                      (ek != null && key.equals(ek)))) {                                     oldVal = e.val;                                     // onlyIfAbsent 为 false 才覆盖老数据                                     if (!onlyIfAbsent)                                         e.val = value;                                     break;                                 }                                 Node pred = e;                                 // 判断是否是链表最后一个结点                                 if ((e = e.next) == null) {                                     // 将当前结点挂在链表最后                                     pred.next = new Node(hash, key,                                                               value, null);                                     break;                                 }                             }                         }                         // 红黑树添加结点                         else if (f instanceof TreeBin) {                             Node p;                             binCount = 2;                             if ((p = ((TreeBin)f).putTreeVal(hash, key,                                                            value)) != null) {                                 oldVal = p.val;                                 if (!onlyIfAbsent)                                     p.val = value;                             }                         }                     }                 }                 if (binCount != 0) {                     // static final int TREEIFY_THRESHOLD = 8;                     // 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树                     if (binCount >= TREEIFY_THRESHOLD)                         // 判断是扩容还是转红黑树                         treeifyBin(tab, i);                     if (oldVal != null)                         // 若 oldValue 有值，返回 oldValue。                         // 若 oldValue 没有值，返回 null                         return oldVal;                     break;                 }             }         }         addCount(1L, binCount);         return null;     } spread(int h) 求哈希值 // HASH_BITS 的二进制表示： 0111 1111 1111 1111 1111 1111 1111 1111 // 除了首位为 0，其他位都为 1 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash  static final int spread(int h) {     // h ^ (h >>> 16) 让 hashCode 的高 16 位参与到索引位置的计算中，从而减少哈希冲突     // 将异或操作后的哈希值对 HASH_BITS 进行 & 运算是为了保证返回的哈希值一定是正数     // 因为 CHM 中数组中的数据的哈希值如果是负数，有特殊含义     return (h ^ (h >>> 16)) & HASH_BITS;   } 1 2 3 4 5 6 7 8 9 10 initTable() 初始化数组 // 数组默认初始化长度 private static final int DEFAULT_CAPACITY = 16;  // LOAD_FACTOR 是个 static final 修饰的常量 private static final float LOAD_FACTOR = 0.75f;  private final Node[] initTable() {       Node[] tab; int sc;       while ((tab = table) == null || tab.length == 0) {         // 数组正在初始化         if ((sc = sizeCtl) < 0)              Thread.yield(); // 让出 CPU 的时间片         // 数组还未初始化，以 CAS 的方式将 sc 修改为 -1，代表数组正在初始化         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {               try {                 // DCL（Double Check Lock）                 if ((tab = table) == null || tab.length == 0) {                     // 默认初始化长度 16                      int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                       // Node 数组初始化完成                     Node[] nt = (Node[])new Node[n];                       // 依次给局部变量和成员变量赋值                     table = tab = nt;                       // 计算下次扩容的阈值。LOAD_FACTOR = 0.75 是个常量。                     // n * (1 - 1/4) = 0.75 * n;                     sc = n - (n >>> 2);                   }               } finally {                 // 局部变量 sc 赋值给成员变量 sizeCtl                 sizeCtl = sc;               }               break;           }       }    return tab;   }  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 treeifyBin() 扩容或链表转红黑树 private final void treeifyBin(Node[] tab, int index) {       Node b; int n, sc;       if (tab != null) {           // static final int MIN_TREEIFY_CAPACITY = 64;         // 若数组长度小于 64，直接扩容         if ((n = tab.length) < MIN_TREEIFY_CAPACITY)               // 扩容前的一些准备的校验             tryPresize(n << 1);           // 链表转红黑树         // 将单向链表转化为 TreeNode 对象（双向链表），再通过 TreeBin 方法转为红黑树         // TreeBin 中保留着双向链表和红黑树         else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {             synchronized (b) {                 if (tabAt(tab, index) == b) {                     TreeNode hd = null, tl = null;                     for (Node e = b; e != null; e = e.next) {                         TreeNode p =                             new TreeNode(e.hash, e.key, e.val,                                               null, null);                         if ((p.prev = tl) == null)                             hd = p;                         else                             tl.next = p;                         tl = p;                     }                     setTabAt(tab, index, new TreeBin(hd));                 }             }             }         }     } } tryPresize(int size) 扩容标识戳      private static final int MAXIMUM_CAPACITY = 1 << 30;     private static int RESIZE_STAMP_BITS = 16;     private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;     // 00000000 00000000 11111111 11111111     private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;          // treeifyBin 中调用该方法时，size 是数组长度的 2 倍     // putAll 中调用该方法时，size 是插入 map 的 size     private final void tryPresize(int size) {          // 初始化数组的长度         int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :             tableSizeFor(size + (size >>> 1) + 1);         int sc;         while ((sc = sizeCtl) >= 0) {             // n : 数组长度             Node[] tab = table; int n;             // 初始化数组             if (tab == null || (n = tab.length) == 0) {                 n = (sc > c) ? sc : c;                 // 以 CAS 的方式将 sc 修改为 -1                 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {                     try {                         // DCL                         if (table == tab) {                             Node[] nt = (Node[])new Node[n];                             table = nt;                             sc = n - (n >>> 2);                         }                     } finally {                         sizeCtl = sc;                     }                 }             }             // c 没有超过阈值或者 数组长度大于等于 MAXIMUM_CAPACITY             else if (c <= sc || n >= MAXIMUM_CAPACITY)                 break;             // 确认 table 没有被其他线程修改过             else if (tab == table) {                 // 计算扩容标识戳                 int rs = resizeStamp(n);                 // bug之1：sc 是局部变量(sc = sizeCtl)，sc 大于等于 0 才能进入 while 循环                 // 由于之前已经判断过初始化了，所以这里必是扩容                 if (sc < 0) {                     Node[] nt;                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || // 判断协助扩容的标识戳是否一致（sc 的高 16 位扩容标识戳 rs）                         sc == rs + 1 || // bug之2 这里应该是 sc == rs << RESIZE_STAMP_SHIFT + 1 判断扩容操作是否已经达到了最后的检查阶段（sc 的高 16 和 rs 相同，如果 sc 和 rs << 16 + 1 相等，则说明 sc 的低 16 位等于 1。）                                                  // MAX_RESIZERS 是 1 左移 16 位减 1 即 低 16 位都是 1                         sc == rs + MAX_RESIZERS || // bug之三，这里应该是 sc == rs << RESIZE_STAMP_SHIFT + MAX_RESIZERS 判断扩容线程是否已经达到最大值                         (nt = nextTable) == null || // 新数组为 null，说明扩容完毕，因为扩容完毕以后会将 nextTable 置为 null                         transferIndex <= 0) // transferIndex 为线程领取任务的最大结点，如果为0，代表所有老数据的迁移任务都被领完了                         break;                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))                         transfer(tab, nt);                 }                 // 第一个进来执行扩容的线程                 // 基于 CAS 的方式将 sizeCtl 从修改为 rs 左移 16 位 + 2                                  // sizeCtl : 10000000 00011010 00000000 00000010 代表三重含义                 // 1. 10000000 00011010 00000000 00000010 < -1，代表正在扩容                 // 2. 低 16 位代表正在扩容的线程数+1，此时低 16 位为 2，表示有 1 个线程正在扩容                 // 3. 高 16 位代表标识戳 rs                                    // 这么做的原因是最后一个迁移完数据的线程需要检查一遍有没有数据漏掉                 // 因为扩容分为两步，创建新数组并迁移数据                 // 当最后一个线程迁移完毕数据后，对低位 -1，最终结果低位还是 1，此时这个线程需要对整个老数组再次检查，数据是否迁移干净 recheck before commit                 else if (U.compareAndSwapInt(this, SIZECTL, sc,                                              (rs << RESIZE_STAMP_SHIFT) + 2))                     // 开始扩容，传入老数组                     transfer(tab, null);             }         }     }  resizeStamp(int n) 计算扩容标识戳 基于数组长度得到一个标识，在其他线程帮助扩容时，需要校验该标识，标识一致才可以帮助扩容。  private static int RESIZE_STAMP_BITS = 16;  // Integer.numberOfLeadingZeros(n) 返回 n 用二进制表示时，前置 0 的个数 // 1 << (RESIZE_STAMP_BITS - 1) 表示 1 左移 15 位，00000000 00000000 10000000 00000000。 // Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)) 中的 '|' 操作是为了保证当前扩容标识戳左移 16 位后一定是负数（最高位为 1）。  // 为什么要保证当前扩容标识戳左移 16 位后一定是负数？ // 跟 跟sizeCtl 有关，sizeCtl 是负数代表正在扩容。  // 假设数组长度 n=32，二进制为：0b 00000000 00000000 00000000 00100000 // Integer.numberOfLeadingZeros(32) = 26 // 26 的二进制为：0b 00000000 00000000 00000000 00011010 // 00000000 00000000 00000000 00011010 ｜ 00000000 00000000 10000000 00000000 // 00000000 00000000 10000000 00011010 static final int resizeStamp(int n) {       return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));   } transfer(tab, null) 第一个进来执行扩容的线程 计算步长 stride 初始化新数组 线程领取迁移数据任务 判断迁移是否结束 查看当前位置数据是否为 null 查看当前位置数据是否为 fwd 链表迁移数据 lastRun 机制 红黑树迁移 迁移完数据长度若小于等于 6，则转回链表 private final void transfer(Node[] tab, Node[] nextTab) {       // stride 迁移数据的步长     int n = tab.length, stride;       // static final int NCPU = Runtime.getRuntime().availableProcessors();     // private static final int MIN_TRANSFER_STRIDE = 16;     // stride = (NCPU > 1) ? (n >>> 3) / NCPU : n     // if(stride < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE;     // 若 cpu 核数 > 1，就计算每个 cpu 需要迁移的数组的下标的长度，计算公式为 n / 8 / NCPU     // 若计算得出的 stride < 16，就用 16，表示每个线程每次最少迁移16长度的数据     if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)           stride = MIN_TRANSFER_STRIDE;      // 初始化新数组     if (nextTab == null) {                     try {               Node[] nt = (Node[])new Node[n << 1];               nextTab = nt;           } catch (Throwable ex) {      // try to cope with OOME               // OOM or 数组长度溢出             sizeCtl = Integer.MAX_VALUE;               return;           }           // 将 nextTab 赋值给成员变量 nextTable         nextTable = nextTab;           // transferIndex 设置为老数组的长度          transferIndex = n;       }     //      int nextn = nextTab.length;       ForwardingNode fwd = new ForwardingNode(nextTab);       boolean advance = true;     // 扩容是否结束     boolean finishing = false; // to ensure sweep before committing nextTab     // 死循环扩容       for (int i = 0, bound = 0;;) {           Node f; int fh;           while (advance) {               int nextIndex, nextBound;               if (--i >= bound || finishing)                   advance = false;             // 说明没有任务可以领取了             // 此处将 transferIndex 赋值给 nextIndex             else if ((nextIndex = transferIndex) <= 0) {                 // 把 i 赋值为 -1，以便进入 if (i < 0 || i >= n || i + n >= nextn)                 i = -1;                   advance = false;               }             // 开始领取任务             // 基于 CAS 的方式将 nextIndex(transferIndex) 的值更新为 nextBound             else if (U.compareAndSwapInt                        (this, TRANSFERINDEX, nextIndex,                         nextBound = (nextIndex > stride ?                                      nextIndex - stride : 0))) {                   bound = nextBound;                  // 老数组长度 -1，nextIndex 就是 transferIndex 更新前的值                 i = nextIndex - 1;                 // 领取任务成功退出循环，迁移 i~bound 之间的任务                 // 举个例子 老数组长度 32，步长 stride 为 16，第一个线程领取到的任务就是32~16，换成数组下标就是31~16，其他线程可能领取到的就是 15~0 的数据的迁移任务。                 advance = false;               }           }         // 迁移完成或没有任务可以领取         if (i < 0 || i >= n || i + n >= nextn) {               int sc;               if (finishing) {                   // 结束扩容，将 nextTable 设置为 null                 nextTable = null;                   // 将迁移完数据的新数组指向老数组                 table = nextTab;                   // 将 sc 赋值为下次扩容的阈值 2 * n - n/2 = 1.5 * n                 sizeCtl = (n << 1) - (n >>> 1);                   return;               }             // 如果一个线程完成了迁移，尝试再去领取任务，若 transferIndex <= 0，所有任务已经被其他线程领走了，则把 i 设置为 -1。再执行退出扩容的操作(sc - 1)，退出扩容成功后，判断当前线程是否最后一个退出扩容的，若是，则做检查操作。             // 基于 CAS 的方式，将 sc 低位 -1，代表当前线程退出扩容             if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {                   // 判断是否是最后一个结束迁移数据的线程                 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)                       return;                   finishing = advance = true;                 // 检查老数组是否迁移完成                   i = n; // recheck before commit             }           }else if ((f = tabAt(tab, i)) == null)              // 如果迁移位置的数据为 null，则放置一个 fwd，表示数据已经迁移（最后一个线程检查时走的逻辑）             advance = casTabAt(tab, i, null, fwd);           else if ((fh = f.hash) == MOVED)               // 最后一个线程检查时走的逻辑             advance = true; // already processed           else {                 synchronized (f) {                     if (tabAt(tab, i) == f) {                         Node ln, hn;                         if (fh >= 0) {                             int runBit = fh & n;                             Node lastRun = f;                             // lastRun 机制                             // 提前循环一次链表，将结点赋值到对应的高低位 Node                             // 便于迁移最后几个都是迁移到高位或者低位的结点                             // 直接将这几个的头结点迁移过去就好了                             for (Node p = f.next; p != null; p = p.next) {                                 int b = p.hash & n;                                 if (b != runBit) {                                     runBit = b;                                     lastRun = p;                                 }                             }                             if (runBit == 0) {                                 ln = lastRun;                                 hn = null;                             }                             else {                                 hn = lastRun;                                 ln = null;                             }                             // 再次循环时，就循环到 lastRun 位置，不用继续往下循环了                             // 这样就不用每个结点都重新创建，节约资源，提升效率                             for (Node p = f; p != lastRun; p = p.next) {                                 int ph = p.hash; K pk = p.key; V pv = p.val;                                 if ((ph & n) == 0)                                     ln = new Node(ph, pk, pv, ln);                                 else                                     hn = new Node(ph, pk, pv, hn);                             }                             // 放低位                             setTabAt(nextTab, i, ln);                             // 放高位                             setTabAt(nextTab, i + n, hn);                             // 将当前桶位置设置为 fwd，代表数据已迁移                             setTabAt(tab, i, fwd);                             // 执行下次循环                             advance = true;                         }                         else if (f instanceof TreeBin) {                             TreeBin t = (TreeBin)f;                             TreeNode lo = null, loTail = null;                             TreeNode hi = null, hiTail = null;                             int lc = 0, hc = 0;                             for (Node e = t.first; e != null; e = e.next) {                                 int h = e.hash;                                 TreeNode p = new TreeNode                                     (h, e.key, e.val, null, null);                                 if ((h & n) == 0) {                                     if ((p.prev = loTail) == null)                                         lo = p;                                     else                                         loTail.next = p;                                     loTail = p;                                     ++lc;                                 }                                 else {                                     if ((p.prev = hiTail) == null)                                         hi = p;                                     else                                         hiTail.next = p;                                     hiTail = p;                                     ++hc;                                 }                             }                             ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :                                 (hc != 0) ? new TreeBin(lo) : t;                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :                                 (lc != 0) ? new TreeBin(hi) : t;                             setTabAt(nextTab, i, ln);                             setTabAt(nextTab, i + n, hn);                             setTabAt(tab, i, fwd);                             advance = true;                         }                     }                 }             } lastRun 机制图示 迁移前： ![[Pasted image 20220901204510.png]] 迁移后： ![[Pasted image 20220901204544.png]]  helpTransfer 协助扩容 final Node[] helpTransfer(Node[] tab, Node f) {       Node[] nextTab; int sc;       // 老数组不为 null，当前结点是 fwd， 新数组也不为 null     if (tab != null && (f instanceof ForwardingNode) &&           (nextTab = ((ForwardingNode)f).nextTable) != null) {           // 创建扩容标识戳         int rs = resizeStamp(tab.length);           // DCL         while (nextTab == nextTable && table == tab &&                  (sc = sizeCtl) < 0) {               if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||                   sc == rs + MAX_RESIZERS || transferIndex <= 0)                   // 上述条件有一个满足就不需要协助扩容了 break                 // sc == rs + 1 || sc == rs + MAX_RESIZERS 这里 bug 同上                 break;               // CAS sc+1 协助扩容             if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {                   transfer(tab, nextTab);                   break;               }           }                 return nextTab;       }       return table;   } 源码中的 BUG 及修复版本 不要以为源码中都是对的，然后强行解释。 - 我说的  BUG 一：sizeCtl 临时变量 sc 判断条件 此 BUG 影响不大，在 JDK 12 中修复。   int rs = resizeStamp(n);    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||                   sc == rs + MAX_RESIZERS || transferIndex <= 0)   上述这个判断条件中源码中出现多次，有问题的下面两个条件：  sc == rs + 1 || sc == rs + MAX_RESIZERS sc 的低 16 位代表正在扩容的线程数+1，此时低 16 位为 2，表示有 1 个线程正在扩容。高 16 位代表标识戳 rs。具体推断逻辑看上文源码分析。  sc == rs + 1 sc == rs + 1 是为了判断扩容操作是否已经达到了最后的检查阶段。 正确的写法应该是 sc == rs << RESIZE_STAMP_SHIFT + 1。因为 sc 的高 16 代表 rs，如果 sc 和 rs << RESIZE_STAMP_SHIFT + 1 相等，则说明 sc 的低 16 位（正在扩容的线程数）等于 1，即到了最后的检查阶段。  sc == rs + MAX_RESIZERS private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; MAX_RESIZERS 是 1 左移 16 位减 1 即 低 16 位都是 1。 sc == rs + MAX_RESIZERS 是为了判断扩容线程是否已经达到最大值。 正确的写法应该是应该是 sc == rs << RESIZE_STAMP_SHIFT + MAX_RESIZERS。  bug fix in jdk12             int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;                          if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||                 (nt = nextTable) == null || transferIndex <= 0)                 break; JDK12 中将 resizeStamp(n) 的返回值左移了 16 位以后再赋值给 rs。同时 (sc >>> RESIZE_STAMP_SHIFT) != rs 也改成了 sc == rs + MAX_RESIZERS。  BUG 二：tryPresize(int size) 中 sc < 0 的判断         // 将 sizeCtl 赋值给局部变量 sc         while ((sc = sizeCtl) >= 0) {             Node[] tab = table; int n;             if (tab == null || (n = tab.length) == 0) {                 n = (sc > c) ? sc : c;                 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {                     try {                         if (table == tab) {                             @SuppressWarnings("unchecked")                             Node[] nt = (Node[])new Node[n];                             table = nt;                             sc = n - (n >>> 2);                         }                     } finally {                         sizeCtl = sc;                     }                 }             }             else if (c <= sc || n >= MAXIMUM_CAPACITY)                 break;             else if (tab == table) {                 int rs = resizeStamp(n);                 if (sc < 0) {                     Node[] nt;                     if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||                         sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||                         transferIndex <= 0)                         break;                     if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))                         transfer(tab, nt);                 }                 else if (U.compareAndSwapInt(this, SIZECTL, sc,                                              (rs << RESIZE_STAMP_SHIFT) + 2))                     transfer(tab, null);             }         } 上述 sc < 0 的判断条件永远不可能进入，因为 sc 是 while 循环中的局部变量。sc >= 0，才会进入 while 循环。如果执行到 sc < 0，则说明之前没有对 sc 做赋值操作。所以此时 sc 肯定是大于等于 0 的。  bug fix in jdk9 private final void tryPresize(int size) {         int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :             tableSizeFor(size + (size >>> 1) + 1);         int sc;         while ((sc = sizeCtl) >= 0) {             Node[] tab = table; int n;             if (tab == null || (n = tab.length) == 0) {                 n = (sc > c) ? sc : c;                 if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {                     try {                         if (table == tab) {                             @SuppressWarnings("unchecked")                             Node[] nt = (Node[])new Node[n];                             table = nt;                             sc = n - (n >>> 2);                         }                     } finally {                         sizeCtl = sc;                     }                 }             }             else if (c <= sc || n >= MAXIMUM_CAPACITY)                 break;             else if (tab == table) {                 int rs = resizeStamp(n);                 // 主要看这里，已经不校验 sc < 0 了                 if (U.compareAndSetInt(this, SIZECTL, sc,                                         (rs << RESIZE_STAMP_SHIFT) + 2))                     transfer(tab, null);             }         }     }  BUG 三：computeIfAbsent 导致死循环 https://bugs.openjdk.org/browse/JDK-8062841 内含 Doug Lea 的回复 此 BUG 在 JDK 9 中被 Doug Lea 老爷子修复。  // https://bugs.openjdk.org/browse/JDK-8062841 中的 demo public class Test {       public static void main(String[] args) {           Map map = new ConcurrentHashMap<>(16);           map.computeIfAbsent(                   "AaAa",                   key -> map.computeIfAbsent(                           "BBBB",                           key2 -> 42)           );       }   } 该方法的意思是：当前 Map 中 key 对应的 value 不存在时，会调用 mappingFunction 函数，并且将该函数的执行结果（不为 null）作为该 key 的 value 返回。  computeIfAbsent In JDK 8     // 上文中分析过的代码此处就不再赘述了     public V computeIfAbsent(K key, Function mappingFunction) {         if (key == null || mappingFunction == null)             throw new NullPointerException();         int h = spread(key.hashCode());         V val = null;         int binCount = 0;         for (Node[] tab = table;;) {             Node f; int n, i, fh;             if (tab == null || (n = tab.length) == 0)                 tab = initTable();             else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {                 Node r = new ReservationNode();                 synchronized (r) {                     // 使用 ReservationNode 占位                     if (casTabAt(tab, i, null, r)) {                         binCount = 1;                         Node node = null;                         try {                             // 使用传入的函数 mappingFunction 计算 value                             if ((val = mappingFunction.apply(key)) != null)                                 node = new Node(h, key, val, null);                         } finally {                             // 将占位的 r 替换成上面的 node                             setTabAt(tab, i, node);                         }                     }                 }                 if (binCount != 0)                     break;             }             else if ((fh = f.hash) == MOVED)                 tab = helpTransfer(tab, f);             else {                 boolean added = false;                 synchronized (f) {                     if (tabAt(tab, i) == f) {                         if (fh >= 0) {                             binCount = 1;                             for (Node e = f;; ++binCount) {                                 K ek; V ev;                                 if (e.hash == h &&                                     ((ek = e.key) == key ||                                      (ek != null && key.equals(ek)))) {                                     val = e.val;                                     break;                                 }                                 Node pred = e;                                 if ((e = e.next) == null) {                                     if ((val = mappingFunction.apply(key)) != null) {                                         added = true;                                         pred.next = new Node(h, key, val, null);                                     }                                     break;                                 }                             }                         }                         else if (f instanceof TreeBin) {                             binCount = 2;                             TreeBin t = (TreeBin)f;                             TreeNode r, p;                             if ((r = t.root) != null &&                                 (p = r.findTreeNode(h, key, null)) != null)                                 val = p.val;                             else if ((val = mappingFunction.apply(key)) != null) {                                 added = true;                                 t.putTreeVal(h, key, val);                             }                         }                     }                 }                 if (binCount != 0) {                     if (binCount >= TREEIFY_THRESHOLD)                         treeifyBin(tab, i);                     if (!added)                         return val;                     break;                 }             }         }         if (val != null)             addCount(1L, binCount);         return val;     } bug fix in jdk9     public V computeIfAbsent(K key, Function mappingFunction) {         if (key == null || mappingFunction == null)             throw new NullPointerException();         int h = spread(key.hashCode());         V val = null;         int binCount = 0;         for (Node[] tab = table;;) {             Node f; int n, i, fh; K fk; V fv;             if (tab == null || (n = tab.length) == 0)                 tab = initTable();             else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {                 Node r = new ReservationNode();                 synchronized (r) {                     if (casTabAt(tab, i, null, r)) {                         binCount = 1;                         Node node = null;                         try {                             if ((val = mappingFunction.apply(key)) != null)                                 node = new Node(h, key, val);                         } finally {                             setTabAt(tab, i, node);                         }                     }                 }                 if (binCount != 0)                     break;             }             else if ((fh = f.hash) == MOVED)                 tab = helpTransfer(tab, f);             else if (fh == h &&                  // check first node                      ((fk = f.key) == key || fk != null && key.equals(fk)) &&                      (fv = f.val) != null)                 return fv;             else {                 boolean added = false;                 synchronized (f) {                     if (tabAt(tab, i) == f) {                         if (fh >= 0) {                             binCount = 1;                             for (Node e = f;; ++binCount) {                                 K ek;                                 if (e.hash == h &&                                     ((ek = e.key) == key ||                                      (ek != null && key.equals(ek)))) {                                     val = e.val;                                     break;                                 }                                 Node pred = e;                                 if ((e = e.next) == null) {                                     if ((val = mappingFunction.apply(key)) != null) {                                         if (pred.next != null)                                             throw new IllegalStateException("Recursive update");                                         added = true;                                         pred.next = new Node(h, key, val);                                     }                                     break;                                 }                             }                         }                         else if (f instanceof TreeBin) {                             binCount = 2;                             TreeBin t = (TreeBin)f;                             TreeNode r, p;                             if ((r = t.root) != null &&                                 (p = r.findTreeNode(h, key, null)) != null)                                 val = p.val;                             else if ((val = mappingFunction.apply(key)) != null) {                                 added = true;                                 t.putTreeVal(h, key, val);                             }                         }                         // bug fix                         else if (f instanceof ReservationNode)                             throw new IllegalStateException("Recursive update");                     }                 }                 if (binCount != 0) {                     if (binCount >= TREEIFY_THRESHOLD)                         treeifyBin(tab, i);                     if (!added)                         return val;                     break;                 }             }         }         if (val != null)             addCount(1L, binCount);         return val;     }  ———————————————— 版权声明：本文为CSDN博主「秀强」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/AlphaBr/article/details/126690815 

 定义 类似于现实中排队时的队列（队尾进，队头出），插入元素的一端称为队尾，删除（取出）元素的一端称为队头。分别对应于入队和出队操作。  队列的特点 1、元素只能从队列的一端进入，从另一端出去 通常，我们将元素进入队列的一端称为“队尾”，进入队列的过程称为“入队”；将元素从队列中出去的一端称为“队头”，出队列的过程称为“出队”。  2、队列中各个元素的进出必须遵循“先进先出”的原则，即最先入队的元素必须最先出队。  3、队列也不能直接访问位于中间的数据，必须通过出队操作将目标数据变成首位后才能访问。  队列的实际应用 解决 CPU 资源的竞争问题  对于一台计算机来说，CPU 通常只有 1 个，是非常重要的资源。如果在很短的时间内，有多个程序向操作系统申请使用 CPU，就会出现竞争 CPU 资源的现象。不同的操作系统，解决这一问题的方法是不一样的，有一种方法就用到了队列这种存储结构。  假设在某段时间里，有 A、B、C 三个程序向操作系统申请 CPU 资源，操作系统会根据它们的申请次序，将它们排成一个队列。根据“先进先出”原则，最先进队列的程序出队列，并获得 CPU 的使用权。待该程序执行完或者使用 CPU 一段时间后，操作系统会将 CPU 资源分配给下一个出队的程序，以此类推。如果该程序在获得 CPU 资源的时间段内没有执行完，则只能重新入队，等待操作系统再次将 CPU 资源分配给它。  顺序队列 顺序队列详解（C语言实现）  实现 我们采用 C 语言中的数组实现顺序表。既然用顺序表模拟实现队列，必然要先定义一个足够大的数组。不仅如此，为了遵守队列中数据从 “队尾进，队头出” 且 “先进先出” 的规则，还需要定义两个变量（top 和 rear）分别记录队头和队尾的具体位置，  缺点 在元素不断入队、出队的过程中，顺序队列会整体向顺序表的尾部移动。整个实现方案存在的缺陷是：  顺序队列前面的空闲空间无法再被使用，会造成空间浪费； 当顺序队列移动至顺序表尾部时，即便顺序表中有空闲空间，新元素也无法成功入队，我们习惯将这种现象称为“假溢出”。 循环队列 顺序队列的 “假溢出” 问题：队列的存储空间未满，却发生了溢出。比如尾指针现在虽然已经指向了最后一个位置的下一位置，但是之前队头也删除了一些元素，那么头指针经历若干次的加1之后，留出了很多空位置，但是顺序队列还在傻乎乎的以为再有元素入队就溢出呢！肯定不合理。故循环队列诞生！  所以解决"假溢出"的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。将新元素插入到第一个位置上，入队和出队仍按先进先出的原则进行，操作效率高，空间利用率高。  缺点 判空的问题，因为仅凭 front = rear 不能判定循环队列是空还是满。  链式队列 队列 使用链表形式来实现队列。  使用单向链表来实现链式队列，链式队列中存储front和rear即可。  为了方便实现，链式队列中的front表示链表的头节点，而front的next才表示队头  在链式队列中，不需要考虑队列是否已满，只要内存足够就可以一直分配空间。而当front和rear都指向头节点的时候，则表示此时队列为空。  入队时移动rear指向最后一个元素即可。  出队时，不需要移动front指针，只需将其next指针指向下一个next元素即可。q->front->next = q->front->next->next; 但是需要考虑一种特殊情况，即当队列中只剩下一个元素时，还需要使rear指针重新指向头节点。  顺序队列和链式队列的比较 顺序队列是用数组实现的，首指针在出队的时候移动，尾指针在入队的时候移动，需要考虑队列为空和队列为满的两种情况 链式队列是用链表实现的，首指针不移动始终指向头节点，尾指针在入队的时候移动，只考虑队列为空的情况（不用考虑满是因为链表长度在程序运行过程中可以不断增加，只要存储空间够malloc就能申请内存空间来存放节点） ———————————————— 版权声明：本文为CSDN博主「Htht111」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/kin_16/article/details/126690243 

 树 名词： 根的子树 根节点 :root 叶子结点：leaf 父节点 ：parent 孩子节点： child 兄弟节点： sibling 树的高度，深度 左孩子 left child 右孩子 right child 满二叉树：一个二叉树上所有非叶子结点都存在左右孩子，并且所有叶子节点都在同一层级上，，满二叉树的每一个分支都是满的 完全二叉树： 所有节点编号从1到n，，如果这个树所有节点和 同样深度的满二叉树的编号从1到n的节点位置相同，则这个树就是完全二叉树 二叉查找树：又叫二叉排序树，，binary search tree, binary sort tree  存储方式：  链式存储 ：存储数据的data，指向左孩子的left指针，，指向右孩子的 right 指针 数组 ：父节点下标 parent ,左孩子下标 2*parent+1 ,右孩子下标2*parent+2 ，。。层序遍历…对于一个稀疏的二叉树而言，用数组法表示非常浪费空间 二叉树的作用：  查找 维持相对顺序 二叉树自平衡：  红黑树 AVL树 树堆 遍历：  深度优先遍历 前序遍历 ： 根节点–左子树–右子树 中序遍历： 左子树–根节点–右子树 后序遍历： 左子树–右子树–根节点 广度优先遍历 层序遍历 ：结合队列，，将根节点放入队列，，，在出队列的时候，将父节点的所有孩子节点都放入队列 public class BinaryTree {      /**      * 二叉树的节点      */     private static class TreeNode{         int data;         TreeNode leftChild;         TreeNode rightChild;          public TreeNode(int data) {             this.data = data;         }          @Override         public String toString() {             return "TreeNode{" +                     "data=" + data ;         }     }      /**      * 构建二叉树      * @param inputList 输入序列      * @return      */ //    public static TreeNode createBinaryTree(LinkedList inputList){ //        if(inputList == null || inputList.isEmpty()){ //            return null; //        } // //        TreeNode treeNode = null; //        Integer data = inputList.removeFirst(); //        if(data != null){ //             treeNode = new TreeNode(data); //             // todo 全部到left去了 //             treeNode.leftChild = createBinaryTree(inputList); //             treeNode.rightChild = createBinaryTree(inputList); //        } //        return treeNode; //    }     public static TreeNode createBinaryTree(LinkedList inputList,TreeNode currentNode){         if(inputList == null || inputList.isEmpty()){             return null;         }          TreeNode treeNode = null;         if( currentNode == null || currentNode.leftChild == null || currentNode.rightChild == null){             Integer data = inputList.removeFirst();             if(data != null){                  treeNode = new TreeNode(data);                 if(currentNode == null){                     currentNode = treeNode;                 }else if(currentNode.leftChild == null){                     currentNode.leftChild = treeNode;                 }else if(currentNode.rightChild == null){                     currentNode.rightChild = treeNode;                 }                  createBinaryTree(inputList,currentNode);             }         }else{             createBinaryTree(inputList,currentNode.leftChild);         }          return currentNode;     }      /**      * 前序遍历      * @param node 根节点      */     public static void preOrderTraveral(TreeNode node){         if(node == null){             return;         }          System.out.println(node.data);         preOrderTraveral(node.leftChild);         preOrderTraveral(node.rightChild);     }      /**      * 中序遍历      */     public static  void inOrderTraveral(TreeNode node){         if(node == null){             return;         }         inOrderTraveral(node.leftChild);         System.out.println(node.data);         inOrderTraveral(node.rightChild);     }      /**      * 后序遍历      */     public static void postOrderTraveral(TreeNode node){         if(node == null){             return;         }         postOrderTraveral(node.leftChild);         postOrderTraveral(node.rightChild);         System.out.println(node.data);     }               public static void preOrderTraveralWithStack(TreeNode root){         Stack stack = new Stack<>();         TreeNode treeNode = root;         //          while (treeNode != null || !stack.isEmpty()){             // 遍历左孩子，，并入栈            while (treeNode != null){                System.out.println(treeNode.data);                stack.push(treeNode);                treeNode = treeNode.leftChild;            }            // 弹出栈，遍历右孩子            if(!stack.isEmpty()){               treeNode = stack.pop();               treeNode = treeNode.rightChild;            }         }     }      /**      * 层序遍历      *  将root放入队列，出队列的同时，将这个节点的孩子节点 放入队列，，，      * @param root 二叉树根节点      */     public static void levelOrderTraversal(TreeNode root){         Queue queue = new LinkedList<>();         queue.offer(root);         while (!queue.isEmpty()){             TreeNode node = queue.poll();             System.out.println(node.data);             if(node.leftChild != null){                 queue.offer(node.leftChild);             }             if(node.rightChild != null){                 queue.offer(node.rightChild);             }         }     }      // todo 层序遍历递归实现      public static void main(String[] args) {         LinkedList list = new LinkedList<>();         list.add(1);         list.add(2);         list.add(3);         list.add(4);         TreeNode root = createBinaryTree(list,null); //        System.out.println(root); //        System.out.println(root.leftChild.leftChild); //        System.out.println(root.rightChild);          preOrderTraveral(root);         System.out.println("中序遍历");         inOrderTraveral(root);         System.out.println("后序遍历");         postOrderTraveral(root);         System.out.println("前序遍历");         preOrderTraveralWithStack(root);         System.out.println("层序遍历");         levelOrderTraversal(root);     } } 二叉堆 二叉堆： 本质是完全二叉树  最大堆：任何一个父节点的值，都大于他左右孩子的值 最小堆：任何一个父节点的值，都小于他左右孩子的值 堆顶 操作：  插入节点 ：插入节点之后，一次跟他的父节点比较，看是否需要上浮 删除节点 ：将最后一个元素去暂时替代要被删除的堆顶,然后让堆顶下沉 构建二叉堆 复杂度O(n) 堆的自我调整： 把一个不符合性质的完全二叉树，调整成一个堆 存储方式：顺序存储,数组  public class BinaryHeap {      /**      * 小的上浮      * @param array  待调整的堆      */     public static void upAdjust(int[] array){         // 2*i+1         int childIndex = array.length -1;         int parentIndex = (childIndex-1)/2;          int temp = array[childIndex];          while (childIndex > 0 && temp            array[childIndex] = array[parentIndex];             childIndex = parentIndex;             parentIndex = (parentIndex -1)/2;         }          array[childIndex] = temp;     }      /**      * 大的下沉  : 上面节点和 孩子节点比较 ，，如果 大于孩子节点，就交换。。      * @param array  待调整的堆      * @param parentIndex 要下沉的父节点      * @param length 堆的有效大小      */     public static void downAdjust(int[] array,int parentIndex,int  length){         int temp = array[parentIndex];         int childIndex = 2*parentIndex +1;          while (childIndex < length){             // 找出孩子节点 最小的             if(childIndex+1< array[childIndex]){                 childIndex++;             }             // temp小于 孩子节点的值，直接跳出，不需要下沉             if(temp <= array[childIndex]){                 break;             }             array[parentIndex] = array[childIndex];             parentIndex = childIndex;             childIndex = 2*childIndex+1;          }         array[parentIndex] = temp;     }       public static void buildHeap(int[] array){         /**  层序遍历          * 最后一个叶子节点 索引： array.length-1          * 他的父节点 ： （array.length-2）/2          */         for (int i = (array.length-2)/2; i >= 0 ; i--) {             downAdjust(array,i,array.length);         }     }      public static void main(String[] args) {         int[] array = new int[]{1,3,2,0};         // 层序遍历 //        upAdjust(array); //        System.out.println(Arrays.toString(array));         buildHeap(array);         System.out.println(Arrays.toString(array));     } 优先队列 优先队列：  最大优先队列 ： 无论入队顺序如何，都是当前最大的元素优先出队(最大堆) 最小优先队列 ： 无论入队顺序如何，都是当前最小的元素优先出队(最小堆) 添加一个元素，，在最后加入一个子节点，，子节点上浮，，， 删除一个元素： 将最后一个孩子节点去替代 堆顶 ，，下浮  public class PriorityQueue {     private int[] array;     private int size;      public PriorityQueue() {         // 队列初始长度         array = new int[4];     }      /**      * 入队      * @param element 入队的元素      */     public void enQueue(int element){         if(size >= array.length){             resize();         }         array[size++] = element;         upAdjust();     }      /**      * 出队      * @return      */     public int deQueue() throws Exception{         if(size <= 0){             throw new Exception("the queue is empty");         }          // 取出堆顶元素         int head = array[0];         // 最后一个元素移动到堆顶         array[0] = array[--size];         downAdjust();         return head;     }      /**      * 将最后一个节点（新增节点），，上浮      */     private void upAdjust(){         int childIndex = size-1;         int parentIndex = (childIndex)/2;          int temp = array[childIndex];          // 插入节点  比 父节点 大         while (childIndex > 0 && temp > array[parentIndex]){             array[childIndex] = array[parentIndex];             childIndex  = parentIndex;             parentIndex = (childIndex-1)/2;         }          array[childIndex] = temp;     }      /**      * 下调。。删除第一个节点，下调      */     private void downAdjust(){         int  parentIndex = 0 ;         int temp = array[parentIndex];         int childIndex =1;         while (childIndex            // 找出的最大的，，和父节点比较             if(childIndex+1 array[childIndex]){                 childIndex++;             }             if(temp >= array[childIndex]){                 break;             }             array[parentIndex] = array[childIndex];             parentIndex = childIndex;             childIndex = 2*parentIndex+1;         }          array[parentIndex] = temp;     }      /**      * 队列扩容      */     public void resize(){         int newSize = size *2;         this.array = Arrays.copyOf(array,newSize);     }      public static void main(String[] args) throws Exception {         PriorityQueue priorityQueue = new PriorityQueue();         priorityQueue.enQueue(1);         priorityQueue.enQueue(5);         priorityQueue.enQueue(3);         priorityQueue.enQueue(4);         System.out.println(priorityQueue.deQueue());         priorityQueue.enQueue(9);         System.out.println(priorityQueue.deQueue());         System.out.println(priorityQueue.deQueue());     } }  ———————————————— 版权声明：本文为CSDN博主「wfsm」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/qq_36022463/article/details/126693051 

双链表的好处就不提了，在linux内核中对链表的设计简直就是天才的设计，内核双链表与普通的链表不一样。    在普通的链表中，头尾指针与数据绑定在一起，即存放在同一个结构体中，创建每一个结点时就需要指明需要何种类型的数据这是无疑的，比如：  typedef struct line{     struct line * prior; //指向直接前趋     int data;     struct line * next; //指向直接后继 }line;   按照平常的学习顺序，接下来就是初始化节点、增删改查等了，增删改查的过程，需要通过line类型的结构体来操作前驱和后驱的指针，此时就决定了不同的结构类型则需要不同的操作函数，比如这次保存int数据是line类型结构体，当需要保存char型数据则需要另外的结构体类型，这就导致了所有的操作函数都要重写，非常麻烦。    传统链表的节点不仅包含了表达链表逻辑的指针，更包含了某一种具体的数据，而关键是这些指针指向了整个节点，这就导致了无法将逻辑表逻辑与具体的数据分开，p是特殊的指针，不具有通用性。   linux内核链表则将链表中的链抽象出来，此时的链表单纯只包含前后指针，而不含有任何特殊的数据，这时候才是真正的链。此时如果要处理数据，只需要将链嵌入到数据里就行，对链表的增删改查则全都是对于链的操作，而与数据并无太大关系。   上面红色的为纯粹的链表，其只负责记录前后结点，对链表的操作相对就比较容易了，蓝色和绿色的则为数据。实际中我们想要的效果是，当将链表嵌入到数据后，对链表的操作在表层的体现仅仅是操作链表，而内层实则也对数据进行了操作，并且操作方法适用于不同类型数据的链表，换句话说，数据其实一直没有动过。内核双链表定义如下：  // 小结构体 // 构成纯粹的链表 typedef struct node{     struct node *next;     struct node *prev; }listNode,*listNodePtr;  //数据结构体 typedef struct data{     int data;     char name[20];     listNode list; }dataNode,*dataNodePtr;   想象一下，如果一个结点同时处于三个链表中该怎么实现？只需在该结点的dataNode中多定义两个链表结点就好了，并且在不同链表中，每一链表结点（小结构体）的操作都是一模一样的。     linux内核链表的突出优点是：由于可以非常方便地将其标准实现（即“小结构体”）镶嵌到任意结点，因此任何数据组成地链表的所有操作都被完全统一。另外在后期维护过程要对结点成员进行升级修改，也完全不影响该结点原有的链表结构。   初始化链表头结点，指向自己：  //写法一： // 初始化标准结构体（小结构体），指向自己 #define INIT_LIST_NODE(ptr) do { \     (ptr)->next = (ptr); \     (ptr)->prev = (ptr); \ } while (0)  //写法二： //初始化小结构体，内联函数，检测类型 #define LIST_HEAD_INIT(NAME) {&name,&name} #define LIST_HEAD(name) (listNode name=LIST_HEAD_INIT(NAME)) static inline void INIT_LIST_HEAD(listNodePtr list) {     list->next = list;     list->prev = list; }  /*     listNode tmp;     INIT_LIST_HEAD(&tmp);     //等价于     listNode tmp = {&tmp,&tmp}; */   插入操作，可插入到头结点之后或者头结点之前，传入参数是listNode类型的结构体，因此插入操作与大结构体没有任何关系：  static inline void __list_add(listNodePtr new,                 listNodePtr prev, listNodePtr next) {     next->prev = new;       new->next = next;     new->prev = prev;     prev->next = new; } // 将节点new，插入到链表head的末尾 // 即：插入到head的前面 static inline void list_add_tail(listNodePtr new,                                  listNodePtr head) {     __list_add(new, head->prev, head); } // 将节点new，插入到链表head的首部 // 即：插入到head的后面 static inline void list_add(listNodePtr new, listNodePtr head) {     __list_add(new, head, head->next); }    可以发现，不管是前插还是后插，最终通过③的计算是一样的，区别只在于传入的参数，即可完成前插或者后插的操作，并且，重点是！整个插入的过程均是链表结点之间的操作，与大的结构体没有任何关系！     删除操作，实际是将一个结点从链表中剔除，与传统链表的删除操作一样，只不过需要注意的是，即使在链表将该结点（小结构体）剔除整个链表，但是大结构通过malloc来的地址并没有释放掉，在后续操作函数中需要注意：  static inline void __list_del(listNodePtr prev, listNodePtr next) {     //更改剔除结点的前后结点的指向     next->prev = prev;     prev->next = next; }  // 将entry从链表中剔除出去 static inline void list_del(listNodePtr entry) {     __list_del(entry->prev, entry->next);     entry->next = (void *) 0;     entry->prev = (void *) 0; }   遍历操作，有多种遍历方法，遍历过程得到的每个结点，可以删除或不能删除，主要由是否传入一个临时结点进去进行缓冲而决定：  // 遍历算法1: 从head开始往后遍历每一个节点 // pos为每次遍历得到的小结构体指针，不可删除 #define list_for_each(pos, head) \ for (pos = (head)->next; pos != (head); pos = pos->next)  // 遍历算法2: 从head开始往前遍历每一个节点 // pos为每次遍历得到的小结构体指针，不可删除 #define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); pos = pos->prev)  // 遍历算法3: 从head开始往后遍历每一个节点 // pos为每次遍历得到的小结构体指针，可删除节点 // n为临时存储变量，从调用处给入，不可操作 #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next)  // 遍历算法4: 从head开始往后遍历每一个节点，并且直接获得大结构体的指针 // pos为每次遍历得到的大结构体指针，不可删除节点 // member为小结构体在大结构体中的名称，比如dataNode中的list #define list_for_each_entry(pos, head, member)                \ for (pos = list_entry((head)->next, typeof(*pos), member);    \ &pos->member != (head);                     \ pos = list_entry(pos->member.next, typeof(*pos), member))  // 遍历算法5: 从head开始往后遍历每一个节点，并且直接获得大结构体的指针 // pos为每次遍历得到的大结构体指针，可删除节点 // n为临时存储变量，从调用处给入，不可操作 // member为小结构体在大结构体中的名称，比如dataNode中的list #define list_for_each_entry_safe(pos, n, head, member)            \ for (pos = list_entry((head)->next, typeof(*pos), member),    \ n = list_entry(pos->member.next, typeof(*pos), member);    \ &pos->member != (head);                     \ pos = n, n = list_entry(n->member.next, typeof(*n), member))     上面遍历方法4和5中出现的list_entry也是一个链表操作函数，主要作用为从小结构体指针获取得到大结构体指针（结点的基地址），这一步是实现内核链表非常关键重要的一步，其定义如下：  // 从小结构体ptr，获得大结构体的指针 #define list_entry(ptr, type, member) \     ((type *)((char *)(ptr)-(size_t)(&((type *)0)->member)))   回顾前面对链表的操作，唯一只涉及到 listNodePtr 指针（即小结构体），链表的相连也都是靠 listNodePtr 记录 listNodePtr 来实现的（并不是记录大结构体的地址），因此 listNodePtr 才是重点。如上图，基地址P是dataNode类型结构体的首地址，member为小结构体在大结构体中的成员们（即list），如果我们要从 ptr 访问到大结构体中的数据，就得先求出大结构体基地址 P，实际求出偏移量 offset 即可。     比如，对于以下结构体进行计算  //先定义一个大结构体 dataNode tmp; //两种方式可得到 ptr 地址为 ptr = &tmp->list ptr = &tmp + offset //等式代换得 offset = &tmp->list - &tmp 实际中&tmp并不重要，它是通过malloc申请得到的内存 有无数个结点申请，都会有对应的&tmp 但唯一不会改变的是tmp与tmp.list之间的地址差值offset 也就是说，tmp地址的改变，并不会影响到offset的值   如果假如tmp的地址为0，那么刚好ptr的地址就为offset，如果tmp的地址为1，那么此时ptr的地址就为(offset+1)，以此类推，说白了就是tmp的地址不会对offset的值产生任何影响，为了计算方便，直接当作0地址来计算：  offset = &(0)->list - (0) = &(0)->list //上式的0为数学上的0，需要转换为大结构体类型 offset = &((type *)0)->list //此时offset还是一个链表节点类型的指针，需要转为整形表示字节数 offset = (size_t)(&((type *)0)->list)   offset的值得到了，可发现，只要通过大结构体的类型（并不是大结构体地址，比如dataNode）和小结构体在其中的成员名称（即list），就可以得到在该大结构体中，基地址与小结构体地址之间的差值了（单位为字节）。  //求大结构体的基地址 P = ptr - (size_t)(&((type *)0)->list) //为了使ptr运算时将offset作为字节偏移量来对待 //需转为(char *)类型，即指针每移动一次步长为1字节 P = (char *)ptr - (size_t)(&((type *)0)->list) //此时得到的P为大结构体真正的地址，但是没有类型指明，需要转换 P = (type *)((char *)ptr - (size_t)(&((type *)0)->list))   完结撒花，因此通过以下宏，即可从小结构体指针得出大结构体指针：  #define list_entry(ptr, type, member) \     ((type *)((char *)(ptr)-(size_t)(&((type *)0)->member)))    如果还不能理解，可以再通俗一点，已知指针移动的步长与它的类型有关（比如int * 指针加1就移动4字节，char * 加1就移动1字节）。   (char *)(ptr)的作用就是保证小结构体指针ptr每次移动的步长都为1，慢慢地移动到基地址（如果不这样强制转换，就会导致ptr每次加1都会移动ptr对应结构体大小的步长，比如listNode，即16字节了，因为里面是两个指针）。   &((type *)0)->member的作用则是取得当大结构体位于0地址时，此时的member地址，首先((type * )0)得到的是0地址强制转换为大结构体指针类型，那么一个箭头加成员名就可以访问到成员，然后我们的目的是得到此时（大结构体位于0地址时）该成员的地址，进而求出偏移量offset，非常值得注意的是，->的优先级高于取地址符&，因此最终得到的是偏移量（还是一个地址值）。   (size_t)(&((type *)0)->member)的作用就是将偏移量的值从地址形式转成整形数，比如一开始offset的值为0x08，强制转换后它的值则为整形数8了。   （如果还是对((type * )0)耿耿于怀，看我的下一篇文章）         因此，对于链表的操作，只要记住头结点的指针即可，实则起关键作用的还是每个节点中小结构体的指针。在对小结构体遍历时，我们就能够获取到每个节点所保存的数据了，调用该宏的例子如下：  dataNodePtr head; //head为头结点大结构体指针，类型为dataNodePtr listNodePtr tmp = head->list->next; //头结点后第一个节点的小结构体指针 dataNodePtr TMP; //大结构体指针 TMP = list_entry(tmp, typeof(* head), list); TMP->data; //此时即可拿到tmp所在大结构体中的数据   list_entry的第二个参数为type，在宏展开后又为( type * )，调用时传入的参数为typeof(* head)，即typeof(dataNode)，传入给宏后经( type * )转换实际得到为dataNodePtr结构体指针类型，与我们想要的效果一致。   关于快速排序的知识在网上非常非常多，这里就不记录了，主要思路就是使用递归思想，每一次以左边的值作为支点，通过low和high两个变量记录位置来对全部数据进行检验，low从左往右找，直到找到比支点值大的值停止，high从右往左找，直到找到比支点值小的值位置，实现将小于支点的值都放在支点的左边，大于支点的值都放在支点的右边。   要将小的值放左边，大的值放右边，则用到一个巧妙地方法，先让high寻找并移动，直到停止再将high停止处的结点与low处的结点互换（内核链表结点互换），然后让low寻找并移动，直到停止再将low停止处的结点与high处的结点互换，一直循环这两个步骤，直到low的值不再小于high的值。   先设pivotkey的值（取第一个数），比如下面pivotkey=49： 循环，判断，第八个数49符合条件，进入循环，high减一； 判断第七个数27，不符合，跳出； 将第low个位置与第high位置数据互换，即第1个和第7个； 在链表实际操作中，互换的是结点，而不是数据。   第一次右往左移结束，接着到low向右移动： 循环，判断第1个数27，符合条件进入，low加1； 判断第2个数38，比支点小，符合进入，low加1； 判断第3个数65，不符合，跳出； 互换low位置地值和high位置的值，即第3个和第7个； 在链表实际操作中，互换地是结点，而不是数据。     上面两个过程在while(low 上面快速排序主要的难点在于互换两个结点，因为是双链表，每一个结点都与其前后结点有关系，因此可以采用以下的方法，主要思路就是增加一个结点作为缓冲，还是画图吧（此时就非常棒地体现出内核链表地牛逼之处了，新增地这个临时结点并不需要数据，它只是一个临时变量）    利用到地是前面提到地增加一个结点和剔除一个结点地操作，剔除结点并没有真正将其从内存中抹去，而只是将其指向改了，并将其前后结点的指向也改了。实现代码如下：  //加入一个节点作为缓存作用， //不管两个节点是相邻还是不相邻 void swapNodePtr(listNodePtr beExTmp, listNodePtr exTmp) {     listNode flag = {NULL, NULL};     list_add_tail(&flag,exTmp);     list_del(exTmp);     list_add_tail(exTmp,beExTmp);     list_del(beExTmp);     list_add_tail(beExTmp,&flag);     list_del(&flag); } 综合以上，所有代码如下： 环境：linux gcc 64位 使用方法：将以下4个文件保存到一个目录，在该目录下执行make，然后运行app     test.h  #ifndef __TEST_ #define __TEST_  #include  #include   typedef int DATATYPE; typedef char NAMETYPE; // 小结构体 // 构成纯粹的链表 typedef struct node{     struct node *next;     struct node *prev; }listNode,*listNodePtr;  //数据结构体 typedef struct data{     DATATYPE data;     NAMETYPE name[20];     listNode list; }dataNode,*dataNodePtr;   int getPartition(dataNodePtr head, int low, int high); void sort(dataNodePtr head, int low, int high); void quickSort(dataNodePtr head); void manHelpInfo(void);  void setNodeData(dataNodePtr head, int pos, int data); DATATYPE getNodeData(dataNodePtr head, int n); listNodePtr getNodePtr(dataNodePtr head, int n); void deleteList(dataNodePtr head); void deleteNode(dataNodePtr head, DATATYPE data); void printList(dataNodePtr head); void addFrontNode(dataNodePtr head, DATATYPE data); void addBackNode(dataNodePtr head, DATATYPE data); dataNodePtr listInit(void); void swapNodePtr(dataNodePtr head, int bxEx, int ex);   // 初始化标准结构体（小结构体），指向自己 #define INIT_LIST_NODE(ptr) do { \     (ptr)->next = (ptr); \     (ptr)->prev = (ptr); \ } while (0)   static inline void __list_del(listNodePtr prev, listNodePtr next) {     next->prev = prev;     prev->next = next; }  // 将entry从链表中剔除出去 static inline void list_del(listNodePtr entry) {     __list_del(entry->prev, entry->next);     entry->next = (void *) 0;     entry->prev = (void *) 0; }  // 从小结构体ptr，获得大结构体的指针 #define list_entry(ptr, type, member) \     ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))  // 遍历算法: 从head开始往后遍历每一个节点，并且直接获得大结构体的指针 // 注意，在遍历的过程中，不可删除节点 #define list_for_each_entry(pos, head, member)                \ for (pos = list_entry((head)->next, typeof(*pos), member);    \ &pos->member != (head);                     \ pos = list_entry(pos->member.next, typeof(*pos), member))  // 遍历算法: 从head开始往后遍历每一个节点，并且直接获得大结构体的指针 // 注意，在遍历的过程中，可删除节点 #define list_for_each_entry_safe(pos, n, head, member)            \ for (pos = list_entry((head)->next, typeof(*pos), member),    \ n = list_entry(pos->member.next, typeof(*pos), member);    \ &pos->member != (head);                     \ pos = n, n = list_entry(n->member.next, typeof(*n), member))  static inline void __list_add(listNodePtr new,                 listNodePtr prev,                 listNodePtr next) {     next->prev = new;       new->next = next;     new->prev = prev;     prev->next = new; } // 将节点new，插入到链表head的末尾 // 即：插入到head的前面 static inline void list_add_tail(listNodePtr new,                                  listNodePtr head) {     __list_add(new, head->prev, head); } // 将节点new，插入到链表head的首部 // 即：插入到head的后面 static inline void list_add(listNodePtr new, listNodePtr head) {     __list_add(new, head, head->next); }  /*设置输出前景色*/ #define PRINT_FONT_RED  printf("\033[31m") //红色 #define PRINT_FONT_WHI  printf("\033[37m") //白色 #define PRINT_FONT_GRE  printf("\033[32m") //绿色 #define PRINT_FONT_YEL  printf("\033[33m") //黄色 #define PRINT_FONT_BLU  printf("\033[34m") //蓝色 #define PRINT_FONT_PUR  printf("\033[35m") //紫色 #define PRINT_FONT_CYA  printf("\033[36m") //青色  /*设置输出背景色*/  #define PRINT_BACK_BLA  printf("\033[40m") //黑色 #define PRINT_BACK_RED  printf("\033[41m") //红色 #define PRINT_BACK_GRE  printf("\033[42m") //绿色 #define PRINT_BACK_YEL  printf("\033[43m") //黄色 #define PRINT_BACK_BLU  printf("\033[44m") //蓝色 #define PRINT_BACK_PUR  printf("\033[45m") //紫色 #define PRINT_BACK_CYA  printf("\033[46m") //青色 #define PRINT_BACK_WHI  printf("\033[47m") //白色  #endif test.c #include  #include   //初始化一个链表 dataNodePtr listInit() {     dataNodePtr head = malloc(sizeof(dataNode));     if (head != NULL)     {         head->data = 0;         sprintf(head->name,"%s","head");         INIT_LIST_NODE(&head->list);         return head;     }     return NULL; } //在头结点的后面增加一个结点 void addBackNode(dataNodePtr head, DATATYPE data) {     dataNodePtr p = malloc(sizeof(dataNode));     if (p != NULL)     {         p->data = data;         head->data += 1;         sprintf(p->name,"结点：%d",head->data);         list_add_tail(&p->list, &head->list);     } } //在头结点的前面增加一个结点 void addFrontNode(dataNodePtr head, DATATYPE data) {     dataNodePtr p = malloc(sizeof(dataNode));     if (p != NULL)     {         p->data = data;         head->data += 1;         sprintf(p->name,"结点：%d",head->data);         list_add(&p->list, &head->list);     } } //打印链表 void printList(dataNodePtr head) {     dataNodePtr tmp;     int flag = 0;     PRINT_FONT_YEL;     printf("链表长度 %d ： ", head->data);     list_for_each_entry(tmp, &head->list, list)     {         printf("%s%d", flag == 0 ? "" : "<-->", tmp->data);         flag = 1;     }     printf("\n");     list_for_each_entry(tmp, &head->list, list)     {         printf("%s --> data: Û5694c72-ef81-496b-a174-031c5ef8ccf0n",tmp->name,tmp->data);     }     printf("\n\n\n");     PRINT_FONT_WHI;     return; } //根据数据内容删除对于结点 void deleteNode(dataNodePtr head, DATATYPE data) {     int flag = 0;     dataNodePtr tmp, n;     list_for_each_entry_safe(tmp, n, &head->list, list)     {         if (tmp->data == data)         {             list_del(&tmp->list);             free(tmp);             tmp = (void *)0;             printf("删除数据 %d 成功！\n", data);             flag = 1;             head->data = (head->data == 0) ? 0 : (head->data - 1);         }     }     if (!flag)         printf("找不到对应节点。\n"); } //删除整个链表 void deleteList(dataNodePtr head) {     dataNodePtr pos, n;     list_for_each_entry_safe(pos, n, &head->list, list)     {         printf("删除数据 %d 成功！\n", pos->data);         list_del(&pos->list);         free(pos);         pos = (void *)0;     }     head->data = 0;     printf("链表已清空！\n"); } //返回第n个结点的指针 listNodePtr getNodePtr(dataNodePtr head, int n) {     listNodePtr tmp = &head->list;     for (int i = 1; i <= n; i++)     {         tmp = tmp->next;     }     return tmp; } //返回某个结点的数据内容 DATATYPE getNodeData(dataNodePtr head, int n) {     listNodePtr tmp = getNodePtr(head, n);     return (list_entry(tmp, typeof(*head), list))->data; } //将某个结点的数据重置 void setNodeData(dataNodePtr head, int pos, int data) {     listNodePtr tmp = getNodePtr(head, pos);     (list_entry(tmp, typeof(*head), list))->data = data; }  //不改变结点位置，只改变其中的数据 //快速排序实现，返回支点位置 // int getPartition(dataNodePtr head, int low, int high) // { //     int tmpData = 0; //     int pivotkey = getNodeData(head, low); //     while (low < high) //     { //         tmpData = getNodeData(head, high); //         while (low < high && tmpData >= pivotkey) //         { //             high--; //             tmpData = getNodeData(head, high); //         } //         setNodeData(head, low, tmpData);  //         tmpData = getNodeData(head, low); //         while (low < high && tmpData <= pivotkey) //         { //             low++; //             tmpData = getNodeData(head, low); //         } //         setNodeData(head, high, tmpData); //     } //     setNodeData(head, low, pivotkey); //     return low; // }  //加入一个节点作为缓存作用， //不管两个节点是相邻还是不相邻 void swapNodePtr(dataNodePtr head, int bxEx, int ex) {     listNodePtr beExTmp = getNodePtr(head,bxEx);     listNodePtr exTmp = getNodePtr(head,ex);      listNode flag = {NULL, NULL};     list_add_tail(&flag,exTmp);     list_del(exTmp);     list_add_tail(exTmp,beExTmp);     list_del(beExTmp);     list_add_tail(beExTmp,&flag);     list_del(&flag); }  //改变结点位置 //快速排序实现，返回支点位置 int getPartition(dataNodePtr head, int low, int high) {     int tmpData = 0;     int pivotkey = getNodeData(head, low);     while (low < high)     {         tmpData = getNodeData(head, high);         while (low < high && tmpData >= pivotkey)         {             high--;             tmpData = getNodeData(head, high);         }         if(low != high) swapNodePtr(head, low, high);          tmpData = getNodeData(head, low);         while (low < high && tmpData <= pivotkey)         {             low++;             tmpData = getNodeData(head, low);         }         if(low != high) swapNodePtr(head, high, low);     }     //setNodeData(head, low, pivotkey);     return low; }  //快速排序实现，用于递归 void sort(dataNodePtr head, int low, int high) {     if (low < high)     {         int pivotloc = getPartition(head, low, high);         sort(head, low, pivotloc - 1);         sort(head, pivotloc + 1, high);     } } //快速排序实现 void quickSort(dataNodePtr head) {     printf("排序前：\n");     printList(head);     sort(head, 1, head->data);     printf("快速排序的结果： \n"); }  //显示帮助信息 void manHelpInfo() {     PRINT_FONT_BLU;     printf("---------------------\n");     printf("前插格式：  [p][空格][数据]\n");     printf("后插格式：  [n][空格][数据]\n");     printf("前插多个：  [P][空格][数据][空格][数据]...\n");     printf("后插多个：  [N][空格][数据][空格][数据]...\n");     printf("删除格式：  [d][空格][数据]\n");     printf("交换结点：  [S][空格][数据][空格][数据]\n");     printf("删除全部：  [D]\n");     printf("查看格式：  [s]\n");     printf("快速排序：  [q]\n");     printf("---------------------\n");     PRINT_FONT_WHI; }   main.c  #include  #include "test.h"  int main() {     dataNodePtr head = listInit();     printf("%s", "\033[1H\033[2J"); //清屏     printf("链表初始化完成！\n");      //用于解析输入的字符串     char cmdStr[100];  //最大一次接收100个字符     char *cmdToken;    //临时变量     char *cmdBuf[100]; //将解析出来的命令保存于此     int cmdBufPos = 0; //位置变量      manHelpInfo();     while (1)     {         PRINT_FONT_BLU;         printf("====================================\n");         printf("查看帮助：[h]  清屏: [c]  退出: [e]\n");         printf("====================================\n");         PRINT_FONT_GRE;         printf("输入>> ");         PRINT_FONT_WHI;          fgets(cmdStr, 100, stdin); //从标准输入流获取一行         cmdToken = cmdStr;         //以空格分开，进行数据解析         while (cmdToken != NULL)         {             cmdBuf[cmdBufPos++] = strsep(&cmdToken, " ");         }          printf("%s", "\033[1H\033[2J"); //清屏          if (cmdBuf[0][0] == 'p' && cmdBufPos > 1)         {             addFrontNode(head, atoi(cmdBuf[1]));             printf("前插数据 %d \n", atoi(cmdBuf[1]));         }          else if (cmdBuf[0][0] == 'P' && cmdBufPos > 1)         {             printf("连续前插数据： ");             for (int i = 1; i < cmdBufPos; i++)             {                 addFrontNode(head, atoi(cmdBuf[i]));                 printf("%d ", atoi(cmdBuf[i]));             }             printf("\n");         }          else if (cmdBuf[0][0] == 'n' && cmdBufPos > 1)         {             addBackNode(head, atoi(cmdBuf[1]));             printf("后插数据 %d \n", atoi(cmdBuf[1]));         }          else if (cmdBuf[0][0] == 'N' && cmdBufPos > 1)         {             printf("连续后插数据： ");             for (int i = 1; i < cmdBufPos; i++)             {                 addBackNode(head, atoi(cmdBuf[i]));                 printf("%d ", atoi(cmdBuf[i]));             }             printf("\n");         }          else if (cmdBuf[0][0] == 'd' && cmdBufPos > 1)         {             deleteNode(head, atoi(cmdBuf[1]));         }         else if (cmdBuf[0][0] == 'D')         {             deleteList(head);         }         else if (cmdBuf[0][0] == 's')         {             printList(head);         }         if (cmdBuf[0][0] == 'h')         {             manHelpInfo();         }         else if (cmdBuf[0][0] == 'c')         {             printf("%s", "\033[1H\033[2J");         }          else if (cmdBuf[0][0] == 'q')         {             quickSort(head);         }          else if(cmdBuf[0][0] == 'S' ){             swapNodePtr(head,atoi(cmdBuf[1]),atoi(cmdBuf[2]));         }          else if (cmdBuf[0][0] == 'e')         {             deleteList(head);             free(head);             head = (void *)0;             break;         }         printList(head);         cmdBufPos = 0;     }     return 0; }     Makefile  SRCS = main.c test.c INC = -I./  objs = $(SRCS:.c=.o) target = app CC = gcc  $(target):$(objs)     $(CC) $(objs) -o $(target)     @make clean  %.o:%.c     $(CC) -c $(INC) $< -o $@  .PHONY : clean clean :     rm *.o        时间问题，代码比较粗糙，如有错误，欢迎指正，谢谢！   ———————————————— 版权声明：本文为CSDN博主「从心开始 &gt;」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/fengge2018/article/details/108718939 

 1. 一些历史遗留问题 1111 Online Map  Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.  Input Specification: Each input file contains one test case. For each case, the first line gives two positive integers N (2≤N≤500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:  V1 V2 one-way length time 1 where V1 and V2 are the indices (from 0 to N−1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.  Finally a pair of source and destination is given.  Output Specification: For each case, first print the shortest path from the source to the destination with distance D in the format:  Distance = D: source -> v1 -> ... -> destination 1 Then in the next line print the fastest path with total time T:  Time = T: source -> w1 -> ... -> destination 1 In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.  In case the shortest and the fastest paths are identical, print them in one line in the format:  Distance = D; Time = T: source -> u1 -> ... -> destination 1 Sample Input 1: 10 15 0 1 0 1 1 8 0 0 1 1 4 8 1 1 1 3 4 0 3 2 3 9 1 4 1 0 6 0 1 1 7 5 1 2 1 8 5 1 2 1 2 3 0 2 2 2 1 1 1 1 1 3 0 3 1 1 4 0 1 1 9 7 1 3 1 5 1 0 5 2 6 5 1 1 2 3 5  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Sample Output 1: Distance = 6: 3 -> 4 -> 8 -> 5 Time = 3: 3 -> 1 -> 5 1 2 Sample Input 2: 7 9 0 4 1 1 1 1 6 1 1 3 2 6 1 1 1 2 5 1 2 2 3 0 0 1 1 3 1 1 1 3 3 2 1 1 2 4 5 0 2 2 6 5 1 1 2 3 5 1 2 3 4 5 6 7 8 9 10 11 Sample Output 2: Distance = 3; Time = 4: 3 -> 2 -> 5 1 比较典型的Dijkstra+DFS找到最短路径的模板题 虽然不知道之前做的时候为什么卡在第二个测试点 以下是订正后的AC代码，找最短和最快路径其实套路是一样的，主要是最后确定路径的时候前者需要时间最小、后者需要经过的结点数最少，以及输出答案的时候注意格式问题即可  #include using namespace std; //推荐两条路：一条最短(最快)，一条最快(最少的中转站) const int inf=INT_MAX; int N,M,v1,v2,one_way,ll,tt; int st,ed; int min_time=inf,min_trans=inf; vector >d,t,pre;//路程，时间  vectors_path,f_path; /*找到最短的路*/ void dfs_shortest(int id,vectortemp){     temp.push_back(id);     if(id==st){         int temp_time=0;         int len=temp.size();         for(int i=len-1;i>=1;i--){             temp_time+=t[temp[i]][temp[i-1]];         }         if(temp_time            min_time=temp_time;             s_path=temp;         }     }else{         for(int i=0;i             dfs_shortest(pre[id][i],temp);          }      }      temp.pop_back();  }  int findShortest(){      vectordis(N,inf);      vectorvis(N,false);      pre.resize(N);      dis[st]=0;      while(1){          int u=-1;          int min_dis=inf;          for(int i=0;i             if(!vis[i]&&min_dis>dis[i]){                  min_dis=dis[i];                  u=i;              }          }          if(u==-1){              break;          }          vis[u]=true;          for(int v=0;v             if(!vis[v]){                  if(d[u][v]!=inf){                      if(dis[u]+d[u][v]                         dis[v]=dis[u]+d[u][v];                          pre[v].clear();                          pre[v].push_back(u);                      }else if(dis[u]+d[u][v]==dis[v]){                          pre[v].push_back(u);                      }                  }              }          }      }      vectortemp;      dfs_shortest(ed,temp);      pre.clear();       return dis[ed];  }  /*找到最快的路*/  void dfs_fastest(int id,vectortemp){      temp.push_back(id);      if(id==st){          int len=temp.size();          if(len             min_trans=len;              f_path=temp;          }  //        printf("=====\n");  //        for(int i=0;i //            printf("%d ",temp[i]);  //        }  //        printf("\n====\n");      }else{          for(int i=0;i             dfs_fastest(pre[id][i],temp);          }      }      temp.pop_back();  }  int findFastest(){      vectordis(N,inf);      vectorvis(N,false);      pre.resize(N);      dis[st]=0;      while(1){          int u=-1;          int min_dis=inf;          for(int i=0;i             if(!vis[i]&&min_dis>dis[i]){                  min_dis=dis[i];                  u=i;              }          }          if(u==-1){              break;          }          vis[u]=true;          for(int v=0;v             if(!vis[v]){                  if(t[u][v]!=inf){                      if(dis[u]+t[u][v]                         dis[v]=dis[u]+t[u][v];                          pre[v].clear();                          pre[v].push_back(u);                      }else if(dis[u]+t[u][v]==dis[v]){                          pre[v].push_back(u);                      }                  }              }          }      }      vectortemp;      dfs_fastest(ed,temp);      pre.clear();       return dis[ed];  }  int main(){      scanf("%d%d",&N,&M);      d.resize(N);      t.resize(N);      for(int i=0;i         d[i].resize(N);          t[i].resize(N);          fill(d[i].begin(),d[i].end(),inf);          fill(t[i].begin(),t[i].end(),inf);          d[i][i]=0;t[i][i]=0;      }      for(int i=0;i         scanf("%d%d%d%d%d",&v1,&v2,&one_way,&ll,&tt);          d[v1][v2]=min(d[v1][v2],ll);          t[v1][v2]=min(t[v1][v2],tt);          if(one_way==0){              d[v2][v1]=d[v1][v2];              t[v2][v1]=t[v1][v2];          }      }      scanf("%d%d",&st,&ed);      int f=findFastest();      int s=findShortest();      if(s_path==f_path){          printf("Distance = %d; Time = %d: ",s,f);          int len=s_path.size();          for(int i=len-1;i>=0;i--){              if(i!=len-1){                  printf(" -> ");              }              printf("%d",s_path[i]);          }      }else{          printf("Distance = %d: ",s);          int len=s_path.size();          for(int i=len-1;i>=0;i--){              if(i!=len-1){                  printf(" -> ");              }              printf("%d",s_path[i]);          }          printf("\nTime = %d: ",f);          len=f_path.size();          for(int i=len-1;i>=0;i--){              if(i!=len-1){                  printf(" -> ");              }              printf("%d",f_path[i]);          }      }      return 0;  }     ————————————————  版权声明：本文为CSDN博主「理想国の糕」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  原文链接：https://blog.csdn.net/qq_45751990/article/details/126639720 

一、 关键字和保留字关键字（keyword）的定义和特点定义：被Java语言赋予了特殊含义，用做专门用途的字符串（单词）特点：关键字中所有字母都为小写根据分类：数据类型：Boolean、int、long、short、byte、float、double、char、class、interface流程控制：if、else、do、while、for、Switch、case、default、break、continue、return、try、catch、finally修饰符：  public、protected、private、final、void、static、abstract、transient、synchronized、volatile、native动作：package、import、throw 、throws、extends、implements、this、supper、instanceof、new保留字：Java保留字：现有Java版本尚未使用，以后可能会作为关键字使用。命名【标识符】时要避免使用这些保留字goto、const二、标识符什么是标识符Java对各种变量，方法和类等要素命名时使用的字符串序列称为标识符技巧：凡是自己可以 起名字的地方都叫标识符定义合法标识符规则由26个英文字母大小写，0-9，_或$组成数字不能包含空格不可以使用关键字和保留字，但能包含关键字个保留字Java中严格区分大小写，长度无限制Java 中名称命名规范包名：多单词组成时所有字母都小写：xxxxyyyy类名：接口名：多单词组成时，所有单词首字母读大写 ： XxxYyy变量名：方法名：多单词组成时，第一个单词首字母小写，第二个单词开始每个单词首字母大写：xxxYyyZzz常量名:所有字母都大写，多单词时每个单词用下划线连接：XXX_YYY_AAA注意点：注意1：在起名字时，为了提高阅读性，要尽量有意义注意2：Java采用Unicode字符集，因此标识符也可以使用汉字声明，但是不建议使用三、变量变量的声明与使用变量的概念： 内存中的一个存储区域该区域的数据可以在同一类型范围内不断变化变量是程序中最基本的存储的单位。包含变量类型  变量名和存储的值变量的作用：用于在内存中保存的数使用变量的注意：Java中每个变量必须先声明，后使用使用变量名来访问这块区域的数据变量的作用域：其定义所在的一对{}内变量只有在其作用域才有效同一个作用域内，不能定义重名的变量声明变量：语法：数据类型  变量名称 int   var；变量的赋值：var =10；声明和赋值变量语法：数据类型  变量名 =初始值int var =10；补充：变量的分类  按声明的位置的不同在方法体外，类体内声明的变量称为成员变量在方法体内，声明的变量称为局部变量所有变量：成员变量、局部变量成员变量和局部变量的区别：成员变量：实例变量（不以static修饰）；类变量（以static修饰）局部变量：形参（方法、构造器中定义的变量）；方法局部变量（在方法内定*义）；代码块局部变量（在代码块内定义）注意:二者在初始值方面的异同异:局部变量除形参外，都需要显式初始化同： 都有生命周期基本数据类型变量的分类  按数据类型对于每一种数据都定义了明确的具体数据类型（强类型语言），在内存中分配了不同大小的内存空间。数据类型包括：基本数据类型和引用数据类型基本数据类型：数值型（整数类型：byte、short、int、long；浮点类型：float、double）、字符型char、布尔型boolean引用数据类型：类class、接口interface、数组 【】整数类型：byte、short、int、longJava各整数类型有固定的表数范围和字段长度，不受OS的影响，以保证Java程序的可移植性。Java的整型常量默认为int型，声明long型常量须后加“l”或‘L’Java程序中变量通常声明为int 型，除非不足以表示较大的数，才使用longbit 计算机中的最小存储单位，byte计算机中基本存储单位下面一个小练习：class VariableTest1 {    public static void main(String[] args) {        //整型：byte（1字节=8bit）  short（2字节）  int（4字节）  long（8字节）        //byte 范围： -128~127         byte b1 = 12;        byte b2 = -128;        //b2=128 编译不通过        System.out.println(b1);        System.out.println(b2);// ② 声明long型变量，必须以“1”或“L”结尾        short s1 = 128;        int i1 = 12345;        long l1 = 345678586;        System.out.println(l1);    }}浮点类型：float 、double 与整数类型类似，Java浮点类型也有固定的表数范围和字段长度，不受具体的操作系统影响。浮点型常量有两种表示形式：十进制数形式：如：5.12 512.0f 0.512 (必须有小数点）科学计数法形式：如：5.12e2 512E2 100E-2float ：单精度，尾数可以精确到7有效数字。很多情况下，精度很难满足需求。double ：双精度，精度是float 的两倍。通常采用此类型。Java的浮点型常量默认为double 型，声明float 型常量，须后加“ f ”或“ F ” 字符类型：charchar 型数据用来表示通常意义上的“字符”（2字节）Java中所有字符都使用Unicode编码，故一个字符可以存储一个字母，一个汉字，或其他书面语的一个字符。字符型变量的三种形式：字符常量是用单引号（‘’）括起来的单个字符、例如：char c1 = ‘a’; char c2 = ‘中’; char c3 = ‘9’;Java中还可以使用转义字符‘ / ’ 来将其后字符转变为特殊字符型常量 。例如：char c3 = ‘\n’;‘\n’ 表示换行符直接使用Unicode 值来表示字符型常量：‘\uXXXX’。其中，XXXX代表一个十六进制整数。如： \u000a 表示\n。char类型是可以进行运算的。因为它都对应有Unicode码。小练习：编程就需要多动手，看会了理解了还需要多多动手class VariableTest1 {    public static void main(String[] args) {         double d1 = 12.3;        System.out.println(d1 + 1);         //定义float类型变量时，变量要以"f" 或"F"结尾        float f1 = 12.3f;        System.out.println(f1);         //② 通常，定义浮点型变量时，使用double变量        //3. 字符型：char(1字符=2字节)        //① 定义char型变量，通常使用一对''        char c1='a';        System.out.println(c1);         char c2 = '1';        char c3 = '中';        char c4 = '&';        System.out.println(c2);        System.out.println(c3);        System.out.println(c4);         //② 表示方式：1.声明一个字符；2.转义字符；3.直接使用Unicode值来表示字符型常量        char c5='\n';//换行符        c5='\t';//制表符        System.out.println("hello"+c5);        System.out.println("world");         char c6= '\u0123';        System.out.println(c6);        char c7 = '\u0043';        System.out.println(c7);    }}布尔类型： Boolean Boolean 类型用来判断逻辑条件，一般用于程序流程控制：if 条件控制语句while 循环控制语句do-while 循环控制语句for 循环控制语句boolean类型数据只允许取值true 和 false ，这点和C语言 不同。Java虚拟机中没有任何供Boolean值专用的字节码指令，Java语言表达所操作的Boolean 值，在编译之后都使用Java虚拟机中的int 类型数据类型代替：true 用1 表示，false 用0表示。代码示例：class VariableTest2 {    public static void main(String[] args) {//4. 布尔型：boolean//① 只能取两个值之一：true . false//② 常常在条件判断. 循环结构中使用        boolean bb1 = true;        System.out.println(bb1);         boolean isMarried=false;        if(isMarried){            System.out.println("禁止入内！");        }else {            System.out.println("可以参观！");        }    }}基本数据类型转换自动类型转换：容量小的类型自动转换为容量大的数据类型，数据类型按容量大小排序为：有多种类型的数据混合运算时，系统首先自动将所有数据转换成容量最大的那种数据类型，然后再 进行计算。byte、short、char之间不会相互转换，他们三者在计算时首先转换为int类型。boolean类型不能与其它数据类型运算。当把任何基本数据类型的值和字符串(String)进行连接运算时(+)，基本数据类型的值将自动转化为 字符串(String)类型。  代码示例：class VariableTest3{    public static void main(String[] args) {        byte b1=2;        int i1=129;         int i2=b1+i1;        long l3=b1+i1;        System.out.println(i2);        System.out.println(l3);         float f = b1 + i1;        System.out.println(f);//***************特别的**************************        char c1 = 'a'; //字符’a‘对应的数字是97        int i3=10;        int i4 = c1 + i3;        System.out.println(i4);    }}字符串类型：StringString不是基本数据类型，属于引用数据类型使用方式与基本数据类型一致。例如：String str= “abcd”;一个字符串可以串接另一个字符串，也可以直接串接其它类型的数据。代码示例：String类型变量的使用1. String属于引用数据类型2. 声明String类型变量时，使用一对""3. String可以和8种基本数据类型变量做运算，且运算只能是连接运算；+4. 运算的结果依然是String类型class  StringTest{    public static void main(String[] args) {        String s1="hello";        System.out.println(s1);        String s2 = "a";        String s3 = "";// char c = ''; //编译不通过//*******************************        int number = 1001;        String numberStr = "学号:";        String info = numberStr + number; //连接运算        boolean b1 = true;        String info1 = info + true;        System.out.println(info1);    }}练习：String str1 = 4; //判断对错：noString str2 = 3.5f + “”; //判断str2对错：yesSystem.out.println(str2); //输出：”3.5”System.out.println(3+4+“Hello!”); //输出：7Hello!System.out.println(“Hello!”+3+4); //输出：Hello!34System.out.println(‘a’+1+“Hello!”); //输出：98Hello!System.out.println(“Hello”+‘a’+1); //输出：Helloa1强制类型转换自动类型转换的逆过程，将容量大的数据类型转换为容量小的数据类型。使用时要加上强制转换 符：()，但可能造成精度降低或溢出,格外要注意。通常，字符串不能直接转换为基本类型，但通过基本类型对应的包装类则可以实现把字符串转换成 基本类型。如：String a = “43”; inti= Integer.parseInt(a);boolean 类型不可以转换为其它的数据类型。练习：判断是否能通过编译short s = 5;s = s-2; //判断：nobyte b = 3;b = b + 4;//判断：nob = (byte)(b+4);//判断：yeschar c = ‘a’;int i = 5;float d = .314F;double result = c+i+d; //判断：yesbyte b = 5;short s = 3;short t = s + b;//判断：no————————————————版权声明：本文为CSDN博主「Serendipity的人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/m0_57448314/article/details/126239827

一、栈相关基础概念① 先进先入。不是所有进完才可以出，入的同时也可以出。②用数组实现栈：入栈和出栈的时间复杂度是O(1)③用单链表实现栈：头插法： 入栈和出栈 O(1)尾插法：入栈和出栈 O(n)所以用单链表实现栈时一定要头入头出。④方法  push、peek、pop、size、empty二、队列相关基础概念① 队尾进，队头出。底层是个双向链表。②Queue是个接口，在实例化时必须实例化LinkedList的对象。        Queue<Integer> q = new LinkedList<>();③用单链表实现队列  ok④ 用数组实现队列 。必须使用循环数组。后面3.6有代码实现逻辑。④方法  offer、poll、peek、size、isEmpty三、OJ题3.1 不可能的出栈顺序核心：入的时候同时可以出3.2 中缀表达式中缀转后缀：按照自己的理解，从左往右加括号，先乘除后加减。再逐步将运算符移到括号后，移                        掉所有的(),就是rug计算中缀表达式的值：遇见数字入栈，遇到运算符就从栈出两个元素。先出的放在运算符的后面，后出栈的放在运算符前面。将计算结果再入栈。3.3 括号匹配 OJ链接：20. 有效的括号 - 力扣（LeetCode）实现代码：class Solution {    public boolean isValid(String s) {        Stack<Character> stack = new Stack<>();        for(int i = 0 ;i<s.length();i++){            char ch = s.charAt(i);            // 遇见左括号就入栈，注意是单引号            if(ch == '[' || ch == '{' || ch == '('){                stack.push(ch);            }else{                // 否则，就与栈顶元素进行比较                // 如果栈是空的，并且遇见的是右括号，直接返回false                // 判断栈空 不能使用stack==null                if(stack.isEmpty()){                    return false;                }else{                    char peek = stack.pop();                    if( (peek == '[' && ch == ']') || (peek == '{' && ch == '}') || (peek == '(' && ch ==')')){                        continue;                    }else{                        return false;                    }                }            }        }        if(stack.isEmpty()){            return true;        }else{            return false;        }    }}3.4 逆波兰表达式求值 OJ链接：150. 逆波兰表达式求值 - 力扣（LeetCode）实现代码：class Solution {     public int evalRPN(String[] tokens) {        Stack<Integer> stack = new Stack<>();        HashSet<String> set = new HashSet<>();        set.add("+");        set.add("-");        set.add("*");        set.add("/");        for(String str:tokens){            // 如果遇见的是不是运算符，是数字，就入栈            if(!set.contains(str)){                stack.push(Integer.parseInt(str));            }else{                // 遇见运算符，就弹出两个数字                int back = stack.pop();                int front = stack.pop();                HashMap<String,Integer> hashMap = new HashMap<>();                hashMap.put("+",front+back);                hashMap.put("-",front-back);                hashMap.put("*",front*back);                //  注意：back有可能为 0                 if(back != 0){                    hashMap.put("/",front/back);                }//计算结果，将结果入栈                int result = hashMap.get(str);                stack.push(result);            }        }        return stack.peek();    }}3.5 出栈入栈次序匹配 OJ链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) 解题思路：要点1：定义一个pos，记录popA数组中元素的位置。要点2：遍历pushA，依次将pushA中的元素入栈，判断栈顶元素和popA中的元素是否相同，相同就出栈，并观察popA中的下一个元素是否和新栈顶元素相等。如果不相等，入栈pushA的下一个元素实现代码：import java.util.*;import java.util.ArrayList; public class Solution {    public boolean IsPopOrder(int [] pushA,int [] popA) {        Stack<Integer> stack1 = new Stack();        int pos = 0;        for(int i=0;i<pushA.length;i++){            stack1.push(pushA[i]);            while(!stack1.isEmpty() && stack1.peek() == popA[pos]){                stack1.pop();                pos++;            }        }        if(stack1.empty()){            return true;        }        return false;    }}3.6 循环队列 OJ链接：622. 设计循环队列 - 力扣（LeetCode）​ 解题思路：要点1：为了区分队列空和满，约定：        rear指向数组最后一个元素的下一个位置，下一次添加数据，可以直接往rear位置上放        front == rear 队列空        rear的下一个元素是front，队列满了。（rear+1）%elem.length要点2：返回队列顶部元素，返回front所在位置元素，front向前移。为了保证front可以从3移到1，front=（front+1）%elem.length要点3：返回队列最后一个元素。如果rear=0，返回elem[elem.length-1].如果rear不为0，就返回elem[rear-1]实现代码：class MyCircularQueue {     private int[] elem;    private int front;    private int rear;     public MyCircularQueue(int k) {        elem = new int[k+1];    }        public boolean enQueue(int value) {        if(isFull()){            return false;        }        if(isEmpty()){            elem[0] = value;            front = 0;            rear = 1;            return true;        }        elem[rear] = value;        rear = (rear+1) % elem.length;        return true;    }        public boolean deQueue() {        if(isEmpty()){            return false;        }        front = (front+1) % elem.length;        return true;    }        public int Front() {        if(isEmpty()){            return -1;        }        return elem[front];     }        public int Rear() {        if(isEmpty()){            return -1;        }        if(rear == 0){            return elem[elem.length-1];        }        return elem[rear-1];     }        public boolean isEmpty() {        return rear == front;     }        public boolean isFull() {        if((rear+1)%elem.length == front){            return true;        }        return false;     }}3.7 用队列实现栈 OJ链接：225. 用队列实现栈 - 力扣（LeetCode）解题思路：要点1：有两个队列要点2：第一次放push数据时，默认放到队列1中要点3：添加元素时，添加到不为空的队列中，这样才能保证顺序要点4：出栈—》获得栈顶元素—》栈后入先出—》弹出最后一个入栈的元素因此，需要找出最后一个入队列的元素。将队列的前n-1个元素，放到另外一个队列中，剩下的就是最后一个入队列的元素实现代码：class MyStack {     private Queue<Integer> qu1;    private Queue<Integer> qu2;     public MyStack() {        qu1 = new LinkedList<>();        qu2 = new LinkedList<>();    }        public void push(int x) {        // 如果队列2是空的，就往队列1里面放。原因：只有放在不为空的队列中顺序才不会乱        if(qu2.isEmpty()){            qu1.offer(x);        }else{            qu2.offer(x);        }            }        public int pop() {        if(empty()){            return -1;        }        if(qu1.isEmpty()){            // 队列2不为空，队列先进先出，将队列前size-1个元素放到队列1中，剩下的最后一个元素就是最后入队列的，也就是栈的第一个元素，将其返回            int size = qu2.size();            while(size > 1){                qu1.offer(qu2.poll());                size--;            }            int result = qu2.poll();            return result;        }        if(qu2.isEmpty()){            int size = qu1.size();            while(size > 1){                qu2.offer(qu1.poll());                size--;            }            int result = qu1.poll();            return result;        }        return -1;    }    public int top() {        if(empty()){            return -1;        }        if(qu1.isEmpty()){            int size = qu2.size();            while(size > 1){                qu1.offer(qu2.poll());                size--;            }            int result = qu2.poll();            qu1.offer(result);            return result;        }        if(qu2.isEmpty()){            int size = qu1.size();            while(size > 1){                qu2.offer(qu1.poll());                size--;            }            int result = qu1.poll();            qu2.offer(result);            return result;        }        return -1;     }        public boolean empty() {        return qu1.isEmpty()&&qu2.isEmpty();    }}3.8 用栈实现队列 OJ链接：232. 用栈实现队列 - 力扣（LeetCode）​ 解题思路：要点1：有两个栈。存数据都存到栈1中，取数据都从栈2中取。要点2：取数据时，如果栈2是空的，就把栈1中的元素全放到栈2中。再从栈2中取。实现代码：class MyQueue {    private Stack<Integer> stack1;    private Stack<Integer> stack2;    public MyQueue() {        stack1 = new Stack();        stack2 = new Stack();    }        public void push(int x) {        stack1.push(x);    }        public int pop() {        if(empty()){            return -1;        }        if(stack2.empty()){            while(!stack1.empty()){                stack2.push(stack1.pop());            }        }        return stack2.pop();    }        public int peek() {        if(empty()){            return -1;        }        if(stack2.empty()){            while(!stack1.empty()){                stack2.push(stack1.pop());            }        }        return stack2.peek();     }        public boolean empty() {        return stack1.empty()&&stack2.empty();     }}3.9 最小栈 OJ链接：155. 最小栈 - 力扣（LeetCode） 解题思路：要点1：创建两个栈。一个栈存放所有的元素，另外一个栈存放栈中最小的元素要点2：第一次push数据，数据存放在两个栈中要点3：之后存放数据，该数据小于等于最小栈的栈顶元素，才能存放到最小栈和stack中。否则，就只能存放到stack中实现代码：class MinStack {    public Stack<Integer> stack;    public Stack<Integer> minStack;     public MinStack() {        stack = new Stack();        minStack = new Stack();    }        public void push(int val) {        // 如果第一次放元素，往stack和minStack里都放        if(stack.empty() && minStack.empty()){            stack.push(val);            minStack.push(val);            return;        }        // 如果存放的数据比minStack元素小，该元素同时放到两个栈中        if(val <= minStack.peek()){            stack.push(val);            minStack.push(val);            return;        }else{            // 否则，就只往stack中放            stack.push(val);            return;        }    }        public void pop() {        int peek = stack.pop();        if(peek == minStack.peek()){            minStack.pop();        }    }        public int top() {        if(stack.empty()){            return -1;        }        return stack.peek();     }        public int getMin() {        if(minStack.empty()){            return -1;        }        return minStack.peek();     }}————————————————版权声明：本文为CSDN博主「刘减减」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/weixin_44258092/article/details/126240946

opK问题输入数组arr，找出其中最大的k个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最大的4个数字是5、6、7、8。示例一： 输入：arr = [3,2,1], k = 2 输出：[3,2]或者[2,3]示例二： 输入：arr = [0,1,2,1], k = 1 输出：[2]解决方法1：先将这个数组排成降序，输出前K个数字即可！注意1.如果排升序，就建立大根堆2.如果排降序，接建立小根堆//交换函数void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}//堆的向下调整（小堆）void AdjustDown(int* a, int n, int parent){    //child记录左右孩子中值较小的孩子的下标    int child = 2 * parent + 1;//先默认其左孩子的值较小    while (child < n)    {        if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小        {            child++;//较小的孩子改为右孩子        }        if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小        {            //将父结点与较小的子结点交换            Swap(&a[child], &a[parent]);            //继续向下进行调整            parent = child;            child = 2 * parent + 1;        }        else//已成堆        {            break;        }    }}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    *returnSize = k;    int i = 0;    //建小堆    for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)    {        AdjustDown(arr, arrSize, i);    }    //排降序    int end = arrSize - 1;    while (end > 0)    {        Swap(&arr[0], &arr[end]);        AdjustDown(arr, end, 0);        end--;    }    //将最大的k个数存入数组    int* retArr = (int*)malloc(sizeof(int)*k);    for (i = 0; i < k; i++)    {        retArr[i] = arr[i];    }    return retArr;//返回最大的k个数}时间复杂度: O(N+NlogN) 空间复杂度：O(N)解决方法2：将数组建成一个大堆，取K次堆顶的数据就可以了。细节：每次拿走堆顶的数据后，需要将堆顶的数据和最后一个数据进行交换，然后重新建堆！//交换函数void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}//堆的向下调整（大堆）void AdjustDown(int* a, int n, int parent){    //child记录左右孩子中值较大的孩子的下标    int child = 2 * parent + 1;//先默认其左孩子的值较大    while (child < n)    {        if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大        {            child++;//较大的孩子改为右孩子        }        if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大        {            //将父结点与较大的子结点交换            Swap(&a[child], &a[parent]);            //继续向下进行调整            parent = child;            child = 2 * parent + 1;        }        else//已成堆        {            break;        }    }}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    *returnSize = k;    int i = 0;    //建大堆    for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)    {        AdjustDown(arr, arrSize, i);    }    //将最大的k个数存入数组    int* retArr = (int*)malloc(sizeof(int)*k);    int end = arrSize - 1;    for (i = 0; i < k; i++)    {        retArr[i] = arr[0];//取堆顶数据        Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据        //进行一次向下调整，不把最后一个数据看作待调整的数据，所以待调整数据为end=arrSize-1        AdjustDown(arr, end, 0);        end--;//最后一个数据的下标改变    }    return retArr;//返回最大的k个数}时间复杂度: O(N+klogN) 空间复杂度：O(N)弊端：如果待待续的数字有100亿个，那么存储100亿个整数究竟需要多大的内存空间？让咱们来大概估算一下： 我们知道1KB=1024byte，1MB=1024KB，1GB=1024MB，于是可以得出1GB大概有230个字节，也就是说1GB大概等于10亿个字节。 存储100亿个整型需要400亿个字节，所以存储100亿个整型数据需要40G左右的内存空间。前面两种算法的空间复杂度均为O(N)，并不适合用于这种海量数据处理。基于上述问题，我们重新建立一种新的解决方法！解决方法3：1.先将前K个数据建立小堆 2.将数组剩下的N-K个数字依次和堆顶的数据比较，如果大于堆顶的数据，进行替换，然后向下调整，使其仍为小堆。//交换函数void Swap(int* x, int* y){    int tmp = *x;    *x = *y;    *y = tmp;}//堆的向下调整（小堆）void AdjustDown(int* a, int n, int parent){    //child记录左右孩子中值较小的孩子的下标    int child = 2 * parent + 1;//先默认其左孩子的值较小    while (child < n)    {        if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小        {            child++;//较小的孩子改为右孩子        }        if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小        {            //将父结点与较小的子结点交换            Swap(&a[child], &a[parent]);            //继续向下进行调整            parent = child;            child = 2 * parent + 1;        }        else//已成堆        {            break;        }    }}int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){    *returnSize = k;    if (k == 0)        return NULL;    //用数组的前K个数建小堆    int i = 0;    int* retArr = (int*)malloc(sizeof(int)*k);    for (i = 0; i < k; i++)    {        retArr[i] = arr[i];    }    for (i = (k - 1 - 1) / 2; i >= 0; i--)    {        AdjustDown(retArr, k, i);    }    //剩下的N-k个数依次与堆顶数据比较    for (i = k; i < arrSize; i++)    {        if (arr[i]>retArr[0])        {            retArr[0] = arr[i];//堆顶数据替换        }        AdjustDown(retArr, k, 0);//进行一次向下调整    }    return retArr;//返回最大的k个数}————————————————版权声明：本文为CSDN博主「XG_JieJie」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/jiejiezuishuai/article/details/126245957