数据结构与算法分析--c语言描述练习自答（第三章）(3.1~3.10)

list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; List MakeEmpty(List L); //List L is unused int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P); ElementType Retrieve(Position P); void PrintList(List L); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" struct Node { ElementType Element; Position Next; }; static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=NULL; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==NULL; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==NULL; } /* Return Position of X in L or NULL if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=NULL&&P->Element!=X) P=P->Next; return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=NULL&&P->Next->Element!=X) P=P->Next; return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=NULL) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P) { return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } }

3.1

#include "list.h" void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=NULL) { printf("%-5d",P->Element); P=P->Next; } }

3.2

#include <stdio.h> #include "list.h" void PrintLots(List L,List P); int main(void) { int i; List L,P,L1,P1; L=MakeEmpty(L); P=MakeEmpty(P); L1=L; P1=P; fputs("Enter integer for L(q to quit):",stdout); while(scanf("%d",&i)==1) { Insert(i,L,L1); L1=Advance(L1); fputs("Continue (q to quit):",stdout); } while(getchar()!='\n') continue; fputs("Enter integer for P(q to quit):",stdout); while(scanf("%d",&i)==1) { Insert(i,P,P1); P1=Advance(P1); fputs("Continue (q to quit):",stdout); } PrintList(L); PrintList(P); putchar('\n'); PrintLots(L,P); return 0; } void PrintLots(List L,List P) { Position PtrL,PtrP; PtrL=L; PtrP=Advance(P); int i,j; i=0; j=Retrieve(PtrP); while(PtrP!=NULL) { for(;i<j;i++) { PtrL=Advance(PtrL); } printf("]",Retrieve(PtrL)); PtrP=Advance(PtrP); if(PtrP!=NULL) j=Retrieve(PtrP); } }

3.3

a.

void SwapWithNext(Positon BeforeP,List L) { Positon P,AfterP; P=BeforeP->Next; AfterP=P->Next; /*Both P and AfterP assumed not NULL*/ P->Next=AfterP->Next; BeforeP->Next=AfterP; AfterP->Next=P; }

b.

void SwapWithNext(Position P,List L) { Position BeforeP,AfterP; BeforeP=P->Pre; AfterP=P->Next; P->Next=AfterP->Next; AfterP->Next->Prev=P; AfterP->Next=P; P->Pre=AfterP; AfterP->Pre=BeforeP; BeforeP->Next=AfterP; }

3.4

List Intersect(List L1,List L2) { List Result; Position L1Pos,L2Pos,ResPos; Result=MakeEmpty(Result); L1Pos=First(L1); L2Pos=First(L2); ResPos=First(Result); while(L1Pos!=NULL&&L2Pos!=NULL) { if(L1Pos->Element>L2Pos->Element) L2Pos=Advance(L2Pos); else if(L1Pos->Element<L2Pos->Element) L1Pos=Advance(L1Pos); else { Insert(L1->Element,Result,ResPos); ResPos=Advance(ResPos); L1Pos=Advance(L1Pos); L2Pos=Advance(L2Pos); } } return Result; }

3.5

List Union(List L1,List L2) { /*The both lists were assumed sorted from small to large*/ List Result; Position L1Pos,L2Pos,ResPos; Result=MakeEmpty(Result); L1Pos=First(L1); L2Pos=First(L2); ResPos=First(Result); while(L1Pos!=NULL&&L2Pos!=NULL) { if(L1Pos->Element<L2Pos->Element) { Insert(L1->Element,Result,ResPos); L1Pos=Advance(L1Pos); } else if(L1Pos->Element>L2Pos->Element) { Insert(L2->Element,Result,ResPos); L2Pos=Advance(L2Pos); } else { Insert(L1->Element,Result,ResPos); L1Pos=Advance(L1Pos); L2Pos=Advance(L2Pos); } ResPos=Advance(ResPos); } /*Flush out remaining list*/ while(L1Pos!=NULL) { Insert(L1Pos->Element,Result,ResPos); L1Pos=Advance(L1Pos); ResPos=Advance(ResPos); } while(L2Pos!=NULL) { Insert(L2Pos->Element,Result,ResPos); L2Pos=Advance(L2Pos); ResPos=Advance(ResPos); } return Result; }

3.6

polynomial.h

#ifndef _POLYNOMIAL_H #define _POLYNOMIAL_H typedef struct Node *PtrToNode; struct Node { int Coefficient; int Exponent; PtrToNode Next; }; typedef PtrToNode Polynomial; /*Node will sorted by Exponent from less to large*/ typedef PtrToNode Position; Polynomial Initiate(Polynomial A); int IsEmpty(Polynomial A); int IsLast(Position P,Polynomial A); void Insert(int Coef,int Exp,Polynomial A,Position P); void Print(Polynomial A); void Sort(Polynomial A); Position Advance(Position P); void Delete(Polynomial A); Polynomial Add(Polynomial A,Polynomial B); Polynomial Multiply(Polynomial A,Polynomial B); #endif

polynomial.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) /*assume both polynomial were sorted from less to large*/ { Polynomial Product; Product=Initiate(Product); Position Pa,Pb,Pp; Pa=A->Next; Pp=Product; while(Pa!=NULL) { Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Product,Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Pa=Advance(Pa); } Sort(Product); return Product; }

test.c

#include <stdio.h> #include "polynomial.h" int main(void) { int Coef,Exp; Polynomial A,B,Sum,Product; Position Temp; A=Initiate(A); B=Initiate(B); puts("Start to create polynomial A:"); Temp=A; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,A,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial A created done!We will print it."); Print(A); puts("Now sort polynomial A.Print it."); Sort(A); Print(A); while(getchar()!='\n') continue; puts("Start to create polynomial B:"); Temp=B; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,B,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial B created done!We will print it."); Print(B); puts("Now sort polynomial B.Print it."); Sort(B); Print(B); puts("A plus B:"); Sum=Add(A,B); Print(Sum); puts("A multiply B:"); Product=Multiply(A,B); Print(Product); puts("Well done!"); Delete(A); Delete(B); Delete(Sum); Delete(Product); return 0; }

3.7

a. polynomial.h

#ifndef _POLYNOMIAL_H #define _POLYNOMIAL_H typedef struct Node *PtrToNode; struct Node { int Coefficient; int Exponent; PtrToNode Next; }; typedef PtrToNode Polynomial; /*Node will sorted by Exponent from less to large*/ typedef PtrToNode Position; Polynomial Initiate(Polynomial A); int IsEmpty(Polynomial A); int IsLast(Position P,Polynomial A); void Insert(int Coef,int Exp,Polynomial A,Position P); void Print(Polynomial A); void Sort(Polynomial A); Position Advance(Position P); void Delete(Polynomial A); Polynomial Add(Polynomial A,Polynomial B); Polynomial Multiply(Polynomial A,Polynomial B); #endif

polynomial.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) /*assume both polynomial were sorted from less to large*/ { Polynomial Product; Product=Initiate(Product); Position Pa,Pb,Pp; Pa=A->Next; Pp=Product; while(Pa!=NULL) { Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Product,Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Pa=Advance(Pa); } Sort(Product); return Product; }

test.c

#include <stdio.h> #include "polynomial.h" int main(void) { int Coef,Exp; Polynomial A,B,Sum,Product; Position Temp; A=Initiate(A); B=Initiate(B); puts("Start to create polynomial A:"); Temp=A; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,A,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial A created done!We will print it."); Print(A); puts("Now sort polynomial A.Print it."); Sort(A); Print(A); while(getchar()!='\n') continue; puts("Start to create polynomial B:"); Temp=B; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,B,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial B created done!We will print it."); Print(B); puts("Now sort polynomial B.Print it."); Sort(B); Print(B); puts("A plus B:"); Sum=Add(A,B); Print(Sum); puts("A multiply B:"); Product=Multiply(A,B); Print(Product); puts("Well done!"); Delete(A); Delete(B); Delete(Sum); Delete(Product); return 0; }

b. polynomial.h

#ifndef _POLYNOMIAL_H #define _POLYNOMIAL_H typedef struct Node *PtrToNode; struct Node { int Coefficient; int Exponent; PtrToNode Next; }; typedef PtrToNode Polynomial; /*Node will sorted by Exponent from less to large*/ typedef PtrToNode Position; Polynomial Initiate(Polynomial A); int IsEmpty(Polynomial A); int IsLast(Position P,Polynomial A); void Insert(int Coef,int Exp,Polynomial A,Position P); void Print(Polynomial A); int CountSize(Polynomial A); void Sort(Polynomial A); Position Advance(Position P); void Delete(Polynomial A); Polynomial Add(Polynomial A,Polynomial B); Polynomial Multiply(Polynomial A,Polynomial B); #endif

polynomial.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } int CountSize(Polynomial A) /*the result is exclude header*/ { int Count=0; Position P; P=A->Next; while(P!=NULL) { Count++; P=Advance(P); } return Count; } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) //O(MN^2),not O(M^2N),i think { int index,M,N; Position Pa,Pb,Pp,Temp; M=CountSize(A); N=CountSize(B); M=M<=N?M:N; Position Parray[M]; for(index=0;index<M;index++) { Parray[index]=Initiate(Parray[index]); } Pa=A->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } Pp=Initiate(Pp); for(index=0;index<M;index++) { Temp=Pp; Pp=Add(Parray[index],Pp); Delete(Temp); } return Pp; }

test.c

#include <stdio.h> #include "polynomial.h" int main(void) { int Coef,Exp; Polynomial A,B,Sum,Product; Position Temp; A=Initiate(A); B=Initiate(B); puts("Start to create polynomial A:"); Temp=A; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,A,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial A created done!We will print it."); Print(A); puts("Now sort polynomial A.Print it."); Sort(A); Print(A); while(getchar()!='\n') continue; puts("Start to create polynomial B:"); Temp=B; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,B,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial B created done!We will print it."); Print(B); puts("Now sort polynomial B.Print it."); Sort(B); Print(B); puts("A plus B:"); Sum=Add(A,B); Print(Sum); puts("A multiply B:"); Product=Multiply(A,B); Print(Product); puts("Well done!"); Delete(A); Delete(B); Delete(Sum); Delete(Product); return 0; }

3.8

polynomial.h

#ifndef _POLYNOMIAL_H #define _POLYNOMIAL_H typedef struct Node *PtrToNode; struct Node { int Coefficient; int Exponent; PtrToNode Next; }; typedef PtrToNode Polynomial; /*Node will sorted by Exponent from less to large*/ typedef PtrToNode Position; Polynomial Initiate(Polynomial A); int IsEmpty(Polynomial A); int IsLast(Position P,Polynomial A); void Insert(int Coef,int Exp,Polynomial A,Position P); void Print(Polynomial A); int CountSize(Polynomial A); void Sort(Polynomial A); Position Advance(Position P); void Delete(Polynomial A); Polynomial Add(Polynomial A,Polynomial B); Polynomial Multiply(Polynomial A,Polynomial B); Polynomial Pow(Polynomial A,int P); #endif

polynomial_1.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } int CountSize(Polynomial A) /*the result is exclude header*/ { int Count=0; Position P; P=A->Next; while(P!=NULL) { Count++; P=Advance(P); } return Count; } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) //O(MN^2),not O(M^2N),i think { int index,M,N,S; Position Pa,Pb,Pp,Temp; M=CountSize(A); N=CountSize(B); S=M<=N?M:N; Position Parray[S]; for(index=0;index<S;index++) { Parray[index]=Initiate(Parray[index]); } if(M<=N) { Pa=A->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } else { Pa=B->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=A->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } Pp=Initiate(Pp); for(index=0;index<S;index++) { Temp=Pp; Pp=Add(Parray[index],Pp); Delete(Temp); } return Pp; } Polynomial Pow(Polynomial A,int P) { int i; Position Temp; Polynomial Unit; Unit=Initiate(Unit); Insert(1,0,Unit,Unit); for(i=0;i<P;i++) { Temp=Unit; Unit=Multiply(Unit,A); Delete(Temp); } return Unit; }

polynomial_2.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } int CountSize(Polynomial A) /*the result is exclude header*/ { int Count=0; Position P; P=A->Next; while(P!=NULL) { Count++; P=Advance(P); } return Count; } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) //O(MN^2),not O(M^2N),i think { int index,M,N,S; Position Pa,Pb,Pp,Temp; M=CountSize(A); N=CountSize(B); S=M<=N?M:N; Position Parray[S]; for(index=0;index<S;index++) { Parray[index]=Initiate(Parray[index]); } if(M<=N) { Pa=A->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } else { Pa=B->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=A->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } Pp=Initiate(Pp); for(index=0;index<S;index++) { Temp=Pp; Pp=Add(Parray[index],Pp); Delete(Temp); } return Pp; } Polynomial Pow(Polynomial A,int P) { int i; Position Temp; Polynomial Unit; Unit=Initiate(Unit); Insert(1,0,Unit,Unit); if(P==0) return Unit; if(P==1) return A; if(P%2==0) return Pow(Multiply(A,A),P/2); else return Multiply(Pow(Multiply(A,A),P/2),A); }

test.c

#include <stdio.h> #include "polynomial.h" int main(void) { int Coef,Exp; Polynomial A,B,Sum,Product; Position Temp; A=Initiate(A); B=Initiate(B); puts("Start to create polynomial A:"); Temp=A; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,A,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial A created done!We will print it."); Print(A); puts("Now sort polynomial A.Print it."); Sort(A); Print(A); while(getchar()!='\n') continue; puts("Start to create polynomial B:"); Temp=B; fputs("Enter two integers for Coefficient and Exponent(q to quit):",stdout); while(scanf("%d%d",&Coef,&Exp)==2) { Insert(Coef,Exp,B,Temp); Temp=Advance(Temp); fputs("another two integers(q to quit):",stdout); } puts("Polynomial B created done!We will print it."); Print(B); puts("Now sort polynomial B.Print it."); Sort(B); Print(B); puts("A plus B:"); Sum=Add(A,B); Print(Sum); puts("A multiply B:"); Product=Multiply(A,B); Print(Product); puts("Well done!"); puts("Now we calculate the Pow of A^2:"); Print(Pow(A,2)); puts("Now we calculate the Pow of B^3:"); Print(Pow(B,3)); Delete(A); Delete(B); Delete(Sum); Delete(Product); return 0; }

3.9

biginteger.h

#ifndef _BIGINTEGER_H #define _BIGINTEGER_H #include "polynomial.h" typedef Polynomial BigInteger; BigInteger IntegerToBigInteger(long long int A); BigInteger PowOfBigInteger(BigInteger A,int P); int * Statistics(BigInteger A); void PrintBigInteger(BigInteger A); #endif

biginteger.c

#include <stdlib.h> #include <stdio.h> #include "biginteger.h" BigInteger IntegerToBigInteger(long long int A) { int exp=0,coef; BigInteger N; Position P; N=Initiate(N); P=N; while(A>0) { coef=A%NumberSystem; Insert(coef,exp,N,P); P=Advance(P); A/=NumberSystem; exp++; } return N; } BigInteger PowOfBigInteger(BigInteger A,int P) { return Pow(A,P); } int * Statistics(BigInteger A) { int *Array; Position P; Array=(int *)malloc(sizeof(int)*NumberSystem); P=A->Next; while(P!=NULL) { Array[P->Coefficient]++; P=Advance(P); } return Array; } void PrintBigInteger(BigInteger A) { Position P; P=A->Next; if(P!=NULL) { PrintBigInteger(P); printf("%d",P->Coefficient); } }

test.c

#include <stdio.h> #include "biginteger.h" int main(void) { int biger,exponent; puts("Enter two integer for biger and exponent:"); fscanf(stdin,"%d%d",&biger,&exponent); int *array,i; BigInteger T; T=IntegerToBigInteger(biger); puts("big integer is:"); PrintBigInteger(T); putchar('\n'); T=PowOfBigInteger(T,exponent); array=Statistics(T); for(i=0;i<NumberSystem;i++) printf("There are %d of %ds in the result.\n",array[i],i); puts("Print the big integer:"); PrintBigInteger(T); return 0; }

polynomial.h

#ifndef _POLYNOMIAL_H #define _POLYNOMIAL_H #define NumberSystem 10 typedef struct Node *PtrToNode; struct Node { int Coefficient; int Exponent; PtrToNode Next; }; typedef PtrToNode Polynomial; /*Node will sorted by Exponent from less to large*/ typedef PtrToNode Position; Polynomial Initiate(Polynomial A); int IsEmpty(Polynomial A); int IsLast(Position P,Polynomial A); void Insert(int Coef,int Exp,Polynomial A,Position P); void Print(Polynomial A); int CountSize(Polynomial A); void Sort(Polynomial A); Position Advance(Position P); void Delete(Polynomial A); Polynomial Add(Polynomial A,Polynomial B); Polynomial Multiply(Polynomial A,Polynomial B); Polynomial Pow(Polynomial A,int P); #endif

polynomial_1.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } int CountSize(Polynomial A) /*the result is exclude header*/ { int Count=0; Position P; P=A->Next; while(P!=NULL) { Count++; P=Advance(P); } return Count; } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) //O(MN^2),not O(M^2N),i think { int index,M,N,S; Position Pa,Pb,Pp,Temp; M=CountSize(A); N=CountSize(B); S=M<=N?M:N; Position Parray[S]; for(index=0;index<S;index++) { Parray[index]=Initiate(Parray[index]); } if(M<=N) { Pa=A->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } else { Pa=B->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=A->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } Pp=Initiate(Pp); for(index=0;index<S;index++) { Temp=Pp; Pp=Add(Parray[index],Pp); Delete(Temp); } return Pp; } Polynomial Pow(Polynomial A,int P) { int i; Position Temp; Polynomial Unit; Unit=Initiate(Unit); Insert(1,0,Unit,Unit); for(i=0;i<P;i++) { Temp=Unit; Unit=Multiply(Unit,A); Delete(Temp); } return Unit; }

polynomial_2.c

#include <stdio.h> #include <stdlib.h> #include "polynomial.h" static int Compare(Position P1,Position P2); /*Return 0 equal,-1 when P1 less than P2,1 when P1 more than P2*/ static void FataError(char *S); static void AdaptCoefficient(Polynomial A); static void AdaptCoefficient(Polynomial A) { Position P; int Adapted=0; while(Adapted==0) { P=A->Next; Adapted=1; while(P!=NULL) { if(P->Coefficient>=NumberSystem) { if(P->Next!=NULL) { P->Next->Coefficient+=P->Coefficient/NumberSystem; P->Coefficient%=NumberSystem; } else { Insert(P->Coefficient/NumberSystem,P->Exponent+1,A,P); P->Coefficient%=NumberSystem; } Adapted=0; } P=Advance(P); } } } static int Compare(Position P1,Position P2) { int result; if(P1->Exponent<P2->Exponent) result=-1; else if(P1->Exponent>P2->Exponent) result=1; else result=0; return result; } static void FataError(char *S) { fputs(S,stderr); putchar('\n'); exit(EXIT_FAILURE); } Polynomial Initiate(Polynomial A) { PtrToNode P; P=(PtrToNode)malloc(sizeof(struct Node)); if(P==NULL) FataError("Fail to create polynomial!"); P->Next=NULL; return P; } int IsEmpty(Polynomial A) { return A->Next==NULL; } int IsLast(Position P,Polynomial A) { return P->Next==NULL; } void Insert(int Coef,int Exp,Polynomial A,Position P) { Position Ptr; Ptr=(PtrToNode)malloc(sizeof(struct Node)); if(Ptr==NULL) FataError("Fail to create Node."); Ptr->Coefficient=Coef; Ptr->Exponent=Exp; Ptr->Next=P->Next; P->Next=Ptr; } void Print(Polynomial A) { Position P; if(IsEmpty(A)) puts("Polynomial is empty!"); else { P=A->Next; while(P!=NULL) { printf(" %dX^%d ",P->Coefficient,P->Exponent); P=Advance(P); if(P!=NULL) putchar('+'); } } putchar('\n'); fputs("Polynomial print done!",stdout); } int CountSize(Polynomial A) /*the result is exclude header*/ { int Count=0; Position P; P=A->Next; while(P!=NULL) { Count++; P=Advance(P); } return Count; } Position Advance(Position P) { return P->Next; } void Delete(Polynomial A) { Position Temp,P; P=A->Next; A->Next=NULL; while(P!=NULL) { Temp=P; P=Advance(P); free(Temp); } } void Sort(Polynomial A) { Position P,Temp; int Sorted=0; while(Sorted==0) { P=A; Sorted=1; while(P->Next->Next!=NULL) { if(Compare(P->Next,P->Next->Next)==1) { Temp=P->Next->Next; P->Next->Next=Temp->Next; Temp->Next=P->Next; P->Next=Temp; Sorted=0; } else if(Compare(P->Next,P->Next->Next)==0) { Temp=P->Next->Next; P->Next->Next=Temp->Next; P->Next->Coefficient+=Temp->Coefficient; Sorted=0; free(Temp); continue; } P=Advance(P); } } } Polynomial Add(Polynomial A,Polynomial B) /*assumed Polynomial A and B are sorted from less to large*/ { Polynomial Sum; Sum=Initiate(Sum); Position Pa,Pb,Psum; Pa=A->Next; Pb=B->Next; Psum=Sum; while(Pa!=NULL&&Pb!=NULL) { if(Compare(Pa,Pb)==-1) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } else if(Compare(Pa,Pb)==1) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } else { Insert(Pa->Coefficient+Pb->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Pb=Advance(Pb); Psum=Advance(Psum); } } while(Pa!=NULL) { Insert(Pa->Coefficient,Pa->Exponent,Sum,Psum); Pa=Advance(Pa); Psum=Advance(Psum); } while(Pb!=NULL) { Insert(Pb->Coefficient,Pb->Exponent,Sum,Psum); Pb=Advance(Pb); Psum=Advance(Psum); } AdaptCoefficient(Sum); return Sum; } Polynomial Multiply(Polynomial A,Polynomial B) //O(MN^2),not O(M^2N),i think { int index,M,N,S; Position Pa,Pb,Pp,Temp; M=CountSize(A); N=CountSize(B); S=M<=N?M:N; Position Parray[S]; for(index=0;index<S;index++) { Parray[index]=Initiate(Parray[index]); } if(M<=N) { Pa=A->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=B->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } else { Pa=B->Next; index=0; while(Pa!=NULL) { Pp=Parray[index]; Pb=A->Next; while(Pb!=NULL) { Insert(Pa->Coefficient*Pb->Coefficient,Pa->Exponent+Pb->Exponent,Parray[index],Pp); Pb=Advance(Pb); Pp=Advance(Pp); } Sort(Parray[index]); Pa=Advance(Pa); index++; } } Pp=Initiate(Pp); for(index=0;index<S;index++) { Temp=Pp; Pp=Add(Parray[index],Pp); Delete(Temp); } return Pp; } Polynomial Pow(Polynomial A,int P) { int i; Position Temp; Polynomial Unit; Unit=Initiate(Unit); Insert(1,0,Unit,Unit); if(P==0) return Unit; if(P==1) return A; if(P%2==0) return Pow(Multiply(A,A),P/2); else return Multiply(Pow(Multiply(A,A),P/2),A); }

3.10

list.h

#ifndef _List_H #define _List_H struct Node; typedef struct Node *PtrToNode; typedef PtrToNode List; typedef PtrToNode Position; typedef int ElementType; struct Node { ElementType Element; Position Next; }; List MakeEmpty(List L); //List L is unused int IsEmpty(List L); int IsLast(Position P,List L); Position Find(ElementType X,List L); void Delete(ElementType X,List L); Position FindPrevious(ElementType X,List L); void Insert(ElementType X,List L,Position P); void DeleteList(List L); Position Header(List L); Position First(List L); Position Advance(Position P,List L); ElementType Retrieve(Position P); void PrintList(List L); #endif

list.c

#include <stdio.h> #include <stdlib.h> #include "list.h" static void FataError(char *S); void FataError(char *S) { fputs("S\n",stderr); exit(EXIT_FAILURE); } /* Initiate a List,L is unused in this implementation */ List MakeEmpty(List L) { Position P; P=(Position)malloc(sizeof(struct Node)); P->Next=P; return P; } /* Return true if L is empty */ int IsEmpty(List L) { return L->Next==L; } /* Return true if P is the last position in List L,Parameter L is unused in this implementation */ int IsLast(Position P,List L) { return P->Next==L; } /* Return Position of X in L or L if not found */ Position Find(ElementType X,List L) { Position P; P=L->Next; while(P!=L&&P->Element!=X) P=P->Next; return P; } /* Delete first occurrence of X from a list */ void Delete(ElementType X,List L) { Position P,TmpCell; P=FindPrevious(X,L); if(!IsLast(P,L)) { TmpCell=P->Next; P->Next=TmpCell->Next; free(TmpCell); } else { TmpCell=L->Next; L->Next=TmpCell->Next; free(TmpCell); } } /* If X is not found , the next field of returned Position is NULL */ Position FindPrevious(ElementType X,List L) { Position P; P=L; while(P->Next!=L&&P->Next->Element!=X) P=P->Next; if(P==L) { while(!IsLast(P,L)) P=Advance(P,L); } return P; } /* Insert after legal position P,Parameter L is unused in this implementation */ void Insert(ElementType X,List L,Position P) { Position TmpCell; TmpCell=malloc(sizeof(struct Node)); if(TmpCell==NULL) FataError("Out of space!!"); TmpCell->Element=X; TmpCell->Next=P->Next; P->Next=TmpCell; } /* avoid delete header */ void DeleteList(List L) { Position P,Tmp; P=L->Next; L->Next=NULL; while(P!=L) { Tmp=P->Next; free(P); P=Tmp; } } /* Return header */ Position Header(List L) { return L; } /* Return the first node except header */ Position First(List L) { return L->Next; } /* Return the next node */ Position Advance(Position P,List L) { if(IsLast(P,L)) return P->Next->Next; return P->Next; } /* Return the select Element */ ElementType Retrieve(Position P) { return P->Element; } void PrintList(List L) { Position P; P=L->Next; if(IsEmpty(L)) FataError("List is empty!!!"); while(P!=L) { printf("%-5d",P->Element); P=P->Next; } }

josephus.c

#include <stdio.h> #include "list.h" int main(void) { int M,N,i,j,count; List L; Position P,Temp; L=MakeEmpty(L); puts("M N:"); scanf("%d%d",&M,&N); for(i=1,P=L;i<=N;i++) { Insert(i,L,P); P=Advance(P,L); } PrintList(L); putchar('\n'); P=L->Next; for(count=0;count<N-1;count++) { for(j=M;j>0;j--) { P=Advance(P,L); } printf("]",Retrieve(P)); Temp=P; P=Advance(P,L); Delete(Retrieve(Temp),L); } PrintList(L); return 0; }