4-4-4.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include  <stdio.h>
#include <malloc.h>
#include <conio.h>
#define N 100
typedef struct node {
int data;
struct node * link;
} NODE;
NODE *s[N];
int i, j, n, t;
NODE *q,*p,*x,*y,*top;

main(){
printf("Enter number of parts.");
scanf("%d",&n);
printf("\nn=%d\n",n);
for(i = 0 ;i < n ;i++ ) s[i] = NULL;
printf("Enter pairs.\n");
while( scanf("%d,%d",&i,&j) ==2 ) { /*输入相连部件对，生成相连部件结点链表*/
p = (NODE*) malloc(sizeof(NODE));
p->data = j; p->link = s[i]; s[i] = p;
p = (NODE*) malloc(sizeof(NODE));
p->data = i; p->link = s[j]; s[j] = p;
}
/*下面的语句段原题没有,是用于打印邻接表状况.加上此段能更好理解程序.
但由于程序本身的设计缺陷,要选用一些比较特殊的测试数据才能得到正确结果.
如:n=8,输入关联数据组为:
0,5
5,6
6,7
1,3
2,4
q 用于退出输入数据组.
上面的数据组能输出正确结果.
*/
////////////////////////
for(i=0;i<n;i++){
top=s[i];
printf("s[%d]",i);
while(top!=NULL){
printf("-%d-",top->data);
top=top->link;
}
printf("\n");
}
/////////////////////////
printf("开始处理....\n");
for (i = 0 ;i < n ;i++ ) /*顺序处理各链表*/
for (top = s[i], s[i] = NULL;top != NULL;) {
/*将第 i 链表移入 top 工作链表，并顺序处理工作链表的各结点 */
q = top;top = top->link;
if (s[j = q->data] != NULL) {/*将j链表也移入工作链表*/
for(p=s[j];p->link != NULL; p = p->link);
p->link = top; top = s[j]; s[j] = NULL;
}
/*在重新生成的第i链表中寻找当前结点的插入点*/
for ( y = s[i] ;y != NULL && y->data < q->data ; x = y, y = y->link);
if (y != NULL && y->data == q->data )
free(q);/*因重新生成的第i链表已有当前结点，当前结点删除*/
else {/*当前结点插入新生成的第i链表*/
q->link = y;
if (y == s[i])s[i]=q;
else x->link = q;
}
}
printf("输出结果:\n");
for(i = 0 ;i < n; i++) { /*输出结果*/
if (s[i] == NULL)continue;
for( p = s[i];p != NULL;){
printf("\t%d",p->data) ;
q = p->link; free(p); p = q;
}
printf("\n");
}
}