众里寻他千百度
今天上完课回实验室后，把昨天面试的三道算法题，完完整整的全部自己重做实现了一遍（多种方法）
以下代码原则上，力争全部都是用C语言实现，但考虑到扩展性和兼容性，算法1使用了模板
测试环境：VS2008
测试结果： 测试通过
/**** 欢迎访问杨刚的CSDN技术交流博客：http://blog.csdn.net/Sunboy_2050 ***/
/**************************************/
/***** 时 间：2010.6.28 ****/
/**************************************/
#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#include <string.h>
#include <io.h>
/**************************************/
/***** 面试题1：两数组归并排序 ****/
/**************************************/
template<typename T>
void PrintArray(T *array, int len)
{
int i;
for(i=0; i<len; i++)
{
printf("%6d", array[i]); /* printf("%6.2f", array[i]); printf("%6c", array[i]);*/
if(9==i%10) /* 每输出5个数据后，就换行 */
printf("\n");
}
printf("\n"); /* 数组全部输出后，换行 */
}
/******* 算法实现1： 升(降)序判定法，时间复杂度为O(n) *******/
template<typename T>
void MergySort(T *array1, int len1, T *array2, int len2, T *array3, int len3)
{
int i, j, k;
int flag1, flag2;
/* 记录数组Array1和Array2的升序或降序规则（首尾两个元素相比较） */
/* 表示规则：1表示升序，0表示降序 */
flag1=(array1[0]<array1[len1-1]) ? 1 : 0;
flag2=(array2[0]<array2[len2-1]) ? 1 : 0;
k=0; /* 目标数组Array3的下标初始化 */
/* if只比较一次，即进入for循环，因此时间复杂度为O（n） */
if(1==flag1 && 1==flag2) /* 升-升: 数组Array1升序，数组Array2升序，则数组Array3仍为升序 */
{
i=0;
j=0;
while(i<len1 && j<len2)
{
if(array1[i]<array2[j])
array3[k++]=array1[i++];
else
array3[k++]=array2[j++];
}
while(i<len1)
array3[k++]=array1[i++];
while (j<len2)
array3[k++]=array2[j++];
}
else if(1==flag1 && 0==flag2) /* 升-降: 数组Array1升序，数组Array2降序，则数组Array3仍为升序 */
{
i=0;
j=len2-1; /* 从末尾开始升序向前比较，依次都为升序进行排序 */
while (i<len1 && j>=0)
{
if(array1[i]<array2[j])
array3[k++]=array1[i++];
else
array3[k++]=array2[j--];
}
while(i<len1)
array3[k++]=array1[i++];
while (j>=0)
array3[k++]=array2[j--];
}
else if(0==flag1 && 1==flag2) /* 降-升: 数组Array1降序，数组Array2升序，则数组Array3仍为降序 */
{
i=0;
j=len2-1; /* 从末尾开始倒序向前比较，依次都为降序进行排序 */
while (i<len1 && j>=0)
{
if(array1[i]>array2[j])
array3[k++]=array1[i++];
else
array3[k++]=array2[j--];
}
while(i<len1)
array3[k++]=array1[i++];
while (j>=0)
array3[k++]=array2[j--];
}
else if(0==flag1 && 0==flag2) /* 降-降: 数组Array1降序，数组Array2降序，则数组Array3仍为降序 */
{
i=0;
j=0;
while (i<len1 && j<len2)
{
if(array1[i]>array2[j])
array3[k++]=array1[i++];
else
array3[k++]=array2[j++];
}
while(i<len1)
array3[k++]=array1[i++];
while (j<len2)
array3[k++]=array2[j++];
}
}
/* 归并两个有序数组（升序或降序）到一个大数组 */
void MergeArray()
{
/*************************************************/
/* 测试用例1：等价划分（升升、升降、降升、降降） */
/*************************************************/
/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={0,3,6,9,12};*/
int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={12,9,6,3,0};
/*int array1[10]={10,9,8,7,6,5,4,3,2,1};
int array2[5]={0,3,6,9,12};*/
/*int array1[10]={10,9,8,7,6,5,4,3,2,1};
int array2[5]={12,9,6,3,0};*/
int array3[15]={0};
/*************************************************/
/* 测试用例2：边界值分析（左边界、包含、右边界） */
/*************************************************/
/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={1,3,6,9,12};*/
/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={2,3,6,8,9};*/
/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={1,3,6,9,10};*/
/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={0,3,6,9,10};*/
/*int array1[10]={1,2,3,4,5,6,7,8,9,10};
int array2[5]={1,1,1,1,1};*/
/*int array1[10]={10,10,10,10,10,10,10,10,10,10};
int array2[5]={1,1,1,1,1};*/
/*int array1[10]={10,10,10,10,10,10,10,10,10,10};
int array2[5]={10,10,10,10,10};*/
//int array3[15]={0};
/*************************************************************/
/* 测试用例3：经验评估测试（浮点型、字符型等非整型异常数据） */
/*************************************************************/
/*float array1[10]={1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9, 10.0};
float array2[5]={1.2, 3.4, 6.7, 9.8, 12.0};
float array3[15]={0.0};*/
/*char array1[10]={'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
char array2[5]={'0', 'A', 'J', 'a', 'z'};
char array3[15]={0.0};*/
printf("\n有序数组Array1：\n");
PrintArray(array1, 10);
printf("\n有序数组Array2：\n");
PrintArray(array2, 5);
MergySort(array1, 10, array2, 5, array3, 15);
printf("\n归并Array1和Array2后的有序数组：\n");
PrintArray(array3, 15);
}
/****************************************************************/
/***** 面试题2：不借助第三方变量，交换两个整型数x和y的值 ****/
/****************************************************************/
void swap()
{
int x, y;
x=5;
y=10;
/*函数声明,引用传地址但未用第三方变量*/
void swap1(int &x, int &y); /* 方法1 */
void swap2(int &x, int &y); /* 方法2 */
void swap3(int &x, int &y); /* 方法3 */
printf("\n原始值：x=%d, y=%d\n", x, y);
swap3(x, y);
printf("\n交换后：x=%d, y=%d\n", x, y);
}
/****************************************/
/******* 方法1：算术运算(加减) *******/
/****************************************/
void swap1(int &x, int &y)
{
x=x+y; /* x存储x与y的和值（核心思想：x同时先把x和y两者的信息都存储下来） */
y=x-y; /* 保持x内存和值不变，y先赋值，即减去y的原始值使其等于x原始的值 */
x=x-y; /* 保持x内存和值不变，x再赋值，即减去y现在存储的原始x值，更新x值为原始y的值 */
}
/**************************************************************/
/******* 方法2：算术运算(乘除、指数运算、三角运算等) *******/
/**************************************************************/
void swap2(int &x, int &y)
{
x=x*y; /* x存储x与y的积值，核心思想同方法1，x同时先把x和y两者的信息都存储下来，本方法以乘除为例 */
y=x/y; /* 保持x内存积值不变，y先赋值，即除去y的原始值使其等于x原始的值 */
x=x/y; /* 保持x内存积值不变，x再赋值，即除去y现在存储的原始x值，更新x值为原始y的值 */
}
/****************************************/
/******* 方法3：逻辑运算(异或) *******/
/****************************************/
void swap3(int &x, int &y)
{
x^=y; /* x存储x与y的异或值（核心思想同上，即x先存储x和y两者信息（异或表示）） */
y^=x; /* 保持x内存和值不变，y先赋值，即利用x异或反转y的原始值使其等于x原始的值 */
x^=y; /* 保持x内存和值不变，x再赋值，即利用x异或反转y的原始值使其等于y原始的值 */
}
/*********************************************************/
/******* 方法4：Linux系统下，利用Python语言实现 *******/
/*********************************************************/
/********** 源代码 **********/
/*
# !/bin/sh/python
# FileName: swap.py
# Function: swap x and y not by other variable
x=5
y=10
print("swap before...")
print("x=%d, y=%d") % (x,y)
x,y=y,x # swap x and y
print("swap after...")
print("x=%d, y=%d") % (x,y)
*/
/********** 编译方法 **********/
/*
说明：
编译环境：Redhat Linux Server 5.2
代码工具：vim文本编辑器
因为绝大部分Linux系统在安装时都会默认自带安装python
在python语言中，#表示注释
第一行 # !/bin/sh/python 告诉系统：编译此py文件的解释器路径，来编译此py源文件
第二行 Filename 注释表示此程序的文件名称为 swap.py，文件执行时不执行
第三行 Filename 注释表示此程序实现的功能，即不利用其它变量交换x和y的值
具体编译运行方法
1、登陆进入Linux系统的终端 Shell 命令界面
2、python swap.py
*/
/********** 运行结果 **********/
/*
[root@localhost python]# python swap.py
swap before...
x=5, y=10
swap after...
x=10, y=5
*/
/****************************************************************/
/***** 面试题3：统计单词出现过的文件，并给出其文件名 ****/
/****************************************************************/
/* 查找匹配文件中是否包含word单词，如果第一次查找匹配成功，则立即返回文件名 */
const char *Find_Word(const char *filePath, const char *word)
{
FILE *pf=NULL;
const char *pword=word;
char ch;
int i, len, flag;
if (NULL==(pf=fopen(filePath, "r"))) /* 判断是否成功以只读方式打开文件 */
{
printf("Sorry! Cannot open file...\n");
return NULL;
}
i=0;
while (pword[i++]!='\0')
;
len=i-1;
i=0;
flag=1;
ch=fgetc(pf);
while(ch!=EOF) /* 循环单个字符读取文件 */
{
if(ch==' ') /* 英文单词以空格分隔，每当遇到空格，则flag=1表示开始匹配新单词 */
{
flag=1;
ch=fgetc(pf);
continue;
}
if(ch==pword[i] && i<len) /* 依次匹配单个字符，成功 */
i++;
else /* 匹配失败，则重置i=0 */
{
i=0;
flag=0;
}
if(i>=len && flag) /* 如果全部匹配成功，则i>=len 返回文件名 */
{
fclose(pf); /* 关闭打开文件 */
pf=NULL; /* 防止野指针 */
return filePath;
}
ch=fgetc(pf);
}
fclose(pf);
pf=NULL;
return NULL;
}
/* 遍历文件夹下的所有*.txt格式文件 */
void Search_TxtFiles(const char *dirPath, const char *word)
{
char *filePath=NULL;
const char *findFileName=NULL;
struct _finddata_t c_file;
long hFile;
if((hFile=_findfirst("*.txt", &c_file))==-1)
{
printf( "There is no *.txt files in current directory!\n" );
return;
}
else
{
printf( "\nListing of files\n" );
printf( "\n%-12s %9ld\n", c_file.name, c_file.size );
findFileName=Find_Word(c_file.name, word); /* 读取第一个文件 */
if(NULL!=findFileName)
printf("\n\n%s is found in file: %s\n\n", word, findFileName);
while( _findnext( hFile, &c_file ) == 0 ) /* 循环读取其它剩余文件 */
{
printf( "\n%-12s %9ld\n", c_file.name, c_file.size );
findFileName=Find_Word(c_file.name, word);
if(NULL!=findFileName)
printf("\n\n%s is found in file: %s\n\n", word, findFileName);
}
_findclose( hFile );
}
printf("\n");
}
/* 显示目录文件夹下（相对路径）所有包含单词word的文件名（*.txt） */
void Display_FileName()
{
char *dirPath="..\\..\\data\\txt\\*.txt";
char *word="baidu"; /* 匹配文件中是否含有baidu的单词 */
Search_TxtFiles(dirPath, word);
}
/* 主函数，实现面试三道C语言算法题 */
int _tmain(int argc, _TCHAR* argv[])
{
MergeArray(); /* 算法题1： 归并两个有序数组（升序或降序） */
swap(); /* 算法题2： 不借助第三方变量，交换两个整型数x和y的值 */
Display_FileName(); /* 算法题3： 统计单词出现过的文件，并给出其文件名 */
return 0;
}
运行结果：
实际result文件记录的包含baidu的文件目录 （手工判断找出的，用以与程序结果对照）
