wex9_30.cpp

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

#include <iostream.h>
#pragma hdrstop

#include "cnode.h"

template <class T>
struct CList
{
	CNode<T> header;
	CNode<T> *rear;
};

// Insert node p at the front of list L
template <class T>
void InsertFront(CList<T>& L, CNode<T> *p)
{
	// insert node p after the header
	L.header.InsertAfter(p);
	// if rear currenty points to the header, the list was
	// empty. assign rear to the address of the new node
	if (L.rear == &L.header)
		L.rear = p;
}

// Insert node p at the rear of list L
template <class T>
void InsertRear(CList<T>& L, CNode<T> *p)
{
	// insert p after the rear node
	L.rear->InsertAfter(p);
	// the rear is now p
	L.rear = p;
}

// delete the first node of list L
template <class T>
CNode<T> *DeleteFront(CList<T>& L)
{
	// unlink the front node and assign its address
	// to p. if the list is empty, DeleteAfter returns NULL
	CNode<T> *p = L.header.DeleteAfter();

	// if the header now points to itself, the list is
	// empty. reassign rear to point to the header
	if (L.header.NextNode() == &L.header)
		L.rear = &L.header;

	return p;
}

// create CList L. the values in the list are a[0]...a[n-1]
void CreateList(CList<int> *L, int a[], int n)
{    
	CNode<int> *newNodePtr;
	
    // build the n element CList L
    for(int i=0;i < n;i++)
    {
        // allocate node with data value a[i]
        newNodePtr = new CNode<int>(a[i]);
        // insert new node at rear of L
		InsertRear(*L, newNodePtr);
    }
}

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

void main(void)
{
	// the data values in a are used to build the list L
	CList<int> L;
	CNode<int> *p;
	int a[] = {2,5,6,3,1,8,15,12,10,4,7,5,3,9,11};
	
	// initialize L.rear to the address of the header
	L.rear = &L.header;
	
	// create and print L. CreateList tests InsertRear
	CreateList(&L,a,15);
	PrintCList(&L);
	cout << endl;

	// test InsertFront/DeleteFront
	cout << "Deleting the first six values in L:" << endl;
	cout << "Deleted: ";
	for(int i=0;i < 6;i++)
	{
		p = DeleteFront(L);
		cout << p->data << "  ";
		delete p;
	}
	cout << endl << "The new list is: ";
	PrintCList(&L);
	cout << endl << "Inserting 5 and 6 at the front of the list:"
		 << endl;
	InsertFront(L,new CNode<int>(6));
	InsertFront(L,new CNode<int>(5));
	cout << endl << "The new list is: ";
	PrintCList(&L);

	cout << endl << "Deleting the entire list." << endl;
	while(DeleteFront(L) != NULL);
	if (L.rear == &L.header)
		cout << "The list is empty." <<endl;
	else
		cout << "Error. The list is not empty!" << endl;
}

/*
<Run>

2  5  6  3  1  8  15  12  10  4  7  5  3  9  11

Deleting the first six values in L:
Deleted: 2  5  6  3  1  8
The new list is: 15  12  10  4  7  5  3  9  11

Inserting 5 and 6 at the front of the list:

The new list is: 5  6  15  12  10  4  7  5  3  9  11

Deleting the entire list.
The list is empty.
*/