pex9_5.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "link.h"
#include "random.h"


// merge lists L and M pairwise. return the new list
template <class T>
LinkedList<T> MergeList(LinkedList<T> L, LinkedList<T> M)
{
	LinkedList<T>  newList;
	
	L.Reset();
	M.Reset();
		
	// merge pairwise until we arrive at the end of L or M 
	while (!L.EndOfList() && !M.EndOfList())
	{
		newList.InsertRear(L.Data());
		L.Next();
		
		newList.InsertRear(M.Data());
		M.Next();
	}
	
	// if either list still has elements, add its tail
	while (!L.EndOfList())
	{
		newList.InsertRear(L.Data());
		L.Next();
	}	

	while (!M.EndOfList())
	{
		newList.InsertRear(M.Data());
		M.Next();
	}	
	 
	return newList;
}

// print list L
template <class T>
void PrintList(LinkedList<T> &L)
{
	L.Reset();
	for (int i = 0; i < L.ListSize(); i++)
	{
		cout << L.Data() << "  ";
		L.Next();
	}
	cout << endl;
}		

void main(void)
{
	int Lcount, Mcount;
	RandomNumber rnd;
	LinkedList<int> L, M, newList;

	// build lists L and M
	Lcount = rnd.Random(10);
	Mcount = rnd.Random(10) + 10;

	for (int i = 0; i < Lcount; i++)
		L.InsertFront(int(rnd.Random(100)));
			
	for (i = 0; i < Mcount; i++)
		M.InsertFront(int(rnd.Random(100) + 100));
			
	// print the lists
	PrintList(L);
	PrintList(M);
	
	// merge the lists pairwise and print the new list
	newList = MergeList(L,M);
	PrintList(newList);
}

/*
26  25  42  76  78  41
111  154  145  151  172  143  160  121  198  131
26  111  25  154  42  145  76  151  78  172  41  143  160  121  198  131

*/