wex9_28.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "cnode.h"

// search for data value elem in the circular linked list with
// the given header node. if found, replace it by newelem and
// return a pointer to the matching node; otherwise, return NULL
template <class T>
CNode<T> *Replace(CNode<T> *header, CNode<T> *start, T elem, T newelem)
{	
	// if we are starting at the header, advance one node forward
	// to the first data value in the list. if this is again the
	// header, the list is empty and we return
	if (start == header)
	{
		start = start->NextNode();
		if (start == header)
			return NULL;
	}
		
	// move p around the list looking for elem
	CNode <T> *p = start, *retvalue = NULL;
	
	do
	{
		// if we find elem, assign retvalue the address p
		// and break from the loop
		if (p->data == elem)
		{
			p->data = newelem;
			retvalue = p;
			break;
		}
		
		// have not found elem yet. advance one node forward
		p = p->NextNode();

		// if p is the header and we did not start at the
		// header, move p forward. if p is the header and
		// we started there, we did not find elem
		if (p == header && start != header)
			p = p->NextNode();
	} while (p != start);
	
	// return address of matching node or NULL
	return retvalue;
}

// 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> header, *p;
	int a[] = {2,5,6,3,1,8,15,12,10,4,7,5,3,9,11};
	
	CreateList(&header,a,15);
	
	cout << "Original circular list: ";
	PrintCList(&header);
	cout << endl;
	
	cout << "Replacing 4 by 55 starting at header:" << endl;
	Replace(&header,&header,4,55);
	PrintCList(&header);
	cout << endl;
	
	cout << "Replacing 6 by 33 starting at fourth node of list:" << endl;
	p = &header;
	for(int i=0;i < 4;i++)
		p = p->NextNode();
	Replace(&header,p,6,33);
	PrintCList(&header);
	cout << endl;
	
	cout << "Attempting to replace 99 by 17" << endl;
	if (Replace(&header,&header,99,17) == NULL)
		cout << "99 is not in the list" << endl;
	else
		cout << "Replace is in error!" << endl;
}

/*
<Run>

Original circular list: 2  5  6  3  1  8  15  12  10  4  7  5  3  9  11

Replacing 4 by 55 starting at header:
2  5  6  3  1  8  15  12  10  55  7  5  3  9  11

Replacing 6 by 33 starting at fourth node of list:
2  5  33  3  1  8  15  12  10  55  7  5  3  9  11

Attempting to replace 99 by 17
99 is not in the list
*/