Eiecutive Summarv: Nodes in a linked list contain two parts: a data part that st

Question

Eiecutive Summarv: Nodes in a linked list contain two parts: a data part that stores an element of the list; a next part that points to a node containing the successor of this list element or that is null if this is the last element in the list. This suggests that each node can be represented as a struct and the linked list can be represented as an array of structs You are asked to use 2D array to simulate the linked list and use it to construct the STACK with six basic functions: Construction, Empty, Push, Top, pop, and Display 1. Write the construction and five basic functions for the STACK listed below by using 2D array to simulate Linked List approach. Details for each function: Construction: construct an empty 2D array with capacity of 26 to simulate the OS 1. Empty: test if the STACK is empty 2. Push(element): Add a value at the top of the stack in a valid random space of the 2D array 3. Top():Read the value at the top of the stack 4. Pop): Remove the value at the top of the stack 5. Display Displays all the elements in the stack using from Top to Bottom ordering. (Show array index, data value, and next array index) After you finished the six functions, create an empty stack (with capacity-26) and then start push 10 values (1,2,3,4,5,6,7,8,9,10) by Push consecutively. After that, you will have 10 elements in your STACK. Run Displayto print out the STACK. Then perform 3 times of Push of value (20,30,40) on yalid positions, run Display() to print out the list every time you insert a new element. Then perform 3 times of Top0 and Pop(), again, run Display) to print our the list every time you delete an element To visualize the requirement, the code should looks like Push(1) Push(2) Push(3) Push(4) Push(5) Push(6) Push(7) Push(8) Push(9) Push(10) Display Push(20)

Explanation / Answer

#include <bits/stdc++.h>

using namespace std;

// struct node of linked list

struct Node {

    int data;

    Node* right, *down;

};

// returns head pointer of linked list

// constructed from 2D matrix

Node* construct(int arr[][3], int i, int j,

                              int m, int n)

{

    // return if i or j is out of bounds

    if (i > n - 1 || j > m - 1)

        return NULL;

    // create a new node for current i and j

    // and recursively allocate its down and

    // right pointers

    Node* temp = new Node();

    temp->data = arr[i][j];

    temp->right = construct(arr, i, j + 1, m, n);

    temp->down = construct(arr, i + 1, j, m, n);

    return temp;

}

// utility function for displaying

// linked list data

void display(Node* head)

{

    // pointer to move right

    Node* Rp;

    // pointer to move down

    Node* Dp = head;

    // loop till node->down is not NULL

    while (Dp) {

        Rp = Dp;

        // loop till node->right is not NULL

        while (Rp) {

            cout << Rp->data << " ";

            Rp = Rp->right;

        }

        cout << " ";

        Dp = Dp->down;

    }

}

// driver program

int main()

{

    // 2D matrix

    int arr[][3] = {

        { 1, 2, 3 },

        { 4, 5, 6 },

        { 7, 8, 9 }

    };

    int m = 3, n = 3;

    Node* head = construct(arr, 0, 0, m, n);

    display(head);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.