之前看《算法导论》这本书，第一个算法就是（直接）插入排序，根据书里给出的伪代码写出了C语言代码，也根据自己的理解重新写了一个。虽然实现了算法的基本要求，但有些细节没有处理好，今天就来完善一下。
在昨天实现的代码中，用来测试的数组int array[] = {5,2,4,6,1,3};是固定的，如果要更换待排序数组话，原来程序中的相关变量就会因为数组长度的改变要做相应的改变。我想要的就是给定任意的数组，在不修改任意代码的条件下实现插入排序。所以，核心问题就是怎么获取给定数组中的元素个数。
自然而然想到的就是sizeof(C/C++中的一个操作符，其功能是返回一个对象或者类型所占的内存字节数)。
一、首先来看看怎么获取整数数组的长度
sizeof的语法形式如下：
（1）sizeof(object); // sizeof( 对象 );
（2）sizeof(type_name); // sizeof( 类型 );
（3）sizeof object;// sizeof 对象;
个人喜欢使用sizeof(object)的形式，因为形式统一，而且可以避免引起混乱导致出错。
假设有一给定数组 int array[] = {5,2,4,6,1,3};，length为数组array[]中的元素个数，那么
length = sizeof(array)/sizeof(*array); //表达式1
//length = sizeof(array)/sizeof(array[0]); //表达式2
//length = sizeof(array)/sizeof(int); //表达式3
上述三个表达式都能得到正确的结果，虽然表达式略有不同，但原理是相同的，即通过sizeof(array)获取整个数组所占的内存字节数，再通过sizeof(*array)或者sizeof(array[0])或者sizeof(int)来获取每个元素所占的字节数，数组所占的字节数除以每个元素所占的字节数就是该数组的元素个数了。
二、字符串数组长度的获取
char str[] = {"This is a string!"};
length = sizeof(str)-1;//包含空格
之所结果要减1，是因为字符串结束符'\0‘在数组中占用了一个字节。
三、源代码
/**************************************
*获取字符串长度（元素个数） By 羽墨
*print_length.c
***************************************/
#include <stdio.h>
void main()
{
int array[] = {5,2,4,6,1,3};
char str[] = {"This is a string!"};
int length = sizeof(array)/sizeof(*array);
printf("The length of string '%s' is %d\n",str,sizeof(str)-1);
printf("The length of array is %d\n",length);
}
运行结果
The length of string 'This is a string!' is 17
The length of array is 6
四、注意
1、如果在定义数组时就给定了数组的大小，如int array[len];，则不管数组中初始化了多少个（显然应不大于len）元素，最后的数组中的元素个数都是len。所以要想获得数组中真实元素的个数，在初始化数组时应注意这一点。
2、向子函数传递数组后，然后在子函数内部获取数组长度。先来看一个错误示例程序：
int getLength(int array[])
{
int length;
length=sizeof(array)/sizeof(array[0]);
return length;
}
len = getLength(array);
printf("The length of array is %d\n",len);
这样得到的结果始终都是1。因为数组作为参数传给函数时传的是指针而不是数组，传递的是数组的首地址。在本示例中，函数名array传递到子函数后就完全退化为一个指针，该指针指向的是数组array所在的地址，即数组array第一个元素array[0]所在的地址。也就是说系统只是告诉该函数这个存储空间存有数据，但并没有告诉函数这个数据存储空间有多大。sizeof(array)的结果是指针变量array所占内存的字节数，具体大小与系统有关，一般在32位机器上占4个字节，array[0]是int类型，同样占4个字节，所以结果为1。所以要获得数组的长度最好在数组定义所在的区域内。
对于上述情形，查阅资料后给出两种解决方案：
（1）进入子函数后用函数memcpy将数组拷贝出来，函数memcpy所需要的长度由另一个形参传递进来，像这样：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**************************************
*摘自360百科（稍作修改） By 羽墨
*将数组内容拷贝到函数内部
***************************************/
void fun(char *p, int len)
{
char *pData;
pData = (char*) malloc (len+1); //申请内存空间
memcpy(pData, p, len+1); //拷贝数组
printf("%s\n",pData);
//计算数组大小(略)
free(pData); //释放内存
pData = NULL;
}
void main ()
{
char str[] = {"This is a string!"};//初始化数组
fun(str, 17);
}
个人觉得没有必要怎么做。如果能够所需的长度作为形参传递到子函数中，显然就不需要在子函数当中另行计算，so，请看另一个方案。
（2）在子函数外部计算好元素个数后作为形参传递到子函数中进行其他操作。在这里仅给出（直接）插入排序算法的main函数，insert_sort(array,length)函数只需将子函数中用于记录数组元素个数的临时变量length放进子函数的参数列表即可。
void main()
{
int array[] = {5,2,4,6,1,3};
char str[] = {"This is a string!"};
int length = sizeof(array)/sizeof(*array); //计算数组中的元素个数
printf("The original");
print_array(array);
insert_sort(array,length); //插入排序
printf("The sorted");
print_array(array); //输出排序结果
}
这样一来，对于任意的目标序列都可以直接进行排序而不需要修改任何程序语句。
网友评论