从数组到C++顺序表类的对比概述

摘 要：程序语言的矛盾实际上是程序设计的矛盾，而存储与处理就是程序设计的基本矛盾。但是存储中包含处理，而存储中的数据就是被处理的对象。矛盾双方既是对立的，同时又统一的。从而可以清晰地对比出从数组到顺序表类的转换而带来的便利。

关键词：数据结构 数组 顺序表

中图分类号：TP311 文I标识码：A 文章编号：1672-3791（2018）02（c）-0001-02

Abstract：The contradiction of programming language is actually the contradiction of program design， and storage and processing is the basic contradiction of program design. But the storage contains processing， and the data stored is the object being processed. The two sides are both antagonistic and unified. This allows for a clear comparison of the convenience of converting from array to sequential table classes.

Key Words：Data structure；Arrya；Sequence table

数据结构是一组有组织的数据和对数据的基本操作，而算法是用基本操作表示的对数据进行处理有限的步骤。所以说算法是要依赖于数据结构的，而数组结构是为算法提供支持的。

在C语言的基本类型中，例如：char类型、double类型、float类型、int类型等，都含有对数据的基本操作。图1是删除数组中的重复的数据元素来说明数组的局限性。

从函数purge_array中可以看出，在对数组插入、删除、确定数组元素个数等的操作，都是经常使用的操作，但是这些基本操作并不是数组所固有的，此时基本操作的代码和算法的代码混在一起难以维护和阅读。我们需要做的就是把这些基本操作分别设计为基本函数。

1 C基本顺序表的局限性

我们要把对数组的基本操作独立出来和数组的定义绑定在一起，使它们近似成为一个类型来改进对数组的处理方式并不是一件容易的事情。比如往数组中插入一个数据元素需要经过以下几个步骤：（1）判断数组空间是否已满。需要确定数组元素的个数是否小于数组容量，如果数组已满，那么不能再插入。（2）检验插入位置。要求要插入的位置的下标大于0，但是同时也要保证不大于数据元素的个数。（3）只要不是在数组的末位插入数据元素那么还需要移动现有的数据元素。（4）插入之后数据的个数要加1。

从以上的步骤可以看出数组作为参数传递的是数组的地址，但是数组长度和数据元素个数不包含在内，还需要单独传递。只有把数组的首元素指针、数组长度和数据元素的个数等基本特征组织为一个整体才能设计出对数组的基本操作函数。因此得到一个被称作SeqList的结构，如图2所示。

我们要使这个SeqList结构在处理数组中起到作用就要使它具备基本的处理。但是语言内部类型的基本处理是用运算符来表示的，而SeqList结构的处理受到C语言的局限性限制只能用函数来表示[1]。我们把SeqList这个结构和基于SeqList结构体来设计对数组的基本操作的函数作为一个整体形成的数据结构叫做基本顺序表。图3为基本顺序表的声明。

从数组的角度来看，顺序表是一种新的发展了的存储结构，图4为删除C顺序表中的重复元素和删除数组中重复的元素的对比。

经过以上的对比我们会发现顺序表提升了C语言数组的抽象层次但是也能看出其固有的局限性：（1）函数和表达式的矛盾。在顺序表中，求长、判空等简单的表达式为了封装的原则都要用函数来表示，这样既占空间又费时间，执行速度慢。（2）数组元素的局限性。在顺序表中的数组元素是结构体时，如果含有逻辑运算符和关系运算符，那么基本操作函数都要修改，破坏了顺序表的复用性[2]。（3）实例化的局限性。顺序表只能实例化一次。（4）基本操作函数和算法很难区分。（5）结构体变量是浅复制的。在顺序表中，使用赋值运算符把一个顺序表变量的值复制给另一个顺序表变量会涉及到其包含的指针data。在复制时要把指针data本身的值和其所指向的空间同时复制给另一个指针。但是C语言只有浅复制，因此顺序表是不可以作为函数的参数的。

2 C++顺序表类的产生

由于C++编译器克服了C语言固有的局限性，因此，我们把C顺序表转换为C++顺序表类来使用。图5为C++顺序表类的声明同时实现了类内部分功能函数的实现。

通过以上的实例可以看出，在顺序表的基本操作函数转换成顺序表的成员函数之后，在定义、声明、调用等方面都能和算法区别开，由此可见C++顺序表类解决了C基本顺序表的局限性，突出了很多优点：（1）实现了代码和数据的抽象。C++是利用private、public、protected等不同关键字的访问权限来实现数据的抽象的。私有成员对成员函数公开，只能由成员函数来访问，因此对算法是不可见的。（2）从关键字struct到class的转换。class的默认项的访问权限是private的。（3）把Type值传递的方式改变为使用const引用传递。（4）把函数返回值类型Type改变为const引用的方式。

C++引入了类的创建机制，通过访问权限把类的数据成员封装起来，使数据的实际存储形式对类的用户是不可见的。

3 结语

程序是算法与数据结构的组成，这说明程序与数据结构是相辅相成不可分割的整体。顺序表虽然在很大程度上克服了这种局限性，但是其基本函数和应用函数在声明、实现、调用上没有区分开来，因此，我们要根据实际情况来应用。

参考文献

[1] 王立柱.C/C++与数据结构（上册）[M].3版.北京：清华大学出版社，2008：142，164.

[2] 严蔚敏，吴伟民.数据结构：C语言版[M].北京：清华大学出版社，2002.