由职工号、姓名排序查找问题

要求：

（1）输入职工号、姓名；

（2）按职工号的大小顺序，升序排序，姓名也随之调整；

（3）输入一个职工号，查找该职工，并输出职工号和姓名；

实现：

 （1）HalfFindElement（） --- 折半查找

 （2）SelectSort （）--- 选择排序

 （3）SortEmployeeByNumber（） --- 由职工号排序

 （4）FindEmployeeByNumber（） --- 由职工号查找该职工

/*******************************************************************************************
** 函数名称:  SelectSort()                      
** 作    者:  张月华                                                 
** 版    本:  1.0.0          
** 日    期:  2011-6-10                                                
** 功能描述:  选择排序法，对一个有N个元素的int型数组元素进行升序排序                                          
** 被本函数调用的函数清单: 无            
** 调用本函数的函数清单:   main()               
** 被访问的表:  无         
** 被修改的表:  无                          
** 输      入:  1. int  array_select[]。int型数组
                2. int element_amount。int变量，数组元素个数   
** 输      出:  无
** 返  回  值:  无                                            
** 其      他:  选择排序原理，以升序排序为例：
                1. 原数组元素： 9 8 5 4 6 0 
				2. 将 array[1]、array[2]、array[3]...中最小的元素和 array[0]交换 0 8 5 4 6 9  
				3. 将 array[2]、array[3]、array[4]...中最小的元素和 array[1]交换 0 4 5 8 6 9 
			    4. 将 array[3]、array[4]、array[5]...中最小的元素和 array[2]交换 0 4 5 8 6 9 
				……
				经过一轮的比较，最小的那个元素已经排在了最前面。
				这样，N个数经过N-1轮的比较，第i轮比较N-1-i次，即可完成排序。                                              
** 修 改 历史:                                        
                                                              
		1. 修改时间:
		   修 改 者:
		   版    本:
		   修改简述:
        2. ......
*********************************************************************************************/

void SelectSort(int array_select[], int n)
{
   int i;   /* 控制比较的外层循环，轮数 */
   int j;  /* 控制内层循环，每轮比较的次数 */
   int  t; /* 交换临时变量 */
   int  min_elment; /* 记录最小元素的下标 */
   
   for (i = 0; i < n - 1; i++)  /* N个数，要比较N-1轮 */
   {
	   min_elment = i;   /* 记录最小元素的下标 */

	   for (j = i + 1;j < n; j++) /* 第i轮要比较N-1-i次 */
	   {
		   		   
		   if ( array_select[j] < array_select[min_elment] )     /* 升序排列 */
			   min_elment = j;  /* 记录最小元素的下标 */

	   }  /* 注意这个for循环直到这里就结束了 */
	   

           if (min_elment != i)           
		   {
			                 t          = array_select[min_elment];
			   array_select[min_elment] = array_select[i];
			      array_select[i]       = t;
		   }
	   
   }

} 

/*******************************************************************************************
** 函数名称:  HalfFindElement()                                        
** 作    者:  张月华                             
** 版    本:  1.0.0                                              
** 日    期:  2011-6-16                                     
** 功能描述:  折半查找，返回元素的位置（从0开始计数，和数组下标一致）
** 被本函数调用的函数清单: 
** 调用本函数的函数清单:  1. main()                
** 被访问的表:  无                                   
** 被修改的表 : 无                            
** 输       入:  
                int array_in[] --- 输入数组，升序排列
				int element_amount --- 元素个数
				int key_in --- 欲查找的关键字                
** 输       出:  无                                                           
** 返  回   值:  查找到 -- 关键字的位置(标号和数组下标一致)  
                 没找到 -- 返回-1
                                                    
** 其       他:  	                            
** 修改历史:                                          
                                                             
		1. 修改时间:
		   修 改 者:
		   版    本:
		   修改简述:
        2. ......
*********************************************************************************************/

int HalfFindElement(int array_in[],int element_amount,int key_in)  /* array_in[]是升序数组 */
{
    int mid;      /* 折半查找的中间位置 */
	int top = 0;
	int bottom = element_amount - 1;
	int is_find = 0;  /* 查找到标识符。找到=1，否则=0 */
	int local ;  /* 找到的元素的位置 */

	if ((key_in < array_in[0]) || (key_in > array_in[element_amount - 1]) )  /* 再循环开始前就判断 */
      {
			local = -1;  /* 标记位置 */
            is_find = 0;  /* 没找到 */
      }

	while ( (is_find == 0) && (top <= bottom))
	{
		mid = (top + bottom) / 2;      

        if (key_in == array_in[mid])  /* 找到了 */
        {
            local = mid;  /* 标记位置 */
            is_find = 1;  /* 找到 */
        }

		else
			if (key_in < array_in[mid])
			{
				bottom = mid - 1;
			}
			else
			{
				top = mid + 1;
			}
	}

	if ((0 == is_find) || ( -1 == local))  /* 返回值 */
	{
		return -1;
	}
	
	else
		
		return local; /* 返回位置 */

}

/*******************************************************************************************
** 函数名称:  SortEmployeeByNumber()                                        
** 作    者:  张月华                             
** 版    本:  1.0.0                                              
** 日    期:  2011-6-16                                     
** 功能描述:  由职工号排序
** 被本函数调用的函数清单: 1.SelectSort(),调用选择排序法，对员工号进行排序
** 调用本函数的函数清单:                 
** 被访问的表:  无                                   
** 被修改的表 : 无                            
** 输       入:  
                struct employee array_in[] --- 输入的职工信息 (姓名和职工号)				
				int employee_amount  --- 职工人数             
** 输       出: struct employee array_out[] --- 排序后的结果(姓名和职工号)                                                           
** 返  回   值:  无                                                    
** 其       他:  	                            
** 修改历史:                                          
                                                             
		1. 修改时间:
		   修 改 者:
		   版    本:
		   修改简述:
        2. ......
*********************************************************************************************/

void SortEmployeeByNumber(struct employee array_in[],struct employee array_out[],int employee_amount)
{

	int liv_i;           /* 循环控制变量 */
	int liv_j;           /* 用来查找相等元素 */
	int number_sort[128];   /* 用来存放职工号,不能写成number_sort[employee_amount] */
	
	for (liv_i = 0; liv_i < employee_amount; liv_i++)
	{
      number_sort[liv_i] = array_in[liv_i].number;
	}
  
	SelectSort(number_sort, employee_amount) ;/* 调用排序法 */

	for (liv_i = 0; liv_i < employee_amount; liv_i++)
	{
		for (liv_j = 0; liv_j < employee_amount; liv_j++)  /* 查找相等的元素 */
		{
			if (number_sort[liv_i] == array_in[liv_j].number)
			{

			  array_out[liv_i].number = number_sort[liv_i];
			  strcpy(array_out[liv_i].name,array_in[liv_j].name);  			    

			}
		}
	}
}

/*******************************************************************************************
** 函数名称:  FindEmployeeByNumber()                                        
** 作    者:  张月华                             
** 版    本:  1.0.0                                              
** 日    期:  2011-6-16                                     
** 功能描述:  输入职工号，查找职工信息
** 被本函数调用的函数清单: 1.SelectSort(),调用选择排序法，对员工号进行排序
                           2.HalfFindElement(),调用折半查找法，进行查找
** 调用本函数的函数清单:                 
** 被访问的表:  无                                   
** 被修改的表 : 无                            
** 输       入: struct employee array_in[] --- 输入职工信息(姓名和学号)				
				int employee_amount --- 职工总数
				int key_number --- 欲查找的职工号
** 输       出: struct employee array_out[1] --- 输出查找结果                                                           
** 返  回   值:  无                                                    
** 其       他:  	                            
** 修改历史:                                          
                                                             
		1. 修改时间:
		   修 改 者:
		   版    本:
		   修改简述:
        2. ......
*********************************************************************************************/

void FindEmployeeByNumber(struct employee array_in[],struct employee array_out[1],int employee_amount,int key_number)
{

    int liv_i;           /* 循环控制变量 */
	
	int number_sort[128];   /* 用来存放职工号,不能写成number_sort[employee_amount] */
	int local;     /* 查找到得元素的下标，位置 */
 	
	for (liv_i = 0; liv_i < employee_amount; liv_i++)
	{
      number_sort[liv_i] = array_in[liv_i].number;
	}
  
	SelectSort(number_sort, employee_amount) ;/* 调用选择排序 */

    local = HalfFindElement(number_sort,employee_amount,key_number);  /* 调用折半查找 */

    if ( local == -1)  /* 没找到 */
    {
		exit(0);
    }
	else
	{
     
      array_out[0].number = key_number;                 /* 得到职工号 */
	  for (liv_i = 0; liv_i < employee_amount; liv_i++) /* 得到职工姓名 */
	  { 
		 if (array_in[liv_i].number == key_number)
		 {
            strcpy(array_out[0].name,array_in[liv_i].name);     
		 }

	  }

	}

}