Question

C语言链表求并集和差集的问题，请大神帮我指出一下代码出错在哪里。

输入输出都是递增的正整数列，用链表实现求A-B的差集C1和并集C2。
我用C free和VC6调试过了，报错都在unionset函数中最后第四个语句：p2->next，实在不知道为什么错了。在求并集的时候，我的算法类似合并两个有序线性表的算法。用两个在A,B上移动的指针完成的。
部分代码如下：（由于字数限制，只能暂时给出这么main和unionset函数，请大神回答时hi我，我把整个代码传过去）

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(Node)
typedef struct Node_List{
int num;
struct Node_List *next;
}Node;
int main()
{
//declare function:
Node *createList(char);
Node *differentSet(Node*,Node*);
Node *unionSet(Node*,Node*);
void isSortList(Node*);
void printList(Node*,char*);
void freeMemery(Node*);

Node *A=createList('A');
Node *B=createList('B');

//Check if the user input the data in ascending order
isSortList(A);
isSortList(B);
Node *C1=differentSet(A,B);
Node *C2=unionSet(A,B);

printList(C1,"C1");
printList(C2,"C2");

//release allocted space of heaps
freeMemery(A);A=NULL;
freeMemery(B);B=NULL;
freeMemery(C1);C1=NULL;
freeMemery(C2);C2=NULL;

return 0;
}

Node *unionSet(Node *i,Node *j)
{
Node *p1,*p2,*head=NULL;

//if empty lists exist.
if(i==NULL) return j;
if(j==NULL) return i;

if(p1=(Node *)malloc(LEN)) ;
else
{
printf("error!");
exit(0);
}
head=p1;

while(i&&j)
//neither the pointers moves to the end of the list
{
if(i->num < j->num)
{
//put A's element into C2
p1->num = i->num;
p2=p1;
p1=(Node *)malloc(LEN);
p2=p1->next;
i=i->next;
}
else if(j->num < i->num)
{
//put B's elment into C2
p1->num = i->num;
p2=p1;
p1=(Node *)malloc(LEN);
p2=p1->next;
//move to the next element of List B
j=j->next;
}
else if(i->num = j->num)
{
//put A's elment into C2
p1->num = i->num;
p2=p1;
p1=(Node *)malloc(LEN);
p2=p1->next;
//move to the next element of both List A and B
i=i->next;
j=j->next;
}
}

while(i)
//while the pointer pointing at A list hasn't moved to the end
{
p1->num = i->num;
p2=p1;
p1=(Node *)malloc(LEN);
p2=p1->next;
i=i->next;
}

while(j)
//while the pointer pointing at B list hasn't moved to the end
{
p1->num = j->num;
p2=p1;
p1=(Node *)malloc(LEN);
p2=p1->next;
j=j->next;
}
p2->next=NULL;
//release unuse space
free(p1);
p1=NULL;

return head;
}

Answer 1

在进行交集、并集运算前，必须确保两个集合是有序的，且各个集合的元素必须是唯一的。

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(Node)
typedef struct Node_List {
	int num;
	struct Node_List *next;
}Node;

int main() {
	Node *createList(char);
	Node *differentSet(Node*,Node*);
	Node *unionSet(Node*,Node*);
	void isSortList(Node*);
	void printList(Node*,char*);
	void freeMemery(Node*);
	
	Node *A = createList('A');
	Node *B = createList('B');
	
	isSortList(A);
	isSortList(B);
	Node *C1 = differentSet(A,B);
	Node *C2 = unionSet(A,B);
	
	printList(C1,"C1");
	printList(C2,"C2");
	
	freeMemery(A);A = NULL;
	freeMemery(B);B = NULL;
	freeMemery(C1);C1 = NULL;
	freeMemery(C2);C2 = NULL;
	
	return 0; 
}

Node *unionSet(Node *i,Node *j) {
	Node *p1,*p2,*head = NULL;
	
	if(i == NULL) return j;
	if(j == NULL) return i;
	
	if(p1 = (Node *)malloc(LEN)) ;
	else {
		printf("error!");
		exit(0);
	}
	head = p1;
	while(i && j) {
		if(i->num < j->num) {
			p1->num = i->num;
			p2 = p1;
			p1 = (Node *)malloc(LEN);
			p2 = p1->next;
			i=i->next;
		}
		else if(j->num < i->num) {
			p1->num = i->num;
			p2 = p1;
			p1 = (Node *)malloc(LEN);
			p2 = p1->next;
			j = j->next;
		}
		else if(i->num == j->num) { // 是==，不是=
			p1->num = i->num;
			p2 = p1;
			p1 = (Node *)malloc(LEN);
			p2 = p1->next;
			i = i->next;
			j = j->next;
		}
	}
	while(i) {
		p1->num = i->num;
		p2 = p1;
		p1 = (Node *)malloc(LEN);
		p2 = p1->next;
		i = i->next;
	}
	while(j) {
		p1->num = j->num;
		p2 = p1;
		p1 = (Node *)malloc(LEN);
		p2 = p1->next;
		j = j->next;
	}
	p2->next = NULL;
	free(p1);
	p1 = NULL;
	return head;
}

追问

请告诉我在哪一行做了修改呢？？

追答

为了“显眼”，只有一行有注释，你仔细找找。

追问

• 　　还是会报错 ，就在那一行p2->next=NULL;
  

追答

Node *unionSet(Node *i,Node *j) {
Node *p,*head = NULL;
if(i == NULL) {
head = CopySet(j); // 集合复制函数
return head;
}
if(j == NULL) {
head = CopySet(i);
return head;
}

    if(head = p = (Node *)malloc(LEN));
    else {
        printf("error!\n");
        exit(1); // 退出码0用于正常结束程序
    }
    while(i && j) {
p->next = (Node *)malloc(LEN));
        if(i->num < j->num) {
            p->next->num = i->num;
i = i->next;
}
else if(i->num > j->num) {
p->next->num = j->num;
j = j->next;
}
else { // 余下的情况只有i->num == j->num，无需判断
p->next->num = i->num; // 或者p->next->num = j->num;
i = i->next;
j = j->next;
        }
p = p->next;
    }
    while(i) {
p->next = (Node *)malloc(LEN));
p->next->num = i->num;
p = p->next;
i = i->next;
}
while(j) {
p->next = (Node *)malloc(LEN));
p->next->num = j->num;
p = p->next;
        j = j->next;
    }
    p->next = NULL;
p = head;
head = p->next;
    free(p);
    p = NULL;
    return head;
}