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

今天又给讲了一道题，而且这道题就是上次我说过的那个同色珠子用双向链表存储的问题。所以可以再次看出我们程序员考试的题大都离不开链表和指针，这里指针当然就是最重要的了，因为链表也是指针构成的啊，一定要对指针熟悉才可以。下面请大家看题：

阅读下列程序说明和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联系我，我一定会尽力的帮忙，因为我们大家都是为考程序员而努力的人。我相信我们的努力一定不会白白浪费的，努力~！奋斗~~~！

本文地址：http://com.8s8s.com/it/it29551.htm