wex9_31.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "cnode.h"

// concatenate circular list with header t onto the
// end of the circular list with header s
template <class T>
void Concat(CNode<T>& s, CNode<T>& t)
{
	// use currs to traverse list s and currt
	// to traverse list t
	CNode <T> *currs = s.NextNode(), *currt = t.NextNode();
	CNode<T> *newNode;

	// find the end of list s
	while(currs->NextNode() != &s)
		currs = currs->NextNode();

	// traverse list t, inserting a copy of each node
	// onto the end of list s
	while(currt != &t)
	{
		newNode = new CNode<T>(currt->data);
		currs->InsertAfter(newNode);
		currs = newNode;
		currt = currt->NextNode();
	}
}
	
// find the length of the circular list with header s
template <class T>
int Length(CNode<T>& s)
{
	// use p to traverse the list
	CNode <T> *p = s.NextNode();
	// the length is accumulated in l
	int l = 0;
	
	// move around the list counting nodes until
	// we arrive back at the header
	while(p != &s)
	{
		l++;
		p = p->NextNode();
	}

	return l;
}

// return a pointer to the first node in circular list
// with header s containing data value elem. a pointer to
// the header is returned if elem is not found
template <class T>
CNode<T> *Index(CNode<T>& s, T elem)
{
	// start at first node in the list
	CNode<T> *currPtr = s.NextNode();
	
	// traverse circular list
	while(currPtr != &s)
	{
		// break out of the loop if elem found
		if(currPtr->data == elem)
			break;
		currPtr = currPtr->NextNode();
	}
	
	// returns pointer to matching node of header address
	return currPtr;
}

// delete all occurrences of key from list whose front
// pointer is head
template <class T>
void Remove(CNode<T>& s, T elem)
{
	// maintain pointers to previous and current nodes
	// intially, the previous node is header and current
	// node is the first node in the list
	CNode<T> *prevPtr = &s, *currPtr = s.NextNode(), *p;
	
	// traverse the list, performing the deletions
	while(currPtr != &s)
	{
		// check for a match with the key
		if (currPtr->data == elem)
		{
			// remember current node address in p
			p = currPtr;
			// move currPtr ahead 
			currPtr = currPtr->NextNode();
			// unlink node using DeleteAfter for previous node.
			// note there is not a special case of a list head
			prevPtr->DeleteAfter();
			// do the actual deletion of the node
			delete p;
		}
		else
		{
			// no match. just move the two pointers along
			prevPtr = currPtr;
			currPtr = currPtr->NextNode();
		}
	}
}

// create circular linked list with given header node.
// the values in the list are a[0]...a[n-1]
void CreateList(CNode<int> *header, int a[], int n)
{
    // begin inserting after the header
    CNode<int> *currPtr = header, *newNodePtr;
    int i;
    
    // build the n element circular list
    for(i=0;i < n;i++)
    {
        // allocate node with data value a[i]
        newNodePtr = new CNode<int>(a[i]);
        
        // insert at end of the list and advance currPtr to end
        currPtr->InsertAfter(newNodePtr);
        currPtr = newNodePtr;
    }
}

template <class T>
void PrintCList(CNode<T> *header)
{
	CNode<T> *currPtr = header->NextNode();
	
	while(currPtr != header)
	{
		cout << currPtr->data << "  ";
		currPtr = currPtr->NextNode();
	}
	cout << endl;
}

void main(void)
{
	CNode<int> s,t;
	int a[] = {9,5,2,3,1,9,15},
		b[] = {12,10,9,7,5,3,11,9};
	
	CreateList(&s,a,7);
	CreateList(&t,b,8);
	
	cout << "Original circular lists: " << endl;
	PrintCList(&s);
	PrintCList(&t);
	
	cout <<  "The length of the lists is: "
		 << Length(s) << "  " << Length(t) << endl;
	cout << endl;
	
	cout << "Concatenating the second list onto the first:" << endl;
	Concat(s,t);
	cout << "The new list is:" << endl;
	PrintCList(&s);
	cout << endl;
	
	cout << "Searching the new list for data values 9 and 77:" << endl;
	if (Index(s,9) != &s)
		cout << "9 found" << endl;
	else
		cout << "9 not in the list (error)" << endl;
	if (Index(s,77) != &s)
		cout << "77 found (error)" << endl;
	else
		cout << "77 not in the list" << endl;
	cout << endl;
	
	cout << "Deleting all occurrences of 9 from the list:" << endl;
	Remove(s,9);
	PrintCList(&s);
}

/*
<Run>

Original circular lists:
9  5  2  3  1  9  15
12  10  9  7  5  3  11  9
The length of the lists is: 7  8

Concatenating the second list onto the first:
The new list is:
9  5  2  3  1  9  15  12  10  9  7  5  3  11  9

Searching the new list for data values 9 and 77:
9 found
77 not in the list

Deleting all occurrences of 9 from the list:
5  2  3  1  15  12  10  7  5  3  11
*/