# Data Structure Linear Table Application (C++)

1. Merge linear tables (A∪B, order not required)

① Calculate the lengths of A and B

②Starting from the first data element in LB, loop n times to perform the following operations:
Find the i (1≤i≤n) data element from LB and assign it to e;
Find element e in LA, if it does not exist, insert e at the end of table LA.

```void MergeList(List & amp; LA, List LB)
{ // Insert all data elements in the linear table LB but not in LA into LA
m = ListLength(LA);
n = ListLength(LB); // Find the length of the linear list for(i=l;i<=n;i ++ )
while (n--)
{
GetElem(LB, i, e); // Get the i-th data element in LB and assign it to e
if (!LocateElem(LA, e)) // LA does not have the same data element as e
ListInsert(LA, + + m, e); // Insert e at the end of LA
}
}```

Table length LA=m LB=n loop execution n times

Sequence table: the value has nothing to do with the insertion time and the table length, the lookup is proportional to the table length m, and the algorithm complexity is O(mxn)

Linked list: The time to get the value is proportional to the length n of the table, the insertion is proportional to the lookup and the length m of the table, assuming that m is greater than n, the algorithm complexity is O(mxn)

(A∩B algorithm is similar, the order of element output is in the order of appearance in set A)

```void MergeList(LinkList & amp; LA, LinkList LB)
{ // Delete all data elements in the linear table LA but not in LB
int m,n,e;
m = ListLength(LA);
n = ListLength(LB);
int i = 1;
while (m--)
{
GetElem(LA, i, e); // Get the i-th data element in LA and assign it to e
if (!LocateElem(LB, e)) // The same data element as e does not exist in LB
ListDelete(LA, i); // delete the element
else i ++ ;
}
}
```

2. Ordered list merge

1) Sequentially ordered list merge

Create an empty table LC, compare LA and LB and extract elements to the end of LC until one of LA and LB is empty. Compare the remaining elements to insert LC.

① Create an empty table LC with a table length of m + n

② The pointer pc is initialized to point to the first element of LC

③ The pointers pa and pb are initialized, pointing to the first element of LA and LB respectively

④ When the pointers pa and pb have not reached the end of the table, compare the element values pointed to by the two in turn, and pick the node with a small element value and insert it into the LC at the end

⑤If pb has reached the end of LB table, insert the remaining elements of LA into the end of LC in sequence

⑥If pa has reached the end of the LA table, insert the remaining elements of LB into the end of LC in sequence

```void MergeList_Sq(SqList LA, SqList LB, SqList & LC)
{
pa = LA.elem;
pb = LB.elem; // The initial values of the pointers pa and pb point to the first elements of the two tables respectively
LC.length = LA.length + LB.length; // The length of the new table is the sum of the lengths of the two tables to be merged
LC.elem = new ElemType[LC.length]; // allocate an array space for the merged new table
pc = LC.elem; // pointer pc points to the first element of the new list
pa_last = LA.elem + LA.length - 1; // The pointer pa_last points to the last element of the LA table
pb_last = LB.elem + LB.length - 1; // The pointer pb_last points to the last element of the LB table
while (pa <= pa_last & &pb <= pb_last)
{
// Both tables are non-empty
if (*pa <= *pb)
*pc + + = *pa + + ;
// "Pick up" the node with the smaller value in the two tables in turn
else
*pc + + = *pb + + ;
}
while (pa <= pa_last)
*pc + + = *pa + + ; // LB table has reached the end of the table, add the remaining elements in LA to LC
while (pb <= pb_last)
*pc + + = *pb + + ; // LA table has reached the end of the list, add the remaining elements in LB to LC
} // MergeList_Sq```

The time complexity of the algorithm is: O(ListLength(La) + ListLength(Lb))
The space complexity of the algorithm is: O(ListLength(La) + ListLength(Lb))
*Using the linked list to achieve the above operations does not need to open up new storage space, which can minimize the space complexity

2) Chained ordered list merge

① The pointers pa and pb are initialized, pointing to the first node of LA and LB respectively

②The value of the LC node is the LA head node

③The pc pointer is initialized to point to the LC head node

④ When the pointers pa and pb have not reached the end of the table, compare the element values pointed to by the two in turn, and pick the node with a small element value and insert it into the LC at the end

⑤ Insert the remaining segments of the non-empty table into the node pointed to by pc

⑥ Release the LB head node

```void MergeList_ L(LinkList & amp;la, LinkList & amp;Lb, LinkList & amp;Lc)
{
pa = La->next;
pb = Lb->next;
pc = Lc = La;
// Use the head node of La as the head node of Lc
while (pa & amp; & amp; pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; // insert remaining segment
delete Lb;
// Release the head node of Lb
}```

The time complexity of the algorithm is: O(ListLength(La) + ListLength(Lb))
The space complexity of the algorithm is: O(1)

3. Polynomial operations

Use the array p to represent: each component p[i] in the array represents the coefficient pi of each item of the polynomial, and the subscript i of the array component corresponds to
The index of the item. The number of nonzero components in the array is the number of terms in the polynomial.

Two polynomial operations:

● create a new array c
● Traverse and compare each item of a and b from the beginning
The exponents are the same, and the corresponding coefficients are added. If the sum is not zero, a new item is added to c
If the exponents are not the same, the item with the smaller exponent is copied to c
●When a polynomial has been traversed, copy the other remaining item to c in sequence
*There are problems in the sequential storage structure: the storage space allocation is not flexible, and the space complexity of the operation is high

Chain storage structure

```typedef struct PNode
{
float coef; // coefficient
int expn;// exponent
struct PNode *next; // pointer field
} PNode, *Polynomial;
```

Linked list – polynomial creation:

The method of creating a polynomial is similar to that of a linked list, the difference is that the polynomial linked list is an ordered list, and the position of each item can only be determined after comparison. First initialize an empty linked list to represent polynomials, and then input each item one by one, and by comparison, find the first item that is greater than the index of the input item, and insert the input item in front of this item,< /strong>In this way, the order of the polynomial linked list can be guaranteed.

1. Create an empty linked list with only the head node.
2. According to the number n of polynomial items, loop n times to perform the following operations:
① Generate a new node *s;
②Enter the coefficient and exponent of the current item of the polynomial and assign it to the data field of the new node *s;
③ Set a precursor pointer pre, which is used to point to the predecessor of the first node to be found that is greater than the index of the input item, and pre initially points to the head node;
④ The pointer q is initialized, pointing to the head node;
⑤ Loop down and compare the value in the current node in the linked list with the index of the input item one by one, and find the first node *q whose value is greater than the index of the input item;
⑥ Insert the input item node *s between *q and its predecessor node pre.

```void CreatePolyn(Polynomial & P, int n)
{
// Input the coefficients and exponents of m items, and create an ordered linked list P representing polynomials
P = new PNode;
P->next = NULL;
// First create a singly linked list with the leading node
for (i = 1; i <= n; + + i)
{
// Enter n non-zero items in sequence
s = new PNode;
// generate new node
cin >> s->coef >> s->expn;
// input coefficient and exponent
pre = P;
// pre is used to save the predecessor of q, the initial value is the head node
q = P->next;
// q initialization, pointing to the head node
while (q & amp; & amp; q->expn < s->expn)
{
// Find the first item *q that is greater than the index of the input item
pre = q;
q = q->next;
s->next = q; // Insert the input item s between q and its predecessor node pre
pre->next = s;
}
}
}```

Time complexity: O(n^2) [loop input n times * loop comparison n times]

Linked list – polynomial addition

① The pointers p1 and p2 are initialized, pointing to the head nodes of Pa and Pb respectively.
②p3 points to the current node of the sum polynomial, and the initial value is the head node of Pa.
③ When the pointers p1 and p2 have not reached the end of the corresponding table, then compare the index values corresponding to the nodes pointed to by p1 and p2 in a loop
(p1->expn and p2->expn) have the following three situations:
When p1>expn= =p2->expn, add the coefficients in the two nodes
If the sum is not zero, modify the coefficient value of the node pointed to by p1 and delete the node pointed to by p2 at the same time
If the sum is zero, delete the nodes pointed to by p1 and p2;
When p1->expnexpn, the node pointed to by p1 should be extracted and inserted into the “sum polynomial” linked list;
When pTxexpn>p2->expn, the node pointed to by p2 should be extracted and inserted into the “sum polynomial” linked list.
④ Insert the remaining segment of the non-empty polynomial after the node pointed to by p3.
⑤Release the head node of Pb.

```void AddPolyn(Polynomial & amp;Pa, Polynomial & amp;Pb) // Polynomial addition: Pa=Pa + Pb, using two polynomial nodes to form a "sum polynomial"
{
p1 = Pa->next;
p2 = Pb->next; // p1 and p2 initially point to the head nodes of Pa and Pb respectively
p3 = Pa; // p3 points to the current node of the sum polynomial, the initial value is Pa
while (p1 & amp; & amp; p2) // both p1 and p2 are not empty
{
if (p1->expn == p2->expn)
{ // indices are equal
sum = p1->coef + p2->coef; // sum saves the coefficient sum of two terms
if (sum != 0) // coefficient sum is not 0
{
// Modify the coefficient value of Pa currently pointing to the node to be the sum of two coefficients
p1->coef = sum;
p3->next = p1;
p3 = p1; // The modified Pa currently points to the node link after p3, and p3 points to p1
p1 = p1->next; // p1 points to the next item
r = p2;
p2 = p2->next;
delete r; // Delete the node that Pb currently points to, and p2 points to the next item
}
else
{
r = p1;
p1 = p1->next;
delete r; // Delete the node that Pa currently points to, and p1 points to the next item
r = p2;
p2 = p2->next;
delete r; // Delete the node that Pb currently points to, and p2 points to the next item
}
}
else if (p1->expn < p2->expn) // Pa is currently pointing to a node whose exponent value is small
{
p3->next = p1; // link p1 after p3
p3 = p1; // p3 points to p1
p1 = p1->next; // p1 points to the next item
}

else // The index value of the node currently pointed to by Pb is small
{ // link p2 after p3
p3->next = p2; // p3 points to p2
p3 = p2; // p2 points to the next item
P2 = p2->next;
}
} // while
p3->next = p1 ? p1 : p2; // insert the remainder of the non-empty polynomial
delete Pb; // release the head node of Pb
}```

Storage structure of library information management system

```struct Book
{
char id[20]; // ISBN
char name[50]; // book title
int price;//Pricing
};

typedef struct
{ // sequence table
Book *elem;
int length;
} SqList;

typedef struct LNode
{ // linked list
Book data;
struct LNode *next;
} LNode, *LinkList;
```
syntaxbug.com © 2021 All Rights Reserved.