学步园

有两个双向链表，头指针为：pListA和pListB，要求删除这两个链表中值相同的结点, C语言实现，结点结构如下：

struct node								// 双向链表结点
{
	int key;
	struct node *front, *next;
};

完整源代码如下：

/*
	功能：删除两个双向链表(都不带头结点)中值(key)相同的结点
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node								// 双向链表结点
{
	int key;
	struct node *front, *next;
};

/*
	功能：	创建双向链表
	返回值：1-创建成功，0-创建失败
	header:	创建的双向链表的头指针
	n:		待创建的结点个数
*/
int createLinklist(struct node **header, int n)
{
	int v;
	struct node *pre, *p;

	*header = pre = p = NULL;
	printf("请输入%d个整数：\n", n);
	while(n-- > 0)
	{
		scanf("%d", &v);
		p = malloc(sizeof(struct node));
		if(p)
		{
			if(*header == NULL)
				*header = p;			// 设置链表头指针
			else
			{
				pre->next = p;			
				p->front = pre;
			}
			p->key = v;
			p->next = *header;			// 新结点的next指向头结点
			(*header)->front = p;		// 更改头结点的front成员
			pre = p;
		}
		else
			return 0;					// 创建链表失败
	}

	return 1;							// 创建链表成功
}

// 输出双向链表中的值
void displayLinklist(struct node *header)
{
	struct node *p = header;
	if(NULL != p)
	{
		do
		{
			printf("[p = %X]\tdata = %d, front = %X, next = %X\n", p, p->key, p->front, p->next);
			p = p->next;
		}while(p != header);
		printf("\n");
	}	
}

// 删除双向链表中所有结点并释放空间(头删法)
void FreeLinklist(struct node *header)
{
	struct node *p;
	int i = 0;
	while(header)
	{
		p = header;
		if(header->next == header)		// 待删除的是最后一个结点
			header = NULL;
		else
		{
			header->front->next = header->next;
			header->next->front = header->front;
			header = header->next;
		}
		free(p);
	}
}

/*
	功能：		删除双向链表(头指针*pHeader)中值与key相同的结点，从结点*pStart开始向后搜索

	返回值：	如果从双向链表中删除了值为指定key的结点，返回1，否则返回0
	pHeader:	双向链表头指针
	pStart:		从*pStart开始向后搜索，删除值与key相同的结点，直到遇到*pHeader
	key:		待删除结点的值

	注意：		调用此函数时，输入参数*pHeader==*pStart，程序将会出错
*/
int removeNode(struct node **pHeader, struct node **pStart, int key)
{
	struct node *p, *temp;
	int del = 0;
	
	p = *pStart;
	*pStart = NULL;
	while(p)
	{
		if(p->key == key)
		{
			del = 1;
			temp = p;							// temp指向待删除的结点
			if(*pHeader == temp)				// 删除头结点
			{
				if(*pHeader == temp->next)		// 该头结点是链表的最后一个结点
					*pHeader = NULL;
				else
				{	
					*pHeader = temp->next;
					p->front->next = *pHeader;	// 最后一个结点的next指向新的头结点
					p->next->front = p->front;	// 被删结点的后继结点的front指向被删结点的前驱
				}
				p = *pHeader;					// p指向新的头结点
			}
			else
			{
				p->front->next = p->next;
				p->next->front = p->front;
				p = p->next;					// p指向被删除结点的后继结点
			}
			free(temp);
		}
		else
		{
			 if(*pStart == NULL)
				 *pStart = p;
			 p = p->next;
		}
		if(*pStart && p == *pHeader)
			break;
	}
	return del;
}

// 删除两个链表中值相同的结点
void removeEqualNodes(struct node **pHeadA, struct node **pHeadB)
{
	struct node *p1, *p2;
	int del = 0;

	p1 = *pHeadA;
	while(p1)
	{
		p2 = *pHeadB;
		if((del = removeNode(pHeadB, &p2, p1->key)) == 1)
		{
			removeNode(pHeadA, &p1, p1->key);
		}
		else
			p1 = p1->next;

		if(*pHeadB == NULL || *pHeadA == NULL || (del == 0 && p1 == *pHeadA))
			break;
	}
}

int main(int argc, char *argv[])
{
	struct node *plistA = NULL, *plistB = NULL;
	int n1, n2;

	if(argc < 3)
	{
		printf("Usage: %s <n1> <n2>\n", argv[0]);
		return 1;
	}
	n1 = atoi(argv[1]);
	n2 = atoi(argv[2]);
	createLinklist(&plistA, n1);			// 创建双向链表
	createLinklist(&plistB, n2);

	printf("Before remove:\n");
	displayLinklist(plistA);				// 显示双向链表内容
	displayLinklist(plistB);

	removeEqualNodes(&plistA, &plistB);		// 删除两个链表中值相同的结点
	printf("\nAfter remove:\n");
	displayLinklist(plistA);
	displayLinklist(plistB);

	FreeLinklist(plistA);					// 释放空间
	FreeLinklist(plistB);

	return 0;
}