|
|
科学的发现往往是偶然的，我在研究算法的时候，发现了C语言指针的另类用法，技巧令人拍案叫绝，欲知详情，请看下文。
首先，先看一下下面的这段代码：
//定义顺序表的元素类型。应根据需要修改
typedef int DataType;
struct SeqList
{ int MAXNUM； //顺序表中最大元素的个数
int n; //存放线性表中元素的个数n≤MAXNUM
DataType *element; //element[0],element[1]，…，element[n - 1]存放//线性表中的元素
}；
这段代码摘自张乃孝《算法与数据结构》一书。
很明显，这是用顺序表示的线性表的数据结构，其中DataType *element这一行代码的含义开始的时候自己是看不懂的，觉得弄那么复杂干啥？后来经过再三的分析，终于明白了。
它的含义：定义一个指向DataType类型的指针变量，实质是利用了指针可以引用（表示）一个数组首地址的性质，所以这里实际上相当于定义了一个数组的首地址，但这个数组没有定义它的大小。后面要用数组来存放数据时只要用element[0],element[1]……表示即可。
我个人是非常佩服这样的算法技巧，相当巧妙。为了做对比，我就把目前主流的顺序表数据结构的定义算法放上来。代码如下：
顺序表类型定义
#define ListSize 100 //表空间的大小可根据实际需要而定，这里假设为100
typedef int DataType; //DataType的类型可根据实际情况而定，这里假设为int
struct SeqList{
DataType data[ListSize]；//向量data用于存放表结点
int length；//当前的表长度
}；
看出了吧，这里都是直接在初始化时把数据存放的空间定死了，就是ListSize 100个DataType数据的空间。
下面对这两段代码做一个比较。
第一种用指针来实现数组的定义，它可以在程序的运行中根据程序的需要，例如根据用户输入的数据量m，一次性定义一个可以存放m个数据的空间。第二种的方法直接在程序代码中限制死了空间的大小，由于很多时候人们为了考虑出现数据量大的情况，所以一般这个空间设置得比较大，这样容易导致内存空间的浪费。
读者可能会问，这样又有什么作用？
可能对于现在的计算机来说，内存已经是很大的了，省这一点空间没有什么的。但我想说的是，假如用在内存资源奇缺的单片机上呢？用在小内存的手机上呢？例如51单片机的内存空间才是512B，这样的情况下，省一点空间就是效率。况且对于算法来说，高效率而占用空间小永远是它的改进方向。
或者有人会说，不用指针，直接定义一个数组DataType element[m]，其中的m的值通过程序运行时再给定。其实，我很遗憾的告诉你，绝大多数的编译器对于数组定义时候，一定要给出一个确定值的，这样的语法是有问题的，所以还是建议你搞好C语言的基础再说吧。
除了上面的不同外，还有一点是他们的创建表的操作也是不一样的。
对于第二种来说，十分简单，创建的代码只用一句就行了：
struct SeqList Seq
但对于第一种来说，多了一个动态分配空间的过程，代码如下：
PSeqList createNullList_seq(int m ) {
// 创建新的顺序表
PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList));
if (palist!=NULL){
palist->element = (DataType*)malloc(sizeof(DataType)*m);
if (palist->element){
palist->MAXNUM=m;
palist ->n = 0; // 空表长度为0
return (palist);
}
else free (palist);
}
printf(“Out of space!!\n”); // 存储分配失败
return NULL;
}
代码的含义是根据需要来创建一个可以存放m个DataType数据类型的数据空间。核心代码是palist->element = (DataType*)malloc(sizeof(DataType)*m);
没看懂的好好体会一下。
通过以上这两种算法的分析，再一次见证了指针的威力，不愧为C语言的精髓所在！希望这种指针的用法可以对大家有所启示，以后可以通过它来提高程序执行效率和通用性。 |
|
发表于 2011-1-20 16:36:59
