从C基本顺序表到C++基本顺序表类

在上一期的“数组和基本顺序结构”一文中我们讲到，优秀的程序员自觉地把函数分为基本操作函数和应用函数，然后把基本操作函数和基本顺序表结构看作一个整体，当作一个类型，用于应用函数即程序的设计和实现，表1简要概括了这些内容。

可是C语言编译器没有把这两类函数区别开，它们的声明、定义和调用方式都一样。不仅如此，它们对结构成员的访问权限也一样，应用程序可以直接访问结构成员，例如表1中的Purge函数可以修改为：

void Purge(SeqList *L)

//删除表中的重复数据

{

int i,j;

for(i=0;i＜L-＞size;i++) //直接访问结构成员size

{

j=i+1;

while(j＜L-＞size)

if(L-＞data[i]==L-＞data[j]) //直接访问结构成员data

Erase(L,j);

else

j++;

}

}

而c++编译器克服了C的局限性，实现程序员的设计方法，从概念和语法两个方面把两类函数区分开来。

1.从C基本顺序表到C++基本顺序表类的转换

下面我们分十步把表1中简化的C基本顺序表结构转化为C++基本顺序表类。

① 布尔型函数。C++增加了布尔型，它占用一个字节，仅取两个值：真和假(true和false)，对应的整型值是1和0。于是，对取真假值的函数，应将其返回值定义为布尔型。例如：

bool ListEmpty(const SeqList *l); //判空

② 将宏常量改为const常量。例如将

#define MaxSeqSize 100

改为

const int MaxSeqSize=100;

在C++中一般都用const常量或者枚举常量来代替宏常量，这是因为宏代表的是在预处理阶段完成的一种文本替换过程，它忽略了语言的作用域、类型系统和所有其他的语言特性和规则，这使它和语言本身割裂开来。

③ 常量型引用调用。把带有形式数据类型参量的值调用函数改为常量型引用调用[1]：

void InsertRear(SeqList *l, const Type& item); //尾插

④ 函数类型是常量型引用。若函数类型是形式数据类型，则将其改为常量型引用[1]：

const Type& GetData(const SeqList *l,int id); //取值

⑤ 重载。简化求长和判空等函数名：

int Size(const SeqList *l); //求长。取元素个数

bool Empty(const SeqList *l); //判空

在C语言中，函数名代表函数地址，因此不同的函数必须有不同的函数名，即使参数表不同而功能相同的函数，也要赋予不同的函数名。例如，在基本顺序表、基本顺序队列和基本顺序栈中的求长基本操作，虽然功能一样，但是函数名必须有别：

int ListSize(const SeqList *l); //基本顺序表求长

int QSize(const Queue *q); //基本顺序队列求长

int StSize(const Stack *s); //基本顺序栈求长

显然，这给程序设计和阅读带来不必要的麻烦。按照简约的习惯，功能相同的函数，即使参数表不同，也应具有相同的函数名，例如：

int Size(const SeqList *l); //基本顺序表求长

int Size(const Queue *q); //基本顺序队列求长

int Size(const Stack *s); //基本顺序栈求长

可是函数名相同而参数表不同的函数如何对应不同的地址呢？一种简单的方法是建立一个映射，使函数名和参数表对应一个新的函数名。这个映射是单一的：只要函数名和参数表有一处不同，所对应的新的函数名就不同。我们让这个新的函数名对应函数的地址，这项工作由C++编译器来完成。它根据参量表的参量个数和类型对函数名进行扩展，形成函数的内部名称，这个内部名称对应函数地址。例如，求长函数经编译器扩展后的内部名称可能是：

Size_const_SeqList*

Size_const_Queue*

Size_const_Stack*

当然，不同的编译器，扩展方法可能不同，但实质相同。

⑥ 成员函数。首先，将构造函数和基本操作函数参量表中的结构指针l改名为this，例如：

void SetList(SeqList *this); //给元素个数size赋值0

int Size(const SeqList *this); //求长

bool Empty(const SeqList *this); //判空

const Type GetData(const SeqList *this,int id);

//取值

void InsertRear(SeqList *this, const Type& item);

//尾插

void Delete(SeqList *this, int id); //定点删除

错误信息报告函数没有结构指针参量，需要补上(补上的this指针在定义中没有用，我们称它为哑元)，然后将函数名简化：

void Error(const SeqList *this,const char *c); //错误信息报告

接下来，将this指针隐藏，指向常量指针this的const修饰符移到参量表括号之后。最后，将构造函数和基本操作函数放入结构体内，成为结构的成员，称为成员函数，后带const修饰符的函数称为常量型成员函数：

const int MaxSeqSize=100;

struct SeqList

{

Type data[MaxSeqSize];

int size;

void SetList(void); //构造函数

int Size (void)const; //常量型成员函数

bool Empty(void)const;

void InsertRear(const Type& item);

const Type& GetData(int id)const; //常量型成员函数

void Erase(int id);

void Error(const char *c)const; //常量型成员函数

};

成员函数的调用方式发生变化，设L为表结构变量，原来是

ListSize(&L); //L基本顺序表结构变量

Erase(&L,1);

现在是

L.Size();

L.Erase(1);

设L为表结构指针，原来是

ListSize(L);

//L基本顺序表结构变量指针

Erase(L,1);

现在是

L-＞Size();

L-＞Erase(1);

C++编译器对新的调用方式在内部展开的过程与上面生成函数成员的过程正相反。例如：

L.Size();

内部展开过程首先是显示this指针参量，然后根据参量表扩展函数名，扩展之后，函数的内部原型可以假设是

int _ListSize(const SeqList*this);

然后调用形式为：

_ListSize(&L);

实质上与原来相同，但是意义大不一样：成员函数属于结构的成员，由结构变量负责调用，而且成员函数中隐藏的this指针就指向那个调用它的结构变量。

原来一个结构空间的大小是其数据成员空间大小之和，现在结构中包含了函数成员，是否结构空间就变大了？答案是没有。从图1演示的成员函数调用的内部过程我们不难理解，新的结构与原来的结构本质上是相同的，只是编译器的工作多了，函数和调用有了内部展开形式。

⑦ 成员函数定义。成员函数的定义可以在结构体内，也可以在结构体外。在结构体内定义，等于内联函数；在结构体外定义，等于函数类型标识符和函数名之间要加入结构名和域解析运算符“::”，以区别于一般的实用函数。在函数定义体内，this指针可以显示，也可以隐藏。

const int MaxSeqSize=100;

struct SeqList

{

Type data[MaxSeqSize];

int size;

void SetList(void);

int Size (void)const{return(size);} // return(this-＞size);

//在结构体内定义

bool Empty(void)const;

……

};

bool SeqList::Empty() const//在结构体外定义

{

return(size==0); //return(this-＞size==0);

}

⑧ 构造函数。现在从声明、定义和调用三个方面把基本操作函数与实用功能函数区分开了，接下来我们区分构造函数和基本操作函数。在基本顺序表中，构造函数的执行过程是：

Seqlis L;

SetList(&L); //调用构造函数

这两条语句是不能分开的，它们一起完成了基本顺序表的创建。C++把这两条语句合并为一条。具体方法是：把构造函数名和结构名统一，都是SeqList，使语句

Seqlis L;

蕴涵着调用构造函数。因为构造函数是基本顺序表定义的一部分，所以它的头应该是结构名称，不含返回值类型说明。又因为它的内容需要程序员定义，所以保留了函数体。

struct SeqList

{ ……

SeqList(void);//构造函数声明，名称与结构名称相同，而且取消了函数返回值类型

……

};

SeqList::SeqList (void) //构造函数外部定义

{

size=0; //this-＞size=0;

}

⑨ 访问权限。在基本顺序表中，各种函数都可以直接访问结构成员，没有区别。C++在结构中增加了访问权限，一般分私有和公有。私有成员只能由结构成员访问，即对结构成员公开，而结构以外的函数只能访问公有成员。公有部分是任何函数都可以直接访问或使用的，即对外公开、可见。

const int MaxSeqSize=100;

struct SeqList

{

private://私有声明

Type data[MaxSeqSize];

int size;

void Error(const char *c)const;//私有函数

public://公有声明

SeqList(void);//构造函数

int Size (void)const;

bool Empty(void)const;

void InsertRear(const Type& item);

const Type& GetData(int id)const;

void Erase(int id);

};

结构以外的函数“看不见”结构中的私有部分。例如，实用功能函数Purge是不能直接访问结构成员data、size和Error，只能通过公有成员函数来处理：

void Purge(SeqList *L)

//删除表中的重复数据

{

int i,j;

for(i=0;i＜L-＞Size();i++)

{

j=i+1;

while(j＜L-＞Size())

if(L-＞GetData(i)==L-＞GetData(j))

L-＞Erase(j);

else

j++;

}

}

⑩ new和delete运算符。构造函数的调用属于顺序表定义语句的一部分，意义是：谁创建顺序表空间，谁就负责调用构造函数给空间赋初值。这时，原有的动态分配函数malloc就不实用了。下面通过表2的对比来认识新的运算符new和delete。

与malloc不同，new负责调用构造函数。与free不同，delete释放动态数组空间要加下标运算符“[]”。

结构体包含成员函数之后，其关键字struct通常换为class，称为类，也可以沿用struct。它们的差别主要是：类(class)的默认项是私有的，在类中，私有成员的说明符private可以省略；而结构(struct)的默认项是公有的，公有成员的说明符public可以省略。何时用结构，何时用类？一般程序员的做法是：仅含公共数据成员，不含接口(即成员函数)时，采用结构，应用程序看到的即为数据成员的实际格式；否则采用类，数据成员的实际格式对外是不可见的、封装的，是可以改造的，应用程序只能通过接口(即公有成员函数)来操作数据成员。例如：

struct Student //结构

{

long ID; float g; //ID表示学号，g表示成绩

};

class SeqList //类

{

private://私有声明(可以省略)

Type data[MaxSeqSize];

int size;

void Error(const char *c)const; //私有函数

public://公有声明

SeqList(void);//构造函数

……

};

由类定义的变量通常称为对象。类的成员函数也称为方法，而且成员函数只能通过类的对象来调用。我们说基于对象的程序设计，就包含了这一层意思。例如：

L.Erase(1); //对象L调用成员函数Erase，删除第2个数据元素

但是，不能用这种方式调用构造函数，即

L.SeqList(); //非法

因为构造函数是用来创建对象的，此时L还不是也不能是对象。

2C++基本顺序表类的声明和实现

前面我们通过变换引入了C++顺序表类，表3和表4分别对比了C++基本顺序表类和C基本顺序表结构的声明和实现，表5对比了C++基本顺序表类应用程序和C基本顺序表结构应用程序。

参考文献

[1] 王立柱. C/C++与数据结构(第3版)(上册)[M]. 北京: 清华大学出版社, 2008.214,216.