第二章 数据抽象
库，是改进效率的最重要的方法。
2.1 声明与定义
声明：向计算机介绍名字；
定义：无论涉及变量还是函数，编译器都在“定义”处分配存储空间。前者由编译器在内存中产生存放变量的空间，后者由使用不带参数表或带地址操作符的函数名产生的指针为之分配存储空间。
定义可以是声明。
声明通常使用extern关键字。只声明变量而非定义它，则要求使用extern。
对函数，extern是可选的。不带函数体的函数名联通参数表或返回值，自动作为一个声明。
函数原型：包括关于参数类型和返回值的全部信息（如：int f(float, char);）。
C++要求必须写出函数原型。
2.2 袖珍C库
/*:LIB.H -- Header file : example C library */
/* Array-like entity created at run-time */
typedef struct STASHtag {
int size; /*Size of each space */
int quantity; /* Number of storage spaces */
int next; /* Next empty space */
/* Dynamically allocated array of bytes; */
unsigned char* storage;
}Stash;
void initialize(Stash* S, int Size);
void cleanup(Stash* S);
int add(Stash* S, void* element);
void* fetch(Stash* S, int index);
int count(Stash* S);
void inflate(Stash* S, int increase);
执行文件：
/*: LIB.C -- Implementation fo example C library */
/* Declare structure and funtions; */
#include "..\l\lib.h"
/* Error testing macros: */
#include <assert.h>
/* Dynamic memory allocation funtions: */
#include <stdlib.h>
#inlcude <string.h> /* memcpy() */
#include <stdio.h>
void initialize(Stash* S, int Size) {
S->size = Size;
S->quantity = 0;
S->storage = 0;
S->next = 0;
}
void cleanup(Stash* S) {
if(S->storage) {
puts("freeing storage");
free(S->storage);
}
}
int add(Stash* S, void* element) {
/* enough space left ? */
if(S->next >= S->quantity)
inflate(S, 100);
/* Copy element into storage, starting at next empty space; */
memcpy(&(S->storage[S->next * S->size]), element, S->size);
S->next++;
return (S->next -1); /*Index number*/
}
void* fetch(Stash* S, int index) {
if(index >= S->next || index < 0)
return 0; /*Not out of bounds ? *?
/*Produce pointer to desired element; */
return &(S->storage[index * S->size]);
}
int count(Stash* S) {
/* Number of elements in stash */
return S->next;
}
void inflate(Stash* S, int) {increase
void* v = realloc(S->storage, (S->quantity +increase) * S->size);
/* Was it successful ? */
assert(v);
S->storage = v;
S->quantity += increate;
}
动态内存分配函数（C库）包括：malloc()、calloc()、realloc()和free()。
其他概念：C堆管理器、assert()预处理宏；
测试该库：
/*: LIBTESTC.C -- Test demonstration library */
#include "..\l\lib.h"
#include <stdio.h>
#include <assert.h>
#define BUFSIZE 80
main() {
Stash intStash, stringStash;
int i;
File* file;
char buf[BUFSIZE];
char* cp;
/*......*/
initialize(&intStash, sizeof(int));
for(i = 0; i < 100; i++)
add(&intStash, i);
/* Holds 80-characters strings; */
initialize(&stringStash, sizeof(char) * BUFSIZE);
file = fopen("LIBTESTC.C", "r");
assert(file);
while(fgets(buf, BUFSIZE, file))
add(&stringStash, buf);
fclose(file);
for(i = 0; i < count(&intStash); i++)
printf("fetch(&intStash, %d) = &d\n", i, *(int*)fetch(&intStash, i));
i = 0;
while((cp = fetch(&stringStash, i++)) != 0)
printf("fetch(&stringStash, %d) = %s", i-1, cp);
putchar(‘\n‘);
cleanup(&intStash);
cleanup(&stringStash);
}
每个独立的C文件就是一个处理单元。
编译器能假设以int参数调用的函数有包含int的参数表，并据此处理它，这是很难发现的错误。
编译器创建目标文件。
目标文件：*.o或*.obj或类似的名字；
连接器将目标文件同必要地启动代码连接成可执行程序。连接期间，所有的外部引用都必须确定。
2.3 放在一起：项目创建工具
使用make程序来避免对所有文件重新编译：make比较源代码文件的日期和目标文件的日期，如果目标文件的日期比源代码文件的早，make就调用编译器处理该单元。
makefile是描述项目中所有文件之间关系的文本文件（类似于编译器经销商定义的项目文件）。
文件名：
C中：头文件是*.h，实现文件是*.c;
C++中：*.h， *.cpp。
2.4 什么是非正常
C中，使用库的最大障碍是名字冲突问题。
C对于函数使用单个名字空间。
2.5 基本对象
C++中，函数可以放在结构内部，作为“成员函数”。
//: LIBCPP.H -- C library converted to C++
struct stash {
int size; // Size of each space
int quantity; // Number of storage spaces
int next; // Next empty space
// Dyanmically allocated array of bytes:
unsigned char* storage;
//Funtions:
void initialize(int size);
int add(void* element);
void* fetch(int index);
int count();
void inflate(int increase);
};
C++中，编译器不要求创建typedef，而是直接把结构名转变为这个程序的新类型名。
使用范围分解运算符::，来避免本结构中的函数与其他结构中的函数相抵触。（如：stash::initialize(int Size, int quantity)）
//: LIBCPP.CPP -- C library converted to C++
//Declare structure and functions:
#include "..\l\libcpp.h"
#include <assert.h> // Error testing macros
#include <stdlib.h> // Dynamic memory
#include <string.h> // memcpy()
#include <stdio.h>
void stash::initialize(int Size) {
size = Size;
quantity = 0;
storage = 0;
next = 0;
}
int stash::cleanup() {
if(storage) {
puts("freeing storage");
free(storage);
}
}
int stash::add(void* element) {
if(next >= quantity) // Enough space left ?
inflate(100);
//Copy element into storage,
//starting at next empty space;
memcpy(&(storage[next * size]), element, size);
next++;
return(next - 1); // Index number
}
void* stash::fetch(int index) {
if(index >= next || index < 0)
return 0; // Not out of bounds ?
// Produce pointer to desired element:
return &(storage[index * size]);
}
int stash::count() {
return next; // Number of elements in stash
}
void stash::inflate(int increase) {
void* v = realloc(storage, (quantity + increase) * size);
assert(v);
storage = (unsigned char*)v;
quantity += increase;
}
其他概念：成员选择器；
在C++中，使用this指针产生这个struct的地址（如this->size = size）。
C允许任何指针赋一个void*(它是malloc()、calloc()和realloc()的返回)，而不需要计算。
void* v = realloc(S->storage, (S->quantity +increase) * S->size);
...
S->storage = v;
但类型在C++中是严格的，当类型信息有任何违例时，编译器就不允许。C++允许将任何类型的指针赋给void*(这是void*的最初意图，它要求void*足够大，以存放任何类型的指针)，但不允许将void*指针赋给任何其他类型的指针。此处严格指派为(unsigned char*)。
//: LIBTEST.CPP -- Test of C++ library
#include "..\l\libcpp.h"
#include <stdio.h>
#include <assert.h>
#define BUFSIZE 80
main() {
stash intStash, stringStash;
int i;
File* file;
char buf[BUFSIZE];
char* cp;
//.....
intStash.initialize(sizeof(int));
for(i = 0; i < 100; i++)
intStash.add(&i);
//Holds 80-character strings
stringStash.initialize(sizeof(char) * BUFSIZE);
file = fopen("LIBTEST.CPP", "r");
assert(file);
while(fgets(buf, BUFSIZE, file))
stringStash.add(buf);
fclose(file);
for(i = 0; i < intStash.count(); i++)
printf("intStash.fetch(%d) = %d\n", i, *(int*)intStash.fetch(i));
i = 0;
while((cp = (char*)stringStash.fetch(i)) != 0)
printf("stringStash.fetch(%d) = %s", i - 1, cp);
putchar(‘\n‘);
intStash.cleanup();
stringStash.cleanup();
}
其他概念：成员运算符（.）；
2.6 什么是对象
2.7 抽象数据类型（abstract data type）
封装：将数据连同函数捆绑在一起，继而允许创建新的类型。
object.member_funtion(arglist);//对一个对象“调用一个成员函数”
面向对象程序设计，总结为一句话，即是“向对象发送消息”；
2.8 对象细节
直接访问结构的字节，而不是使用标识符，不一定是效率最高的办法。
一个结构的大小是它所有成员大小的和（或略高于）。
example：
//:SIZEOF.CPP -- Sizes of structs
#include <stdio.h>
#include "..\l\lib.h"
#include "..\l\libcpp.h"
struct A {
int I[100];
}
struct B {
void f();
}
void B::f() {}
main() {
printf("sizeof struct A = %d bytes\n", sizeof(A)); //200,int占二个字节
printf("sizeof struct B = %d bytes\n", sizeof(B)); //最小的非零长度
printf("sizeof Stash in C = %d bytes\n", sizeof(Stash)); //后两者长度相同
printf("sizeof stash in C++ = %d bytes\n", sizeof(stash)); //C++尽力不增加任何花费
}
2.9 头文件的形式
C++中，头文件是是存放接口规范的唯一地方（不要源代码而使用库，只需要对象文件或库文件）。
基本原则：“只声明”；
典型的防止重复声明的方法是使用预处理器隔离该头文件。
#ifndef FOO_H_
#define FOO_H_
//Reset of Header here...
//endif //FOO_H_
注：不用前导下划线，因为标准C用前导下划线指明保留标识符。
2.10 嵌套结构
在全局名字空间之外为数据和函数取名字。
例子：用链接表方式实现一个栈
//: NESTED.H -- Nested(嵌套的) struct in linked list
#ifndef NESTED_H_
#define NESTED_H_
struct stack {
struct link {
void* data;
link* next;
void initialize(void* Data, link* Next);
} * head;
void initialize();
void push(void* Data);
void* peek(); //从栈顶返回data指针，但保留这个栈顶元素
void* pop(); //返回栈顶data指针，并去除栈顶元素
void cleanup();
};
#endif //NESTED_H_
注意：head指针紧接在struct link 声明之后定义，而不是单独定义link* head。(C文法)
//: NESTED.CPP -- Linked list with nesting
#include <stdlib.h>
#include <assert.h>
#include "nested.h"
void stack::link::initialize(void* Data, link* Next) {
data = Data;
next = Next;
}
void stack::initialize() { head = 0; } //空表
void push(void* Data) {
link* newlink = (link*)malloc(sizeof(link));
assert(nextlink);
newlink->initialize(Data, head);
head = newlink;
}
void* stack::peek() { return head->data; }
void* stack::pop() {
if(head == 0) return 0;
void* result = head->data;
link* oldHead = head;
head = head->next;
free(oldHead);
return result;
}
void stack::cleanup() {
link* cursor = head;
while(head) {
cursor = cursor->next;
free(head->data); //Assume a malloc !
free(head);
head = cursor;
}
}
测试例子：
//: NESTEST.CPP -- Test of nested linked list
#include "..\l\nested.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
main(int argc, char** argv){
stack textlines;
FILE* file;
char* s;
#define BUFSIZE 100;
char buf[BUFSIZE];
assert(argc == 2); // File name is agrument
textlines.initialize();
file = fopen(argv[1], "r");
assert(file);
//Read file and store lines in the stack
while(fgets(buf, BUFSIZE, file)) {
char* string = (char*)malloc(strlen(buf) + 1);
assert(string);
strcpy(string, buf);
textlines.push(string);
}
//Pop the lines from the stack and print them
while((s = (char*)textlines.pop()) != 0) {
printf("%s", s);
free(s);
}
textlines.cleanup();
}
注：文件是反序打印的。
其他概念：全局范围分解
例子：
//: SCOPERES.CPP -- Global scope resolution
int A;
void f() {}
struct S {
int A;
void f();
};
void S::f() {
::f(); // Would be recursive（递归） otherwise;
::A++; // Select the global A
A--; //The A at struct scope
}
main() {}
注：如果在S::f() 中没有范围分解，编译器会缺省的选择f() 和A的成员版本。
