本文用一个简单的例子来说明接口设计的重要性。使用的是Linux kernel中list_head,顺便说一句,如果你想使用复合模式组织你的对象,那么Linux kernel中的kobject结构是个不错的选择,如果时间允许,我准备用一下,想象一下Linux是如何组织缤纷复杂的总线和外部以及内部设备的吧。
从一个古老的又比较简单的问题说起,这个问题就是古罗马的约瑟夫问题:设有n个人围坐在圆桌周围,现从某个位置 i 上的人开始报数,数到 m 的人就站出来。下一个人,即原来的第m+1个位置上的人,又从1开始报数,再是数到m的人站出来。依次重复下去,直到全部的人都站出来,按出列的先后又可得到一个新的序列。为了节省篇幅,将i定为1。
对于解决这类问题,最后留下的最有价值的东西就是问题本身的解决思路,而不是一堆看起来很棒的代码,这些代码用尽了所有的语法特性,为了寻求更多的荣誉,动用了大量的编程语言…这些都是垃圾!古罗马没有编程语言,但是人家照样完美的解决了这个问题,编程语言只是一个工具,所以不要动不动就代码啊代码,实现啊实现,貌似啊貌似,作为从事精准工作的程序员,如果你觉得你的想法有道理,那就直说,绝对不要使用诸如“貌似…吧”之类的短语,而这种短语在编程相关的论坛上十分常见,实际上发言人所要做的仅仅是呈出一个意见,十有八九是在挑刺,挑出楼上一个人代码的一个毛病。还是那句老话,编程并不一定比烧锅炉更有技术含量,它在某种意义上称不上一种真正的技术,就像锄头一样,工具而已,真想搞有技术含量的,那就去搞火箭,卫星,生物医学,基因工程,超弦之类的…言归正传,不管任何算法题目,最有价值的东西就是算法本身,也就是解决方案的思路,而不是什么代码。
垃圾实现:
用一个main函数实现的那种代码绝对是写给会C语言的人看的,不懂编程的人根本看不懂,竟然还上了wiki,这种实现绝对是垃圾!在这里也就不贴代码了,google一下或者摆渡一下,全都是这种代码。我也不是说我实现的就一定好,其实我写的代码也很垃圾,但是绝对比把所有逻辑都交给main要好。以下是我的实现,一步一步引导,最终说明接口的重要性。
普通单链表实现:
以下的代码使用了最常见的普通单向链表,一般都是这种设计的,如果你不想花点时间设计通用接口的话。虽然这种实现体现了封装,但是还是没有办法直接体现算法的思路,没法让人一眼看出你是怎么想的。下面是代码:
#include <stdio.h>
struct entry {
int value;
struct entry *next;
};
struct entry *g_list = NULL;
struct entry *g_last = NULL;
void init_list(int *vs, int len)
{
int i = 0;
struct entry *head = (struct entry*)calloc(1, sizeof(struct entry));
struct entry *first = g_list = head;
head->value = vs[0];
for (i = 1; i < len; i++) {
struct entry *next = (struct entry*)calloc(1, sizeof(struct entry));
next->value = vs[i];
head->next = next;
head = next;
}
head->next = first;
g_last = head;
}
int go_to(struct entry *list, int T)
{
struct entry *pre = g_last;
struct entry *curr = list;
struct entry *next = list->next;
int i = 0;
for (i = 0; i < T-1; i ++) {
pre = pre->next;
curr = curr->next;
next = next->next;
}
pre->next = next;
g_list = next;
g_last = pre;
return curr->value;
}
int main (int argc, const char * argv[])
{
int va[] = {1,2,3,4,5,6,7,8};
init_list(va, sizeof(va)/sizeof(int));
struct entry *thread = g_list;
do {
printf("out man:%d\n", go_to(g_list, 4));
}while (g_last != g_list);
printf("last man:%d\n", go_to(g_list, 4));
return 0;
}
以上的单链表实现,我们发现了两个问题,第一个问题就是在go_to函数中维护了三个指针,分别是当前指针,当前指针的前一个,当前指针的下一个。为了维护这三个指针中的后两个,一定要在链表初始化时定位最后一个节点以及保存链表头。第二个问题就是在main函数中用递推方法组织了整个算法,实际上我们发现,这是个明显可以递归解决的问题。关于第一个问题,交给了list_head实现,关于第二个问题,以下给出递归实现。
递归实现
基本思路没有什么变化,只是更加清晰了,使用了递归
#include <stdio.h>
#include <stdlib.h>
struct entry {
int value;
struct entry *next;
};
struct entry* init_list(int *vs, int len)
{
int i = 0;
struct entry *head = (struct entry*)calloc(1, sizeof(struct entry));
struct entry *first = head;
head->value = vs[0];
for (i = 1; i < len; i++) {
struct entry *next = (struct entry*)calloc(1, sizeof(struct entry));
next->value = vs[i];
head->next = next;
head = next;
}
head->next = first;
return head;
}
void go_to(struct entry *list, struct entry *pre_l, int T)
{
struct entry *pre = pre_l;
struct entry *curr = list;
struct entry *next = list->next;
int i = 0;
if (list->next == list) {
printf("last:%d\n", list->value);
return;
}
for (i = 0; i < T-1; i ++) {
pre = pre->next;
curr = curr->next;
next = next->next;
}
pre->next = next;
printf("ddddd:%d\n", curr->value);
go_to(next, pre, T);
//return curr->value;
}
int main (int argc, const char * argv[])
{
int va[] = {1,2,3,4,5,6,7,8};
struct entry *ll = init_list(va, sizeof(va)/sizeof(int));
go_to(ll->next, ll, 4);
return 0;
}
以上的代码看来,明显简洁了不少,没有用main函数组织逻辑,算法逻辑全部交给了go_to,需要注意的是go_to的返回值,由于只是介绍思路,因此没有将“出列者”保存于任何容器,只是简单的printf打印,而实际上,应该另外单独维护一个容器,比如栈或者队列,然后在printf的地方将出列者放进队列,然后在main函数中统一打印之。
在递归实现中,go_to函数中的三个指针依旧,能否去除它们呢?那就是使用双向链表,可是我们怎么实现双向链表呢?
简单双向链表实现
一步一步的,现在使用双向链表实现,所谓双向链表,那无非就是在单向链表中增加了一个指针,那就是:
struct entry {
int value;
struct entry *next, *prev;
};
接下来就不贴代码了,和单向链表相区别的是初始化函数以及go_to函数,不必再维护三个指针了,也不用维护全局变量了,只需要简单取出prev和next即可。现在,唯一的问题就是代码还是体现不出解决问题的思路,还是堆砌了很多编程技巧相关的代码,比如链表操作之类的,很显然的做法就是将这些封装成接口,然而这种封装只能让这个约瑟夫问题看起来好些,对于其它的问题是无法重用的,因为entry结构体是不可重用的。
Linux内核中list_head解决了这个问题。
list_head实现
Linux内核中的list_head是一个体现OO思想的良好设计的“侵入式”双向链表。所谓侵入式,那就是它不和任何特定的数据结构相耦合,谁想将自己组织成链表,只需简单包含list_head字段即可,然后可以通过该字段在对应结构体中的偏移来根据list_head字段的地址取出相应结构体的地址,十分方便好用,内核的list.h头文件定义了几乎所有的操作,在约瑟夫实现中,还需要一个接口,那就是list_step,该接口实现向前(向后-还没有实现)推进N的功能:
struct list_head *list_step(struct list_head* list, int step)
{
int i = 0;
while(i++ < step)
list = list->next;
return list;
}
有了上述接口,连同kernel自带的,我给出使用list_head实现的约瑟夫问题的代码:
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct entry {
struct list_head list;
int value;
};
struct list_head *init_list(int *vs, int len)
{
int i = 0;
struct list_head *head = NULL;
for (i = 0; i < len; i++) {
struct entry *next = (struct entry*)calloc(1, sizeof(struct entry));
INIT_LIST_HEAD(&next->list);
next->value = vs[i];
if (i==0)
head = &(next->list);
else
list_add_tail(&next->list, head);
}
return head;
}
void go_to(struct list_head *list, int T)
{
int i = 0;
struct list_head *curr = NULL, *next = NULL;
struct entry *e = NULL, *e2;
if (list_empty(list)) {
e = list_entry(list, struct entry, list);
printf("last:%d\n", e->value);
return;
}
curr = list_step(list, T-1);
next = list_step(curr, 1);
list_del(curr);
e = list_entry(curr, struct entry, list);
printf("curr:%d \n", e->value);
go_to(next, T);
}
int main (int argc, const char * argv[])
{
int va[] = {1,2,3,4,5,6,7,8};
struct list_head *head = init_list(va, sizeof(va)/sizeof(int));
go_to(head, 4);
return 0;
}
可见,这个代码很简单,除了我的函数以及变量命名不是很好之外,如果命名良好,只要看英语就可以知道整个解决思路了,没有任何让人看来是编程者专利的东西。
分享到:
相关推荐
约瑟夫环问题一个很好的版本,整理了很久。
【源码】【数据结构几个实例】【约瑟夫环问题--停车场管理--二叉树的建立与遍历--图遍历--哈希表设计】
约瑟夫环问题,多的不说了,内行都明白的。 就是一群人,从中选择一个人 这是自己写的,有比较详细的注释,大家自己读哈,谢谢诶
c语言实习作业,约瑟夫环
提供约瑟夫环给想要的各位朋友, typedef struct CLnode { int data; int number; struct CLnode * next; }CLnode;
约瑟夫环问题的链表和数组两种解法 设有N个人围坐一圈并按顺时针方向从1到N编号,从第S个人开始进行1到M报数,报到第M个人时,此人出圈,再从他的下一个人重新开始1到M的报数,如此进行下去直到所有的人都出圈为止,...
约瑟夫问题-循环链表典型应用 n 个人围成一个圆圈,首先第 1 个人从 1 开始一个人一个人顺时针报数, 报到第 m 个人,令其出列。然后再从下一 个人开始从 1 顺时针报数,报 到第 m 个人,再令其出列,…,如此下去,...
约瑟夫环 数据结构中是约瑟夫环采用比较简单是算法计算,成功的约瑟夫环
这是约瑟夫问题的静态链解法,代码量少,易理解,是一种很好的思路
不同的方式实现约瑟夫环joseph-master.zip
用数据结构以及C实现约瑟夫环Jonseph-master.zip
约瑟夫问题面向对象解法报告书(C++版)pdf格式
约瑟夫环的三种解法JosephRing-master.zip
约瑟夫环问题,设置一个初始密码,进行计数,到第几人,则其出列,拿出其密码在进行下一次计数,依次出列,直至最后一人。(每个人都带密码的)
约瑟夫问题 约瑟夫问题_基于C++的约瑟夫问题的一种变种_题解
使用c语言中的循环链表及结构体实现约瑟夫环问题
约瑟夫(Josephus)环问题: 设有n个人围成一圈,现从第s个人开始,拨顺时针方向从1开始报数,数到d的人退出圆圈,然后从退出圆圈的下一个人重新开始报数,数到d的人又退出國圈,依此重复下去,直到最后一个人出圈为止...
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
古罗马的史学家约瑟夫(Josephus),他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫和犹太叛军战士们,设法守住了裘达伯特城达47天之久。在城市沦陷之后,他和40名犹太叛军的将士们在附近的一个洞穴中避难...