1 # include2 struct Slist{ 3 int size; 4 struct sl* head; 5 }; 6 struct sl{ 7 int k; 8 struct sl* next; 9 }; 10 typedef struct Slist Sl; 11 typedef struct sl sl; 12 void init(Sl* m,int k){ 13 sl* p = (sl *)malloc(sizeof(sl)); 14 p->k = k; 15 p->next = NULL; 16 m->head =p; 17 m->size = 1; 18 } 19 20 sl* add(Sl* m,int key ){ 21 sl* p=(sl *)malloc(sizeof(sl)); 22 sl* q = (sl *)malloc(sizeof(sl)); 23 p->k = key; 24 p->next = NULL; 25 q = m->head; 26 while (q->next != NULL) 27 q = q->next; 28 q->next = p; 29 m->size++; 30 return p; 31 } 32 33 void FanZhuan(Sl* m){ //链表反转 34 35 sl* p = m->head; 36 sl* q =NULL; 37 sl* r =NULL; 38 while (p->next!=NULL){ 39 40 q = p->next; 41 p->next = r; 42 r = p; 43 p = q; 44 } 45 q->next = r; 46 m->head = q; 47 } 48 49 void BianLi(Sl* m){ //遍历链表 50 51 sl* a = m->head; 52 printf(" \n"); 53 while (a != NULL){ 54 printf("%d",a->k); 55 a = a->next; 56 } 57 } 58 59 sl* CheckLoop(Sl* m){ //测试是否有环 60 sl* a = m->head; 61 sl* b = m->head; 62 while (b!=NULL){ 63 a = a->next; 64 if (b->next == NULL) 65 return NULL; 66 if (b->next->next == NULL) 67 return NULL; 68 b = b->next->next; 69 if (a == b) 70 return a; 71 } 72 return NULL; 73 } 74 75 int NloopCheck(Sl* f,Sl* n){ //两者均无环，测相交 76 sl* k1 = f->head; 77 sl* k2 = n->head; 78 while (k1->next!=NULL) 79 { 80 k1 = k1->next; 81 } //取得表k1的最后一个节点 82 while (k2 != NULL){ 83 k2 = k2->next; 84 if (k2 == k1) 85 { 86 return 1; 87 } 88 } 89 return 0; 90 } 91 92 void Check(Sl*t1,Sl*t2){ //测试是否相交 93 94 sl* Y1 = CheckLoop(t1); //先测两个表的每个表是否有环 95 sl* Y2 = CheckLoop(t2); 96 // if (Y1 != NULL) 97 // printf("The first have loop!\n"); 98 // if (Y2 != NULL) 99 // printf("The second have loop!"); 100 101 int y1 = (Y1 != NULL);102 int y2 = (Y2 != NULL);103 int y = y1 + y2;104 int yes = 0;105 sl* test = NULL;106 switch (y)107 {108 case 0: //均无环109 printf("\n Two have no loop!");110 yes = NloopCheck(t1, t2);111 break;112 113 case 1: //一个有环，一个没有114 printf("\n One Have loop!");115 yes = 0;116 break;117 118 case 2: //两者都有环119 printf("\n Two have loop!");120 test = t2->head;121 while (1)122 {123 if (test == Y2)124 {125 yes = 1;126 break;127 }128 test = test->next;129 }130 break;131 default:132 break;133 }134 135 if (yes == 1)136 printf("\n Have intersection!");137 else138 printf("\n Don't have intersection!");139 }140 141 void main(){142 Sl* t1 = (Sl*)malloc(sizeof(Sl)); //创建带环链表t1143 t1->size=0;144 t1->head = NULL;145 init(t1,8);146 add(t1, 3);147 add(t1, 2);148 sl* t1Start=add(t1, 1); //loop start!149 add(t1, 0);150 add(t1, 9);151 sl* t2Start=add(t1, 10);152 t2Start->next = t1Start; //Add loop!153 154 Sl* t2 = (Sl*)malloc(sizeof(Sl)); //创建链表t2与t1相交155 t2->size = 0;156 t2->head = NULL;157 init(t2, 8);158 add(t2, 3);159 add(t2, 2);160 sl* w2 = add(t2, 1);161 w2->next = t2Start;162 163 164 Sl* t3 = (Sl*)malloc(sizeof(Sl)); //创建五环链表t3165 t3->size = 0;166 t3->head = NULL;167 init(t3, 8);168 add(t3, 3);169 add(t3, 2);170 sl* w3= add(t3, 1);171 add(t3,7);172 add(t3,27);173 174 Sl* t4 = (Sl*)malloc(sizeof(Sl)); //创建链表t4与t3相交175 t4->size = 0;176 t4->head = NULL;177 init(t4, 8);178 add(t4, 3);179 add(t4, 2);180 sl* w4 = add(t4, 1);181 w4->next = w3;182 183 Sl* t5 = (Sl*)malloc(sizeof(Sl)); //创建链表t5，不与上相交184 t5->size = 0;185 t5->head = NULL;186 init(t5, 8);187 add(t5, 53);188 add(t5, 42);189 printf("\n SingList t1 and t2:");190 Check(t1, t2);191 printf("\n\n SingList t3 and t4:");192 Check(t3, t4);193 printf("\n\n SingList t1 and t3:");194 Check(t3, t1);195 printf("\n\n SingList t3and t5:");196 Check(t5, t3);197 198 199 200 201 system("pause");202 }
执行效果图如下：
