08年9月入学，12年7月毕业，结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾，索引参见：http://www.jb51.cc/article/p-srsfcefa-vo.html
链式队列各种基本运算算法的实现
队列是一种先进先出的线性表。就如同现实中的排队，先来的先服务。通过基本的append（）将元素加入队列，serve（）将元素移出队列。
链式队列是不同于循环数组的另一种队列的实现形式。队列中的元素以Node形式存储。节点Node中存有此节点存于队列中的元素以及指向下一个元素的指针。链式队列的需要保存指向队头和队尾的指针的数据成员。同链式栈的实现一样，链式队列的实现尤其重点和难点的部分是编写自己的析构函数，拷贝构造函数和重载赋值运算符。
链式队列是不同于循环数组的另一种队列的实现形式。队列中的元素以Node形式存储。节点Node中存有此节点存于队列中的元素以及指向下一个元素的指针。链式队列的需要保存指向队头和队尾的指针的数据成员。同链式栈的实现一样，链式队列的实现尤其重点和难点的部分是编写自己的析构函数，拷贝构造函数和重载赋值运算符。
【实验说明】
我选择的题目是书中应用程序多项式的编写。1.链式队列中的元素以节点的形式存储，首先编写结构Node的定义和实现。
2.编写链式队列的定义和实现。队列中的数据成员是指向队头的指针*font以及指向队尾的指针*rear。成员函数有最基本的操作appent(),serve(),retireve()分别用以相队列中填入、移出元素以及得到队头的元素。empty（）用以判断队列是否为空。更重要的是编写队列自己的析构函数~Queue(),拷贝构造函数Queue(const Queue &original);以及重载赋值运算符void operator=(const Queue &original);
3.从队列中继承一个新的类Extended_queue，添加一些新的功能——size()得到队列大小，clear()清空队列，serve_and_retrieve()得到并移出队头的元素。
4.分析多项式中每一项既有系数又有指数。定义并实现一个新的结构Term用以表示多项式中的一项。Term中含有公有数据成员degree和coefficient。
5.因为多项式的特点，所以定义多项式类Polynomial为从类Extended_queue中派生出来的类。
并添加他自己的一些成员函数。print()打印多项式；equals_sum()求两个多项式的和，equals_difference()求两个多项式的差；degree()得到多项式最高项的系数。
6.实现多项式类。
7.编写主函数简单实现并测试多项式的运算。
【相关代码】
linked_queue.h
typedef Term Queue_entry;
class Queue
{
public:
Queue();
bool empty()const;
Error_code append(const Queue_entry &item);
Error_code serve();
Error_code retireve(Queue_entry &item)const;
~Queue();
Queue(const Queue &original);
void operator=(const Queue &original);
protected:
Node *front,*rear;
};
class Extended_queue: public Queue
{
public:
//bool full()const;
int size()const;
void clear();
Error_code serve_and_retrieve(Queue_entry &item);
};linked_queue.cpp
Queue::Queue()
{
front=rear=NULL;
}
bool Queue::empty()const{
if(front==NULL)
return true;
else
return false;
}
Error_code Queue::append(const Queue_entry &item)
{
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;
}
Error_code Queue::serve()
{
if(front==NULL)
return underflow;
Node *old_front=front;
front=old_front->next;
if(front==NULL)
rear=NULL;
delete old_front;
return success;
}
Error_code Queue::retireve(Queue_entry &item)const{
if(empty())
return underflow;
else{
item=front->entry;
return success;
}
}
Queue:: ~Queue()
{
while(!empty())
serve();
}
void Queue::operator =(const Queue &original)
{
Node *new_rear,*new_front,*new_copy,*original_node=original.front;
if(original_node==NULL){
new_front=new_rear=NULL;
}
else{
new_copy=new_front=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;
}
original_node=original.rear;
new_rear=new Node(original_node->entry);
new_rear->next=NULL;
}
while(!empty())
serve();
front=new_front;
rear=new_rear;
}
Queue::Queue(const Queue &original)
{
Node *new_copy,*original_node=original.front;
if(original_node==NULL)
front=rear=NULL;
else{
front=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;
}
original_node=original.rear;
rear=new_copy=new Node(original_node->entry);
}
}
int Extended_queue::size()const
{
Node *window=front;
int count=0;
while(window != NULL){
window=window->next;
count++;
}
return count;
}
void Extended_queue::clear()
{
while(!empty())
serve();
}
Error_code Extended_queue::serve_and_retrieve(Queue_entry &item)
{
if(front==NULL)
return underflow;
Node *old_front=front;
front=old_front->next;
item=old_front->entry;
if(front==NULL)rear=NULL;
delete old_front;
return success;
}Polynomial.h
class Polynomial: private Extended_queue
{
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,Term t);
};Polynomial.cpp
void Polynomial::print() const
{
Node *print_node=front;
bool first_term=true;
while(print_node != NULL){
Term &print_term=print_node->entry;
if(first_term){
first_term=false;
if(print_term.coefficient<0)
cout<<" - ";
}
else 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";
cout<<endl;
}
void Polynomial::read()
{
clear();
double coefficient;
int last_exponent,exponent;
bool first_term=true;
cout<<"Enter the coffiecients and exponents for the polynomial,"
<<"one pair per line. Exponents must be in descending order."<<endl
<<"Enter a coefficient of 0 or exponent of 0 to termnimante."<<endl;
do{
cout<<"coefficient?"<<flush;
cin>>coefficient;
if(coefficient!=0.0){
cout<<"exponent?"<<flush;
cin>>exponent;
if((!first_term&&exponent>=last_exponent)||exponent<0){
exponent=0;
cout<<"Bad exponent: Polynomial terminates without its last term."
<<endl;
}
else{
Term new_term(exponent,coefficient);
append(new_term);
first_term=false;
}
last_exponent=exponent;
}
}while(coefficient!=0.0&&exponent!=0);
}
void Polynomial::equals_sum(Polynomial p,Polynomial q)
{
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);
}
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+q_term.coefficient!=0){
Term answer_term(p_term.degree,p_term.coefficient+q_term.coefficient);
append(answer_term);
}
}
}
}
void Polynomial::equals_difference(Polynomial p,Polynomial q)
{
Polynomial neg_q;
while(!q.empty()){
Term temp;
q.serve_and_retrieve(temp);
temp.coefficient=-1*temp.coefficient;
neg_q.append(temp);
}
equals_sum(p,neg_q);
}
int Polynomial::degree()const
{
if(empty())
return -1;
Term lead;
retireve(lead);
return lead.degree;
}
【过程记录】
实验截图：
【结果分析】
1.同链式栈一样，链式队列中以节点的形式存储队列中的元素，所以他的实现与栈有很多相似之处。所不同的是队列中元素操作原则是“先进先出”，不同于栈的“后进先出”，所以类Queue中需要分别保存指向队列首元素和尾元素地址的指针。
2.同样，链式队列要注意编写自己的析构函数，拷贝构造函数和重载赋值运算符。
3.通过对多项式特点的分析，我们从拓展队列Extended_queue中派生出类Polynomial，继承是c++中非常重要的性质，可以简化我们很多程序的编写。
4.多项式中每一项的元素包括系数和指数两部分，所以我们编写了结构Term用以表示多项式中的每一项，此时类增多，要时刻保持清醒的头脑了解他们的关系，Term是存储于节点中的entry部分，不同类的存储我们没有用类模板，而是使用typedef，这就要很仔细的定义他们的类型，不然很容易出现函数调用中类型不能转换的错误。
2.同样，链式队列要注意编写自己的析构函数，拷贝构造函数和重载赋值运算符。
3.通过对多项式特点的分析，我们从拓展队列Extended_queue中派生出类Polynomial，继承是c++中非常重要的性质，可以简化我们很多程序的编写。
4.多项式中每一项的元素包括系数和指数两部分，所以我们编写了结构Term用以表示多项式中的每一项，此时类增多，要时刻保持清醒的头脑了解他们的关系，Term是存储于节点中的entry部分，不同类的存储我们没有用类模板，而是使用typedef，这就要很仔细的定义他们的类型，不然很容易出现函数调用中类型不能转换的错误。
