文档库

最新最全的文档下载
当前位置:文档库 > c程序员成长 (16)

c程序员成长 (16)

//组合的威力
软件设计的两个基本原则:
1、针对接口编程,而不是针对实现编程。接口是抽象的,因为抽象所以简单。接口是对象的本质,因为是本质所以稳定。接口是降低复杂度和隔离变化的有力武器,C语言没有接口的概念,不是因为接口不重要,而是C语言把它视为理所当然的东西(函数指针无处不在)。
2、优先使用组合,而不是类继承。与组合相比,继承更为复杂,特别是多重继承和多层继承,甚至带来一些歧义,给理解上造成困难。与组合相比,继承缺乏灵活性,继承在编译时就绑定了父类和子类之间的关系,而组合却可以在运行时动态改变,C语言没有继承的概念(当然可以实现继承),自然大量使用组合来构建大型系统,这在客观上恰恰与设计原则是一致的。
这里借助队列,栈和哈希表来练习这种基本的重用方法。
//队列
队列是一种很常用的数据,操作系统用队列来管理运行的进程,驱动程序用队列来管理要传输的数据包,GUI框架用队列来管理各种GUI事件。队列是一种先进先出(FIFO)的数据结构,数据只能从队列头取,向队列尾追加。队列的名称很形象的表达了它的意义,就像排队上车一样,前面的先上,后来的站在后面排队。
队列主要的接口函数有:
o 创建队列:queue_creat
o 取队列头的元素:queue_head
o 追加一个元素到队列尾:queue_push
o 删除队列头元素:queue_pop
o 取队列中元素个数(同时也可以判断队列是否为空):queue_length
o 遍历队列中的元素:queue_foreach
o 销毁队列:queue_destroy
队列看起来比链表和数组要高级一点,其实它只不过是链表和数组的一种特殊形式而已,下面我们用重用链表实现队列:
o 队列的数据结构
struct _Queue
{
Dlist *dlist;
};
这里队列只是双向链表的一个包装。
o 创建队列
Queue *queue_creat(DataDestroyFunc data_destroy, void *ctx)
{
Queue *thiz = (Queue *)malloc(sizeof(Queue));
if (thiz != NULL)
{
if ((thiz->data = dlist_creat(data_destroy, ctx)) == NULL)
{
free(thiz);
thiz = NULL;
}
}
return thiz;
}
创建队列时,除了分配自己的空间外,就是简单的创建一个双向链表。
o 取队列头的元素
Ret queue_head(Queue *thiz, void *data)
{
return _val_if_fail(thiz != NULL && data != NULL, RET_INVALED_PARAMS);
return dlist_get_by_index(thiz->dlist, 0, data);
}
我们认为链表的第一个元素是队列头,取队列头的元素就是取链表的第一个元素。
o 追加一个元素到队列尾
Ret queue_push(Queue *thiz, void *data)
{
return _val_if_fail(thiz != NULL, RET_INVALID_PARAMS);
return dlist_append(thiz->dlist, data);
}
我们认为链表的最后一个元素就是队列尾,追加一个元

素到队列尾就是追加一个元素到链表尾。
o 删除队列头元素
Ret queue_pop(Queue *thiz, void *data)
{
return _val_if_fail(thiz != NULL, RET_INVALID_PARAMS);

return dlist_delete(thiz->dlist, 0);
}
删除队列头的元素就是删除链表的第一个元素。
o 取队列中的元素个数
size_t queue_length(Queue *thiz)
{
return _val_if_fail(thiz != NULL, 0);
return dlist_length(thiz->dlist);
}
队列中元素个数等同于链表元素的个数
o 遍历队列中的元素
Ret queue_foreach(Queue *thiz, DataVisitFunc visit, void *ctx)
{
return _val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);
return dlist_foreach(thiz->dlist, visit, ctx);
}
o 销毁队列
void queue_destroy(Queue *thiz)
{
if (thiz != NULL)
{
dlist_destroy(thiz->dlist);
thiz->dlist = NULL;
free(thiz);
}
return;
}
销毁链表然后释放自身的空间。
上面我们实现的通用队列,除了它以外还有集中特殊的队列应用也非常广泛:
o 优先级队列:它不同之处在于,插入元素时不必追加到队尾,而是根据元素的优先级插入到队列适当的位置。这个就像排队上车时,后面来了个老人,我们让她先上一样的。内核的进程管理器通常采用优先级队列管理进程
o 循环队列:循环队列的特点就是最大元素个数是固定的。它的有点是两个并发的实体(进程或线程),按一个读一个写的方式访问,不需要加锁。设备驱动程序经常使用循环队列来管理数据包。
//栈
栈是一种后进先出(LIFO)的数据结构,栈是最重要的数据结构之一:没有栈,基于下推自动机的编译器不能工作,我们只能写汇编程序。没有栈,无法实现递归/多级函数调用,程序根本无法工作。
栈的主要接口函数有:
o 创建栈
o 取栈顶元素
o 放入元素到栈顶
o 删栈顶元素
o 取栈中元素个数
o 遍历栈中的元素
o 销毁栈
//哈希表
哈希表 = 数组 + 链表
哈希表的基本接口:
o 创建
o 插入
o 删除
o 查找
o 计算元素个数
o 遍历所有元素
o 销毁
哈希函数的好坏基本决定了哈希表的效率,好的哈希函数计算出的哈希值分布比较平均。但哈希表的好坏只能动态评估,它与数据类型和应用环境密切相关。按照惯例,实现者不知道的事就应该让调用者取实现,所以把哈希函数设计成回调函数,有调用者提供。