首页 > 试题广场 >

已知集合A和B的元素分别用不含头结点的单链表存储，函数dif

[填空题]

已知集合A和B的元素分别用不含头结点的单链表存储，函数difference( )用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。

链表结点的结构类型定义如下：

struct node
{
int elem;
node* next;
};

void difference(node** LA , node* LB)
{
node *pa , *pb , *pre , *q;
pre = NULL;
1//1
while(pa) {
pb = LB;
while2                 //2
pb = pb->next;
if3                   //3
{
if(!pre)
      *LA = 4 ; //4
else
5 = pa->next; //5
q = pa;
pa = pa->next;
free(q);
}
else {
6 ; //6
pa = pa->next;
}
}
}

查看答案及解析

newcomer

#include<stdio.h>

struct node{
	int elem;
	struct node* next;
};

/*
	本题的解法思路较简单：
	因为要求集合A和集合B的差集(A-B)，结果保存在集合A中.
	所以我们取出集合A中每一个元素，然后在集合B中寻找(代码22行所实现) 找到即删除此节点 否则保留 
	此时while循环跳出只有两种情况，pb为NULL或者 pa->elem==pb->elem
	当pb不为null时，即找出集合A和集合B的公有元素，此时要删除这个元素 
		pre(实现删除节点之后的链接) 
		当pre为NULL时，说明是首次找到A和B的公有元素，此时 *LA指向pa->next 所以*LA仍然是头结点
		当pre不为NULL时， pre指向pa->next，顺利实现删除节点的链接 
*/


void difference(node** LA,node* LB){
	node*pa,*pb,*pre,*q;
	pre=NULL;
	pa=*LA;/*LA是指向指针的指针,pa指向集合的元素*/
	while(pa){
		pb=LB;/*pb指向集合B的元素*/
		while(pb && pa->elem!=pb->elem) /*在链表LB中寻找与pa所指元素相等的节点*/
			pb=pb->next;
		if(pb){ /*pa所指元素与pb所指元素相等*/
			if(!pre){
				*LA=pa->next;
			}else{
				pre->next=pa->next;
			}
			q=pa;/*求差集 所以要删除pa节点*/
			pa=pa->next;
			free(q);
		}else{
			pre=pa;
			pa=pa->next;
		}
	}
}

编辑于 2016-05-28 14:56:20 回复(7)

二咩

这也算错。。

发表于 2015-11-08 00:31:15 回复(6)

book生活

typedef struct node
{
   int elem;
   struct node*next;

}*Lnode;

void Different_Set(Lnode &La,Lnode Lb)//需要在La上进行更改，所以使用引用
{
   Lnode pLa,pLb,pre,tmp;
   pre=NULL;
   pLa=La;
   while(pLa)//当La链表没到头的时候
   {
       pLb=Lb;
       while(pLb && pLa->elem != pLb->elem)//LB中没有和LA中相等的元素就继续寻找
       {
           pLb=pLb->next;
       }
       if(pLb)
       {
           if(!pre)//如果LB中和LA中的第一个元素相等了
           {
               La=pLa->next;//换掉LA中第一个节点
           }
           else//否则删除当前LA中与LB中相等的元素节点
           {
               pre->next=pLa->next;
           }
           tmp=pLa;
           pLa=pLa->next;
           delete tmp;
       }
       else
       {
           pre=pLa;
           pLa=pLa->next;
       }
   }

}

发表于 2015-11-15 14:51:34 回复(0)

Hunger

pre指向当前非公有元素。当查找到A和B的公有元素时，若pre为空，说明前面的元素都是公有元素，需要修改*LA的表头；若pre不为空，则pre->next=pa->next跳过pa指向的当前公有元素，实现删除。

发表于 2016-12-23 11:09:23 回复(0)

是萌萌的前辈呀

LA为二维指针，pa为一维指针，将pa指向链表A时，需要LA执行一次解引用操作，即pa=*LA;
A在外层循环，B内层循环。每次取出A中一个值x后，在B中从头到尾找值为x的节点,即执行如下代码
```
while(pb && pa->elem != pb->elem)
     pb=pb->next;
```
其中pre始终指向pa的上一个节点。
2.1找到x
（1）若pre==NULL
则说明此时在B中找到了A链表的首节点相同的元素，应该将此节点删除。所以执行*LA=pa->next,后面的
```
      q = pa;
      pa = pa->next;
      free(q);
```
是将此时A中pa指向的节点删除，pa移到下一个元素，而*LA保持为A链表首节点；
（2）若pre非NULL
因为pa节点要删除，所以pre的下一个节点应该指向pa->next,即执行
```
      pre->next=pa->next;
```
总地来说，就是保证pre是要操作的节点pa的上一个节点；
2.2未找到x，也就是pb为NULL
此时pa节点不会删除，pa会往后移，而在它后移之前，我们需要保证pre是移到后pa的上一个节点，所以执行
```
      pre=pa;
      pa=pa->next;
```