数据抽象
如果你正在设计一个栈，目前这个栈只存放int数据，那么你会如何设计它呢？其实栈的结构并不复杂，我们在头脑中就能建立一个栈的模型，当然我们在纸上把它的结构画出来也许会更好一点：
这张图就是一个以数组实现的栈的模型，栈底的索引是0，Pointer是栈顶指针，它指向索引5这个位置，说明现在栈里刚好有5个元素，当Pointer指向索引0时，栈为空，表示栈里已经没有元素了，当Pointer指向索引9时（这个位置不属于我们，因为它超出了范围，而且在图里也没有，但可以猜到这个位置在索引8的上一个位置，在这里我们并没有使用这块内存，仅仅只是当做一个标致），表示栈已经满了（当然我们可以动态增加，比如利用realloc）。
一个栈我想应该实现这些功能吧：
1、入栈(Push)：把一个元素添加到栈顶的位置，并使栈顶指针向上移动一个位置。
2、出栈(Pop)：把一个元素从栈顶取出，并使栈顶指针向下移动一个位置。
3、获得栈顶元素(Peek)：把一个元素从栈顶取出，并不移动栈顶指针的位置。
注意：入栈时要检查栈是否已经满了，如果栈已经满了，输出信息提示用户，并不做任何操作。出栈和获得栈顶元素时要检查栈是否为空，如果栈为空，输出信息提示用户，不做任何操作并返回0（返回0的原因是大多时候它并不会造成一些错误，而且测试条件时也为假）。
可能还需要这样一些功能：
1、获得栈元素的数量(GetSize)：这个很简单，我们只需要返回栈顶指针对应的索引值就行了，它刚好是栈元素的数量。
2、获得栈底指针(GetBottomPointer)：返回这个数组的名字，它代表这个栈的底指针。
3、获得栈顶指针(GetTopPointer)：返回栈顶指针即可。
2和3可以用在遍历栈时用到，比如：
程序代码：int* bPointer = GetBottomPointer(&stack);
int* tPointer = GetTopPointer(&stack);
while (bPointer != tPointer) // (1)
printf("%d", *bPointer++);
// or
while (tPointer != bPointer) // (2)
printf("%d", *--tPointer);
(1)可以从栈底到栈顶遍历这个栈。(2)可以从栈顶到栈底遍历这个栈。
看来一共有6个函数：
1、void Push(Stack*)。
2、int Pop(Stack*)。
3、int Peek(Stack*)。
4、int GetSize(Stack*)。
5、int* GetTopPointer(Stack*)。
6、int* GetBottomPointer(Stack*)。
好了，可以写代码了：
程序代码：/**
* Stack.h
* Code by Kenier Lee.
*/
#ifndef _KENIER_LEE_STACK_H
#define _KENIER_LEE_STACK_H
#define STACK_SIZE 1024 /* Size of the Stack */
typedef struct StackTag Stack; /* Prepare type definition*/
struct StackTag {
int storage[STACK_SIZE]; /* Array of int */
int* tp; /* Top pointer */
};
void Push(Stack*, int);
int Pop(Stack*);
int Peek(Stack*);
int GetSize(Stack*);
int* GetTopPointer(Stack*);
int* GetBottomPointer(Stack*);
#endif /* _KENIER_LEE_STACK_H */这里栈的大小是1024，Stack里有一个字段是tp，它表示栈顶指针。程序代码：/**
* Stack.c
* Code by Kenier Lee.
*/
#include "Stack.h"
#include <stdio.h>
void InitStack(Stack* stack) {
stack-> tp = stack->storage;
}
void Push(Stack* stack, int value) {
int size = GetSize(stack);
if (size == STACK_SIZE) /* Full */
printf("Error: The stack is full.\n");
else
*stack->tp++ = value;
}
int Pop(Stack* stack) {
int value = 0;
if (stack->tp == stack->storage) /* Empty */
printf("Error: The stack is empty.\n");
else
value = *--stack->tp;
return value;
}
int Peek(Stack* stack) {
int value = 0;
if (stack->tp == stack->storage) /* Empty */
printf("Error: The stack is empty.\n");
else
value = *stack->tp;
return value;
}
int GetSize(Stack* stack) {
return stack->tp - stack->storage;
}
int* GetTopPointer(Stack* stack) {
return stack->tp;
}
int* GetBottomPointer(Stack* stack) {
return stack->storage;
}下面是测试代码，记得链接Stack.o程序代码：/**
* StackTest.c
* Code by Kenier Lee.
*/
#include "Stack.h"
#include <stdio.h>
int main(void) {
Stack stack;
int i, *tPointer, *bPointer;
InitStack(&stack);
for (i = 0; i < 10; ++i)
Push(&stack, i);
for (i = 0; i < 10; ++i)
printf("%d ", Pop(&stack));
printf("\n");
for (i = 0; i < 10; ++i)
Push(&stack, i);
printf("Sizeof stack: %d\n", GetSize(&stack));
tPointer = GetTopPointer(&stack);
bPointer = GetBottomPointer(&stack);
while (bPointer != tPointer)
printf("%d ", *bPointer++);
printf("\n");
bPointer = GetBottomPointer(&stack);
while (tPointer != bPointer)
printf("%d ", *--tPointer);
printf("\n");
for (i = 0; i < 10; ++i)
printf("%d ", Pop(&stack));
printf("\n");
printf("%d\n", Pop(&stack));
printf("%d\n", Peek(&stack));
return 0;
} /* Output:
9 8 7 6 5 4 3 2 1 0
Sizeof stack: 10
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
Error: The stack is empty.
0
Error: The stack is empty.
0
*/
这样的函数调用：InitStack(&stack);
Push(&stack, i);
Pop(&stack);
Peek(&stack);
GetSize(&stack);
GetTopPointer(&stack);
GetBottomPointer(&stack);
每个函数调用都需要传递Stack结构体的指针，更危险的是我们可以随意修改Stack里的所有字段，比如我们修改的tp字段的值，这样的修改显然是致命的，而我们无法阻止这些操作。在最开始调用任何函数之前必须先调用InitStack函数，不然可能会出现一些对话框，提示该内存不能为"write"或"read"（在Linux下面是段错误），这表示我们使用了不属于我们程序的内存，因为未初始化的tp的值是未知的。最后我们来看看Stack的C++版本：
程序代码：/**
* Stack.h
* Code by Kenier Lee.
*/
#ifndef _KENIER_LEE_STACK_H
#define _KENIER_LEE_STACK_H
class Stack {
public:
enum { STACK_SIZE = 1024 }; // Size of the Stack
Stack();
void push(int);
int pop();
int peek();
int getSize();
int* getTopPointer();
int* getBottomPointer();
private:
int storage[STACK_SIZE]; // Array of int
int* tp; // Top pointer
};
#endif // _KENIER_LEE_STACK_H不需要typedef，我们也不能直接修改tp的值了，因为它是私有的，我们能使用的只有从public:到private:之前的名字。程序代码：/**
* Stack.cpp
* Code by Kenier Lee.
*/
#include "Stack.h"
#include <iostream>
using namespace std;
Stack::Stack() {
tp = storage;
}
void Stack::push(int value) {
int size = getSize();
if (size == STACK_SIZE) /* Full */
cout << "Error: The stack is full." << endl;
else
*tp++ = value;
}
int Stack::pop() {
int value = 0;
if (tp == storage) /* Empty */
cout << "Error: The stack is empty." << endl;
else
value = *--tp;
return value;
}
int Stack::peek() {
int value = 0;
if (tp == storage) /* Empty */
cout << "Error: The stack is empty." << endl;
else
value = *tp;
return value;
}
int Stack::getSize() {
return tp - storage;
}
int* Stack::getTopPointer() {
return tp;
}
int* Stack::getBottomPointer() {
return storage;
}这是定义之前声明的那些成员函数，其中还有一个构造函数Stack()，它与类名相同，在创建Stack对象时它将被自动调用，它可以替代InitStack，而且比InitStack好，因为不用担心它不会被调用。程序代码：/**
* StackTest.cpp
* Code by Kenier Lee.
*/
#include "Stack.h"
#include <iostream>
using namespace std;
int main() {
Stack stack; // Constructor called
int i, *tPointer, *bPointer;
for (i = 0; i < 10; ++i)
stack.push(i);
for (i = 0; i < 10; ++i)
cout << stack.pop() << " ";
cout << endl;
for (i = 0; i < 10; ++i)
stack.push(i);
cout << "Sizeof stack: " << stack.getSize() << endl;
tPointer = stack.getTopPointer();
bPointer = stack.getBottomPointer();
while (bPointer != tPointer)
cout << *bPointer++ << " ";
cout << endl;
bPointer = stack.getBottomPointer();
while (tPointer != bPointer)
cout << *--tPointer << " ";
cout << endl;
for (i = 0; i < 10; ++i)
cout << stack.pop() << " ";
cout << endl;
cout << stack.pop() << endl;
cout << stack.peek() << endl;
} /* Output:
9 8 7 6 5 4 3 2 1 0
Sizeof stack: 10
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
9 8 7 6 5 4 3 2 1 0
Error: The stack is empty.
0
Error: The stack is empty.
0
*/
现在我们又看到了这样的调用：stack.push(i);
stack.pop();
stack.peek();
stack.getSize();
stack.getTopPointer();
stack.getBottomPointer();
我感觉这样要清晰得多，很容易看出这些操作是指对于那个对象的，并且如果你现在写这样的代码：stack.tp++ 或 stack.tp = 0 ... 等等修改tp字段值的操作都会被编译器看作是错误，因为tp被声明为私有的（只能在这个类的成员函数中使用），这样就安全多了。Stack stack;这句话被执行的时候，该类的构造函数Stack()就自动调用了，它完成了初始化的工作，不用担心初始化会被遗忘。
C++提供了一种，把函数与自定义数据类型绑定在一起的特性，这被称做数据抽象，而且上面的代码量明显要比前一个C版本的要少，语法更清楚，数据抽象的用途远不止这些，更多的特性，如果以后我有时间再与大家一一分享吧！
不知道看了这些代码之后同鞋们有没有兴趣去学习 C Plus Plus呢？
[ 本帖最后由 lz1091914999 于 2012-2-6 22:10 编辑 ]
