习题2.5

设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。

实现函数：

void Decompose(LinkList& La, LinkList& Lb, LinkList& Lc)
{

	LNode* pa;
	LNode* ra;

	

	pa = La->next;
	
	
	while (1)
	{
		

		ra = pa->next;
		if (pa->data < 0)
		{
			pa->next = Lb->next;
			Lb->next = pa;
		}
		else
		{
			pa->next = Lc->next;
			Lc->next = pa;
		}
		pa = ra;
		if (pa == NULL) break;
	}
	
}

完整代码：

#include <iostream>
#include <stdlib.h>
using namespace std;

//单链表的存储结构
typedef struct LNode {
	int data;//结点的数据域
	struct LNode* next;//结点的指针域
} LNode, * LinkList;//LinkList为指向结构体LNode的指针类型

void PrintList(LinkList L);
void Decompose(LinkList& La, LinkList& Lb, LinkList& Lc);
LinkList TailInsert(LinkList& L);



//链表初始化，构造一个单链表L
void InitList(LinkList& L) {
	L = new LNode;//生成新结点作为头结点，用头指针L指向头结点
	L->next = NULL;//头结点的指针域置空
}

int main()
{

	cout << "计科2104张子涵 211040100425" << endl;
	LinkList La;
	LinkList Lc;
	LinkList Lb;
	cout << "请键入一个链表La";
	cout << endl;
	TailInsert(La);//创建La
	
	InitList(Lb);
	InitList(Lc);
	
	cout << endl;
	Decompose(La, Lb, Lc);//拆分
	cout << "Lc为：";
	PrintList(Lc);
	cout << endl;
	cout << "Lb为：";
	PrintList(Lb);
	system("pause");
	return 0;
}

void PrintList(LinkList L) {
	LNode* p = L->next;
	while (p) {
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

void Decompose(LinkList& La, LinkList& Lb, LinkList& Lc)
{

	LNode* pa;
	LNode* ra;

	

	pa = La->next;
	
	
	while (1)
	{
		

		ra = pa->next;
		if (pa->data < 0)
		{
			pa->next = Lb->next;
			Lb->next = pa;
		}
		else
		{
			pa->next = Lc->next;
			Lc->next = pa;
		}
		pa = ra;
		if (pa == NULL) break;
	}
	
}

LinkList TailInsert(LinkList& L) {
	InitList(L);
	LNode* s, * r = L;
	int x = 0;
	int mk[100];

	while (1)
	{
		cin >> mk[x];
		s = (LNode*)malloc(sizeof(LNode));
		s->data = mk[x];
		r->next = s;
		r = s;
		if (cin.get() == '\n') break;
		x++;
	}
	r->next = NULL;
	return L;
}