Создание двусвязного списка из 2D-матрицы
Опубликовано: 11 Января, 2022
Учитывая двумерную матрицу, задача состоит в том, чтобы преобразовать ее в двусвязный список с четырьмя указателями: следующий, предыдущий, верхний и нижний, каждый узел этого списка должен быть подключен к его следующему, предыдущему, верхнему и нижнему узлам. .
Примеры:
Вход: 2D-матрица 1 2 3 4 5 6 7 8 9 Выход:
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Approach: The main idea is to construct a new node for every element of the matrix and recursively create it’s up, down, previous and next nodes and change the pointer of previous and up pointers respectively.
Below is the implementation of the above approach:
C++
// C++ programm to construct a Doubly // linked linked list from 2D Matrix #include <iostream> using namespace std; // define dimension of matrix #define dim 3 // struct node of doubly linked // list with four pointer // next, prev, up, down struct Node { int data; Node* next; Node* prev; Node* up; Node* down; }; // function to create a new node Node* createNode( int data) { Node* temp = new Node(); temp->data = data; temp->next = NULL; temp->prev = NULL; temp->up = NULL; temp->down = NULL; return temp; } // function to construct the // doubly linked list Node* constructDoublyListUtil( int mtrx[][dim], int i, int j, Node* curr) { if (i >= dim || j >= dim) { return NULL; } // Create Node with value contain // in matrix at index (i, j) Node* temp = createNode(mtrx[i][j]); // Assign address of curr into // the prev pointer of temp temp->prev = curr; // Assign address of curr into // the up pointer of temp temp->up = curr; // Recursive call for next pointer temp->next = constructDoublyListUtil( mtrx, i, j + 1, temp); // Recursive call for down pointer temp->down = constructDoublyListUtil( mtrx, i + 1, j, temp); // Return newly constructed node // whose all four node connected // at it"s appropriate position return temp; } // Function to construct the doubly linked list Node* constructDoublyList( int mtrx[][dim]) { // function call for construct // the doubly linked list return constructDoublyListUtil( mtrx, 0, 0, NULL); } // function for displaying // doubly linked list data void display(Node* head) { // pointer to move right Node* rPtr; // pointer to move down Node* dPtr = head; // loop till node->down is not NULL while (dPtr) { rPtr = dPtr; // loop till node->right is not NULL while (rPtr) { cout << rPtr->data << " " ; rPtr = rPtr->next; } cout << "
" ; dPtr = dPtr->down; } } // driver code int main() { // initialise matrix int mtrx[dim][dim] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; Node* list = constructDoublyList(mtrx); display(list); return 0; } |
Java
// Java program to construct a Doubly // linked linked list from 2D Matrix import java.util.*; class GFG{ // define dimension of matrix static int dim= 3 ; // struct node of doubly linked // list with four pointer // next, prev, up, down static class Node { int data; Node next; Node prev; Node up; Node down; }; // function to create a new node static Node createNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; temp.prev = null ; temp.up = null ; temp.down = null ; return temp; } // function to construct the // doubly linked list static Node constructDoublyListUtil( int mtrx[][], int i, int j,Node curr) { if (i >= dim || j >= dim) { return null ; } // Create Node with value contain // in matrix at index (i, j) Node temp = createNode(mtrx[i][j]); // Assign address of curr into // the prev pointer of temp temp.prev = curr; // Assign address of curr into // the up pointer of temp temp.up = curr; // Recursive call for next pointer temp.next = constructDoublyListUtil(mtrx, i, j + 1 , temp); // Recursive call for down pointer temp.down= constructDoublyListUtil(mtrx, i + 1 , j, temp); // Return newly constructed node // whose all four node connected // at it"s appropriate position return temp; } // Function to construct the doubly linked list static Node constructDoublyList( int mtrx[][]) { // function call for construct // the doubly linked list return constructDoublyListUtil(mtrx, 0 , 0 , null ); } // function for displaying // doubly linked list data static void display(Node head) { // pointer to move right Node rPtr; // pointer to move down Node dPtr = head; // loop till node.down is not null while (dPtr != null ) { rPtr = dPtr; // loop till node.right is not null while (rPtr!= null ) { System.out.print(rPtr.data+ " " ); rPtr = rPtr.next; } System.out.print( "
" ); dPtr = dPtr.down; } } // driver code public static void main(String args[]) { // initialise matrix int mtrx[][] = { { 1 , 2 , 3 }, { 4 , 5 , 6 }, { 7 , 8 , 9 } }; Node list = constructDoublyList(mtrx); display(list); } } // This code is contributed by AbhiThakur |
Python3
# Python3 programm to construct # a Doubly linked linked list # from 2D Matrix # define dimension of matrix dim = 3 # struct node of doubly linked # list with four pointer # next, prev, up, down class Node: def __init__( self , data): self .data = data self .prev = None self .up = None self .down = None self . next = None # function to create a # new node def createNode(data): temp = Node(data); return temp; # function to construct the # doubly linked list def constructDoublyListUtil(mtrx, i, j, curr): if (i > = dim or j > = dim): return None ; # Create Node with value # contain in matrix at # index (i, j) temp = createNode(mtrx[i][j]); # Assign address of curr into # the prev pointer of temp temp.prev = curr; # Assign address of curr into # the up pointer of temp temp.up = curr; # Recursive call for next # pointer temp. next = constructDoublyListUtil(mtrx, i, j + 1 , temp); # Recursive call for down pointer temp.down = constructDoublyListUtil(mtrx, i + 1 , j, temp); # Return newly constructed node # whose all four node connected # at it"s appropriate position return temp; # Function to construct the # doubly linked list def constructDoublyList(mtrx): # function call for construct # the doubly linked list return constructDoublyListUtil(mtrx, 0 , 0 , None ); # function for displaying # doubly linked list data def display(head): # pointer to move right rPtr = None # pointer to move down dPtr = head; # loop till node->down # is not NULL while (dPtr ! = None ): rPtr = dPtr; # loop till node->right # is not NULL while (rPtr ! = None ): print (rPtr.data, end = " " ) rPtr = rPtr. next ; print () dPtr = dPtr.down; # Driver code if __name__ = = "__main__" : # initialise matrix mtrx = [[ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 7 , 8 , 9 ]] list = constructDoublyList(mtrx); display( list ); # This code is contributed by Rutvik_56 |
C#
// C# program to construct a Doubly // linked linked list from 2D Matrix using System; class GFG{ // define dimension of matrix static int dim= 3; // struct node of doubly linked // list with four pointer // next, prev, up, down public class Node { public int data; public Node next, prev, up, down; }; // function to create a new node static Node createNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; temp.prev = null ; temp.up = null ; temp.down = null ; return temp; } // function to construct the // doubly linked list static Node constructDoublyListUtil( int [,] mtrx, int i, int j,Node curr) { if (i >= dim || j >= dim) { return null ; } // Create Node with value contain // in matrix at index (i, j) Node temp = createNode(mtrx[i,j]); // Assign ad
РЕКОМЕНДУЕМЫЕ СТАТЬИ |