C 语言中的 OOP - 归并排序算法

引言

面向对象编程（OOP）是一种众所周知的编程方法，得到了 C++、Java、C# 等一些主流编程语言的支持。这是我最常使用的编程方法。大部分时间，我使用 C++ 编程。

然而，OOP 的原则可以应用于任何语言。OOP 是一种思维方式，无论编程语言是否支持它，它都会影响编程的方式。

在这个实验中，我将 OOP 应用于用 C 编写程序。结果可能不是在 C 中实现它的理想方式，因为 C 是更接近硬件的程序的首选语言，并且在性能至关重要的情况下。通常，一方面是编写可重用代码，另一方面是满足高性能要求，这之间存在权衡。

代码

在这里，我试图遵循我的 OOP 习惯，而不试图让代码特别可重用，看看我能实现什么。

该程序演示了归并排序算法。它对无符号整数数组进行排序。程序基本上是对我的算法实现运行单元测试和黑盒测试。

• 下载地址： https://github.com/ariel1segal/mergesort/releases

或克隆 git 仓库

git clone https://github.com/ariel1segal/mergesort.git

代码具有 OOP 特征

• 一个对象来表示一个项目列表
• 构造函数
• 析构函数
• 比较操作的委托
• 算法的分解

所有这些功能都面向代码重用，但正如我上面提到的，这并不是 C 语言的直观编码方式。

在此情况下使用 OOP 原则的优点

让我们研究一下在这个特定的 C 程序中使用 OOP 原则的优点

对象构造函数/析构函数

对象类型被定义为这个简单的结构。

typedef struct
{
    unsigned size; // Length of list.
    unsigned *ar; // pointer to an unsigned int array.
} list_t;

显然，没有尝试支持不同的元素类型。元素仅通过构造函数创建，这些构造函数分配内存并初始化元素。

构造函数

list_t *CreateList(unsigned size, unsigned ar[]);
list_t *CreateEmptyList(unsigned size);
list_t *CloneList(list_t *orig);

构造函数的名称具有自解释性。

处理元素的唯一正确方法是使用析构函数

void DestroyList(list_t **list);

它首先释放为数组分配的内存，然后释放对象。

优点 1：线程安全的代码。在操作列表对象时，没有全局变量的访问。

比较操作的委托

用于排序元素的が基本操作是比较两个元素。此操作的委托泛化了要执行的排序类型。我在代码中提供了两个比较操作的实现。一个，为了降序排序，优先较大的值，另一个，为了升序排序，优先较小的值。所以总的来说，当比较两个元素时，该操作决定哪个元素在前。

委托通过函数指针完成。它被声明为一种类型

typedef compare_t (*compareFunction_t)(unsigned, unsigned);

compare 函数返回 compare_t 类型的值

typedef enum
{
    Tie_e
    , LeftWins_e
    , RightWins_e
} compare_t;

优点 2：代码在一定程度上可重用。重用代码来排序无符号整数以外的元素是一项更复杂的任务。这是一个例子，表明在编码时拥有 OOP 思维模式足以使代码的某些方面可重用。

算法分解

面向对象的思维方式促使将算法分解成更小的部分，使它们成为可以应用于对象的*操作*。算法的三个构建块是

• 比较 - 上面已讨论过，使用委托

其他两个不使用委托。

• 拆分 - 将一个列表分成两个列表，尽可能长度相同

  void SplitList(list_t *orig, list_t **left, list_t **right);

• 合并 - 将两个已排序的列表合并成一个已排序的列表

void MergeLists(list_t **merged, list_t *left, list_t *right,

compareFunction_t compare);

现在，伪代码中的排序算法看起来像这样

if list length is greater than 1
    split the list into left_list and right_list
    sort left_list // recursive call
    sort right_list // recursive call
    merge left_list and right_list into sorted list
    return sorted list
else if list length equals 1
    the list is sorted - return it

优点 3：更改代码以排序无符号整数以外的其他类型非常容易。只需更改 list_t 中数组的类型，并提供适当的比较函数。

此代码不可重用，因为

1. 必须更改代码才能将其用于其他类型。
2. 需要为程序需要的每种类型复制代码。

结论

OOP 关乎代码重用和易于维护。虽然维护性永远不应妥协，无论使用哪种编程语言，但对于 C 语言编写的大多数软件来说，代码重用都有一些缺点。正如我之前提到的，C 语言是必须满足严格性能要求的代码段的首选语言。在尝试将 OOP 原则应用于 C 语言时，我受到 C++ 的启发。C++ 实现的代码重用方式往往会降低性能。另一个问题是，OOP 设计往往会产生大量使用堆内存的代码，这可能不适合内存有限的系统。

将 OOP 应用于 C 的好处主要体现在代码重用的程度上，尽管我上面已经解释了为什么此代码不是真正可重用的。

OOP 的封装特性倾向于生成线程安全的代码，这对于 C 语言是首选的许多系统（例如实时应用程序）来说是一个巨大的优势。

下一步

在 C 语言中编写真正可重用的代码是否可能？

这样的代码必须遵循两条规则

1. 一段代码可以用于同一功能的多个实例，或用于多个执行线程。
2. 无需更改代码即可支持不同的数据类型。

这两条规则也衍生出可重用代码应支持同一程序中不同数据类型的多个实例的要求。

在我的下一篇文章中，我将尝试修改代码以使其更具可重用性。