您所在位置：主题：第34次编程比赛结果（第一题）
eastcowboy [专家分：25370] 发布于 2006-07-16 19:22:00
本题实际上是从内存管理方法得出的一个极简化的问题，忽略了“需要将连续的内存相合并”等诸多因素，主要考查的是程序员编程的严谨程度，少犯或不犯错误。当然也需要考查代码的实际运行效率。
以下是各选手的测试：
[color=0000FF]iAkiak（1楼）[/color]
从代码上看，iAkiak兄对程序的性能做了较多考虑。包括对较小的数采取空间换时间，采用排序和二分查找，通过设置标记减少排序次数。但在Out函数中，无论长度有无剩余，都将该电线拿出，剪掉后再将剩下的放回。虽然题目的叙述是这样的，这里似乎应该变通一下，我的想法是：如果有剩余的话，直接减掉，再把“是否已排序”的标志修改。毕竟插入和删除元素不是vector的强项。
（lower_bound函数模板似乎没有明确说是使用二分查找，只说了是在已排序的数列里找）
正确性测试：得到正确结果。
[color=0000FF]songwei（2楼）[/color]
你的确没有正确的理解题意。这主要体现在Out函数中，题目并没有说借出的就马上还回。所以Out函数最后的In(length);一句应去掉。
另外我想给你一些建议：
1、如果找到合适的电线，它的长度正好等于需要的长度，也就是说借出后该段电线长度为零，则应该把它从链表中删除。虽然不删除也不会出现错误的情况，但是它已经是无用的数据了，不删除会占用内存空间。
2、postion->length=postion->length-length;这一句看起来有些复杂。在C/C++语言中，一般将它写为postion->length -= length;
3、在Out函数中，你将temp_length赋了初始值100，这是不对的。假设有人借走了长为100的电线，又有人还来长为120的电线。现在有人要借长为110的电线，按你的方法，就借不出去了。
4、在End函数中，对链表的释放存在错误。释放链表的空间应该一个一个的释放，像这样：
NODE *p, *q;
p = h;
while( p != NULL )
{
q = p;
p = p->next;
free(q);
}
5、iostream.h头文件已经过时，如果你想学习C++，请使用较新的教材。
正确性测试：由于题意没理解好，所以没有得到正确结果。
[color=0000FF]天国龙（3楼）[/color]
思路是维护一个递增的链表。
你的指针使用得有些混乱，看起来有些像循环链表，但似乎有不是。本题中循环链表的作用可能不大。鉴于你大量的使用到prev和next，可以考虑专门写一些链表操作的函数，这样代码看起来也没那么繁杂，同时可以把注意力集中到更小的范围上，把问题各个击破。参见题目帖中5楼yxs0001的代码。
你的lest指针似乎是用来指向最后一个元素，那么以下循环：
for(p=first; p!=lest; p=p->next) /* ... */
就没有访问到最后一个元素。也就是说，如果链表中有n个元素，则这个循环只能访问前面的n-1个。你的程序中多次出现这样的错误。
正确性测试：出现了意外的死循环。
[color=0000FF]johnywoo（4楼）[/color]
思路也是维护一个递增的链表。
程序的结构有点问题，在In函数中，最后的：
if (iWire==NULL)
{
jWire->next=w;
}
由于iWire和jWire可能未初始化，是一随机值，使用jWire->next可能让程序崩溃。
应该将它移动到else if (wireMan!=NULL)那个条件以内。
正确性测试：程序崩溃。按照以上方法修改后得到正确结果。
[color=0000FF]yxs0001（5楼）[/color]
思路仍然是维护一个递增的链表。但加入了一个max变量，希望增加程序的效率。
我个人感觉是加入后效率没有明显变化，毕竟需要寻找到最后一个的仅仅是少数，为此增加若干判断并不值得。
Find函数的注释似乎不正确……
一点小建议：在构造函数中，将暂时不使用的指针赋值为空。
正确性测试：有错误。原因是在Out函数中max的值没有被正确设置。假设开始时还来一根长为110的电线，然后借走长为104的，则现在max的值为6。正确值为100。
[color=0000FF]hanshuyujifen（6楼）[/color]
在In函数中把新的结点接到了原来链表中的第二个位置，不知道你是有意的还是无意的。
在Out函数中，循环：while(p->next != NULL)将不会访问到链表的最后一个元素。正确的写法是while(p != NULL);
看来你对于链表的两种方式（有头结点、无头结点）有些迷糊。
另：没有释放链表的代码。
正确性测试：有错误。你在寻找“与需要长度最接近的长度”时处理方法不正确。你希望利用每根电线的长度与需要长度的差来判断，并取最大的正值。但实际上应该取最小的正值。
[color=0000FF]szh（7楼）[/color]
思路是维护一个递增的链表。
处理得较好，没有发现问题。
正确性测试：得到正确结果。
[color=0000FF]magicalking（8楼）[/color]
思路也是维护一个递增的链表。
由于函数接口和题目要求有些不一致，做了适当更改。（参见题目帖中，iAkiak在1楼的模式）
代码简单易懂。缺点：对借出后长度为零的电线，没有去掉，以至于排序时反复操作大量的0元素，效率降低。
正确性测试：得到正确结果。
小结：
通过正确性测试的选手有：[color=0000FF]iAkiak（1楼）、szh（7楼）、magicalking（8楼）[/color]
效率测试：
在VS2005的Debug模式下，借出/还回操作共计10000次。iAkiak：约1秒；szh：约1秒；magicalking：30秒后仍无法计算完毕，数据规模缩小到1000后耗时6秒。
在VS2005的Release模式下，借出/还回操作共计50000次。iAkiak：约1秒；szh：约3秒；magicalking：约6秒。
magicalking的代码在Debug模式下表现不佳，原因可能是因为STL函数在Debug模式时没有进行彻底的内联，导致函数调用开销过大。iAkiak虽然也使用STL，但由于多数情况下是利用数组的优化，此问题不明显。
另外magicalking没有删除零元素，导致排序时效率降低，此问题会随着数据规模的增大而越发明显。因此认为magicalking的程序在效率上比前两名选手差。
虽然iAkiak兄的程序的确是效率第一，但我还是想选szh来当这个冠军，借此鼓励一下新人。希望iAkiak老兄不要生气~
[color=FF0000]请szh准备第35次比赛的第一题，并宣布比赛的相关事宜。[/color]
好了，公事办完，下面该检讨了。
最近大约有一个多月，我来论坛的时间比较少。这一事实可能造成了一些朋友的不满，我在此向大家检讨。
虽然马上大四了，事情多了点，但我自问除了考试那段时间外，挤一些时间来上论坛还是可以做到的，但我没有这样做。是我对不起大家。
我以后会尽量到论坛来。但现在时间比较紧，我可能不会像以前那样活跃，希望大家能够理解。
eastcowboy在这里向大家认错了。
以下是各选手的测试：
[color=0000FF]iAkiak（1楼）[/color]
从代码上看，iAkiak兄对程序的性能做了较多考虑。包括对较小的数采取空间换时间，采用排序和二分查找，通过设置标记减少排序次数。但在Out函数中，无论长度有无剩余，都将该电线拿出，剪掉后再将剩下的放回。虽然题目的叙述是这样的，这里似乎应该变通一下，我的想法是：如果有剩余的话，直接减掉，再把“是否已排序”的标志修改。毕竟插入和删除元素不是vector的强项。
（lower_bound函数模板似乎没有明确说是使用二分查找，只说了是在已排序的数列里找）
正确性测试：得到正确结果。
[color=0000FF]songwei（2楼）[/color]
你的确没有正确的理解题意。这主要体现在Out函数中，题目并没有说借出的就马上还回。所以Out函数最后的In(length);一句应去掉。
另外我想给你一些建议：
1、如果找到合适的电线，它的长度正好等于需要的长度，也就是说借出后该段电线长度为零，则应该把它从链表中删除。虽然不删除也不会出现错误的情况，但是它已经是无用的数据了，不删除会占用内存空间。
2、postion->length=postion->length-length;这一句看起来有些复杂。在C/C++语言中，一般将它写为postion->length -= length;
3、在Out函数中，你将temp_length赋了初始值100，这是不对的。假设有人借走了长为100的电线，又有人还来长为120的电线。现在有人要借长为110的电线，按你的方法，就借不出去了。
4、在End函数中，对链表的释放存在错误。释放链表的空间应该一个一个的释放，像这样：
NODE *p, *q;
p = h;
while( p != NULL )
{
q = p;
p = p->next;
free(q);
}
5、iostream.h头文件已经过时，如果你想学习C++，请使用较新的教材。
正确性测试：由于题意没理解好，所以没有得到正确结果。
[color=0000FF]天国龙（3楼）[/color]
思路是维护一个递增的链表。
你的指针使用得有些混乱，看起来有些像循环链表，但似乎有不是。本题中循环链表的作用可能不大。鉴于你大量的使用到prev和next，可以考虑专门写一些链表操作的函数，这样代码看起来也没那么繁杂，同时可以把注意力集中到更小的范围上，把问题各个击破。参见题目帖中5楼yxs0001的代码。
你的lest指针似乎是用来指向最后一个元素，那么以下循环：
for(p=first; p!=lest; p=p->next) /* ... */
就没有访问到最后一个元素。也就是说，如果链表中有n个元素，则这个循环只能访问前面的n-1个。你的程序中多次出现这样的错误。
正确性测试：出现了意外的死循环。
[color=0000FF]johnywoo（4楼）[/color]
思路也是维护一个递增的链表。
程序的结构有点问题，在In函数中，最后的：
if (iWire==NULL)
{
jWire->next=w;
}
由于iWire和jWire可能未初始化，是一随机值，使用jWire->next可能让程序崩溃。
应该将它移动到else if (wireMan!=NULL)那个条件以内。
正确性测试：程序崩溃。按照以上方法修改后得到正确结果。
[color=0000FF]yxs0001（5楼）[/color]
思路仍然是维护一个递增的链表。但加入了一个max变量，希望增加程序的效率。
我个人感觉是加入后效率没有明显变化，毕竟需要寻找到最后一个的仅仅是少数，为此增加若干判断并不值得。
Find函数的注释似乎不正确……
一点小建议：在构造函数中，将暂时不使用的指针赋值为空。
正确性测试：有错误。原因是在Out函数中max的值没有被正确设置。假设开始时还来一根长为110的电线，然后借走长为104的，则现在max的值为6。正确值为100。
[color=0000FF]hanshuyujifen（6楼）[/color]
在In函数中把新的结点接到了原来链表中的第二个位置，不知道你是有意的还是无意的。
在Out函数中，循环：while(p->next != NULL)将不会访问到链表的最后一个元素。正确的写法是while(p != NULL);
看来你对于链表的两种方式（有头结点、无头结点）有些迷糊。
另：没有释放链表的代码。
正确性测试：有错误。你在寻找“与需要长度最接近的长度”时处理方法不正确。你希望利用每根电线的长度与需要长度的差来判断，并取最大的正值。但实际上应该取最小的正值。
[color=0000FF]szh（7楼）[/color]
思路是维护一个递增的链表。
处理得较好，没有发现问题。
正确性测试：得到正确结果。
[color=0000FF]magicalking（8楼）[/color]
思路也是维护一个递增的链表。
由于函数接口和题目要求有些不一致，做了适当更改。（参见题目帖中，iAkiak在1楼的模式）
代码简单易懂。缺点：对借出后长度为零的电线，没有去掉，以至于排序时反复操作大量的0元素，效率降低。
正确性测试：得到正确结果。
小结：
通过正确性测试的选手有：[color=0000FF]iAkiak（1楼）、szh（7楼）、magicalking（8楼）[/color]
效率测试：
在VS2005的Debug模式下，借出/还回操作共计10000次。iAkiak：约1秒；szh：约1秒；magicalking：30秒后仍无法计算完毕，数据规模缩小到1000后耗时6秒。
在VS2005的Release模式下，借出/还回操作共计50000次。iAkiak：约1秒；szh：约3秒；magicalking：约6秒。
magicalking的代码在Debug模式下表现不佳，原因可能是因为STL函数在Debug模式时没有进行彻底的内联，导致函数调用开销过大。iAkiak虽然也使用STL，但由于多数情况下是利用数组的优化，此问题不明显。
另外magicalking没有删除零元素，导致排序时效率降低，此问题会随着数据规模的增大而越发明显。因此认为magicalking的程序在效率上比前两名选手差。
虽然iAkiak兄的程序的确是效率第一，但我还是想选szh来当这个冠军，借此鼓励一下新人。希望iAkiak老兄不要生气~
[color=FF0000]请szh准备第35次比赛的第一题，并宣布比赛的相关事宜。[/color]
好了，公事办完，下面该检讨了。
最近大约有一个多月，我来论坛的时间比较少。这一事实可能造成了一些朋友的不满，我在此向大家检讨。
虽然马上大四了，事情多了点，但我自问除了考试那段时间外，挤一些时间来上论坛还是可以做到的，但我没有这样做。是我对不起大家。
我以后会尽量到论坛来。但现在时间比较紧，我可能不会像以前那样活跃，希望大家能够理解。
eastcowboy在这里向大家认错了。
