24.txt

弦链表算法合成等

//VC6.0调试通过
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <float.h>
#include <malloc.h>
typedef struct tagL{  //弦链表
      int s,e;
      struct tagL *n;}L,*pL;
pL LNew(int s,int e){ //生成新结点
      pL u=(pL)malloc(sizeof(L));
      u->s=s;u->e=e;u->n=NULL;
      return u;}
//两链表合成一链表
void LL(pL *h,pL p){
      pL u,v,w;
      if(!p){return;}
      if(!*h){v=NULL;}
      else{for(u=*h;u;v=u,u=u->n);}
      for(u=p;u;u=u->n){
            for(w=*h;w;w=w->n)
            if(w->s==u->s&&w->e==u->e||
                   w->s==u->e&&w->e==u->s)
                        break;
      if(w){break;}
      if(!v){*h=LNew(u->s,u->e);v=*h;}
      else{v->n=LNew(u->s,u->e);v=v->n;}}}
void main(void){
      FILE *fp;
      int n,i,j,k,kk,s;
      double *x,*y,**c,**d,t,tmp;
      pL **h,p;
      fp=fopen("input.dat","r");//读入数据
      fscanf(fp,"%d",&n);
      x=(double*)malloc(n*sizeof(double));
      y=(double*)malloc(n*sizeof(double));
      for(i=0;i<n;i++)
            fscanf(fp,"%lf%lf",x+i,y+i);
      fclose(fp);
      //分配存贮空间
      d=(double**)malloc(n*sizeof(double*));
      c=(double**)malloc(n*sizeof(double*));
      h=(pL**)malloc(n*sizeof(pL*));
      for(i=0;i<n;i++){
            d[i]=(double*)malloc(n*sizeof(double));
            c[i]=(double*)malloc((n-1)*sizeof(double));
            h[i]=(pL*)malloc((n-1)*sizeof(pL));    }
      //计算各弦的长度
      for(i=0;i<n;i++)for(j=i+1;j<n;j++)
                  d[i][j]=d[j][i]=pow(pow(x[i]-x[j],2)+pow(y[i]-y[j],2),0.5);
      //约定s=2时最优三角剖分值为0，弦链表为空
      for(s=2,i=0;i<n;i++){
            c[i][s-2]=0;     h[i][s-2]=NULL;  }
      //s=3时最优三角剖分值为周长，弦链表置初值
      for(s=3,i=0;i<n;i++){
            c[i][s-2]=d[i][(i+1)%n]+d[(i+1)%n][(i+2)%n]+d[(i+2)%n][i];
            h[i][s-2]=LNew(i,(i+2)%n); }
      //对s>=4，计算最优三角剖分值和弦链表
      for(s=4;s<=n;s++)     for(i=0;i<n;i++){
                  for(t=DBL_MAX,k=1;k<=s-2;k++){
                  tmp=c[i][k+1-2]+c[(i+k)%n][s-k-2]+
                  d[i][(i+k)%n]+d[(i+k)%n][(i+s-1)%n]+
                              d[(i+s-1)%n][i];
                        if(tmp<t){t=tmp;kk=k;}              }
                  c[i][s-2]=t;//保存s时的最优三角剖分值
                  if(kk==1)//计算弦链表
                   h[i][s-2]=LNew((i+kk)%n,(i+s-1)%n);
                  else   h[i][s-2]=LNew(i,(i+kk)%n);
                  LL(&(h[i][s-2]),h[i][kk+1-2]);
                  LL(&(h[i][s-2]),h[(i+kk)%n][s-kk-2]);}
      for(i=0;i<n;i++){//输出结果
            for(p=h[i][n-2];p;p=p->n)
                  printf("%d  %d\n",p->s,p->e);
            printf("%lf\n",c[i][n-2]);}
      for(i=0;i<n;i++){
            free(d[i]);free(c[i]);free(h[i]);}
      free(x);free(y);free(d);free(c);free(h);}