`
阿尔萨斯
  • 浏览: 4110239 次
社区版块
存档分类
最新评论

数据结构 - 从一个链表中删除在另一个链表中的元素(C++)

 
阅读更多

/*
Sort both list from small to big. And then use the following code.
*/

#include <iostream>

using namespace std;

struct Node
{
	char data;
	Node* next;
};

Node* create()
{
	Node* head = NULL;
	Node* rear = head;
	Node* p; // The pointer points to new created node.
	char tmp;

	do
	{
		cout << "Please input integer or char '#':";
		cin >> tmp;
		if(tmp != '#')
		{
			p = new Node;
			p->data = tmp;
			p->next = NULL;

			if(head == NULL)
			{
				head = p;
			}
			else
			{
				rear->next = p;
			}

			rear = p;
		}
	}
	while(tmp != '#');

	return head;
}

void print(Node* head)
{
	Node* p = head;

	if(head != NULL)
	{
		do
		{
			cout << p->data << ' ';
			p = p->next;
		}
		while(p != NULL);
	}

	cout << endl;
}

Node* del(Node* l1, Node* l2)
{
	if(!l1 || !l2)
	{
		return NULL;
	}

	Node *p = new Node;
	p->next = l1;
	Node *pL1 = l1, *pL2 = l2, *head = p;

	while(pL1 && pL2)
	{
		if(pL1->data < pL2->data)
		{
			pL1 = pL1->next;
			p = p->next;
		}
		else if(pL1->data > pL2->data)
		{
			pL2 = pL2->next;
		}
		else
		{
			pL1 = pL1->next;
			p->next = pL1;
		}
	}

	l1 = head->next;

	return l1;
}

int main()
{
	cout << "Please input the first list:" << endl;
	Node* l1 = create();

	cout << endl << "Please input the second list:" << endl;
	Node* l2 = create();

	cout << endl << "--------------------------" << endl;
	cout << "The first list is: ";
	print(l1);
	cout << "The second list is: ";
	print(l2);

	Node* l = del(l1, l2);
	cout << endl << "The result list is: ";
	print(l);

	return 0;
}

// Output:
/*
Please input the first list:
Please input integer or char '#':1
Please input integer or char '#':1
Please input integer or char '#':1
Please input integer or char '#':1
Please input integer or char '#':3
Please input integer or char '#':3
Please input integer or char '#':3
Please input integer or char '#':3
Please input integer or char '#':4
Please input integer or char '#':5
Please input integer or char '#':6
Please input integer or char '#':6
Please input integer or char '#':6
Please input integer or char '#':7
Please input integer or char '#':7
Please input integer or char '#':8
Please input integer or char '#':8
Please input integer or char '#':8
Please input integer or char '#':9
Please input integer or char '#':9
Please input integer or char '#':9
Please input integer or char '#':9
Please input integer or char '#':#

Please input the second list:
Please input integer or char '#':1
Please input integer or char '#':2
Please input integer or char '#':5
Please input integer or char '#':5
Please input integer or char '#':5
Please input integer or char '#':7
Please input integer or char '#':7
Please input integer or char '#':7
Please input integer or char '#':7
Please input integer or char '#':7
Please input integer or char '#':9
Please input integer or char '#':#

--------------------------
The first list is: 1 1 1 1 3 3 3 3 4 5 6 6 6 7 7 8 8 8 9 9 9 9
The second list is: 1 2 5 5 5 7 7 7 7 7 9

The result list is: 3 3 3 3 4 6 6 6 8 8 8
*/
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics