12306网站建设费用,wordpress主题开发出,wordpress 环保主题,本地建设网站软件目录如何应对数据结构的代码题#xff1f;采取的学习流程①首先对C语言的语法的熟悉②学习掌握基本代码的写法#xff0c;做到熟练2.1插入排序2.2快速排序2.3二分查找2.4树的遍历③跟着网上视频开始熟悉对一些问题的解答④结合真题的代码#xff0c;寻找其中的结题规律如何应…
目录如何应对数据结构的代码题采取的学习流程①首先对C语言的语法的熟悉②学习掌握基本代码的写法做到熟练2.1插入排序2.2快速排序2.3二分查找2.4树的遍历③跟着网上视频开始熟悉对一些问题的解答④结合真题的代码寻找其中的结题规律如何应对数据结构的代码题
一开始我对代码题还是无从下手的通过这些流程对408真题上的代码逐渐理解并能自己写出个大概。希望我的复习流程可以大家提供一定的参考意义。
采取的学习流程
首先要明白几点真题的代码是在一些基础代码的基础上进行增加参数或者增加步骤进而得到的
①首先对C语言的语法的熟悉
包括对结构体的定义指针、数组、重命名以及一些打印输出的句子。 学习的资料网址菜鸟教程
基础的一些语法格式
定义结构体、以及重命名
typedef struct node{int data;struct node next;
}Lnode ,*List
//这里利用typdef对结构体数据类型进行重命名方便后面定义变量
//结构体变量struct node,命名为了Lnode结构体变量struct node的指针命名为了List
那么你可以用分别用Lnode代替struct node List 代替struct node* 进行变量的定义数组
int nums[5]{1,2,3,4,5};
nums(int *)malloc(sizeof(int)*(n1));打印
char *a123asd
printf(();
printf(%c,s);②学习掌握基本代码的写法做到熟练
基础代码
2.1插入排序
链表实现 注意插入排序链表实现的特点 维护的几个变量 LastSorted已经排好序的最后一个结点 curr需要进行插入排序的当前结点 Pre寻找第一个大于当前结点之前的结点
//将结点指针变量的声明符号重新定义为 list 方便后续定义结点指针变量
typedef struct ListNode* list;
struct ListNode *insertionSortList(struct ListNode *head) {if (head NULL) {return head;}list dummyHead malloc(sizeof(struct ListNode));//虚拟头结点为了更好的对第一个元素之前进行插入dummyHead-val 0;dummyHead-next head;list lastSorted head;//已排序元素的最后一个元素list curr head-next;//当前需要进行判断的元素while (curr ! NULL) {//当当前元素大于等于已排好的最后元素直接改最后元素if(lastSorted-valcurr-val){lastSortedlastSorted-next;}//当当前元素小于已经排好元素时需要从头开始找到第一个大于当前元素的前一个结点else{list predummyHead;while(pre-nextpre-next-valcurr-val)//当下一个结点大于时或者当前结点为最后一个结点时跳出循环{prepre-next;}lastSorted-nextcurr-next;//最后结点不变最后结点的下一个结点变为原节点的下一节点curr-nextpre-next;//当前结点的下一节点先修改pre-nextcurr;//然后修改pre结点的下一节点为当前结点}currlastSorted-next;//将已排序的后一个元素进行排序}return dummyHead-next;//最后返回head结点
}
数组实现
int insersorted(int a[],int n)
{for(int i2;in;i)//从第二个元素开始{if(a[i]a[i-1])//小于往前插入{a[0]a[i];for(int ji-1;a[j]a[0];j--){a[j1]a[j];}a[j1]a[0]}
}2.2快速排序
//设计两个函数
//第一个函数实现每趟的交换排序
int partition(int *nums,int low,int high)
{ int temnums[low];while(lowhigh){while(lowhighnums[high]tem)high--;nums[low]num[high];while(lowhighnums[low]tem)low;nums[high]nums[low];}nums[low]tem;return low;//最后返回元素被最终放置的位置然后以此为基点对左右两边的数进行划分
}
//第二个函数实现递归的调用
int * quicksort(int * nums,int low,int high)
{if(lowhigh){int pivpartition(nums,low,high);quicksort(nums,piv1,high);quicksort(nums,low,piv-1);}
}2.3二分查找
维护的变量 low最左边的位置 high最右边的位置 middle中间的位置 每次根据中间位置值与目标变量的大小关系调整low和high的值
int searchInsert(int* nums, int numsSize, int target){int low0,highnumsSize-1,middle;while(lowhigh){middle(lowhigh)/2;if(nums[middle]target)return middle;else if(nums[middle]target){lowmiddle1;}else{highmiddle-1;}}if (nums[middle]target)return middle;elsereturn middle1;
}2.4树的遍历
递归实现
//先序遍历
typedef struct BiNode
{struct BiNode* lchild,rchild;int data;
}BNode,*BiTree;
void preorder(BiTree T)
{
if(T!NUll){visit(T);preorder(T-lchild);preorder(T-rchild);}
}
//中序遍历
void inorder(Bitree T)
{if(T!NUll){inorder(T-lchild);visit(T);inorder(T-rchild);}
}
//后续遍历
void postorder(Bitree T)
{
if(T!NUll){postorder(T-lchild);postorder(T-rchild);visit(T);}
}非递归实现
//中序遍历
void inorder(BiTree T)
{InitStack(S);//用于存储有左子树的根节点BiTree pT;//用于向下探索结点while(P||isempty(S))//当T不为空同时栈内存在元素时循环{//如果当前结点不为空则把器左节点放入栈中if(p){push(S,p);pp-lchild;}else{pop(S,p);visit(p);pp-rchild;}}
}
③跟着网上视频开始熟悉对一些问题的解答
B站一位up主的的讲解视频23考研数据结构编程代码题逐句精讲 看完视频并写完代码后对于线性表的相关问题会有比较好的理解。 看视频时注重积累相关问题的结题方法需要设置几个参数。 涉及的题目的结题代码
④结合真题的代码寻找其中的结题规律
2009年 寻找倒数第k个结点利用两个指针pq q先向后探测到第k-1个结点如果此节点不是最后一个结点那么pq共同向后移动知道q为最后一个结点此时的p即为所求、
int find_k(Lnode *head, int k){Lnode *phead,*qhead;int countk-1;while(countk-1q-next){qq-next;}if(q-nextnull) return 0;while(q-next){pp-next;qq-next;}printf(倒数第%d个位置上的值为%d,k,p-data);return 1;
}2010年 将数组元素玄幻啊左移p位那么可以采用对前p位反转后n-p为反转然后整体反转
void reverse(int *num,int low, int high)
{int mark(lowhigh)/2,tem;for(int i0;imark;i){temnum[i];num[i]num[lowhigh-i];num[lowhigh-i]tem;}
}
void leftmove(int *num,int p,int n){reverse(num,0,p-1);reverse(num,p,n-1);reverse(num,0,n-1);
} 2011年 因为s1、s2等长为L那么中位数为第L个元素因为s1、s2均为升序排序所以我可以用p、q表示s1、s2的下标每次比较s1[p]s2[q]的大小更小的元素指针后移同时记录下次数更小的那个数当后移了L次时即找到了答案。 时间复杂度为O(n),空间复杂度为O(1)
int find_middle(int* s1,int* s2,int L){int count0,p0,q0,pre_min;whiel(countL){if(s1[p]s2[q]){pre_mins1[p];p;}else{pre_mins2[q];q;}count;return pre_min;}2012年 思路 后缀的起始位置的点的特点结点的地址的指针相同。注意不是结点的值相同虽然这里结点的值页相同但是只考虑地址相同会更方便 我们可以从后往前看只要我们同时从后面往前数第一个重合的元素开始比较然后第一个相同的就是我们要找的。
所以可以先分别算出str1、str2的长度 然后算出长度的差值distance 用pq分别记录各链表的点的指针 对于长的链表p先后移distance个结点然后pq开始比较
Lnode* find(Lnode* str1,Lnode* str2)
{int m0,n0;Lnode* temstr1-next;//先计算长度m、nwhile(tem){m;temtem-next;}temstr2-next;while(tem){n;temtem-next;}Lnode *pstr1-next;Lnode *qstr2-next;//将链表队尾对齐while(mn){pp-next;m--;}while(nm){qq-next;n--;}int flag1;//寻找第一个相同地址的结点结束条件可能是找到最后没有找到那么就是nullwhile(flagpq){if(pq)flag0;else{pp-next;qq-next;}return p;
}
2014年 基础代码先序遍历的递归实现 积累点 涉及对于需要考虑层数的添加变量deep。
//在先序遍历的递归的基础上加上参数deep深度然后在找到叶子节点时计算权重weight*deep每次进行累加
typedef struct node{struct node * left,*right;int weight;
}*Btree;
static int count0;//用来记录权重void func1(Btree root,int deep)
{if(root-leftNULLroot-rightNULL){countcount(root-weight)*deep;//找到叶子节点时计算权重}if(root-left)func1(root-left,deep1);//未找到叶子结点继续往下找深度1if(root-right)func1(root-right,deep1);
}func1(root,0)//一开始我根节点属于第0层
return count;
2015 思路 首先目标是删除绝对值相同的结点然后这里只考虑时间复杂度尽可能高效所以我们用空间换时间采取数组存放对于以访问数的情况。 数组下标为数的绝对值0表示未被访问到1表示已存在。数组的长度为n1 空间复杂度on创建的数组 时间复杂度om只要扫描一遍链表即可
typedef struct Lnode{int data;struct Lnode *link;
}List,LNode;
List funt(List L,int n)
{int * nums(int*)malloc(sizeof(int)*(n1));List tem,preL;int num;while(L-link){ numL-link-data;if(nums[num]0)num[num]1;else{tempre-link;pre-linkpre-next-next;free(tem);}}free(nums);return L;
} 2016 思路 首先满足n1-n2最小s1-s2绝对值最大那么我们需要找出最小n1个数以及最大的n2个数同时n1n/2(向下取整n1) 采用快速排序每次排序对元素进行划分确定一个元素的最终位置将元素分为左右两部分左边的都是小于其的右边的都是大于其的。 所以我们需要在快速排序的基础上尽快的排到第n/2这个位置。
int func(int *nums ,int n)
{int low0,highn-1;int pre_low0,pre_highn-1;//用来保存前一次的low和high 的值因为每次排序后low最终等于highint markn/2,int flag1;tem;//mark最为最终要排序的点的位置 flag 用来控制循环的进行while(flag){ temnums[low];while(lowhigh){while(nums[high]temlowhigh)high--;nums[low]nums[high];while(nums[low]temlowhigh)low;nums[high]nums[low];}nums[low]tem;//排序完一次查看一下排好的元素的位置与最终位置的差距if(lowmark){flag0;}else{if(lowmark){lowlow1;pre_lowlow;highpre_high;}else{highlow-1;pre_highhigh;lowpre_low;} }}int s10,s20;for(int i0;in;i){if(imark)s1s1nums[i];else s2s2nums[i];}return s2-s1;
}2017 思路 首先二叉树的采用递归的中序遍历 首先对于每个结点来说要打印结点的字符串。 然后对于根节点和叶子结点直接打印字符串而对于非叶子结点需要先打印“然后打印”.
所以需要对结点进行区分区分叶子结点只需要判断结点的左右子树是否都为空而判断根节点非叶结点我们只能引入层数deep变量来加以区分
void func(BTree *root,int deep)
{if(root-leftNULLroot-rightNULL)printf(%c,root-data);else{if(deep1)printf(();if(root-left!NULL)func(root-left,deep1);prinf(%c,root-data);if(root-right!NULL)func(root-right,deep1);if(deep1)printf(();}
}
void real(BTree * root)
{func(root,1);
}2019 思路 首先找到链表的中点结点 然后对中点后的结点采用头插法进行逆序 然后对中点后的结点按指定位置插入中点前方的结点 维护的变量 p中间结点 q用来逆序以及插入时作为标记后面结点的指针
void reorder(Lnode* head ){Lnode * p,q,r,s;phead;qhead;while(q-next){pp-next;qq-next;if(q-next)qq-next;//p每次移动一下q每次移动两下。假设7个节点当为奇数个结点时p移动到了4位置当为偶数个结点6时p移动到了3}保持p结点不变头插法逆转后续序列qp-next;p-nextNULL;while(q){rq-next//记录下一个要插入的结点q-nextp-next;p-nextq;qr;}shead-next;//第一个结点qp-next;//中点的后一个结点需要第一个插入到前面的结点p-nextNULL;//p最终变为为最后的结点下一节点为空while(q){rq-next;//记录下一个需要插入的结点q-nextp-next;//先记录p的下一个结点p-nextq;//p的下一个结点为qpq-next;//下一个p为q的nextqr;}
}
时间复杂度为On空间复杂度为O1 这里需要多次对链表进行操作需要对头插法实现序列的转置比较熟悉
2020 首先看清题目要求只是输出最小距离不需要输出相应的三元组。 这类问题先进行问题的简化搞清楚我们要求什么。 要使距离D最小怎么找。 假设a《b《c 那么D b-a c-b c-a 2(c-a)也就最大值-最小值的两倍。 那么要使D最小我们就要不断的让最小值a向最大值c接近。 假设用abc分别表示3个数组中遍历的数那么我们每次将其中最小的数的下标后移1知道某个数组的下标超出数组的长度时停止。 为什么的数不需要计算了 首先当一个列表的元素到了末尾说明上一次结尾找出的最小值为这个元素的最后一个元素然后下标进行加1但此时数组里已经没有元素了。如果你取其他的数组里的元素由于数组是从小到大排序的那么其他数组的后一个元素必然导致与最小值的距离最变大既c-a变大相当于a以及不变了你去移动其他元素。 所以此时得到的就是最小距离了。
#define MAX 9999999;
//计算绝对函数
int abs_(int a,int b){if(ab) return a-b;else return b-a;}
int calculate(int* s1,int n1,int*s2,int n2,int* s3,int n3){int i0,j0,k0;int pre_minMAX;int dis0;while(in1jn2kn3){disabs(s1[i],s2[j])abs_(s2[j],s3[k])abs_(s3[j],s1[k]);if(dispre_min){pre_mindis;}if(s1[i]s2[j]s1[i]s3[k]){i;}else if(s2[j]s3[k]s2[j]s1[i]){j;}else{ k;}}return pre_min;
}
