pex9_15.cpp

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

#include <iostream.h>
#include <stdlib.h>
#pragma hdrstop

#include "dnode.h"
#include "link.h"

// print the linked list L
template <class T>
void PrintList(LinkedList<T>& L)
{
	for(L.Reset();!L.EndOfList();L.Next())
		cout << L.Data() << "  ";
	cout << endl;
}		


void main(void)
{
	// header for the doubly linked list
	DNode<int> header, *p;
	// singly linked lists holding the positive and
	// negative data values
	LinkedList<int> positives, negatives;
	int item;

	// read 10 integers, inserting the positive
	// integers to the right of the header and
	// the negatives ones to the left of the header
	for (int i = 0; i < 10; i++)
	{
		cin >> item;
		p = new DNode<int>(item);
		if (item < 0)
			header.InsertLeft(p);
		else
			header.InsertRight(p);
	}

	// display the doubly linked list. print the negative numbers
	// and the positive numbers from left to right. indicate the
	// position of the header
	cout << "Doubly linked list: ";
	// find the last node going left that has a negative data value
	p = &header;
	while(p->NextNodeLeft() != &header && p->NextNodeLeft()->data < 0)
		p = p->NextNodeLeft();
	// print the negative values from p. stop at the header
	while(p != &header)
	{
		cout << p->data << "  ";
		p = p->NextNodeRight();
	}
	// indicate we have reached the header
	cout << "<header>  ";
	// print the positive values by moving right from the header.
	// stop when we find a negative value or encounter the header
	p = header.NextNodeRight();
	while(p != &header && p->data >= 0)
	{
		cout << p->data << "  ";
		p = p->NextNodeRight();
	}
	cout << endl;

	// move right from the header, inserting each postive
	// integer into the singly linked list positives. stop
	// when a negative value is found or the header is reached
	p = header.NextNodeRight();
	while(p != &header && p->data >= 0)
	{
		positives.InsertRear(p->data);
		p = p->NextNodeRight();
	}
	
	// move left from the header, inserting each negative
	// integer at the front of the singly linked list negatives.
	// stop when a positive value is found or the header is reached.
	// insert at the front so the list will reflect the left to
	// right ordering in the doubly linked list
	p = header.NextNodeLeft();
	while(p != &header && p->data < 0)
	{
		negatives.InsertFront(p->data);
		p = p->NextNodeLeft();
	}
	
	// print the two singly linked lists
	cout << "Negative numbers: ";
	PrintList(negatives);
	cout << "Positive numbers: ";
	PrintList(positives);
}

/*
<Run>

3 -5 6 2 8 -4 -9 -1 7 9
Doubly linked list: -5  -4  -9  -1  <header>  9  7  8  2  6  3
Negative numbers: -5  -4  -9  -1
Positive numbers: 9  7  8  2  6  3
*/