使用Cmockery和TDD开发的栈结构和基本算法
继续敲入Cmockery的include头文件，熟悉Cmockery和部分TDD；栈Stack是程序开发中非常常用的一种数据结构，比如涉及到函数调用的程序，在调用其它的函数时，需要保存自己的寄存器内容，并将被调用函数需要的参数传递过去，这些都是通过栈来实现的。
一. 还是先考虑下大概的接口：
除了create，destroy，length以及is_empty外，还有：
push(Stack, Element) 将元素加入至Stack的尾端
pop(Stack) 从栈中弹出最后的元素
top(Stack) 获取栈中的最后元素
二. 基于Cmockery框架编写Stack接口的测试程序：
#include <stdarg.h>
#include <stddef.h>
#include <setjmp.h>
#include <cmockery.h>
#include "./stack_list.h"
#ifdef WIN32
#pragma comment(lib, "D:/Code_Lib/cmockery/windows/cmockery.lib")
#endif
void create_test(void **state)
{
Stack stack = create();
assert_false(!is_empty(stack));
assert_int_equal(length(stack), 0);
destroy(stack);
}
void push_test(void **state)
{
int i;
Stack stack = create();
for(i=0; i<5; i++)
{
push(stack, i*10+1);
assert_int_equal(length(stack), i+1);
assert_int_equal(top(stack), i*10+1);
}
destroy(stack);
}
void pop_test(void **state)
{
int i,j;
Stack stack = create();
for(i=0; i<5; i++)
{
push(stack, i*10+1);
}
for (j=0; j<5; j++)
{
assert_int_equal(pop(stack), (4-j)*10+1);
assert_int_equal(length(stack), 4-j);
}
destroy(stack);
}
int main(int argc, char* argv[])
{
const UnitTest tests[] = {
unit_test(create_test),
unit_test(push_test),
unit_test(pop_test),
};
return run_tests(tests);
};
三. 完成Stack的接口：
typedef int ElementType;
typedef struct TNode
{
ElementType data;
struct TNode* next;
} Node;
typedef Node* Stack;
Stack create();
// free whole spaces of the stack, not only the head
void destroy(Stack stack);
int is_empty(Stack stack);
int length(Stack stack);
void push(Stack stack, ElementType ele);
ElementType pop(Stack stack);
// only return the top element, not pot out
ElementType top(Stack stack);
四. 编写实现：基于链表结构
#include "./stack_list.h"
#include <stdlib.h>
Stack create()
{
Node* node = (Node*)malloc(sizeof(Node));
node->next = 0;
return node;
}
void destroy(Stack stack)
{
if (!is_empty(stack))
pop(stack);
free(stack);
}
int is_empty(Stack stack)
{
if (stack->next)
return 0;
else
return 1;
}
int length(Stack stack)
{
int num=0;
Node* node = stack;
while (node->next)
{
++num;
node = node->next;
}
return num;
}
void push(Stack stack, ElementType ele)
{
Node* node = stack;
Node* nnode = (Node*)malloc(sizeof(Node));
nnode->data = ele;
nnode->next = 0;
while (node->next)
node = node->next;
node->next = nnode;
}
ElementType pop(Stack stack)
{
Node* node = stack;
Node* last = 0;
ElementType ele;
if (!node->next) /* empty stack */
return 0;
while(node->next->next)
node = node->next;
last = node->next;
ele = last->data;
free(last);
node->next = 0;
return ele;
}
ElementType top(Stack stack)
{
Node* node = stack;
if (!node->next) // empty stack
return 0;
while (node->next)
node = node->next;
return node->data;
}
五. 测试通过了；Review一下代码，发现push和pop的效率都不好，究其原因，是在实现链表栈时，push和pop操作都在linked list的尾部进行，这样的时间复杂度为O(N)，而如果将push和pop放在linked list的头部进行，则可将时间复杂度变位常数；我们重构实现如下：
#include "./stack_list.h"
#include <stdlib.h>
Stack create()
{
Node* node = (Node*)malloc(sizeof(Node));
node->next = 0;
return node;
}
void destroy(Stack stack)
{
if (!is_empty(stack))
pop(stack);
free(stack);
}
int is_empty(Stack stack)
{
if (stack->next)
return 0;
else
return 1;
}
int length(Stack stack)
{
int num=0;
Node* node = stack;
while (node->next)
{
++num;
node = node->next;
}
return num;
}
void push(Stack stack, ElementType ele)
{
Node* node = stack;
Node* nnode = (Node*)malloc(sizeof(Node));
nnode->data = ele;
nnode->next = node->next;
node->next = nnode;
}
ElementType pop(Stack stack)
{
Node* node = stack;
Node* last = 0;
ElementType ele;
if (!node->next) /* empty stack */
return 0;
last = node->next;
ele = last->data;
node->next = last->next;
free(last);
return ele;
}
ElementType top(Stack stack)
{
Node* node = stack;
if (!node->next) // empty stack
return 0;
return node->next->data;
}
六. 至此，这个过程结束。
七. 考虑基于数组的实现，这也是最常用的实现方式，接口如下：
// stack_array.h
#define MAX_LENGTH 100
typedef int ElementType;
typedef struct TDStack
{
int top_index;
ElementType* data;
} TStack;
typedef TStack* Stack;
Stack create();
void destroy(Stack stack);
int length(Stack stack);
int is_empty(Stack stack);
void push(Stack stack, ElementType ele);
ElementType pop(Stack stack);
ElementType top(Stack stack);
八. 数组实现：
#include "./stack_array.h"
#include <stdlib.h>
Stack create()
{
Stack stack = (Stack)malloc(sizeof(TStack));
stack->top_index = -1;
stack->data = (ElementType*)malloc(sizeof(ElementType)*MAX_LENGTH);
return stack;
}
void destroy(Stack stack)
{
stack->top_index = -1;
free(stack->data);
free(stack);
}
int length(Stack stack)
{
return stack->top_index+1;
}
int is_empty(Stack stack)
{
if (stack->top_index>=0)
return 0;
else
return 1;
}
void push(Stack stack, ElementType ele)
{
if (stack->top_index+1 >= MAX_LENGTH)
{
return; // is full
}
++stack->top_index;
stack->data[stack->top_index] = ele;
}
ElementType pop(Stack stack)
{
ElementType ele;
if (stack->top_index < 0)
{
return 0; // is empty
}
ele = stack->data[stack->top_index];
--stack->top_index;
return ele;
}
ElementType top(Stack stack)
{
if (stack->top_index < 0)
return 0; //is empty
return stack->data[stack->top_index];
}
九. 虽然采用不同的实现，但是接口是一致的，这很好！
十. 注意，在vc编译器上，不要混合使用cpp和c后缀的文件，否则由于编译器对c和c++函数符号的处理不一致，导致链接时错误！
Ps：推荐Spolsky论战Bob大叔 这篇文章， 我经常发现个现象，很多原则和模式都表达的很绝对，而且宣扬这样观点的牛人也说的很绝对，比如敏捷的那些人就说一定要敏捷才是开发者最好的选择，而当初推崇RUP的大师们也说RUP是软件开发最好的指导过程；我的经验和哲学观告诉我，世上不可能有那么绝对的方法，软件开发领域尤其如此，每个方法和原则只是在适当的Context下才可能适用。我想那些大师的思考肯定不会比我差，但他们为什么还要那样绝对呢？ 这个困惑，我朦胧的想到过可能的答案：对每个具体的技术领域，至少理论上，它必须要表达出它可达到的高度，和解决问题的适应性，否则，如果它首先就指出，它可能有用，也可能无用，要自己根据具体情况具体判断，这样一般用户就会很快迷失，进而对它失去信心和兴趣。所以，大师们需要用自己坚定不移的态度表明它的实用性，这样才能达到推广的目的。 而一般用户在美好前景的激励下，逐渐掌握相关知识和技能，然后才可以体会其优缺点，形成自己的理解。 当然，还有一个可能原因，我们接触的技术领域都是从西方过来的，而西方人的思维一般习惯于明确的表达，而不像我们东方人经常表达：这也可以，那也可以。 最近学习信息系统项目管理，体会尤其明显，tmd明明有更好的方法既可以按时完成工期，又可以节约项目成本，他的正确答案偏偏就不是这个。 这篇文章说的很好：“它可能鼓励他们做出取舍──甚至在学会做取舍的代价和含义之前。”。看到此句，豁然觉得正是自己没表达出来的。
最新评论