408强化（二）线性表纯享版

目录

一、顺序表（数组）和链表总览

二、考情分析

 2.1 从历年考情可以看出，如果一个方法出现了第2次，一般是以下情况：

 2.2 没有考过的地方

三、 共同操作或考法

3.1 多指针后移

3.2 逆置

3.3 空间换时间的操作

3.4 只保留首次出现的元素（共同考法）

3.4 排序

 四、独有操作或考法

4.1 在顺序表中遍历，找到符合要求的元素并删除

4.2 判断单链表是否存在环

4.3 找到两个链表中的共同结点

---

红色字体为线性表的共同操作， 蓝色背景为下文有模板。绿色字体为统计的考频分析（易想到不饶弯子的）

一、顺序表（数组）和链表总览

第一步：看到题目，分析情况

1. 多指针后移                    2010较优解； 2020年最优解（三指针）
2. 以空间换时间                2018
3. 排序或排序后利于操作 2013较优解； 2016暴力解
4. 逆置                              2010最优解（三次逆置）
5. 折半查找                       2011最优解
6. 删除、插入
7. 只保留首次出现的元素

第二步：分析坑 

1. 表长是奇数或偶数时需讨论
2. 空表怎么处理

 第一步：看到题目，分析情况

1. 多指针后移
2. 以空间换时间     2015
3. 排序
4. 头插法逆置         2019 
5. 前后指针            2012最优解
6. 快慢指针
7. 只保留首次出现的元素

第二步：分析坑

1. 头插法是逆序建立链表，尾插法是正序建立链表
2. 单链表只能向后查找，故可能需要前驱指针
3. 不可修改链表结构
4. 有free()操作
5. 需malloc()结点 
6. 注意是否有头结点
7. 不同于数组改变下标，链表是p=p->next，本质一样

二、考情分析

2.1 从历年考情可以看出，如果一个方法出现了第2次，一般是以下情况：

1. 升级版。2011年能用二指针后移，2020年需要设置三指针后移。
2. 数组考过，换到链表考。如2015年和2018年都是以空间换时间
3. 太过重要。如快排，是某一年的解的一部分。2013年是较优解，2016年是暴力解。

 2.2 没有考过的地方

数组的插入删除；链表的多指针后移；不使用数组进行链表排序。都具有很大的考察可能。

2021，2022，2023年为图，二叉树，图。2018，2019，2020年都是线性表，2024年很可能回归线性表。

三、 共同操作或考法

3.1多指针后移

条件：多个线性表；有序。

1. 归并链表或数组，使之有序。
2. 归并的升级操作：找到两个序列中的相同元素或其他，本质仍是比大小，改变的是比的内容或对结果的操作。

多指针后移常用于有序线性表（顺序表和链表都可以），如果考试中给出有序的线性表，优先考虑这种方式，这种方式可以用于合并多个有序线性表、查找共同排序后第k个大小的元素等等，归并排序就是用到了这种思想。

归并两个升序数组

                       
void Merge(int A[], n, B[], m){  //数组A、B长度分别为n、mint C[n+m]; //新数组int pa=pb=k=0;                  //pa、pb作为遍历A、B的下标while (pa<n && pb<m)              //直到有一个数组遍历完if (A[pa]<B[pb])                //将小的那个数存入C数组C[k++]=A[pa++];else C[k++]=B[pb++];for (; pa<n; i++)C[k++]=A[pa];                  //将A中剩余的数存入C数组for (; pb<m; j++)C[k++]=B[pb];                  //将B中剩余的数存入C数组
}

归并两个升序链表，结果存放在LA中，使之降序。

void MergeList （LinkList &La，LinkList &Lb）{
LNode *pa=La->next,*pb=Lb->next; //分别是工作指针
LNode *r；//头插法防止断链需要的指针
La->next=NULL; //结果链表初始化为空
while(pa！=NULL&&pb！=NULL)
if（pa->data<=pb->data）{
r=pa->next; //r暂存pa的后继指针
pa->next=La->next;
La->next=pa;
pa=r； //恢复pa为当前待比较结点
}
else{
r=pb->next; //r暂存pb的后继指针
pb->next=La->next;
La->next=pb;
pb=r； //恢复pb为当前待比较结点
}
if(pa!=NULL) pb=pa  //pa不空的将原La剩余元素继续前插进结果链表La，这里用到了一个小技巧
while(pb!=NULL){ //pb不空的话将Lb剩余元素继续前插进结果链表La
r=pb->next; 
pb->next=La->next;
La->next=pb;
pb=r;
}
free(Lb); //将最后只剩下的一个Lb头结点free掉
}

归并两个升序链表，结果存放在LA中，使之升序

void Merge(LinkList *La, *Lb){           LNode *pa=La->next, *pb=Lb->next;    //pa、pb指向L1、L2第一个元素LNode *r=La;                      //新链表头节点为La，r指向末尾LNode *par, *pbr;                    //用来暂存pa->next和pb->nextwhile (pa!=null && pb!=null)         //直到有一个链表遍历完if (pa->data<pb->data){            //将小的那个数存入新链par=p->next;                    //par为pa下一个元素r->next=pa;                    //pa插入到r后面pa->next=NULL;                //这是新链最后一个元素r=pa;                           //尾指针r指向最后一个元素pa=par;                          //pa指向pa下一个元素}else{ pbr=pb->next;                  //pbr为pb下一个元素r->next=pb;                   //pb插入到r后面pb->next=NULL;               //这是新链最后一个元素r=pb;                          //尾指针r指向最后一个元素pb=pbr;                         //pb指向pb下一个元素}if (pa!=null)r->next=pa;                      //将剩余部分连到r后面if (pb!=null)r->next=pb;                      //将剩余部分连到r后面//La是合并后的升序链表，注意最后此时r已经不是指向新链表尾元素的指针了

3.2逆置

顺序表

数组可以任意下标到任意下表逆置

void Reverse（int low,int high,Sqlist *L）{ElemType temp;  //用于暂存for（int i=0;i<(high-low+1)/2;i++）{//注意边界条件，交换对应位置元素temp=L.data[low];L.data[low]=L.data[high];L.data[high]=temp;}}

链表

链表用头插法逆置

LinkList Reverse（LinkList L）{LNode *p，*r；
//p为工作指针，r为p的后继结点指针p=L->next;L->next=NULL;      //先断开头结点while(p!=NULL){    r=p->next;p->next=L->next;  L->next=p;   //将p结点插入到头结点后，第一个结点插入时即为尾结点p=r;                       //工作指针后移}return L；}

3.3 空间换时间的操作

空间保存状态。原序列最多只有n种情况，设置一个大小为n，初始值为0的数组A[n-1]用于保存这些情况。遍历一遍序列将出现的情况对于的数组置1。

3.4 只保留首次出现的元素（共同考法）

顺序表课后第06题

链表课后第12题

 3.4 排序

传统数组排序

快速排序的平均时间复杂度是O(nlogn)，平均空间复杂度是O(logn)，是考试中最快的不稳定排序算法，一般要用到排序时都使用快速排序。快速排序的最坏时间复杂度是O(n2)，最坏空间复杂度都是O(n)，但我们只需要加一个小优化就能避免最坏情况：即随机选择一个元素作为枢值。优化后最坏时间复杂度O(nlogn)，最坏空间复杂度O(logn)。
（注：快速排序有很多写法，交换式和挖坑式，不同写法中间过程不一样但只要能实现排序即可，本代码适用于算法大题，方便记忆）
代码如下：

 void Qsort(int A[], L, R){           //a数组保存数据，L和R是边界if (L>=R) return;              //当前区间元素个数<=1则退出int pivot, i=L, j=R;             //i和j是左右两个数组下标移动把A[L~R]中随机一个元素和A[L]交换   //快排优化，使得基准值的选取随机pivot=A[L];                     //pivot作为基准值参与比较while (i<j){while (i<j && A[j]>pivot)j--;while (i<j && A[i]<=pivot)i++;Rif (i<j)swap(A[i], A[j]);       //交换A[i]和A[j]}swap(A[L], A[i]); //将基准值放入他的最终位置
/*此时A[L~i-1]<=A[i]<=A[i+1~R]*/Qsort(A, L, i-1);          //递归处理左区间Qsort(A, i+1, R);           //递归处理右区间}

单链表排序

1. 使用O（n）大小的辅助数组，进而可以使用第7章的排序算法，最后重置链表的结点数据域。
2. 直接插入排序思想，代码如下:

void   Sort(LinkList &L){LNode *p=L->next,*pre;LNode *r=p->next;p->next=NULL;   //构造只含一个数据结点的有序表p=r;while（p!=NULL）{  //每次插入一个结点并使链表有序r=p->next;pre=L；  //将pre置于头结点，用于循环找到插入的合适位置while(pre->next!=NULL&&pre->next->data<p->data)  pre=pre->next;p->next=pre->next; pre->next=p; //将*p插入到*pre之后p=r； //工作指针迭代}//第一个while}//void

 四、独有操作或考法

4.1 在顺序表中遍历，找到符合要求的元素并删除

两种方法

1. 用count记录已保存的元素个数，遍历时将需要保存的元素移动到下标count的位置，并更新count值
2. 用count记录已删除的元素个数，遍历时更新count，或者将需要保留的元素前移count

两种方法结束后都要修改L.length

1. L.length=count;
2. L.length-=count;

4.2 判断单链表是否存在环

如果有环，快指针早晚追上慢指针

课后21题

4.3 找到两个链表中的共同结点

1）对齐后（前后指针），同时扫描两链表

2）for循环枚举

---

 咸鱼学长统计，我在这里保存一下方便查看