已知两个非降序链表序列S1与S2,设计函数构造出S1与S2的交集新链表S3。
输入格式:
输入分两行,分别在每行给出由若干个正整数构成的非降序序列,用−1表示序列的结尾(−1不属于这个序列)。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的交集序列,数字间用空格分开,结尾不能有多余空格;若新链表为空,输出NULL。
我的代码
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int Data;
struct Node *Next;
}node,*List;
List read();
int main(){
List L1,L2,L3,h;
L1=read();
L2=read();
L3=h=(List)malloc(sizeof(struct Node));
while(L1!=NULL){
L3->Next=(List)malloc(sizeof(struct Node));
while(L2!=NULL){
if(L1->Data==L2->Data){
L3->Next->Data=L1->Data;
L3=L3->Next;
}
L2=L2->Next;
}
L1=L1->Next;
}
L3->Next=NULL;
L3=h->Next;
free(h);
if(L3==NULL){
printf("NULL");
}else{
while(L3!=NULL){
printf("%d",L3->Data);
L3=L3->Next;
}
}
return 0;
}
List read(){
List L,h;
int n;
L=h=(List)malloc(sizeof(struct Node));
scanf("%d",&n);
while(n!=-1){
L->Next=(List)malloc(sizeof(struct Node));
L->Next->Data=n;
L=L->Next;
scanf("%d",&n);
}
L->Next=NULL;
L=h->Next;
free(h);
h=L;
return h;
不是很能理解错哪儿了,有人可以具体解惑一下吗?要怎么改呢?希望可以讲的简单易懂一点,先谢谢了(^~^)
我觉得还是逻辑问题吧,没把链表的头结点和第一个数据节点分离开来,感觉在读取输入的时候也有问题。改了下:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int Data;
struct Node *Next;
}node, *List;
List read(); // 读取链表
List intersection(List L1, List L2); // 求两个链表的交集
void printList(List L); // 打印链表
int main(){
List L1, L2, L3;
L1 = read();
L2 = read();
L3 = intersection(L1, L2);
printList(L3);
return 0;
}
List read(){
List L, h, p;
int n;
h = (List)malloc(sizeof(node));
p = h;
scanf("%d", &n);
while(n != -1){
L = (List)malloc(sizeof(node));
L->Data = n;
p->Next = L;
p = L;
scanf("%d", &n);
}
p->Next = NULL;
L = h->Next;
free(h);
return L;
}
List intersection(List L1, List L2){
List h, p, q;
h = (List)malloc(sizeof(node));
p = h;
while(L1 != NULL && L2 != NULL){
if(L1->Data < L2->Data){
L1 = L1->Next;
}else if(L1->Data > L2->Data){
L2 = L2->Next;
}else{
q = (List)malloc(sizeof(node));
q->Data = L1->Data;
p->Next = q;
p = q;
L1 = L1->Next;
L2 = L2->Next;
}
}
p->Next = NULL;
List L3 = h->Next;
free(h);
return L3;
}
void printList(List L){
if(L == NULL){
printf("NULL");
}else{
while(L != NULL){
printf("%d ", L->Data);
L = L->Next;
}
}
}