salesman-temp.cpp

货郎担 最短路径问题 用链表储存最短路径节点

// salesman.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "malloc.h"

#define N   10  //the number of node
#define M   22  //the number of arc
#define MAXINT  10000000;

static int COST;
static int ARC[M][3]={
                {1,2,12},
				{1,3,1},
				{1,5,36},
				{1,7,10},
				{2,3,2},
				{2,4,3},
				{2,5,18},
				{2,6,23},
				{2,8,19},
				{3,4,8},
				{3,5,35},
				{3,10,66},
				{4,5,4},
				{4,6,80},
				{4,9,33},
				{5,6,19},
				{5,10,5},
				{6,8,8},
				{6,7,9},
				{7,8,25},
				{8,9,7},
				{9,10,6}
	};


typedef struct NODE{
    int X;
    int Y;
    struct NODE* next;
}node;

void  order(){
    int i,j;
    int temp[1][3];
    bool NotOver=true;
    for(i=1;(i<=M)&&NotOver;i++){
        NotOver=false;
        for(j=0;j<M-i;j++){
            if(ARC[j][2]>ARC[j+1][2]){
			temp[0][0]=ARC[j][0];
			temp[0][1]=ARC[j][1];
            temp[0][2]=ARC[j][2];
			ARC[j][0]=ARC[j+1][0];
			ARC[j][1]=ARC[j+1][1];
            ARC[j][2]=ARC[j+1][2];
            ARC[j+1][0]=temp[0][0];
			ARC[j+1][1]=temp[0][1];
			ARC[j+1][2]=temp[0][2];
			NotOver=true;
            }
        }
    }
}

void greed(){
    int k=0;
	int i=0;
	int j=0;
    int v=0;		//标记当前边有几个端点在链表里  0 ,1 ,2
	// NO标记当前弧 k 的第几个端点与链表里 p 的第几个端点相连
	//若只有一个端点相连，00表示k弧的端点0与p的端点X相连，前一位为弧的端点
	//同理，若有两个端点相连，用四位表示，如0000
    int NO=00;		
    COST=0;
    node* L=(node*)malloc(sizeof(node));
	node* p=NULL;
	node* q=NULL;
	node* last=L;
	node* p1=NULL;		//记录X节点的位置
	node* p2=NULL;		//记录Y节点的位置
    int temp= (int)MAXINT;	
    for(i=1;i<=N;i++){
        while(ARC[k][2]==temp){
			k++;
		}//while((ARC[k][2])==MAXINT))
		if(i==1){
			p=(node*)malloc(sizeof(node));
			p->X=ARC[k][0];
			p->Y=ARC[k][1];
			L->next=p;
			last=p;
			last->next=NULL;
			COST=ARC[k][2];
			i++;
			k++;
		}//if(i==1)
        COST=COST+ARC[k][2];
		q=L->next;
		v=0;
		NO=-1;
		//查找当前弧的两个端点是否在链表中
		while(q){
			if(ARC[k][0]==q->X){
				v++;
				NO=00;
				p1=q;
			}
			if(ARC[k][0]==q->Y){
				v++;
				NO=01;
				p1=q;
			}
			if(ARC[k][1]==q->X){
				v++;
				if(v==2){
					NO=100*NO+10;
				}
				else {NO=10;}
				p2=q;
			}
			if(ARC[k][1]==q->Y){
				v++;
				if(v==2){
					NO=100*NO+11;
				}
				else {NO=11;}
				p2=q;
			}
			q=q->next;
		}//while(q)

		switch(v){
			case 0:	p=(node*)malloc(sizeof(node));
					p->X=ARC[k][0];
					p->Y=ARC[k][1];
					last->next=p;
					last=p;
					last->next=NULL;
					break;

			case 1:
				if(i!=N-1){
				//将边（A,Y）的长度定为MAXINT
					switch(NO){
						case 00:
							for(j=0;j<M;j++){
								if(((ARC[k][1]==ARC[j][0])&&(p1->Y==ARC[j][1]))||
									((ARC[k][1]==ARC[j][1])&&(p1->Y==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						case 01:
							for(j=0;j<M;j++){
								if(((ARC[k][1]==ARC[j][0])&&(p1->X==ARC[j][1]))||
									((ARC[k][1]==ARC[j][1])&&(p1->X==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						case 10:
							for(j=0;j<M;j++){
								if(((ARC[k][0]==ARC[j][0])&&(p2->Y==ARC[j][1]))||
									((ARC[k][0]==ARC[j][1])&&(p2->Y==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						case 11:
							for(j=0;j<M;j++){
								if(((ARC[k][0]==ARC[j][0])&&(p2->X==ARC[j][1]))||
									((ARC[k][0]==ARC[j][1])&&(p2->X==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						default:break;
					}//switch(NO)
				}//if(i!=N-1)
				for(j=k+1;j<M;j++){
					if((NO==01)||(NO==00)){
						if((ARC[j][0]==ARC[k][0])||(ARC[j][1]==ARC[k][0])){
							ARC[j][2]=MAXINT;
						}
					}
					else if((NO==10)||(NO==11)){
						if((ARC[j][0]==ARC[k][1])||(ARC[j][1]==ARC[k][1])){
							ARC[j][2]=MAXINT;
						}
					}
				}//for(j=k+1;j<M;j++)
				//修改链表中的端点
				if(NO==00){
					p1->X=ARC[k][1];
				}
				else if(NO==01){
					p1->Y=ARC[k][1];
				}
				else if(NO==10){
					p2->X=ARC[k][0];
				}
				else if(NO==11){
					p2->Y=ARC[k][0];
				}
				break;

			case 2:	
				if(i!=N-1){
					switch(NO){
						case 0010:
							for(j=0;j<M;j++){
								if((p1->Y==ARC[j][0])&&(p2->Y==ARC[j][1])||
									((p1->Y==ARC[j][1])&&(p2->Y==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						case 0110:
							for(j=0;j<M;j++){
								if((p1->X==ARC[j][0])&&(p2->Y==ARC[j][1])||
									((p1->X==ARC[j][1])&&(p2->Y==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						case 0011:
							for(j=0;j<M;j++){
								if((p1->Y==ARC[j][0])&&(p2->X==ARC[j][1])||
									((p1->Y==ARC[j][1])&&(p2->X==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						case 0111:
							for(j=0;j<M;j++){
								if((p1->X==ARC[j][0])&&(p2->X==ARC[j][1])||
									((p1->X==ARC[j][1])&&(p2->X==ARC[j][0]))){
									ARC[j][2]=MAXINT;
								}
							}
							break;
						default:
							break;
					}
				}
				//从ARC数组中删除与当前弧的两个端点有关的边
				for(j=k+1;j<M;j++){
						if((ARC[j][0]==ARC[k][0])||(ARC[j][1]==ARC[k][0])){
							ARC[j][2]=MAXINT;
						}
						if((ARC[j][0]==ARC[k][1])||(ARC[j][1]==ARC[k][1])){
							ARC[j][2]=MAXINT;
						}
					}
				//修改链表
				if(NO==0010){
					p1->X=p2->Y;
				}
				else if(NO==0011){
					p1->X=p2->X;
				}
				else if(NO==0110){
					p1->Y=p2->Y;
				}
				else if(NO==0111){
					p1->Y=p2->X;
				}
				q=L;
				while((q->next)&&(q->next!=p2)){
					q=q->next;
				}
				q->next=p2->next;
				free(p2);
				break;//case 2
				

			default :
				printf("\nERROR!\n");
				break;
		}//switch()
		k++;
    }//for(i=1;i<=N;i++)
	free(L);
	free(q);
	free(p1);
	free(p2);
}


void Print(){
	int j;
	int i=0;
	int temp= (int)MAXINT;
	for(j=0;j<M;j++){
	   if(ARC[j][2]!=temp){
            i++;
       }
    }
    if(i!=N)
        {printf(" %d 数据有错误，无法每个城市都只经过一遍后回到原地！\n  ",i);}
    else {
	   for(j=0;j<M;j++){
		  if(ARC[j][2]!=temp){
			 printf("( %d,%d )",ARC[j][0],ARC[j][1]);			
		  }
	   }
	   printf("\n the length is %d \n",COST);
    }
}

void main(){
	order();
	greed();
	Print();
}