C语言用libcstl实战

利用图结构计算城市之间的换乘线路

#include "libxl.h"
#include<stdio.h>
#include<string.h>
#include<cvector.h>
#define MAX_LENGTH 16
#define AP_COUNT 22
#define AL_COUNT 41

char ap_names[AP_COUNT][MAX_LENGTH];

vector_t *paths[AP_COUNT][AP_COUNT];
int matrix[AP_COUNT][AP_COUNT];
int matrix2[AP_COUNT][AP_COUNT];

int m_tmp[AP_COUNT][AP_COUNT];

void load_airport(BookHandle bookhd, int apname_index)
{
	int k;
	SheetHandle sheet = xlBookGetSheet(bookhd, apname_index);
	for(k = 0; k<AP_COUNT; ++k)
		strcpy(ap_names[k], xlSheetReadStr(sheet, k+1, 0, 0));
	
}

int get_apid(const char * name)
{
	int k;
	for(k=0;k<AP_COUNT&&strcmp(name,ap_names[k]);++k);
	if(k==AP_COUNT) {printf("[get_apid] 第%d个：%s 机场名称未找到。\n", k+1, name); return -1;}
	else return k;
}

int create_matrix(const char * data_path)
{
	int k;
	BookHandle book = xlCreateBook();
	if(book) {
		SheetHandle sheet;
		if(xlBookLoad(book, data_path)) {
			load_airport(book, 1);
//			for(k=0;k<AP_COUNT;++k)printf("%s\n",ap_names[k]);
			sheet = xlBookGetSheet(book, 0);
			if(sheet) {
				int elapse;
				int row, start, end;
				for(row=1; row<AL_COUNT; ++row)
				{
					start = get_apid(xlSheetReadStr(sheet, row, 0, 0));
					end = get_apid(xlSheetReadStr(sheet, row, 1, 0));
					elapse = xlSheetReadNum(sheet, row, 2, 0);
					if(start>=0 && end>=0)
					{
						if(matrix[start][end]==0 || matrix[start][end]>elapse)
						{
							matrix[start][end] = elapse;
						}
					}
//					else
//					printf("第%d行：从(%d)到(%d)经过%d分钟\n",row+1,start,end,elapse);
				}
			} else printf("Error when opening sheet0\n");
		} else printf("File cannot be opened.\n");
		xlBookRelease(book);
	} else printf("Can not createBook.\n");
}

int multiply()
{
	int i, j, k, flag = 0;
	printf("-");

	memcpy(m_tmp, matrix2, sizeof(m_tmp));
	for(i = 0; i < AP_COUNT; ++i)
	{
		for(j = 0; j < AP_COUNT; ++j)
		{
	 
			if(i == j || matrix2[i][j] > 0) continue;
			for(k = 0; k < AP_COUNT; ++k)
			{
				if(matrix2[i][k] > 0 && matrix[k][j] > 0)
				{
					int t;
					flag = 1;
					t = matrix2[i][k] + matrix2[k][j];
					// 对于矩阵中为0，或者矩阵大于t  
					if(m_tmp[i][j] == 0 || m_tmp[i][j] > t)
					{
//						memcpy(&paths[i][j][0], &paths[i][k][0], sizeof(int)*AP_COUNT);
//						paths[i][j][++paths[i][j][0]] = k;
						paths[i][j] = create_vector(int);
						if(paths[i][k]==NULL)
							vector_init(paths[i][j]);
						else
							vector_init_copy(paths[i][j], paths[i][k]);
						vector_push_back(paths[i][j], k);
						m_tmp[i][j] = t;  
					}
				}
			}
		}
	}
	memcpy(matrix2, m_tmp, sizeof(m_tmp));
	return flag;
}

int matrix_power()
{
	int k;
	int i ;
	memset(paths, 0, sizeof(paths));
	memcpy(matrix2, matrix, sizeof(matrix));
	for(k=1; k < AP_COUNT && multiply(); ++k);
	printf("完成%d 次幂运算。\n", k-1);
	return k;
}


int query()
{

	char from[MAX_LENGTH], to[MAX_LENGTH];
	int  from_id, to_id;
	//  118-130是为了得到机场的序号 
	do {
		printf("从哪里出发？请输入起始机场名称(q退出)："); 
		scanf("%s", from);
		if(!strnicmp(from, "q", 1)) return 0;
		from_id = get_apid(from);
	} while(from_id < 0);
	
	do {
	printf("请输入目的机场名称：");
	scanf("%s", to);
	to_id = get_apid(to);
	} while(to_id < 0);

	if(from_id == to_id) return 0;

	if(matrix2[from_id][to_id] > 0)
	{
		int k;
		if(paths[from_id][to_id]==NULL)
		{
			printf("从 %s 直达 %s 需要 %d 分钟\n", from, to, matrix2[from_id][to_id]);
		}
		else
		{
			int i ;
			for(i=0;i<vector_size(paths[from_id][to_id]);++i)
			{
				printf("%d",* (int *)vector_at(paths[from_id][to_id],i));
			}
			printf("=========================\n从 %s 到 %s 需要换乘 %d 次， %d 分钟\n",
				 from, to,
				vector_size(paths[from_id][to_id]), 
				 matrix2[from_id][to_id]);

			printf("换乘方案为：\n-------------------------\n"); 
			printf("\t%d: %s --> %s\t%d分钟\n", 1,
					ap_names[from_id], ap_names[* (int *)vector_at(paths[from_id][to_id],0)],
					matrix[from_id][* (int *)vector_at(paths[from_id][to_id],0)]);
			for(k=0; k<vector_size(paths[from_id][to_id]); ++k)
			{
				printf("%d",* (int *)vector_at(paths[from_id][to_id],k));
				int ap1, ap2;
				ap1 = * (int *) vector_at(paths[from_id][to_id],k);
				if(k<vector_size(paths[from_id][to_id]) && k+1 == vector_size(paths[from_id][to_id]))
				{
					ap2 = to_id ; 
				}
				else 
				{
					ap2 = * (int *) vector_at(paths[from_id][to_id],k+1) ;	
				}
				printf("\t%d: %s --> %s\t%d分钟\n", k+2,
					ap_names[ap1], ap_names[ap2], matrix[ap1][ap2]);
			}
		}
	}
	else
	{
		printf("从 %s 到 %s 没有航班以及换乘方案\n", from, to);
	}
	return 1;
}

int main()
{
	// 初始化邻接矩阵 
	memset(matrix, 0, sizeof(matrix));
	create_matrix("机场.xls");
	matrix_power();
	while(query());
	return 0;
	
}