polyeuclid.cpp

初学密码内容

/******多项式到目前为止功能汇总******/
/**在原有基础上加入模、求多项式公因式、求GF（p(x)）逆元等函数**/

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>

enum Error_code{success, fail, underflow, overflow};				//标志
typedef float Node_entry;
typedef float Stack_entry;
struct Node{							//结点结构
  Node_entry ne;						//ne为指数
  Node_entry nf;						//nf为系数
  Node *next;							//指向下结点的指针
  Node();
  Node(Node_entry item_ne, Node_entry item_nf, Node *add_on=NULL);
};

Node::Node()
{
 next=NULL;
}

Node::Node(Node_entry item_ne, Node_entry item_nf, Node *add_on)
{
 ne=item_ne;
 nf=item_nf;
 next=add_on;
}

/***一个功能超强的栈类（用链表实现）[主要为多项式服务]***/
class Stack{									
	public:
	 Stack();
	 ~Stack();
	 bool empty()const;							//判断栈是否为空
	 Node* gettopnode();						//获得链头指针
	 Error_code pop();							//弹出栈顶元素
	 Error_code top(Stack_entry &item_ne, Stack_entry &item_nf)const;	//获取栈顶元素
	 Error_code push(const Stack_entry &item_ne, const Stack_entry &item_nf);	//把元素加入栈
	 Stack& operator =(const Stack &original);	//重载运算符"="
	 void Readline(char *p);					//读取用户输入串p，并转化为多项式
	 void addstack(Stack &b);					//两个链(多项式)相加 this = this+b
	 void substack(Stack &b);					//两个链(多项式)相减 this = this-b
	 void mulstack(Stack &a, Stack &b);			//两个链(多项式)相乘 this = a*b
	 void pmodstack(int pmod);					//对多项式求模 this = this mod pmod
	 Error_code divstack(Stack &a, Stack &b);	//多项式相除 this = a/b 结果a为余数

	 /***所有带模函数不仅对于pmod = 2时成立，而且对于任正整数pmod也成立***/
	 Error_code divstack(Stack &a, Stack &b, int pmod);		//多项式带模相除 this = a/b mod pmod 结果a为余数
	 Error_code gcdstack_div(Stack &a, Stack &b, int pmod);	//求多项式a与b的公因式（模pmod）结果a为公因式
	 Error_code	PoExEuclid(Stack &m, Stack &b, int pmod);	//求GF（m(x)）中b的乘法逆元（带模pmod）
											
	 void show_Stack();							//遍历栈中所有元素（显示多项式）
	 void clear();								//把栈中所有元素清除
	private:
	 Node *top_node;							//栈顶指针
};

Stack::Stack()
{
    top_node=NULL;
}

Stack::~Stack()
{
    while(!empty())
    pop();
}

bool Stack::empty()const
{
  if(top_node == NULL) return true;
  return false;
}

Node* Stack::gettopnode()
{
	return top_node;
}


Error_code Stack::push(const Stack_entry &item_ne, const Stack_entry &item_nf)
{													//把结点（多项式的一项）加入栈
  Node *new_top=new Node(0, 0, top_node);			//预处理，先让top_node不为空	
  if(new_top == NULL) return overflow;
  top_node=new_top;

  Node *new_node=new Node(item_ne, item_nf);		//申请加入结点
  if(new_node == NULL) return overflow;				
  Node *pre = top_node;					
  Node *temp = top_node;
  temp = temp->next;
  while(temp != NULL){								//找适合位置加入（按指数从高到低排列多项式）	
      if(temp->ne < item_ne)						//已经找到，加入结点
       {
		pre->next = new_node;
		new_node->next = temp;
		pop();
		return success;
		}

      if(temp->ne==item_ne)							//找到指数相同的，作加法运算
		{
		 temp->nf = temp->nf + item_nf;
		 delete new_node;
		if(temp->nf==0)								//运算结果为0，删除该项
		{
			pre->next = temp->next;
			delete temp;
		}
	  pop();										//把预处理加入的垃圾元素弹出
	  return success;
	 }

	 pre = pre->next;
	 temp = temp->next;
   }
   pre->next = new_node;
   pop();
   return success;
}

Error_code Stack::pop()								//弹出栈顶元素
{
  Node *old_top = top_node;
  if(top_node == NULL) return underflow;
  top_node = old_top->next;
  delete old_top;
  return success;
}

Error_code Stack::top(Stack_entry &item_ne, Stack_entry &item_nf)const
{													//获取栈顶元素
  if(top_node == NULL) return underflow;
  item_ne = top_node->ne;
  item_nf = top_node->nf;
  return success;
}

Stack& Stack::operator = (const Stack &original)	//重载运算符"="
{
  while( !empty() ) pop();
  Node *new_top, *new_copy, *original_node=original.top_node;
  if(original_node == NULL) new_top = NULL;
  else{
     new_copy = new_top = new Node(original_node->ne, original_node->nf);
     while(original_node->next != NULL){
       original_node = original_node->next;
       new_copy->next = new Node(original_node->ne, original_node->nf);
       new_copy = new_copy->next;
     }
  }
  top_node = new_top;
  return *this;
}

void Stack::Readline(char *p)						//读取用户输入串p，并转化为多项式
{
  char temp[10];
  int j, t=0, s_ne=1, s_nf=1;

  for(int i=0; i<strlen(p); i++)
   {
     int sign=1;
     if(p[i] == '-')  sign = -1;
     if(p[i] == '+' || p[i] == '-')
      {  
		if(t == 0)  s_ne = 0;
		if(i != 0) push(s_ne, s_nf);
		i++;	 t=0;
		if(p[i] == 'x' || p[i] == 'X') {s_nf = sign*1; sign = 1;}
       }
	if(p[i] == 'x' || p[i] == 'X')  { i++; t = 1;}

    j=0;
    while((p[i]!='+') && (p[i]!='-') && (p[i]!='x') && (p[i]!='X') && (i<strlen(p)))
     {
      temp[j] = p[i];
      i++;  j++;
      }
     i--;
     if(j == 0) { temp[j] = '1'; j++; }
     temp[j] = '\0';
     if(t == 1)  s_ne=sign*atoi(temp);
     else  s_nf = sign*atoi(temp);
    }
     if(t == 0)  s_ne = 0;
     push(s_ne, s_nf);
}

void Stack::addstack(Stack &b)						//两个链(多项式)相加 this = this+b
{
  Node *t = b.top_node;
  while(t!=NULL){
    push(t->ne, t->nf);
    t=t->next;
    }
}

void Stack::substack(Stack &b)						//两个链(多项式)相减 this = this-b
{
  Node *t = b.top_node;
  while(t != NULL){
    push(t->ne, -(t->nf));
    t=t->next;
    }
}

void Stack::mulstack(Stack &a, Stack &b)			//两个链(多项式)相乘 this = a*b
{
  Node *t_a = a.top_node;
  Node *t_b = b.top_node;
  Stack_entry ttne,ttnf;
  while(t_b != NULL){
   while(t_a != NULL){
    ttne=(t_a->ne) + (t_b->ne);
    ttnf=(t_a->nf) * (t_b->nf);
	if(ttnf != 0)
		push(ttne, ttnf);
    t_a = t_a->next;
    }
   t_a = a.top_node;
   t_b = t_b->next;
   }
}

Error_code Stack::divstack(Stack &a, Stack &b)		//多项式相除 this = a/b 结果a为余数
{
  Stack_entry m_ne;
  float m_nf;
  Node *t_a = a.top_node;
  Node *t_b = b.top_node;
  if(t_b == NULL) return fail;
  while((t_a->ne) >= (t_b->ne)){
      m_ne = (t_a->ne) - (t_b->ne);
      m_nf = (t_a->nf)*1.0 / (t_b->nf)*1.0;
      push(m_ne, m_nf);
      while(t_b != NULL){
		a.push(t_b->ne+m_ne, -(t_b->nf*m_nf));
		t_b = t_b->next;
	}
      t_b = b.top_node;
      t_a = a.top_node;
      if(a.top_node == NULL) return success;
   }
   return success;
}

void Stack::pmodstack(int pmod)						//对多项式求模 this = this mod pmod
{													//即把多项式各项的系数模pmod
  Node *pre = top_node;
  Node *temp = top_node;
  if(temp == NULL)  return;
  int nfmod;
  while(temp != NULL)
   {
     nfmod = temp->nf;								//获取系数并对其模pmod
	 nfmod = (nfmod % pmod + pmod) % pmod;
	 temp->nf = nfmod;

	 if(temp->nf == 0)								//模求得可能为0，即应该删除此结点
	 {												//用pre记住此结点的前一结点
		 if(temp != top_node)	pre->next = temp->next;
		 else	top_node = NULL;
		 delete temp;								//删除结点
		 temp = pre;
	 }
	 if(temp != top_node) pre = pre->next;
     temp = temp->next;
   }
}
													 
Error_code Stack::divstack(Stack &a, Stack &b, int pmod)	//多项式带模相除 this = a/b mod pmod
{															//输出：this为商，参数a为余数
  int m_ne, m_nf;
  int ttne, ttnf; 
  a.pmodstack(pmod);
  b.pmodstack(pmod);
  Node *t_a = a.top_node;
  Node *t_b = b.top_node;
  if(t_b == NULL) return fail;

  while((t_a->ne) >= (t_b->ne)){							//求商的一项
      m_ne = (t_a->ne) - (t_b->ne);
      m_nf = (t_a->nf) / (t_b->nf);
	  if( t_b->nf * m_nf != t_a->nf )  return fail;			//此为适应pmod不为2时的情况（必须除尽）		
      push(m_ne, m_nf);

      while(t_b != NULL){									//把商的这一项乘上除数多项式
			ttne = t_b->ne + m_ne;
			ttnf = -(t_b->nf * m_nf);
			a.push(ttne, ttnf);								//并用初除数减去上面乘积结果
			a.pmodstack(pmod);
			t_b = t_b->next;
		}
      t_b = b.top_node;										//重新赋值，循环
      t_a = a.top_node;
      if(a.top_node == NULL) return success;
   }
   return success;
}

//欧几里德算法（多项式）									 //辗转相除法求最大公因数
Error_code Stack::gcdstack_div(Stack &a, Stack &b, int pmod) //输出：a为最大公因式
{
  Stack tt;
  Node *t_b = b.top_node;
  while(t_b != NULL &&t_b->nf != 0) 
  {															//求a / b mod pmod
	  if( tt.divstack(a, b, pmod) == success )				//tt为商, a为余数
	  {
		  tt.clear();
		  tt = a;											//交换被除数、除数
	      a = b;
	      b = tt;
		  t_b = b.top_node;
	  }
	  else return fail;
  }
  return success;
}
													//求GF（m(x)）中b的乘法逆元（带模pmod）
//扩展欧几里德算法（多项式）						//输入：多项式m必须比b阶数高
Error_code Stack::PoExEuclid(Stack &m, Stack &b, int pmod)
{													//输出：m为原m与原b的公因式，b为所求逆元
  Stack A[3], B[3], tB[3], T[3];					//带小写t开头的均用于暂存
  Stack Q, tt, tA2, tQ;
  Node *temp;

  A[0].push(0, 1);		A[1].push(0, 0); 	 A[2] = m;	//赋初值
  B[0].push(0, 0);		B[1].push(0, 1); 	 B[2] = b;
  b.clear();

  while(1)
	{
	    temp = B[2].top_node;
		if((temp == NULL) || (temp->nf == 0)) { m = A[2];  return fail; }	//没逆元，失败退出
		if((temp->ne == 0) && (temp->nf == 1))		//找到逆元
		{
			m = B[2];								//m为公因式
			B[1].pmodstack(pmod);					
			b = B[1];								//b为逆元
			return success; 
		}											//成功退出
		
		tA2 = A[2];
		tt.clear();
		tt.divstack(tA2, B[2], pmod);
		Q = tt;										//求Q Q = A[2]/B[2] mod pmod

		for(int i=0; i<3; i++)
		{
			tB[i] = B[i];
			tt.clear();
			tQ = Q;
			tt.mulstack(tQ, tB[i]);					//tt = tQ*tB[i] mod pmod
			tt.pmodstack(pmod);
			A[i].substack(tt);						//A[i] = A[i] - tt	mod pmod
			A[i].pmodstack(pmod);
			T[i] = A[i];							//交换A[i]与B[i]
			A[i] = B[i];							
			B[i] = T[i];							
		}
	}

}

void Stack::show_Stack()							//遍历栈中所有元素（显示多项式）
{
  Node *temp = top_node;
  if((temp == NULL) || (temp->nf == 0)) {cout<<"0"; return;}
  while(temp != NULL)
   {
     if(temp->nf == 0) return;
     if(temp != top_node && temp->nf > 0) cout<<"+";
     if(temp->nf == -1) { cout<<"-"; if(temp->ne == 0) cout<<"1"; }
     else{ if((temp->nf!=1) || ((temp->ne==0) && (temp->next==NULL))) cout<<temp->nf; }
     if(temp->ne != 0)
      {
       cout<<"x";
       if(temp->ne != 1) cout<<temp->ne;
       }
     temp = temp->next;
   }
}

void Stack::clear() { while(!empty()) pop();}		//删除栈中所有元素

void main()
{
  Stack s_a,s_b,s_c,s_r,s_t, tt;
  const int MAXLINE=100;
  int k=0;
  char data_a[MAXLINE];
  char data_b[MAXLINE];
  cout<<"\n******正在进行多项式显示程序******";
  cout<<"\n例: 3x2-1 表示 3*x*x-1"<<endl;
  cout<<"\n请输入多项式A: ";
  cin>>data_a;
  s_a.Readline(data_a);

  cout<<"\n请输入多项式B: ";
  cin>>data_b;
  s_b.Readline(data_b);
/*
  s_c=s_a;
  s_c.addstack(s_b);
  cout<<endl<<"A+B=";
  s_c.show_Stack();
  cout<<endl;

  s_c=s_a;
  s_c.substack(s_b);
  cout<<endl<<"A-B=";
  s_c.show_Stack();
  cout<<endl;

  s_c.clear();
  s_c.mulstack(s_a,s_b);
  cout<<endl<<"A*B=";
  s_c.show_Stack();
  cout<<endl;

  s_c.clear();
  s_r=s_a;                        //s_c :xiang  s_r:yushu;
  s_c.divstack(s_r,s_b);
  cout<<endl<<"A/B=";
  //cout<<endl<<"Result=";
  s_c.show_Stack();
  cout<<endl<<"A%B=";
  s_r.show_Stack();
  cout<<endl;
*/
  cout<<endl<<"---欧几里德算法求最大公因数---"<<endl;
  s_c.clear();
  s_r=s_a;
  s_t=s_b;
  s_c.gcdstack_div(s_r, s_t, 2);
  
  cout<<"  Gcd(A, B)_Eu = ";
  s_r.show_Stack();
  cout<<endl<<endl;


  cout<<endl<<"---扩展欧几里德算法---"<<endl;
  s_c.clear();
  s_r=s_a;
  s_t=s_b;
												//如果B比A阶数要高，则交换A，B
    if(s_r.gettopnode()->ne < s_t.gettopnode()->ne)
	{	tt = s_r; s_r = s_t; s_t = tt; tt.clear(); 
		cout<<"-在GF（B(x)）中求A(x)的乘法逆元-"<<endl;
		k=1;
		}
	else cout<<"-在GF（A(x)）中求B(x)的乘法逆元-"<<endl;

  s_c.PoExEuclid(s_r, s_t, 2);
  
  cout<<"  Gcd(A,B)_ExEu = ";						//用扩展欧几里德求出的逆元
  s_r.show_Stack();
  cout<<endl;

  if(k==1)	cout<<"  A的逆元 = ";					//B阶比A高
  else		cout<<"  B的逆元 = ";				
  s_t.show_Stack();									//若输出为0，即表示没逆元

  cout<<endl<<endl<<"Press any key to Quit"<<endl;
  getch();

}