データ構造-単一サイクルチェーンテーブルの

循環チェーンテーブル:循環チェーンテーブルは、最初と最後に接続されたチェーンテーブルです.単一チェーンテーブルの最後のノードのポインタドメインをNULLからテーブルヘッダノードを指すように変更すると,単一チェーン形式のループチェーンテーブルが得られ,ループ単一チェーンテーブルと呼ばれる.同様に、多重チェーンのループチェーンテーブルも使用できます.

//     
typedef struct Node {
 int data;
 struct Node *next;
}Node,*LinkList;

	//        :
    LinkList *InitCLinkList(LinkList *CL)//CL                       
	{
 		*CL = (Node *)malloc(sizeof(Node));//     
 		(*CL)->next = *CL;//         CL
 		return CL;
	}

//        ，                 
void CreateFromTail(LinkList CL)//        
{
 Node *s, *rear;
 int i;
 rear = (Node *)CL;
 int flag = 1;
 while (flag)
 {
  scanf("%d", &i);
  if (i != -1)
  {
   s = (Node *)malloc(sizeof(Node));
   s->data = i;
   rear->next = s;
   rear = s;
  }
  else
  {
   flag = 0;
   
  }
 }
 rear->next = CL;
}

//          ，          :O(n)
LinkList merge_1(LinkList LA, LinkList LB)
{
 Node *p, *q;
 p = LA;
 q = LB;
 while (p->next != LA)
 {
  p = p->next;
 }
 while (q->next != LB)
 {
  q = q->next;
 }
 q->next = LA;
 p->next = LB->next;
 free(LB);
 return LA;
}

//           ，          ：O(1)
LinkList merge_2(LinkList LC, LinkList LD)
{
 Node *p;
 p = LC->next;
 LC->next = LD->next->next;
 free(LD->next);
 LD->next = p;
 return LD; 
}

//       
void print(LinkList CL)
{
 Node *p;
 p = CL->next;
 printf("          :");
 while (p!=CL)
 {
  printf("%5d", p->data);
  p = p->next;
 }
 printf("
");
}

//  
int main()
{
 LinkList CL;
 InitCLinkList(&CL);
 printf("     ，  -1  :
");
 CreateFromTail(CL);
 print(CL);
 system("CLS");
 printf("    A   ，  -1  :
");
 LinkList LA;
 InitCLinkList(&LA);
 CreateFromTail(LA);
 print(LA);
 printf("    B   ，  -1  :
");
 LinkList LB;
 InitCLinkList(&LB);
 CreateFromTail(LB);
 print(LB);
 merge_1(LA, LB);
 print(LA);
 printf("merge_1         ：O(n)");
 //system("CLS");
 printf("
    C   ，  -1  :
");
 LinkList LC;
 InitCLinkList(&LC);
 CreateFromTail(LC);
 print(LC);
 printf("    D   ，  -1  :
");
 LinkList LD;
 InitCLinkList(&LD);
 CreateFromTail(LD);
 print(LD);
 merge_2(LC, LD);
 print(LD);
    return 0;
}