pex9_1.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "node.h"
#include "nodelib.h"

// delete the rear node in the list. return a pointer
// to the deleted node
template <class T>
Node<T> *DeleteRear(Node<T> * & head)
{
	// prevPtr, currPtr traverse the list
	Node<T> *currPtr = head, *prevPtr = NULL;
	
	// if the list is empty, return NULL
	if (head == NULL)
		return NULL;
	else
	{
		// cycle the list, looking for the node whose
		// pointer is NULL. this is the rear node
		while (currPtr->NextNode() != NULL)
		{
			prevPtr = currPtr;
			currPtr = currPtr->NextNode();
		}

		// if prevPtr is NULL, the list has only 1 element
		// the list is now empty
		if (prevPtr == NULL)
			head = NULL;
		else
			// delete the rear of a list with >= 2 nodes
			prevPtr->DeleteAfter();
		// return address of the former rear
		return currPtr;
	}
}			

// delete all occurrences of key from list whose front
// pointer is head
template <class T>
void DeleteKey(Node<T> * & head, const T& key)
{
	// maintain pointers to previous and current nodes
	Node<T> *prevPtr = NULL, *currPtr = head, *p;
	
	// traverse the list, performing the deletions
	while(currPtr != NULL)
	{
		// check for a match with the key
		if (currPtr->data == key)
		{
			// remember current node address in p
			p = currPtr;
			// see if deletion occured at front of list or inside
			if (prevPtr == NULL)
				// unlink front node by reassigning head
				head = currPtr->NextNode();
			else
				// unlink interior node using DeleteAfter for previous node
				prevPtr->DeleteAfter();
			// node currPtr contains address of new current node 
			currPtr = currPtr->NextNode();
			// do the actual deletion of the node
			delete p;
		}
		else
		{
			// no match. just move the two pointers along
			prevPtr = currPtr;
			currPtr = currPtr->NextNode();
		}
	}
}

void main(void)
{
	// A contains the 10 values inserted into the list
	int A[10] = {3, 7, 7, 2, 9, 7, 3, 5, 2, 1};
	int key;
	// the linked list
	Node<int> *list = NULL, *p;

	// form the list using InsertFront
	for (int i = 0; i < 10; i++)
	{
		InsertFront(list,A[i]);
	}
	// print the original list		
	PrintList(list);
	cout << endl;
	
	// prompt for a key, delete all occurrences of the key
	// and print the modified list
	cout << "Enter a key: ";
	cin >> key;
	DeleteKey(list,key);
	PrintList(list);
	cout << endl;
	
	// use DeleteRear to successively delete nodes, printing
	// the data value in each one
	while (list != NULL)
	{
		p = DeleteRear(list);
		cout << p->data << "  ";
		delete p;
	}
	cout << endl;
	
	// the list should now be empty
	if (list == NULL)
		cout << "The list is empty." << endl;
	else
		cout << "The list is not empty (error)." << endl;
}

/*
<Run>

1  2  5  3  7  9  2  7  7  3
Enter a key: 7
1  2  5  3  9  2  3
3  2  9  3  5  2  1
The list is empty.
*/