算法设计与分析（郑宗汉）几个代码错误

上学期用了这本书。而且还有悲剧的上机，无奈这本书的代码错误有点多，小到括号丢失，大到原则错误……毕竟是本教材，小女子就把自己上机的时候发现的几个错误贴上来，也为了方便后来的师弟师妹（抄代码？呵呵）学习。

多项式乘法分治算法和动态规划有单独写出来，最后是我们的结课设计，堆排序，基数排序，合并有序数列和冒泡都在里面，如果有人需要单独的函数，我相信从这里面摘出来比自己改要容易，呵呵，当然是运行没有问题的。

多项式乘法分治算法，貌似只有这本书用这个名称
#include stdio.h
#include stdlib.h
#include math.h
void product(float p[],float q[],float c[])
{
float a=p[0];
float b=p[1];
float e=q[0];
float d=q[1];
c[0]=a*e;
c[2]=b*d;
c[1]=(a+b)*(e+d)-c[0]-c[2];
}
void plus(float p[],float q[],float c[],int n)
{
int i;
for (i=0;i
#define MAX_TYPE 1000
#define ZERO_TYPE 0

template
struct NODE
{
int v_num;
Type len;
NODE *next;
};

template
Type fgraph(NODE node[],int route[],int n)
{
int i;
NODE *pnode;
int *path = new int[n];
Type min_cost,*cost = new Type[n];
for(i=0;i=0;i--)
{
pnode=&node[i];
while(pnode!=NULL)
{
if ((pnode->len+cost[pnode->v_num])len+cost[pnode->v_num];
path[i]=pnode->v_num;
}
pnode=pnode->next;
}
}
i=0;
while((route[i]!=n-1)&&(path[i]!=-1))
{
i++;
route[i]=path[route[i-1]];
}
min_cost=cost[0];
delete path;
delete cost;
return min_cost;
}

int main()
{
int i,rep,p,n=10;
int route[100];
NODE node[30];
int A[100]={1,30,2,20,3,25,100,4,32,5,35,6,40,100,4,30,5,28,6,10,100,4,35,5,25,6,20,100,7,21,8,23,100,7,20,8,38,100,7,29,8,40,100,9,38,100,9,28,100};
p=0;
for(i=0;i *qnode,*snode;
snode=qnode=&node[i];
while(1)
{
rep=A[p++];
if(rep>n)
{
snode->next=NULL;
delete qnode;
break;
}
else
{
qnode->v_num=rep;
qnode->len=A[p++];
qnode->next=new NODE;
snode=qnode;
qnode=qnode->next;
}
}
}
printf("%d\n",fgraph(node,route,n));
for(i=0;i<5;i++)>
#include math.h
#include stdlib.h
#include time.h
#include windows.h

void swap(int &x,int &y)
{
int temp;
temp=x;
x=y;
y=temp;

}

void Bubble(int a[],int n)
{
int i,k;
for(k=n-1;k>0;k--)
{
for(i=0;ia[i+1])
{
swap(a[i],a[i+1]);
}
}
}

}

void Merge(int a[],int p,int q,int r,int m)
{
int *bp=new int[m];
int i,j,k;
i=p;j=q+1;k=0;
while(i<=q&&j<=r) { if(a[i]<=a[j]) bp[k++]=a[i++]; else bp[k++]=a[j++]; } if(i==q+1) for(;j<=r;j++) bp[k++]=a[j]; else for(;i<=q;i++) bp[k++]=a[i]; k=0; for(i=p;i<=r;i++) a[i]=bp[k++]; delete bp; } void theBubble() { int i,q,s[10001],n=10000; FILE *fp1,*fp2; fp1=fopen("cindy.txt","r"); fp2=fopen("out.txt","w"); for(i=0;i<100;i++) q="0;q<100;q++)" t =" clock();" sec =" t;" sec2 =" clock();" p="L-">next;
if (p!=L)
{
p->prior->next=p->next;
p->next->prior=p->prior;
}
else p=NULL;
return p;
}

void add_entry(LinkedList *L,LinkedList *p){
p->prior=L->prior;
p->next=L;
L->prior->next=p;
L->prior=p;
}


int get_digital(LinkedList *p,int i){
int key ;
key=p->key;
if (i!=0)
key =key /(int)pow(10,i);
return key %10;

}
void append (LinkedList *L,LinkedList *L1){
if(L1->next!=L1){
L->prior->next=L1->next;
L1->next->prior=L->prior;
L1->prior->next=L;
L->prior=L1->prior;
}
}

void radix_sort(LinkedList *L,int k){
LinkedList *Lhead[10],*p;
int i,j;
for (i=0;i<10;i++) i="0;inext=Lhead[j];
Lhead[j]->prior=Lhead[j];
}
while (L->next!=L){
p=del_entry(L);
j=get_digital(p,i);
add_entry(Lhead[j],p);
}
for (j=0;j<10;j++) i="0;i<10;i++)" s="-1649273;" fp1="fopen(" fp2="fopen(" n="10000;" tp2 =" (LinkedList">key=-1;
tp2->prior=NULL;
tp2->next=NULL;
tp1=tp2;
l=tp1;

for(i=0;ikey=j;
tp1->next=tp2;
tp2->prior=tp1;
tp2->next=NULL;
tp1=tp2;
}
k=1;
for(i=0;k==1;i++){
if((s/(int)pow(10,i))==0){k=0;}
}
k=i-1;
tp2->next=l;
clock_t t = clock();
long sec = t;
radix_sort(l,k);
tp1=l->next;
long sec2 = clock();
printf("%ld\n",sec2-sec);

fclose(fp1);
fclose(fp2);
}

/*****the radix******/




template
void swap(Type &x,Type &y)
{
Type temp;
temp=x;
x=y;
y=temp;
}
template
void sift_down(Type H[],int n,int i)
{
BOOL done=FALSE;
if ((2*i)<=n) { while(!done&&(i=2*i)<=n) { if (i+1<=n && H[i+1]>H[i])
i=i+1;
if (H[i/2]
void make_heap(Type A[],int n)
{
int i;
A[n]=A[0];
for(i=n/2;i>=1;i--)
sift_down(A,n,i);
}
template
void heap_sort(Type A[],int n)
{
int i;
make_heap(A,n);
for (i=n;i>1;i--)
{
swap(A[1],A[i]);
sift_down(A,i-1,1);
}
}


void theheap()
{
int A[10001];
int n=10000,i,q;
FILE *fp1,*fp2;
fp1=fopen("cindy.txt","r");
fp2=fopen("out.txt","w");
for(i=0;i<100;i++) q="0;q<100;q++)" t =" clock();" sec =" t;" sec2 =" clock();">
void merge(Type a[],int p,int q,int r,int m)
{
int *bp=new int[m];
int i,j,k;
i=p;j=q+1;k=0;
while(i<=q&&j<=r) { if(a[i]<=a[j]) bp[k++]=a[i++]; else bp[k++]=a[j++]; } if(i==q+1) for(;j<=r;j++) bp[k++]=a[j]; else for(;i<=q;i++) bp[k++]=a[i]; k=0; for(i=p;i<=r;i++) a[i]=bp[k++]; delete bp; } template
void merge_sort(Type A[],int n)
{
int x,s,t=1;
while(t
s=t,t=2*s;x=0;
while(x+t
merge(A,x,x+s-1,x+t-1,t);
x=x+t;
}
if(x+s
merge(A,x,x+s-1,n-1,n-x);
}
}
void themerge()
{

long int a,b;
int i,q,n=10000;
int A[10001];
FILE *fp1,*fp2;
fp1=fopen("cindy.txt","r");
fp2=fopen("out.txt","w");
for(i=0;i<100;i++)
{
for(q=0;q<100;q++)
{
fscanf(fp1,"%d",&A[i]);
}
}
a=clock();
merge_sort(A,n);
b=clock();
printf("%ld\n",b-a);
fclose(fp1);
fclose(fp2);
}
/************************/
void main()
{
FILE *fp;
fp=fopen("cindy.txt","wr");
int m,p,ch1;
double ch;
char rep=getchar();
if(rep=='f')
{
for(m=0;m<100;m++)
{
for(p=0;p<100;p++)
{
ch=rand()%1000/10.0;
fprintf(fp,"%f",ch);
}
}
printf("DATE TYPE IS FLOAT\n");
}
if(rep=='i')
{
for(m=0;m<100;m++)
{
for(p=0;p<100;p++)
{
ch1=rand()%1000;
fprintf(fp,"%d",ch1);
}
}
printf("DATE TYPE IS INT\n");
}
theBubble();
themerge();
theheap();
theradix();
fclose(fp);
}