# Data structure -- decomposing a single chain table with a leading node into two single chain tables

1. Problem description

• The design algorithm decomposes the single chain table L1 of a leading node into two chain tables L2 and L3 with the same structure, in which the node of L2 table is the node whose median value is less than zero in L1 table, and the node of L3 table is the node whose median value is greater than zero in L1 table (the element in L1 is non-zero integer, so L2 and L3 tables are required to use the node of L1 table).

2. Topic analysis

• The head node of the L2 table uses the head node of the original L1 table to apply for a new head node for the L3 table. Starting from the first node of L1 table, take each node p in turn, and judge whether the value of node p is less than 0. Using the forward interpolation method, insert the node less than 0 into L1 table, and the node greater than or equal to 0 into L3 table.
```// Linked list decomposition
{
LNode *p;
p = L1->next;      // p is the working pointer

L2 = L1;
L2->next = NULL;   // L2 table initialization

L3 = new LNode;   // Apply node space for L3
L3->next = NULL;    // L3 initialized to empty table

while (p != NULL)
{
LNode *r;
r = p->next;      // The successor of temporary p
if (p->data < 0)
{
p->next = L2->next;
L2->next = p;       // Link nodes less than 0 into L2 table, forward interpolation
}
else if (p->data > 0)
{
p->next = L3->next;
L3->next = p;
}           // Chain nodes greater than or equal to 0 into table C, forward interpolation

p = r;   // p points to a new pending node
}
}```

3. Code implementation

• main.cpp
```#include <iostream>

using namespace std;

typedef struct LNode
{
int data;
struct LNode *next;

{
L = new LNode;
L->next = NULL;
return 1;
}

{
LNode *p;
p = L->next;

while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

// Establishing chain list by tail insertion
{
L = new LNode;
L->next = NULL;
LNode *r;
r = L;
for (int i = 0; i < n; i++)
{
printf("Please enter the link list No.%d Values of elements:", i + 1);
LNode *s;
s = new LNode;
scanf("%d", &s->data);
s->next = NULL;
r->next = s;
r = s;
}
}

{
LNode *p;
p = L1->next;      // p is the working pointer

L2 = L1;
L2->next = NULL;   // L2 table initialization

L3 = new LNode;   // Apply node space for L3
L3->next = NULL;    // L3 initialized to empty table

while (p != NULL)
{
LNode *r;
r = p->next;      // The successor of temporary p
if (p->data < 0)
{
p->next = L2->next;
L2->next = p;       // Link nodes less than 0 into L2 table, forward interpolation
}
else if (p->data > 0)
{
p->next = L3->next;
L3->next = p;
}           // Chain nodes greater than or equal to 0 into table C, forward interpolation

p = r;   // p points to a new pending node
}
}

int main()
{

if (InitList(L1))
{
printf("L1 Initialization successful!\n");
}
else
{
printf("L1 initialization failed!\n");
}

int n1;
scanf("%d", &n1);
CreateList(L1, n1);
TraveList(L1);

DisCompose(L1, L2, L3);
printf("The list is broken down into L2,L3:\n");
printf("L2: ");
TraveList(L2);
printf("L3: ");
TraveList(L3);

system("pause");

return 0;
}```
• Operation result Keywords: less

Added by etones on Thu, 31 Oct 2019 22:15:46 +0200