现在的位置: 首页 > 综合 > 正文

删除两个双向链表中值相同的结点–带空白头结点

2019年08月10日 ⁄ 综合 ⁄ 共 7095字 ⁄ 字号 小 中 大 ⁄ 评论关闭

有两个双向链表，空白头结点为：ListA和ListB，要求删除这两个链表中关键字相同的结点, C语言实现，结点结构如下：

view
plain
  1. struct node                             // 双向链表结点  
  2. {  
  3.     int key;  
  4.     struct node *front, *next;  
  5. };
     

 完整代码：

/*
	功能：删除两个双向链表(都带空白头结点)中值(key)相同的结点，规定header.front始终指向尾结点

	名词定义：
		空白头结点：该结点不作为真正保存值的结点；其front成员规定指向尾结点, next指向第一个非空白结点；当该链表无结点时，规定其front和next都为NULL.
		头结点：	链表的第一个非空白头结点(第一个元素)
		尾结点：	链表的最后一个非空白结点
*/

#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 *p = NULL;

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

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

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

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

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

	返回值：	如果从双向链表中删除了值为指定key的结点，返回1，否则返回0
	pHeader:	双向链表空白头指针
	pStart:		从*pStart开始向后搜索，删除值与key相同的结点，直到遇到pHeader->next
	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->next == p)						// 删除头结点
			{
				if(pHeader->front == pHeader->next)		// 待删结点是链表的唯一结点
					pHeader->front = pHeader->next = NULL;
				else
				{	
					pHeader->front->next = p->next;
					p->next->front = pHeader->front;	// 尾结点的next指向新的头结点
					pHeader->next = p->next;
				}
				p = pHeader->next;						// p指向新的头结点
			}
			else
			{
				p->front->next = p->next;
				p->next->front = p->front;
				if(p == pHeader->front)					// 待删除的是尾结点
					pHeader->front = p->front;			// pHeader->front指向新的尾结点
				p = p->next;							// p指向被删除结点的后继结点
			}
			free(temp);
		}
		else
		{
			 if(*pStart == NULL)
				 *pStart = p;
			 p = p->next;
		}
		if(*pStart && p == pHeader->next)
			break;
	}
	return del;
}

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

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

		if(pHeadB->next == NULL || pHeadA->next == NULL || (del == 0 && p1 == pHeadA->next))
			break;
	}
}

int main(int argc, char *argv[])
{
	struct node listA, listB;				// 定义两个双向链表的空白头结点
	int n1, n2;								// 保存待创建的链表结点个数

	if(argc < 3)
	{
		printf("Usage: %s <n1> <n2>\n", argv[0]);
		return 1;
	}

	n1 = atoi(argv[1]);
	n2 = atoi(argv[2]);
	listA.front = listA.next = NULL;
	listB.front = listB.next = NULL;

	createLinklist(&listA, n1);				// 创建双向链表
	createLinklist(&listB, n2);

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

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

	FreeLinklist(&listA);					// 释放空间
	FreeLinklist(&listB);

	return 0;
}

运行结果：

E:\Program\VC\del\Debug>del.exe 2 4
请输入2个整数：
14 25
请输入4个整数：
14 25
63 66
Before remove:
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 14, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807A8, next = 0x3807A8

header.front = 0x3808C0, header.next = 0x380818
[p = 0x380818]  data = 14, front = 0x3808C0, next = 0x380850
[p = 0x380850]  data = 25, front = 0x380818, next = 0x380888
[p = 0x380888]  data = 63, front = 0x380850, next = 0x3808C0
[p = 0x3808C0]  data = 66, front = 0x380888, next = 0x380818


After remove:
header.front = 0x0, header.next = 0x0
header.front = 0x3808C0, header.next = 0x380888
[p = 0x380888]  data = 63, front = 0x3808C0, next = 0x3808C0
[p = 0x3808C0]  data = 66, front = 0x380888, next = 0x380888


E:\Program\VC\del\Debug>del.exe 2 4
请输入2个整数：
14 25
请输入4个整数：
12 23 21 54
Before remove:
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 14, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807A8, next = 0x3807A8

header.front = 0x3808C0, header.next = 0x380818
[p = 0x380818]  data = 12, front = 0x3808C0, next = 0x380850
[p = 0x380850]  data = 23, front = 0x380818, next = 0x380888
[p = 0x380888]  data = 21, front = 0x380850, next = 0x3808C0
[p = 0x3808C0]  data = 54, front = 0x380888, next = 0x380818


After remove:
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 14, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807A8, next = 0x3807A8

header.front = 0x3808C0, header.next = 0x380818
[p = 0x380818]  data = 12, front = 0x3808C0, next = 0x380850
[p = 0x380850]  data = 23, front = 0x380818, next = 0x380888
[p = 0x380888]  data = 21, front = 0x380850, next = 0x3808C0
[p = 0x3808C0]  data = 54, front = 0x380888, next = 0x380818


E:\Program\VC\del\Debug>del.exe 0 0
请输入0个整数：
请输入0个整数：
Before remove:
header.front = 0x0, header.next = 0x0
header.front = 0x0, header.next = 0x0

After remove:
header.front = 0x0, header.next = 0x0
header.front = 0x0, header.next = 0x0

E:\Program\VC\del\Debug>del.exe 0 2
请输入0个整数：
请输入2个整数：
12 54
Before remove:
header.front = 0x0, header.next = 0x0
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 12, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 54, front = 0x3807A8, next = 0x3807A8


After remove:
header.front = 0x0, header.next = 0x0
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 12, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 54, front = 0x3807A8, next = 0x3807A8


E:\Program\VC\del\Debug>del.exe 2 0
请输入2个整数：
14 25
请输入0个整数：
Before remove:
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 14, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807A8, next = 0x3807A8

header.front = 0x0, header.next = 0x0

After remove:
header.front = 0x3807E0, header.next = 0x3807A8
[p = 0x3807A8]  data = 14, front = 0x3807E0, next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807A8, next = 0x3807A8

header.front = 0x0, header.next = 0x0

E:\Program\VC\del\Debug>del.exe 1 1
请输入1个整数：
25 25
请输入1个整数：
Before remove:
header.front = 0x3807A8, header.next = 0x3807A8
[p = 0x3807A8]  data = 25, front = 0x3807A8, next = 0x3807A8

header.front = 0x3807E0, header.next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807E0, next = 0x3807E0


After remove:
header.front = 0x0, header.next = 0x0
header.front = 0x0, header.next = 0x0

E:\Program\VC\del\Debug>del.exe 5 6
请输入5个整数：
14 25 63 47 58 14
请输入6个整数：
25 36 47 55 25
Before remove:
header.front = 0x380888, header.next = 0x3807A8
[p = 0x3807A8]  data = 14, front = 0x380888, next = 0x3807E0
[p = 0x3807E0]  data = 25, front = 0x3807A8, next = 0x380818
[p = 0x380818]  data = 63, front = 0x3807E0, next = 0x380850
[p = 0x380850]  data = 47, front = 0x380818, next = 0x380888
[p = 0x380888]  data = 58, front = 0x380850, next = 0x3807A8

header.front = 0x3809D8, header.next = 0x3808C0
[p = 0x3808C0]  data = 14, front = 0x3809D8, next = 0x3808F8
[p = 0x3808F8]  data = 25, front = 0x3808C0, next = 0x380930
[p = 0x380930]  data = 36, front = 0x3808F8, next = 0x380968
[p = 0x380968]  data = 47, front = 0x380930, next = 0x3809A0
[p = 0x3809A0]  data = 55, front = 0x380968, next = 0x3809D8
[p = 0x3809D8]  data = 25, front = 0x3809A0, next = 0x3808C0


After remove:
header.front = 0x380888, header.next = 0x380818
[p = 0x380818]  data = 63, front = 0x380888, next = 0x380888
[p = 0x380888]  data = 58, front = 0x380818, next = 0x380818

header.front = 0x3809A0, header.next = 0x380930
[p = 0x380930]  data = 36, front = 0x3809A0, next = 0x3809A0
[p = 0x3809A0]  data = 55, front = 0x380930, next = 0x380930


E:\Program\VC\del\Debug>
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞