已知L为循环单链表的哨兵结点指针,编写把链表从地址为Y的结点处分开,形成两个循环链表的算法
#include <iostream>
using namespace std;
typedef struct node
{
int data;
node* next;
} listNode, *linkList;
linkList createCycList();
void split(linkList, linkList);
void dispCycList(linkList);
int main()
{
linkList a{createCycList()};
linkList b{new listNode};
split(a, b);
dispCycList(a);
dispCycList(b);
return 0;
}
linkList createCycList()
{
listNode* h{new listNode}; // 创建带头节点的循环单链表
h->next = nullptr;
cout << "请输入循环单链表中的元素值(按回车结束): ";
for (linkList t{h}; ; ) {
listNode* s = new listNode;
cin >> s->data;
t->next = s; // 将新创建的节点插入至表尾
t = s;
t->next = h; // 将当前尾节点的指针域指向头节点
if (cin.get() == '\n') {
break;
}
}
return h;
}
void split(linkList a, linkList b)
{
listNode* p{a->next}; // 将指针p指向a的第一个节点(头节点的后一个节点)
listNode* ra{a};
listNode* rb{b};
ra->next = nullptr;
rb->next = nullptr;
for ( ; p != a; p = p->next) {
if (p->data >= 0) { // 若当前节点数据域的值非负
ra->next = p; // 则插入至a中
ra = p;
} else {
rb->next = p;
rb = p;
}
}
ra->next = a;
rb->next = b;
}
void dispCycList(linkList a)
{
for (linkList ra{a->next}; ra != a; ra = ra->next) {
cout << ra->data << " ";
}
cout << endl;
}