2019年408数据结构大题代码实现
2019年408数据结构大题代码实现请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L (a1 ,a2 ,a3 ,...,an-2,an-1,an)。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。（3）说明你所设计的算法的时间复杂度
·
题目描述：
设线性表 L (a1 ,a2 ,a3 ,...,an -2,an-1 ,an ) 采用带头结点的单链表保存，链表中
的结点定义如下：
typedef struct node {
int data;
struct node* next;
} NODE；
请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，
得到线性表 L (a1 ,a2 ,a3 ,...,an -2,an-1 ,an )。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度
完整实现代码：
#include <iostream>
#include "stdio.h"
#include "stdlib.h"
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*LinkList;
void list_tail(LinkList &L){
L=(LinkList) malloc(sizeof (LNode));
L->next=NULL;
int e;
LinkList q,p;
p=L;
scanf("%d",&e);
while (e!=9999){
q=(LinkList) malloc(sizeof (LNode));
q->data=e;
p->next=q;
p=q;
scanf("%d",&e);
}
p->next=NULL;
}
void Print(LinkList L){
LinkList p=L->next;
while(p){
printf("%3d",p->data);
p=p->next;
}
printf("\n");
}
void get_medium(LinkList L,LinkList &L2){
L2=(LinkList) malloc(sizeof (LNode));
LinkList p_two,p_one;
p_one=p_two=L->next;
while (p_two){
p_two=p_two->next;
if (p_two==NULL){
break;
} else{
p_two=p_two->next;
if(p_two==NULL){
break;
}
p_one=p_one->next;
}
}
L2->next=p_one->next;
p_one->next=NULL;
}
void reversed(LinkList &L2){
LinkList r,s,t;
r=L2->next;
if (r==NULL){
return;//链表为空 无需逆序
}
s=r->next;
if(s==NULL){
return;//链表只有一个元素 无需逆序
}
t=s->next;
while(t!=NULL){
s->next=r;
r=s;
s=t;
t=t->next;
}
s->next=r;
(L2->next)->next=NULL;
L2->next=s;
}
void merge(LinkList L,LinkList L2){
LinkList p,q,p_now;
p_now=L->next;
p=p_now->next;
q=L2->next;
while(p!=NULL&&q!=NULL){
p_now->next=q;
p_now=q;
q=q->next;
p_now->next=p;
p_now=p;
p=p->next;
}
while(p!=NULL){
p_now->next=p;
p=p->next;
}
while(q!=NULL){
p_now->next=q;
q=q->next;
}
}
int main() {
LinkList L,L2;
list_tail(L);//利用尾插法实现的链表初始化
Print(L);
LinkList p_two,p_one;//实现p_two指针一次走两步 p_one指针一次走一步
get_medium(L,L2);//利用get_mediumh函数就可以得到链表的后半部分了，由p_one指针指向
// printf("%d\n",p_one->data);//检查一下是不是真的指向了链表的后半部分
Print(L);
Print(L2);
reversed(L2);
Print(L2);
merge(L,L2);
Print(L);
free(L2);
return 0;
}
运行截图：
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)