不然你要我怎么样

链表实现方法

一、单链表的建立

有了动态内存分配的基础，要实现链表就不难了。

所谓链表，就是用一组任意的存储单元存储线性表元素的一种数据结构。

链表又分为单链表、双向链表和循环链表等。我们先讲讲单链表。

所谓单链表，是指数据接点是单向排列的。一个单链表结点，其结构类型分为两部分： Read the rest of this entry »

原文地址：http://hi.baidu.com/xy_zm/blog/item/04cfcb08e2dcec34e82488af.html

为什么用动态内存分配

当我们未学习链表的时候，如果要存储数量比较多的同类型或同结构的数据的时候，总是使用一个数组。比如说我们要存储一个班级学生的某科分数，总是定义一个float型（存在0.5分）数组：

float score[30];

但是，在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？

在很多的情况下，你并不能确定要使用多大的数组，比如上例，你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。这样，你的程序在运行时就申请了固定大小的你认为足够大的内存空间。即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新去修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称之为静态内存分配。但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时：在大多数情况下会浪费大量的内存空间，在少数情况下，当你定义的数组不够大时，可能引起下标越界错误，甚至导致严重后果。

那么有没有其它的方法来解决这样的问题呢？有，那就是动态内存分配。 Read the rest of this entry »

关键字const

用法：

1．可以定义 const 常量

2．const可以修饰函数的参数、返回值，甚至函数的定义体。被const修饰的东西都受到强制保护，可以预防意外的变动，能提高程序的健壮性。

const意味着”只读”。区别如下代码的功能非常重要。

const int a;
int const a;
const int *a;
int * const a;
int const * a const;

前两个作用是一样的，a是一个常整型数。

第三个意味着a是一个指向常整型数的指针（也就是，整型数是不可修改的，但指针可以）。

第四个意思是a是一个指向整型数的常指针（也就是，指针指向的整型数是可以修改的，但指针是不可修改的）。

最后一个意味着a是一个指向常整型数的常指针（也就是，指针指向的整型数是不可修改的，同时指针也是不可修改的）。

关键字const的作用是为给读你代码的人传达非常有用的信息。例如，在函数的形参前添加const关键字意味着这个参数在函数体内不会被修改，属于”输入参数”。在有多个形参的时候，函数的调用者可以凭借参数前是否有const关键字，清晰的辨别哪些是输入参数，哪些是可能的输出参数。

合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改，这样可以减少bug的出现。

const在C++语言中则包含了更丰富的含义，而在C语言中仅意味着：”只能读的普通变量”，可以称其为”不能改变的变量”（这个说法似乎很拗口，但却最准确的表达了C语言中const的本质），在编译阶段需要的常数仍然只能以#define宏定义！故在C语言中如下程序是非法的：

const int SIZE = 10;
char a[SIZE]; /* 非法：编译阶段不能用到变量 */

以下是工作中的使用const例子：

const unsigned char * pbyData;
unsigned char const DayPerMonth[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 } ;
extern void dp_write_dsp_block ( const word *bp, word len );
const unsigned short InterMapSparseIdx[];

手边有书，心中无书。实在是厌烦了去查书，so，好好总结下。

—————————————————————

关键字static：

关键字static是一个存储类说明符，同extern，typedef一样，因此他们不能同时使用。

定义：说明符static将声明的对象说明为静态存储类

在C语言中，关键字static有三个明显的作用：

1．static用于声明内部变量

在函数体内，一个被声明为static的变量在这一函数被调用过程中仅分配一次内存，且函数结束后其不会被销毁。

e.g.：

输出为：
2
3
4
5
6

2．static用于声明外部变量

在模块内（但在函数体外），一个被声明为static的变量可以被模块内所有函数访问，但不能被模块外其它函数访问。它是一个本地的全局变量（最常见的用法）。

3．static用于声明函数

在模块内，一个被声明为static的函数只可被这一模块内的其它函数调用。那就是，这个函数被限制在声明它的模块的本地范围内使用。

算法就是源动力~

———————————————————-

算法是计算机科学领域最重要的基石之一，但却受到了国内一些程序员的冷落。许多学生看到一些公司在招聘时要求的编程语言五花八门，就产生了一种误解，认为学计算机就是学各种编程语言，或者认为，学习最新的语言、技术、标准就是最好的铺路方法。其实，大家被这些公司误导了。编程语言虽然该学，但是学习计算机算法和理论更重要，因为计算机语言和开发平台日新月异，但万变不离其宗的是那些算法和理论，例如数据结构、算法、编译原理、计算机体系结构、关系型数据库原理等等。在“开复学生网”上，有位同学生动地把这些基础课程比拟为“内功”，把新的语言、技术、标准比拟为“外功”。整天赶时髦的人最后只懂得招式，没有功力，是不可能成为高手的。

算法与我

当我在1980年转入计算机科学系时，还没有多少人的专业方向是计算机科学。有许多其他系的人嘲笑我们说：“知道为什么只有你们系要加一个‘科学’，而没有‘物理科学系’或‘化学科学系’吗？因为人家是真的科学,不需要画蛇添足，而你们自己心虚，生怕不‘科学’，才这样欲盖弥彰。” 其实，这点他们彻底弄错了。真正学懂计算机的人（不只是“编程匠”）都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。

记得我读博时写的Othello对弈软件获得了世界冠军。当时，得第二名的人认为我是靠侥幸才打赢他，不服气地问我的程序平均每秒能搜索多少步棋，当他发现我的软件在搜索效率上比他快60多倍时，才彻底服输。为什么在同样的机器上，我可以多做60倍的工作呢？这是因为我用了一个最新的算法，能够把一个指数函数转换成四个近似的表，只要用常数时间就可得到近似的答案。在这个例子中，是否用对算法才是能否赢得世界冠军的关键。

还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想了解为什么他们的语音识别系统比我开发的慢几十倍，而且，在扩大至大词汇系统后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让系统跑了起来，但这么贵的计算资源让他们的产品部门很反感，因为“昂贵” 的技术是没有应用前景的。在与他们探讨的过程中，我惊讶地发现一个O(n*m)的动态规划（dynamic programming）居然被他们做成了 O(n*n*m)。更惊讶的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学会议里，希望能得到大奖。当时，贝尔实验室的研究员当然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧!

网络时代的算法

有人也许会说：“今天计算机这么快，算法还重要吗?”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。

再举另一个网络时代的例子。在互联网和手机搜索上，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢?

最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。

这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆,那这么做应该没什么问题,反正计算量不大。但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了。在这种情况下,我们该怎样优化算法呢?

首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”,然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。

问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。

上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个“点”，如果要搜索一个“面”该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”,因为树中间的每一个节点都是一个范围，一个有边界的范围。
通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。

并行算法：Google的核心优势

上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。

在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用 Google的服务，也产生很多很多的日志（Log）。因为Log每分每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对 log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但在实际应用中是几乎不可行的。按照他们的算法，即便用上几万台机器，我们的处理速度都跟不上数据产生的速度。

那么Google是如何解决这些问题的呢？

首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事倍功半的代价是没有哪家公司可以