ch04鏈接堆棧和隊列

Chapter

4Linked

Stacks

and

QueuesContent

PointsPointers

and

Linked

StructuresLinked

StacksLinked

Stacks

with

SafeguardsLinked

QueuesApplication:

Polynomial

ArithmeticAbstract

Data

Types

and

Their

ImplementationsPOINTERS

AND

LINKED

STRUCTURES（指針和鏈式結構）Introduction

and

Survey The

Problem

of

OverflowIf

weimplement

adatastructurebystoringallthedatawithin

arrays,

then

the

arrays

must

be

declaredto

have

somesize

that

is

fixed

when

the

program

is

written,

andthattherefore

cannot

be

changedwhile

the

program

isrunning.When

writinga

program,

we

mustdecide

onthemaximumamount

of

memory

that

will

be

needed

for

our

arraysandsetthis

asidein

thedeclarations.we

canencounteroverflow.PointersModernlanguages,

including

C++,

provide

constructions

thatallow

us

to

keep

datastructures

inmemory

without

usingarrays,wherebywecanavoidthesedifficulties.POINTERS

ANDLINKED

STRUCTURESDiagram

Conventions（有關圖的表示的約定）In

the

diagram,

theobject

“Dave”is

lost,

withno

pointer

referring

to

it,and

therefore

there

is

noway

to

find

it.

In

such

asituation,

we

shall

say

thatthe

object

has egarbage.Therefore,

in

ourwork,we

shall

always

strive

toavoid

the

creationofgarbage.POINTERS

ANDLINKED

STRUCTURESLinked

StructuresPOINTERS

ANDLINKED

STRUCTURESContiguous

and

Linked

List（順序表和鏈表）We

speak

of

a

list

kept

in

an

array

as

a

contiguouslist.Dynamic

Memory

Allocation（動態(tài)分配內存）advantages

of

dynamic

memory

allocation：a

program

can

start

small

and

grow

only

as

necessary,so

that

when

it

is

small,

it

can

run

more

efficiently,and,

when

necessary,it

can

grow

to

the

limits

of

thecomputer

system.Pointersand

Dynamic

Memory

in

C++AutomaticObjectsAutomatic

objects

are

those

that

are

declared

andnamed,asusual,

whilewriting

theprogram.Space

for

them

isexplicitly

allocated

by

the

compilerand

exists

as

long

as

the

block

of

the

program

in

whichthey

are

declaredis

running.Dynamic

ObjectsDynamic

objects

are

created(and

perhaps

destroyed)during

program

execution.Since

dynamicobjectsdonotexistwhiletheprogram

iscompiled,

butonlywhen

itisrun,

theyare

notassignednames

while

itis

being

written.

Moreover,

the

storageoccupied

by

dynamicobjects

must

be

managed

entirely

bythe

programmer.The

onlywaytoaccessadynamicobjectisbyusingpointers.Pointersand

Dynamic

Memory

in

C++C++Notation（符號）指針的定義

Item

*item_ptr;we

see

that

the

declaration

says

that

item_ptr

is

a

pointerto

an

Item

object.Creating

and

Destroying

Dynamic

ObjectsFor

example,

suppose

that

p

has

been

declared

as

a

pointerto

typeItem.

Then

thestatementp

=

new

Item;creates

a

new

dynamic

object

of

type

Item

and

assigns

itslocation

to

the

pointerp.the

modified

statementp

=

new(nothrow)Item;restoresthe

traditional

behavior

of

the

newoperator.Pointersand

Dynamic

Memory

in

C++delete

p;disposes

of

the

object.

After

this

delete

statement

isexecuted,

thepointer

variable

pis

undefined

andso

shouldnotbe

useduntil

itis

assigned

a

new

value.Pointersand

Dynamic

Memory

in

C++FollowingthePointersFor

example,the

assignmentexpression

*p=0resetsthevalue

of

the

object

referenced

by

p

to

0.a

dereferenced

pointerPointersand

Dynamic

Memory

in

C++NULL

PointersThis

situation

can

beestablished

bytheassignmentp

=

NULL;Indiagrams

we

reserve

the

electrical

ground

symbolActually,

thevalueNULL

isnot

partoftheC++language,but

it

is

defined,

as

0,

in

standard

header

files

such

as<cstddef>

that

we

include

in

our

utility

headerfile.Note

carefully

the

distinction

between

a

pointervariable

whose

valueis

undefinedanda

pointer

variablewhose

value

is

NULL.Pointersand

Dynamic

Memory

in

C++NULL

PointersThe

assertion

p

==

NULL

means

that

p

currentlypoints

to

no

dynamic

object.

If

the

value

of

p

isundefined,

then

p

might

point

to

any

randomlocation

in

memory.Pointersand

Dynamic

Memory

in

C++Dynamically

allocated

arraysThenewanddelete

keywordscanbe

usedto

assign

anddelete

contiguous

blocks

of

dynamic

storagefor

use

asarrays.

Forexample,

if

array_size

represents

an

integervalue,the

declarationitem_array

=

new

Item[array_size];creates

a

dynamic

array

of

Item

objects.

The

entries

ofthis

array

are

indexed

from

0

up

to

array_size

-1.

Weaccess

atypicalentrywith

anexpression

such

asitem_array[i].Pointersand

Dynamic

Memory

in

C++Dynamically

allocated

arraysFor

example,

we

can

read

in

an

array

size

from

auser

and

create

and

use

an

appropriate

array

withthe

following

statements.

The

resultingassignments

are

illustrated

in

Figure

4.5.int

size,

*dynamic_array,

i;cout

<<

"Enter

an

array

size:

"

<<

flush;cin

>>

size;dynamic_array

=

new

int[size];for

(i

=

0;

i

<

size;

i++)

dynamic_array[i]

=

i;Pointersand

Dynamic

Memory

in

C++The

result

is

illustrated

as:The

statement

delete

[]dynamic

array;

returns

thestorage

in

dynamic

array

to

the

free

store.Pointersand

Dynamic

Memory

in

C++Pointersand

Dynamic

Memory

in

C++Addresses

of

automatic

objectsIf

xisa

variable

oftypeItem,

then&x

isa

value

of

typeItem that

gives

the

address

of

x.

In

this

case

adeclarationandassignment

such

as

Item

*ptr

=&x

would

establish

apointer,

ptr,

to

the

object

x.Address

of

an

arrayThe

address

of

the

initial

element

of

an

array

is

found

byusing

the

array'snamewithout

anyattached

[]operators.For

example,

given

a

declaration

Item

x[20]

theassignmentItem*ptr=

xsets

upapointer

ptrto

theinitialelement

of

thearrayx.An

assignment

expression

ptr

=

&(x[0])

could

also

be

used

tofind

this

address.Pointersand

Dynamic

Memory

in

C++Pointers

to

Structures(*p).the_data，p->the_data等價，但后者使用更簡便例：class

Fraction{public:int

numerator;int

denominator;};Fraction

*p;p->numerator=0，(*p).numerator=0兩者意義一樣The

Basics

of

Linked

StructuresNodes

and

Type

DeclarationsTheonly

difference

between

a

struct

anda

class

is

that,unless

modified

by

the

keywords

private

andpublic,membersof

a

struct

are

public

whereas

members

of

a

class

areprivate.Thus,

by

usingmodifiers

public

and

private

to

adjustthe

visibility

of

members,

wecan

implement

any

structure

aseithera

struct

ora

class.struct

Node

{//

data

membersNode_entry

entry;Node*next;//

constructorsNode(

);Node(Node_entry

item,

Node

*add_on

=

NULL);};The

Basics

of

Linked

StructuresThe

Basics

of

Linked

StructuresNode

ConstructorsNode

::

Node(){next

=

NULL;}Thesecondform

acceptstwo

parameters

forinitializingthedatamembers.Node

::

Node(Node_entry

item,

Node

*add_on){entry

=

item;next

=

add_on;}The

Basics

of

Linked

StructuresFor

example,

the

following

codewill

produce

the

linkednodesillustrated

in

Figure

4.8.Node

first_node(‘a’);

//

Node

first_node

stores

data

’a’.Node

*p0

=

&first_node;

//

p0

points

to

first_Node.Node

*p1

=

new

Node(‘b’);

//

A

second

node

storing

‘b’

is

created.p0->next

=

p1;

//

The

second

Node

is

linked

after

first_node.Node

*p2

=

new

Node(‘c’,

p0);

//

A

third

Node

storing

‘c’

is

created.//

Thethird

Nodelinks

back

to

the

first

node,

*p0.p1->next

=

p2;

//

The

third

Node

is

linked

after

the

secondNode.Linked

Stacks（鏈棧）typedef

Stack_entry

Node_entry;Linked

Stacksdeclaration

of

type

Stackclass

Stack

{public:Stack(

);bool

empty(

)const;Error_code

push(const

Stack_entry

&item);Error_code

pop(

);Error_code

top(Stack_entry

&item)

const;protected:Node

*top_node;};Linked

Stacks Themost

importantreason

isto

maintainencapsulation:

Ifwe

do

notuse

a

classto

containour

stack,

welose

theabilityto

set

up

methods

for

thestack. The

second

reason

is

to

maintain

the

logical

distinctionbetween

the

stack

itself,

which

is

made

up

of

all

of

itsentries(eachin

anode),

and

thetopofthestack,

which

isapointer

toa

single

node.The

fact

that

we

need

only

keep

track

of

the

topof

the

stack

to

find

all

its

entries

is

irrelevant

to

this

logicalstructure. The

third

reason

is

to

maintainconsistency

with

other

datastructures

andotherimplementations,where

structures

areneededto

collect

several

methods

and

pieces

of

information. Finally,

keeping

a

stack

and

apointer

to

itstop

as

patibledata

types

helps

with

debugging

by

allowing

the

compiler

toperform

bettertype

checking.Linked

Stacksempty

stack（空棧）Let

usstartwith

an

emptystack,

which

nowmeanstop_node

==NULL,

and

consider

how

to

addStack_entryitem

as

the

first

entry.

We

must

create

a

new

Node

storing

acopy

ofitem,indynamicmemory.WeshallaccessthisNodewith

a

pointer

variable

new_top.We

must

then

copy

theaddress

storedin

new_topto

the

Stack

membertop_node.Hence,pushing

item

onto

the

Stack

consists

of

theInstructionsNode

*new_top

=new

Node(item);

top_node

=

new_top;Notice

that

the

constructor

that

creates

the

Node*new_top

sets

its

next

pointer

to

the

default

value

NULL.Linked

Stackspushing

a

linked

stack（入棧）Linked

Stackspushing

a

linked

stack（入棧）Error_code

Stack

::

push(constStack_entry

&item)/*

Post:

Stack_entry

item

is

added

to

the

top

of

the

Stack;

returnssuccess

or

returns

a

code

of

overflow

if

dynamic

memory

isexhausted.

*/{Node

*new_top

=

new

Node(item,

top_node);if

(new_top

==

NULL)

return

overflow;top_node

=

new_top;return

success;}Linked

Stackspopping

a

linked

stack（出棧）Error_code

Stack

::

pop(

)/*

Post:

Thetop

of

the

Stack

is

removed.

If

the

Stack

is

empty

themethod

returns

underflow;

otherwise

it

returns

success.*/{Node

*old_top

=

top_node;if

(top_node

==

NULL)

return

underflow;top_node=old_top->next;delete

old_top;return

success;}LINKED

STACKS

WITHSAFEGUARDSThe

DestructorProblem

Examplefor(int

i

=

0;i

<

1000000;

i++)

{Stack

small;small.push(some_data);}destructorsTheC++languageprovides

class

methods

known

asdestructors

that

solve

our

problem.

For

every

class,a

destructor

is

a

special

method

that

is

executed

onobjects

of

the

class

immediately

before

they

go

outofscope.Stack

::

~Stack(

);LINKED

STACKS

WITHSAFEGUARDSStack

::

Stack(

)

//

Destructor/*

Post:

The

Stack

is

cleared.

*/{while

(!empty(

))pop();}LINKED

STACKS

WITHSAFEGUARDSOverloading

the

Assignment

OperatorStack

outer_stack;for

(int

i

=

0;

i

<

1000000;

i++)

{Stackinner_stack;inner_stack.push(some_data);inner_stack

=outer_stack;}LINKED

STACKS

WITHSAFEGUARDSoverloaded

assignmentvoid

Stack

::

operator

=(const

Stack&original);operator

syntaxFirst,

we

must

make

a

copy

of

the

data

stacked

in

thecalling

parameter.Next,

wemust

clearout

any

data

already

in

theStackobject

being

assignedto.Finally,

we

must

move

the

newly

copied

data

to

the

Stackobject.LINKED

STACKS

WITHSAFEGUARDSvoid

Stack

::

operator

=

(const

Stack

&original)//

Overload

assignment/*

Post:

The

Stack

is

reset

as

acopy

of

Stack

original.*/{Node

*new_top,

*new_copy,

*original_node

=

original.top_node;if

(original_node

==

NULL)

new_top

=

NULL;else

{

//

Duplicate

the

linkednodesnew_copy

=

new_top

=

new

Node(original_node->entry);while

(original_node->next!=

NULL)

{original_node

=

original_node->next;new_copy->next

=

new

Node(original_node->entry);new_copy

=

new_copy->next;}}while

(!empty(

))

//

Clean

out

old

Stack

entriespop();top_node

=

new_top;

//

and

replace

them

with

newentries.}LINKED

STACKS

WITHSAFEGUARDSThe

Copy

ConstructorProblem

example:void

destroy_the_stack

(Stack

copy){}int

main(

){Stackvital_data;destroy_the_stack(vital_data);}copy

constructorStack

::

Stack(const

Stack

&original);LINKED

STACKS

WITHSAFEGUARDSStack

::

Stack(const

Stack

&original)

//

copy

constructor/*

Post:The

Stack

is

initialized

as

a

copy

of

Stack

original.

*/{Node

*new_copy,

*original_node

=

original.top_node;if

(original_node

==

NULL)

top_node

=

NULL;else

{

//

Duplicate

the

linked

nodes.top_node

=

new_copy

=

new

Node(original_node->entry);while

(original_node->next!=

NULL)

{original_node

=

original_node->next;new_copy->next

=

new

Node(original_node->entry);new_copy

=

new_copy->next;}}}LINKED

STACKS

WITHSAFEGUARDSThe

Modified

Linked-Stack

Specificationclass

Stack

{public://

Standard

Stack

methodsStack(

);bool

empty(

)

const;Error_code

push(const

Stack_entry

&item);Error_code

pop(

);Error_code

top(Stack_entry

&item)

const;//

Safety

features

for

linked

structures~Stack(

);Stack(const

Stack

&original);void

operator

=

(const

Stack

&original);protected:Node

*top_node;};LINKED

QUEUES（鏈隊列）LINKED

QUEUES（鏈隊列）Basic

Declarationsclass

Queue

{public://

standard

Queue

methodsQueue(

);bool

empty(

)

const;Error_code

append(const

Queue_entry

&item);Error_code

serve(

);Error_code

retrieve(Queue_entry

&item)

const;//

safety

features

for

linked

structures~Queue(

);Queue(const

Queue

&original);void

operator

=

(const

Queue

&original);protected:Node

*front,

*rear;};LINKED

QUEUESInitialize（初始化）Queue

::

Queue(

)/*

Post:

The

Queue

is

initialized

to

be

empty.

*/{front

=

rear

=

NULL;}LINKED

QUEUESAppend（入隊）Error_code

Queue

::

append(const

Queue_entry

&item)/*

Post:

Add

item

to

the

rear

of

the

Queue

and

return

a

code

ofsuccess

or

return

a

code

of

overflow

if

dynamic

memoryisexhausted.

*/{Node

*new_rear

=

new

Node(item);if

(new_rear

==

NULL)

return

overflow;if

(rear

==

NULL)front

=

rear

=

new_rear;else

{rear->next

=new_rear;rear

=

new_rear;}return

success;}LINKED

QUEUESServe（出隊）Error_code

Queue

::

serve(

)/*

Post:

The

front

of

the

Queue

is

removed.

If

the

Queueis

empty,

return

an

Error_code

of

underflow.

*/{if

(front

==

NULL)

return

underflow;Node

*old_front

=

front;front

=

old_front->next;if

(front

==

NULL)

rear

=

NULL;delete

old_front;return

success;}LINKED

QUEUESExtended

Linked

Queuesclass

Extended_queue:

public

Queue

{public:bool

full(

)

const;int

size(

)

const;void

clear(

);Error_codeserve_and_retrieve(Queue_entry

&item);};LINKED

QUEUESint

Extended_queue

::

size(

)

const/*

Post:

Return

the

number

of

entries

intheExtended_queue.*/{Node

*window

=

front;int

count

=

0;while

(window

!=

NULL)

{window

=

window->next;count++;}return

count;}APPLICATION:

POLYNOMIAL

ARITHMETIC（多項式運算）We

develop

a

program

that

simulates

a

calculator

that

doesaddition,

subtraction,

multiplication,

division,

and

otheroperations

for

polynomials

ratherthan

numbers.We

modela

reverse

Polish

calculator

whose

operands(polynomials)

areentered

before

the

operation

is

specified.Theoperands

are

pushed

onto

astack.

When

an

operation

isperformed,

itpops

itsoperands

from

the

stack

and

pushes

itsresult

back

onto

the

stack. We

reuse

the

conventions

of

Section2.3:

?denotespushing

anoperand

onto

the

stack,

C

,

-,

*,

/represent

arithmeticoperations,

and=

means

printing

the

top

of

the

stack

(but

notpopping

itoff).APPLICATION:POLYNOMIAL

ARITHMETICThe

Main

Programint

main(

) /*

Post:

The

program

has

executed

simple

polynomialarithmetic

commands

entered

by

the

user. Uses:

The

classes

Stack

and

Polynomial

and

thefunctions

introduction, mand,

and mand.

*/

{Stack

stored_polynomials;introduction(

);instructions(

);while

(

mand(

mand(

)

stored

polynomials));APPLICATION:POLYNOMIAL

ARITHMETICPolynomial

MethodsAs

in

Section

2.3,

we

represent

the

commandsthat

a

user

can

type

by

the

characters

?

,

=

,

+

,

-,*

,

/,

where

?

requests

input

of

a

polynomial

fromthe

user,

=

prints

the

result

of

an

operation,

andthe

remaining

symbols

denote

addition,

subtraction,multiplication,

and

division,

respectively.Most

of

these

commands

will

need

to

invokePolynomial

class

methods;

hence

we

must

now

decideon

the

form

of

some

of

these

methods.APPLICATION:POLYNOMIAL

ARITHMETICWe

will

need

a

method

to

add

a

pair

of

polynomials.

Oneconvenientway

to

implement

this

method

is

as

a

method,equals_sum,

ofthePolynomialclass.Thus,ifp,q,rarePolynomial

objects,

the

expression

p.equals_sum(q,r)

replaces

pby

thesum

of

thepolynomialsqand

r.We

shall

implement

similar

methodscalled

equals_difference,equals_product,

and

equals_quotient

to

perform

otherarithmetic

operations

on

polynomials.The

user

commands

=

and

?

will

lead

us

to

call

on

Polynomialmethods

to

print

out

and

readin

polynomials.

Thus

weshallsuppose

that

Polynomial

objectshave

methodswithoutparameterscalled

print

and

readto plish

thesetasks.APPLICATION:POLYNOMIAL

ARITHMETICPerforming

Commandsbool mand(char

command,

Stack

&stored_polynomials) /*

Pre:

The

first

parameter

specifies

a

valid

calculatorcommand. Post:

The

command

specified

by

the

first

parameterhas

been

applied

to

the

Stack

of

Polynomial

objectsgiven

by

the

second

parameter.

A

result

of

true

isreturned

unless

command

==

‘q’.Uses:

The

classes

Stack

and

Polynomial.

*/

{Polynomial

p,

q,

r;APPLICATION:POLYNOMIAL

ARITHMETICswitch

(command)

{case

‘?’:p.read(

);if

(stored_polynomials.push(p)

==overflow)cout

<<

"Warning:

Stack

full,

lostpolynomial"

<<

endl;break;case

‘=‘:if

(stored_polynomials.empty(

))cout

<<

"Stack

empty"

<<

endl;else

{stored_polynomials.top(p);p.print(

);}break;APPLICATION:POLYNOMIAL

ARITHMETICcase

‘+’:if

(stored_polynomials.empty(

))cout

<<

"Stack

empty"

<<endl;else

{stored_polynomials.top(p);stored_polynomials.pop();if

(stored_polynomials.empty(

))

{cout

<<

"Stack

has

just

one

polynomial"

<<

endl;stored_polynomials.push(p);}else

{stored_polynomials.top(q);stored_polynomials.pop();r.equals_sum(q,

p);if

(stored_polynomials.push(r)

==

overflow)cout

<<

"Warning:

Stack

full,

lost

polynomial"<<endl;}}break;APPLICATION:POLYNOMIAL

ARITHMETIC//

Add

options

for

further

user

commands.case

‘q’:cout

<<

"Calculation

finished."

<<

endl;return

false;}

//end

switchreturn

true;}APPLICATION:POLYNOMIAL

ARITHMETICStubs

and

Testing class

Polynomial

{ public:void

read();void

print();void

equals_sum(Polynomial

p,

Polynomial

q);void

equals_difference(Polynomial

p,

Polynomial

q);void

equals_product(Polynomial

p,

Polynomial

q);Error_code

equals_quotient(Polynomial

p,

Polynomial

q);private:double

value;};APPLICATION:POLYNOMIAL

ARITHMETICStubs

and

Testing class

Polynomial

{ public:void

read();void

print();void

equals_sum(Polynomial

p,

Polynomial

q);void

equals_difference(Polynomial

p,

Polynomial

q);void

equals_product(Polynomial

p,

Polynomial

q);Error_code

equals_quotient(Polynomial

p,

Polynomial

q);private:double

value;};void

Polynomial

::

equals_sum(Polynomial

p,

Polynomial

q){value

=

p.value

+

q.value;}The

Polynomial

Data

Structurestruct

Term

{Term

int

degree;double

coefficient;Term

(int

exponent

=

0,

double

scalar

=

0);};Term::

Term(int

exponent,

double

scalar)/*

Post:

The

Term

is

initialized

with

the

given

coefficient

andexponent,

or

with

default

parameter

values

of

0.

*/{degree

=

exponent;coefficient

=

scalar;}The

Polynomial

Data

Structuretypedef

Term

Node_entry;

typedef

Node_entry

Queue_entry;typedef

Polynomial

Stack_entryThe

Polynomial

Data

Structureclass

Polynomial:

private

Extended_queue

{

//

Use

private

inheritance.public:void

read();void

print(

)

const;void

equals_sum(Polynomial

p,

Polynomial

q);void

equals_difference(Polynomial

p,

Polynomial

q);void

equals_product(Polynomial

p,

Polynomial

q);Error_code

equals_quotient(Polynomial

p,

Polynomial

q);int

degree(

)

const;private:void

mult_term(Polynomial

p,

Termt);};Readingand

Writing

Polynomialsprint

Polynomialvoid

Polynomial::

print(

)

const/*

Post:ThePolynomialis

printedto

cout.

*/{Node

*print_node

=

front;bool

first_term

=

true;while

(print_node

!=

NULL)

{Term&print_term

=

print_node->entry;if

(first_term)

{

//

In

this

case,

suppress

printing

an

initial‘+’.first_term

=

false;if

(print_term.coefficient

<

0)cout

<<

"-";}Readingand

Writing

Polynomialselse

if

(print_term.coefficient

<

0)

cout

<<

"

-

";else

cout

<<

"

+

";double

r

=

(print_term.coefficient

>=

0)?

print_term.coefficient

:

-(print_term.coefficient);if

(r

!=

1)

cout

<<

r;if

(print_term.degree

>

1)

cout

<<

"

X?"

<<

print_term.degree;if

(print_term.degree

==

1)

cout

<<

"

X";if

(r

==

1

&&

print_term.degree

==

0)

cout

<<

"

1";print_node=print_node->next;}if

(first_term)cout

<<

"0";

//

Print

0

for

an

emptyPolynomial.cout

<<

endl;}Readingand

Writing

Polynomialsread

Polynomialvoid

Polynomial

::

read(

)/*

Post:ThePolynomialis

readfrom

cin.

*/{clear(

);double

coefficient;int

last_exponent,

exponent;bool

first_term

=

true;cout

<<

"Enter

the

coefficients

and

exponents

for

the

polynomial,

"<<

"one

pair

per

line.

Exponents

must

be

in

descending

order."

<<

endl<<

"Enter

a

coefficient

of

0

oran

exponent

of

0

to

terminate."

<<

endl;do{cout

<<

"coefficient?

"

<<

flush;cin

>>coefficient;if

(coefficient

!=

0.0)

{cout

<<

"exponent?

"

<<

flush;cin

>>

exponent;Readingand

Writing

Polynomialsif

((!first_term

&&

exponent

>=

last_exponent)

||

exponent

<

0)

{exponent

=

0;cout

<<

"Bad

exponent:

Polynomial

terminates

without

its

lastterm."<<

endl;}else

{Term

new_term(exponent,

coefficient);append(new_term);first_term

=

false;}last_exponent

=exponent;}}

while

(coefficient

!=

0.0

&&

exponent

!=

0);}Addition

of

Polynomials（多項式相加）void

Polynomial

::

equals_sum(Polynomial

p,

Polynomial

q)/*

Post:

ThePolynomial

object

is

reset

as

the

sum

of

the

twoparameters.*/{clear(

);while

(!p.empty(

)

||

!q.empty(

))

{Term

p_term,

q_term;if

(p.degree(

)

>

q.degree(

))

{p.serve_and_retrieve(p_term);append(p_term);}Addition

of

Polynomials（多項式相加）else

if

(q.degree(

)

>

p.degree(

))

{q.serve_and_retrieve(q_term);append(q_term);}else

{p.serve_and_retrieve(p_term);q.serve_and_retrieve(q_term);if

(p_term.coefficient

+