[数据结构]算法设计题--拆分链表

编程 2023-12-06 17:28:12

题目

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

解答

  1. 链表B使用链表A的头结点,链表C申请一个新的头结点。
  2. 对链表A进行遍历的同时进行拆解,可以使用前插法或者后插法。
/*
设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C,其中B表的结点为A表中值小于零的结点,
而C表中的结点为A表中值大于零的结点。(链表A中的元素为非零整数,要求B、C表利用A表的结点。)
*/
#include <iostream>
using namespace std;
typedef struct LNode {
	int data;
	struct LNode *next;
}LNode, *LinkList;

void createList(LinkList &L) {
	L = new LNode;
	L->next = NULL;
	int n;
	cout << "链表的元素个数:" << endl;
	cin >> n;
	cout << "链表的元素:" << endl;
	LinkList p, q = L;
	for (int i = 0; i < n; ++i) {
		p = new LNode;
		cin >> p->data;
		p->next = q->next;
		q->next = p;
		q = p;
	} 
}

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

void splitList(LinkList &La, LinkList &Lb, LinkList &Lc) {
	LinkList pa = La->next;
	Lb = La;
	Lb->next = NULL;
	Lc = new LNode;
	Lc->next = NULL;
	LinkList pb = Lb, pc = Lc, q;
	// 前插法保存链表A中的数据
	while (pa) {
		q = pa->next; // 存p的后继结点
		if (pa->data < 0) {
			pa->next = Lb->next;
			Lb->next = pa;
		} else if (pa->data > 0) {
			pa->next = Lc->next;
			Lc->next = pa;
		}
		pa = q;
	}
}

int main() {
	LinkList La = NULL, Lb = NULL, Lc = NULL;

	cout << "La链表:" << endl;
	createList(La);
	cout << "La链表:" << endl;
	printList(La);

	splitList(La, Lb, Lc);

	cout << "Lb链表:" << endl;
	printList(Lb);
	cout << "Lc链表:" << endl;
	printList(Lc);
	return 0;
}
声明:该文观点仅代表作者本人,必看呐发布平台,仅提供信息存储空间服务。