Question

一道数据结构的题，请帮忙改错。。在线等

题目：
求2个非降序链表的并集，如1->2->3 和 2->3->5 并为 1->2->3->5，只能输出结果，不能修改两个链表的数据。
【输入形式】第一行为第一个链表的各结点值，以空格分隔。
第二行为第二个链表的各结点值，以空格分隔。
【输出形式】合并好的链表，以非降序排列，值与值之间以空格分隔。
【样例输入】
4 7 10 34
1 4 6 29 34 34 52
【样例输出】
1 4 6 7 10 29 34 52
【评分标准】要使用链表实现，否则不能得分。

我的算法是，先输入第一行的数，建成链表。再把第二行的数逐个插入链表中，相同的则不插入（这个功能在INSERT里实现）
请帮忙用我的算法改一下我的程序的错误~
在改完错的基础上，如果有更好的方法，也写出来。另外加50分。谢谢了

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *link;
}LNode,*LinkList;
LinkList INSERT(LinkList list,int item){
LinkList p,q,r;
q=(LinkList)malloc(sizeof(LNode));
q->data=item;
q->link=NULL;
p=list;
r=NULL;
while(p!=NULL){
if((p->data)==(q->data))
break;
else if((p->data)<(q->data)){
r=p;
p=p->link;
}
else{
if((p->data)==(list->data)){
q->link=p;
list=q;
}
else{
r->link=q;
q->link=p;
}
}
}
if(p==NULL){
r->link=q;
q->link=NULL;
}
return list;
}
int main(){
LinkList p,r,lista;
int a,i;
char c;
lista=NULL;
do{
scanf("%d",&a);
c=getchar();
p=(LinkList)malloc(sizeof(LNode));
p->data=a;
p->link=NULL;
if(lista==NULL)
lista=p;
else
r->link=p;
r=p;
}while(c==' ');
do{
scanf("%d",&a);
c=getchar();
lista=INSERT(lista,a);
}while(c==' ');
p=lista;
while(lista!=NULL){
printf("%d ",lista->data);
p=lista;
lista=lista->link;
free(p);
}
return 0;
}

Answer 1

这是按你的思路改的，没问题了。但我觉得不太合适，因为你没有建立两个链表，
#include<stdio.h>
#include<stdlib.h>
typedef struct node{

int data;

struct node *link;

}LNode,*LinkList;

LinkList INSERT(LinkList list,int item)
{

LinkList p,q,r;

q=(LinkList)malloc(sizeof(LNode));

q->data=item;

q->link=NULL;

p=list;

r=NULL;

while(p!=NULL)
{

if((p->data)==(q->data))

break;

else if((p->data)<(q->data))
{

r=p;

p=p->link;

}

else
{
if(r==NULL)
{
q->link=list;
list=q;
}
else
{
r->link=q;

q->link=p;
}

break;

}

}

if(p==NULL)
{

r->link=q;

q->link=NULL;

}

return list;

}

int main()
{

LinkList p,r,lista;

int a,i;

char c;

lista=NULL;

do
{

scanf("%d",&a);

c=getchar();

p=(LinkList)malloc(sizeof(LNode));

p->data=a;

p->link=NULL;

if(lista==NULL)

lista=p;

else

r->link=p;

r=p;

}
while(c==' ');

do
{

scanf("%d",&a);

c=getchar();

lista=INSERT(lista,a);

}
while(c==' ');

p=lista;

while(p!=NULL)
{

printf("%d ",p->data);

p=p->link;

}

return 0;

}

Answer 2

//用新链表存储，完全符合题意
#include <stdio.h>
#include <malloc.h>
typedef struct _node
{
int data;
struct _node *next;
}node;
node *creatlist();
void add_to_list(node *head,int number);
node *sort(node *first,node *second);
void print(node *head);
void destory(node *head);
int main()
{
int i=0;
int number1[]={4,7,10,34,52,59};
int number2[]={1,4,6,29,34,34,52};
node *m_first_list=creatlist();
node *m_second_list=creatlist();
for (i=0;i<6;i++)
add_to_list(m_first_list,number1[i]);
for(i=0;i<7;i++)
add_to_list(m_second_list,number2[i]);
node *out_list=sort(m_first_list,m_second_list);
print(out_list);
destory(m_first_list);
destory(m_second_list);
destory(out_list);
return 0;
}
node * creatlist()
{
node *head=(node *)malloc(sizeof(node));
head->next=NULL;
return head;
}
void add_to_list( node *head,int number )
{
node *p=head;
node *tmp=(node *)malloc(sizeof(node));
tmp->data=number;
tmp->next=NULL;
while(p->next!=NULL)
p=p->next;
p->next=tmp;
}
node *sort( node *first,node *second )
{
node *p=first->next;
node *q=second->next;
node *head=creatlist();
while(p!=NULL&&q!=NULL)
{
if(p->data>q->data)
{
add_to_list(head,q->data);
q=q->next;
}
else if(p->data<q->data)
{
add_to_list(head,p->data);
p=p->next;
}
else
{
if(q->next==NULL)
p=p->next;
else
q=q->next;
}
}
if(p==NULL)
while(q!=NULL)
{
add_to_list(head,q->data);
q=q->next;
}
else
{
while(p!=NULL)
{
add_to_list(head,p->data);
p=p->next;
}
}
return head;
}
void print( node *head )
{
head=head->next;
while(head->next!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
printf("%d\n",head->data);
}
void destory( node *head )
{
node *p=head;
while(head->next!=NULL)
{
head=head->next;
free(p);
p=head;
}
free(head);
}

Answer 3

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct LNode
{
int data;
struct LNode *next;
}LNode;
void CreatList_L(LNode *&L, int n)
//建立带头结点的单链线性表L
{
LNode *p1, *p2;
int i;
L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
p2 = L;
for (i=0; i<n; ++i)
{
p1 = (LNode *)malloc(sizeof(LNode));
printf("第%d个：",i + 1);
scanf("%d",&p1->data);
p1->next = p2->next;
p2->next = p1;
p2 = p1;
}
}//CreatList_L
void PrintList_L(LNode *&L)
//输出链式线性表的值
{
LNode *p = NULL;
p = L->next;
while (p != NULL)
{
printf("%3d",p->data);
p = p->next;
}
printf("\n");
}//PrintList_L
void MergList_L(LNode *&La, LNode *&Lb,LNode *&Lc)
{
LNode *pa = NULL;
LNode *pb = NULL;
LNode *p1 = NULL;
LNode *p2 = NULL;
char c = 0;
pa = La->next;
pb = Lb->next;
Lc = (LNode *)malloc(sizeof(LNode));//建立新链表,存储归并后的链表
Lc->next = NULL;
p2 = Lc;
while (pa && pb)
{
if (pa->data >= pb->data)
{
p1 = (LNode *)malloc(sizeof(LNode));
p1->data = pa->data;
p1->next = p2->next;
p2->next = p1;
p2 = p1;
pa = pa->next;
}
else
{
p1 = (LNode *)malloc(sizeof(LNode));
p1->data = pb->data;
p1->next = p2->next;
p2->next = p1;
p2 = p1;
pb = pb->next;
}
}
while (pa)//插入剩余段
{
p1 = (LNode *)malloc(sizeof(LNode));
p1->data = pa->data;
p1->next = p2->next;
p2->next = p1;
p2 = p1;
pa = pa->next;
}
while (pb)//插入剩余短
{
p1 = (LNode *)malloc(sizeof(LNode));
p1->data = pb->data;
p1->next = p2->next;
p2->next = p1;
p2 = p1;
pb = pb->next;
}
}//MergList_L
void main(void)
{
LNode *La = NULL;
LNode *Lb = NULL;
LNode *Lc = NULL;
int L_length = 0;
printf("输入线性表的长度：");
scanf("%d",&L_length);
CreatList_L(La,L_length);
PrintList_L(La);
printf("输入线性表的长度：");
scanf("%d",&L_length);
CreatList_L(Lb,L_length);
PrintList_L(Lb);
MergList_L(La, Lb, Lc);
PrintList_L(Lc);
}
这个好像不很符合你的要求。。。。。

Answer 4

希望你以后写程序加点注释。。我在帮你看