《數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、/*
數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)
P42-43
編譯環(huán)境：Dev-C++ 4.9.9.2
日期：2011年2月10日
*/
#include
#include
#include
// 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)
typedef struct // 項的表示,多項式的項作為LinkList的數(shù)據(jù)元素
{
float coef; // 系數(shù)
int expn; // 指數(shù)
}term, ElemType;
//
2、 兩個類型名:term用于本ADT,ElemType為LinkList的數(shù)據(jù)對象名
typedef struct LNode // 結(jié)點類型
{
ElemType data;
struct LNode *next;
}LNode,*Link,*Position;
typedef struct _LinkList // 鏈表類型
{
Link head,tail; // 分別指向線性鏈表中的頭結(jié)點和最后一個結(jié)點
int len; // 指示當前線性鏈表中數(shù)據(jù)元素的個數(shù)
}LinkList;
typedef LinkList polynomia
3、l;
#define DestroyPolyn DestroyList
#define PolynLength ListLength
// 已知p指向線性鏈表L中的一個結(jié)點，返回p所指結(jié)點的直接前驅(qū)的位置
// 若無前驅(qū)，則返回NULL
Position PriorPos(LinkList L,Link p)
{
Link q;
q=L.head->next;
if(q==p) // 無前驅(qū)
return NULL;
else
{
while(q->next!=p) // q不是p的直接前驅(qū)
q=q->next;
r
4、eturn q;
}
}
// 若升序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素，則q指示L中
// 第一個值為e的結(jié)點的位置，并返回1；否則q指示第一個與e滿足判定函數(shù)
// compare()取值>0的元素的前驅(qū)的位置。并返回0。（用于一元多項式）
int LocateElemP(LinkList L,ElemType e,Position *q,
int(*compare)(ElemType,ElemType))
{
Link p=L.head,pp;
do
{
pp=p;
p=p->next;
}while
5、(p&&(compare(p->data,e)<0)); // 沒到表尾且p->data.expndata,e)>0) // 到表尾或compare(p->data,e)>0
{
*q=pp;
return 0;
}
else // 找到
{
*q=p;
return 1;
}
}
// h指向L的一個結(jié)點，把h當做頭結(jié)點，刪除鏈表中的第一個結(jié)點并以q返回。
// 若鏈表為空(h指向尾結(jié)點)，q=NULL，返回0
int DelFirst(LinkList *L,Link
6、h,Link *q)
{
*q=h->next;
if(*q) // 鏈表非空
{
h->next=(*q)->next;
if(!h->next) // 刪除尾結(jié)點
(*L).tail=h; // 修改尾指針
(*L).len--;
return 1;
}
else
return 0; // 鏈表空
}
// 分配由p指向的值為e的結(jié)點，并返回1；若分配失敗。則返回0
int MakeNode(Link *p,ElemType e)
{
*p = (Link)malloc(sizeof(LNode));
7、//動態(tài)分配一個Link空間
if(!*p)
return 0;
(*p)->data = e; // 賦值
return 1;
}
// 釋放p所指結(jié)點
void FreeNode(Link *p)
{
free(*p); //老規(guī)矩，先釋放存儲空間，然后置空
*p=NULL;
}
// h指向L的一個結(jié)點，把h當做頭結(jié)點，將s所指結(jié)點插入在第一個結(jié)點之前
// 頭結(jié)點沒有數(shù)據(jù)域，而第一個結(jié)點是h->next
int InsFirst(LinkList *L,Link h,Link s)
{
s->next = h->next;
8、
h->next=s;
if(h==(*L).tail) // 如果h指向尾結(jié)點
(*L).tail=h->next; // 修改尾指針
(*L).len++;
return 1;
}
// 按有序判定函數(shù)compare()的約定，將值為e的結(jié)點插入或合并到升序
// 鏈表L的適當位置
int OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term))
{
Position q,s;
if(LocateElemP(*L,e,&q,compare)) // L中存在該指數(shù)項
9、
{
q->data.coef+=e.coef; // 改變當前結(jié)點系數(shù)的值
if(!q->data.coef) // 系數(shù)為0
{
// 刪除多項式L中當前結(jié)點
s = PriorPos(*L,q); // s為當前結(jié)點的前驅(qū)
if(!s) // q無前驅(qū)
s=(*L).head;
DelFirst(L,s,&q);
FreeNode(&q);
}
return 1;
}
else // 生成該指數(shù)項并插入鏈表
if(MakeNode(&s,e)) // 生成結(jié)點成功
{
10、
InsFirst(L,q,s);
return 1;
}
else // 生成結(jié)點失敗
return 0;
}
// 依a的指數(shù)值<、=或>b的指數(shù)值，分別返回-1、0或+1
// CreatPolyn()的實參
int cmp(term a,term b)
{
if(a.expn==b.expn)
return 0;
else
return (a.expn-b.expn)/abs(a.expn-b.expn);
}
// 構(gòu)造一個空的線性鏈表
int InitList(LinkList *L)
{
11、 Link p;
p=(Link)malloc(sizeof(LNode)); // 生成頭結(jié)點
if(p)
{
p->next=NULL;
//將頭尾結(jié)點都分配好，并將其下一結(jié)點置空
(*L).head=(*L).tail=p;
(*L).len=0; //初始為0
return 1;
}
else // 分配失敗返回
return 0;
}
// 算法2.22 P42
// 輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P
void CreatPolyn(polynomial *P,int m)
{
Posi
12、tion q,s;
term e;
int i;
InitList(P);
printf("請依次輸入%d個系數(shù)，指數(shù)：（空格）\n",m);
for(i=1;i<=m;++i)
{
// 依次輸入m個非零項（可按任意順序）
scanf("%f%d",&e.coef,&e.expn);
// 當前鏈表中不存在該指數(shù)項,cmp是實參
if(!LocateElemP(*P,e,&q,cmp))
if(MakeNode(&s,e)) // 生成結(jié)點并插入鏈表
InsFirst(P,q,s);
}
}
//
13、 返回線性鏈表L中頭結(jié)點的位置
Position GetHead(LinkList L)
{
return L.head;
}
// 已知p指向線性鏈表L中的一個結(jié)點，返回p所指結(jié)點的直接后繼的位置
// 若無后繼，則返回NULL
Position NextPos(Link p)
{
return p->next;
}
// 已知p指向線性鏈表中的一個結(jié)點，返回p所指結(jié)點中數(shù)據(jù)元素的值
ElemType GetCurElem(Link p)
{
return p->data;
}
// 將指針s(s->data為第一個數(shù)據(jù)元素
14、)所指(彼此以指針相鏈,以NULL結(jié)尾)的
// 一串結(jié)點鏈接在線性鏈表L的最后一個結(jié)點之后,并改變鏈表L的尾指針指向新
// 的尾結(jié)點
int Append(LinkList *L,Link s)
{
int i=1; //記錄s為頭的串結(jié)點個數(shù)
(*L).tail->next=s; //尾結(jié)點指向s
while(s->next)
{
s=s->next;
i++;
}
(*L).tail=s;
(*L).len+=i;
return 1;
}
// 若線性鏈表L為空表，則返回1，否則返回0
int ListEmpty(L
15、inkList L)
{
if(L.len)
return 0;
else
return 1;
}
// 將線性鏈表L重置為空表（頭尾結(jié)點相同為空表），并釋放原鏈表的結(jié)
// 點空間，不釋放頭尾結(jié)點，只是置空而已
int ClearList(LinkList *L)
{
Link p,q;
if((*L).head!=(*L).tail)// 不是空表
{
p=q=(*L).head->next;
(*L).head->next=NULL;
while(p!=(*L).tail)
{
p=q->next;
16、 free(q);
q=p;
}
free(q);
(*L).tail=(*L).head;
(*L).len=0;
}
return 1;
}
// 銷毀線性鏈表L，L不再存在
int DestroyList(LinkList *L)
{
ClearList(L); // 清空鏈表（頭尾結(jié)點并沒有釋放）
FreeNode(&(*L).head); //再釋放頭尾結(jié)點
(*L).tail=NULL;
(*L).len=0;
return 1;
}
// 算法2.23 P43
// 多項式加法:Pa=
17、Pa+Pb,并銷毀一元多項式Pb
void AddPolyn(polynomial *Pa,polynomial *Pb)
{
Position ha,hb,qa,qb;
term a,b;
ha=GetHead(*Pa);
hb=GetHead(*Pb); // ha和hb分別指向Pa和Pb的頭結(jié)點
qa=NextPos(ha);
qb=NextPos(hb); // qa和qb分別指向Pa和Pb中當前結(jié)點（現(xiàn)為第一個結(jié)點）
while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa)
{ // Pa和Pb均非空且h
18、a沒指向尾結(jié)點(qa!=0)
a=GetCurElem(qa);
b=GetCurElem(qb); // a和b為兩表中當前比較元素
switch(cmp(a,b))
{
case -1:
ha=qa; // 多項式Pa中當前結(jié)點的指數(shù)值小
qa=NextPos(ha); // ha和qa均向后移一個結(jié)點
break;
case 0:
qa->data.coef+=qb->data.coef;
// 兩者的指數(shù)值相等,修改Pa當前結(jié)點的系數(shù)值
if(qa->data.coef==0) // 系數(shù)和為
19、0，則刪除多項式Pa中當前結(jié)點
{
DelFirst(Pa,ha,&qa);
FreeNode(&qa);
}
else
ha=qa;
DelFirst(Pb,hb,&qb);
FreeNode(&qb);
qb=NextPos(hb);
qa=NextPos(ha);
break;
case 1:
DelFirst(Pb,hb,&qb); // 多項式Pb中當前結(jié)點的指數(shù)值小
InsFirst(Pa,ha,qb);
ha=ha->next;
qb=Next
20、Pos(hb);
}
}
if(!ListEmpty(*Pb))
{
(*Pb).tail=hb;
Append(Pa,qb); // 鏈接Pb中剩余結(jié)點
}
DestroyPolyn(Pb); // 銷毀Pb
}
// 另一種多項式加法的算法:Pa=Pa+Pb,并銷毀一元多項式Pb
void AddPolyn1(polynomial *Pa,polynomial *Pb)
{
Position qb;
term b;
qb=GetHead(*Pb); // qb指向Pb的頭結(jié)點
qb=qb->next; // qb指
21、向Pb的第一個結(jié)點
while(qb)
{
b=GetCurElem(qb);
OrderInsertMerge(Pa,b,cmp);
qb=qb->next;
}
DestroyPolyn(Pb); // 銷毀Pb
}
// 一元多項式系數(shù)取反
void Opposite(polynomial Pa)
{
Position p;
p=Pa.head;
while(p->next)
{
p=p->next;
p->data.coef*=-1;
}
}
// 多項式減法:Pa=Pa-Pb,并銷毀一元多項式
22、Pb
void SubtractPolyn(polynomial *Pa,polynomial *Pb)
{
Opposite(*Pb);
AddPolyn(Pa,Pb);
}
// 多項式乘法:Pa=PaPb,并銷毀一元多項式Pb
void MultiplyPolyn(polynomial *Pa,polynomial *Pb)
{
polynomial Pc;
Position qa,qb;
term a,b,c;
InitList(&Pc);
qa=GetHead(*Pa);
qa=qa->next;
while(qa)
{
23、
a=GetCurElem(qa);
qb=GetHead(*Pb);
qb=qb->next;
while(qb)
{
b=GetCurElem(qb);
c.coef=a.coef*b.coef;
c.expn=a.expn+b.expn;
OrderInsertMerge(&Pc,c,cmp);
qb=qb->next;
}
qa=qa->next;
}
DestroyPolyn(Pb); // 銷毀Pb
ClearList(Pa); // 將Pa重置為空表
(*Pa).head=Pc.
24、head;
(*Pa).tail=Pc.tail;
(*Pa).len=Pc.len;
}
// 打印輸出一元多項式P
void PrintPolyn(polynomial P)
{
Link q;
q=P.head->next; // q指向第一個結(jié)點
printf(" 系數(shù) 指數(shù)\n");
while(q)
{
printf("%f %d\n",q->data.coef,q->data.expn);
q=q->next;
}
}
int main()
{
polynomial p,q;
int m;
25、
// 多項式相加
printf("兩個一元多項式相加\n");
//構(gòu)建一個多項式
printf("請輸入第一個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&p,m);
//構(gòu)建另一個多項式
printf("請輸入第二個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&q,m);
//多項式相加
AddPolyn(&p,&q);
printf("兩個一元多項式相加的結(jié)果：\n");
//打印多項式
PrintPolyn(p);
26、
// 使用另一種多項式相加的方法
printf("\n兩個一元多項式相加(另一種方法)\n");
printf("請輸入第三個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&p,m);
printf("請輸入第四個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&q,m);
// 多項式相加的另一種方法
AddPolyn1(&p,&q);
printf("兩個一元多項式相加的結(jié)果(另一種方法)：\n");
PrintPolyn(p);
//
27、多項式相減
printf("\n兩個一元多項式相減\n");
printf("請輸入第五個個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&p,m);
printf("請輸入第六個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&q,m);
// 多項式相減
SubtractPolyn(&p,&q);
printf("兩個一元多項式相減的結(jié)果：\n");
PrintPolyn(p);
//多項式相乘
printf("\n兩個一元多項式相乘\n");
28、 printf("請輸入第七個個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&p,m);
printf("請輸入第八個一元多項式的非零項的個數(shù)：");
scanf("%d",&m);
CreatPolyn(&q,m);
//多項式相乘
MultiplyPolyn(&p,&q);
printf("兩個一元多項式相乘的結(jié)果：\n");
PrintPolyn(p);
//銷毀多項式
DestroyPolyn(&p);
DestroyPolyn(&q);
system("pause");
29、return 0;
}
/*
輸出效果：
兩個一元多項式相加
請輸入第一個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
1 0 1 1
請輸入第二個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
-1 0 -2 1
兩個一元多項式相加的結(jié)果：
系數(shù) 指數(shù)
-1.000000 1
兩個一元多項式相加(另一種方法)
請輸入第三個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
1 0 1 1
請輸入第四個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
-1 0 -
30、2 1
兩個一元多項式相加的結(jié)果(另一種方法)：
系數(shù) 指數(shù)
-1.000000 1
兩個一元多項式相減
請輸入第五個個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
1 0 2 1
請輸入第六個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
-2 0 -1 1
兩個一元多項式相減的結(jié)果：
系數(shù) 指數(shù)
3.000000 0
3.000000 1
兩個一元多項式相乘
請輸入第七個個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
1 0 1 1
請輸入第八個一元多項式的非零項的個數(shù)：2
請依次輸入2個系數(shù)，指數(shù)：（空格）
1 0 1 1
兩個一元多項式相乘的結(jié)果：
系數(shù) 指數(shù)
1.000000 0
2.000000 1
1.000000 2
請按任意鍵繼續(xù). . .
*/
數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫
