时间过得很快，没程序员考试补课笔记-第十二天

今天老师和我们讲了链表，和老潭书里一样大家都讲得很好，让人很容易就可以听进。所以这里我也不再重复了，大家自己慢慢看一下老潭书里的链表那节，绝对不会觉得难的，而且还举了一些生动的例子来到说明。下面我就从网上找来一些关于指针的文章，这个人绝对是高手，大家这回要好好研究一下咯。相信看完第一遍之后一定对指针有个大概，第二遍已经有印象在脑海里不停的回旋了，第三遍可以大功告成了。 ^_^
为初学者服务。这是我的帖子的宗旨。我也是个初学者（强调了无数遍了）

，我以我的理解把初学者觉得难懂的东西用浅显的语言写出来。由于小学时语文

没学好，所以竭尽全力也未必能达到这个目的。尽力而为吧。

指针是c和c++中的难点和重点。我只精通dos下的basic。c语言的其它各种特

性，在basic中都有类似的东西。只有指针，是baisc所不具备的。指针是c的灵魂

。

我不想重复大多数书上说得很清楚的东西，我只是把我看过的书中说得不清

楚或没有说，而我又觉得我理解得有点道理的东西写出来。我的目的是：

1。通过写这些东西，把我脑袋中关于c的模糊的知识清晰化。

2。给初学者们一点提示。

3。赚几个经验值。（因为贴这些东西没有灌水之嫌啊）


第一章。指针的概念

指针是一个特殊的变量，它里面存储的数值被解释成为内存里的一个地址。


要搞清一个指针需要搞清指针的四方面的内容：指针的类型，指针所指向的

类型，指针的值或者叫指针所指向的内存区，还有指针本身所占据的内存区。让

我们分别说明。

先声明几个指针放着做例子：

例一：

(1)int *ptr;
(2)char *ptr;
(3)int **ptr;
(4)int (*ptr)[3];
(5)int *(*ptr)[4];
如果看不懂后几个例子的话，请参阅我前段时间贴出的文?lt;<如何理解c和c
++的复杂类型声明>>。


1。 指针的类型。

从语法的角度看，你只要把指针声明语句里的指针名字去掉，剩下的部分就

是这个指针的类型。这是指针本身所具有的类型。让我们看看例一中各个指针的

类型：

(1)int *ptr; //指针的类型是int *
(2)char *ptr; //指针的类型是char *
(3)int **ptr; //指针的类型是 int **
(4)int (*ptr)[3]; //指针的类型是 int(*)[3]
(5)int *(*ptr)[4]; //指针的类型是 int *(*)[4]
怎么样？找出指针的类型的方法是不是很简单？


2。指针所指向的类型。

当你通过指针来访问指针所指向的内存区时，指针所指向的类型决定了编译

器将把那片内存区里的内容当做什么来看待。

从语法上看，你只须把指针声明语句中的指针名字和名字左边的指针声明符

*去掉，剩下的就是指针所指向的类型。例如：

(1)int *ptr; //指针所指向的类型是int
(2)char *ptr; //指针所指向的的类型是char
(3)int **ptr; //指针所指向的的类型是 int *
(4)int (*ptr)[3]; //指针所指向的的类型是 int()[3]
(5)int *(*ptr)[4]; //指针所指向的的类型是 int *()[4]
在指针的算术运算中，指针所指向的类型有很大的作用。

指针的类型(即指针本身的类型)和指针所指向的类型是两个概念。当你对C越

来越熟悉时，你会发现，把与指针搅和在一起的"类型"这个概念分成"指针的

类型"和"指针所指向的类型"两个概念，是精通指针的关键点之一。我看了不

少书，发现有些写得差的书中，就把指针的这两个概念搅在一起了，所以看起书

来前后矛盾，越看越糊涂。


3。 指针的值，或者叫指针所指向的内存区或地址。

指针的值是指针本身存储的数值，这个值将被编译器当作一个地址，而不是

一个一般的数值。在32位程序里，所有类型的指针的值都是一个32位整数，因为

32位程序里内存地址全都是32位长。

指针所指向的内存区就是从指针的值所代表的那个内存地址开始，长度为si
zeof(指针所指向的类型)的一片内存区。以后，我们说一个指针的值是XX，就相

当于说该指针指向了以XX为首地址的一片内存区域；我们说一个指针指向了某块

内存区域，就相当于说该指针的值是这块内存区域的首地址。

指针所指向的内存区和指针所指向的类型是两个完全不同的概念。在例一中

，指针所指向的类型已经有了，但由于指针还未初始化，所以它所指向的内存区

是不存在的，或者说是无意义的。

以后，每遇到一个指针，都应该问问：这个指针的类型是什么？指针指向的

类型是什么？该指针指向了哪里？

4。 指针本身所占据的内存区。

指针本身占了多大的内存？你只要用函数sizeof(指针的类型)测一下就知道

了。在32位平台里，指针本身占据了4个字节的长度。

指针本身占据的内存这个概念在判断一个指针表达式是否是左值时很有用。


第二章。指针的算术运算

指针可以加上或减去一个整数。指针的这种运算的意义和通常的数值的加减

运算的意义是不一样的。例如：

例二：

1。 char a[20];
2。 int *ptr=a;
...
...
3。 ptr++;
在上例中，指针ptr的类型是int*,它指向的类型是int，它被初始化为指向整

形变量a。接下来的第3句中，指针ptr被加了1，编译器是这样处理的：它把指针

ptr的值加上了sizeof(int)，在32位程序中，是被加上了4。由于地址是用字节做

单位的，故ptr所指向的地址由原来的变量a的地址向高地址方向增加了4个字节。

由于char类型的长度是一个字节，所以，原来ptr是指向数组a的第0号单元开始的

四个字节，此时指向了数组a中从第4号单元开始的四个字节。

我们可以用一个指针和一个循环来遍历一个数组，看例子：

例三：

例三：

int array[20];
int *ptr=array;
...
//此处略去为整型数组赋值的代码。

...
for(i=0;i<20;i++)
{
(*ptr)++;
ptr++；

}
这个例子将整型数组中各个单元的值加1。由于每次循环都将指针ptr加1，所

以每次循环都能访问数组的下一个单元。

再看例子：

例四：

1。 char a[20];
2。 int *ptr=a;
...
...
3。 ptr+=5;
在这个例子中，ptr被加上了5，编译器是这样处理的：将指针ptr的值加上5
乘sizeof(int)，在32位程序中就是加上了5乘4=20。由于地址的单位是字节，故

现在的ptr所指向的地址比起加5后的ptr所指向的地址来说，向高地址方向移动了

20个字节。在这个例子中，没加5前的ptr指向数组a的第0号单元开始的四个字节

，加5后，ptr已经指向了数组a的合法范围之外了。虽然这种情况在应用上会出问

题，但在语法上却是可以的。这也体现出了指针的灵活性。

如果上例中，ptr是被减去5，那么处理过程大同小异，只不过ptr的值是被减

去5乘sizeof(int)，新的ptr指向的地址将比原来的ptr所指向的地址向低地址方

向移动了20个字节。


总结一下，一个指针ptrold加上一个整数n后，结果是一个新的指针ptrnew，

ptrnew的类型和ptrold的类型相同，ptrnew所指向的类型和ptrold所指向的类型

也相同。ptrnew的值将比ptrold的值增加了n乘sizeof(ptrold所指向的类型)个字

节。就是说，ptrnew所指向的内存区将比ptrold所指向的内存区向高地址方向移

动了n乘sizeof(ptrold所指向的类型)个字节。

一个指针ptrold减去一个整数n后，结果是一个新的指针ptrnew，ptrnew的类

型和ptrold的类型相同，ptrnew所指向的类型和ptrold所指向的类型也相同。pt
rnew的值将比ptrold的值减少了n乘sizeof(ptrold所指向的类型)个字节，就是说

，ptrnew所指向的内存区将比ptrold所指向的内存区向低地址方向移动了n乘siz
eof(ptrold所指向的类型)个字节。


第三章。运算?amp;和*

这里&是取地址运算符，*是...书上叫做"间接运算符"。

&a的运算结果是一个指针，指针的类型是a的类型加个*，指针所指向的类型

是a的类型，指针所指向的地址嘛，那就是a的地址。

*p的运算结果就五花八门了。总之*p的结果是p所指向的东西，这个东西有这

些特点：它的类型是p指向的类型，它所占用的地址是p所指向的地址。

例五：

int a=12;
int b;
int *p;
int **ptr;
p=&a;//&a的结果是一个指针，类型是int*，指向的类型是int，指向的地址

是a的地址。

*p=24;//*p的结果，在这里它的类型是int，它所占用的地址是p所指向的地

址，显然，*p就是变量a。

ptr=&p;//&p的结果是个指针，该指针的类型是p的类型加个*，在这里是int
**。该指针所指向的类型是p的类型，这里是int*。该指针所指向的地址就是指针

p自己的地址。

*ptr=&b;//*ptr是个指针，&b的结果也是个指针，且这两个指针的类型和所

指向的类型是一样的，所以用&b来给*ptr赋值就是毫无问题的了。

**ptr=34;//*ptr的结果是ptr所指向的东西，在这里是一个指针，对这个指

针再做一次*运算，结果就是一个int类型的变量。


第四章。指针表达式。

一个表达式的最后结果如果是一个指针，那么这个表达式就叫指针表达式。

下面是一些指针表达式的例子：

例六：

int a,b;
int array[10];
int *pa;
pa=&a;//&a是一个指针表达式。

int **ptr=&pa;//&pa也是一个指针表达式。

*ptr=&b;//*ptr和&b都是指针表达式。

pa=array;
pa++;//这也是指针表达式。

例七：

char *arr[20];
char **parr=arr;//如果把arr看作指针的话，arr也是指针表达式

char *str;
str=*parr;//*parr是指针表达式

str=*(parr+1);//*(parr+1)是指针表达式

str=*(parr+2);//*(parr+2)是指针表达式

由于指针表达式的结果是一个指针，所以指针表达式也具有指针所具有的四

个要素：指针的类型，指针所指向的类型，指针指向的内存区，指针自身占据的

内存。

好了，当一个指针表达式的结果指针已经明确地具有了指针自身占据的内存

的话，这个指针表达式就是一个左值，否则就不是一个左值。

在例七中，&a不是一个左值，因为它还没有占据明确的内存。*ptr是一个左

值，因为*ptr这个指针已经占据了内存，其实*ptr就是指针pa，既然pa已经在内

存中有了自己的位置，那么*ptr当然也有了自己的位置。


第五章。数组和指针的关系

如果对声明数组的语句不太明白的话，请参阅我前段时间贴出的文?lt;<如何

理解c和c++的复杂类型声明>>。

数组的数组名其实可以看作一个指针。看下例：

例八：

int array[10]={0,1,2,3,4,5,6,7,8,9},value;
...
...
value=array[0];//也可写成：value=*array;
value=array[3];//也可写成：value=*(array+3);
value=array[4];//也可写成：value=*(array+4);
上例中，一般而言数组名array代表数组本身，类型是int [10]，但如果把a
rray看做指针的话，它指向数组的第0个单元，类型是int *，所指向的类型是数

组单元的类型即int。因此*array等于0就一点也不奇怪了。同理，array+3是一个

指向数组第3个单元的指针，所以*(array+3)等于3。其它依此类推。


例九：

例九：

char *str[3]={
"Hello,this is a sample!",
"Hi,good morning.",
"Hello world"
};
char s[80]；

strcpy(s,str[0]);//也可写成strcpy(s,*str);
strcpy(s,str[1]);//也可写成strcpy(s,*(str+1));
strcpy(s,str[2]);//也可写成strcpy(s,*(str+2));
上例中，str是一个三单元的数组，该数组的每个单元都是一个指针，这些指

针各指向一个字符串。把指针数组名str当作一个指针的话，它指向数组的第0号

单元，它的类型是char**，它指向的类型是char *。

*str也是一个指针，它的类型是char*，它所指向的类型是char，它指向的地

址是字符串"Hello,this is a sample!"的第一个字符的地址，即'H'的地址。

str+1也是一个指针，它指向数组的第1号单元，它的类型是char**，它指向

的类型是char *。

*(str+1)也是一个指针，它的类型是char*，它所指向的类型是char，它指向

"Hi,good morning."的第一个字符'H'，等等。


下面总结一下数组的数组名的问题。声明了一个数组TYPE array[n]，则数组

名称array就有了两重含义：第一，它代表整个数组，它的类型是TYPE [n]；第二

，它是一个指针，该指针的类型是TYPE*，该指针指向的类型是TYPE，也就是数组

单元的类型，该指针指向的内存区就是数组第0号单元，该指针自己占有单独的内

存区，注意它和数组第0号单元占据的内存区是不同的。该指针的值是不能修改的

，即类似array++的表达式是错误的。

在不同的表达式中数组名array可以扮演不同的角色。

在表达式sizeof(array)中，数组名array代表数组本身，故这时sizeof函数

测出的是整个数组的大小。

在表达式*array中，array扮演的是指针，因此这个表达式的结果就是数组第

0号单元的值。sizeof(*array)测出的是数组单元的大小。

表达式array+n（其中n=0，1，2，....。）中，array扮演的是指针，故arr
ay+n的结果是一个指针，它的类型是TYPE*，它指向的类型是TYPE，它指向数组第

n号单元。故sizeof(array+n)测出的是指针类型的大小。

例十：

int array[10];
int (*ptr)[10];
ptr=&array;
上例中ptr是一个指针，它的类型是int (*)[10]，他指向的类型是int [10]
，我们用整个数组的首地址来初始化它。在语句ptr=&array中，array代表数组本

身。


本节中提到了函数sizeof()，那么我来问一问，sizeof(指针名称)测出的究

竟是指针自身类型的大小呢还是指针所指向的类型的大小？答案是前者。例如：


int (*ptr)[10];
则在32位程序中，有：

sizeof(int(*)[10])==4
sizeof(int [10])==40
sizeof(ptr)==4
实际上，sizeof(对象)测出的都是对象自身的类型的大小，而不是别的什么

类型的大小。


第六章。指针和结构类型的关系

可以声明一个指向结构类型对象的指针。

例十一：

struct MyStruct
{
int a;
int b;
int c;
}
MyStruct ss={20,30,40};//声明了结构对象ss，并把ss的三个成员初始

化为20，30和40。

MyStruct *ptr=&ss;//声明了一个指向结构对象ss的指针。它的类型是

MyStruct*,它指向的类型是MyStruct。

int *pstr=(int*)&ss;//声明了一个指向结构对象ss的指针。但是它的

类型和它指向的类型和ptr是不同的。


请问怎样通过指针ptr来访问ss的三个成员变量？

答案：

ptr->a;
ptr->b;
ptr->c;
又请问怎样通过指针pstr来访问ss的三个成员变量？

答案：

*pstr；//访问了ss的成员a。

*(pstr+1);//访问了ss的成员b。

*(pstr+2)//访问了ss的成员c。

呵呵，虽然我在我的MSVC++6.0上调式过上述代码，但是要知道，这样使用p
str来访问结构成员是不正规的，为了说明为什么不正规，让我们看看怎样通过指

针来访问数组的各个单元：

例十二：

int array[3]={35,56,37};
int *pa=array;
通过指针pa访问数组array的三个单元的方法是：

*pa;//访问了第0号单元

*(pa+1);//访问了第1号单元

*(pa+2);//访问了第2号单元

从格式上看倒是与通过指针访问结构成员的不正规方法的格式一样。

所有的C/C++编译器在排列数组的单元时，总是把各个数组单元存放在连续的

存储区里，单元和单元之间没有空隙。但在存放结构对象的各个成员时，在某种

编译环境下，可能会需要字对齐或双字对齐或者是别的什么对齐，需要在相邻两

个成员之间加若干?quot;填充字节"，这就导致各个成员之间可能会有若干个字节

的空隙。

所以，在例十二中，即使*pstr访问到了结构对象ss的第一个成员变量a，也

不能保证*(pstr+1)就一定能访问到结构成员b。因为成员a和成员b之间可能会有

若干填充字节，说不定*(pstr+1)就正好访问到了这些填充字节呢。这也证明了指

针的灵活性。要是你的目的就是想看看各个结构成员之间到底有没有填充字节，

嘿，这倒是个不错的方法。

通过指针访问结构成员的正确方法应该是象例十二中使用指针ptr的方法。


第七章。指针和函数的关系

可以把一个指针声明成为一个指向函数的指针。

int fun1(char*,int);
int (*pfun1)(char*,int);
pfun1=fun1;
....
....
int a=(*pfun1)("abcdefg",7);//通过函数指针饔煤?
可以把指针作为函数的形参。在函数调用语句中，可以用指针表达式来作为

实参。

例十三：

int fun(char*);
int a;
char str[]="abcdefghijklmn";
a=fun(str);
...
...
int fun(char*s)
{
int num=0;
for(int i=0;i
{
num+=*s;s++;
}
return num;
)
这个例子中的函数fun统计一个字符串中各个字符的ASCII码值之和。前面说

了，数组的名字也是一个指针。在函数调用中，当把str作为实参传递给形参s后

，实际是把str的值传递给了s，s所指向的地址就和str所指向的地址一致，但是

str和s各自占用各自的存储空间。在函数体内对s进行自加1运算，并不意味着同

时对str进行了自加1运算。


第八章。指针类型转换

当我们初始化一个指针或给一个指针赋值时，赋值号的左边是一个指针，赋

值号的右边是一个指针表达式。在我们前面所举的例子中，绝大多数情况下，指

针的类型和指针表达式的类型是一样的，指针所指向的类型和指针表达式所指向

的类型是一样的。

例十四：

1。 float f=12.3;
2。 float *fptr=&f;
3。 int *p;
在上面的例子中，假如我们想让指针p指向实数f，应该怎么搞？是用下面的

语句吗？

p=&f;
不对。因为指针p的类型是int*，它指向的类型是int。表达式&f的结果是一

个指针，指针的类型是float*,它指向的类型是float。两者不一致，直接赋值的

方法是不行的。至少在我的MSVC++6.0上，对指针的赋值语句要求赋值号两边的类

型一致，所指向的类型也一致，其它的编译器上我没试过，大家可以试试。为了

实现我们的目的，需要进行"强制类型转换"：

p=(int*)&f;
如果有一个指针p，我们需要把它的类型和所指向的类型改为TYEP*和TYPE，

那么语法格式是：

(TYPE*)p；

这样强制类型转换的结果是一个新指针，该新指针的类型是TYPE*，它指向的

类型是TYPE，它指向的地址就是原指针指向的地址。而原来的指针p的一切属性都

没有被修改。


一个函数如果使用了指针作为形参，那么在函数调用语句的实参和形参的结

合过程中，也会发生指针类型的转换。

例十五：

void fun(char*);
int a=125,b;
fun((char*)&a);
...
...
void fun(char*s)
{
char c;
c=*(s+3);*(s+3)=*(s+0);*(s+0)=c;
c=*(s+2);*(s+2)=*(s+1);*(s+1)=c;
}
}
注意这是一个32位程序，故int类型占了四个字节，char类型占一个字节。函

数fun的作用是把一个整数的四个字节的顺序来个颠倒。注意到了吗？在函数调用

语句中，实参&a的结果是一个指针，它的类型是int *，它指向的类型是int。形

参这个指针的类型是char*，它指向的类型是char。这样，在实参和形参的结合过

程中，我们必须进行一次从int*类型到char*类型的转换。结合这个例子，我们可

以这样来想象编译器进行转换的过程：编译器先构造一个临时指针 char*temp，

然后执行temp=(char*)&a，最后再把temp的值传递给s。所以最后的结果是：s的

类型是char*,它指向的类型是char，它指向的地址就是a的首地址。


我们已经知道，指针的值就是指针指向的地址，在32位程序中，指针的值其

实是一个32位整数。那可不可以把一个整数当作指针的值直接赋给指针呢？就象

下面的语句：

unsigned int a;
TYPE *ptr;//TYPE是int，char或结构类型等等类型。

...
...
a=20345686;
ptr=20345686;//我们的目的是要使指针ptr指向地址20345686（十进制

）

ptr=a;//我们的目的是要使指针ptr指向地址20345686（十进制）

编译一下吧。结果发现后面两条语句全是错的。那么我们的目的就不能达到

了吗？不，还有办法：

unsigned int a;
TYPE *ptr;//TYPE是int，char或结构类型等等类型。

...
...
a=某个数，这个数必须代表一个合法的地址；

ptr=(TYPE*)a；//呵呵，这就可以了。

严格说来这里的(TYPE*)和指针类型转换中的(TYPE*)还不一样。这里的(TYP
E*)的意思是把无符号整数a的值当作一个地址来看待。

上面强调了a的值必须代表一个合法的地址，否则的话，在你使用ptr的时候

，就会出现非法操作错误。


想想能不能反过来，把指针指向的地址即指针的值当作一个整数取出来。完

全可以。下面的例子演示了把一个指针的值当作一个整数取出来，然后再把这个

整数当作一个地址赋给一个指针：

例十六：

int a=123,b;
int *ptr=&a;
char *str;
b=(int)ptr;//把指针ptr的值当作一个整数取出来。

str=(char*)b;//把这个整数的值当作一个地址赋给指针str。


好了，现在我们已经知道了，可以把指针的值当作一个整数取出来，也可以

把一个整数值当作地址赋给一个指针。


第九章。指针的安全问题

看下面的例子：

例十七：

char s='a';
int *ptr;
ptr=(int*)&s;
*ptr=1298；

指针ptr是一个int*类型的指针，它指向的类型是int。它指向的地址就是s的

首地址。在32位程序中，s占一个字节，int类型占四个字节。最后一条语句不但

改变了s所占的一个字节，还把和s相临的高地址方向的三个字节也改变了。这三

个字节是干什么的？只有编译程序知道，而写程序的人是不太可能知道的。也许

这三个字节里存储了非常重要的数据，也许这三个字节里正好是程序的一条代码

，而由于你对指针的马虎应用，这三个字节的值被改变了！这会造成崩溃性的错

误。

让我们再来看一例：

例十八：

1。 char a;
2。 int *ptr=&a;
...
...
3。 ptr++;
4。 *ptr=115;
该例子完全可以通过编译，并能执行。但是看到没有？第3句对指针ptr进行

自加1运算后，ptr指向了和整形变量a相邻的高地址方向的一块存储区。这块存储

区里是什么？我们不知道。有可能它是一个非常重要的数据，甚至可能是一条代

码。而第4句竟然往这片存储区里写入一个数据！这是严重的错误。所以在使用指

针时，程序员心里必须非常清楚：我的指针究竟指向了哪里。

在用指针访问数组的时候，也要注意不要超出数组的低端和高端界限，否则

也会造成类似的错误。

在指针的强制类型转换：ptr1=(TYPE*)ptr2中，如果sizeof(ptr2的类型)大

于sizeof(ptr1的类型)，那么在使用指针ptr1来访问ptr2所指向的存储区时是安

全的。如果sizeof(ptr2的类型)小于sizeof(ptr1的类型)，那么在使用指针ptr1
来访问ptr2所指向的存储区时是不安全的。至于为什么，读者结合例十七来想一

想，应该会明白的。
有讲到多少就快放学了。好了，我也不多说了，今天就这样吧

程序员考试补课笔记-第十三天

　　今天特别的兴奋，起床也起得特别的早。在走之前我把电脑开了，那当然是为了做服务器，我不知道我开学后能不能够这样做，因为家里的一些因素。不过只要能为大家服务我已经很开心了，而且也一种强激的幸福感，这种幸福并不是一般的家庭幸福。我为坚持做下去的，我也常常问一些网友关于这件事，他们都说只有你自己可以就行了，他们都支持我坚持做下去。好吧，说远了离题了，我说说今天的补课吧。
　　今天的课程也令我吃了一惊，是讲数据结构里的树。为什么队列和堆栈都没有讲就直接讲树呢？会不会太快了一点，而且我们刚放完假有些人都没有集中精神到课堂来。不过我会相信老师的选择的，应该有他的理由。那么就来讲讲树的一些基本概念，大家都知道树是数据结构里的非线性结构之一，和之前说的链表是完全不同的，链表就只有前驱和后继结点，但树就不是了，他可以有很多的结点，称为分支结点，而且他的分支结点又可以有分支结点。因为树接触到的概念太多了，只好自己看一下书才行。树运用得很广范，像我们操作系统里文件管理就是了，多级的目录。二级目录就像树的子树，而且子树里可能还有很多的子树，越往下就越多级。

　　我们来试试定义一个树的结构，一般树都分得很随意，所有我们这里也随便画一个树来说一下。看图第十三天图一我们看到圆圈就代表一个结点，而且最顶的那个就是根结点，往下的就是子结点。子结点的上一个就是父结点，同一级的结点左右都是为兄弟结点。我们按照这样的结构定义一个，如下：
　　struct tree
　　{
　　　　int data;
　　　　struct tree *next; /*右兄弟结点*/
　　　　struct tree *pre; /*左兄弟结点*/
　　　　struct tree *up; /*父结点*/
　　　　struct tree *down; /*子结点*/
　　};
下面来看看如何建立一棵树。
　　struct tree *p,*r;
　　r=(struct tree *)malloc(sizeof(struct tree)); /*建立根结点空间*/
　　r->data=3; /*根结点赋值*/
　　r->next=r->pre=r->up=NULL;
　　p=(struct tree *)malloc(sizeof(struct tree)); /*建立第二个结点*/
　　r->down=p; /*根结点的子结点连向新的子结点*/
　　p->data=5; /*子结点赋值*/　
　　p->pre=NULL;
　　p->next=(struct tree *)malloc(sizeof(struct tree));
　　p->next->data=2;
　　p->next->pre=p;
　　　　　:
　　　　　:
　　　　　:
　　因为结点多而无规律性，所有这种建立方法是不能采用的，现在只是拿出来研究一下一棵树是如何建立起来的。
　　现在说说另一种树“二叉树”。因为二叉树与一般的树结构比较，二叉树在结构上更规范和更有确定性，因此，应用也比树更为广泛。二叉树与树不同，首先二叉树可以为空，空的二叉树没有结点；另外，在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。
二叉树又是如何建立的呢？这里很简单，因为二叉树有其规律性，下面请看
　　typedef struct bnode
　　{
　　　　int data;
　　　　struct bnode *left,*right;
　　}btree;
　　void creat(btree *b)
　　{
　　　　int x;
　　　　btree *s;
　　　　b=NULL;
　　do
　　{
　　　　scanf("%d",&x);
　　　　s=(btree *)malloc(sizeof(btree));
　　　　s->data=x;
　　　　s->left=s->right=NULL;
　　　　insert(b,s);
　　}
}
　　void insert(btree *b,btree *s)
　　{
　　　　if(b==NULL) b=s;
　　　　else if(s-data==b->data) return();
　　　　else if(s-data<b->data) insert(b->left,s);
　　　　else if(s-data>b->data) insert(b->right,s);
　　}
　　这条程序不单只建立了一个树，而且还给排好了序（左小右大）。输入相应的数值看看结果，如图第十三天图二。
　　今天也就是这些了，还有得就是要多看些递归的程序，因为树的建立和操作离不开递归。还有的就是大家做做如下一题，就是已知有一个无序的二叉树，让我们用中序遍历排列成由大到小的程序。

程序员考试补课笔记-第十四天

　　今天继续是讲二叉树，树一个重要的操作就是遍历。所谓遍历就是输出所有的结点，二叉树不同于树只有前序和后序遍历，因为二叉树左右子树木特点，所有还有另一种遍历方法，就是中序。这些遍历也十分简单，最主要的还是看根遍历的前后来分别是前中后序遍历的。下面看图第十四天这些颜色圈着代表分别当一个树来看，所有我们知道其规律就可以写出程序来了，程序也十分简单，如下：
out1(btree *t) /*前序遍历*/
{
　　printf("%d",t->data);
　　out1(t->left);
　　out1(t->right);
}
out2(btree *t) /*中序遍历*/
{
　　out2(t->left);
　　printf("%d",t->data);
　　out2(t->right);
}
out3(btree *t) /*后序遍历*/
{
　　out3(t->left);
　　out3(t->right);
　　printf("%d",t->data);
}
　　上面三种遍历是不是很简单（这个递归想一想就明白的了），而且他们很像似只是改变了行位置，我们由此可以看出如果是前序的那个输出是最先的，跟着才是进入左树到右树。看完了遍历就看看二叉查找树，二叉查找树是这样的一种树，他的左结点都小于根，右结点都大于左结点。有这么一种性质所以他的插入特别好办，用中序遍历的方法设计这个排序算法特别好，因为这个树本来就是这样排序下来的。下面就来看看程序是如何实现的
insert(btree *h,btree *p)
{
　　if(h= =NULL) h=p; p->left=p->right=NULL; /*最后一个结点一定是没有左右子树*/
　　else
　　{
　　　　if(p->data<h->data) insert (h->left);
　　　　if(p->data>h->data) insert(h->right);
　　}
}
　　看上去很简单的几行，可是因为递归就得弄明白一些思路，看看它是如何产生插入到合适的位置，和前一堂课的建立二叉树思路一样，也是比较他的值大小排位置。大家要好好的看明白。就是因为我们班里的几个同学都对树比较陌生，跟不上来所以老师决定先把树告一断落，其实树还有很多方面的知识还没有讲到，只好等过一排思维清晰了才可以继续，其实如果我之前没有自己看过一下，到老师说的时候可能真的听不明白，突意间飞来的大难点啊。
　　时间真的用了很多在这些树上，而且还没有什么大的效果。老师也马上看机行事，跳过这节来讲一下查找这章。到于查其实我们平常也接触得多了，特别是我以前学Foxbase的时候，基本上什么都离不开查找，不过当时的查找就是这么一条命令就搞定了。现在要自己编出来也真的挺好玩的，以前完全封装性的Foxbase命令，今天就要编成这个系统的C语言来深入研究它，之前说的链表和结构就是用来做数据库的了（如果我没有估错的话）。说多了费了，马上讲讲学习查找的情况。顺序查找相信大家都知道原理了，因为一个一个顺序的判断是否相等这是最常见的了。我在这里就不再多讲，继续讲下一个，折半查找法。在讲这个之前老师和我们做了一个游戏，就是他在纸上写下一个数值，范围在1到1000内让我们来猜，如果我们说的数大过这个数老师就是太大了，反之就太小了。其实这个折半原理早就在QB里见过了，也没有什么难度嘛。很快我们就按照那个方法给猜出来了得数，老师都见我们懂了的样子就直接叫我们写个程序好了，当时我一时看到这题有重复的规律性就一直以递归的思路来做这题了，可是我错了，不过这个错令我学到了另一个技巧。下面先来看看我的程序，如下：
假如a[]已经是有了值，而且还是顺序排好的了。
serch(int r, int k, int n)
{
　　int mid;
　　if(r>k) return(-1);
　　else
　　{
　　　　mid=(r+k)/2;
　　　　if(a[mid]>n) serch(r,mid-1,n);
　　　　if(a[mid]<n) serch(mid+1,k,n);
　　　　if(a[mid]= =n) return(mid) /*注意就是这里有问题了*/
　　}
}
　　好像看上去没有什么问题似的，其实问题都挺大的，因为返回值根本不能返到最顶的那个自调用里，就只能返回一层，所有我的答案也根本出不来嘛。虽然老师还是赞了我一下会去用递归来做这题（其实因为本来循环可以很简单的可以实现了，而且不会浪费那么多的空间了），不过错还是错的。老师按照我的这个思路写了一个新的出来，如下：
serch(int r,int k,int n)
{
　　int mid;
　　if (r > k) return (-1);
　　mid =(r+k)/2;
　　if(a[mid]= =n) return(mid);
　　else
　　{
　　　　a[mid]<n ? r=mid+1; k=mid-1;
　　　　return (serch(r,k,n) ); /*巧妙的就是这里了*/
　　}
}
　　一条程序可以反应该人的水平说的真没错，这条程序几个地方都写得很好，特别巧妙的可以令递归返回值到最顶的那个可真棒啊。就这样随着时间的到来，我们也差不多放学了，我还真的要努力才行了，我要努力再努力，坚持再坚持。

程序员考试补课笔记-第十五天

　　今天续着上堂的查找一章，上回已经讲了顺序查找和二分查找，这两个都是经常用到的。还有一种是特别的查找方法就是散列表（这里说明一下，这个查找方法是有几种不同的名字的，杂凑表和哈希表）。因为这个可能讲起来会用很多时间，老师也没有细详的解说，只是举了一个相对的思想出来，如下：
　　Ri　　 keyi
　a(0)　=　20
　a(1)　=　30
　a(2)　=　40
　a(3)　=　50　　　　addr(Ri)=H(keyi)
　　　　　　　　　　　Ri=keyi/10-2　这个关系
　　就是这样，它对不同的问题当然有不同的关系，只能只要知道这个思想就好了。教程里的查找也就是这三种了，现在开始讲排序了。排序相对查找来说多了很多的方法，我们之前也碰过好几种排序的方法了，就是前一章的二叉树排序就是了，还有很早之前讲过的冒泡排序，我想很多人都应该知道这个经典的排序了吧。现在下来要讲的是直接插入排序法，这种方法的优势在于已经排好序的结点插入一个新的结点，有顺序的这样就可以用到上章学过的折半查找就可以找到该插入的位置了。其实给出一个没有序的一排数组，可以把它划分为两大部份，一部份是已排好序的结点，而另一部分则是待插入的结点，这样就可以模拟这个算法了，看看第十五天图一
这里可以清楚看到整个的思路是如何的。下面我们就要用C语言来到描述这个排序算法了，一共有好种种版本，大家一个一个的对比看看，看谁的效率高。
　　int a[10]={8,7,10,30,5,1,7,10,0,25};
　　int i,j,k;
　　for(i=1;i<n;i++)
　　{
　　　　for(t=e,j=i-1;j>=0 && t<e[j];j--)
　　　　　　e[j+1]=e[j];
　　　　e[j+1]=t;
　　}
另一个
　　for(i=1;i<=9;i++)
　　　　for(j=0;j<=i-1;j++)
　　　　{
　　　　　　if(a[j]>a)
　　　　　　{
　　　　　　　　t=a[j];
　　　　　　　　a[j]=a;
　　　　　　　　a=t;
　　　　　　}
　　　　}
再另一个
　　for(i=1;i<n;i++)
　　{
　　　　k=a;
　　　　for(j=i-1;j>=0;j--)
　　　　　　if(k>a[j]) break;
　　　　　　else a[j+1]=a[j];
　　　　a[j+1]=k;
　　}
　　以前三个程序请大家自己分析，一定要自己动过脑去想。好了，难题终于又是到最后出来了，就是把这个排序的算法变为链表形式的，大家有没有想到呢？我们都急着笔去试了，可是最后还是不行，如果对于至前没有接触过这类型的是正常的情况，所有我们都没有做出来。下面看看老师写的程序好了：
前一些定义之类的略
　　p=h->next;h->next=NULL;
　　while(p)
　　{
　　　　if(p->data<h->data)
　　　　{
　　　　　　q=p->next;
　　　　　　p->next=h;
　　　　　　h=p;p=q;
　　　　}
　　　　else
　　　　{
　　　　　　q=h;r=q->next;
　　　　　　while(r && p->data > r->data)
　　　　　　{
　　　　　　　　q=r;r=r->next;
　　　　　　}
　　　　　　q->next=p;p=p->next;
　　　　　　q->next->next=r;
　　　　}
　　}
　　今天我有些失落，可能是因为做题的事吧，反正整个人都不知道怎么的，不过我还是会坚持，我会继续加把劲，希望大家可以和我一齐努力吧！

程序员考试补课笔记-第十六天

今天继续是链表方式的排序，前天的一题大家有没有弄懂了。弄不懂不要紧，这是要慢慢来的，急不来。
p=h->next;h->next=NULL;
　　while(p)
　　{
　　　　if(p->data<h->data)
　　　　{
　　　　　　q=p->next;
　　　　　　p->next=h;
　　　　　　h=p;p=q;
　　　　}
　　　　else
　　　　{
　　　　　　q=h;r=q->next;
　　　　　　while(r && p->data > r->data)
　　　　　　{
　　　　　　　　q=r;r=r->next;
　　　　　　}
　　　　　　q->next=p;p=p->next;
　　　　　　q->next->next=r;
　　　　}
　　}
　　按照这条程序的思路让我们来想想整个的过程，这个程序分了两部份，一部分就是如果当前待排序的结点值是小于头的结点值就直接把它插到第一个里，因为如果对比头的那个已经小于它了，所以后面的都不要比较了。如果待插入排序的结点值不是小于当前头结点的话，那么就应该要找到合适的位置才可以插入该结点了，我们来看q和r指针是用来做什么来的，它指向头指针h和r指向q指针的一下个结点，因为我们知道单向链表的缺点是不能知道它前面的结点是什么，所以一断开就可能会导至链表失败。我们的目的就是用q来保存它的前一个结点。在while循环里就是有两种可能，一种是r为空，这里r为空时就是说明了这个链表已经比到最后一个了，所以直接把待插入的结点插在后面就行了。至于p->data>r->data是要等p->data比r->data小时就说明已经找到该插入的位置里，我们就可以继续往下进行插入的步骤。while里面的是如果这两个条件都是真的时候说明还没有找到，那么就让两个双链指针往后移一个继续比较，等找到符合了就可以插入了。
如果还是比较模糊的话大家不要紧，再看看下面这条程序：
struct node *li_sort(struct node *h)
{
　　struct node *t,*s,*u,*v;
　　s=h->next;
　　h->next=NULL;
　　while(s!=NULL)
　　{
　　　　for(t=s,v=h;v!=NULL && v->data < t->data; u=v,v=v->next);
　　　　　　s=s->next;
　　　　if(v==h) h=t;
　　　　else u->next=t;
　　　　t->next=v;
　　}
}
　　我们可以看出这个程序很像上面的，但它更简化了，把整个判断都在一个for语句里了。我们慢慢来分析一下这个程序，相信只有去想的话大家应该都会明白的了。S=h->next 和h->next=NULL这两句都是同上一样，把他们分开成已排序部份和待排序部份。跟着主要的是要看看for语句里的，因为所有判断条件都在这里了。这里t是临时变量代s的，s的角色就是当前要插入的那个结点，v和u指针都和上面一程序的q和r是一样的，都是用来补缺单向链表的缺点。这里的条件也是一样，和上面程序的分别就是它整合了两种情况的可能性在，跟着下面的程序又作了一个条件来分别这是插入头的还是中间的。好了，还是一句要自己的脑根去想，这里第十六天图一里有整个的过程。
　　说完了单向链表的当然就是要讲讲双向链表了，因为双向链表可以往前移的关系，所以程序也比较好办，不过麻烦的就是它的插入和删除操作，也当再一次练习链表操作的机会吧。大家先自己想想，再试着写出程序来，有了上面单向链表的基础应该也很容易可以跟着思路编出。大家把编好的程序发到http://zhgpa.vicp.net/bbs 程序员考试那版里，看看大家的方法有何不同一齐讨论。大家先不要看我下面的程序：
一些定义略
while(p)
{
　　for(q=p->pre,r=p;q && p->data < q->data; q=q->pre);
　　p=p->next;
　　r->pre->next=p;
　　if (p) p->pre=r->pre;
　　if(q)
　　{
　　　　p->next=q->next;
　　　　if(q->next) q->next->pre=p;
　　　　p->pre=q;
　　　　q->next=p;
　　}
　　else
　　{
　　　　r->next=h;
　　　　r->pre=NULL;
　　　　h->pre=r;
　　}
}
　　好了，大家的程序又是如何呢？希望大家多多讨论。这几天虽然学的内容不算多，但是就从中吸受到很多经验，现在链表的操作又更一步的前进了。懂得了分析程序的一些方法，编程这条路看起来真的很漫长，我在这条路里我什么都不懂，可是我会坚持。

程序员考试补课笔记-第十七天

离上一次的补课时间看起来有整整的五天，但是在我眼里只是短短的几眨眼。因为我这几天里脑海里根本没有什么事情发生过似的，每天过着重复而简单的生活。怎样简单法？那那当然就是坐在电脑前啦，可以说一坐就坐上了整天。嗯！好，不说这个了，这不是我想要说的重点。
　　我想问问大家有没有去认真的学习过文件那章？这里说实话，在之前我自学C语言的时候我并没有太重视过它，随便的把他翻了过去（嗯！这么简单，我懂了，过吧）。真到前几天放假这段时间里我说了个苦头，我发现我自己根本不懂文件里的文本流和二进制流的概念啊。天啊！从文字表面上来说很简单嘛，不就是文件内容是ASCII码的就是文本流嘛，而二进制流当然就是内容是二进制嘛。哈哈这不简单。当前我也是这么想的，文本流的概念是理解对了，可是进制流把我搞糊涂了。我还总是认为我打开的那个文件就是以二进制形式出来"101100101"这样的，可是我看到的并不是这样，而是一些我根本不知道的符号。这一切一切都在这几天里把我折磨到连忙叫苦，不过这一切都过去了。我真正认识到这些概念，其实二进制流并不是真的就是存放的内容是101001这样的，它和内存形式中的一样，所以每个怪字符都是由这些连续的二进制每8位构成的。唉！~！害我苦了这么多天！
　　今天回到学校第一个要讲的内容当然就是放假期间布置的作业啦，嘻嘻，不要告诉别人我的程序是昨晚做的喔，而且还是有BUG在的呢！现给出我原来没有改时候的原程序吧：
#include <stdio.h>
#define SIZE 5
typedef struct student
{
　　int num;
　　char name[10];
　　int score;
　　float averge;
　　struct student *next;
}student;
void main()
{
　　FILE *fp;
　　student *h,*p;
　　int i;
　　if( (fp=fopen("stud.txt","wb")==NULL )
　　{
　　　　printf("Can't open the file";
　　　　exit(1);
　　}
　　h=p=(student *)malloc(sizeof(student));
　　for(i=0;i<SIZE;i++)
　　{
　　　　printf("please input num name score\n";
　　　　scanf("%d%s%d",&p->num,p->name,&p->score); /*这里输入经常有莫名奇怪的问题*/
　　　　p->averge=p->score/3;
　　　　p->next=(student *)malloc(sizeof(student));
　　　　p=p->next;
　　}
　　p->next=NULL;
　　for(p=h,i=0;i<SIZE;i++,p=p->next)
　　{
　　　　printf("%s",p->name);
　　　　fwrite(p,sizeof(student),1,fp); /*这里初以为用指针不行*/
　　}
　　fclose(fp);
}
　　这里指出来两个问题，第一个问题之前我也有遇到过，不过当时没有理会，今天吃吃苦。不过现在网络方便，而且CSDN高手如云，有问题当然就是到CSDN啦（不是在卖广告吧？哈哈）。CSDN上得知原来scanf（）这个函数有个缓冲的问题，所以导致输入次数无端端的减少，这里有个方法就是给scanf("%d%s%d",&p->num,p->name,&p->score); 这句之上加上一个处理缓冲的函数fflush(stdin);至于用法大家查查书就行了。第二个问题得知原因之后更不是问题了，其实本身这就是对的。为什么我为产生这个误解，原因都是我试着读入数据来看的时候产生的，下面加下一些补充后程序如下：
#include <stdio.h>
#define SIZE 5
typedef struct student
{
　　int num;
　　char name[10];
　　int score;
　　float averge;
　　struct student *next;
}student;
void main()
{
　　FILE *fp;
　　student *h,*p;
　　student test[SIZE]; /* 加上这个定义是为了下面测试用 */
　　int i;
　　if( (fp=fopen("stud.txt","wb")==NULL )
　　{
　　　　printf("Can't open the file";
　　　　exit(1);
　　}
　　h=p=(student *)malloc(sizeof(student));
　　for(i=0;i<SIZE;i++)
　　{
　　　　printf("please input num name score\n";
　　　　fflush(stdin); /* 这里加上这句解决输入缓冲问题*/
　　　　scanf("%d%s%d",&p->num,p->name,&p->score);
　　　　p->averge=p->score/3;
　　　　p->next=(student *)malloc(sizeof(student));
　　　　p=p->next;
　　}
　　p->next=NULL;
　　for(p=h,i=0;i<SIZE;i++,p=p->next)
　　{
　　　　printf("%s",p->name);
　　　　fwrite(p,sizeof(student),1,fp); /*这里初以为用指针不行*/
　　}
　　
　　/***这里加上读入文件***/
　　for(i=0;i<SIZE;i++)
　　{
　　　　fread(test[ i ],sizeof(student),1,fp);
　　　　printf("%d%s%d%3.1f\n",test.num, test.name, test.score, test.averge);
　　}
　　fclose(fp);
}
　　看上面加上了读入文件数据到结构数组test里，那么我们就看看结果吧，编译成果，好了，你是不是根本看不到你想要的结果呢，而得到是一堆莫名奇妙的符号呢，是的，没错，就是因为这点我才起初误认为写入数据fwrtie对指针的问题。好了下面我们解决这个迷吧（可能有些高手已经知道了），其实就是文件指针的问题，当我们上面那个写入到文件事那个指针已经到底了，到输入到数组里时当然就是不知明的数据了。
　　fseek(fp,0,0);
　　/***这里加上读入文件***/
　　for(i=0;i<SIZE;i++)
　　{
　　　　fread(test[ i ],sizeof(student),1,fp);
　　　　printf("%d%s%d%3.1f\n",test.num, test.name, test.score, test.averge);
　　}
　　在这句之前加上fseek(fp,0,0); 这个函数，这是和文件函数相配对的随机读入函数。这里参数都是0是说明文件指针指向最顶，好了，看看结果是不是我们想要的结果了。
下面继续深入研究一下文件这章吧，你有没有想过把本身你写的这个程序C程序显示在屏幕上呢，当然不是用DOS的命令type 等一些其它的命令啦，就是直接用C语言程序把自身读出来。其实这个问题实现起来太简单了，你有看过老潭的那章吗？记得文件COPY的那个小实例吗？哈哈~！~！看下程序：
#include <stdio.h>
main()
{
　　FILE *fp;
　　char c;
　　if( (fp=fopen("当前写的文件名","r")==NULL )
　　{
　　　　printf("Can't open the file";
　　　　exit(1);
　　}
　　c=fgetc(fp);
　　whle(!feof(fp))
　　{
　　　　c=fgetch(fp);
　　　　putchar(c);
　　}
}
　　记起来了吗？没错就是这么简单啦，跟着下面的比较有挑战性。我们把自身逆序输出，嘻嘻，其实也不用怕。如果掌握了fseek()和ftell()这两个文件函数就可以了，大家自己试写写，我的程序如下：
#include <stdio.h>
main()
{
　　FILE *fp;
　　char c;
　　long se;
　　if( (fp=fopen("当前写的文件名","r")==NULL )
　　{
　　　　printf("Can't open the file";
　　　　exit(1);
　　}
　　fseek(fp,0,2); /*这里是指向最后的一个字节*/
　　se=ftell(fp); /*结合上面的那个取得总字符数*/
　　for(;se>=0;se--)
　　{
　　　　fseek(fp,se,0);
　　　　fread(&c,,1,1,fp);
　　　　puthcar(c);
　　}
}
　　看看，是不是很可爽很过瘾，自身源程序都倒过来了。好了，文章也该告一段落了。因为今年下午都要上学的原因，自然学的东西也多了，那么……嘻嘻，我的字也很应该多些吧，这样才对得住大家啊。不过因为今天做了很多初程的题目，所以也不太多的写上来了，写一个比较有用的吧，如下：
/*这个程序的作用是将一个字符数组里大写的字母都改为小写*/
void main()
{
　　int i=0;
　　char s[120];
　　printf("Enter a string\n";
　　scanf("%s",s)
　　while( _____ )
　　{
　　　　if( _____ )
　　　　s=s-'A'+'a';
　　　　i++;
　　}
　　printf("%s\n",s);
}
　　如果对于字符串这方面比较熟悉的，相信很快已经想到这题案了吧。这里最吓人的一句就是s=s-'A'+'a'; 其实也没有什么好怕的，大家好好想想把你的答案发到http://zhgpa.vicp.net/bbs（没有办法，我的站点人气太少咯，呵呵），好了，就这样没完没了的结束今天吧。

程序员考试补课笔记-第十八天

什么都不用说了，马上入正题（免得给人说我口水多了，哈哈）。那么今天学了些什么呢？知识当然每天都要吸收，但在乎吸收得多少。有时候一个看起来的小问题，其实足可以引发另一些问题，这一切都是靠自己，看自己怎么对待这些问题。
　　我们现在来做一道初程的题目，大家也不要看少初程的题喔，其实这题我在中程的试题来看到过，不过不同的地方只是把它改为用指针了。所以这里也想说说，其实中程里绝大部份的题都是围绕着指针这灵活的东西（我不把它看作"难搞"，只是太"灵活"，难掌握一些罢了），所以我们考中程的同道中人一定要好好掌握啊。
问题如下：
阅读下列程序说明和C代码，将应填入 __(n)__ 处的字句写在答题纸的对应栏内。
[程序说明]
　　设一个环上有编号为 0～n-1 的 n 粒不同颜色的珠子 ( 每粒珠子颜色用字母表示，n 粒珠子的颜色由输入的字符串表示)。将环中某两粒珠子间剪开，环上珠子形成一个序列，然后按以下规则从序列中取走珠子：首先从序列左端取走所有连续同包珠子;然后从序列右端在剩下珠子中取走所有连续同色珠子，两者之和为该剪开处可取走珠子的粒数。在不同位置剪开，能取走的珠子数不尽相同。
　　本程序所求的是在环上哪个位置剪开，按上述规则可取走的珠子粒数最多。程序中用数组存储字符串。例如，10 粒珠子颜色对应字符串为"aaabbbadcc"，从 0 号珠子前剪开，序列为 aaabbbadcc，从左端取走 3 粒 a 色珠子，从右端取走 2 粒 c 色珠子，共取走 5 粒珠子。若在 3 号珠子前剪开，即 bbbadccaaa 共可取走 6 粒珠子。
【程序】
#include <stdio.h>
int count(char*s，int start，int end)
{
　　int i，c = 0，color = s[start]，step = ( start > end ) ?-1; 1;
　　for ( i = start; s = color ; i += step ) {
　　　　if ( step > 0 && i > end || __(1)__ ) break;
　　　　__(2)__
　　}
　　return c ;
}
void main()
{
　　char t，s[120]; int i，j，c，len，maxc，cut=0 ;
　　printf( "请输入环上代表不同颜色珠子字符串：" ) ;
　　scanf( "%s"，s) ;
　　len = strlen(s) ;
　　for ( i = maxc = 0 ; i < len ; i++ ) { /*尝试不同的剪开方式*/
　　　　c = count(s，0，len-1) ;
　　　　if ( c < len ) c += count( __(3)__ );
　　　　if ( c > maxc) { cut = i ; maxc = c; }
　　　　/*数组s的元素循环向左移动一个位置*/
　　　　t = s[0] ;
　　　　for ( j = 1; j < len ; j++ ) __(4)__ ;
　　　　__(5)__ ;
　　}
　　printf( "在第 %d 号珠子前面剪开，可以取走制个珠子.\n" , cut，maxc ) ;
}
　　这题最重要最重要的一点就是要看懂题目，也因为这个题目比较长，所以令人感到恐惧，所以做起来也会比较紧张。所以我们千万要记住不要给题目先吓倒了，一但了解了它的是什么意思的话，好么好吧了。下面我作个图来分析一下这个程序的作用和操作。图第十八天图一看到了基本的运算。现在一步一步的来到填这几个空，有了大概基本思路就好办了。
　　首先是看主函数里的程序，for ( i = maxc = 0 ; i < len ; i++ ) 这里开始，这个继续是控制了总共有检测多少个珠子，c=count(s,0,len-1)这里调用count()这个函数了，不过这里为什么参数次次都是0为开始呢？其实我们可以再往下看程序
/*数组s的元素循环向左移动一个位置*/
t = s[0] ;
for ( j = 1; j < len ; j++ ) __(4)__ ;
__(5)__ ;
　　这里就清楚的告诉了我们，因为这里巧妙的利用了整个数组往动，所以每次新的下标0都是下一个的新珠子。既然这段都已经看懂了，先填了这两个空吧。第4就是循环里的移动数组，很显然就是s[j-1]=s[j]了，t这里是刚开始的那个0下标，将其填到最后一个下标里s[j-1]，就把整个数组转动了，即第5个空是s[j-1]=t这里可以再看看图第十八天图一。
　　现在知道为什么那个函数参数为什么次次都是零了，可以进入count函数里看个究竟了。这里step=(step>end) ? -1 : 1;妙巧的配合了左右两边查找同色珠子的问题
if ( step > 0 && i > end || __(1)__ ) break;
__(2)__
　　这里的空也不难看出了，因为知道有两种可能性，这里第1个空只判断了正方向还没有判断反方向，大家还等什么，马上填入答案不就是了吗？setp < 0 && i<end 。既然这里是要统计有多少个同色的珠子，c是这里的返回数，那么一定不要说了，一定是c了，可是程序里又没有看到有一个是累加c的，嘻嘻，我来我来，我填第5个空c++就行了嘛（总是挣些简单的问题来答，真TMD）。现在剩下最后一个空，即第三个，上面我们都是统计了正方向的，这个正好就是要取反方面的连续同色珠子数，知道参数形式是int count(char*s，int start，int end)，s是那个字符串，start是开始的位置和end是结未。那么这次是反方面，那当然就是由未下标的那个元素开始找到正方面还没有找到的连续同色珠子，即刚才有连续同色珠子的c, c也是正方向连续同色珠子的结未下标，所以答案也就是s,len-1,c了。
　　嗯~！今天也就是分析了这么一道题，还有就是讲了一下排序的时间复杂度，这个问题对于我来说真的非常的难，我连看个公式也看不懂啊！不过我还是知道通常排序时间复杂度就是那么三种，所以我加以记一记就好了，分别是O(n2)、O(n log2n)、O(n)

这个已经有些难度了..........