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.

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;
        }
    }
}

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
}

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;