?? duoxs.cpp
字號:
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#define ERROR 0
#define OK 1
static n=0;
char vari_name[7]={' ','L','M','N','X','Y','Z'};
//變元名稱；從“1”號單元開始，“0”號單元不使用；全局變量
//代表你可以使用上面這些變元構造你的m元多項式
//下標越小，代表變元的層次越高
typedef int Status;
typedef int ElemTag;//標識結點類型
typedef struct MPNode{
ElemTag tag;//區分原子結點和表結點；
//tag=1,表示是表結點（即系數是另一個變元的多項式）；
//tag=0,表示是原子結點（即系數是一個常數）
int exp ; //指數域
union{
float coef;//系數域
struct MPNode *hp;//表結點的表頭指針
};
struct MPNode *tp;//相當于線性鏈表的next，指向下一個元素結點，即一元多項式的下一項
}MPNode,*UPList,*MPList;//MPNode 代表“m元多項式的廣義表類型”的結點結構；
//MPList 指向“m元多項式的廣義表”的表頭結點
//UPList 指向“m元多項式的廣義表”的每一層上的表頭結點
//其實“m元多項式廣義表”的每一層又可看作是該層的主變元的“一元多項式”）
//具體說明：
//①m元多項式的廣義表類型帶一個“表頭結點”，這個表頭結點的exp域在這里標識這個m元多項式的變元的個數；
//②廣義表的每一層也帶一個“表頭結點”，這個表頭結點的exp域在這里標識這一層的“主變元”（即這一層的第一變元）
//在變元名稱數組vari_name[ ]上的下標
int Locate(char vari){//返回變元vari在數組vari_name[ ]上的下標
int i=1;
while(i<=6 && vari_name[i]!=vari)
i++;
if(i>6)
i=0;//找不到這個變元
return i;
}//Locate
Status MakeUPList(UPList *upl,float coef,int num,...){
//對給定的一個包含num個變元的“項”（例如："coef,2,e1,e2" 表示一個這樣的項
//“這個項包含2個變元，這個項的系數是coef,這個項的第一變元的指數是e1,
//第二變元的指數是e2 ")構造一個UPList類型的廣義表,并由upl所指向的“表頭指針”返回這個廣義表。
//關于可變參數"..."的格式說明：
//例如："float,int,char,int,char,int" 表示這個項含有2個變元，2個char分別是兩個變元的名稱，
// 每個char之后的int就是這個變元的指數（第一個int代表變元的個數）,這個項的系數是float .
// 注意：對于一個常數，也應該指明它的變元（可以是任一個），且應該指定這個變元的指數為0,
// 即要求這里的num總是不小于1的。
// 注意：輸入多個變元時，按變元的層次級別，由高至低排列；變元的層次級別見 vari_name[ ] 數組
if(upl==NULL || num<1)
return ERROR;//參數非法
va_list ap;
va_start(ap,num);//讓ap指向可變參數列表中的第一個參數
UPList *pph; //p是指向“表頭指針”的“指針”
pph=upl; //初始化
MPNode *pnode; //指向表結點的指針
int i;//作計數之用
for(i=1;i<=num;i++){
if(!((*pph)=(UPList)malloc(sizeof(MPNode)))) return ERROR;
if(!(pnode=(MPNode *)malloc(sizeof(MPNode)))) return ERROR;
(*pph)->tag=1;
(*pph)->exp=Locate(va_arg(ap,char));
(*pph)->hp=NULL;
(*pph)->tp=pnode;
//該層上的表頭結點構造完畢
pnode->exp=va_arg(ap,int);
if(i<num) {
pnode->tag=1;
pph=&(pnode->hp);
}else{
pnode->tag=0;
pnode->coef=coef;
}//else
pnode->tp=NULL;
//表結點構造完畢
}//for
return OK;
}//MakeUPList
Status PutUPList(UPList ph)
{//第一種輸出方式：防照輸出“以二元組單鏈表表示的一元多項式”時的方式，以廣義表的字符串書寫形式輸出m元多項式
// 三元組（系數，變量名稱，指數），其中系數也可以是一個多項式。
//
//第二種輸出方式(即去掉while語句之前和之后的 printf("("); 語句，下面使用的輸出方式即是這種了）：
// 以一個括號代表一層，括號里面：
// 倒數第2項一定是變元的名稱
// 倒數第1項一定是該變元的指數
// 前面所有的項相加后的多項式，即為這個變元的系數
// 最外一層是沒有括號的，代表沒有變元，所以這些項相加就是完整的多項式了
char vari;//保存屬于該層的變元名稱
vari=vari_name[ph->exp];
MPNode *p;//指向表結點
p=ph->tp;
while(p!=NULL) {
if(p->tag==0) {//是原子結點
printf("(%.1f,%c,%d)",p->coef,vari,p->exp);
} else{
printf("(");
PutUPList(p->hp);
printf(",%c,%d)",vari,p->exp );
}//else
p=p->tp;
if(p!=NULL)
printf(",");
}//while
return OK;
printf("\n");
}//PutUPList
Status AddMPoly(UPList phA,UPList phB){
//phA和phB分別是兩個m元多項式的表頭指針，這兩個m元多項式所含變元的個數不一定相同；
//仿照求“以二元組單鏈表方式表示的一元多項式”相加時的方法，求兩個m元多項式的和
//結果用原來兩個m元多項式的儲存空間儲存
//結果以phA所指向的表頭結點返回（要注意的）
if(phA==NULL || phB==NULL) return ERROR;//參數非法，入口斷言
if(phA->exp<phB->exp){
//phA多項式的主變元層次級別“高于”phB多項式的主變元層次級別；將phB多項式做升元處理
UPList pheadno;//新建一個表頭指針
MPNode *plistno;//新建表結點指針
if(!(pheadno=(UPList)malloc(sizeof(MPNode)))) return ERROR;
if(!(plistno=(MPNode *)malloc(sizeof(MPNode)))) return ERROR;
pheadno->tag=1;
pheadno->exp=phA->exp;
pheadno->hp=NULL;
pheadno->tp=plistno;
//頭結點構造完畢
plistno->tag=1;
plistno->exp=0;
plistno->hp=phB;
plistno->tp=NULL;
//表結點構造完畢
phB=pheadno;
//phB多項式升元處理完畢
AddMPoly(phA,phB);
}//if(phA->exp<phB->exp)
else if(phA->exp>phB->exp){
//phA多項式的主變元層次級別“低于”phB多項式的主變元層次級別；將phA多項式做升元處理
UPList pheadno;//新建一個表頭指針
MPNode *plistno;//新建表結點指針
if(!(pheadno=(UPList)malloc(sizeof(MPNode)))) return ERROR;
if(!(plistno=(MPNode *)malloc(sizeof(MPNode)))) return ERROR;
pheadno->tag=1;
pheadno->exp=phA->exp;
pheadno->hp=NULL;
pheadno->tp=phA->tp;
//頭結點構造完畢,其實是復制一個phA所指向的表頭結點
plistno->tag=1;
plistno->exp=0;
plistno->hp=pheadno;
plistno->tp=NULL;
//表結點構造完畢
phA->exp=phB->exp;
phA->tp=plistno;
//phA多項式升元處理完畢
AddMPoly(phA,phB);
}//else if(phA->exp>phB->exp)
else {
//phA多項式的主變元層次級別與phB多項式的主變元層次級別相同
MPNode *pa,*pb,*pre,*ptemp;
//pa指向phA多項式中當前比較的結點，pre指向pa所指結點的前驅結點
//pb指向phB多項式中當前比較的結點;ptemp指針是作修改指針時之用的。
pa=phA->tp;//初始化，指向多項式的第一個結點
pre=phA;//初始化，指向phA多項式的表頭結點
pb=phB->tp;//初始化，指向多項式的第一個結點
while(pa!=NULL && pb!=NULL){
//比照求“一元多項式相加”時的方法處理，采取逐項相加
//注意：多項式各項的排列方式是先按第一變元（即最高層次變元）的冪次降冪排列，然后按第
//二變元的冪次降冪排列，依此類摔推。
if(pa->exp>pb->exp){
n++;
printf("\nn=%d pa->exp>pb->exp \n",n);
printf("\nvari=%c phA->tp->tag=%d \n",vari_name[phA->exp],phA->tp->tag );
pre=pa;
pa=pa->tp;
}//if(pa->exp>pb->exp)
else if(pa->exp<pb->exp){
ptemp=pb->tp;
pre->tp=pb;
pb->tp=pa;
pre=pb;
pb=ptemp;
}//else if(pa->exp<pb->exp)
else if(pa->tag==0 && pb->tag==0){
// pa->exp=pb->exp 且 pa和pb所指向的結點都是原子結點，即系數是常數
if(pa->coef +pb->coef==0){
//要刪除pa當前所指向的結點
ptemp=pa;
pre->tp=pa->tp;
pa=pa->tp;
free(ptemp);
pb=pb->tp;
}//if(pa->coef +pb->coef==0)
else{
//更新pa所指向的結點的值
pa->coef+=pb->coef;
pre=pa;
pa=pa->tp;
pb=pb->tp;
}//else 更新pa所指向的結點的值
}//else if(pa->tag==0 && pb->tag==0)
else if(pa->tag ==0 && pb->tag ==1) {
// pa->exp=pb->exp 且 pa所指結點是原子結點（即系數是常數）而pb所指結點是表結點（即系數是另一變元的多項式）
//構造一個常數多項式，這個常數即是pa所指結點的系數域，這個常數多項式的主變元是pb所指結點的系數子表的主變元
//求這個常數多項式與pb系數子表的多項式的和，并將結果返回給pa的hp域。
UPList pheadno;//新建一個表頭指針
MPNode *plistno;//新建一個表結點指針
if(!(pheadno=(UPList)malloc(sizeof(MPNode)))) return ERROR;
if(!(plistno=(MPNode *)malloc(sizeof(MPNode)))) return ERROR;
pheadno->tag=1;
pheadno->exp=pb->hp->exp;
pheadno->hp=NULL;
pheadno->tp=plistno;
//表頭結點構造完畢
plistno->tag=0;
plistno->exp=0;
plistno->coef=pa->coef;
plistno->tp=NULL;
//表結點構造完畢
AddMPoly(pheadno,pb->hp);
printf("PutUPList(pheadno) \n");
PutUPList(pheadno);
printf("\n");
pa->tag=1;
pa->hp=pheadno;
pre=pa;
pa=pa->tp;
pb=pb->tp;
}//else if(pa->tag ==0 && pb->tag ==1)
else if(pa->tag==1 && pb->tag==0){
//處理方法比照上面
UPList pheadno;//新建一個表頭指針
MPNode *plistno;//新建一個表結點指針
if(!(pheadno=(UPList)malloc(sizeof(MPNode)))) return ERROR;
if(!(plistno=(MPNode *)malloc(sizeof(MPNode)))) return ERROR;
pheadno->tag=1;
pheadno->exp=pa->hp->exp;
pheadno->hp=NULL;
pheadno->tp=plistno;
//表頭結點構造完畢
plistno->tag=0;
plistno->exp=0;
plistno->coef=pb->coef;
plistno->tp=NULL;
//表結點構造完畢
AddMPoly(pa->hp,pheadno);
pre=pa;
pa=pa->tp;
pb=pb->tp;
}//else if(pa->tag=1 && pb->tag==0)
else{
//pa和pb所指結點的系數都是子表，即是另一個變元的多項式
AddMPoly(pa->hp ,pb->hp);
if(pa->hp->tp==NULL){
//相當于系數相加等于0,則刪除pa所指結點
ptemp=pa;
pre->tp=pa->tp;
pa=pa->tp;
free(ptemp);
pb=pb->tp;
}//if(pa->hp->tp==NULL)
else if(pa->hp->tp->tag ==0 && pa->hp->tp->exp==0){
//相當于相加得到一個常數
pa->tag=0;printf("\n-1-\n");
ptemp=pa->hp ;
pa->coef=ptemp->tp->coef ;
pre=pa;
pa=pa->tp;
pb=pb->tp;
free(ptemp);
}else{//兩個系數子表相加結果仍是一個子表
pre=pa;
pa=pa->tp;
pb=pb->tp;
}//else 兩個系數子表相加結果仍是一個子表
}//else pa和pb所指結點的系數都是子表，即是另一個變元的多項式
}//while
if(pa==NULL && pb==NULL){
pre->tp=NULL;
}//if(pb!=NULL)
else if(pa==NULL && pb!=NULL){
pre->tp=pb;
}//else if
}//else phA多項式的主變元層次級別與phB多項式的主變元層次級別相同
if(phA->tp!=NULL && phA->tp->exp==0){
//相當于變元個數減少了
printf("\nn=%d phA->tp!=NULL && phA->tp->exp==0 相當于變元個數減少了 \n",n);
UPList newp;
newp=phA ;//循環初始化
while(newp->tp->exp==0 && newp->tp->tag!=0)
newp=newp->tp->hp ;
phA->exp=newp->exp;
phA->tp=newp->tp;
}//
return OK;
}//AddMPoly
void main(){
UPList UPL_1;//表頭指針
UPList UPL_2;//表頭指針
UPList Polytemp;//表頭指針，輔助變量，用于構造多項式中的一個項時用的，并將構造出來的這個項加到某個多項式中
UPList *pph;
pph=&UPL_1;
MakeUPList(pph,2,1,'Y',2);//構造多項式UPL_1的第1項
pph=&Polytemp;
MakeUPList(pph,3,2,'X',2,'Z',1);//構造多項式UPL_1的第2項
AddMPoly(UPL_1,Polytemp);
MakeUPList(pph,1,3,'X',2,'Y',1,'Z',1);//構造多項式UPL_1的第3項
AddMPoly(UPL_1,Polytemp);
pph=&UPL_2;
MakeUPList(pph,-3,2,'X',2,'Z',1);//構造多項式UPL_2的第1項
pph=&Polytemp;
MakeUPList(pph,6,2,'X',2,'Y',3);//構造多項式UPL_2的第2項
AddMPoly(UPL_2,Polytemp);
printf("\nbefore add :\n多項式UPL_1＝");
PutUPList(UPL_1);
printf("\n多項式UPL_2＝");
PutUPList(UPL_2);
printf("\n");
AddMPoly(UPL_1,UPL_2);
printf("\nafter add :\n多項式UPL_1＝");
PutUPList(UPL_1);
printf("\n");
}//main
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -