【简答题】

试题四
阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内。
[程序4说明]
设一个环上有编号为 0～n-1 的 n 粒不同颜色的珠子(每粒珠子颜色用字母表示, n 粒珠子颜色由输入的字符串表示)。以环上某两粒珠子间为断点,从断点一方按顺时针方向取走连续同色的珠子,又从断点另一方按逆时针方向对剩下珠子取走连续同色的珠子,两者之和为该断点可取走珠子的粒数。移动断点,能取走的珠子数不尽相同。本程序找出可以取走最多的珠子数及断点的位置。程序中用双向链表存储字符串。例如,编号为0-9的10粒珠子颜色的字符串为“aaabbbadcc",对应链表为:
      
若在2号与3号珠子间为断点,共可取走6粒珠子,且为取走的珠子数最多。
[程序4]
#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
}
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
}
　
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 ) ;
}