/*中國系統(tǒng)分析員顧問團(tuán)，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 ) { /*輸入相連部件對，生成相連部件結(jié)點(diǎn)鏈表*/
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;
}
/*下面的語句段原題沒有,是用于打印鄰接表狀況.加上此段能更好理解程序.
但由于程序本身的設(shè)計(jì)缺陷,要選用一些比較特殊的測試數(shù)據(jù)才能得到正確結(jié)果.
如:n=8,輸入關(guān)聯(lián)數(shù)據(jù)組為:
0,5
5,6
6,7
1,3
2,4
q 用于退出輸入數(shù)據(jù)組.
上面的數(shù)據(jù)組能輸出正確結(jié)果.
*/
////////////////////////
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 工作鏈表，并順序處理工作鏈表的各結(jié)點(diǎn) */
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鏈表中尋找當(dāng)前結(jié)點(diǎn)的插入點(diǎn)*/
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鏈表已有當(dāng)前結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)刪除*/
else {/*當(dāng)前結(jié)點(diǎn)插入新生成的第i鏈表*/
q->link = y;
if (y == s[i])s[i]=q;
else x->link = q;
}
}
printf("輸出結(jié)果:\n");
for(i = 0 ;i < n; i++) { /*輸出結(jié)果*/
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");
}
}