pex9_2.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "strclass.h"
#include "nodelib.h"

struct IntEntry
{
	int	value;		// integer number
	int count;		// number of occurrences of value 
};

// relational equals. compare the value fields
int operator== (const IntEntry& a, const IntEntry& b)
{
	return a.value == b.value;
}

// relational less than. compare the value fields
int operator< (const IntEntry& a, const IntEntry& b)
{
	return a.value < b.value;
}

// output IntEntry item in form "value(count)"
ostream& operator<< (ostream& ostr, const IntEntry& item)
{
	ostr << item.value;
	ostr << "(" << item.count << ")";

	return ostr;
}

// insert IntEntry item into an ordered list if
// it is not already in the list. if in the list, increment
// the count field of item
void InsertOrder(Node<IntEntry>* & head, IntEntry item)
{
    // currPtr moves through list, trailed by prevPtr
    Node<IntEntry> *currPtr, *prevPtr, *newNode;
    
    // prevPtr == NULL signals match at front
    prevPtr = NULL;
    currPtr = head;
    
    // cycle through the list and find insertion point
    while (currPtr != NULL && currPtr->data < item)
    {
		// advance currPtr so prevPtr trails it
        prevPtr = currPtr;
        currPtr = currPtr->NextNode();
    }   

	// if currPtr == NULL and prevPtr == NULL, the list is empty.
	// insert item at the front of the list
	if (currPtr == NULL && prevPtr == NULL)
		InsertFront(head,item);
	else
	// the list is not empty. determine whether to update
	// the count field of an existing data value or insert
	// the data value into the list
	
	// if the value fields match, increment the count field
	if (currPtr->data == item)
		currPtr->data.count++;
	else
	    // insert item into the list
	    
	    if (prevPtr == NULL)
		// if prevPtr == NULL, insert at front
	        InsertFront(head,item);
		else
	    {
			// insert new node after previous
			newNode = GetNode(item);
			prevPtr->InsertAfter(newNode);
	    }
}

void DeleteGreater(Node<IntEntry>* & head, int key)
{
	// cycle through the list using prevPtr, currPtr
	Node<IntEntry> *prevPtr = NULL, *currPtr = head;
	
	while(currPtr != NULL)
		// delete any record whose value field is > key
		if (key < currPtr->data.value)
		{
			// if front node is > key, the entire list
			// must be deleted. do this by deleting
			// the front element until the list is empty
			if (prevPtr == NULL)
				while(head != NULL)
					DeleteFront(head);
			else
				// delete the list from currPtr to the end by
				// executing prevPtr->DeleteAfter until the
				// pointer field of prevPtr becomes the NULL pointer
				do
					prevPtr->DeleteAfter();
				while (prevPtr->NextNode() != NULL);
			return;
		}
		else
		{
			// move the pair of pointers along
			prevPtr = currPtr;
			currPtr = currPtr->NextNode();
		}
}

void main(void)
{
	Node<IntEntry> *list = NULL;
	IntEntry item;
	int A[10] = {1, 1, 5, 6, 6, 9, 7, 6, 2, 8}, key;

	// set count field of item to 1. we change the value field as
	// records are inserted into the list. if a data record matching
	// the value field is not in the list, item is added with a count
	// of 1; otherwise, the count field of the existing list record
	// is incremented
	item.count = 1;
	// insert each element of A into the ordered list
	for (int i = 0; i < 10; i++)
	{
		item.value = A[i];
		InsertOrder(list,item);
	}
	PrintList(list);
	cout << endl << endl;

	cout << "Enter a key: ";
	cin >> key;
	DeleteGreater(list,key);
	PrintList(list);
	cout << endl;
}

/*
<Run>

1(2)  2(1)  5(1)  6(3)  7(1)  8(1)  9(1)

Enter a key: 6
1(2)  2(1)  5(1)  6(3)
*/