啊哈!算法


第 1 章 一大波数正在靠近——排序 1 一大波数正在靠近 排序 第1章 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 2 第 1 节 最快最简单的排序——桶排序 在我们生活的这个世界中到处都是被排序过的东东。站队的时候会按照身高排序,考试 的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排 序……总之很多东东都需要排序,可以说排序是无处不在。现在我们举个具体的例子来介绍 一下排序算法。 首先出场的是我们的主人公小哼,上面这个可爱的娃就是啦。期末考试完了老师要将同 学们的分数按照从高到低排序。小哼的班上只有 5 个同学,这 5 个同学分别考了 5 分、3 分、 5 分、2 分和 8 分,哎考得真是惨不忍睹(满分是 10 分)。接下来将分数进行从大到小排序, 排序后是 8 5 5 3 2。你有没有什么好方法编写一段程序,让计算机随机读入 5 个数然后将这 5 个数从大到小输出?请先想一想,至少想 15 分钟再往下看吧(*^__^*) 。 第 1 章 一大波数正在靠近——排序 3 我们这里只需借助一个一维数组就可以解决这个问题。请确定你真的仔细想过再往下 看哦。 首先我们需要申请一个大小为 11 的数组 int a[11]。OK,现在你已经有了 11 个变量,编 号从 a[0]~a[10]。刚开始的时候,我们将 a[0]~a[10]都初始化为 0,表示这些分数还都没有人 得过。例如 a[0]等于 0 就表示目前还没有人得过 0 分,同理 a[1]等于 0 就表示目前还没有人 得过 1 分……a[10]等于 0 就表示目前还没有人得过 10 分。 下面开始处理每一个人的分数,第一个人的分数是 5 分,我们就将相对应的 a[5]的值在 原来的基础增加 1,即将 a[5]的值从 0 改为 1,表示 5 分出现过了一次。 第二个人的分数是 3 分,我们就把相对应的 a[3]的值在原来的基础上增加 1,即将 a[3] 的值从 0 改为 1,表示 3 分出现过了一次。 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 4 注意啦!第三个人的分数也是 5 分,所以 a[5]的值需要在此基础上再增加 1,即将 a[5] 的值从 1 改为 2,表示 5 分出现过了两次。 按照刚才的方法处理第四个和第五个人的分数。最终结果就是下面这个图啦。 你发现没有,a[0]~a[10]中的数值其实就是 0 分到 10 分每个分数出现的次数。接下来, 我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次,具体如下。 a[0]为 0,表示“0”没有出现过,不打印。 a[1]为 0,表示“1”没有出现过,不打印。 a[2]为 1,表示“2”出现过 1 次,打印 2。 a[3]为 1,表示“3”出现过 1 次,打印 3。 a[4]为 0,表示“4”没有出现过,不打印。 a[5]为 2,表示“5”出现过 2 次,打印 5 5。 a[6]为 0,表示“6”没有出现过,不打印。 a[7]为 0,表示“7”没有出现过,不打印。 a[8]为 1,表示“8”出现过 1 次,打印 8。 a[9]为 0,表示“9”没有出现过,不打印。 a[10]为 0,表示“10”没有出现过,不打印。 最终屏幕输出“2 3 5 5 8”,完整的代码如下。 #include int main() { int a[11],i,j,t; for(i=0;i<=10;i++) a[i]=0; //初始化为0 for(i=1;i<=5;i++) //循环读入5个数 { 第 1 章 一大波数正在靠近——排序 5 scanf("%d",&t); //把每一个数读到变量t中 a[t]++; //进行计数 } for(i=0;i<=10;i++) //依次判断a[0]~a[10] for(j=1;j<=a[i];j++) //出现了几次就打印几次 printf("%d ",i); getchar();getchar(); //这里的getchar();用来暂停程序,以便查看程序输出的内容 //也可以用system("pause");等来代替 return 0; } 输入数据为: 5 3 5 2 8 仔细观察的同学会发现,刚才实现的是从小到大排序。但是我们要求是从大到小排序, 这该怎么办呢?还是先自己想一想再往下看哦。 其实很简单。只需要将 for(i=0;i<=10;i++)改为 for(i=10;i>=0;i--)就 OK 啦,快去试一试吧。 这种排序方法我们暂且叫它“桶排序”。因为其实真正的桶排序要比这个复杂一些,以 后再详细讨论,目前此算法已经能够满足我们的需求了。 这个算法就好比有 11 个桶,编号从 0~10。每出现一个数,就在对应编号的桶中放一个 小旗子,最后只要数数每个桶中有几个小旗子就 OK 了。例如 2 号桶中有 1 个小旗子,表示 2 出现了一次;3 号桶中有 1 个小旗子,表示 3 出现了一次;5 号桶中有 2 个小旗子,表示 5 出现了两次;8 号桶中有 1 个小旗子,表示 8 出现了一次。 现在你可以尝试一下输入 n 个 0~1000 之间的整数,将它们从大到小排序。提醒一下, 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 6 如果需要对数据范围在 0~1000 之间的整数进行排序,我们需要 1001 个桶,来表示 0~1000 之间每一个数出现的次数,这一点一定要注意。另外,此处的每一个桶的作用其实就是“标 记”每个数出现的次数,因此我喜欢将之前的数组 a 换个更贴切的名字 book(book 这个单 词有记录、标记的意思),代码实现如下。 #include int main() { int book[1001],i,j,t,n; for(i=0;i<=1000;i++) book[i]=0; scanf("%d",&n);//输入一个数n,表示接下来有n个数 for(i=1;i<=n;i++)//循环读入n个数,并进行桶排序 { scanf("%d",&t); //把每一个数读到变量t中 book[t]++; //进行计数,对编号为t的桶放一个小旗子 } for(i=1000;i>=0;i--) //依次判断编号1000~0的桶 for(j=1;j<=book[i];j++) //出现了几次就将桶的编号打印几次 printf("%d ",i); getchar();getchar(); return 0; } 可以输入以下数据进行验证。 10 8 100 50 22 15 6 1 1000 999 0 运行结果是: 1000 999 100 50 22 15 8 6 1 0 最后来说下时间复杂度的问题。代码中第 6 行的循环一共循环了 m 次( m 为桶的个数), 第 9 行的代码循环了 n 次(n 为待排序数的个数),第 14 行和第 15 行一共循环了 m+n 次。 所以整个排序算法一共执行了 m+n+m+n 次。我们用大写字母 O 来表示时间复杂度,因此该 第 1 章 一大波数正在靠近——排序 7 算法的时间复杂度是 O(m+n+m+n)即 O(2*(m+n))。我们在说时间复杂度的时候可以忽略较小 的常数,最终桶排序的时间复杂度为 O(m+n)。还有一点,在表示时间复杂度的时候,n 和 m 通常用大写字母即 O(M+N)。 这是一个非常快的排序算法。桶排序从 1956 年就开始被使用,该算法的基本思想是由 E.J.Issac 和 R.C.Singleton 提出来的。之前我说过,其实这并不是真正的桶排序算法,真正的 桶排序算法要比这个更加复杂。但是考虑到此处是算法讲解的第一篇,我想还是越简单易懂 越好,真正的桶排序留在以后再聊吧。需要说明一点的是:我们目前学习的简化版桶排序算 法,其本质上还不能算是一个真正意义上的排序算法。为什么呢?例如遇到下面这个例子就 没辙了。 现在分别有 5 个人的名字和分数:huhu 5 分、haha 3 分、xixi 5 分、hengheng 2 分和 gaoshou 8 分。请按照分数从高到低,输出他们的名字。即应该输出 gaoshou、huhu、xixi、haha、hengheng。 发现问题了没有?如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输 出的也仅仅是分数,但没有对人本身进行排序。也就是说,我们现在并不知道排序后的分数 原本对应着哪一个人!这该怎么办呢?不要着急,请看下节——冒泡排序。 第 2 节 邻居好说话——冒泡排序 简化版的桶排序不仅仅有上一节所遗留的问题,更要命的是:它非常浪费空间!例如需 要排序数的范围是 0~2100000000 之间,那你则需要申请 2100000001 个变量,也就是说要写 成 int a[2100000001]。因为我们需要用 2100000001 个“桶”来存储 0~2100000000 之间每一 个数出现的次数。即便只给你 5 个数进行排序(例如这 5 个数是 1、1912345678、2100000000、 18000000 和 912345678),你也仍然需要 2100000001 个“桶”,这真是太浪费空间了!还有, 如果现在需要排序的不再是整数而是一些小数,比如将 5.56789、2.12、1.1、3.123、4.1234 这五个数进行从小到大排序又该怎么办呢?现在我们来学习另一种新的排序算法:冒泡排 序。它可以很好地解决这两个问题。 冒泡排序的基本思想是:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换 过来。 例如我们需要将 12 35 99 18 76 这 5 个数进行从大到小的排序。既然是从大到小排序, 也就是说越小的越靠后,你是不是觉得我在说废话,但是这句话很关键(∩_∩)。 首先比较第 1 位和第 2 位的大小,现在第 1 位是 12,第 2 位是 35。发现 12 比 35 要小, 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 8 因为我们希望越小越靠后嘛,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 12 99 18 76。 按照刚才的方法,继续比较第 2 位和第 3 位的大小,第 2 位是 12,第 3 位是 99。12 比 99 要小,因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 99 12 18 76。 根据刚才的规则,继续比较第 3 位和第 4 位的大小,如果第 3 位比第 4 位小,则交换位 置。交换之后这 5 个数的顺序是 35 99 18 12 76。 最后,比较第 4 位和第 5 位。4 次比较之后 5 个数的顺序是 35 99 18 76 12。 经过 4 次比较后我们发现最小的一个数已经就位(已经在最后一位,请注意 12 这个数 的移动过程),是不是很神奇。现在再来回忆一下刚才比较的过程。每次都是比较相邻的两 个数,如果后面的数比前面的数大,则交换这两个数的位置。一直比较下去直到最后两个数 比较完毕后,最小的数就在最后一个了。就如同是一个气泡,一步一步往后“翻滚”,直到 最后一位。所以这个排序的方法有一个很好听的名字“冒泡排序”。 说到这里其实我们的排序只将 5 个数中最小的一个归位了。每将一个数归位我们将其称 第 1 章 一大波数正在靠近——排序 9 为“一趟”。下面我们将继续重复刚才的过程,将剩下的 4 个数一一归位。 好,现在开始“第二趟”,目标是将第 2 小的数归位。首先还是先比较第 1 位和第 2 位, 如果第 1 位比第 2 位小,则交换位置。交换之后这 5 个数的顺序是 99 35 18 76 12。接下来你 应该都会了,依次比较第 2 位和第 3 位,第 3 位和第 4 位。注意此时已经不需要再比较第 4 位和第 5 位。因为在第一趟结束后已经可以确定第 5 位上放的是最小的了。第二趟结束之后 这 5 个数的顺序是 99 35 76 18 12。 “第三趟”也是一样的。第三趟之后这 5 个数的顺序是 99 76 35 18 12。 现在到了最后一趟“第四趟”。有的同学又要问了,这不是已经排好了吗?还要继续? 当然,这里纯属巧合,你若用别的数试一试可能就不是了。你能找出这样的数据样例来吗? 请试一试。 “冒泡排序”的原理是:每一趟只能确定将一个数归位。即第一趟只能确定将末位上的 数(即第 5 位)归位,第二趟只能将倒数第 2 位上的数(即第 4 位)归位,第三趟只能将倒 数第 3 位上的数(即第 3 位)归位,而现在前面还有两个位置上的数没有归位,因此我们仍 然需要进行“第四趟”。 “第四趟”只需要比较第 1 位和第 2 位的大小。因为后面三个位置上的数归位了,现在 第 1 位是 99,第 2 位是 76,无需交换。这 5 个数的顺序不变仍然是 99 76 35 18 12。到此排 序完美结束了,5 个数已经有 4 个数归位,那最后一个数也只能放在第 1 位了。 最后我们总结一下:如果有 n 个数进行排序,只需将 n1 个数归位,也就是说要进行 n-1 趟操作。而“每一趟”都需要从第 1 位开始进行相邻两个数的比较,将较小的一个数放 在后面,比较完毕后向后挪一位继续比较下面两个相邻数的大小,重复此步骤,直到最后一 个尚未归位的数,已经归位的数则无需再进行比较(已经归位的数你还比较个啥,浪费表情)。 这个算法是不是很强悍?记得我每次拍集体照的时候就总是被别人换来换去的,当时特 别烦。不知道发明此算法的人当时的灵感是否来源于此。啰里吧嗦地说了这么多,下面是代 码。建议先自己尝试去实现一下看看,再来看我是如何实现的。 #include int main() { int a[100],i,j,t,n; scanf("%d",&n); //输入一个数n,表示接下来有n个数 for(i=1;i<=n;i++) //循环读入n个数到数组a中 scanf("%d",&a[i]); 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 10 //冒泡排序的核心部分 for(i=1;i<=n-1;i++) //n个数排序,只用进行n-1趟 { for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数,想一想为什 么到n-i就可以了。 { if(a[j] struct student { char name[21]; char score; };//这里创建了一个结构体用来存储姓名和分数 int main() { struct student a[100],t; int i,j,n; scanf("%d",&n); //输入一个数n for(i=1;i<=n;i++) //循环读入n个人名和分数 scanf("%s %d",a[i].name,&a[i].score); 第 1 章 一大波数正在靠近——排序 11 //按分数从高到低进行排序 for(i=1;i<=n-1;i++) { for(j=1;j<=n-i;j++) { if(a[j].score int a[101],n;//定义全局变量,这两个变量需要在子函数中使用 void quicksort(int left,int right) { int i,j,t,temp; if(left>right) return; temp=a[left]; //temp中存的就是基准数 i=left; j=right; while(i!=j) { //顺序很重要,要先从右往左找 while(a[j]>=temp && i int main() { int a[1001],n,i,t; for(i=1;i<=1000;i++) a[i]=0; //初始化 scanf("%d",&n); //读入n for(i=1;i<=n;i++) //循环读入n个图书的ISBN号 { scanf("%d",&t); //把每一个ISBN号读到变量t中 a[t]=1; //标记出现过的ISBN号 } for(i=1;i<=1000;i++) //依次判断1~1000这个1000个桶 { if(a[i]==1)//如果这个ISBN号出现过则打印出来 printf("%d ",i); } getchar();getchar(); return 0; } 这种方法的时间复杂度就是桶排序的时间复杂度,为 O(N+M)。 第二种方法我们需要先排序再去重。排序我们可以用冒泡排序或者快速排序。 20 40 32 67 40 20 89 300 400 15 将这 10 个数从小到大排序之后为 15 20 20 32 40 40 67 89 300 400。 接下来,要在输出的时候去掉重复的。因为我们已经排好序,所以相同的数都会紧挨在 第 1 章 一大波数正在靠近——排序 23 一起。只要在输出的时候,预先判断一下当前这个数 a[i]与前面一个数 a[i1]是否相同。如 果相同则表示这个数之前已经输出过了,不用再次输出;不同则表示这个数是第一次出现, 需要输出这个数。 #include int main() { int a[101],n,i,j,t; scanf("%d",&n); //读入n for(i=1;i<=n;i++) //循环读入n个图书ISBN号 { scanf("%d",&a[i]); } //开始冒泡排序 for(i=1;i<=n-1;i++) { for(j=1;j<=n-i;j++) { if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } printf("%d ",a[1]); //输出第1个数 for(i=2;i<=n;i++) //从2循环到n { if( a[i] != a[i-1] ) //如果当前这个数是第一次出现则输出 printf("%d ",a[i]); } getchar();getchar(); return 0; } 这种方法的时间复杂度由两部分组成,一部分是冒泡排序的时间复杂度,是 N (N2),另 一部分是读入和输出,都是 O(N),因此整个算法的时间复杂度是 O(2*N+N 2)。相对于 N2 来 说,2*N 可以忽略(我们通常忽略低阶),最终该方法的时间复杂度是 O(N2)。 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 24 接下来我们还需要看下数据范围。每个图书 ISBN 号都是 1~1000 之间的整数,并且参 加调查的同学人数不超过 100,即 n≤100。之前已经说过,在粗略计算时间复杂度的时候, 我们通常认为计算机每秒钟大约运行 10 亿次(当然实际情况要更快)。因此以上两种方法都 可以在 1 秒钟内计算出解。如果题目中图书的 ISBN 号范围不是在 1~1000 之间,而是 2147483648~2147483647 之间的话,那么第一种方法就不可行了,因为你无法申请出这么 大的数组来标记每一个 ISBN 号是否出现过。另外如果 n 的范围不是小于等于 100,而是小 于等于 10 万,那么第二种方法的排序部分也不能使用冒泡排序。因为题目要求的时间限制 是 1 秒,使用冒泡排序对 10 万个数进行排序,计算机要运行 100 亿次,需要 10 秒钟,因此 要替换为快速排序,快速排序只需要 100000×log2100000≈100000×17≈170 万次,这还不到 0.0017 秒。是不是很神奇?同样的问题使用不同的算法竟然有如此之大的时间差距,这就是 算法的魅力! 我们来回顾一下本章三种排序算法的时间复杂度。桶排序是最快的,它的时间复杂度是 O(N+M);冒泡排序是 O(N 2);快速排序是 O(NlogN)。 最后,你可以到“添柴编程学习网”提交本题的代码,来验证一下你的解答是否完全 正确。《小哼买书》题目的地址如下: www.tianchai.org/problem-12001.html 接下来,本书中的所有算法都可以去“添柴编程学习网”一一验证。如果你从来没有 使用过类似“添柴编程学习网”这样的在线自动评测系统(online judge),那么我推荐你可 以先尝试提交下这道题:A+B=? 地址如下: www.tianchai.org/problem-10000.html 第 2 章 栈、队列、链表 25 栈、队列、链表 第2章 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 26 第 1 节 解密 QQ 号——队列 新学期开始了,小哈是小哼的新同桌(小哈是个小美女哦~),小哼向小哈询问 QQ 号, 小哈当然不会直接告诉小哼啦,原因嘛你懂的。所以小哈给了小哼一串加密过的数字,同时 小哈也告诉了小哼解密规则。规则是这样的:首先将第 1 个数删除,紧接着将第 2 个数放到 这串数的末尾,再将第 3 个数删除并将第 4 个数放到这串数的末尾,再将第 5 个数删除…… 直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一 起就是小哈的 QQ 啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。 第 2 章 栈、队列、链表 27 OK,现在轮到你动手的时候了。快去找出 9 张便签或小纸片,将“6 3 1 7 5 8 9 2 4”这 9 个数分别写在 9 张便签上,模拟一下解密过程。如果你没有理解错解密规则的话,解密后 小哈的 QQ 号应该是“6 1 5 9 4 7 2 8 3”。 其实解密的过程就像是将这些数“排队”。每次从最前面拿两个,第 1 个扔掉,第 2 个 放到尾部。具体过程是这样的:刚开始这串数是“6 3 1 7 5 8 9 2 4”,首先删除 6 并将 3 放到 这串数的末尾,这串数更新为“1 7 5 8 9 2 4 3”。接下来删除 1 并将 7 放到末尾,即更新为 “5 8 9 2 4 3 7”。再删除 5 并将 8 放到末尾即“9 2 4 3 7 8”,删除 9 并将 2 放到末尾即“4 3 7 8 2”,删除 4 并将 3 放到末尾即“7 8 2 3”,删除 7 并将 8 放到末尾即“2 3 8”,删除 2 并将 3 放到末尾即“8 3”,删除 8 并将 3 放到末尾即“3”,最后删除 3。因此被删除的顺序是“6 1 5 9 4 7 2 8 3”,这就是小哈的 QQ 号码了,你可以加她试试看^_^。 既然现在已经搞清楚了解密法则,不妨自己尝试一下去编程,我相信你一定可以写出来的。 首先需要一个数组来存储这一串数即 int q[101],并初始化这个数组即 int q[101]= {0,6,3,1,7,5,8,9,2,4};(此处初始化是我多写了一个 0,用来填充 q[0],因为我比较喜欢从 q[1] 开始用,对数组初始化不是很理解的同学可以去看一下我的上本书《啊哈 C!思考快你一 步》)。接下来就是模拟解密的过程了。 解密的第一步是将第一个数删除,你可以想一下如何在数组中删除一个数呢。最简单的 方法是将所有后面的数都往前面挪动一位,将前面的数覆盖。就好比我们在排队买票,最前 面的人买好离开了,后面所有的人就需要全部向前面走一步,补上之前的空位,但是这样的 做法很耗费时间。 在这里,我将引入两个整型变量 head 和 tail。head 用来记录队列的队首(即第一位), tail 用来记录队列的队尾(即最后一位)的下一个位置。你可能会问:为什么 tail 不直接记 录队尾,却要记录队尾的下一个位置呢?这是因为当队列中只剩下一个元素时,队首和队尾 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 28 重合会带来一些麻烦。我们这里规定队首和队尾重合时,队列为空。 现在有 9 个数,9 个数全部放入队列之后 head=1;tail=10;此时 head 和 tail 之间的数就是 目前队列中“有效”的数。如果要删除一个数的话,就将 head++就 OK 了,这样仍然可以保 持 head 和 tail 之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间,却节省了 大量的时间,这是非常划算的。新增加一个数也很简单,把需要增加的数放到队尾即 q[tail] 之后再 tail++就 OK 啦。 我们来小结一下,在队首删除一个数的操作是 head++;。 在队尾增加一个数(假设这个数是 x)的操作是 q[tail]=x;tail++;。 整个解密过程,请看下面这个霸气外漏的图。 第 2 章 栈、队列、链表 29 最后的输出就是 6 1 5 9 4 7 2 8 3,代码实现如下。 #include int main() { int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail; int i; //初始化队列 head=1; tail=10; //队列中已经有9个元素了,tail指向队尾的后一个位置 while(head struct queue { int data[100];//队列的主体,用来存储内容 int head;//队首 第 2 章 栈、队列、链表 31 int tail;//队尾 }; int main() { struct queue q; int i; //初始化队列 q.head=1; q.tail=1; for(i=1;i<=9;i++) { //依次向队列插入9个数 scanf("%d",&q.data[q.tail]); q.tail++; } while(q.head #include int main() { char a[101],s[101]; int i,len,mid,next,top; gets(a); //读入一行字符串 len=strlen(a); //求字符串的长度 mid=len/2-1; //求字符串的中点 top=0;//栈的初始化 //将mid前的字符依次入栈 for(i=0;i<=mid;i++) s[++top]=a[i]; //判断字符串的长度是奇数还是偶数,并找出需要进行字符匹配的起始下标 if(len%2==0) next=mid+1; else next=mid+2; //开始匹配 for(i=next;i<=len-1;i++) 第 2 章 栈、队列、链表 35 { if(a[i]!=s[top]) break; top--; } //如果top的值为0,则说明栈内所有的字符都被一一匹配了 if(top==0) printf("YES"); else printf("NO"); getchar();getchar(); return 0; } 可以输入以下数据进行验证。 ahaha 运行结果是: YES 栈还可以用来进行验证括号的匹配。比如输入一行只包含“()[]{}”的字符串,请判断 形如“([{}()])”或者“{()[]{}}”的是否可以正确匹配。显然上面两个例子都是可以正确匹 配的。“([)]”是不能匹配的。有兴趣的同学可以自己动手来试一试。 堆栈最早由 Alan M. Turing(艾伦·图灵)于 1946 年提出,当时是为了解决子程序的调 用和返回。艾伦·图灵这个大帅哥可是个大牛人,图灵奖就是以他的名字命名的。如果你对 他感兴趣不妨去读一读《艾伦·图灵传:如谜的解谜者》和《图灵的秘密》。 第 3 节 纸牌游戏——小猫钓鱼 星期天小哼和小哈约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓 鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的 第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌 的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 36 可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人 手中的牌全部出完时,游戏结束,对手获胜。 假如游戏开始时,小哼手中有 6 张牌,顺序为 2 4 1 2 5 6,小哈手中也有 6 张牌,顺序 为 3 1 3 5 6 4,最终谁会获胜呢?现在你可以拿出纸牌来试一试。接下来请你写一个程序来 自动判断谁将获胜。这里我们做一个约定,小哼和小哈手中牌的牌面只有 1~9。 我们先来分析一下这个游戏有哪几种操作。小哼有两种操作,分别是出牌和赢牌。这恰 好对应队列的两个操作,出牌就是出队,赢牌就是入队。小哈的操作和小哼是一样的。而桌 子就是一个栈,每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候,依次将牌从桌上 拿走,这就相当于出栈。那如何解决赢牌的问题呢?赢牌的规则是:如果某人打出的牌与桌 上的某张牌相同,即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌 了呢?最简单的方法就是枚举桌上的每一张牌,当然也有更好的办法我们待会再说。OK, 小结一下,我们需要两个队列、一个栈来模拟整个游戏。 首先我们先来创建一个结构体用来实现队列,如下。 struct queue { int data[1000]; int head; int tail; } 第 2 章 栈、队列、链表 37 上面代码中 head 用来存储队头,tail 用来存储队尾。数组 data 用来存储队列中的元素, 数组 data 的大小我预设为 1000,其实应该设置得更大一些,以防数组越界。当然对于本题 的数据来说 1000 已经足够了。 再创建一个结构体用来实现栈,如下。 struct stack { int data[10]; int top; }; 其中 top 用来存储栈顶,数组 data 用来存储栈中的元素,大小设置为 10。因为只有 9 种不同的牌面,所以桌上最多可能有 9 张牌,因此数组大小设置为 10 就够了。提示一下: 为什么不设置为 9 呢?因为 C 语言数组下标是从 0 开始的。 接下来我们需要定义两个队列变量 q1 和 q2。q1 用来模拟小哼手中的牌,q2 用来模拟小 哈手中的牌。定义一个栈变量 s 用来模拟桌上的牌。 struct queue q1,q2; struct stack s; 接下来来初始化一下队列和栈。 //初始化队列q1和q2为空,此时两人手中都还没有牌 q1.head=1; q1.tail=1; q2.head=1; q2.tail=1; //初始化栈s为空,最开始的时候桌上也没有牌 s.top=0; 接下来需要读入小哼和小哈最初时手中的牌,分两次读入,每次读入 6 个数,分别插入 q1 和 q2 中。 //先读入6张牌,放到小哼手上 for(i=1;i<=6;i++) { scanf("%d",&q1.data[q1.tail]); //读入一个数到队尾 q1.tail++;//队尾往后挪一位 } //再读入6张牌,放到小哈手上 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 38 for(i=1;i<=6;i++) { scanf("%d",&q2.data[q2.tail]); //读入一个数到队尾 q2.tail++;//队尾往后挪一位 } 现在准备工作已经基本上做好了,游戏正式开始,小哼先出牌。 t=q1.data[q1.head]; //小哼先亮出一张牌 小哼打出第一张牌,也就是 q1 的队首,我们将这张牌存放在临时变量 t 中。接下来我们 要判断小哼当前打出的牌是否能赢得桌上的牌。也就是判断桌上的牌与 t 有没有相同的,如 何实现呢?我们需要枚举桌上的每一张牌与 t 进行比对,具体如下: flag=0; for(i=1;i<=top;i++) { if(t==s[i]) { flag=1; break; } } 如果 flag 的值为 0 就表明小哼没能赢得桌上的牌,将打出的牌留在桌上。 if(flag==0) { //小哼此轮没有赢牌 q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队 s.top++; s.data[s.top]=t; //再把打出的牌放到桌上,即入栈 } 如果 flag的值为 1就表明小哼可以赢得桌上的牌,需要将赢得的牌依次放入小哼的手中。 f(flag==1) { //小哼此轮可以赢牌 q1.head++;//小哼已经打出一张牌,所以要把打出的牌出队 q1.data[q1.tail]=t; //因为此轮可以赢牌,所以紧接着把刚才打出的牌又放到手中牌的 末尾 q1.tail++; while(s.data[s.top]!=t) //把桌上可以赢得的牌(从当前桌面最顶部一张牌开始取,直 至取到与打出的牌相同为止)依次放到手中牌的末尾 第 2 章 栈、队列、链表 39 { q1.data[q1.tail]=s.data[s.top]; //依次放入队尾 q1.tail++; s.top--; //栈中少了一张牌,所以栈顶要减1 } } 小哼出牌的所有阶段就模拟完了,小哈出牌和小哼出牌是一样的。接下来我们要判断游 戏如何结束。即只要两人中有一个人的牌用完了游戏就结束了。因此需要在模拟两人出牌代 码的外面加一个 while 循环来判断,如下。 while(q1.head0) //如果桌上有牌则依次输出桌上的牌 { printf("\n桌上的牌是"); for(i=1;i<=s.top;i++) printf(" %d",s.data[i]); } else printf("\n桌上已经没有牌了"); } } 反之,小哈获胜,代码的实现也是差不多的,就不再赘述了。到此,所有的代码实现就 都讲完了。 在上面我们讲解的所有实现中,每个人打出一张牌后,判断能否赢牌这一点可以优化。 之前我们是通过枚举桌上的每一张牌来实现的,即用了一个 for 循环来依次判断桌上的每一 张牌是否与打出的牌相等。其实有更好的办法来解决这个问题,就是用一个数组来记录桌上 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 40 有哪些牌。因为牌面只有 1~9,因此只需开一个大小为 10 的数组来记录当前桌上已经有哪 些牌面就可以了。 int book[10]; 这里我再一次使用了 book 这个单词,因为这个单词有记录、登记的意思,而且单词拼 写简洁。另外很多国外的算法书籍在处理需要标记问题的时候也都使用 book 这个单词,因 此我这里就沿用了。当然你也可以使用 mark 等你自己觉得好理解的单词啦。下面需要将数 组 book[1]~book[9]初始化为 0,因为刚开始桌面上一张牌也没有。 for(i=1;i<=9;i++) book[i]=0; 接下来,如果桌面上增加了一张牌面为 2 的牌,那就需要将 book[2]设置为 1,表示牌面 为 2 的牌桌上已经有了。当然如果这张牌面为 2 的牌被拿走后,需要及时将 book[2]重新设 置为 0,表示桌面上已经没有牌面为 2 的牌了。这样一来,寻找桌上是否有与打出的牌牌面 相同的牌,就不需要再循环枚举桌面上的每一张牌了,而只需用一个 if 判断即可。这一点是 不是有点像第 1 章第 1 节的桶排序的方法呢?具体如下。 t=q1.data[q1.head]; //小哼先亮出一张牌 if(book[t]==0) // 表明桌上没有牌面为t的牌 { //小哼此轮没有赢牌 q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队 s.top++; s.data[s.top]=t; //再把打出的牌放到桌上,即入栈 book[t]=1; //标记桌上现在已经有牌面为t的牌 } OK,算法的实现讲完了,下面给出完整的代码,如下: #include struct queue { int data[1000]; int head; int tail; }; 第 2 章 栈、队列、链表 41 struct stack { int data[10]; int top; }; int main() { struct queue q1,q2; struct stack s; int book[10]; int i,t; //初始化队列 q1.head=1; q1.tail=1; q2.head=1; q2.tail=1; //初始化栈 s.top=0; //初始化用来标记的数组,用来标记哪些牌已经在桌上 for(i=1;i<=9;i++) book[i]=0; //依次向队列插入6个数 //小哼手上的6张牌 for(i=1;i<=6;i++) { scanf("%d",&q1.data[q1.tail]); q1.tail++; } //小哈手上的6张牌 for(i=1;i<=6;i++) { scanf("%d",&q2.data[q2.tail]); q2.tail++; } while(q1.head0) //如果桌上有牌则依次输出桌上的牌 { printf("\n桌上的牌是"); for(i=1;i<=s.top;i++) printf(" %d",s.data[i]); } else printf("\n桌上已经没有牌了"); } else { printf("小哈win\n"); printf("小哈当前手中的牌是"); for(i=q2.head;i<=q2.tail-1;i++) printf(" %d",q2.data[i]); if(s.top>0) //如果桌上有牌则依次输出桌上的牌 { printf("\n桌上的牌是"); for(i=1;i<=s.top;i++) printf(" %d",s.data[i]); } else printf("\n桌上已经没有牌了"); } getchar();getchar(); return 0; } 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 44 可以输入以下数据进行验证。 2 4 1 2 5 6 3 1 3 5 6 4 运行结果是: 小哼win 小哼当前手中的牌是 5 6 2 3 1 4 6 5 桌上的牌是 2 1 3 4 接下来你需要自己设计一些测试数据来检验你的程序。在设计测试数据的时候你要考虑 各种情况,包括各种极端情况。通过设计测试数据来检测我们的程序是否“健壮”是非常重 要的,如果你的程序可以通过任何一组测试数据,才表示你的程序是完全正确的。 如果你设计一些测试数据来验证的话,会发现我们刚才的代码其实还是有问题的。比如 游戏可能无法结束。就是小哼和小哈可以永远玩下去,谁都无法赢得对方所有的牌。请你自 己想一想如何解决游戏无法结束的问题。 第 4 节 链表 在存储一大波数的时候,我们通常使用的是数组,但有时候数组显得不够灵活,比如下 面这个例子。 有一串已经从小到大排好序的数 2 3 5 8 9 10 18 26 32。现需要往这串数中插入 6 使其得 到的新序列仍符合从小到大排列。如我们使用数组来实现这一操作,则需要将 8 和 8 后面的 数都依次往后挪一位,如下: 这样操作显然很耽误时间,如果使用链表则会快很多。那什么是链表呢?请看下图。 第 2 章 栈、队列、链表 45 此时如果需要在 8 前面插入一个 6,就只需像下图这样更改一下就可以了,而无需再将 8 及后面的数都依次往后挪一位。是不是很节省时间呢? 那么如何实现链表呢?在 C 语言中可以使用指针和动态分配内存函数 malloc 来实现。 指针?天啊!如果你在学习 C 语言的时候没有搞懂指针,或者还不知道指针是啥,不要紧, 我们现在就回顾一下指针。指针其实超级简单。如果你已经对指针和 malloc 了如指掌则可以 跳过下面这一小段,继续往后看。 先看下面两行语句。 int a; int *p; 第一行我们很熟悉了,就是定义一个整型变量 a。第二行你会发现在 p 前面多了一个* 号,这就表示定义了一个整型指针变量 p。即定义一个指针,只需在变量前面加一个*号就 OK 啦。 接下来,指针有什么作用呢?答案是:存储一个地址。确切地说是存储一个内存空间的 地址,比如说整型变量 a 的地址。严格地说这里的指针 p 也只能存储“一个存放整数的内存 空间”的地址,因为在定义的时候我们已经限制了这一点(即定义的时候*p 的前面是 int)。 当然你也可以定义一个只能用来存储“一个存放浮点数的内存空间”的地址,例如: double *p; 简单地说,指针就是用来存储地址的。你可能要问:不就是存储地址嘛,地址不都一样 吗,为什么还要分不同类型的指针呢?不要着急,待会后面再解释。接下来需要解决的一个 问题:整型指针 p 如何才能存储整型变量 a 的地址呢?很简单,如下: p=&a; &这个符号很熟悉吧,就是经常在 scanf 函数中用到的&。&叫取地址符。这样整型指针 p 就获得了(存储了)整型变量 a 的地址,我们可以形象地理解整型指针 p 指向了整型变量 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 46 a。p 指向了 a 之后,有什么用呢?用处就是我们可以用指针 p 来操作变量 a 了。比如我们可 以通过操作指针 p 来输出变量 a 的值,如下: #include int main() { int a=10; int *p; //定义个指针p p=&a; //指针p获取变量a的地址 printf("%d",*p); //输出指针p所指向的内存中的值 getchar();getchar(); return 0; } 运行结果是: 10 这里 printf 语句里面*p 中的*号叫做间接运算符,作用是取得指针 p 所指向的内存中的 值。在 C 语言中*号有三个用途,分别是: 1. 乘号,用做乘法运算,例如 5*6。 2. 申明一个指针,在定义指针变量时使用,例如 int *p;。 3. 间接运算符,取得指针所指向的内存中的值,例如 printf("%d",*p);。 到目前为止,你可能还是觉得指针没啥子实际作用,好好的变量 a 想输出是的话直接 printf("%d",a); 不完了,没事搞个什么指针啊,多此一举。嗯,到目前为止貌似是这样的 O(∩_∩)O 哈哈~~不要着急,真枪实弹地来了。 回想一下,我们想在程序中存储一个整数 10,除了使用 int a;这种方式在内存中申请一 块区域来存储,还有另外一种动态存储方法。 malloc(4); malloc 函数的作用就是从内存中申请分配指定字节大小的内存空间。上面这行代码就申 请了 4 个字节。如果你不知道 int 类型是 4 个字节的,还可以使用 sizeof(int)获取 int 类型所 占用的字节数,如下: malloc(sizeof(int)); 第 2 章 栈、队列、链表 47 现在你已经成功地从内存中申请了 4 个字节的空间来准备存放一个整数,可是如何来 对这个空间进行操作呢?这里我们就需要用一个指针来指向这个空间,即存储这个空间的 首地址。 int *p; p=(int *)malloc(sizeof(int)); 需要注意,malloc 函数的返回类型是 void * 类型。void * 表示未确定类型的指针。在 C 和 C++中,void * 类型可以强制转换为任何其他类型的指针。上面代码中我们将其强制转化 为整型指针,以便告诉计算机这里的 4 个字节作为一个整体用来存放整数。还记得我们之前 遗留了一个问题:指针就是用来存储内存地址的,为什么要分不同类型的指针呢?因为指针 变量存储的是一个内存空间的首地址(第一个字节的地址),但是这个空间占用了多少个字 节,用来存储什么类型的数,则是由指针的类型来标明的。这样系统才知道应该取多少个连 续内存作为一个数据。 OK,现在我们可以通过指针 p 对刚才申请的 4 个字节的空间进行操作了,例如我们向 这个空间中存入整数 10,如下: *p=10; 完整代码如下,注意当在程序中使用 malloc 函数时需要用到 stdlib.h 头文件。 #include #include int main() { int *p; //定义一个指针p p=(int *)malloc(sizeof(int)); //指针p获取动态分配的内存空间地址 *p=10; //向指针p所指向的内存空间中存入10 printf("%d",*p); //输出指针p所指向的内存中的值 getchar();getchar(); return 0; } 运行结果是: 10 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 48 到这里你可能要问:为什么要用这么复杂的办法来存储数据呢?因为之前的方法,我们 必须预先准确地知道所需变量的个数,也就是说我们必须定义出所有的变量。比如我们定义 了 100 个整型变量,那么程序就只能存储 100 个整数,如果现在的实际情况是需要存储 101 个,那必须修改程序才可以。如果有一天你写的软件已经发布或者交付使用,却发现要存储 1000 个数才行,那就不得不再次修改程序,重新编译程序,发布一个新版本来代替原来的。 而有了 malloc 函数我们便可以在程序运行的过程中根据实际情况来申请空间。 啰嗦了半天,总算介绍完了什么是指针以及如何动态申请空间。注意,本节接下来的代 码对于还没有理解指针的朋友来说可能不太容易,不要紧,如果你痛恨指针,大可直接跳过 下面的内容直接进入下一节。下一节中我将介绍链表的另外一种实现方式——数组模拟链表。 首先我们来看一下,链表中的每一个结点应该如何存储。 每一个结点都由两个部分组成。左边的部分用来存放具体的数值,那么用一个整型变量 就可以;右边的部分需要存储下一个结点的地址,可以用指针来实现(也称为后继指针)。 这里我们定义一个结构体类型来存储这个结点,如下。 struct node { int data; struct node *next; }; 上面代码中,我们定义了一个叫做 node 的结构体类型,这个结构体类型有两个成员。 第一个成员是整型 data,用来存储具体的数值;第二个成员是一个指针,用来存储下一个结 点的地址。因为下一个结点的类型也是 struct node,所以这个指针的类型也必须是 struct node * 类型的指针。 如何建立链表呢?首先我们需要一个头指针 head 指向链表的最开始。当链表还没有建 立的时候头指针 head 为空(也可以理解为指向空结点)。 struct node *head; head = NULL;//头指针初始为空 第 2 章 栈、队列、链表 49 现在我们来创建第一个结点,并用临时指针 p 指向这个结点。 struct node *p; //动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点 p=(struct node *)malloc(sizeof(struct node)); 接下来分别设置新创建的这个结点的左半部分和右半部分。 scanf("%d",&a); p->data=a;//将数据存储到当前结点的data域中 p->next=NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空 上面的代码中我们发现了一个很奇怪的符号“->” 。->叫做结构体指针运算符,也是用 来访问结构体内部成员的。因为此处 p 是一个指针,所以不能使用.号访问内部成员,而要 使用->。 下面来设置头指针并设置新创建结点的*next 指向空。头指针的作用是方便以后从头遍 历整个链表。 if(head==NULL) head=p;//如果这是第一个创建的结点,则将头指针指向这个结点 else q->next=p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点 如果这是第一个创建的结点,则将头指针指向这个结点。 如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点。 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 50 最后要将指针 q 也指向当前结点,因为待会儿临时指针 p 将会指向新创建的结点。 q=p;//指针q也指向当前结点 完整代码如下。 #include #include //这里创建一个结构体用来表示链表的结点类型 struct node { int data; struct node *next; }; int main() { struct node *head,*p,*q,*t; int i,n,a; scanf("%d",&n); head = NULL;//头指针初始为空 for(i=1;i<=n;i++)//循环读入n个数 { scanf("%d",&a); //动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点 p=(struct node *)malloc(sizeof(struct node)); p->data=a;//将数据存储到当前结点的data域中 p->next=NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空 if(head==NULL) head=p;//如果这是第一个创建的结点,则将头指针指向这个结点 else q->next=p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点 q=p;//指针q也指向当前结点 } //输出链表中的所有数 t=head; while(t!=NULL) { 第 2 章 栈、队列、链表 51 printf("%d ",t->data); t=t->next;//继续下一个结点 } getchar();getchar(); return 0; } 需要说明的一点是:上面这段代码没有释放动态申请的空间,虽然没有错误,但是这样 会很不安全,有兴趣的朋友可以去了解一下 free 命令。 可以输入以下数据进行验证。 9 2 3 5 8 9 10 18 26 32 运行结果是: 2 3 5 8 9 10 18 26 32 接下来需要往链表中插入 6,操作如下。 首先用一个临时指针 t 从链表的头部开始遍历。 t=head;//从链表头部开始遍历 等到指针 t 的下一个结点的值比 6 大的时候,将 6 插入到中间。即 t->next->data 大于 6 时进行插入,代码如下。 scanf("%d",&a);//读入待插入的数 while(t!=NULL)//当没有到达链表尾部的时候循环 { if(t->next->data > a)//如果当前结点下一个结点的值大于待插入数,将数插入到中间 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 52 { p=(struct node *)malloc(sizeof(struct node));//动态申请一个空间,用来 存放新增结点 p->data=a; p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点 t->next=p;//当前结点的后继指针指向新增结点 break;//插入完毕退出循环 } t=t->next;//继续下一个结点 } 完整代码如下。 #include #include //这里创建一个结构体用来表示链表的结点类型 struct node { int data; struct node *next; }; int main() { struct node *head,*p,*q,*t; int i,n,a; scanf("%d",&n); head = NULL;//头指针初始为空 for(i=1;i<=n;i++)//循环读入n个数 { scanf("%d",&a); //动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点 p=(struct node *)malloc(sizeof(struct node)); p->data=a;//将数据存储到当前结点的data域中 p->next=NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空 if(head==NULL) head=p;//如果这是第一个创建的结点,则将头指针指向这个结点 else q->next=p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点 第 2 章 栈、队列、链表 53 q=p;//指针q也指向当前结点 } scanf("%d",&a);//读入待插入的数 t=head;//从链表头部开始遍历 while(t!=NULL)//当没有到达链表尾部的时候循环 { if(t->next->data > a)//如果当前结点下一个结点的值大于待插入数,将数插入到中间 { p=(struct node *)malloc(sizeof(struct node));//动态申请一个空间, 用来存放新增结点 p->data=a; p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点 t->next=p;//当前结点的后继指针指向新增结点 break;//插入完毕退出循环 } t=t->next;//继续下一个结点 } //输出链表中的所有数 t=head; while(t!=NULL) { printf("%d ",t->data); t=t->next;//继续下一个结点 } getchar();getchar(); return 0; } 可以输入以下数据进行验证。 9 2 3 5 8 9 10 18 26 32 6 运行结果是: 2 3 5 6 8 9 10 18 26 32 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 54 第 5 节 模拟链表 如果你觉得上一节的代码简直是天书,或者你压根就很讨厌指针这些东西,没关系!链 表还有另外一种使用数组来实现的方式,叫做模拟链表,我们一起来看看。 链表中的每一个结点只有两个部分。我们可以用一个数组 data 来存储每序列中的每一个 数。那每一个数右边的数是谁,这一点该怎么解决呢?上一节中是使用指针来解决的,这里 我们只需再用一个数组 right来存放序列中每一个数右边的数是谁就可以了,具体怎么做呢? 上图的两个数组中,第一个整型数组 data 是用来存放序列中具体数字的,另外一个整型 数组 right 是用来存放当前序列中每一个元素右边的元素在数组 data 中位置的。例如 right[1] 的值为 2,就表示当前序列中 1 号元素右边的元素存放在 data[2]中;如果是 0,例如 right[9] 的值为 0,就表示当前序列中 9 号元素的右边没有元素。 现在需要在 8 前面插入一个 6,只需 将 6 直接存放在数组 data 的末尾即 data[10]=6。接下 来只需要将right[3]改为10,表示新序列中3号元素右边的元素存放在data[10]中。再将right[10] 改为 4,表示新序列中 10 号元素右边的元素存放在 data[4]中。这样我们通过 right 数组就可以 从头到尾遍历整个序列了(序列的每个元素的值存放在对应的数组 data 中),如下。 完整的代码实现如下。 #include int main() { int data[101],right[101]; 第 2 章 栈、队列、链表 55 int i,n,t,len; //读入已有的数 scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&data[i]); len=n; //初始化数组right for(i=1;i<=n;i++) { if(i!=n) right[i]=i+1; else right[i]=0; } //直接在数组data的末尾增加一个数 len++; scanf("%d",&data[len]); //从链表的头部开始遍历 t=1; while(t!=0) { if(data[right[t]]>data[len])//如果当前结点下一个结点的值大于待插入数,将 数插入到中间 { right[len]=right[t];//新插入数的下一个结点标号等于当前结点的下一个结 点编号 right[t]=len;//当前结点的下一个结点编号就是新插入数的编号 break;//插入完成跳出循环 } t=right[t]; } //输出链表中所有的数 t=1; while(t!=0) { printf("%d ",data[t]); t=right[t]; } 混混藏书阁:http://book-life.blog.163.com 啊哈!算法 56 getchar(); getchar(); return 0; } 可以输入以下数据进行验证。 9 2 3 5 8 9 10 18 26 32 6 运行结果是: 2 3 5 6 8 9 10 18 26 32 使用模拟链表也可以实现双向链表和循环链表,大家可以自己来试一试。
还剩249页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 1 人已下载

下载pdf

pdf贡献者

xd72

贡献于2016-01-18

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf