20-程序设计

程序设计

Optimization hinders evolution. [^1]

程序设计

零前言

实际应用中的程序显然比本系列教学的例子要大，但是你可能不会意识到会大多少。如今，大多数功能完整的程序至少有十万行代码，百万行级的程序已经很常见。

虽然 C 语言不是专门用来编写大型程序的，但许多大型程序的确是用 C 编写的。

编写大型程序（通常称为“大规模程序设计”）与编写小程序有很大的不同——就如同写一篇学期论文与写一本长篇小说之间的差别一样。大型程序需要更加注意编写风格，因为会有很多人一起工作。需要有正规的文档，同时还需要对维护进行规划，因为程序可能会多次修改。

尤其是，相对于小型程序，编写大型程序需要更仔细的设计和更详细的计划。

一模块

设计 C 程序（或其他任何语言的程序）时，最好将它看作是一些独立的模块。模块是一组服务的集合，其中一些服务可以被程序的其他部分（称为客户）使用。每个模块都有一个接口来描述所提供的服务。模块的细节（包括这些服务自身的源代码）都包含在模块的实现中。

在 C 语言环境下，这些“服务”就是函数。模块的接口就是头文件，头文件包含那些可以被程序其他文件调用的函数的原型。模块的实现就是包含该模块中函数的定义的源文件。

比如，前面我们写的程序：文本格式化 中 line.h 和 word.h 就是接口，line.c 和 word.c 就是实现，包含 main 函数的 justify.c 为客户。

将程序分割成模块有一系列好处。

抽象。我们知道模块会做什么，但是不需要知道这些功能的实现细节。我们不必为了修改部分程序而了解整个程序是如何工作的。
可复用性。任何一个提供服务的模块都有可能在其他程序中复用。
可维护性。将程序模块化后，程序中的错误通常只会影响一个模块实现，因而更容易找到错误并修正错误。在修正了错误之后，重建程序只需要重新编译该模块实现（然后重新链接整个程序）。

比如我们以 inventory 程序为例。最初将零件记录存储在一个数组中。假设在程序使用一段时间后，客户不同意对零件存储数量设置固定的上限。为了满足客户需求，我们可能会改用链表。为了这个修改，需要仔细检查整个程序，找出所有依赖于零件存储方式的地方。如果一开始就采用了不同的方式来设计程序，我们可能只需要重写这一个模块的实现，而不需要重写整个程序。

一旦我们确定了要进行模块设计，设计程序的过程就变成了确定需要哪些模块，每个模块应该提供哪些服务，各个模块之间的相互关系是什么。

二信息隐藏

设计良好的模块经常会对它的客户隐藏一些信息。例如，我们的栈模块的客户就不需要知道栈是用数组，链表还是其他形式存储的。这种故意对客户隐藏信息的方法称为信息隐藏。信息隐藏有两大优点：

安全性。如果客户不知道栈是如何存储的，就不可能通过栈的内部机制擅自修改栈的数据。
灵活性。无论对模块的内部机制进行多大的改动，都不会很复杂。

C 语言中，强制信息隐藏的主要工具是 static 存储类型。将具有文件作用域的变量声明称 static 可以使其具有内部链接，从而避免它被其他文件（包含模块的客户）访问；将函数声明成 static 也可以使其具有内部链接，这样函数只能被同一文件中的其他函数直接调用。

1. 栈模块

为了清楚地看到信息隐藏所带来的好处，下面我们来看看栈模块的两种实现。一种使用数组，一种使用链表。我们假设模块的头文件如下所示：

stack.h

#ifndef STACK_H
#define STACK_H

#include<stdbool.h> //C99 only

void make_empty();
bool is_empty();
bool is_full();
void push(int i);
int pop();

#endif

数组实现：

stack1.c

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>
#include"stack.h"

#define STACK_SIZE 100

static int contents[STACK_SIZE];
static int top = 0;

static void terminate(const char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

void make_empty() {
	top = 0;
}

bool is_empty() {
	return top == 0;
}

bool is_full() {
	return top == STACK_SIZE;
}

void push(int i) {
	if (is_full())
		terminate("Error in push: stack is full\n");
	contents[top++] = i;
}

int pop() {
	if (is_empty())
		printf("Error in pop: stack is empty\n");
	return contents[--top];
}

组成栈的变量（contents 和 top）都被声明为 static 了，因为没有理由让程序的其他部分直接访问它们。terminate 函数也声明为 static 。这个函数不属于模块的接口；相反，它只能在模块的实现内使用。

我们可以用宏来指明那些函数和变量是公有的（程序的任何地方可以访问）或私有的（一个文件内访问）：

#define PRIVATE static
#define PUBLIC //empty

下面是使用 PUBLIC 和 PRIVATE 栈实现的样子：

PRIVATE int contents[STACK_SIZE];
PRIVATE int top = 0;

PRIVATE void terminate(const char* message) { ... }
PUBLIC void make_empty(){...}
PUBLIC bool is_empty() { ... }
PUBLIC bool is_full() { ... }
PUBLIC void push(int i) { ... }
PUBLIC int pop() { ... }

链表实现：

stack2.c

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include"stack.h"

typedef struct node {
	int data;
	struct node* next;
}node;

static node* top = NULL;

static void terminate(char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

void make_empty() {
	while (!is_empty())
		pop();
}

bool is_empty() {
	return top == NULL;
}

bool is_full() {
	return false;
}

void push(int i) {
	
	node* new_node = (node*)malloc(sizeof(node));
	if (new_node == NULL)
		terminate("Error in push: stack is full.\n");

	new_node->data = i;
	new_node->next = top;
	top = new_node;
}

int pop() {
	
	if (is_empty())
		terminate("Error in pop: stack is empty.\n");

	int data = top->data;
	
	node* del = top;
	top = top->next;
	free(del);

	return data;
}

三抽象数据类型

作为抽象对象的模块（比如上面的栈模块）有一个严重的缺点：无法拥有该对象的多个实例（本例中指多个栈）。为了达到这个目的，我们需要进一步创建一个新的类型。

Stack s1, s2;

make_empty(s1);
make_empty(s2);
...

我们不知道 s1 和 s2 究竟是什么（结构？指针？），但这并不重要。对于栈模块的客户，s1 和 s2 是抽象，它只响应特定的操作。

修改头文件：

stack2.h

#ifndef STACK2_H
#define STACK2_H

#define STACK_SIZE 100

typedef struct{
	int contents[STACK_SIZE];
	int top;
}Stack;

void make_empty(Stack* s);
bool is_empty(const Stack* s);
bool is_full(const Stack* s);
void push(Stack* s, int i);
int pop(Stack* s);

#endif

函数 make_empty, push 和 pop 参数的栈变量需要为指针，因为这些函数会改变栈的内容。is_empty 和 is_full 函数的参数并不需要为指针，但我们依然使用指针，因为传递 Stack 值会导致整个数据结构被复制。

1. 封装

遗憾的是，上面的 Stack 不是抽象数据类型，因为 stack2.h 暴露了 Stack 类型的具体实现方式，因此无法阻止客户将 Stack 变量作为结构直接使用：

Stack s1;

s1.top = 0;
s1.contents[top++] = 1;

所以，我们真正需要的是一种组织客户知道 Stack 类型具体实现的方式。C 语言对于封装类型的支持有限。新的基于 C 的语言（Java，C++ 和 C#）对于封装的支持更好一些。

2. 不完整类型

C 语言提供的唯一的封装工具为不完整类型（incomplete type）。C 标准对不完整类型的描述为：描述了对象但缺少定义对象大小所需的信息。例如，声明：

struct t;

告诉编译器 t 是一个结构标记，但没有描述结构的成员。所以编译器没有足够的信息去确定该结构的大小。这样做的意图是：不完整类型将会在程序的其他地方将信息补充完整。

不完整类型的使用是受限的。因为编译器不知道不完整类型的大小，所以它不能用于变量达到声明：

struct t s;// wrong

但是完全可以定义一个指针类型引用不完整的类型：

typedef struct t* T;

可以声明类型 T 的变量，将其作为函数的参数传递，并可以执行合法的指针运算（指针的大小不依赖于它所指向的对象，这就解释了为什么 C 语言允许这种行为。）。但是我们不能使用 -> 运算符。

四栈抽象数据类型

为了说明怎么利用不完整数据类型进行封装，我们需要开发一个基于前面描述的栈模块的栈抽象数据类型（Abstract Data Type，ADT）。这一过程中，我们将用 3 种不同的方法实现栈。

1. 为栈抽象数据类型定义接口

Stack 类型作为指针指向 stack_type 结构。这个结构是一个不完整类型，在实现栈的文件中信息将变得完整。

stackADT.h

#ifndef STACKADT_H
#define STACKADT_H

#include<stdbool.h>

typedef struct stack_type* Stack;

Stack create(); // 自动给栈分配内存，同时把栈化位空状态
void destory(Stack s);// 释放栈的动态内存分配
void make_empty(Stack s);
bool is_empty(const Stack s);
bool is_full(const Stack s);
void push(Stack s, int i);
int pop(Stack s);

#endif

包含头文件 stackADT.h 的客户就可以声明 Stack 类型的变量，这些变量都可以指向 stack_type 结构。之后客户就可以调用在 stackADT.h 中的函数来对栈进行操作。但是客户不能访问 stack_type 结构的成员，因为该结构定义在另一个文件中。

下面的客户文件可以用于测试栈抽象数据类型。

stackclient.c

#include<stdio.h>
#include"stackADT.h"

int main(void) {

	Stack s1, s2;

	s1 = create();
	s2 = create();

	push(s1, 1);
	push(s1, 2);
	
	printf("%d\n", pop(s1));
	printf("%d\n", pop(s1));

	destory(s1);
	destory(s2);

		return 0;
}

输出：

2
1

2. 使用定长数组实现栈抽象数据类型

stackADT.c

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include"stackADT.h"

#define STACK_SIZE 100

typedef struct stack_type {
	int contents[STACK_SIZE];
	int top;
}stack_type;



static void terminate(char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

Stack create() {
	
	Stack s = (Stack)malloc(sizeof(stack_type));
	if (s == NULL) {
		terminate("Error in create: stack could not be created.\n");
		exit(EXIT_FAILURE);
	}
	s->top = 0;
	
	return s;
}


void destory(Stack s) {

	free(s);
}


void make_empty(Stack s) {
	
	s->top = 0;
}

bool is_empty(Stack s) {
	return s->top == 0;
}

bool is_full(Stack s) {
	return s->top == STACK_SIZE;
}

void push(Stack s, int i) {
	
	if (is_full(s)) {
		terminate("Error in push: stack is full.\n");
		exit(EXIT_FAILURE);
	}

	s->contents[s->top++] = i;
}

int pop(Stack s) {
	
	if (is_empty(s)) {
		terminate("Error in pop: stack is empty.\n");
		exit(EXIT_FAILURE);
	}

	return s->contents[--s->top];
}

3. 改变栈抽象数据类型中的数据的类型

栈中的项都是整数，太具有局限性了。为了使栈抽象数据类更易于针对不同的数据项类型进行修改，我们在 stackADT.h 中增加了一行类型定义。现在用类型名 Item 表示存储到栈中的数据的类型。

stackADT2.h

#ifndef STACKADT2_H
#define STACKADT2_H

#include<stdbool.h>

typedef int Item;

typedef struct stack_type* Stack;

Stack create();
void destory(Stack s);
void make_empty(Stack s);
bool is_empty(const Stack s);
bool is_full(const Stack s);
void push(Stack s, Item i);
Item pop(Stack s);

#endif

修改 stackADT.c : 我们只需将 int 出现的地方换为 Item 即可：

typedef struct stack_type {
	Item contents[STACK_SIZE];
	int top; // 这个 int 无需修改
}stack_type;

void push(Stack s, Item i) {

	if (is_full(s)) {
		terminate("Error in push: stack is full.\n");
		exit(EXIT_FAILURE);
	}

	s->contents[s->top++] = i;
}

Item pop(Stack s) {

	if (is_empty(s)) {
		terminate("Error in pop: stack is empty.\n");
		exit(EXIT_FAILURE);
	}

	return s->contents[--s->top];
}

4. 用动态数组实现栈抽象数据类型

修改 stack_type 结构：

typedef struct stack_type {
	int top;
	int size;
	Item contents[]; // 柔性数组
}stack_type;

使 contents 成员为指向数据项所在数组的指针，而不是数组本身；增加 size 成员来存储栈的最大容量（contents 数组长度）。使用这个成员检测“栈满”情况。使用柔性数组可以减少 create 函数中的一次 malloc。（什么是柔性数组？https://mp.weixin.qq.com/s/FfNI5ooT75VyIdM9dmiq-A）

stackADT3.h

#ifndef STACKADT3_H
#define STACKADT3_H

#include<stdbool.h>

typedef int Item;

typedef struct stack_type* Stack;

Stack create(int size); // change
void destory(Stack s);
void make_empty(Stack s);
bool is_empty(const Stack s);
bool is_full(const Stack s);
void push(Stack s, Item i);
Item pop(Stack s);

#endif

stackADT3.c

修改的地方不多：

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include"stackADT3.h"


typedef struct stack_type {
	int top;
	int size;
	Item contents[]; // 柔性数组
}stack_type;



static void terminate(char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

Stack create(int size) {
	
	// sizeof(stack_type) 的大小不含有柔性数组
	Stack s = (Stack)malloc(sizeof(stack_type) + sizeof(Item) * size);
	if (s == NULL) {
		terminate("Error in create: stack could not be created.\n");
		exit(EXIT_FAILURE);
	}
	s->top = 0;
	s->size = size;

	return s;
}


void destory(Stack s) {

	free(s); // 柔性数组只需要释放一次
}


void make_empty(Stack s) {

	s->top = 0;
}

bool is_empty(Stack s) {
	return s->top == 0;
}

bool is_full(Stack s) {
	return s->top == s->size;// change
}

void push(Stack s, Item i) {

	if (is_full(s)) {
		terminate("Error in push: stack is full.\n");
		exit(EXIT_FAILURE);
	}

	s->contents[s->top++] = i;
}

Item pop(Stack s) {

	if (is_empty(s)) {
		terminate("Error in pop: stack is empty.\n");
		exit(EXIT_FAILURE);
	}

	return s->contents[--s->top];
}

事实上，你可以不使用柔性数组：create 函数先为结构变量整体 malloc，然后再为表示栈的数组 malloc 。同样，释放时也需要 2 次分步释放。

客户文件在调用 create 时需要给出栈的大小：

s1 = create(2);
s2 = create(2);

5. 使用链表实现栈抽象数据类型

链表中的结点用如下结构表示：

typedef struct node{
	int data;
	struct node* next;
}node;

为了使栈的接口不变，我们需要再定义一个包含指向链表首节点的结构：

typedef struct stack_type{
    node* top;
}stack_type;

stackADT4.h

#ifndef STACKADT4_H
#define STACKADT4_H

#include<stdbool.h>

typedef int Item;

typedef struct stack_type* Stack;

Stack create();
void destory(Stack s);
void make_empty(Stack s);
bool is_empty(const Stack s);
bool is_full(const Stack s);
void push(Stack s, Item i);
Item pop(Stack s);

#endif

stackADT4.c

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include"stackADT4.h"

typedef struct node{
	Item data;
	struct node* next;
}node;

typedef struct stack_type {
	node* top;
}stack_type;


static void terminate(char* message) {
	printf("%s\n", message);
	exit(EXIT_FAILURE);
}

Stack create() {
	Stack s = (Stack)malloc(sizeof(stack_type));
	if (s == NULL) {
		terminate("Error in create: stack could not be created.\n");
		exit(EXIT_FAILURE);
	}
	s->top = NULL;

	return s;
}

void destory(Stack s) {
	
	make_empty(s);
	free(s);
}



void make_empty(Stack s) {
	while (!is_empty(s))
		pop(s);
}

bool is_empty(Stack s) {
	return s->top == NULL;
}

bool is_full(Stack s) {
	return false;
}

void push(Stack s, Item i) {

	node* new_node = (node*)malloc(sizeof(node));
	if (new_node == NULL) {
		terminate("Error in push: stack is full.\n");
		exit(EXIT_FAILURE);
	}

	new_node->data = i;
	new_node->next = s->top;
	s->top = new_node;
}

Item pop(Stack s) {

	if (is_empty(s))
		terminate("Error in pop: stack is empty.\n");

	int data = s->top->data;

	node* del = s->top;
	s->top = s->top->next;
	free(del);

	return data;
}

五抽象数据类型的设计问题

前面描述了栈的抽象数据类型，并介绍了几种实现方法。遗憾的是，这里的抽象数据类型存储一些问题，使其达不到工业级强度。

1. 命名惯例

目前的栈抽象数据类型函数都采用简短，便于记忆的名字：create，destroy 等。如果一个程序中有多个抽象数据类型，两个模块中很可能具有同名函数，这样就出现了名字冲突。所以，我们可能需要在函数名中加入抽象数据类型本身的名字。

下面是修改后的部分头文件：

Stack stack_create();
void stack_destory(Stack s);
void stack_make_empty(Stack s);
bool stack_is_empty(const Stack s);
bool stack_is_full(const Stack s);
void stack_push(Stack s, Item i);
Item stack_pop(Stack s);

2. 错误处理

栈抽象数据类型通过显示出错误消息或终止程序的方式来处理错误。这是一个不错的方式，但是，我们希望为程序提供一种从这些错误中恢复的途径，而不是简单的终止程序。

一种方式是让 push 和 pop 函数返回一个 bool 类型的值说明函数调用是否成功。push 返回类型为 void，所以很容易改为成功时返回 true，失败时返回 false；但是修改 pop 就没那么简单了，因为目前 pop 是返回 Item 类型的值。如果让 pop 返回指向弹出的值的指针而不是数值，我们可以让 pop 返回 NULL 表示栈为空。

修改后的函数定义如下：

PUBLIC bool stack_push(Stack s, Item i) {

	node* new_node = (node*)malloc(sizeof(node));
	if (new_node == NULL)
		return false;

	new_node->data = i;
	new_node->next = s->top;
	s->top = new_node;

	return true;
}

PUBLIC Item* stack_pop(Stack s) {

	if (stack_is_empty(s))
		return NULL;

	node* del = s->top;
	s->pop_val = del->data;
	s->top = s->top->next;
	free(del);

	return &s->pop_val;
}

最后，C 库包含 assert 宏，可以在指定条件不满足时终止程序。我们可以用改宏的调用取代目前使用的 if 语句和 terminate 函数。

3. 通用抽象数据类型

现在的抽象数据类型栈还存在一个严重问题：程序不能创建两个数据类型不同的栈。

为了允许多个栈具有不同数据类型，我们可以复制栈抽象数据类型的头文件和源文件，并改变 Item 的类型定义，然后使 Stack 类型以及相关函数具有不同的名字。

我们希望有一个“通用”的栈类型。C 语言有很多不同的途径做到这一点，但是没有一个是令人满意的。最常见的一种方法是使用void*作为数据项类型，这样就可以使用各种类型的指针了。

只需要修改接口中的 push 和 pop 函数：

bool stack_push(Stack s, void* i);
void* stack_pop(Stack s);

那么程序应该如何改写呢？这个问题留给大家吧。

使用 void* 作为数据项类型有两个缺点：

这种方法不适用于无法用指针形式表示的数据
不能进行函数参数的错误检查

4. 新语言中的抽象数据类型

上面的问题在新的基于 C 的语言（C++，Java，C#）中处理的更好。

通过在类中定义函数可以避免名字冲突问题
这些语言都提供了一种称为异常处理的特性
专门提供了定义通用数据类型的特性。例如，在 C++ 中我们可以定义一个模板，而不是指定数据项的类型。

[^1]: 优化阻碍进化。Epigrams on Programming 编程警句

参考资料：《C语言程序设计：现代方法》

程序设计

目录

程序设计

零 前言

一 模块

二 信息隐藏

1. 栈模块

三 抽象数据类型

1. 封装

2. 不完整类型

四 栈抽象数据类型

1. 为栈抽象数据类型定义接口

2. 使用定长数组实现栈抽象数据类型

3. 改变栈抽象数据类型中的数据的类型

4. 用动态数组实现栈抽象数据类型

5. 使用链表实现栈抽象数据类型

五 抽象数据类型的设计问题

1. 命名惯例

2. 错误处理

3. 通用抽象数据类型

4. 新语言中的抽象数据类型

零前言

一模块

二信息隐藏

三抽象数据类型

四栈抽象数据类型

五抽象数据类型的设计问题