pex9_4.cpp

数据结构C++代码,经典代码,受益多多,希望大家多多支持

#include <iostream.h>
#pragma hdrstop

#include "nodelib.h"
#include "random.h"

// add linked list p to the end of the list whose last
// node is pointed to by rear
template <class T>
void Append(Node<T> * & rear, Node<T> *p)
{
	// use q to traverse rear of modified list
	Node<T> *q = rear, *newNode;
	
	// return if list p is empty
	if (p == NULL)
		return;

	// if the destination is empty, build the first node by
	// copying the first node of p. this is the new value of
	// rear. move p to the 2nd node.
	if (rear == NULL)
	{
		rear = new Node<T>(p->data);
		// use q to build the new list and p to traverse
		// the remainder of the existing one
		q = rear;
		p = p->NextNode();
	}
	
	// traverse list p and append each new node to the
	// end of the list with rear node q
	while(p != NULL)
	{
		// create new node with same data value as p
		newNode = new Node<T>(p->data);
		// insert new node after current end of new list
		q->InsertAfter(newNode);
		// move the two pointers forward
		q = newNode;
		p = p->NextNode();
	}
}

// merge lists L and M pairwise and return a pointer to
// the merged list
template <class T>
Node<T> *MergeList(Node<T> *L, Node<T>* M)
{
	// pL traverses L, pM traverses M and the head of
	// the merged list is newList. pnew follows the
	// rear of the new list
	Node<T>  *pL = L, *pM = M, *newList = NULL, *pnew;
	Node<T> *newNode;
	
	// merge pairwise as long as an element remains in
	// both lists
	while (pL != NULL && pM != NULL)
	{
		// if newList is NULL, we are adding the first
		// node to the merged list
		if (newList == NULL)
		{
			InsertFront(newList,pL->data);
			pnew = newList;
		}
		else
		{
			// append an element of L to the new list and
			// move pnew to the new rear
			newNode = new Node<T>(pL->data);
			pnew->InsertAfter(newNode);
			pnew = newNode;
		}
		// append an element of M to the new list and
		// move pnew to the new rear
		newNode = new Node<T>(pM->data);
		pnew->InsertAfter(newNode);
		pnew = newNode;
		
		// move the L and M pointers forward
		pL = pL->NextNode();
		pM = pM->NextNode();
	}
	
	// if elements remain in L, append the tail of L
	// to the new list
	if (pL != NULL)
		// newList == NULL, pL != NULL means M is empty
		// copy L to the new list
		if (newList == NULL)
			Append(newList,pL);
		else
			// append the tail of L to the new list
			Append(pnew,pL);
	else	
	if (pM != NULL)
		// newList == NULL, pM != NULL means L is empty
		// copy M to the new list
		if (newList == NULL)
			Append(newList,pM);
		else
			// append the tail of M to the new list
			Append(pnew,pM);
	 
	// return the address of the first node in the new list
	return newList;
}		

void main(void)
{
	int i, j, k;
	RandomNumber rnd;
	// build lists L, M and merge them into N
	Node<int> *L = NULL, *M = NULL, *N;

	// 1 <= i <= 10
	i = 1 + rnd.Random(10);
	// 1 <= j <= 20
	j = 1 + rnd.Random(20);
	
	// build an i element list of random numbers
	// in the range 0 to 99
	for (k = 0; k < i; k++)
		InsertFront(L,int(rnd.Random(100)));
			
	// build a j element list of random numbers
	// in the range 100 to 199
	for (k = 0; k < j; k++)
		InsertFront(M,int(rnd.Random(100) + 100));
			
	// print lists L and M
	cout << "L:" << endl;
	PrintList(L);
	cout << endl << endl;
	cout << "M:" << endl;
	PrintList(M);
	cout << endl << endl;
	
	// merge L and M and assign the head of the
	// new list to N. print the merged list
	N = MergeList(L,M);
	cout << "Merged list N:" << endl;
	PrintList(N);
	cout << endl;
}

/*
<Run>

L:
74  53  78

M:
155  191  175  173  100

Merged list N:
74  155  53  191  78  175  173  100
*/