沈阳做网站的企业,网站怎么做海外推广,wordpress随机文章小工具,深圳seo公司排名目录
一、顺序表#xff08;数组#xff09;和链表总览
二、考情分析 2.1 从历年考情可以看出#xff0c;如果一个方法出现了第2次#xff0c;一般是以下情况#xff1a; 2.2 没有考过的地方
三、 共同操作或考法
3.1 多指针后移
3.2 逆置
3.3 空间换时间的操作
3.…目录
一、顺序表数组和链表总览
二、考情分析 2.1 从历年考情可以看出如果一个方法出现了第2次一般是以下情况 2.2 没有考过的地方
三、 共同操作或考法
3.1 多指针后移
3.2 逆置
3.3 空间换时间的操作
3.4 只保留首次出现的元素共同考法
3.4 排序 四、独有操作或考法
4.1 在顺序表中遍历找到符合要求的元素并删除
4.2 判断单链表是否存在环
4.3 找到两个链表中的共同结点 红色字体为线性表的共同操作 蓝色背景为下文有模板。绿色字体为统计的考频分析易想到不饶弯子的
一、顺序表数组和链表总览 第一步看到题目分析情况 多指针后移 2010较优解 2020年最优解三指针以空间换时间 2018排序或排序后利于操作 2013较优解 2016暴力解逆置 2010最优解三次逆置折半查找 2011最优解删除、插入只保留首次出现的元素第二步分析坑 表长是奇数或偶数时需讨论空表怎么处理第一步看到题目分析情况 多指针后移以空间换时间 2015排序头插法逆置 2019 前后指针 2012最优解快慢指针只保留首次出现的元素第二步分析坑 头插法是逆序建立链表尾插法是正序建立链表单链表只能向后查找故可能需要前驱指针不可修改链表结构有free()操作需malloc()结点 注意是否有头结点不同于数组改变下标链表是pp-next本质一样二、考情分析
2.1 从历年考情可以看出如果一个方法出现了第2次一般是以下情况
升级版。2011年能用二指针后移2020年需要设置三指针后移。数组考过换到链表考。如2015年和2018年都是以空间换时间太过重要。如快排是某一年的解的一部分。2013年是较优解2016年是暴力解。2.2 没有考过的地方
数组的插入删除链表的多指针后移不使用数组进行链表排序。都具有很大的考察可能。
202120222023年为图二叉树图。201820192020年都是线性表2024年很可能回归线性表。
三、 共同操作或考法
3.1多指针后移
条件多个线性表有序。
归并链表或数组使之有序。归并的升级操作找到两个序列中的相同元素或其他本质仍是比大小改变的是比的内容或对结果的操作。
多指针后移常用于有序线性表顺序表和链表都可以如果考试中给出有序的线性表优先考虑这种方式这种方式可以用于合并多个有序线性表、查找共同排序后第k个大小的元素等等归并排序就是用到了这种思想。 归并两个升序数组
void Merge(int A[], n, B[], m){ //数组A、B长度分别为n、mint C[nm]; //新数组int papbk0; //pa、pb作为遍历A、B的下标while (pan pbm) //直到有一个数组遍历完if (A[pa]B[pb]) //将小的那个数存入C数组C[k]A[pa];else C[k]B[pb];for (; pan; i)C[k]A[pa]; //将A中剩余的数存入C数组for (; pbm; j)C[k]B[pb]; //将B中剩余的数存入C数组
} 归并两个升序链表结果存放在LA中使之降序。 void MergeList LinkList LaLinkList Lb{
LNode *paLa-next,*pbLb-next; //分别是工作指针
LNode *r//头插法防止断链需要的指针
La-nextNULL; //结果链表初始化为空
while(paNULLpbNULL)
ifpa-datapb-data{
rpa-next; //r暂存pa的后继指针
pa-nextLa-next;
La-nextpa;
par //恢复pa为当前待比较结点
}
else{
rpb-next; //r暂存pb的后继指针
pb-nextLa-next;
La-nextpb;
pbr //恢复pb为当前待比较结点
}
if(pa!NULL) pbpa //pa不空的将原La剩余元素继续前插进结果链表La这里用到了一个小技巧
while(pb!NULL){ //pb不空的话将Lb剩余元素继续前插进结果链表La
rpb-next;
pb-nextLa-next;
La-nextpb;
pbr;
}
free(Lb); //将最后只剩下的一个Lb头结点free掉
} 归并两个升序链表结果存放在LA中使之升序 void Merge(LinkList *La, *Lb){ LNode *paLa-next, *pbLb-next; //pa、pb指向L1、L2第一个元素LNode *rLa; //新链表头节点为Lar指向末尾LNode *par, *pbr; //用来暂存pa-next和pb-nextwhile (pa!null pb!null) //直到有一个链表遍历完if (pa-datapb-data){ //将小的那个数存入新链parp-next; //par为pa下一个元素r-nextpa; //pa插入到r后面pa-nextNULL; //这是新链最后一个元素rpa; //尾指针r指向最后一个元素papar; //pa指向pa下一个元素}else{ pbrpb-next; //pbr为pb下一个元素r-nextpb; //pb插入到r后面pb-nextNULL; //这是新链最后一个元素rpb; //尾指针r指向最后一个元素pbpbr; //pb指向pb下一个元素}if (pa!null)r-nextpa; //将剩余部分连到r后面if (pb!null)r-nextpb; //将剩余部分连到r后面//La是合并后的升序链表注意最后此时r已经不是指向新链表尾元素的指针了3.2逆置 顺序表 数组可以任意下标到任意下表逆置 void Reverseint low,int high,Sqlist *L{ElemType temp; //用于暂存forint i0;i(high-low1)/2;i{//注意边界条件交换对应位置元素tempL.data[low];L.data[low]L.data[high];L.data[high]temp;}} 链表 链表用头插法逆置 LinkList ReverseLinkList L{LNode *p*r
//p为工作指针r为p的后继结点指针pL-next;L-nextNULL; //先断开头结点while(p!NULL){ rp-next;p-nextL-next; L-nextp; //将p结点插入到头结点后第一个结点插入时即为尾结点pr; //工作指针后移}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 (LR) return; //当前区间元素个数1则退出int pivot, iL, jR; //i和j是左右两个数组下标移动把A[L~R]中随机一个元素和A[L]交换 //快排优化使得基准值的选取随机pivotA[L]; //pivot作为基准值参与比较while (ij){while (ij A[j]pivot)j--;while (ij A[i]pivot)i;Rif (ij)swap(A[i], A[j]); //交换A[i]和A[j]}swap(A[L], A[i]); //将基准值放入他的最终位置
/*此时A[L~i-1]A[i]A[i1~R]*/Qsort(A, L, i-1); //递归处理左区间Qsort(A, i1, R); //递归处理右区间} 单链表排序 使用On大小的辅助数组进而可以使用第7章的排序算法最后重置链表的结点数据域。直接插入排序思想代码如下:void Sort(LinkList L){LNode *pL-next,*pre;LNode *rp-next;p-nextNULL; //构造只含一个数据结点的有序表pr;whilep!NULL{ //每次插入一个结点并使链表有序rp-next;preL //将pre置于头结点用于循环找到插入的合适位置while(pre-next!NULLpre-next-datap-data) prepre-next;p-nextpre-next; pre-nextp; //将*p插入到*pre之后pr //工作指针迭代}//第一个while}//void 四、独有操作或考法 4.1 在顺序表中遍历找到符合要求的元素并删除 两种方法 用count记录已保存的元素个数遍历时将需要保存的元素移动到下标count的位置并更新count值用count记录已删除的元素个数遍历时更新count或者将需要保留的元素前移count两种方法结束后都要修改L.length L.lengthcount;L.length-count;4.2 判断单链表是否存在环 如果有环快指针早晚追上慢指针 课后21题 4.3 找到两个链表中的共同结点 1对齐后前后指针同时扫描两链表 2for循环枚举 咸鱼学长统计我在这里保存一下方便查看
