从顺序表的算法看指针的妙用

By 祥泰

科学的发现往往是偶然的，我在研究算法的时候，发现了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语言的精髓所在！希望这种指针的用法可以对大家有所启示，以后可以通过它来提高程序执行效率和通用性。