01年下午程序员试题4，求教大侠，非常感谢你们的帮助
再次请教一下各位兄弟，如下的双向循环列表是如何形成的,麻烦各位朋友了
并祝节日快乐
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 -> bpt = q ; //开始时插入的新节点的前趋指针 后继指针，p,q都指向新建节点
else {
p -> bpt -> fpt = q ; //请问接下来的p,q是如何变化的? 这行等价于p=q吗？
q -> fpt = p ; //这下面三行我有点糊涂了
q -> bpt = p->bpt;
p->bpt=q ;
}
}
return p;
}
-----------------------------------------------------------------
全部代码如下：在TC2.0下已调试正确。
(顺便说一下，人邮版那书错误连篇，几乎页页都有错误，老顽童 网站上此题代码也有至少两处错误
，我要考完试，第一件事就是公布勘误大全，呵呵^-^)
试题四
阅读下列程序说明和C代码,将应填入__(n)__处的字句写在答题纸的对应栏内。
[程序4说明]
设一个环上有编号为 0～n-1 的 n 粒不同颜色的珠子(每粒珠子颜色用字母表示, n 粒珠子颜色由输入的
字符串表示)。以环上某两粒珠子间为断点,从断点一方按顺时针方向取走连续同色的珠子,又从断点另一
方按逆时针方向对剩下珠子取走连续同色的珠子,两者之和为该断点可取走珠子的粒数。移动断点,能取走
的珠子数不尽相同。本程序找出可以取走最多的珠子数及断点的位置。程序中用双向链表存储字符串。例
如,编号为0-9的10粒珠子颜色的字符串为“aaabbbadcc",对应链表为: (图可参见老顽童网站
http://oldchild.myrice.com/spks/cxy01x.htm )
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct node { char ch ;
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 -> bpt = q ;
else {
p -> bpt -> fpt = q ;
q -> fpt = p ;
q -> bpt = p->bpt;
p->bpt=q ;
}
}
return p;
}
int count( NODE *start , int maxn ,int step ) /*求可取走珠子粒数*/
{ int color ,c ;
NODE *p ;
color = -1 ; c = 0 ;
for ( p = start ; c <maxn ; p = step > 0 ? p -> fpt:p -> bpt ){
if ( color == -1 ) color = p -> ch ;
else if (color!=p->ch) break ;
c++ ;
}
return c;
}
int find ( char *s ,int *cutpos ) /*寻找取走珠子数最多的断点和粒数*/
{ int i , c , cut , maxc = 0 ,len = strlen(s) ;
NODE *p ;
if ( ( p = building(s) ) == NULL ){ *cutpos = -1 ; return -1 ; }
i = 0 ;
do { c = count( p , len ,1 ) ;
c = c + count(p->bpt,len-c,-1);
if ( c > maxc ) { maxc = c ; cut = i ; }
p=p->fpt;
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 ) ;
}
问题点数：40、回复次数：7Top
1 楼zheliu（吉祥）回复于 2004-05-04 01:26:55 得分 0
对不起，地址有误。应该是http://oldchild.nbc.net.cn/stcxy.htm
谢谢大家Top
2 楼zheliu（吉祥）回复于 2004-05-04 14:27:01 得分 0
请帮帮我。谢谢Top
3 楼cngdzhang（）回复于 2004-05-04 15:12:01 得分 30
p -> bpt -> fpt = q ; //请问接下来的p,q是如何变化的? 这行等价于p=q吗？
q -> fpt = p ; //这下面三行我有点糊涂了
q -> bpt = p->bpt;
p->bpt=q ;
这是插入多于一个节点的情形,q是待插入节点,p是头指针
p -> bpt -> fpt = q ; //q成为p的后继的前驱
q -> fpt = p ; //p成为q的前驱
q -> bpt = p->bpt; //p的后继成为q的后继
p->bpt=q ; //q成为p的后继
这实际上是把新节点插入到了p和 p的原后继之间
画一个图会好理解一些
并不是p=q,这是为了插入节点时能保持前后继的索引,不至于丢失
Top
4 楼lbaby（春天来了...）回复于 2004-05-04 15:30:03 得分 10
看得人迷迷糊糊的
好像写程序的人把程序写的容易看明白一点就对不起这个世界似的
替换一下
typedef struct node
{
char ch ;
struct node *next; /*后继指针*/
struct node *prev; /*前趋指针*/
}NODE ;
/* ... */
NODE *building( char *s )
{
NODE *node = NULL, *new_node ;
while ( *s )
{
new_node = ( NODE * ) malloc( sizeof( NODE ) ) ;
new_node -> ch = *s++ ;
if ( node == NULL )
{
node = new_node -> next
= new_node -> prev
= new_node ;
}
else
{
node -> prev -> next = new_node ; //这种写法是为了改变这个双向链表本身
//的内容，而不是node的内容
//你可以试试 改一下,node = new_node
//看看最后的结果会是什么
new_node -> next = node ;
new_node -> prev = node->prev;
node->prev=new_node ;
}
}
return node;
}
另外,上边的代码没有对内存不足作出准备，如果内存不足的话...
Top
5 楼zheliu（吉祥）回复于 2004-05-04 21:13:34 得分 0
谢谢cngdzhang() 我画过图了，你的文字意思我看懂了，其实质确实是把新节点插入到了p和 p的原后继之间。
但我觉我的分析有误！
我对代码的理解是，在已有一个节点(p指向)时，分配一个新节点(q指向)，发生如下变化：
p -> bpt -> fpt = q ; //q成为p的前驱的后继 即p指向的节点的后继指针指向新分配的节点
q -> fpt = p ; //p成为q的后继
q -> bpt = p->bpt; //p的前驱成为q的前驱 既新分配节点指向原来的老节点(p指向的)
p->bpt=q ; //q成为p的前驱
我的问题现在变成了如果从字面上理解 p -> bpt -> fpt = q的意思是
q成为p的前驱的后继 还是 q成为p的后继的前驱？（虽然我知道后面的肯定是对的)
因为
题目上的规定struct node *fpt ; /*后继指针*/
struct node *bpt ; /*前趋指针*/
To lbaby(阳光下对着天使竖起中指)
您的意思 这种写法是为了改变这个双向链表本身的内容，而不是p的内容，您的意思我不太明白。
现在我发现p->bpt->fpt竟然不是p? 哎，绕死了
Top
6 楼cngdzhang（）回复于 2004-05-04 21:22:17 得分 0
我没有看到你的题目啊
题目上的规定struct node *fpt ; /*后继指针*/
struct node *bpt ; /*前趋指针*/
我的翻译是 *fpt front pointer 向前指针
*bpt back pointer 向后指针
如果你要按题目去理解,那么把我的"前驱"换成"后继","后继"换成"前驱"就好了
都能达到插入节点的目的
Top
7 楼zheliu（吉祥）回复于 2004-06-08 17:05:44 得分 0
非常感谢你们Top
