xlabel - title graphics matlab

Lista enlazada MATLAB

Question

¿Cuáles son algunas formas posibles de implementar una lista vinculada en MATLAB ?

Nota: Estoy haciendo esta pregunta por valor pedagógico, no valor práctico. Me doy cuenta de que si realmente está haciendo su propia lista enlazada en MATLAB, probablemente esté haciendo algo mal. Sin embargo, soy un TA para una clase que es intensiva en MATLAB este semestre, y mi objetivo al hacer esta pregunta es comprender mejor la estructura general del lenguaje. Como las instalaciones de programación de propósito general de MATLAB son un poco inusuales, siento que una pregunta como esta me ayudará a entenderlas.

Answer 1

Crear una lista vinculada en MATLAB no es tan malo con la nueva estructura orientada a objetos. Creo que lo que la mayoría de la gente extraña es que la mayoría del comportamiento del puntero se puede lograr en MATLAB mediante el uso de "clases de manejo".

Entonces, comienza con una clase Node ...

classdef Node < handle

       properties
           next
           prev
           value
       end

       methods
            function this = Node(inVal)
                this.value = inVal;
            end
       end
 end 

Entonces su clase de lista vinculada se vería algo así ...

classdef LinkedList < handle

           properties
               firstNode
               lastNode
           end

           methods
               function this = LinkedList(newNode)
                   % Initialize LinkedList with newNode
                   this.firstNode = newNode;
                   this.lastNode = newNode;
               end
               function addNode(this,newNode)
                   % Add newNode to the end of the list
                   newNode.prev = this.lastNode;
                   this.lastNode.next = newNode;
                   this.lastNode = newNode;
               end
           end
    end

Tiré esto bastante rápido, así que no sé si funcionará como está escrito. Pero si solo está interesado en cómo se vería la estructura de una lista vinculada de MATLAB, estoy seguro de que esto es suficiente para comenzar.

El concepto clave aquí es la superclase de control. Cada vez que creas una clase de handle de tipo, obtienes un "puntero" a esa clase. Ese puntero se puede pasar a otras funciones o clases lo que hace posible que los nodos de la lista apunten a otros nodos.

Puede encontrar más información sobre esto here .

Answer 2

El link sugirió Lulu en los comentarios es probablemente la opción que elegiría si quisiera implementar una lista vinculada en MATLAB. Sin embargo, este enfoque se desviaría hacia las características orientadas a objetos de MATLAB, que puede no ser lo que usted desea, ya que usted menciona querer "comprender mejor la estructura general del lenguaje". Como tal, puede hacerlo mejor con un ejemplo más simple que incorpore las características principales generales de la programación de MATLAB.

Se han mencionado varias características generales en otras respuestas, como matrices e indexación matricial , creación de estructuras y uso de funciones anidadas y manejadores de funciones . Voy a ver un ejemplo que hace uso de todas estas características y, con suerte, da una buena introducción a una serie de conceptos clave en MATLAB ...

Código de muestra:

Guarde el siguiente código en un archivo llamado linked_list.m en la ruta MATLAB:

function listObject = linked_list(values)

  data = reshape(values,1,[]);
  listObject = struct(''display'',@display_list,...
                      ''addAfter'',@add_element,...
                      ''delete'',@delete_element);

  function display_list
    %# Displays the data in the list
    disp(data);
  end

  function add_element(values,index)
    %# Adds a set of data values after an index in the list, or at the end
    %#   of the list if the index is larger than the number of list elements
    index = min(index,numel(data));
    data = [data(1:index) reshape(values,1,[]) data(index+1:end)];
  end

  function delete_element(index)
    %# Deletes an element at an index in the list
    data(index) = [];
  end

end

Descripción:

La función linked_list acepta una matriz de tamaño arbitrario y primero la reforma en un vector de fila utilizando la función RESHAPE . Esto se convierte en la "lista vinculada" inicial, almacenada en los data variables.

A continuación, se crea una estructura (utilizando la función STRUCT ) que tiene tres elementos: display , addAfter y delete . Cada uno de estos campos almacena un identificador de función para una de las tres funciones que está anidada dentro de la función linked_list . Estas funciones anidadas pueden acceder a los data variables almacenados en la función primaria.

La estructura listObject se devuelve desde linked_list . Mientras exista esta estructura en el espacio de trabajo, y por lo tanto, mientras exista la función maneja, la variable de data persistirá incluso después de que la función linked_list regrese. Entonces podemos invocar las funciones anidadas (usando sus manejadores) para modificar los data variables. Aquí hay un ejemplo ...

Primero, crea una lista vinculada "objeto" y muestra los contenidos:

>> listObj = linked_list([1 2 3]);  %# A linked list with three elements
>> listObj.display()  %# Access the `display` field and invoke the function
     1     2     3

A continuación, agregue un elemento "4" después del segundo elemento de lista y visualice:

>> listObj.addAfter(4,2)  %# Access the `addAfter` field and invoke the function
>> listObj.display()
     1     2     4     3

Y finalmente, elimine el segundo elemento de lista y visualice:

>> listObj.delete(2)  %# Access the `delete` field and invoke the function
>> listObj.display()
     1     4     3

Observe cómo las funciones anidadas add_element y delete_element utilizan la indexación matricial para modificar los data variables.

Puede ampliar este ejemplo para crear muchas otras funciones anidadas para operar en una lista vinculada, agregando nuevos campos a la estructura para almacenar sus identificadores de función.

Answer 3

He visto un poco la función de gnovice. Creo que lo que más me gusta no es una lista real de C ++ (creo que puedes generar una lista vinculada solo con clases en matlab) sino solo un objeto general donde puedes almacenar matrices de matlab aleatorias. Desde el boceto de gnovice he generado lo siguiente:

function listObject = listfuncs()

  data = cell(0);
  listObject = struct(''display_list'',@display_list,''listlength'',@listlength,''add_firstelement'',@add_firstelement,''add_firstelements'',@add_firstelements,''add_lasttelement'',@add_lasttelement,...
                        ''add_lasttelements'',@add_lasttelements,''add_element'',@add_element,''add_elements'',@add_elements,''set_element'',@set_element,''delete_element'',@delete_element,''delete_first'',@delete_first,...
                        ''delete_last'',@delete_last,''GET_first'',@GET_first,''GET_last'',@GET_last,''GET'',@GET);

  function display_list
    %# Displays the data in the list
    disp(data);
  end

  function N = listlength
    %# Numbers of elements in list
    N = length(data);
  end

  function add_firstelement(datain)
    %# Add an element first
    data = [datain;data];
  end

  function add_firstelements(datain)
    %# Add many element first
    data = [datain(:);data];
  end

  function add_lasttelement(datain)
    %# Add element last
    data = [data;datain];
  end

  function add_lasttelements(datain)
    %# Add many elements last
    data = [data;datain(:)];
  end


  function add_element(datain,index)
    %# Adds a set of data values after an index in the list, or at the end
    %#   of the list if the index is larger than the number of list elements
    index = min(index,numel(data));
    data = [data(1:index) datain data(index+1:end)];
  end

  function add_elements(datain,index)
    %# Adds a set of data values after an index in the list, or at the end
    %#   of the list if the index is larger than the number of list elements
    index = min(index,numel(data));
    data = [data(1:index) datain(:) data(index+1:end)];
  end

  function set_element(datain,index)
    %# function to just change element at position index
    data{index} = datain;
  end

  function delete_element(index)
    %# Deletes an element at an index in the list
    if (index<=length(data) && index>0)
        data(index) = [];
    end
  end

  function delete_first()
    %# Deletes fisrt element
    data = data(2:end);
  end

  function delete_last()
    %# Deletes fisrt element
    data = data(1:end-1);
  end

  function dataout = GET_first()
    %# get first element
    dataout = data{1};
  end    

  function dataout = GET_last()
    %# get last element
    dataout = data{end};
  end    

  function dataout = GET(index)
    %# get element at index here the cell can be transformed to standard arrays
    dataout = cell2mat(data(index));
  end

end

Uso celdas como datos para poder almacenar objetos aleatorios. Tal vez algunos de ustedes tengan algunas ideas mejores

Answer 4

MATLAB tiene acceso a Java:

>> a=java.util.LinkedList;
>> li=a.listIterator;
>> li.add(2);
>> li.add(int8(77));
>> li.add(77);
>> li.add(boolean(true));
>> li.add(''Mr. Bill'');
>> li.previous();
>> li.add([1 2 3 4 5]);
>> a

a =

[2.0, 77, 77.0, true, [D@66a917, Mr. Bill]

>> a.get(4)

ans =

     1
     2
     3
     4
     5

El único inconveniente de este enfoque es que MATLAB no tiene una forma de reunir o serializar objetos arbitrarios MATLAB en Java, está limitado a números de punto flotante, enteros (necesidad de convertirlos en MATLAB usando int8 etc.), booleanos, cadenas, matrices y objetos Java.

Answer 5

No creo que usted (o yo) podamos hacer estructuras dinámicas de datos en ''MATLAB''. Tenemos que usar las características de MATLAB OO y las clases de MATLAB. Como creo que estas instalaciones son realmente un envoltorio de MATLAB en torno a Java, afirmo que esas instalaciones están fuera de MATLAB. Una cuestión de semántica, lo concedo. Si quiere hacer estructuras dinámicas de datos con MATLAB, tiene que usar OO y clases, no puede hacerlo con lo que considero el lenguaje central, que carece de punteros a nivel de usuario.

Answer 6

Puede implementar una lista vinculada con un identificador de función a una función anidada que mantiene los datos de la lista vinculada en el espacio de trabajo del elemento primario anidado.

--Loren

Answer 7

Puede intentar simular punteros usando índices. Es una forma muy incómoda de hacerlo, pero como dijiste, Matlab es un poco inusual y no puede hacer una lista vinculada "real".

Puede usar una estructura de Matlab que consta de dos element campo y next . element sería el elemento de la lista, y el next sería el índice del siguiente nodo. Entonces puede tener una matriz global de estos, representando su "memoria". Puede definir la función "malloc" que agrega un elemento a esta matriz y devuelve su índice. Luego tiene un índice principal que es el índice del primer elemento de la lista, y puede establecer los next campos apropiadamente para formar una lista vinculada.

Si realmente quieres volverse loco, también puedes implementar una "administración de memoria" free y hacer tu propio seguimiento de los nodos usados ​​y gratuitos.