来自数据结构 ( c语言版 ) 的一个实验题
题目大意:已知两个带头结点的单链表L1和L2(结点值按升序排序),现在要将这两个表合并成一个表,先升序合并、输出,再降序合并,输出。
思路:因为我写的函数破坏了原来表的结构(lll¬ω¬),所以我直接在升序排序前复制了h1和h2的值(主要是没写出来不破坏结构的qwq!!!)
代码:
#include
#include
typedef struct link_node{
int info;
struct link_node *next;
}node;
typedef node *linklist;
linklist init()
{
node *head;
head=(node*)malloc(sizeof(node));
head->next=NULL;
return head;
}
linklist creatbyqueue()
{
linklist head=init(),r,s;
int x;
head->next=r=NULL;
printf("请输入若干整数序列:\n");
scanf("%d",&x);
while(x){
s=(linklist)malloc(sizeof(node));
s->info=x;
if(head->next==NULL) head->next=s;
else r->next=s;
r=s;
scanf("%d",&x);
}
if(r) r->next=NULL;
return head;
}
linklist copy(linklist L)
{
linklist head=init(),r,s,pl=L->next;
head->next=r=NULL;
while(pl&&pl->info){
s=(linklist)malloc(sizeof(node));
s->info=pl->info;
if(head->next==NULL) head->next=s;
else r->next=s;
r=s;
pl=pl->next;
}
if(r) r->next=NULL;
return head;
}
void delList(linklist head)
{
linklist p=head->next;
while(p){
head=p->next;
free(p);
p=head;
}
return ;
}
void print(linklist head)
{
linklist p;
int i=0;
p=head->next;
printf("List is:\n");
while(p){
printf("%-5d",p->info);
p=p->next;
i++;
if(i%10==0) printf("\n");
}
printf("\n");
return ;
}
linklist mergeAscend(linklist L1,linklist L2)
{
linklist L3,r,p,q;
L3=r=(linklist)malloc(sizeof(node));
p=L1->next;
q=L2->next;
while(p&&q){
if(p->infoinfo){
L1->next=p->next;
r->next=p;
r=p;
p=L1->next;
}
else{
L2->next=q->next;
r->next=q;
r=q;
q=L2->next;
}
}
while(p){
L1->next=p->next;
r->next=p;
r=p;
p=L1->next;
}
while(q){
L2->next=q->next;
r->next=q;
r=q;
q=L2->next;
}
r->next=NULL;
free(L1);
free(L2);
return L3;
}
linklist mergeDescend(linklist L1,linklist L2)
{
linklist L3,r,q,p;
L3=r=(linklist)malloc(sizeof(node));
L3->next=NULL;
p=L1->next;
q=L2->next;
while(p&&q){
if(p->infoinfo){
L1->next=p->next;
p->next=r->next;
r->next=p;
p=L1->next;
}
else{
L2->next=q->next;
q->next=r->next;
r->next=q;
q=L2->next;
}
}
while(p){
L1->next=p->next;
p->next=r->next;
r->next=p;
p=L1->next;
}
while(q){
L2->next=q->next;
q->next=r->next;
r->next=q;
q=L2->next;
}
free(L1);
free(L2);
return L3;
}
int main()
{
linklist h1,h2,h3,h4,h5;
h1=creatbyqueue();
h2=creatbyqueue();
h4=copy(h1);
h5=copy(h2);
print(h1);
print(h2);
h3=mergeAscend(h1,h2);
print(h3);
h3=mergeDescend(h4,h5);
print(h3);
delList(h3);
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)