資料結構—帶頭結點單循環連結清單的合并

單循環連結清單的合并

• 設兩個單循環連結清單A和B（都帶頭結點，設A和B都非空），合并A和B的思路是:
• 将A最後一個結點的指針域指向B的第一個結點（即指向頭結點後的那個結點，首元結點），然後将B的最後一個元素的指針域指向A的頭結點，釋放B的頭結點。

• 算法：
  • 1.擷取A的最後一個結點，設為p1;
  • 2.擷取B的最後一個結點，設為p2;
  • 3.令p1的指針域指向B的第一個結點，p1->next=B(頭)->next；
  • 4.令p2的指針域指向A的頭結點，p2->next=A(頭)。

void Combine(LinkList L1, LinkList L2) 
{
	LNode *p1;
	LNode *p2;
	p1 = L1->next;
	p2 = L2->next;
	LNode *s1;
	LNode *s2;
	
	while (p1 != L1) 
	{
		if (p1->next == L1) 
		{
			s1 = p1;    // s1指向表L1的最後一個結點 
			break;
		}
		p1 = p1->next;    // 指針後移 
	}
	while (p2 != L2) 
	{
		if (p2->next == L2) 
		{
			s2 = p2;//s2指向表L2的最後一個結點 
			break;
		}
		p2 = p2->next;//指針後移 
	}
	
	s1->next = L2->next;   // L1尾部接到L2首元結點
	delete(L2);  // 釋放L2頭結點
	s2->next = L1;   // L2尾部接到L1頭結點
}
           

代碼實作

• main.cpp

#include<iostream>

using namespace std;

typedef struct LNode 
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

// 初始化 
int InitList(LinkList &L) 
{
	L = new LNode;
	L->next = L;
	return 1;
}

int ListLength(LinkList L) 
{
	int length = 0;
	LNode *p;
	p = L->next;
	
	while (p != L) 
	{
		p = p->next;
		length++;
	}

	return length;
}

void TraveList(LinkList L) 
{
	LNode *p;
	p = L->next;
	while (p != L) 
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}


// 尾插法建立單循環連結清單
void CreateList(LinkList &L, int n)
{
	L = new LNode;
	L->next = L;
	LNode *r;
	r = L;

	printf("請輸傳入連結表元素值:\n");
	for (int i = 0; i < n; i++)
	{
		printf("請輸入第%d個元素的值:", i + 1);
		LNode *p;
		p = new LNode;
		scanf("%d", &p->data);
		p->next = L;
		r->next = p;
		r = p;
	}
}

void Combine(LinkList L1, LinkList L2) 
{
	LNode *p1;
	LNode *p2;
	p1 = L1->next;
	p2 = L2->next;
	LNode *s1;
	LNode *s2;
	
	while (p1 != L1) 
	{
		if (p1->next == L1) 
		{
			s1 = p1;    // s1指向表L1的最後一個結點 
			break;
		}
		p1 = p1->next;    // 指針後移 
	}
	while (p2 != L2) 
	{
		if (p2->next == L2) 
		{
			s2 = p2;//s2指向表L2的最後一個結點 
			break;
		}
		p2 = p2->next;//指針後移 
	}
	
	s1->next = L2->next;   // L1尾部接到L2首元結點
	delete(L2);  // 釋放L2頭結點
	s2->next = L1;   // L2尾部接到L1頭結點
}

int main() 
{
	LinkList A;    // 連結清單A 
	LinkList B;   // 連結清單B 

	if (InitList(A)) 
	{
		printf("連結清單A初始化成功!\n");
	}
	else 
	{
		printf("連結清單A初始化失敗!\n");
	}

	if (InitList(B)) 
	{
		printf("連結清單B初始化成功!\n");
	}
	else 
	{
		printf("連結清單B初始化失敗!\n");
	}

	printf("請輸傳入連結表A的長度:");
	int n1;
	scanf("%d", &n1);
	CreateList(A, n1);
	printf("周遊連結清單A:\n");
	TraveList(A);

	printf("請輸傳入連結表B的長度:");
	int n2;
	scanf("%d", &n2);
	CreateList(B, n2);
	printf("周遊連結清單B:\n");
	TraveList(B);

	Combine(A, B);
	printf("合并後的連結清單:\n");
	TraveList(A);
	printf("合并後連結清單長度是:%d\n", ListLength(A));

	system("pause");

	return 0;
}
           

• 運作結果