考研数据结构 |
您所在的位置：网站首页 › 题目头的好处 › 考研数据结构 |
|
考研数据结构目录 1、顺序表（链表操作） （1）基础单链表操作(模板) （2）必看链表习题(常规套路) 2、堆栈与队列 （1）栈的基本操作 （2）栈的链表操作 后续将持续更新~ 前言：首先这四个题都是考研真题，不要觉得它就难了，很有锻炼思维的作用，自我感觉都是很基础的，而且最重要的一点是如何处理这一类问题是有固定方法的。 这四个题可以说也是固定思想套路，都是建立一个新的链表进行辅助操作，在考研中算是比较公认的一种处理方法了，小伙伴们平常做题也可以使用。 补充：有些小伙伴可能说会说，“我还有更好的方法或者更简洁的代码”，当然肯定会出现这种情况，我也并不反对，但是你的代码是给阅卷老师看的，这种新建链表的方法往往结构会更清晰。 建议：这些题小伙伴们可以先自己独立思考一下，建议先在脑子里有自己的动态想法 目录 1、倒置链表 2、合并有序链表 3、将链表中所有负数结点移动到所有整数之前 4、将最小节点移动到第一个节点的前面 5、完整运行代码 1、倒置链表 //倒置链表 void reverse(NODE * head){ //方法：建议一个新的节点专门存 //注意：这里给出的head没有头节点滴 NODE * head_a,*p,*s; head_a=(NODE*)malloc(sizeof(NODE)); head_a->next=NULL; s=head_a; p=head; while(p){//或者head->next head=p->next;//1、孤立结点 p->next=s->next;//2、插到新节点后面 s->next=p; p=head; // 3、返回p指针 } head=s->next;//4、把head和head_a对接 printLink(head); } 2、合并有序链表 //合并有序链表 void merge(NODE * head_a,NODE * head_b){ NODE * head_c,*p1,*p2,*s; head_c=(NODE*)malloc(sizeof(NODE)); head_c->next=NULL; s=head_c;p1=head_a;p2=head_b; while(p1&&p2){ if(p1->datadata){//p小，先排head_a链表 head_a=p1->next;//孤立 p1->next=s->next; s->next=p1; s=p1; p1=head_a; }else{ head_b=p2->next; p2->next=s->next; s->next=p2; s=p2; p2=head_b; } if(p1){ s->next=p1; }else{ s->next=p2; } } printLink(head_c); } 3、将链表中所有负数结点移动到所有整数之前 //把负数移动到所有整数之前 void move(NODE * head){ //初始化 NODE * head_a,*p,*q,*s; head_a=(NODE*)malloc(sizeof(NODE)); s=head_a;head_a->next=NULL; //为便于操作 给它原始链表加一个头节点 p= (NODE*)malloc(sizeof(NODE)); p->next=head;head=p; //进入正题 while(p->next){ if(p->next->datanext; p->next=q->next;//最后q(也就是负数节点)被孤立出来 q->next=s->next; s->next=q; s=q; }else{ p=p->next; } } //最后把head_a上所有的负数节点加到原链表上 q->next=head->next;//最后是q在head_a的尾部 free(head);//把原来多余的头节点释放掉 head_a=head_a->next;//把新建的头结点孤立掉 printLink(head_a); } 4、将最小节点移动到第一个节点的前面 //把最小节点移动到第一个节点的前面 void moveMin(NODE * head){ NODE *p,*q,*s; //为原来节点加一个头结点 p=(NODE*)malloc(sizeof(NODE)); p->next=head; head=p; //进入正题 p=head; q=head->next; while(q->next){ if(q->next->datanext->data){ p=q; } q=q->next; } //最后p为最小值的 前一个节点 s=p->next;//s就是最小值的节点 p->next=s->next;//孤立s节点 s->next=head->next; head->next=s; head=head->next;//删除head头结点 printLink(head); } 5、完整运行代码 #include typedef struct node{ int data; struct node * next; }NODE; //打印节点 void printLink(NODE * head){//打印结点 NODE * p; p=head; while(p->next){ printf("%2d ",p->data); p=p->next; } printf("%d\n",p->data);//上面那个循环不会打印最后一个，把最后一个也打印 } //创建节点 NODE * creat(){ NODE * head,*p,*s; head=(NODE*)malloc(sizeof(NODE)); p=head; head->next=NULL; int flag=-1; for(int i=1;i//或者head->next head=p->next;//1、孤立结点 p->next=s->next;//2、插到新节点后面 s->next=p; p=head; // 3、返回p指针 } head=s->next;//4、把head和head_a对接 printLink(head); } //合并有序链表 void merge(NODE * head_a,NODE * head_b){ NODE * head_c,*p1,*p2,*s; head_c=(NODE*)malloc(sizeof(NODE)); head_c->next=NULL; s=head_c;p1=head_a;p2=head_b; while(p1&&p2){ if(p1->datadata){//p小，先排head_a链表 head_a=p1->next;//孤立 p1->next=s->next; s->next=p1; s=p1; p1=head_a; }else{ head_b=p2->next; p2->next=s->next; s->next=p2; s=p2; p2=head_b; } if(p1){ s->next=p1; }else{ s->next=p2; } } printLink(head_c); } //把负数移动到所有整数之前 void move(NODE * head){ //初始化 NODE * head_a,*p,*q,*s; head_a=(NODE*)malloc(sizeof(NODE)); s=head_a;head_a->next=NULL; //为便于操作 给它原始链表加一个头节点 p= (NODE*)malloc(sizeof(NODE)); p->next=head;head=p; //进入正题 while(p->next){ if(p->next->datanext; p->next=q->next;//最后q(也就是负数节点)被孤立出来 q->next=s->next; s->next=q; s=q; }else{ p=p->next; } } //最后把head_a上所有的负数节点加到原链表上 q->next=head->next;//最后是q在head_a的尾部 free(head);//把原来多余的头节点释放掉 head_a=head_a->next;//把新建的头结点孤立掉 printLink(head_a); } //把最小节点移动到第一个节点的前面 void moveMin(NODE * head){ NODE *p,*q,*s; //为原来节点加一个头结点 p=(NODE*)malloc(sizeof(NODE)); p->next=head; head=p; //进入正题 p=head; q=head->next; while(q->next){ if(q->next->datanext->data){ p=q; } q=q->next; } //最后p为最小值的 前一个节点 s=p->next;//s就是最小值的节点 p->next=s->next;//孤立s节点 s->next=head->next; head->next=s; head=head->next;//删除head头结点 printLink(head); } int main(){ NODE * head,*p,*s; head=creat(); // reverse(head); move(head); } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |