怎么制作网站来赚钱,国外网站做网站主播,室内设计学校推荐,带娃儿做的工作网站文章目录 第19章 程序设计19.1 模块19.1.1 内聚性与耦合性19.1.2 模块的类型 19.2 信息隐藏19.2.1 栈模块 19.3 抽象数据类型19.3.1 封装19.3.2 不完整类型 19.4 栈抽象数据类型19.4.1 为栈抽象数据类型定义接口19.4.2 用定长数组实现栈抽象数据类型19.4.3 改变栈抽象数据类型中… 文章目录 第19章 程序设计19.1 模块19.1.1 内聚性与耦合性19.1.2 模块的类型 19.2 信息隐藏19.2.1 栈模块 19.3 抽象数据类型19.3.1 封装19.3.2 不完整类型 19.4 栈抽象数据类型19.4.1 为栈抽象数据类型定义接口19.4.2 用定长数组实现栈抽象数据类型19.4.3 改变栈抽象数据类型中数据项的类型19.4.4 用动态数组实现栈抽象数据类型19.4.5 用链表实现栈抽象数据类型 19.5 抽象数据类型的设计问题19.5.1 命名惯例19.5.2 错误处理19.5.3 通用抽象数据类型19.5.4 新语言中的抽象数据类型 问与答写在最后 第19章 程序设计
——只要有模块化就有可能发生误解隐藏信息的另一面是阻断沟通。 实际应用中的程序显然比本书中的例子要大但你可能还没意识到会大多少。更快的CPU和更大的主存已经使我们可以编写一些几年前还完全不可行的程序。图形用户界面的流行大大增加了程序的平均长度。如今大多数功能完整的程序至少有十万行代码百万行的程序已经很常见甚至千万行以上的程序都听说过。 虽然C语言不是专门用来编写大型程序的但许多大型程序的确是用C语言编写的。这会很复杂需要很多的耐心和细心但确实可以做到。本章将讨论那些有助于编写大型程序的技术并且会展示C语言的哪些特性例如static存储类特别有用。 编写大型程序通常称为“大规模程序设计”与编写小型程序有很大的不同——就如同写一篇学期论文当然是双倍行距10页与写一本1000页的书之间的差别一样。大型程序需要更加注意编写风格因为会有许多人一起工作。需要有正规的文档同时还需要对维护进行规划因为程序可能会经历多次修改。 相比于小型程序编写大型程序尤其需要更仔细的设计和更详细的计划。正如Smalltalk编程语言的设计者Alan Kay所言“You can build a doghouse out of anything”。建造犬舍不需要任何特别的设计可以使用任何原材料但是对于人居住的房屋就不能这么干了后者要复杂得多。 第15章曾经讨论过用C语言编写大型程序但更多地侧重于语言的细节。本章会再次讨论这个主题并着重讨论好的程序设计所需要的技术。全面地讨论程序设计问题显然超出了本书的范围但我会尽量简要地涵盖一些在程序设计中比较重要的观念并展示如何使用它们来编写出易读、易于维护的C程序。 19.1节讨论如何将C程序看作一组相互提供服务的模块。随后会介绍如何使用信息隐藏19.2节和抽象数据类型19.3节来改进程序模块。19.4节通过一个示例栈数据类型展示了如何在C语言中定义和实现抽象数据类型。19.5节描述了C语言在定义抽象数据类型方面的一些局限并讨论了解决方案。 19.1 模块 设计C程序或其他任何语言的程序时最好将它看作一些独立的模块。模块是一组服务的集合其中一些服务可以被程序的其他部分称为客户使用。每个模块都有一个接口来描述所提供的服务。模块的细节包括这些服务自身的源代码都包含在模块的实现中。 在C语言环境下这些“服务”就是函数。模块的接口就是头文件头文件中包含那些可以被程序中其他文件调用的函数原型。模块的实现就是包含该模块中函数定义的源文件。
为了解释这个术语我们来看一下第15章中的计算器程序。这个程序由calc.c文件和一个栈模块组成。calc.c文件包含main函数栈模块则存储在stack.h和stack.c文件中见下面的图。文件calc.c是栈模块的客户文件stack.h是栈模块的接口它提供了客户需要了解的全部信息stack.c文件是栈模块的实现其中包括栈函数的定义以及组成栈的变量的声明。 #mermaid-svg-6W82W81R46Akaz09 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-6W82W81R46Akaz09 .error-icon{fill:#552222;}#mermaid-svg-6W82W81R46Akaz09 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-6W82W81R46Akaz09 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-6W82W81R46Akaz09 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-6W82W81R46Akaz09 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-6W82W81R46Akaz09 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-6W82W81R46Akaz09 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-6W82W81R46Akaz09 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-6W82W81R46Akaz09 .marker.cross{stroke:#333333;}#mermaid-svg-6W82W81R46Akaz09 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-6W82W81R46Akaz09 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-6W82W81R46Akaz09 .cluster-label text{fill:#333;}#mermaid-svg-6W82W81R46Akaz09 .cluster-label span{color:#333;}#mermaid-svg-6W82W81R46Akaz09 .label text,#mermaid-svg-6W82W81R46Akaz09 span{fill:#333;color:#333;}#mermaid-svg-6W82W81R46Akaz09 .node rect,#mermaid-svg-6W82W81R46Akaz09 .node circle,#mermaid-svg-6W82W81R46Akaz09 .node ellipse,#mermaid-svg-6W82W81R46Akaz09 .node polygon,#mermaid-svg-6W82W81R46Akaz09 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-6W82W81R46Akaz09 .node .label{text-align:center;}#mermaid-svg-6W82W81R46Akaz09 .node.clickable{cursor:pointer;}#mermaid-svg-6W82W81R46Akaz09 .arrowheadPath{fill:#333333;}#mermaid-svg-6W82W81R46Akaz09 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-6W82W81R46Akaz09 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-6W82W81R46Akaz09 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-6W82W81R46Akaz09 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-6W82W81R46Akaz09 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-6W82W81R46Akaz09 .cluster text{fill:#333;}#mermaid-svg-6W82W81R46Akaz09 .cluster span{color:#333;}#mermaid-svg-6W82W81R46Akaz09 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-6W82W81R46Akaz09 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} stack.h cal.c stack.c //stack.h
#include stdbool.h
void make_empty(void);
bool is_empty(void);
bool is_full(void);
void push(int i);
int pop(void);//cal.c
#include stack.h
int main(void){make_empty();...
}//stack.c
#include stack.h
int contents[100];
int top 0;
void make_empty(void){...
}
bool is_empty(void) {...
}
bool is_full(void) {...
}
void push(int i) {...
}
int pop(void) {...
}C库本身就是一些模块的集合。库中每个头都是一个模块的接口。例如stdio.h是包含输入/输出函数的模块的接口string.h是包含字符串处理函数的模块的接口。 将程序分割成模块有一系列好处: 抽象。如果模块设计合理则可以将其作为抽象对待。我们知道模块会做什么但不需要知道这些功能的实现细节。因为抽象的存在所以不必为了修改部分程序而了解整个程序是如何工作的。同时抽象让一个团队的多个程序员共同开发一个程序更容易。一旦对模块的接口达成一致实现每一个模块的责任可以被分派到各个成员身上。团队成员可以更大程度上相互独立地工作。可复用性。任何一个提供服务的模块都可能在其他程序中复用。例如我们的栈模块就是可复用的。由于通常很难预测模块的未来使用情况最好将模块设计成可复用的。可维护性。将程序模块化后程序中的错误通常只会影响一个模块实现因而更容易找到并修正错误。在修正了错误之后重建程序只需重新编译该模块实现然后重新链接整个程序即可。更广泛地说为了提高性能或将程序移植到另一个平台上我们甚至可以替换整个模块的实现。
上面这些好处都很重要但其中可维护性是最重要的。现实中大多数程序会使用许多年在使用过程中会发现问题并做一些改进以适应需求的变化。将程序按模块来设计会使维护更容易。维护一个程序就像维护一辆汽车一样修理轮胎应该不需要同时检修引擎。 我们就以第16章和第17章中的inventory程序为例。最初的程序参见16.3节将零件记录存储在一个数组中。假设在程序使用了一段时间后客户不同意对可以存储的零件数量设置固定的上限。为了满足客户的需求我们可能会改用链表17.5节就是这么做的。为了做这个修改需要仔细检查整个程序找出所有依赖于零件存储方式的地方。如果一开始就采用不同的方式来设计程序使用一个独立的模块来处理零件的存储就可能只需要重写这一个模块的实现而不需要重写整个程序。 一旦确定要进行模块化设计设计程序的过程就变成了确定究竟应该定义哪些模块每个模块应该提供哪些服务以及各个模块之间的相互关系是什么。现在就来简要地看看这些问题。如果需要了解程序设计的更多信息可以参考软件工程方面的图书比如Ghezzi、Jazayeri和Mandrioli的Fundamentals of Software Engineering。 19.1.1 内聚性与耦合性 好的模块接口并不是声明的随意集合。在设计良好的程序中模块应该具有下面2个性质: 高内聚性。模块中的元素应该彼此紧密相关。可以认为它们是为了同一目标而相互合作的。高内聚性会使模块更易于使用同时使程序更容易理解。低耦合性。模块之间应该尽可能相互独立。低耦合性可以使程序更便于修改并方便以后复用模块。
我们的计算器程序有这些性质吗实现栈的模块明显是具有内聚性的其中的函数表示与栈相关的操作。整个程序的耦合性也很低文件calc.c依赖于stack.h当然stack.c也依赖于stack.h但除此之外就没有其他明显的依赖关系了。 19.1.2 模块的类型 由于需要具备高内聚性、低耦合性模块通常分为下面几类: 数据池。数据池是一些相关的变量或常量的集合。在C语言中这类模块通常只是一个头文件。从程序设计的角度来说通常不建议将变量放在头文件中但建议把相关常量放在头文件中。在C库中float.h头23.1节和limits.h头23.2节都属于数据池。库。库是一个相关函数的集合。例如string.h头就是字符串处理函数库的接口。抽象对象。抽象对象是指对于隐藏的数据结构进行操作的函数的集合。本章中的术语“对象”含义与其他章中的不同。在C语言术语中对象仅仅是可以存储值的一块内存而在本章中对象是一组数据以及针对这些数据的操作的集合。如果数据是隐藏起来的那么这个对象是“抽象”的。我们讨论的栈模块属于这一类。抽象数据类型ADT。将具体数据实现方式隐藏起来的数据类型叫作抽象数据类型。客户模块可以使用该类型来声明变量但不会知道这些变量的具体数据结构。如果客户模块需要对这种变量进行操作则必须调用抽象数据类型模块所提供的函数。抽象数据类型在现代程序设计中起着非常重要的作用。我们会在19.3节~19.5节回过头来讨论。 19.2 信息隐藏 设计良好的模块经常会对它的客户隐藏一些信息。例如我们的栈模块的客户就不需要知道栈是用数组、链表还是其他形式存储的。这种故意对客户隐藏信息的方法叫作信息隐藏。信息隐藏有以下2大优点: 安全性。如果客户不知道栈是如何存储的就不可能通过栈的内部机制擅自修改栈的数据。它们必须通过模块自身提供的函数来操作栈而这些函数都是我们编写并测试过的。灵活性。无论对模块的内部机制进行多大的改动都不会很复杂。例如我们可以首先将栈用数组实现以后再改用链表或其他方式实现。我们当然需要重写这个模块的实现但只要模块是按正确的方式设计的就不需要改变模块的接口。
在C语言中强制信息隐藏的主要工具是static存储类型18.2节。将具有文件作用域的变量声明为static可以使其具有内部链接从而避免它被其他文件包括模块的客户访问。将函数声明为static也是有用的——函数只能被同一文件中的其他函数直接调用。 19.2.1 栈模块 为了清楚地看到信息隐藏所带来的好处下面来看看栈模块的两种实现。一种使用数组另一种使用链表。假设模块的头文件如下所示 //stack.h
#ifndef STACK_H
#define STACK_H #include stdbool.h /* C99 only */ void make_empty(void);
bool is_empty(void);
bool is_full(void);
void push(int i);
int pop(void); #endif首先用数组实现这个栈
#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(void)
{ top 0;
} bool is_empty(void)
{ return top 0;
} bool is_full(void)
{ return top STACK_SIZE;
} void push(int i)
{ if (is_full()) terminate(Error in push: stack is full.); contents[top] i;
} int pop(void)
{ if (is_empty()) terminate(Error in pop: stack is empty.); return contents[--top];
}组成栈的变量contents和top都被声明为static了因为没有理由让程序的其他部分直接访问它们。terminate函数也声明为static。这个函数不属于模块的接口相反它只能在模块的实现内使用。 出于风格的考虑一些程序员使用宏来指明哪些函数和变量是“公有”的可以在程序的任何地方访问哪些是“私有”的只能在一个文件内访问 #define PUBLIC /* empty */
#define PRIVATE static将static写成PRIVATE是因为static在C语言中有很多用法使用PRIVATE可以更清晰地指明这里它是被用来强制信息隐藏的。下面是使用PUBLIC和PRIVATE后栈实现的样子
PRIVATE int contents[STACK_SIZE];
PRIVATE int top 0; PRIVATE void terminate(const char *message) { ... } PUBLIC void make_empty(void) { ... } PUBLIC bool is_empty(void) { ... } PUBLIC bool is_full(void) { ... } PUBLIC void push(int i) { ... } PUBLIC int pop(void) { ... } 现在换成使用链表实现 //stack2.c
#include stdio.h
#include stdlib.h
#include stack.h struct node { int data; struct node *next;
}; static struct node *top NULL; static void terminate(const char *message)
{ printf(%s\n, message); exit(EXIT_FAILURE);
} void make_empty(void)
{ while (!is_empty()) pop();
} bool is _empty(void)
{ return top NULL;
} bool is_full(void)
{ return false;
} void push(int i)
{ struct node *new_node malloc(sizeof(struct node)); if (new_node NULL) terminate(Error in push: stack is full.); new_node-data i; new_node-next top; top new_node;
} int pop(void)
{ struct node *old_top; int i; if (is_empty()) terminate(Error in pop: stack is empty.); old_top top; i top-data; top top-next; free(old_top); return i;
}注意!!is_full函数每次被调用时都返回false。链表对大小没有限制所以栈永远不会满。程序运行时仍然可能不过可能性不大出现内存不够的问题从而导致push函数失败但事先很难测试这种情况。
我们的栈示例清晰地展示了信息隐藏带来的好处使用stack1.c还是使用stack2.c来实现栈模块无关紧要。这两个版本都能匹配模块的接口定义因此相互替换时不需要修改程序的其他部分。 19.3 抽象数据类型 作为抽象对象的模块像上一节中的栈模块有一个严重的缺点无法拥有该对象的多个实例本例中指多个栈。为了达到这个目的需要创建一个新的类型。 一旦定义了Stack类型就可以有任意个栈了。下面的程序片段显示了如何在同一个程序中有两个栈
Stack s1, s2; make_empty(s1);
make_empty(s2);
push(s1, 1);
push(s2, 2);
if (!is_empty(sl)) printf(%d\n, pop(s1)); /* prints 1 */ 我们并不知道s1和s2究竟是什么是结构还是指针但这并不重要。对于栈模块的客户s1和s2是抽象它只响应特定的操作make_empty、is_empty、is_full、push以及pop。
接下来将stack.h改成提供Stack类型的方式其中Stack是结构。这需要给每个函数增加一个Stack类型或Stack *的形式参数。stack.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);函数make_empty、push和pop参数的栈变量应为指针因为这些函数会改变栈的内容。is_empty和is_full函数的参数并不需要是指针但这里我们仍然使用了指针。给这两个函数传递Stack指针比传递Stack值更有效因为传递值会导致整个数据结构被复制。 19.3.1 封装 遗憾的是上面的Stack不是抽象数据类型因为stack.h暴露了Stack类型的具体实现方式因此无法阻止客户将Stack变量作为结构直接使用 Stack s1; s1.top 0;
s1.contents[top] 1;由于提供了对top和contents成员的访问模块的客户可以破坏栈。更糟糕的是由于无法评估客户的修改所产生的效果我们不能改变栈的存储方式。
我们真正需要的是一种阻止客户知道Stack类型的具体实现的方式。C语言对于封装类型的支持很有限。新的基于C的语言包括C、Java和C#对于封装的支持更好一些。 19.3.2 不完整类型 C语言提供的唯一封装工具为不完整类型incomplete type在17.9节和第17章最后的“问与答”部分简单提过。C标准对不完整类型的描述“描述了对象但缺少定义对象大小所需的信息。”例如声明 struct t; /* incomplete declaration of t */告诉编译器t是一个结构标记但并没有描述结构的成员。因此编译器并没有足够的信息来确定该结构的大小。这样做的意图是不完整类型会在程序的其他地方将信息补充完整。
不完整类型的使用是受限的。因为编译器不知道不完整类型的大小所以不能用它来声明变量
struct t s; /*** WRONG ***/但是完全可以定义一个指针类型引用不完整类型
typedef struct t *T;这个类型定义表明类型T的变量是指向标记为t的结构的指针。现在可以声明类型T的变量将其作为函数的参数进行传递并可以执行其他合法的指针运算指针的大小并不依赖于它指向的对象这就解释了为什么C语言允许这种行为。但我们不能对这些变量使用-运算符因为编译器对t结构的成员一无所知。 19.4 栈抽象数据类型
为了说明抽象数据类型怎样利用不完整类型进行封装需要开发一个基于19.2节描述的栈模块的栈抽象数据类型Abstract Data Type, ADT。这一过程中将用3种不同的方法来实现栈。 19.4.1 为栈抽象数据类型定义接口 首先需要一个定义栈抽象数据类型的头文件并给出代表栈操作的函数原型。现在将该头文件命名为stackADT.h。Stack类型将作为指针指向stack_type结构该结构存储栈的实际内容。这个结构是一个不完整类型在实现栈的文件中信息将变得完整。该结构的成员依赖于栈的实现方法。下面是stackADT.h文件的内容 /*
stackADT.h(版本1)
*/
#ifndef STACKADT_H
#define STACKADT_H #include stdbool.h /* since C99 */ typedef struct stack_type *Stack; Stack create(void);
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
bool is_full(Stack s);
void push(Stack s, int i);
int pop(Stack s); #endif包含头文件stackADT.h的客户可以声明Stack类型的变量这些变量都可以指向stack_type结构。之后客户就可以调用在stackADT.h中声明的函数来对栈变量进行操作。但是客户不能访问stack_type结构的成员因为该结构的定义在另一个文件中。
需要注意的是每一个函数都有一个Stack参数或返回一个Stack值。19.3节中的栈函数都具有Stack *类型的参数。导致这种差异的原因是Stack变量现在是指针指向存放着栈内容的stack_type结构。如果函数需要修改栈则改变的是结构本身而不是指向结构的指针。
同样需要注意函数create和destroy。模块通常不需要这些函数但抽象数据类型需要。create会自动给栈分配内存包括stack_type结构需要的内存同时把栈初始化为“空”状态。destroy将释放栈的动态分配内存。 下面的客户文件可以用于测试栈抽象数据类型。它创建了两个栈并对它们执行各种操作 /*
stackclient.c
*/
#include stdio.h
#include stackADT.h int main(void)
{ Stack s1, s2; int n; s1 create(); s2 create(); push(s1, 1); push(s1, 2); n pop(s1); printf(Popped %d from s1\n, n); push(s2, n); n pop(s1); printf(Popped %d from s1\n,n); push(s2, n); destroy(s1); while (!is_empty(s2)) printf(Popped %d from s2\n, pop(s2)); push(s2, 3); make_empty(s2); if (is_empty(s2)) printf(s2 is empty\n); else printf(s2 is not empty\n); destroy(s2); return 0;
}如果栈抽象数据类型的实现是正确的程序将产生如下输出
Popped 2 from s1
Popped 1 from s1
Popped 1 from s2
Popped 2 from s2
s2 is empty19.4.2 用定长数组实现栈抽象数据类型 实现栈抽象数据类型有多种方法这里介绍的第一种方法是最简单的。stackADT.c文件中定义了结构stack_type该结构包含一个定长数组记录栈中的内容和一个整数记录栈顶: /*
stackADT.c
*/
#include stdio.h
#include stdlib.h
#include stackADT.h #define STACK_SIZE 100 struct stack_type { int contents[STACK_SIZE]; int top;
}; static void terminate (const char *message)
{ printf(%s\n, message); exit(EXIT_FAILURE);
} Stack create(void)
{ Stack s malloc(sizeof(struct stack_type)); if (s NULL) terminate(Error in create: stack could not be created.); s-top 0; return s;
} void destroy(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.); s-contents[s-top] i;
} int pop(Stack s)
{ if (is_empty(s)) terminate(Error in pop: stack is empty.); return s-contents[--s-top];
}这个文件中的函数最显眼的地方是它们用-运算符而不是.运算符来访问stack_type结构的contents和top成员。参数s是指向stack_type结构的指针而不是结构本身所以使用.运算符是非法的。 19.4.3 改变栈抽象数据类型中数据项的类型 现在我们已经有了栈抽象数据类型的一个版本下面对其进行改进。首先注意到栈里的项都是整数太具有局限性了。事实上栈中的数据项类型是无关紧要的可以是其他基本类型float、double、long等也可以是结构、联合或指针。 为了使栈抽象数据类型更易于针对不同的数据项类型进行修改我们在 stackADT.h中增加了一行类型定义。现在用类型名Item表示待存储到栈中的数据的类型。
/*
stackADT.h(版本2)
*/
#ifndef STACKADT_H
#define STACKADT_H #include stdbool.h /* since C99 */ typedef int Item;
typedef struct stack_type *Stack; Stack create(void);
void destroy(Stack s);
void make_empty(Stack s);
bool is_empty(Stack s);
bool is_full(Stack s);
void push(Stack s, Item i);
Item pop (Stack s); #endif除新增了Item类型外push和pop函数也做了修改。push现在具有一个Item类型的参数而pop则返回Item类型的值。从现在起我们将使用这一版本的stackADT.h来代替先前的版本。
为了跟stackADT.h匹配stackADT.c文件也需要做相应的修改但改动很小。stack_type结构将包含一个数组数组的元素是Item类型而不是int类型
struct stack_type { Item contents[STACK_SIZE]; int top;
};push和pop的函数体部分没有改变相应的改变仅仅是把push的第二个参数和pop的返回值改成了Item类型。
stackclient.c文件可以用于测试新的stackADT.h和stackADT.c以验证Stack类型仍然可以很好地工作。确实如此现在就可以通过修改stackADT.h中Item类型的定义来任意修改数据项类型了。尽管我们不需要改变stackADT.c文件但仍然需要对它进行重新编译。 19.4.4 用动态数组实现栈抽象数据类型 栈抽象数据类型的另一个问题是每一个栈的大小的最大值是固定的目前设置为100。当然这一上限值可以根据我们的意愿任意增加但使用Stack类型创建的所有栈都会有同样的上限值。这样我们就不能拥有容量不同的栈了也不能在程序运行的过程中设置栈的大小。 有两种方法可以解决这个问题。一种方法是把栈作为链表来实现这样就没有固定的大小限制了。稍后我们将讨论这种方法下面先来看看另一种方法——将栈中的数据项存放在动态分配的数组17.3节中。
这种方法的关键在于修改stack_type结构使contents成员为指向数据项所在数组的指针而不是数组本身
struct stack_type { Item *contents; int top; int size;
};我们还增加了一个新成员size来存储栈的最大容量contents指向的数组长度。下面将使用这个成员检查“栈满”的情况。
create函数有一个参数指定所需栈的最大容量
Stack create(int size);调用create函数时它会创建一个stack_type结构和一个长度为size的数组。结构的contents成员将指向这个数组。
除了在create函数中新增size参数外文件stackADT.h和之前的一致。重新命名为stackADT2.h。但文件stackADT.c需要进行较多的修改:
/*
stackADT2.c
*/
#include stdio.h
#include stdlib.h
#include stackADT2.h struct stack_type { Item *contents; int top; int size;
}; static void terminate (const char *message)
{ printf(%s\n, message); exit(EXIT_FAILURE);
} Stack create(int size)
{ Stack s malloc(sizeof(struct stack_type)); if (s NULL) terminate(Error in create: stack could not be created.); s-contents malloc(size * sizeof(Item)); if (s-contents NULL) { free(s); terminate(Error in create: stack could not be created.); } s-top 0; s-size size; return s;
} void destroy(Stack s)
{ free(s-contents); 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;
} void push(Stack s, Item i)
{ if (is_full(s)) terminate(Error in push: stack is full.); s-contents[s-top] i;
} Item pop(Stack s)
{ if (is_empty(s)) terminate(Error in pop: stack is empty.); return s-contents[--s-top];
} 现在create函数调用malloc2次一次是为stack_type结构分配空间另一次是为包含栈数据项的数组分配空间。任意一处malloc失败都会导致调用terminate函数。destroy函数必须调用free函数两次来释放由create分配的内存。
stackclient.c文件可以再次用于测试栈抽象数据类型。但create函数的调用需要有所改变因为现在的create函数需要参数。例如可以将语句
s1 create();
s2 create();改为
s1 create(100);
s2 create(200);19.4.5 用链表实现栈抽象数据类型 使用动态分配数组实现栈抽象数据类型比使用定长数组更灵活但客户在创建栈时仍然需要指定其最大容量。如果使用链表来实现栈就不需要预先设定栈的大小了。 下面的实现与19.2节中的stack2.c文件相似。链表中的结点用如下结构表示
struct node { Item data; struct node *next;
};data成员的类型现在是Item而不是int但除此之外结构和之前是一样的。
stack_type结构包含一个指向链表首结点的指针
struct stack_type { struct node *top;
}; 乍一看这个结构似乎有点冗余我们可以简单地把Stack定义为struct node*同时让Stack的值为指向链表首结点的指针。但是我们仍然需要这个stack_type结构这样可以使栈的接口保持不变。如果不这样做任何一个对栈进行修改的函数都需要Stack *类型的参数而不是Stack参数。此外如果将来想存储更多的信息stack_type结构的存在可以简化对实现的修改。例如如果以后想给stack_type结构增加栈数据项的计数器可以很容易地为stack_type结构增加一个成员来存储该信息。
我们不需要对stackADT.h做任何修改。我们使用这个头文件不用 stackADT2.h。测试的时候仍然可以使用stackclient.c文件但需要做一些改动下面是新版本
/*
stackADT3.c
*/
#include stdio.h
#include stdlib.h
#include stackADT.h struct node { Item data; struct node *next;
}; struct stack_type { struct node *top;
}; static void terminate(const char *message)
{ printf(%s\n, message); exit(EXIT_FAILURE);
} Stack create(void)
{ Stack s malloc(sizeof(struct stack_type)); if (s NULL) terminate(Error in create: stack could not be created.); s-top NULL; return s;
} void destroy(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)
{ struct node *new_node malloc(sizeof(struct node)); if (new_node NULL) terminate(Error in push: stack is full.); new_node-data i; new_node-next s-top; s-top new_node;
} Item pop(Stack s)
{ struct node *old_top; Item i; if (is_empty(s)) terminate(Error in pop: stack is empty.); old_top s-top; i old_top-data; s-top old_top-next; free(old_top); return i;
}注意!!destroy函数在调用free函数释放stack_type结构所占的内存前先调用了make_empty释放链表中结点所占的内存。 19.5 抽象数据类型的设计问题
19.4节描述了栈抽象数据类型并介绍了几种实现方法。遗憾的是这里的抽象数据类型存在一些问题使其达不到工业级强度。下面一起来看看这些问题并探讨一下可能的解决方案。 19.5.1 命名惯例
目前的栈抽象数据类型函数都采用简短、便于记忆的名字create、destroy、make_empty、is_empty、is_full、push和pop。如果在一个程序中有多个抽象数据类型两个模块中就很可能有同名函数这样就会导致命名冲突。例如每个抽象数据类型都需要自己的create函数。所以我们可能需要在函数名中加入抽象数据类型本身的名字比如使用stack_create代替create。 19.5.2 错误处理 栈抽象数据类型通过显示出错消息或终止程序的方式来处理错误。这是一个不错的处理方式。程序员可以通过在每次调用pop之前调用is_empty以及在每次调用push之前调用is_full来避免从空栈中弹出数据项或者向满栈里压入数据项。因此从理论上来讲对pop和push的调用没有理由会出错。但在链表实现中调用is_full并没有效果后续调用push仍然可能出错。不过我们可能希望为程序提供一种从这些错误中恢复的途径而不是简单地终止程序。 一个可选的方案是让push和pop函数返回一个bool值说明函数调用是否成功。目前push的返回类型为void所以很容易改为在操作成功时返回true当栈已满时返回false。但修改pop函数就困难一些了因为目前pop函数返回的是弹出的值。如果让pop返回一个指向弹出的值的指针而不是返回该值本身那就可以让pop返回NULL来表示此时栈为空。
最后关于错误处理的一点评论C标准库包含带参数的assert宏24.1节可以在指定的条件不满足时终止程序。可以用该宏的调用取代目前栈抽象数据类型中使用的if语句和terminate函数的调用。 19.5.3 通用抽象数据类型 在19.4节中我们通过简化对存储在栈中的数据项类型的修改来改进栈抽象数据类型——我们需要做的工作只是改变Item类型的定义。这样做仍然有些麻烦如果栈能够适应任意类型的值而不需要改变stack.h文件会更好些。同时我们注意到现在的抽象数据类型栈还存在一个严重的问题程序不能创建两个数据类型不同的栈。创建多个栈很容易但这些栈中的数据项必须具有相同的类型。为了允许多个栈具有不同的数据项类型需要复制栈抽象数据类型的头文件和源文件并改变一组文件使Stack类型及相关的函数具有不同的名字。 我们希望有一个“通用”的栈类型可以用来创建整数栈、字符串栈或者需要的其他类型的栈。在C中有很多不同的途径可以做到这一点但没有一个是完全令人满意的。最常见的一种方法是使用void *作为数据项类型这样就可以压入和弹出任何类型的指针了。如果使用这种方法stackADT.h文件和我们最初的版本相似但push和pop函数的原型需要修改为如下形式
void push(Stack s, void *p);
void *pop(Stack s);pop返回一个指向从栈中弹出的数据项的指针如果栈为空则返回空指针。
使用void *作为数据项类型有2个缺点:
第一这种方法不适用于无法用指针形式表示的数据。数据项可以是字符串用指向字符串第一个字符的指针表示或动态分配的结构但不能是int、double之类的基本类型。第二不能进行错误检测。存放void *数据项的栈允许各种类型的指针共存因此无法检测出由压入错误的指针类型所导致的错误。 19.5.4 新语言中的抽象数据类型 上面讨论的问题在新的基于C的语言如C、Java和C#中处理得更好。通过在类中定义函数名可以避免命名冲突的问题。栈抽象数据类型可以用一个Stack类来表示栈函数都属于这个类而且仅当作用于Stack对象时才能被编译器识别。这些语言都提供了一种叫作异常处理exception handling的特性允许push和pop等函数在检测出错误时“抛出”异常。客户代码可以通过“捕获”异常来处理错误。C、Java和C#还专门提供了定义通用抽象数据类型的特性。例如在C中可以定义一个栈模板而不用指定数据项的类型。 问与答 问1本节中提到C语言不是为开发大型程序设计的。UNIX不是大型程序吗 答在C语言被设计出来时还不是。在1978年的一篇论文中Ken Thompson估计UNIX内核约有10000行C代码加上一小部分汇编代码。UNIX其他部分的大小也类似。在1978年的另一篇论文中Dennis Ritchie和他的同事将PDP-11的C编译器大小设定为9660行。按现在的标准这绝对只是小型程序。 问2C库中有什么抽象数据类型吗 答从技术上说没有。但有一些很接近包括FILE类型22.1 节定义在stdio.h中。在对文件进行操作之前必须声明FILE *类型的变量
FILE *fp;这个fp变量随后会被传递给不同的文件处理函数。
程序员需要把FILE作为一种抽象在使用时不需要知道FILE具体是怎样的。FILE可能是一个结构类型但C标准并不保证这一点。实际上最好不要管FILE值究竟是如何存储的因为FILE类型的定义对不同的编译器可能也确实经常是不一样的。
当然我们总是可以通过查看stdio.h文件来找到FILE到底是什么。如果这么做那么就没什么可以阻止我们编写代码来访问FILE的内部机制。例如我们可能发现FILE结构中有一个名为bsize文件的缓冲区大小的成员
typedef struct { ... int bsize; /* buffer size */ ...
} FILE; 一旦知道了bsize成员就无法阻止我们直接访问特定文件的缓冲区大小
printf(Buffer size: %d\n, fp-bsize);然而这样做并不好因为其他C编译器可能将缓冲区大小存储在其他名字中或者用不同的方式跟踪这个值。试图修改bsize成员则更糟糕
fp-bsize 1024;这是一件非常危险的事除非我们知道文件存储的全部细节。即使我们的确知道相关的细节不同的编译器或是同一编译器的新版本也可能不一样。 问3除了不完整结构类型还有别的不完整类型吗 答最常见的不完整类型之一出现于声明数组但不指定大小时
extern int a[]; 在这个声明第一次遇到这个声明是在15.2节之后a具有不完整类型因为编译器不知道a的大小。有可能a在程序的另一个文件中定义该定义补充了缺失的长度信息。
另一种不完整类型出现在没有指定数组的长度但提供了初始化器的数组声明中
int a[] {1, 2, 3}; 在这个例子中数组a刚开始具有不完整类型但初始化器使得该类型完整了。
声明联合标记而不指明联合的成员也会创建不完整类型。 弹性数组成员17.9节C99的特性就具有不完整类型。最后void也是不完整类型。void类型具有不同寻常的性质它永远不能变成完整类型因此无法声明这种类型的变量。 问4不完整类型在使用上有别的限制吗 答有下面这些限制
sizeof运算符不能用于不完整类型这不奇怪因为不完整类型的大小未知。结构或联合的成员弹性数组成员除外不可以具有不完整类型。类似地数据元素不可以具有不完整类型。最后函数定义中的形式参数不可以具有不完整类型在函数声明中可以。编译器会“调整”函数定义中的每个数组形式参数使其具有指针类型从而阻止其具有不完整类型。 写在最后 本文是博主阅读《C语言程序设计现代方法第2版·修订版》时所作笔记日后会持续更新后续章节笔记。欢迎各位大佬阅读学习如有疑问请及时联系指正希望对各位有所帮助Thank you very much
