- 论坛徽章:
- 0
|
C语言补课笔记----(zt)
第十四天 2002年08月18日
今天继续是讲二叉树,树一个重要的操作就是遍历。所谓遍历就是输出所有的结点,二叉树不同于树只有前序和后序遍历,因为二叉树左右子树木特点,所有还有另一种遍历方法,就是中序。这些遍历也十分简单,最主要的还是看根遍历的前后来分别是前中后序遍历的。下面看图第十四天这些颜色圈着代表分别当一个树来看,所有我们知道其规律就可以写出程序来了,程序也十分简单,如下:
- 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) ); /*巧妙的就是这里了*/
- }
- }
一条程序可以反应该人的水平说的真没错,这条程序几个地方都写得很好,特别巧妙的可以令递归返回值到最顶的那个可真棒啊。就这样随着时间的到来,我们也差不多放学了,我还真的要努力才行了,我要努力再努力,坚持再坚持。
第十五天 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语言来到描述这个排序算法了,一共有好种种版本,大家一个一个的对比看看,看谁的效率高。
- 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;
- }
另一个
- 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;
- }
- }
再另一个
- 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;
- }
以前三个程序请大家自己分析,一定要自己动过脑去想.好了,难题终于又是到最后出来了,就是把这个排序的算法变为链表形式的,大家有没有想到呢?我们都急着笔去试了,可是最后还是不行,如果对于至前没有接触过这类型的是正常的情况,所有我们都没有做出来。下面看看老师写的程序好了:
前一些定义之类的略
- 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[i].num, test[i].name, test[i].score, test[i].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[i].num, test[i].name, test[i].score, test[i].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[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 粒珠子。
- 【程序】
- #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〕
- #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分拿走喔。对于链表之前我也有说过了,这里就不再赘述.大家先做好这些填空好,我们一齐来分析讨论。
- void first_insert( NODE **p,int v)
- {
- NODE *q = (NODE *) malloc( sizeof(NODE));
- q ->; va1 = v;__(1)__; *p = __(2)__;
- }
这个函数等于建立一个链表,不过这里最特别的就是用了指向指针的指针。其实也没有什么大不了,因为指针也是变量啊,当然就是有地址嘛!那么我们只是定义另一个指针指向这个指针罢了。利用指针的因素是因为这个函数没有返回值,我们想要返回头地址上去调用那里, 就要用到地址传递了.看看第一个空,整个函数的功能是插入一个新结点在链表头,那么填这个空就当然好办啦,就是q->;next=*p ,为什么p是地址还要加上*号呢? 上面不是说明了这个是指向指针的指针嘛,这里当然就是要取得链表头指针,把链表头链上新的结点。第二个空也实在是太简单了,因为
我们是要用返回链表头地指的所以就把新加入的结点变成头结点,即填q就行了。
- 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，就这样完成了。
- 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粒珠子,且为取走的珠子数最多。
[程序]
- #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 ) ;
- }
不过在这题里我只想讲建立双向链表的那部份,其它的算法也类似于上次初程的那题,大家自己好好看一看就可以做出来了。也因为之前没有试过建立双向循环链表的经验, 所以今天我们大家也不会做,不过这也是正常的,因为这里建立的算法真的非常的巧妙。
- 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联系我,我一定会尽力的帮忙,因为我们大家都是为考程序员而努力的人。我相信我们的努力一定不会白白浪费的,努力~奋斗~~~
第二十一天 （完）
很快今天就是到补课结束的日子了, 现在的心情真的一言难尽。所以我也费话少说了,因为我根本无法用文字来表达我现在的心情。在放学前老师也答应了我们,如果我们考上了程序员就请我们吃一餐。我一定要努力把这餐得到手,大家也努力喔,我看到时还感激都来不及了。
好,下面我就讲一下最后一天的补课情况。今天还是围绕着练习题为主, 而且最都是有关链 表的题目(我再三强调,链表是考试的重点)。看下程序:
- 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了。
下面我们试着把这个程序改一改,在上面的程序里没有考虑到两条链表已经是排好序的特性,所以效率不高。看下程序:
- 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 链表,直接在当前的位置继续往后比较就行了。下面老师还写了另外一个程序,我们来看看
- 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 的交流论坛程序员考试专区里,把你的程序或者问题帖上去, 我们大家一同研究,这样的学习方式总比自己一个人狐独的看好啊。
补课也结束了,现在更多的时间在家里学习,也希望大家一同努力.总结一下这二十天的里的学习情况,总的来说真的学了不少东西,不过我还觉得浪费了一些时间在我下午的学习里,可能就是没人管吧,睡觉就成了我最好的理由不看书了。不过这几天一定不能让自己这样, 今年的梦想就是考上程序员,我知道坚持就能把这个梦成真。 |
|
免费注册
发表于 2003-10-17 10:41
