继续 代码大全（2）

辛昕

继续 代码大全（2） [复制链接]

上一个代码大全的帖子 已经到了8页了，有点长。
于是决定写一个新帖。

同样希望以后写的更简洁，更有说服力。

辛昕

其实也很久没看 代码大全，第一个帖子的内容，绝大多数 停留在 前十章。
最近，因为偶然想起来看了一下 复杂数据结构 这一章

主要讲了三个内容：
1.结构和记录（对于C语言，说白了，就是 结构体）；
2.表驱动方法（Table-driven method）；
3.抽象数据结构（ADTs）；

代码大全的作者 说了一段 很实在 的话：
算法 和 数据结构 书上 讲了一堆的数学理论，然后又讲述了N多抽象得不行的 数据结构类型，结果除了把人吓坏以外，什么用都没有。

实际上，数据结构 非常有用，而且有时，还挺有趣。

我前阵子翻阅了一本 C实现的算法书，只看到了 几种表 的实现 和 二叉树 就晕的七七八八了。
不过也正是这个原因，后来在我不断写代码的过程中，有一次，我无意意识到自己可以用一种 我说不出名字 的数据结构 去简化一系列读键函数，当时我误以为 自己使用的是 抽象数据结构。

直到后来，我才知道，自己使用的其实是 表驱动方法。

辛昕

考虑一个题目：

在单片机编程里，读键函数是很常见的。
假设我们现在要处理连键。

读键函数必然少不了抖动，比较灵活的方法是。
在读键函数内部定义一个 静态计时器，然后循环调用这个函数，读到键值，就累加 这个静态计时器。

1. U8 ReadKey(void)
   

   {
   

       static U8 timer;
   

       static U8 flag = NO;
   

   
   

       // IF KEY IS PRESS DOWN //伪代码 判断
   

       {
   

            timer++;
   

            if(timer >= SHAKE_TIME && flag != YES)
   

            {
   

                  // 键有效；
   

   //还要植 flag;
   

               flag = YES;
   

            }
   

       }
   

       else
   

       {
   

            flag = NO;
   

            timer = 0;  //不管怎么滴，清定时器；

复制代码

}
}


直到它到达一个阀值，我们就可以认为 有效读键。

处理单键和连键的关键在于，怎么确认第一个键以后的键值；
单键一般要求，键要有一个释放过程，再读才有效；
而连键则不要求释放过程；

上述贴的第一个代码，正是 单键的处理；对于多键，则不需要那个flag;
不过为了分辨第一次单键和连键——不至于出现单键判成两三个键，要对timer的起始值做一定处理，如下：

1. U8 ReadKey(void)
   
2. {
   
3. static U8 timer;
   
4. 
   
5. // IF KEY IS PRESS DOWN //伪代码 判断
   
6. timer++;
   
7. else
   
8. timer = 0; //不管怎么滴，清定时器；
   
9. 
   
10. if(timer >= FIRST_KEY_DELAY)
    
11. {
    
12.     //单键有效；
    
13.     //把timer的起始值拉高，以避免反复误认为单键；
    
14.      timer = 0x10;
    
15. }
    
16.     if(timer >= 0x10 + DELAY)
    
17.      {
    
18.         //键有效，并植回起始值；
    
19.         timer = 0x10;
    
20.      }
    
21. 
    

复制代码

现在的一个 连键的题目是：
读一个键，每读到一次，就计数一次，然后把计数值用数码管显示出来；



现在不仅要处理连键，还要考虑加速确认按键：
意思就是说，按着键时间越久，计数就更快，也就是说 是 加速确认连键。

在函数中，我们可能不止一个地方要用到这种连键，并且，每一个地方的连键的 具体 加速的速率 和 消抖时间 都不一样。

那么，这样一个题目，你会怎么做？

[ 本帖最后由 辛昕 于 2012-10-20 09:53 编辑 ]

辛昕

我们先来简单说一下结构体。

单单说结构体，没什么可说。
但是，它是实现很多基本数据结构的基础。

比如 链表。
还有我们下面即将说到的 表驱动方法，可以说，没有结构体，就没有表驱动。

这里先只纯粹说 结构体本身。

结构体 和 数组 相比，有一个共同点，一个差异点：
公共的是，它的元素，在内存上 都是 连续排列的；
差异的是，后者的元素要求数据类型一致，而前者没要求。

正因如此，结构体有时也被叫 柔性数组。

纯粹使用结构体，大多数时候，个人觉得是在 组织数据上体现得比较充分，也就是从易于理解程序的角度来说，意义比较大。

因为我们可以把一个对象的一系列参数，特征，都放到一个结构体里，这样，数据之间彼此就有了联系。

其他的，倒也说不出太多。

哦，另一个不太明显的好处是。
如果使用 结构体作为变量传递到函数里，可以简化 参数表，避免出现复杂的接口。

比如说，我们要处理一匹马，需要用到它的名字，出生年月，身高，重量.....
如果我们一个一个传，这个函数就会有至少四个形参。

而如果我们以一个结构体存储这些信息

HorseStr;
传递时，就只需要传递这个结构体了。

辛昕

为了避免这个名词被神秘化，我来举一个最简单的例子说明什么是  表驱动。

这个例子大家一定非常熟悉，它就是我们初学51时常说到的 用查表获得平方数。
我们都知道，乘除运算消耗的时间比较长，所以，为了提高速度，有时候，我们就会直接把平方数存储在一个表格里，然后采用查表的方法直接获得结果，避免了直接乘法运算。

表驱动。

首先，表 是一种 抽象数据结构 的名字（作为三种最基本的之一，另两种 是 栈 和 队列）

它有好几种形式，比如说，一个 数组 就是一个最简单的 表。
还包括我前面提过的 链表。

你可以先简单地把它理解为一个连续的数组。因为关于 数据结构，这个话题实在太沉重。

我们接着说 表驱动方法。

表驱动方法 说的是 用 查表的方法 来取代 复杂的逻辑或者运算。

前面说到的这个 51里的查平方表 的方法属于后者。

它把直接运算 转换成了查表，因为后者的运行速度要远远快于前者。

这也是表驱动的一种核心思想：
——不管是 复杂的运算，还是复杂的逻辑，它都转换成一张表，然后通过一个简单的（通常还是循环的）查询过程 替代。

下一个帖子，将会举一个简单的 取代复杂逻辑 方面的例子。

辛昕

代码大全 这本书上提到一个 计算保险 的例子，略显复杂。
我在这里举一个稍微简单一些的例子。

比如以前数学题里经常出现的 运输成本问题。

我们考虑这样一个问题：
假设我们需要M种货物，有N个渠道，但是，不同的渠道进不同的货物的成本都是不一样的。

我们很自然地会想到，这实际上是一个 M*N矩阵。

我们每次都可能从N个渠道中的某几个渠道 获得 某几种货物。
现在我们要计算总共所需的成本 的时候，就要了解对应的 M*N种不同成本。

在最简单的情况下，M = N = 1.
我们想都不会想，都是直接定义一个变量。

如果M和N稍微大一点，我们也许会想到用
if(M == 3 && N== 4)之类的if-else结构来实现；

只有当N，M相当大，大到你一直打if打到手软的时候，才会促使你去思考用另一种更简洁的方式实现。

当然，这个情形非常简单，你很自然地，甚至一开始就会想打 用一个 二维数组存储不同成本的方法。

因为，这个问题在描述时，就已经把人的思维引导到 二维数组 的思路上去了。

nullyb

mark！！！！

辛昕

前面我写结构体的时候，我对于纯粹使用结构体带来的好处，重视程度不够，这是因为当时我还没大量使用结构体。

现在我来补充一点：

一个过程往往不能一次完成，比如说读键，它需要延迟来消抖。
而在实际编程里，我们不能光等待来延迟。
任何时候，在程序里使用纯粹软件延迟，一直等待的方式 都是不可原谅的。
除非这个时间短到在一到十倍机器周期。

那么我们经常做的方法就是，循环调用这个函数，然后内部设置一个静态计数器。

如果现在我们要在外部一个地方清零这个计数器，你会怎么做呢？

也许你会这样做，这个函数增加一个形参，这个形参为1就清除，不为1就不清除
——至少我曾这样干了很久。

这个当然不好，第一，它增加了接口的复杂性；第二，它让这个函数的调用变得很奇怪。

你清零计数器的目的是什么？很难说得清楚，但至少不是读这个键吧？
然而，这个函数却是为读键而存在的。
而你却用一个读键函数去实现另一个目的。

所有这一切，核心原因在于：
1.你使用了静态变量，除非你进到它的函数内部，否则你没办法操作它。
2.它又不能是局部的，因为它用来累计时间；

你会很爽快的说，那我用 全局变量 好了！
全局变量，，，全局变量当然好，它是无所不能的存在。
不过，别忘了，它也可能是无所不在的麻烦所在。

现在有了结构体，我们有了另一种方法。

我们可以把这个静态变量（也许还有其他的参数，比如说，延迟最大单位啊）
封装成一个结构体，然后单独为这个结构体设计几个操作函数
比如递减静态计时器，比如判断静态计时器是否已经到钟.......

接下来，我上代码会解释的更好

1. typedef struct
   
2. {
   
3.     U8 MaxDelay;
   
4.     U8 Delay;
   
5. }DelayStruct;
   
6. 
   
7. void Initial_DelayStruct(DelayStruct *Str,U8 MaxDelay)
   
8. {
   
9.      Str->MaxDelay = MaxDelay;
   
10.      Str->Delay = 0;
    
11. }
    
12. 
    
13. U8 IsDelayUp(DelayStruct *Str)
    
14. {
    
15.    Str->Delay++;
    
16. 
    
17.    if(Str->Delay >= Str->MaxDelay)
    
18.       return YES;
    
19.    else
    
20.       return NO;
    
21. }

复制代码

瞧好了。
现在，哪里我需要延迟，我可以在主调这个延迟函数的地方定义这样一个静态结构体，然后再按地址传入这几个通用的操作函数，就可以完成延迟，但是，这个静态计数器（就在静态结构体里），对于延迟函数来说，是在外部的，要清除它是易如反掌，压根无须进入其内部。

辛昕

话说我这两天，在淘宝上买了一本盗版的代码大全，22，京东上的所谓原版都要80多，我就，，，
诶，果断是便宜没好货，今天到了。
我才知道原来盗版也是分等级的，明显的纸质就差很远，看来真不该省这纸钱，，早知道在淘宝上搞本40多的……

成风

“1.你使用了静态变量，除非你进到它的函数内部，否则你没办法操作它。”

不知道通过返回静态变量的地址，来修改静态变量呢？

辛昕

呵呵，这事还真没干过。