柯桥建设局网站,如何做汉服,wordpress 4.0 中文主题,做网站首页2019年(单链表)41.(13分)设线性表采用带头结点的单链表保存#xff0c;链表中的结点定义如下:typedef struct node {int data;struct node* next;}NODE;请设计一个空间复杂度为O(1)且时间上尽可能高效的算法#xff0c;重新排列L中的各结点#xff0c;得到线性表L(q,a,,a,an…2019年(单链表)41.(13分)设线性表采用带头结点的单链表保存链表中的结点定义如下:typedef struct node {int data;struct node* next;}NODE;请设计一个空间复杂度为O(1)且时间上尽可能高效的算法重新排列L中的各结点得到线性表L(q,a,,a,an-1,as,an-2y…)。要求:(1)给出算法的基本设计思想。(2)根据设计思想采用C或C语言描述算法关键之处给出注释。(3)说明你所设计的算法的时间复杂度。思路因为题目要求要空间复杂度为O(1)所以我们不能再额外申请空间了然后再找到链表的中间结点将其一分为二分为L和L2的单链表并将L2链表进行原地逆置最后再将L和L2进行混合合并。一、找到中间结点并一分为二。思路定义两个指针p1和p2p1指针每次走两步p2指针每次走一步当p1指针走到最后p2指针必定走到中间结点。写代码的过程中还应该注意总结点是奇数还是偶数代码段void find_middle(LinkList L,LinkList L2) //寻找链表中间结点并设置好L2链表
{L2 (LinkList)malloc(sizeof(LNode)); //设置第二条链表的头结点 LinkList pcur,ppre; //双指针法pcur跨两步ppre跨一步。 ppre pcur L-next; //一开始都指向第一个结点即首元结点 while(pcur) {pcur pcur-next;if(pcur NULL) //防止pcur为空 {break;}pcur pcur-next; //若此处pcur为空则不满足循环条件 if(pcur NULL) //为了使得偶数个ppre依然指向a1a2到a6中的a3结点 {break;}ppre ppre-next;}L2-next ppre-next; //由L2头结点指向后面一半链表,L2的第一个结点是此时ppre所指向的结点 ppre-next NULL; //此时的ppre为前一半链表的最后一个结点最后一个结点的指针域应该为NULL
}二、将L2原地逆置思路分别定义3个指针r、s、t让r、s、t分别指向前三个结点再让第二个结点指向第一个结点然后r、s、t同时向后移动一位再让第三个结点指向第二个结点然后r、s、t同时向后移动一位如此往复循环当t为null时循环结束。因为原有链表的头结点变成链表最后一个结点最后一个结点应该指向NULL最后让L2头结点指向新的首元结点s。代码段void reverse(LinkList L2) //逆转。因为L2的头结点不会发生改变
{LinkList r,s,t;r L2-next; //一开始r指向首元结点 if(r NULL){return ;//链表为空 }s r-next; //一开始r指向s if(s NULL){return;//链表只有1个结点 } t s-next; //一开始让s指向twhile(t){s-next r; //原地逆置让s指向r r s; //以下3句是3个指针同时向后移动一位 s t;t t-next; } s-next r;L2-next-next NULL;//逆置后原本链表的第一个结点的指针域为空。即逆置后新链表的最后一个结点。 L2-next s; //此时s是逆置后链表的第一个结点L2的头结点应该指向它
}三、将L与L2进行混合合并思路将L与L2链表合并合并时分别轮流放入一个结点。定义3个指针pc、p、q一开始指针pc指向L链表的首元结点指针p指向L链表的第二结点指针q指向L2链表的首元结点。并且让pc指针始终指向合并后新链表的尾部,使用p指针始终指向链表L待放入的结点q指针始终指向链表L2待放入的结点。代码段void merge(LinkList L,LinkList L2) //将L与L2混合并合并
{LinkList pcur,p,q;pcur L-next; //pcur一开始指向L链表的首元结点。pcur始终指向组合后新链表的链表尾p pcur-next; //p指向L链表的第二个结点。p用来遍历L链表。 q L2-next; //q指向L2链表的首元结点。q用来遍历L2的链表。 while(p!NULL q!NULL) //以下步骤画图就会非常的直观。 {pcur-next q;q q-next;pcur pcur-next;pcur-next p;p p-next;pcur pcur-next; } //任何一个链表都可能剩余一个结点放进来即可。 if(p!NULL){pcur-next p;}if(q!NULL){pcur-next q;}
}总代码#includestdio.h //2019年考研408真题第41题
#includestdlib.htypedef int ElemType;
typedef struct LNode{ElemType data; //数据域 struct LNode *next; //指针域
}LNode,*LinkList;void list_tail_insert(LinkList L) //尾插法建立链表
{L (LinkList)malloc(sizeof(LNode));L-next NULL;ElemType x;scanf(%d,x);LNode *s;//用来指向申请的新结点LNode *rL;//r始终指向链表尾部while(x ! 999){s (LinkList)malloc(sizeof(LNode));s-data x;r-next s; //r-next指向s结点r s; //r要指向新的尾部 scanf(%d,x); } r-next NULL; //让尾结点的next为NULL
}void find_middle(LinkList L,LinkList L2) //寻找链表中间结点并设置好L2链表
{L2 (LinkList)malloc(sizeof(LNode)); //设置第二条链表的头结点 LinkList pcur,ppre; //双指针法pcur跨两步ppre跨一步。 ppre pcur L-next; //一开始都指向第一个结点即首元结点 while(pcur) {pcur pcur-next;if(pcur NULL) //防止pcur为空 {break;}pcur pcur-next; //若此处pcur为空则不满足循环条件 if(pcur NULL) //为了使得偶数个ppre依然指向a1a2到a6中的a3结点 {break;}ppre ppre-next;}L2-next ppre-next; //由L2头结点指向后面一半链表,L2的第一个结点是此时ppre所指向的结点 ppre-next NULL; //此时的ppre为前一半链表的最后一个结点最后一个结点的指针域应该为NULL
} void reverse(LinkList L2) //逆转。因为L2的头结点不会发生改变
{LinkList r,s,t;r L2-next; //一开始r指向首元结点 if(r NULL){return ;//链表为空 }s r-next; //一开始r指向s if(s NULL){return;//链表只有1个结点 } t s-next; //一开始让s指向twhile(t){s-next r; //原地逆置让s指向r r s; //以下3句是3个指针同时向后移动一位 s t;t t-next; } s-next r;L2-next-next NULL;//逆置后原本链表的第一个结点的指针域为空。即逆置后新链表的最后一个结点。 L2-next s; //此时s是逆置后链表的第一个结点L2的头结点应该指向它
}void merge(LinkList L,LinkList L2) //将L与L2混合并合并
{LinkList pcur,p,q;pcur L-next; //pcur一开始指向L链表的首元结点。pcur始终指向组合后新链表的链表尾p pcur-next; //p指向L链表的第二个结点。p用来遍历L链表。 q L2-next; //q指向L2链表的首元结点。q用来遍历L2的链表。 while(p!NULL q!NULL) //以下步骤画图就会非常的直观。 {pcur-next q;q q-next;pcur pcur-next;pcur-next p;p p-next;pcur pcur-next; } //任何一个链表都可能剩余一个结点放进来即可。 if(p!NULL){pcur-next p;}if(q!NULL){pcur-next q;}
}void print_list(LinkList L) //打印输出链表
{L L-next;while(L ! NULL){printf(%3d,L-data);L L-next;}printf(\n);
}int main()
{LinkList L; //L是头指针 LinkList search; //用来存储拿到的某一个结点 list_tail_insert(L); //输入数据可以为数据 print_list(L);//链表打印LinkList L2NULL; find_middle(L,L2); //寻找中间结点并返回第二条链表 。只有一个结点时L2中是没有结点的 printf(-----------------------------\n);print_list(L);print_list(L2);printf(-----------------------------\n);reverse(L2);print_list(L2);printf(-----------------------------\n);merge(L,L2);free(L2);print_list(L);return 0;
}
