程序设计

Optimization hinders evolution. ¹

程序设计

零前言

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

虽然 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++ 中我们可以定义一个模板，而不是指定数据项的类型。

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

Footnotes

优化阻碍进化。Epigrams on Programming 编程警句 ↩

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

20-程序设计.md

20-程序设计.md

程序设计

目录

程序设计

零前言

一模块

二信息隐藏

1. 栈模块

三抽象数据类型

1. 封装

2. 不完整类型

四栈抽象数据类型

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

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

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

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

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

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

1. 命名惯例

2. 错误处理

3. 通用抽象数据类型

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

Files

20-程序设计.md

Latest commit

History

20-程序设计.md

File metadata and controls

程序设计

目录

程序设计

零 前言

一 模块

二 信息隐藏

1. 栈模块

三 抽象数据类型

1. 封装

2. 不完整类型

四 栈抽象数据类型

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

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

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

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

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

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

1. 命名惯例

2. 错误处理

3. 通用抽象数据类型

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

Footnotes

零前言

一模块

二信息隐藏

三抽象数据类型

四栈抽象数据类型

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