众里寻他千百度

今天上完课回实验室后,把昨天面试的三道算法题,完完整整的全部自己重做实现了一遍(多种方法)

以下代码原则上,力争全部都是用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++]!='')   
    ;   
    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的文件目录

(手工判断找出的,用以与程序结果对照)

原文: 面试及总结2