准备明年考高程,所以就到网上找了点资料(发现这方面的东西比较少, ),看了一下这个东西,觉得不错,很多都是些基本的东西,特转来与大家分享,特别是也想考高程的朋友,也希望有这方面经验的朋友给予帮助.
这些东西好像是原作者为了考程序员而参加相关的C语言培训时做的听课笔记.好像还没有写完,如果想知道最新的情况请到下面附的网址去看.感谢原作者!
程序员考试补课笔记
huoniaolinx http://www.cnitexam.com
第一天
今天是第一天补课,终于有又机会可以听到林老师的课了,我觉得他比老潭说得还要好呢,虽然我没有听过老潭的课,不过我相信绝大部份在校的人学C语言都是用老潭的《C程序设计》吧。这本书的好处是有很多的,最主要的一点就是可以用生动的例子来说明一些概念,不过还是一点不好的地方,就是本书全都只是围绕着基础来说,没有一些可以让同学深入研究的课题。就我知道机械工业译的一本《C语言设计教程》,这本书有大量的实例练习,而且是围绕着生活的。学习和乐趣合在一齐,我在看这本书时都有好几个特别吸引我的兴趣课题呢！书就介绍到这里吧,还是说回今天补课的情况。
今天因为第一天吧,老师还不太清楚我们的底究竟到那里。是因为我们之前都是全自学的,所以现在要摸一摸底吧。一开始,他直接引入了上界程序员考试的下午的第一道题,是一道编程填空题。如下:
code]
int strcmp( char *s, char *t)
{
while(*s && *t && _______)
{ s++;t++;
}
return ________;
}
[/code]
这是模仿C语言字符函数库里的字符比较函数,当时我第一时间就想到了一种方法,第一空因为大家都没有问题吧,*s和*t这两个都保持为逻辑真就行,表明这个存储单元是用字符的,大家都知道C语言里没有字符串这种变量的,只有字符数组,'\0'这个符号就是用来表明这个字符数组到了结尾了,这里又有一个新的概念要说说的了,就是C语言逻辑里非零的都为真,那么'\0'这个符号就是为零。所以填这个空就应该没有什么太大的难度了,跟着就是还要有一个条件退出循环,因为是比较大小,只要保持一样都继续,所以条件也很显示的可以写出来*s == *t。
至于第二题当时我的思维就销定在条件运算符里,因为返回的值是有三种可以性的,大于返回正数,等于就返回零,小于就返回负数。知道了这三种可能就可以用条件运算符填了,我当时的答案是这样的 *s == *t? 0: *s>;*t ? 1 : -1 ,这是不是很长呢,其实我的答案我也不知道是否对,但是真正的答案是 *s - * t .知道答案为什么是这样吗?当时我也一时给答案吓住啦,因为当时我真想到是用它们本身的比较就可以得出结果(运用ACSII码),*s - *t 如果s指针所指向的单元如果是大于当然就是正数啦,跟着其它的原理一样,这里不再详细说明。
除了引用这道答给我们说了很多的基础知识外,还更详细地给我们介绍了指针,唉！为什么老师说的总是这么的清晰明白,如果当初可以老师教的话就可以走少很多弯路了。算了,说这些话都是没有用的,只有现在能学好就行了。大家都指针的基础还有些吧,这里重要的提一提老师今天反复强调的一个概念,就是指针就是指向地址的一个变量.今天就到这里吧。
第二天
因为前天老师摸到我们的底的关系,所以今天要补一补前面的基础部份。他先是列出一个
数据类型的表,如下:
| 整型
| 字符型
| 基本类型< | | 单精度型
| | 实型(浮点型)< |
| | | 双精度型
| | 枚举类型
|
|
数据类型< | | 数组类型
| 构造类型< | 结构体类型 (结构)
| | 共用体类型 (联合)
| 指针类型
| 空类型
上面这个表,基本类型是我们平常用得最多的,包括整型、字符型、实型(浮点型),就从这里最常用的数据类型说起吧。
说起C语言的数据内容就要说说计算机里存放的数据是究竟怎么一回事,大家应该都知道计算机只可以处理二进制的数吧,因为是硬件的关系(二态器件), 这些只能有两种表示的状态,所以运用到计算机里就显得特别有用了。从现在开始我们要知道计算机处理的所有数据都是二进制数,那么他究竟是怎么运算的呢? 老师先给一些十进制数转换为二进制数的几道题我们做,这些小儿科当然是没问题啦,很简单的就做了出来。老师当然知道我们是会做的了,但是其实是想我们在做这些题目的时候找出更简单的转换方法。例:
1011101 =(93)10 很简单的就可以计算出来了, 我的方法就是传统的计算方法。它们都有自己的位权,第一位就是20,第二位是21, 跟着的都如些类推,将有1的地方乘上该位的数跟着相加起来就等于93了。这里说说其实二进制的次方特别好算,就像我们的内存一样阶梯上去的,1-2-4-8-16-32-64-128-256-512-1024……你知道这规律吗,如果知道是不是计算起来特别别好办呢！
不过老师在这里提出了一个更好的方法,起码比一个一个加上去也快多了。就是将那个要转换的数变为全都是1111111,你知道这个数是多少吗?其实就是有一技巧在里面,把它看成10000000 减 1吧！那么是不是很快就知道10000000是多少呢,没错就是128嘛,再减1就是127了,在些基础上试着将原来的那个二进制数位为零的那两个数求出来, 第一个零在第二位,所以是2,第二个零在第六位,所以是32,将其加起来被127减去就可以得出93了,是不是很简单方便呢(学到东西快交学费啊,哈哈~)。你知道计算机里二进制有几种运算吗?我在这里告诉你,其实就只有这么的一种,就是加法运算(你不要告诉我你连二进制的加法也不会运算,其实就是逢二进一嘛).为什么这样说呢?其实二进制也有减法运算和乘除,但是计算机里有一种叫补码的方法,可以将减法运算变为加法运算,至于怎么实现教师也没有再深入讲下去了(在些补充,乘法也是利用移位来实现转为加法的)。
现在转入到C语言的整型数据里,C语言的整型数据是2字节的,就是16位,最多可以存储65536,他的范围是 -32768 到 32767 。C语言里分有符号类型和无符号类型, 如果是没有符号的整数类型的范围就是0 到 65535 了。关于字符型数据,如果严格来说C语言里根本没有字符这种类型,因为他所存储的是它的ASCII码。直接可以用来和其它的数据类型运算,比如:
CODE:
[Copy to clipboard]
main()
{
char s='A';
int i=2;
s=s+i;
printf("%d",s); /*这里可以直接输出其ASCII码*/
printf("%c",s); /*这里的结果因为上面的语句改变了字符s的字符,输出的是'C'*/
}
那么更不要说字符串了,所以字符串在C语言里也只是用数组来表示,和其它的高级语言不同,有其的字符串类型,而且还是字符和字符串结合在同一种类型里。现在该说一下实型数据了,实数类型通常用在有小数位的一些数据。就像这题一样:
S=1/1+1/3-1/5+1/7……1/2n-1
这个程序是我写的:
CODE:
[Copy to clipboard]
main()
{
int n,i,s;
int r=1;
printf("please input: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
s=s+r/(2*i-1);
r=-1*r;
}
printf("%d",s);
}
这个是考试里的:
CODE:
[Copy to clipboard]
void fun(float *sn, int n)
{
float s=0.0,w,f=-1.0;
int i=0;
for(i=0;i<n;i++)
{
f=___*f; /*这里填 -1 */
w=f / (2*i+1);
s+=w;
}
____=s; /*这里填 *sn */
}
考试里的两个空我都做对了,可是自己写的那个程序就有大问题了,就是答案用了整型数据,从答可知答案应该是小数啊,真的一时的糊涂就可以致命啊！我们几乎所有人都是错了这点,当然也要另类的错法,就是用回来以前QB的一些运算符,^ 这个是QB里的次方运算符,这可真的闹出笑话了。之后是要我们编一个主函数来调用这个函数。
这是我做的
CODE:
[Copy to clipboard]
main()
{
float s;
int n;
printf("please input:");
scanf("%d",&n);
fun(&s,n);
printf("%f",s);
}
这是这么几条简单的语句,不过就难倒了几乎所有人(除了我)。你知道他们的答案吗?让我给大家展示出来吧
CODE:
[Copy to clipboard]
main()
{
float *ss;
int n;
printf("Please input:");
scanf("%d",&n);
fun(*ss,n); /*这里出了问题*／
printf("%f",*ss);
}
他可能还没有了解到C语言里的函数参数的问题吧,既没有定义一个可以存放结果的变量,参数方面也用错了,如果真的要用指针也得要指针指向一个存储单元才行吧。而且还不是传了地址,他反而是试图传一个指针指向单元进函数里,这是绝对错误的。因为该调用的函数是地址,好了,下面给他的程序更正一下。如下:
CODE:
[Copy to clipboard]
main()
{
float *ss,s; /*这里多定义一个单精度的变量*/
int n;
ss=&
printf("Please input:");
scanf("%d",&n);
fun(*ss,n); /*这里出了问题,应该是fun(ss,n) */
printf("%f",*ss);
}
好了,就这样这条程序就完全正确了,不过要是为了节省空间就用我写的那条吧,因为不要多开消一个指针变量。今天写得特别的长,也特别的嗅,望大家见谅了。
第三天
很快的就到了第三天了,接下来的学习任务应该越来越重了。至于今天讲了些什么,现在想起来也觉得没有什么似的,可能因为我之前已经把这今天所讲的内容搞懂搞透的原因吧。不过也得把今天的写下来,也没有什么特别原因的,想有个回忆吧。
今天所讲的都是围绕着数组,我们在C语言里定义数组和其它高级语言定义的不同,这里示出C语言和其它语言的。
C语言 Foxbase
int a[10][10]; dim a(10,10)
是不是符号也不同了,我们以前用惯的都是小括号,但是现在突然来的是中括号真的是有些不习惯呢。但是谁叫我们是学 C 语言呢,不习惯都要得习惯了。还记得以前定数组根本就是不用理会它的地址,只知道用就行了,就算用错了会编译出错。可是C语言可不是呢,一但你定义了一个数组之后,你就得好好的管住它,因为数组出了边界是绝对不会通知你的。数组的定义和调用方法也是很多,真是灵活多变,这里不再重复书上里的东西了。现在就定义一个数组来看看:
int a[10];
如这个表所示,数组定义之后有相对地址,而且数组名a就是存放这些地址的首地址。现在我们多定义一个整型指针变量, int *p; ,让它指向数组a, p=a; 我们试着让指针运算递增一个p++; 我们看到的结果是p指向了新的地址2003,原来的地址是2001,为什么递增一个就移向了2003,而不是2002呢？不是2002才是正确的吗?其实这里就说明了我们定义指针变量为什么要整型了,是因为所有的指针运算都是看自己本身是什么类型的指针才作出什么样的运算的。就是现在是整型类型,整型数据存储是需要2字节的,所以针指运算也是按这个方式来进行,结果很显然就是往下移2了。其实这里说这么多,老潭那本书里基本上都有详细说明介绍,所以我一开始说只要自己有看过书的,应该也很容易明白了(反而上面可能被我说模糊了)。
好了,接下来我们做一些题目吧,这是今天老师给我们出的题,其实也是2001年程序员下午考试里出现过的题目。所以请大家自己也动手做做,多思考,看看谁的方法比较好。 在n行n列矩阵中,每行都有最大数,本程序求这几个最大数中的最小一个。
CODE:
[Copy to clipboard]
#include <stdio.h>;
#define N 100
int a[N][N];
void main()
{
int row,col,max,min,n;
/*输入合法的n和n*n个整数的代码, 注,这里略了一部份到后面练习自己做回*/
for(row=0;row<n;row++)
{
for(max=a[row][0],col=1;col<n;col++)
if ( ) max=a[row][col]; /*max<a[row][col]*/
if ( ) min=max; /**/
else if ( ) min=max;
｝
printf("最大数中的最小数为:%d\n",min);
}
这题可真有些难度,它的难就难在第二个空那里,相信第一个空绝大部分都会做, 可是第二个空呢,真的下不笔了。当时看程序的最后继续两个空后面的语句为什么一样的呢,可真的没有想通,只是要死钻牛解尖,老是想着一定是用数组的,第一个循环里是行,跟着就是列了,可是还是想不到答案,因为我的思路已经大错特错了。最后老师还是说出答案,也说这题真的是比较难。第二空其实是填row==0,为什么这样填呢,是因为这个矩阵里一开始要有一个BASE数做底,所以row==0只出现一次,很自然的就成了第一个比较的基数,跟着这个if语句里的就是比较这几个最大数中的最小一个数了,第二个空填了出来当然答案也就随之可以出来了max<min。看来我现在的功力去考中程还是白费心机吧,因为这只是第一大题啊,有很多难的题都在后几题。那么既然现在知道自己的弱点就应该去好好克服改正它,好了,这只是第一道练习题,跟着下面还有将略了的那部份编出来。
我所写的如下,因为考虑到整数类型界限的问题,我所编的所着重这里。
CODE:
[Copy to clipboard]
printf("
输入二维数组的维数 n:");
scanf("%d",&n);
for(row=0;row<n;row++)
for(col=0;col<n;col++)
{
do
{
printf("please a[%d][%d]",row,col);
scanf("%d",&a[row][col]);
}while(a[row][col]<-32767 && a[row][col]>;32767 );
}
接下的是第二题了,题目如下:
求n*n的对角线和
这题因为全由自己写,所以各种写法都有。在下面先写我的最基础简单的方法吧。
CODE:
[Copy to clipboard]
#include <stdio.h>;
#define n 5
main()
{
int a[n][n];
int row, col;
int sum=0;
/* 输入略 */
for(row=col=0;row<n;row++,col++)
sum+=a[row][col];
for(row=0,col=n-1;row<n;row++,col--)
sum+=a[row][col];
if ( n%2 !=0)
sum-= a[n/2][n/2];
printf("%d",max);
}
这是最基本的方法了,两个循环跟着判断是否偶数来减去中间重复出现的一个数,这样就求得结果了
下面我写一个我同学编的还比较简单,而且方法独到的(反正所有人都没有想过这种方法,除了他)。这里主要写一写他的方法。
CODE:
[Copy to clipboard]
int sum=0,j;
for ( j=0; j<n; j++ )
sum+=a[j][j]+a[j][n-1-j];
if ( n%2 !=0 )
sum-=a[n/2][n/2];
够简单吧,一次循环就可以了,他的思路是这样的,比方有一个如下的矩阵每次都两个两个刚好相对立,所以可以一次就扫描完了。
好了,我写的有些累了,因为今天没有什么精神,最后老师还补充了另一个更简单的,方法其实就是一种只是运用了条件运算符
sum+=a[j][j]+( (j == (n-1-j) ? 0: a[j][n-1-j];
C语言真的想有多简洁有多简洁.
第四天
真的不知道为什么,我所有WORD的日期都变了,可是是WORD的宏病毒吧。但是为什么感染上的呢?这下可真奇怪了,我没有用过宏啊。算了,现在没有时间去理会它了,我要抓紧时间写完这篇补习日记。
今天的课程里终于到了重点了,就是算法,因为才刚开始,先从容易的排序算法开始说,抄了一道题目让我们做,如下:
已有一个已排序的数组,今输入一个数,要求按原来的排序规律将它插入数组中。
看到了这个题目我觉得自己比较有把握,很快的就写了出来,可是谁知道我的程序有一个至命的地方,刚给老师看的时候还得意洋洋,可是看完指出我的错来时真的不好受,既然都错了,就把我所做的那个答案写下来吧,也好让大家比较比较。
CODE:
[Copy to clipboard]
#define n 8
main()
{
int a[n];
int i,j,t,s;
for(i=1;i<=7;i++)
a[i-1]=i*10;
for ( i=0;i < 7;i--)
if ( a[ i ] < a[ i+1 ] )
{ s=a[ i ] ; a[ i ] = a[ i+1] ; a[ i+1] = s; }
for(i=0;i<7;i++)
printf("%d,a[ i ]);
}
看上去真的对的,没有错误,可能如果不细心都走眼的了。老师就是有这种本领可以看出来,让我慢慢道来我的错误吧,其实就是错在那一个最后没有赋值的元素,因为没有初始传值,随机生成的数可能很大,也可能很少,不过如果刚好小于插入的数话,那么就不再是正确的排序了。好了,说了我的错让我们看一个正确的程序吧
CODE:
[Copy to clipboard]
#define N 8
main()
{
int a[N]={20,30,40,50,60,70,80};
int n,i;
for(i=N-1;i>;=0;i--)
{
if(n<a[i]) a[i+1]=a[i];
else break;
}
a[i+1]=n;
}
这里就是一个比较好的排序算法了,在讲这些排序的时候老师画了一个图,如第四天图一这个图可以方便的表示出当时的排序情况,排起序来更清晰了。不过更重要的一点就是不排让人只单独看源程序那样头晕,根本不知道这是怎么一回事。因为我也是,自己编这个程序的时候跟着看完,看得模?
?
所以我推荐大家也学一学这种方法。
说到排序,我们又教我们一种新的排序方法,就是冒泡排序法了。记得以前我学QB里也学过,不过今天听着老师说,自己动着手画图来看,真的变得清晰多了。说冒泡排序法其实也可以叫左下沉排序法,因为是按程序的两个循环来决定,如果是按从底到顶当然就是冒泡啦,相反从顶到底就是下沉了。显下两个程序:
CODE:
[Copy to clipboard]
int n=6,i,j;
for ( i=n-1; i >; 0; i--)
for(j=0; j < i; j++)
if(a[j]>;a[j+1] { 交换 };
以上的是冒泡法
CODE:
[Copy to clipboard]
int n=6,i,j;
for ( i=0; i < n; i++)
for(j=n-1; j >; i; j--)
if(a[j]<a[j-1] { 交换 };
这就是下沉了。
我们今天基本上全都在练习这个排序了,快到放学了,可是老师还是把握好时间,真的一点都不浪费啊,而且还拖了半个钟头堂。唉~,有时候我觉得他人好,好时候真的不好。可是怎么说呢,他至终都是我们的老师。那么他拖了我们半个钟就是为了说完C语言里条件语句,不过说真的还是学到了一些东西。
C语言里条件语句也有好几种形式,用条件运算符 ? : ,基本的if语句,还有就是switch语句,至于最灵活都是答件运算符 ? : , 而且还是C语言里唯一的三目运算符了。为什么这么灵活,因为他的参数是表达式,C语言最灵活也就是表达式了,那么它能不灵活吗！这里给出一个源程序:
CODE:
[Copy to clipboard]
int a=5,b=10,c=8;
if(a>;b)
if(a>;c)printf("a");
else if(b>;c)printf("b");
else printf("c");
这么一条源程序是否让你看得不舒服呢,这就是C语言的另一个特点啊,你知道这条程序的答案吗?不过其实也不难,程序也很短嘛,就让我说出答案好了,答案不就是输出b嘛,道理很简单一看就出了,谁?谁?谁在这里搞乱,答案会是输出b 吗,笨！所以写你功夫还不到家嘛,下面让整理一下程序
CODE:
[Copy to clipboard]
int a=5,b=10,c=8;
if(a>;b)
if(a>;c)
printf("a");
else
if(b>;c)printf("b");
else printf("c");
这样看清楚了吗?答案就是什么都没有,因为一开始第一个if语句就不成立了,那里有答案出呢！这里也看出一个情况,所以我们要陪养好代码的格式,如果有良好的编码风格就有好的程序。还有我今日又明白了一样,想看看下面的if语句:
if if
else else if
if else if
else else if
if
else
我原还以为这两个是不同的呢,在QB里的印象是两个不if语句呢。可是今天就给我弄明白了,大家也应该知道吧,可能就是我笨了。
在C语言里swtich也和别的高级语言不同,你们有发现吗?现在看看第四天图二吧在这个图里清楚的说明了这个语句与其的不同之处,而且条件是用常量的,所以老师说给我们听他自己也不怎么喜欢用这个swtich语句。如果用懂了这个条件运算符? : 还真的挺方便的,这个也是可以无限嵌套的,这里不多说了,让自己慢慢体会研究。
第五天
今天是离散学礼的最后一天了,我的成绩嘛,当然也不会高得去那里了,还很有可能第一呢(倒数啊)。都怪自己不好,不过也不能全怪。因为学校本来的电脑课程也不少了,可就是全部都在教图形方面呢,什么PS 、CW都要我们编程班的去学,真有点不爽。
好了,也不说太多自己学校的羞事了。那么下面我们就开始来学习今天的知识吧,很多朋友都是我整天在打字,可我自己觉得打一篇这些也不是浪费很多时间,而且收益的更多(早上听完,晚上复习)。故语有云"温故知新",我觉得这句特别有道理的,因为通常我在看书里也看不到老师在课堂里向我们提出的问题?昧撕昧?我还是赶紧说说今天的学习吧。昨天老师布置的我们一道答,我昨天都给忙了做,而是今天突然想起才冲冲的赶着做,是这样的一道题:
给一个不多于5位的正整数,要求:1,这个数有几位2,打印每一位的数,3逆序打印,
比如321 输出 123。
好在这答也不难,用了一会儿时间就做完了。
CODE:
[Copy to clipboard]
main()
{
int n; int num;
int i=0,a[5];
printf("请输入不大于5位的正整数");
scanf("%d",&num);
do
{
do[i] =num % 10;
num /=10;
i++;
}while(num!=0);
n=i;
printf("LEN%d",n);
for(i=n-1;i>;=0;i--)
printf("%d",a[ i ]);
for(i=0;i<n;i++)
printf("%d",a[ i ]);
}
做这题时我也用到了昨天老师教的画图方法作了验算,不过还是要上机求正否,这样一来可以锻练一下编写程序。我们大家都各有各的方法,有些是很长(用Switch语句呢),我也不知道他怎么想的了,不过不同人有不同思想是正确的,编程这玩意没有完全统一的答案的。那么你们想想你们有什么方法做呢,好吧,就给五分钟你们做做吧。……好了,时间到了,下面我再说说我的另一位同学做的方法吧,他是用字符数组的,也很简单方便可以实现。你们做的怎么了?如果有好的方法也可以大家交流啊,因为我写这些都是为了大家(也为了自己)。
大家应该都看得明白我的程序吧,因为我的思想就是这么单纯。
老师说完了昨天的作业后就开始说今天要讲的课程了。今天的主题是循环语句,其实C语言里也只是这么几条循环语句吗?相比QB来说真的可以算是见大场面了,因为QB里单是循环语句已经有七八种之种,至于有那些我也记不太清了。那么下面讲讲C语言的好了。C语言的循环语句一共有三种,先说说比较简单的前两种吧！
While ( 条件 ) { 语句；} 和 do { 语句；}
while ( 条件 )；
这里我想重复一下老师给我们说的一个笑话,就是有一个小女孩问妈妈拿糖的小故事。有一个很乖的小女孩总是先问妈妈可不可以吃糖,如果得么批准了就拿一粒来吃?墒怯幸淮嗡?就很拿着一粒吃着了,跟着才问妈妈我可不可吃糖啊,如果可以当然就是继续可以吃了,否则就不准了,不过已经有一粒在口了。这个刚好可以比喻这两个循环语句,第一个循环语句是先当条件真才可以继续下去,否则退出。而第二个呢,就是直运行里面的程序先,跟着才到条件里看是否可以再继续运行多一次?昧苏饬礁霰冉霞虻サ木涂纯碈语言里特有的一个for循环语句,这个循环比较特别,如第五天图一
它的结构也比较特别,而且里面三个表达式是非常灵活的。这里随便给出一个程序让大家看看:
CODE:
[Copy to clipboard]
int i=0;
for(; if(i++>;10) break;
printf("%d",i);
这说这里i是多少呢?这里就关系到这个运算符了++递增运算符,可以有两种方式,一种是i++就像上面的那样,至于另一种就是++i,这里的答案是前者等于12,而后者就等于11。这里全是因为++递增的两个方式所至,那么我们要好好掌握一下这个,你自己试试动手上机编一下。另一个程序好让看出这个递增运算符的:
CODE:
[Copy to clipboard]
int i=0;
if (i++) printf("a"; /*
如果这里为真的就输出a */
else printf("b"; /*否则就是输出b */
自己试试看,是不是很明显可以知道这个递增符的原理呢,这里说一下吧,其实i++这个呢就是先那i比较后才运算++的,所以很自然就是0那么结果当然就是输出b了,则那个++i就是先把i加1才比较,那么真就输出a了,好了,那么++递增和- -递减都是同一性质的。不过要注意的是这两个递增递减运算符都是要变量才行的,不可以和常量运算。
好了,说完了循环语句当然就是要懂得去运用在编程里了啊！所以老师马上出了一道题让我们想想,不过相信有些人都是研究过的了,就是"魔方阵",可是老师说虽然这个魔方阵虽然有直接的算法可以运算出来,但是要让我们思考用循环做这题,利用计算机的能力来完成,但看到要排列这么多的数,循环也更不要说要很多了,所以我根本没法想下去了(开始头晕起来)。最后还是没有一个能做出,只好听老师说了,不过老师也没有完全说完,只是给了我们一个结构,如第五天图二让我们自己有兴趣就去完成它吧,我对数学这东西最没有FEEL
的了。
好了,接着继续第二题,也是一个排列组合的问题,你们手头上应该都有老潭的
《C程序语言第二版》了,那么请大家翻翻书到第121页,6.15题,这题就是排列组合的题目了。这其实也是有一个规律可以找到的,不过不是我们找到的而是老师给我们说,今天这堂课真的有太多的难题了,至少对于我来说。下面我也没有什么好插嘴的了,只好示出老师的方法吧,如第五天图三
程序也在下。
CODE:
[Copy to clipboard]
char xyz[]=['X','Y',"Z'};
int i,j,k;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(j==i0 continue;
for(k=0;k<3;k++)
if(k==i || k==j) continue;
printf("A-%c\n",xyz[i]);
prihtf("B-%c\n",xyz[j]);
prihtf("C-%c\n",xyz[k]);
让大家自己看明白了?昧?今天我的头也特别的晕,肩膀也特别的酸。不过我还是要努力的！
第六天 2002年08月18日
今天的整个课程只有这么的一道题,但是学到的东西确很多。下面给出这条题目:
字符数字转为整数数值(字符可以任意:比如"342A"遇到其它否数字取前数。
我所写的程序如下,自认为写得不错:
CODE:
[Copy to clipboard]
#define N 10;
int catio(const char *str) /*const
的作用是常数,所以这里的地址不会返回到实参里*/
{
int num[N];
int i=0;j=1,n=0;
for(;*str++;i++)
{
if(*str<48 || *str>;57)
break; /*判断是否数字数值*/
num[i]=*str-48;
}
for(i-=1;i>;=0;i--)
{
n+=num[i]*j;
j*=10;
}
return n;
}
你们说是不是比较简单呢?现在看不出等看完以下的另一个程序先断定吧。如下:
CODE:
[Copy to clipboard]
long catio(char c[]);
{
int n,d;
char *q,*p;
long e=1,s=0;
for(q=p=c,n=0;*p!='\0' && *p>;='0' && *p<='9';p++,n++,e*=10);
while(n>;0)
{
d=*q++;
switch(d)
{
case 48: d=0;break; /*太长了,略*/
:
:
case 57: d=9;break;
}
s+=d*(e/=10);
n--;
}
return (s);
}
现在比较来看看,不过虽然这条程序是比我那个复杂,但是也有他的思路和可取之处。像在那个for循环了,一条命令带过很方便也很简洁。其实我们可以继续改造这个程序,我们跟着老师的思路一步一步的把它进化,现在看看如下:
CODE:
[Copy to clipboard]
long catio(char c[]);
{
int n,d;
char *q,*p;
long e=1,s=0;
for(q=p=c,n=0;*p && *p>;='0' && *p<='9';p++,n++,e*=10);
while(n>;0)
{
d=*q++-'0';
s+=d*(e/=10);
n--;
}
return (s);
这样是不是更简化了,那么还可以再简化下去吗?前面的我们是可以做出来啊,当是老师说还可以更简单,我们都只好怀着期待的心情去听了。他一步一步的说出来,第一就是在s+d*(e/10)这里可以变为另一种形式,s=s*10+d,如果按照这样又可以去掉一个多余的变量了,变量e就没有了。接下来的更不可意议了,我不知道怎么说,看看程序先吧。
CODE:
[Copy to clipboard]
long catio(char *c);
{
long s=0;
for(;*p && *c>;='0' && *c<='9';s=s*10+*c++-'0');
return (s);
}
大家看到了吗?原来这么长的程序可以一再简化到这个地步,这就是C语言的灵活了(我好像已经说了好几遍了,真的没有办法,不得不赞叹)。
今天就是这么一题,可真的有意外惊喜呢！好了,现在不写了,还有十道练习题等着我去做呢,大家也要努力喔！
第七天 2002年08月18日
今天终于都讲到C语言比较后的范围了,"函数"说是C语言的一切真的没错(可能有吧,我不知道)?。很多书上都说着函数是C语言根本,就是说函数是构成C语言的?看以下这个程序:
CODE:
[Copy to clipboard]
main()
{
printf("Hello World";
}
main()就是C语言里最特殊的一个函数,是构成整个程序的关键。在C编译器里首先就是要找出这个主函数才开始执行编译,好了,说了一些书上原来的东西。现在我们就来看看C语言里的函数究竟是怎么的,如果我们从基础的说起也没有什么意思。那么我们就从函数的另一个特点说起,"递归函数"相信很多人都知道这个吧,看过老潭的教程应该都知道他经典的第一个递归程序吧:
CODE:
[Copy to clipboard]
int abc(int n)
{
int s;
if(n >;1) s= n*abc(n-1);
else s=1;
return (s);
}
从这个源程序很容易就看出有一个同自己名字的函数在里面,所以以后我们看到一个函数里面调用自己就是递归函数了。而且我们看一个递归函数就主要就是看它是否一个返回的条件,就好像一条又黑又深的山洞,我们前去探险如果往到底就一定要回头,就算是更深的也要返回啊！所以我们判定一个递归函数是否成立也常常是看它的返回条件。至于上面的那个源程序我也不想多说了,应该大家也看得明白。
这里就看看另一个利用递归函数做的题目吧,就是诺汉塔(老潭的书上也是有)。
CODE:
[Copy to clipboard]
#include <stdio.h>;
void move(char x,char y)
{
printf("%c-->;%c\n",x,y);
}
void hanoi (int n,char one ,char two,char three)
{
if(n==1) move (one ,three);
else
{
hanoi (n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}
main()
{
int m;
printf("input the number of diskes:";
scanf("%d",&m);
printf("the step to moving %3d diskes:\n",m);
hanoi(m,'A','B','C');
}
/*运行情况如下:
input the number of diskes:3 回车
the step to moving 3 diskes:
A-->;C
A-->;B
C-->;B
A-->;C
B-->;A
B-->;C
A-->;C
书上说hanoi(n-1,one,three,two);是把"one"上的n-1个往"two"上移,接着move(one,three);然后是hanoi(n-1,two,one,three)即把"two"上的n-1个往"three"上移；
|h(2,1,3,2)|h(1,1,2,3)=>;move(1,3) <-----1------
| | move(1,2) <-----2------
| |h(1,3,1,2)=>;move(3,2) <-----3------
|move(1,3) <-----4------
| h(3,1,2,3) | |h(1,2,3,1)=>;move(2,1) <-----5------
| h(2,2,1,3)|move(2,3) <-----6-------
| |h(1,1,2,3)=>;move(1,3) <-----7------
|
*/
注意以上是网上一个网友写的,并不是我写的。诺汉塔最不同的就是它多次调用自己,所以看起来也比较复杂一点。当时我在看这条程序的时候也是看了老半天也看不懂,最好我在网上看到一位朋友说他自己是真的拿了一些碟子自己试着移来看看,后来我也自己试着看,效果真的挺好(我当然没有笨那这么大的碟子啦,用我的光盘写上大、中、小),大家不访也试试看。加上看了上面这个图我也比较清晰了,我要感谢那位网友才行,你们说是吗?这个程序一定要自己慢慢去理解它,祝大家早日理解它吧。递归函数部份我因为不太懂也不能说些什么了,现在来看看函数的另一个内容吧,就是函数的参数调用。我这里先给出一个程序先吧:
CODE:
[Copy to clipboard]
int abc(int a,int b)
{
a=a=b; return( a+b );
}
main()
{
int xy[]={3,5};
int s;
s=abc(xy[0],xy[1]);
}
这里的将xy[0]和xy[1]分别传入形参里,这里要说的一点就是和其它高级语言不同的,C语言的函数调用都是单向传递的。限实参传了给形参之后并不会返回到传进来的实参的,所以我们务必记住这点。又如下面一题:
CODE:
[Copy to clipboard]
int abc(int a[])
{
int i,j;
/* 排序 */
}
main()
{
int x[5]={3,5,1,2,4}
abc(x);
/* 输出 */
}
这条源程序可为什么会改变实参的数值呢?老潭的书里说的很明白,说是因为这是地址传递,但是我们老师不太认同这点,他说这个也应该是值传递,只不过这个值是比较特殊的一个值,是地址,所以传到形参时可以通过调用这个地址指向的元素而已。如果按老潭的这样说以下这条程序都叫地址传递啦?
CODE:
[Copy to clipboard]
int abc(int *p)
{
*p=10;
}
main()
{
int a=20,*w;
w=&
abc(w); /*abc(&a)*/
printf("%d",a);
}
指针P也只是一个值而已,这个值是地址。如果说这是地址传递,那不是应该w的地址传给形参吗?剩下来的大家自己想想吧。(这里也不能够说谁对谁错)
接下来说说变量的存储类别,其实这个知识点也挺容易理解的,不过可能给C语言太多的这样的关系弄的糊涂了。C语言里有变量的类型,变量的存储类别,变量的全局性还是局部性,是静态的还是动态的呢。一切都是C语言变量的东西,我们这回也该好好的结束了它。(我们大家一齐看书吧)
很对不起大家,因为今天我的眼有点问题(可能看电脑看太久了)。所以不要再继续和大家进一步讲讲存储类别,这里有一条源程序大家看看吧,我不行了,我要好好休息一下才行了。
CODE:
[Copy to clipboard]
int abc(int a)
{
int i,j;
scanf("%d%d",&i,&j);
if(i>;j)
{
int k=1,i=2,j=3;
pirntf("%d\n",i*3);
printf("%d\n",j*10);
}
printf("%d",k);
}
第八天 2002年08月18日今天回到学佼也没有讲课,因为老师忙着一些其它事,听说好像是多媒体比赛的吧,要今天上交了。那我们只好回到课室里自己看书了,不过在这段时间里我们都没有看什么书,只是大家聊了起来。我也插了嘴吹了几句,可是很快就没有心情了,唉！只好睡一睡吧。当我休息了一会发现老师都已经回来了,而且说让我们今天上机房。今天是第一次上机房,不过如果不是什么事我也不愿上机房,因为我觉得听老师讲课还好。我们上到机房,老师给了一条程序我们,喔！这不是前两天说要搞的那个诺汉塔吗！而且是结合了图形表示的。
我们都兴奋起来了,开始研究着这条程序。我开始执行这个诺塔了,他给的参数不是很多,只是十个盘子而已,你知道我按了多长时间吗?我一直按着来看也看了快一个5分钟才看完啊,这个问题果然是复杂.看着这些图画演示让我更加清晰的明白了诺汉塔的原理,这里我不敢自私,我把源程序也COPY回家了,以下就是了:
CODE:
[Copy to clipboard]
#include <conio.h>;
#include <string.h>;
char dd[10][20],space[20];
int a[11],b[11],c[11];
init()
{
int i,j;
for(i=0;i<20-1;i++) space[i]=' ';
space[i]='\0';
for(i=0;i<10;i++)
{ for(j=0;j<20-1;j++)dd[i][j]=' ';
dd[i][j]='\0';
for(j=9-i;j<=9+i;j++)dd[i][j]='a'+i;
}
for(i=0;i<10;i++) a[i]=i,b[i]=-1,c[i]=-1;
a[10]=2,b[10]=25,c[10]=50;
for(i=0;i<10;i++)
{
gotoxy(a[10],10+i);
cprintf("%s",dd[i]);
}
}
move(int *s,int *d)
{ int i,j;
for(i=0;s[i]==-1&&i<10;i++);
gotoxy(s[10],10+i);
cprintf("%s",space);
for(j=0;d[j]==-1&&j<10;j++);
j--;
gotoxy(d[10],10+j);
cprintf("%s",dd[s[i]]);
d[j]=s[i];s[i]=-1;
getche();
}
void hanoi(int n,int *s,int *w,int *d)
{ int i;
if(n==1)move(s,d);
else
{
hanoi(n-1,s,d,w);
move(s,d);
hanoi(n-1,w,s,d);
}
}
main()
{
clrscr();
init();
getche();
hanoi(10,a,b,c);
getche();
}
最后除了看了这条程序,老师还给我们试着用TC调试程序了。你知道我以前调试程序是怎样的吗?我就是直接ALT+F9看看有没有出错,如果有就修改,没有则成功了. 可是真天我真正认识到TC里调试程序的真正方法,其实TC里有一大推的调试工具,这是我以前一直没有用过的,只知道有一个就是一步一步执行,跟着其它就一无所知了。其实TC里可以把一些变量的值跟踪显示出来,这是调试程序的重要手段,以前不知道这个功能都是用笔写在纸上的,现在可以很方便准确的看出来了。下面的几张图片是我自己切出来的,大家看看就知道知道了(可能大家原来就知道,是我菜摆了)。今天的课程也算学到东西了吧,我该回去好好利用这个功能来调试程序了。
第九天
今天终于到了C语言的核心部份了,指针一直都是被学习C语言公认为最难的一个大重点了,如果假如我们不学C语言的指针的话,那我们可以说根本没有学过C语言了。不过话说回来,在我刚开始接触C的时候前面的基本语法倒是很快的过了,可是学到指针结合到数组里就傻了眼,因为我根本看不明为么可以有这么多的数组调用方式(结合指针)。其实我下面的三言两语也很难说的明白指针这家伙的,请大家在上机里多多调试看看,待增加了经验后再回头看看指针这章,相信也能全摸透了。因为我也是这样过来的,我还特别看了很多运用指针方面的源程序。
现在我们就从相对于二维数组来说比较简单的一维数组开始吧,先看看如何定义一个指向一维数组的指针吧。
int a[5]={1,2,3,4,5};
int *p;
p=a; /*这里a因为是数组的变量名,它的值是这个数组的首地址*/
跟着我们可以通过指针来改变数组的值
p++;
*p=6; /*那么数组的第二个元素就等于6了*/
这里的意思就是让指针向下移一个,这样一来指向了数组的第二个元素。我们再细一点看看它的地址,通过这个指针,即当前指向的元素的地址。那么地址又是怎么运行的呢?p++这个命令就是让地址往下移的了,如果按照数组a 的类型来看,数组a是一个整数的类型,占的空间是两字节,而p++就只加1,顶多都是到第一个元素的后一半里,哪里可以指到第二个元素呢?其实这里就关系到定义指针时的类型,我们这里定义的也是整型类型,"对啊,这里定义整型是对的啊,因为它要指向整形数据嘛,那么当然就是一定要定义这种类型啦",其实这并不是真正的答案,而且也不必一定要定义为跟指向的数据一样类型,我们完全可以定义指针的类型为其它的。就比如定义为float吧,不过这里执行p++就直接跳过了一个数组元素,那么现在我们来看看究竟是怎么一回事。其实我们定义的指针类型就是用来结合指针,进行一定规则的运算方式。这里很明显可以看出如果是定义int 类型的就可以到第二个元素,说
明了p++不是简单的地址加一,而是先结合这个是什么类型才进行运算的,加一次就等于地址移了2位了。float道理一样移4位,所以得到的结合是移到第三个元素。再往下看看:
a=a+1;
这里我们进行地址移位赋值,不过这条命令是错误的,C语言里数组名是一个地址常量,所以不以试图改变它的值。
接下来简单地说一说二维数组,因为我们今天的任务就是首先搞清一维数组先。现在我们先来定义一个二维数组
int a[2][4];
这里我不再重复书里讲的东西,我讲一下老师给我们的那种思想。我们这样来看一个二维数组,就是一维数组的元素又为是一维数组,这样嵌套。当然其它的多维数维都是这样一直嵌套下去的了。我们先看看这个图如图第九天图一这样就很容易说明了为什么a[0] 和 &a[0]为什么是一样都是代表着地址,其实都只是首地址,这里从文字很难可以说通,但是从意义上就可以理解。我们把二维数组的整列都充当为一个一维数组,不把它看作二维,这样得出如下:
a[1][1];
充当一维 M为名
M[1]; /*调用第二个元素*/
我们试着把所有都这样看作,定义这样的一个一维数组
int a0[4],a1[4],a2[4];
这样一来,我们就知道a0、a1、a2都是首地址了。
好了,可能也越说越模糊了,如果看不明白还是按照自己原来的思想去考虑数组吧,这是因为每个人都有自己的的想法和理解。
第十天 2002年08月18日
今天接着上天的二维数组,我们看看指向二维数组的指针是怎么的。在讲之前我想再重复一次,如果你自己理解好二维数组的就按你以往的去理解吧。不过多想想几种方法也是一件好事,那么下面就来讲讲了。
现在来看看昨天的那个二维数组图,第九天图一。我们定义一个指向二维数数的指针
int a[3][4];
int *p;
p=a;
其实这也指向一维数组的指针完全没有分别,二维数组因为是行优先的,一行下来就是列顺序了,我们可以这样来用指针指向列,如下:
p++;
我们这里就是指向了第0行的第1列了,那么我们怎么可以到第下一行呢,其实定义数组时内存就给数组分配好一连串的连续空间,我们直接可以将指针继续往下移,当移到了0行最后一列时,加移的话就到了第1行了。其实C语言里还有一种更方面的指向方法,看如下:
int (*p)[4] /*这里是定义一个数指针,而这个指针是指向有数组四个元素的指针*/
我们看看这种定义的方式,*p为什么一定要括号括住呢,因为[]这个运算符比*优先,如果不加括号的话就变成了定义另一个指针值,至于是什么指针在最面就会讲到了,现在先来看看这种指针。
p=a;
p++; 这样会得到什么的结果呢?就是直接往下移一行了,这也是和前天说过的那个道理一样,是按照定义的类型结合来到运算的。我们知道了如何可以移行,那么该怎么移列呢?这个问题又更复杂一点了,试着把指针移到第1行第2列看看。我们先来看看这个表达式代表什么吧,a+1 这就是第一行的首地址吧,同理p+1也是指向第一行的首地址。至于列呢?先想想一维数组是怎么移到列的,就是首地址加上列序吧！那么我们就可以先表达出一维数组的首地址先,*(p+1)+2,看,这样是不是指向了第一行第二列了呢。我们不可以简单的理解(p+1)为行,从另一种意义上可以看成是列的首地址了(这里实在太难理解了,明还是有一点明,不过我还想用回自己一直对指针的理解好了,千万不要综合起来理解喔,这样就太错特错了)。
好了说回了二维数组成的现在来看看还有其它的什么指针,字符指针是比较简单的,不过也有它的一些特别之处。我们来看看以下的一些程序:
char *p;
p="ABC"; /*这里说说,既然是字符串就是一定有结束符的,这是和字符数组不同的*/
这样的赋值是可以的,这里是将字符串ABC的首地址赋给指针p,下现再看看另一个程序:
char a[4];
a="ABC";
这里有错吗?对于C语言来说是错了的了,因为字符数组a是一个常量,不能给赋值。其它的高级语言就可以直接赋值给它就回事了,那么我们想把ABC赋给字符数组该怎么呢,这里有几种方法,一种就是一个一个字符赋值,一种就是利用指针,不过这里还是用回C语言函数库里的复制字符串函数完成strcpy();大家应该都对这个函数不默生吧,那好,现在就给五分钟做做练习,编制一个类于strcpy()的函数。…………时间真的过得快,我把我做的写出来吧。
mycpy(char *s1,char *s2)
{ for(;*s1++=*s2++; }
好了,就这么短短二行就完成了复制功能,这只有C语言才能做到的。
现在再来看看以下两个程序吧
char *p,*q; char *p,*q,*r;
p="ABC"; r="ABC";
q="ABC"; p=r;
*q='D'; q=r;
printf("%s",%s",p,q); *q='D';
printf("%s,%s",p,q);
这里的答案是什么呢?自己先想想吧。
好了,应该都想完了吧,现在就给出正确的答案,第一条程序是输出ABC,DBC,而第二条程序就是输出DBC,DBC。这里为什么呢?其实是因为第一个程序都是指向了同一个地址,那当然就是值一样啦。
现在就剩下函数指针了,其实我们平常也不怎么多人,但是老师还是给我们讲了一下,也提出了一个特别的地方,是今天我们才发现的,程序如下:
CODE:
[Copy to clipboard]
int b=0;
int a[2]={10,20};
int *ab(int *p)
{
p++;
return (p);
}
main()
{
b=*ab(a);
/*
这里我们试着将调用的函数返回的地址再加*号,看看可不可以指到那个值,
至于结果怎么样,我们也没有试过,我在写这篇日记时也没有上过机试,大家有兴趣也试试吧,这个问题我们是怎么引出来的呢,其实我们一开始定义了一个指向函数的指针,就比如(*cd)()吧,我们提出了如果没有了括号会怎么样,因为本来(*cd)()就是指向一个返回指针值的函数,那么我们为了试验所以另编一个返回地址的函数来试试
*/
printf("%d",b);
}
好了,今天就将指针讲完了,不过指针的运用就还有很多在后面呢,就我知道的就有结构体和共用体还可以用到指针,跟着就是其它的一个综合运用链表、堆栈、队列等等的。我想我就是这方面还一点经验都没有吧,之前看了一下数据结构也没有太大的兴趣看下去了,因为我看到一大堆的指针都已经头晕了。不过近几天拿回来看看又好像明了些什么似的,反正就觉得不太头晕了吧。
第十一天 2002年08月18日
今天讲到结构体,在讲之前先把前天布置的几道针指的练习题先讲了。那些题目都是老潭书里的指针那章,大家自己慢慢做做喔,用来掌握指针很重要喔,学编程就是要多实践。今天我上网里看到了一篇很好的文章,我帖下来:
发信人: ycs830 (老山羊), 信区: C
标 题: Re: 如果快速学会C语言
学会C语言很容易,它没几个语句,没几个函数。但用是另一回事。就象华山剑法难学,令狐师兄学了若干年,但还是谁也打不赢。独孤求败只有三 招,令狐师兄却熬了若干小时就学会,但他先看了各派剑法,融会贯通需要和高手来回打架。
学C是一个过程,我现在看C和十年前观念很不一样。说到底,C只是一个工具,问题是你要干什么,怎么干。C玩好了就象独孤九剑学好了,你可以俯视其它剑法。但岳不群学独孤九剑就不见得有令狐冲的效果。
学数学对逻辑思维能力是个锻炼。我的数学知识大部分还给了老师,但逻辑思维能力却对编程极有用。数分、高代、空解作为数学系的基础课,确实对我很有用。C语言是死的,算法是活的,就象独孤九剑本无招--在融天下剑法之后。
大家觉得怎么样?自己慢慢思考吧。
好了,现在该讲讲今天的课题了,结构体。我们先来了解一下什么叫结构体,其实结构体就像数据库里的记录,结构体里面的就相当于一条记录里的各个属性,我们在描述一样东西通常都是集在一起的一个整体,就好比像一个学生吧,学生有他相关的属性,比如姓名、年龄、性别、班级等等。我们编程里虽然可以定义多个变量来分别代表着这些属性,令可这样一个一个分开来何必不将他们集中在一个整体里呢,所以C语言里就考虑到这个有了结构体。我们看看如何定义一个结构体,如下:
struct student
{
char name[10];
char sex;
int age;
:
:
}; /*注意喔,这个分号是一定要的喔*/
这里定义的是一个结构体student,但这绝对不是定义了一个可以调用的变量,这只是声明好有这么一个结构,我们要学定义一个结构的变量的话,就像定义其实类型一样:
int a,b;
和
struct student a,b;
都是同一个道理,都只是定义一个变量,类型就是看前面的了。一样可以定义其它的类型,比如struct student *p;这也是正确的(结构体数组也是有的喔)。这种指针类型可是以后要讲到的链表里很重要的喔,那么先来看看这种结构体指针先吧。我们同样可以用指针的方法指向这个结构体的首地址:
a.sex='m';这是最调用结构体里的元素运算符 .
struct student *p;
(*p). sex='m';这里一样也是这样来表示,不过结构体有另一种很好的表示方式,用到了另一个运符号->;。p->;sex='m'；我们来这样理解这个表达式,p是地址,->;这个是指向这个结构体里的,p->;sex就是指向这个结构体里的元素了。
时间过得很快,没有讲到多少就快放学了?昧?我也不多说了,今天就这样吧。
第十二天 2002年08月18日
今天老师和我们讲了链表,和老潭书里一样大家都讲得很好,让人很容易就可以听进。所以这里我也不再重复了,大家自己慢慢看一下老潭书里的链表那节,绝对不会觉得难的,而且还举了一些生动的例子来到说明。下面我就从网上找来一些关于指针的文章,这个人绝对是高手,大家这回要好好研究一下咯。相信看完第一遍之后一定对指针有个大概,第二遍已经有印象在脑海里不停的回旋了,第三遍可以大功告成了。
为初学者服务。这是我的帖子的宗旨。我也是个初学者(强调了无数遍了),我以我的理解把初学者觉得难懂的东西用浅显的语言写出来。由于小学时语文没学好,所以竭尽全力也未必能达到这个目的。尽力而为吧。
指针是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];
如果看不懂后几个例子的话,请参阅我前段时间贴出的文章<<如何理解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位长。
指针所指向的内存区就是从指针的值所代表的那个内存地址开始,长度为sizeof(指针所指向的类型)的一片内存区。以后,我们说一个指针的值是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所指向的类型也相同。ptrnew的值将比ptrold的值减少了n乘sizeof(ptrold所指向的类型)个字节,就是说,ptrnew所指向的内存区将比ptrold所指向的内存区向低地址方向移动了n乘sizeof(ptrold所指向的类型)个字节。
第三章。运算符&和*
这里&是取地址运算符,*是...书上叫做"间接运算符"。
&a的运算结果是一个指针,指针的类型是a的类型加个*,指针所指向的类型是a的类型,指针所指向的地址嘛,那就是a的地址。
*p的运算结果就五花八门了。总之*p的结果是p所指向的东西,这个东西有这些特点:它的类型是p指向的类型,它所占用的地址是p所指向的地址。
例五:
int a=12;
int b;
int *p;
int **ptr;
p=&//&a的结果是一个指针,类型是int*,指向的类型是int,指向的地址是a的地址。
*p=24;//*p的结果,在这里它的类型是int,它所占用的地址是p所指向的地址,显然,*p就是变量a。
ptr=&//&p的结果是个指针,该指针的类型是p的类型加个*,在这里是int**。该指针所指向的类型是p的类型,这里是int*。该指针所指向的地址就是指针p自己的地址。
*ptr=&//*ptr是个指针,&b的结果也是个指针,且这两个指针的类型和所指向的类型是一样的,所以用&b来给*ptr赋值就是毫无问题的了。
**ptr=34;//*ptr的结果是ptr所指向的东西,在这里是一个指针,对这个指针再做一次*运算,结果就是一个int类型的变量。
第四章。指针表达式。
一个表达式的最后结果如果是一个指针,那么这个表达式就叫指针表达式。
下面是一些指针表达式的例子:
例六:
int a,b;
int array[10];
int *pa;
pa=&//&a是一个指针表达式。
int **ptr=&//&pa也是一个指针表达式。
*ptr=&//*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当然也有了自己的位置。
第五章。数组和指针的关系
如果对声明数组的语句不太明白的话,请参阅我前段时间贴出的文章<<如何理解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],但如果把array看做指针的话,它指向数组的第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扮演的是指针,故array+n的结果是一个指针,它的类型是TYPE*,它指向的类型是TYPE,它指向数组第n号单元。故sizeof(array+n)测出的是指针类型的大小。
例十:
int array[10];
int (*ptr)[10];
ptr=&
上例中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的指针。它的类型是MyStruct*,它指向的类型是MyStruct。
int *pstr=(int*)&//声明了一个指向结构对象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上调式过上述代码,但是要知道,这样使用pstr来访问结构成员是不正规的,为了说明为什么不正规,让我们看看怎样通过指针来访问数组的各个单元:
例十二:
int array[3]={35,56,37};
int *pa=array;
通过指针pa访问数组array的三个单元的方法是:
*pa;//访问了第0号单元
*(pa+1);//访问了第1号单元
*(pa+2);//访问了第2号单元
从格式上看倒是与通过指针访问结构成员的不正规方法的格式一样。
所有的C/C++编译器在排列数组的单元时,总是把各个数组单元存放在连续的存储区里,单元和单元之间没有空隙。但在存放结构对象的各个成员时,在某种编译环境下,可能会需要字对齐或双字对齐或者是别的什么对齐,需要在相邻两个成员之间加若干"填充字节",这就导致各个成员之间可能会有若干个字节的空隙。
所以,在例十二中,即使*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=&
3。 int *p;
在上面的例子中,假如我们想让指针p指向实数f,应该怎么搞?是用下面的 语句吗?
p=&
不对。因为指针p的类型是int*,它指向的类型是int。表达式&f的结果是一个指针,指针的类型是float*,它指向的类型是float。两者不一致,直接赋值的方法是不行的。至少在我的MSVC++6.0上,对指针的赋值语句要求赋值号两边的类型一致,所指向的类型也一致,其它的编译器上我没试过,大家可以试试。为了实现我们的目的,需要进行"强制类型转换":
p=(int*)&
如果有一个指针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*)还不一样。这里的(TYPE*)的意思是把无符号整数a的值当作一个地址来看待。
上面强调了a的值必须代表一个合法的地址,否则的话,在你使用ptr的时候,就会出现非法操作错误。
想想能不能反过来,把指针指向的地址即指针的值当作一个整数取出来。完全可以。下面的例子演示了把一个指针的值当作一个整数取出来,然后再把这个整数当作一个地址赋给一个指针:
例十六:
int a=123,b;
int *ptr=&
char *str;
b=(int)ptr;//把指针ptr的值当作一个整数取出来。
str=(char*)b;//把这个整数的值当作一个地址赋给指针str。
好了,现在我们已经知道了,可以把指针的值当作一个整数取出来,也可以把一个整数值当作地址赋给一个指针。
第九章。指针的安全问题
看下面的例子:
例十七:
char s='a';
int *ptr;
ptr=(int*)&
*ptr=1298；
指针ptr是一个int*类型的指针,它指向的类型是int。它指向的地址就是s的首地址。在32位程序中,s占一个字节,int类型占四个字节。最后一条语句不但改变了s所占的一个字节,还把和s相临的高地址方向的三个字节也改变了。这三个字节是干什么的?只有编译程序知道,而写程序的人是不太可能知道的。也许这三个字节里存储了非常重要的数据,也许这三个字节里正好是程序的一条代码,而由于你对指针的马虎应用,这三个字节的值被改变了,这会造成崩溃性的错误。
让我们再来看一例:
例十八:
1。 char a;
2。 int *ptr=&
...
...
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所指向的存储区时是不安全的。至于为什么,读者结合例十七来想一想,应该会明白的。
第十三天 2002年08月18日
今天特别的兴奋,起床也起得特别的早。在走之前我把电脑开了,那当然是为了做服务器, 我不知道我开学后能不能够这样做,因为家里的一些因素。不过只要能为大家服务我已经很开心了,而且也一种强激的幸福感,这种幸福并不是一般的家庭幸福。我为坚持做下去的,我也 常常问一些网友关于这件事,他们都说只有你自己可以就行了,他们都支持我坚持做下去 吧,说远了离题了,我说说今天的补课吧。
今天的课程也令我吃了一惊,是讲数据结构里的树。为什么队列和堆栈都没有讲就直接讲树呢?会不会太快了一点,而且我们刚放完假有些人都没有集中精神到课堂来。不过我会相信老师的选择的,应该有他的理由。那么就来讲讲树的一些基本概念,大家都知道树是数据结构里的非线性结构之一,和之前说的链表是完全不同的,链表就只有前驱和后继结点,但树就不是了,他可以有很多的结点,称为分支结点,而且他的分支结点又可以有分支结点。因为树接触到的概念太多了,只好自己看一下书才行。树运用得很广范,像我们操作系统里文件管理就是了,多级的目录。二级目录就像树的子树,而且子树里可能还有很多的子树,越往下就越多级。
我们来试试定义一个树的结构,一般树都分得很随意,所有我们这里也随便画一个树来说一下.看图(第十三天图一)我们看到圆圈就代表一个结点,而且最顶的那个就是根结点,往下的就是子结点。子结点的上一个就是父结点,同一级的结点左右都是为兄弟结点。我们按照这样的结构定义一个,如下:
struct tree
{
int data;
struct tree *next; /*右兄弟结点*/
struct tree *pre; /*左兄弟结点*/
struct tree *up; /*父结点*/
struct tree *down; /*子结点*/
};
下面来看看如何建立一棵树。
CODE:
[Copy to clipboard]
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;
:
:
:
因为结点多而无规律性,所有这种建立方法是不能采用的,现在只是拿出来研究一下一棵树是如何建立起来的。
现在说说另一种树“二叉树”。因为二叉树与一般的树结构比较,二叉树在结构上更规范和更有确定性,因此,应用也比树更为广泛。二叉树与树不同,首先二叉树可以为空,空的二叉树没有结点；另外,在二叉树中,结点的子树是有序的,分左、右两棵子二叉树。
二叉树又是如何建立的呢?这里很简单,因为二叉树有其规律性,下面请看
CODE:
[Copy to clipboard]
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);
}
这条程序不单只建立了一个树,而且还给排好了序(左小右大)。输入相应的数值看看结果,如图第十三天图二。
今天也就是这些了,还有得就是要多看些递归的程序,因为树的建立和操作离不开递归。还有的就是大家做做如下一题,就是已知有一个无序的二叉树,让我们用中
序遍历排列成由大到小的程序。
第十四天 2002年08月18日
今天继续是讲二叉树,树一个重要的操作就是遍历。所谓遍历就是输出所有的结点,二叉树不同于树只有前序和后序遍历,因为二叉树左右子树木特点,所有还有另一种遍历方法,就是中序。这些遍历也十分简单,最主要的还是看根遍历的前后来分别是前中后序遍历的。下面看图第十四天这些颜色圈着代表分别当一个树来看,所有我们知道其规律就可以写出程序来了,程序也十分简单,如下:
CODE:
[Copy to clipboard]
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);
}
上面三种遍历是不是很简单(这个递归想一想就明白的了),而且他们很像似只是改变了行位置,我们由此可以看出如果是前序的那个输出是最先的,跟着才是进入左树到右树.看完了遍历就看看二叉查找树,二叉查找树是这样的一种树,他的左结点都小于根,右结点都大于左结点。有这么一种性质所以他的插入特别好办,用中序遍历的方法设计这个排序算法特别好,因为这个树本来就是这样排序下来的。下面就来看看程序是如何实现的
CODE:
[Copy to clipboard]
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[]已经是有了值,而且还是顺序排好的了。
CODE:
[Copy to clipboard]
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) /*注意就是这里有问题了*/
}
}
好像看上去没有什么问题似的,其实问题都挺大的,因为返回值根本不能返到最顶的那个自调用里,就只能返回一层,所有我的答案也根本出不来嘛。虽然老师还是赞了我一下会去用递归来做这题(其实因为本来循环可以很简单的可以实现了,而且不会浪费那么多的空间了),不过错还是错的。老师按照我的这个思路写了一个新的出来,如下:
CODE:
[Copy to clipboard]
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) ); /*巧妙的就是这里了*/
}
}
一条程序可以反应该人的水平说的真没错,这条程序几个地方都写得很好,特别巧妙的可以令递归返回值到最顶的那个可真棒啊。就这样随着时间的到来,我们也差不多放学了,我还真的要努力才行了,我要努力再努力,坚持再坚持。
第十五天 2002年08月18日
今天续着上堂的查找一章,上回已经讲了顺序查找和二分查找,这两个都是经常用到的。还有一种是特别的查找方法就是散列表(这里说明一下,这个查找方法是有几种不同的名字的,杂凑表和哈希表)。因为这个可能讲起来会用很多时间,老师也没有细详的解说,只是举了一个相对的思想出来,如下:
Ri keyi
a(0) = 20
a(1) = 30
a(2) = 40
a(3) = 50 addr(Ri)=H(keyi)
Ri=keyi/10-2 这个关系
就是这样,它对不同的问题当然有不同的关系,只能只要知道这个思想就好了。教程里的查找也就是这三种了,现在开始讲排序了。排序相对查找来说多了很多的方法,我们之前也碰过好几种排序的方法了,就是前一章的二叉树排序就是了,还有很早之前讲过的冒泡排序,我想很多人都应该知道这个经典的排序了吧。现在下来要讲的是直接插入排序法,这种方法的优势在于已经排好序的结点插入一个新的结点,有顺序的这样就可以用到上章学过的折半查找就可以找到该插入的位置了。其实给出一个没有序的一排数组,可以把它划分为两大部份,一部份是已排好序的结点,而另一部分则是待插入的结点,这样就可以模拟这个算法了,看看第十五天图一
这里可以清楚看到整个的思路是如何的。下面我们就要用C语言来到描述这个排序算法了,一共有好种种版本,大家一个一个的对比看看,看谁的效率高。
CODE:
[Copy to clipboard]
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[i],j=i-1;j>;=0 && t<e[j];j--)
e[j+1]=e[j];
e[j+1]=t;
}
另一个
CODE:
[Copy to clipboard]
for(i=1;i<=9;i++)
for(j=0;j<=i-1;j++)
{
if(a[j]>;a[i])
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
}
再另一个
CODE:
[Copy to clipboard]
for(i=1;i<n;i++)
{
k=a[i];
for(j=i-1;j>;=0;j--)
if(k>;a[j]) break;
else a[j+1]=a[j];
a[j+1]=k;
}
以前三个程序请大家自己分析,一定要自己动过脑去想.好了,难题终于又是到最后出来了,就是把这个排序的算法变为链表形式的,大家有没有想到呢?我们都急着笔去试了,可是最后还是不行,如果对于至前没有接触过这类型的是正常的情况,所有我们都没有做出来。下面看看老师写的程序好了:
前一些定义之类的略
CODE:
[Copy to clipboard]
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;
}
}
今天我有些失落,可能是因为做题的事吧,反正整个人都不知道怎么的,不过我还是会坚持,我会继续加把劲,希望大家可以和我一齐努力吧
第十六天
今天继续是链表方式的排序,前天的一题大家有没有弄懂了。弄不懂不要紧,这是要慢慢来的,急不来。
CODE:
[Copy to clipboard]
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里面的是如果这两个条件都是真的时候说明还没有找到,那么就让两个双链指针往后移一个继续比较,等找到符合了就可以插入了。
如果还是比较模糊的话大家不要紧,再看看下面这条程序:
CODE:
[Copy to clipboard]
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 程序员考试那版里,看看大家的
方法有何不同一齐讨论。大家先不要看我下面的程序:
一些定义略
CODE:
[Copy to clipboard]
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在的呢！现给出我原来没有改时候的原程序吧:
CODE:
[Copy to clipboard]
#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);至于用法大家查查书就行了。第二个问题得知原因之后更不是问题了,其实本身这就是对的。为什么我为产生这个误解,原因都是我试着读入数据来看的时候产生的,下面加下一些补充后程序如下:
CODE:
[Copy to clipboard]
#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[i].num, test[i].name, test[i].score, test[i].averge);
}
fclose(fp);
}
看上面加上了读入文件数据到结构数组test里,那么我们就看看结果吧,编译成果,好了,你是不是根本看不到你想要的结果呢,而得到是一堆莫名奇妙的符号呢,是的,没错,就是因为这点我才起初误认为写入数据fwrtie对指针的问题。好了下面我们解决这个迷吧(可能有些高手已经知道了),其实就是文件指针的问题,当我们上面那个写入到文件事那个指针已经到底了,到输入到数组里时当然就是不知明的数据
了。
CODE:
[Copy to clipboard]
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[i].num, test[i].name, test[i].score, test[i].averge);
}
在这句之前加上fseek(fp,0,0); 这个函数,这是和文件函数相配对的随机读入函数。这里参数都是0是说明文件指针指向最顶,好了,看看结果是不是我们想要的结果了。下面继续深入研究一下文件这章吧,你有没有想过把本身你写的这个程序C程序显示在屏幕上呢,当然不是用DOS的命令type 等一些其它的命令啦,就是直接用C语言程序把自身读出来。其实这个问题实现起来太简单了,你有看过老潭的那章吗?记得文件COPY的那个小实例吗>;哈哈~~,看下程序：
CODE:
[Copy to clipboard]
#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()这两个文件函数就可以了,大家自己试写写,我的程序如下：
CODE:
[Copy to clipboard]
#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);
}
}
看看,是不是很可爽很过瘾,自身源程序都倒过来了。好了,文章也该告一段落了。因为今天下午都要上学的原因,自然学的东西也多了,那么……嘻嘻,我的字也很应该多些吧,这样才对得住大家啊。不过因为今天做了很多初程的题目,所以也不太多的写上来了,写一个比较有用的吧,如下:
CODE:
[Copy to clipboard]
/*
这个程序的作用是将一个字符数组里大写的字母都改为小写*/
void main()
{
int i=0;
char s[120];
printf("Enter a string\n";
scanf("%s",s)
while( _____ )
{
if( _____ )
s[i]=s[i]-'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 粒珠子。
CODE:
[Copy to clipboard]
【程序】
#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[i] = 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) 。
第十九天
大家应该没有忙了今天是什么节日了吧?我想大家应该没有吧。因为这是我小时候最刺激的时候了,因为我和我的兄弟们都忙着准备那晚的东西,在街上捡些石头啊,线子啊,木棒啊,有什么用?当然就是用来打鬼的啊!(我们太大胆了吧!?) 真奇怪当时会这么勇呢。但同样是该节的今天(什么? 真的不知道今天是什么日子?那就是7月14鬼节啊!),我又约好朋友一齐去玩了,但屈指一数今年都已经18了,长大了,当然不能和小时候一样年少无知。所以我们什么也没有拿,只拿了最重要的一样东西,当然是钱啊,"有钱使的鬼推磨"。不过我们还是很快的喝了些东西就马上回家
了,望路上没有什么东西跟着我回去吧。
也就是因为这样今晚要写的补课日记也误了,只好今天(23号)把它补回吧。其实从前天开始已经是开始接触程序员的考试的试题了,希望大家在我讲的时候也能自己先做做。下面我们开始写下这道2001年程序员考试的试题,如下：
阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内。
[程序说明]
本程序中的函数 first_insert() 的功能是在已知链表的首表元之前插入一个指定值的表元;函数 reverse_copy() 的功能是按已知链表复制出一个新链表,但新链表的表元链接顺序与已知链表的表元链接顺序相反;函数 print_link() 用来输出链表中各表元的值;函数 free_link()用来释放链表全部表元空间。
[程序2〕
CODE:
[Copy to clipboard]
#include
〈stdip.h〉
#include〈malloc.h〉
typedef struct node
{
int val;
struct node *next;
} NODE;
void first_insert( NODE **p,int v)
{
NODE *q = (NODE *) malloc( sizeof(NODE));
q ->; va1 = v;__(1)__; *p = __(2)__;
}
NODE *reverse_copy(NODE *p)
{
NODE *u;
for( u = NULL ; p ; p = p ->;next ) first_insert(__(3)__);
return u;
}
void print_link( NODE *p )
{
for( ;__(4)__) printf ("%d\t" , p ->; val);
printf("\n";
}
void free_link(NODE*p)
{
NODE *u;
while( p != NULL){ u=p-〉next;free( p );__(5)__;}
}
void main()
{
NODE *link1 , *link2;
int i ;linkl = NULL ;
for( i = 1;i <= 10 ; i++ )
first insert( &link1,i );
link2 = revere_ copy(link1);
print_link(link1);freeJink(linkl);
print_link(link2);free_link(link2);
}
这个就是链表的问题了,其实我们知道每天基本上都会有一题链表的题目,所以大家也要准备好把这15分拿走喔。对于链表之前我也有说过了,这里就不再赘述.大家先做好这些填空好,我们一齐来分析讨论。
CODE:
[Copy to clipboard]
void first_insert( NODE **p,int v)
{
NODE *q = (NODE *) malloc( sizeof(NODE));
q ->; va1 = v;__(1)__; *p = __(2)__;
}
这个函数等于建立一个链表,不过这里最特别的就是用了指向指针的指针。其实也没有什么大不了,因为指针也是变量啊,当然就是有地址嘛!那么我们只是定义另一个指针指向这个指针罢了。利用指针的因素是因为这个函数没有返回值,我们想要返回头地址上去调用那里, 就要用到地址传递了.看看第一个空,整个函数的功能是插入一个新结点在链表头,那么填这个空就当然好办啦,就是q->;next=*p ,为什么p是地址还要加上*号呢? 上面不是说明了这个是指向指针的指针嘛,这里当然就是要取得链表头指针,把链表头链上新的结点。第二个空也实在是太简单了,因为
我们是要用返回链表头地指的所以就把新加入的结点变成头结点,即填q就行了。
CODE:
[Copy to clipboard]
NODE *reverse_copy(NODE *p)
{
NODE *u;
for( u = NULL ; p ; p = p ->;next ) first_insert(__(3)__);
return u;
}
这个空同样道理,复制一个新的反序链表. 因为first_insert()参数是指向指针的形式,所以我们就要用 & 取地址符把u的地址赋传入函数里了。还有另一个参数是数据,数据就是刚好循环里的p指针的数据。现在可以把这个空也填上了
&u,p->;val，就这样完成了。
CODE:
[Copy to clipboard]
void print_link( NODE *p )
{
for( ;__(4)__) printf ("%d\t" , p ->; val);
printf("\n";
}
如果算了链表连这个输出也不会我没有话好说了，答案是p;p=p->;next。
void free_link(NODE*p)
{
NODE *u;
while( p != NULL){ u=p->;next;free( p );__(5)__;}
}
这个也比较简单的问题,很容易可以看出来,因为链表不能断开,所以删除也要一个一个的按顺序来不是的话就可以删到中途就往下删不了.一定要一个临时的变量来到保存好链表的完整性才可以完整的删除链表,答案也是很简单p=u就行了。
虽然说难不难,但是没有搞懂链表的朋友也得借些机会慢慢的体会一下了。如果有什么问题的话可以发E-mail过来, E-mail是zhgpa@sohu.com不过在这里说明我也是初学者,愿和大家共同进步。
第二十天
今天又给讲了一道题,而且这道题就是上次我说过的那个同色珠子用双向链表存储的问题。所以可以再次看出我们程序员考试的题大都离不开链表和指针,这里指针当然就是最重要的了,因为链表也是指针构成的啊,一定要对指针熟悉才可以。下面请大家看题:
阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内.
[程序说明]
设一个环上有编号为 0～n-1 的 n 粒不同颜色的珠子(每粒珠子颜色用字母表示, n 粒珠子颜色由输入的字符串表示)。以环上某两粒珠子间为断点,从断点一方按顺时针方向取走连续同色的珠子,又从断点另一方按逆时针方向对剩下珠子取走连续同色的珠子,两者之和为该断点可取走珠子的粒数。移动断点,能取走的珠子数不尽相同.本程序找出可以取走最多的珠子数及断点的位置。程序中用双向链表存储字符串。例如,编号为0-9的10粒珠子颜色的字符串为"aaabbbadcc",对应链表为:图第二十天图一
若在2号与3号珠子间为断点,共可取走6粒珠子,且为取走的珠子数最多。
[程序]
CODE:
[Copy to clipboard]
#include
〈stdio.h〉
#include〈string.h〉
#include〈malloc.h〉
typedef struct node
{
char d ;
struct node *fpt ; /*后继指针*/
struct node*bpt ; /*前趋指针*/
}NODE ;
NODE *building( char *s ) /*生成双向循环链表*/
{
NODE *p = NULL , *q ;
while ( *s )
{
q = ( NODE * ) malloc( sizeof( NODE ) ) ;
q ->; ch = *s++ ;
if ( p = NULL ) p = q ->; fpt = q ->; b t = q ;
else {
p ->; bpt ->; fpt = q ;
q ->; fpt = p ;
q -〉bpt = __(1)__;
__(2)__ ;
}
}
return （q）
}
int count( NODE *start , int maxn ,int step ) /*求可取走珠子粒数*/
{
int color ,c ;
NODE *p ;
color = -1 ; C = 0 ;
for ( p = start ; c <maxn ; p = step >; O ? p ->; fpt ; p ->; bpt ){
if ( color == -1 ) color = p ->; ch ;
else if (__(3)__) break ;
c++
}
return (c);
}
int find ( char *s ,int *cutpos ) /*寻找取走珠子数最多的断点和粒数*/
{
int i , c , cut , maxc = 0 ,1en = strlen(s) ;
NODE *p ;
if ( ( p = building(s) ) = NULL ){ *cu1tpos = -1 ; return -1 ; }
i = 0 ;
do
{
c = count( p , 1en ,1 ) ;
c = c + __(4)__ ;
if ( c >; maxc ) { maxc = c ; cut = i ; }
__(5)__ ;
i++ ;
}while (i < len ) ;
* cutpos = cut ;
return maxc ;
}
void main()
{
int cut , max ;
char s[120] ;
scanf( , %s', s ) ;
max = find( s , &cut ) ;
printf ( "Cut position = %d , Number = %d.\n" , cut , max ) ;
}
不过在这题里我只想讲建立双向链表的那部份,其它的算法也类似于上次初程的那题,大家自己好好看一看就可以做出来了。也因为之前没有试过建立双向循环链表的经验, 所以今天我们大家也不会做,不过这也是正常的,因为这里建立的算法真的非常的巧妙。
CODE:
[Copy to clipboard]
NODE *building( char *s ) /*
生成双向循环链表*/
{
NODE *p = NULL , *q ;
while ( *s )
{
q = ( NODE * ) malloc( sizeof( NODE ) ) ;
q ->; ch = *s++ ;
if ( p = NULL ) p = q ->; fpt = q ->; b t = q ;
else
{
p ->; bpt ->; fpt = q ;
q ->; fpt = p ;
q ->; bpt = __(1)__;
__(2)__ ;
}
}
return （q）
}
这里也说明一下bpt指向前一个结点, fpt是指向后一个结点。好了,继续看程序
if ( p = NULL ) p = q ->; fpt = q ->; b t = q ;
这个很容易可以判断出是专门用来处理新建链表时第一个为头结点,初始化了结点q,使两个前后指针都指向自己先。
p ->; bpt ->; fpt = q ;
q ->; fpt = p ;
q ->; bpt =p->;bpt;
p->;bpt=q;
这里先给出答案先,因为这题确实比较难,所以直接说说他建立双向循环链表的思路好了,至于我能不能讲得明白真的很难担保。在这里我再此强调我自己也是个初学者,不过我会尽我的全力来到和大家一齐学习。
一句说完p->;btp->;fpt=q;和q-bpt=p->;bpt; 这两来句就是建立双向循环链表的技巧所在,所以我们要好好的看明白这两句。p->;btp->;fpt=q;分把这句拆开成各一句先,即p->;btp这里是代表双向链表的头结点前指针所指向的结点,注意双向链表在这里有特性, 就是头结点的前指针永远是指针最后一个的结点,所以在此基础上加上->;ftp即p->;btp->;fpt就可以得到最后一个结点的后指针所指向的结点,再将新建立的结点q链入，p->;btp->;fpt=q;就是链接好新结点了。
q->;ftp=p;这里也没有什么特别的,就只是直接后指针指向头结点,这样就头结点和尾结点相链了。再继续看第三行q ->; bpt =p->;bpt; 这里还有将新结点前指针所指向指在旧双向链表的尾结点。(这里也是同上的那个特性,头点结指针所指向的结点是尾结点) 第四句就是要把头结点前指针所指向指向新插入的新结点(即新双向链表的尾结点),这样就再次构成那个双向链表了。
希望大家能够看得明白我写的东西,如果真的不是太明的话,请用E-mail联系我,我一定会尽力的帮忙,因为我们大家都是为考程序员而努力的人。我相信我们的努力一定不会白白浪费的,努力~奋斗~~~
第二十一天 （完）
很快今天就是到补课结束的日子了, 现在的心情真的一言难尽。所以我也费话少说了,因为我根本无法用文字来表达我现在的心情。在放学前老师也答应了我们,如果我们考上了程序员就请我们吃一餐。我一定要努力把这餐得到手,大家也努力喔,我看到时还感激都来不及了。
好,下面我就讲一下最后一天的补课情况。今天还是围绕着练习题为主, 而且最都是有关链 表的题目(我再三强调,链表是考试的重点)。看下程序:
CODE:
[Copy to clipboard]
typedef struct elem
{
int val;
struct elem *next;
}intNode; /*一看定义这种结构就知道是链表了*/
/*合并升序链表*/
intNode *merge(intNode *a,intNode *b)
{
intNode *h=a,*p,*q;
while(b)
{
for(p=h;p && p->;val < b->;val; q=p,p=p->;next); /*注意这里又用到了双指针*/
if (p= =h)____1____;else_____2____;
q=b;b=b->;next;____3_____;
}
return h ;
}
看题目知道这是两条链表要合成一个新的链表,那么参数当然也就是有两条链表了。这条程序也比较简单,只是考了我们对链表是否熟悉, 在前几天的补课笔记里我已经讲了很多有关链表的知识了,所以不再赘述。我们来直接看看怎么填这些空
if (p= =h)____1____;else_____2____;
这里是特为处理如果合并时插入在头结点前的时候,原因嘛,那当然就是单向链表的特性了。从for循环里的条件p->;val < b->;val知道, 当b->;val小于p->;val就插,所以我们要插的当然就是b指向的结点了。第一个空可以马上的写出 h = b ,现在下面考虑不是插入头结点的情况。这个问题比较简单,这里运用了双指针,即q和p, 这里q一定是p之前的一个结点,为什么要用双指针？
这也是单向链表的缺点嘛。第二个空填 q->;next = b ,下面q=b是把新结点为p之前的结点,b=b->;next继续准备下一个待插入的结点,第三个空可以按链表的形式可以想出来该怎么填,其实就是没有把b->;next指向它的下一个结点,不过我们之前已经把 b=b->;next移向了下一个结点,所以不能再用b->;next=p了,不过还好q是在没有移之前把b的地址赋给了它,所以第三个空当然就是
q->;next=p了。
下面我们试着把这个程序改一改,在上面的程序里没有考虑到两条链表已经是排好序的特性,所以效率不高。看下程序:
CODE:
[Copy to clipboard]
intNode *merge(intNode *a,intNode *b)
{
intNode *h=a,*p,*q;
p=h; /*就是这里提前了，其它什么也没有动过*/
while(b)
{
for(;p && p->;val < b->;val; q=p,p=p->;next); /*注意这里又用到了双指针*/
if (p= =h) h=b ; else q->;next=b;
q=b;b=b->;next; q->;next=p ;
}
return h ;
}
我们就是这么一移,整个程序的效率就提高了, 这里是因为知道a已经是有序的了,程序就不必再从头开始搜索过 a 链表,直接在当前的位置继续往后比较就行了。下面老师还写了另外一个程序,我们来看看
CODE:
[Copy to clipboard]
intNode *merge(intNode *a,intNode *b)
{
intNode *h,*h1,*p,*q;
if (a->;val <= b->; val ){ h=a; h1=b }
else {h=b; h1=a}
for( p=h;p && h1
if(h1->;val<p->;val)
{
q->;next=h1;q=h;
h1=h1->;next;q->;next=p;
}
else
{
q=p;p=p->;next;
}
if (!p ) q->;next =h;
}
这条程序是用一个循环就可以把两条链表合并起来了,至于整个程序的流程就由大家自已慢慢看一下,其实有几个地方也特别的妙。如果有什么更好的方法或者有什么问题的话, 欢迎上来http://zhgpa.vicp.net 的交流论坛程序员考试专区里,把你的程序或者问题帖上去, 我们大家一同研究,这样的学习方式总比自己一个人狐独的看好啊。
补课也结束了,现在更多的时间在家里学习,也希望大家一同努力.总结一下这二十天的里的学习情况,总的来说真的学了不少东西,不过我还觉得浪费了一些时间在我下午的学习里,可能就是没人管吧,睡觉就成了我最好的理由不看书了。不过这几天一定不能让自己这样, 今年的梦想就是考上程序员,我知道坚持就能把这个梦
成真。