MATLAB链表

Question

在MATLAB中实现链表的几种可能方法是什么？

注意:我问的是这个问题的教学价值,而不是实用价值.我意识到,如果你实际上在MATLAB中滚动自己的链表,你可能会做错事.但是,我是本学期MATLAB密集课程的助教,我提出这个问题的目的是更好地理解语言的一般结构.由于MATLAB的通用编程设备有点不寻常,我觉得这样的问题可以帮助我理解它们.

Answer 1

MATLAB可以访问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

这种方法的一个缺点是因为MATLAB没有办法将任意MATLAB对象编组或序列化为Java,你只限于浮点数,整数(需要在MATLAB中使用它们int8等等),布尔值,字符串,数组和Java对象.

Answer 2

如果我想在MATLAB中实现链表,那么Lulu在评论中建议的链接 可能就是我的选择.然而,这种方法会偏离MATLAB的面向对象特性,这可能不是你想要的,因为你提到要"更好地理解语言的一般结构".因此,您可以使用包含MATLAB编程的一般核心功能的更简单示例来做得更好.

在其他答案中已经提到了许多一般特征,例如矩阵和矩阵索引,创建结构,以及使用嵌套函数和函数句柄.我将通过一个使用所有这些功能的示例,希望能够很好地介绍MATLAB中的一些关键概念......

示例代码:

将下面的代码保存在linked_list.mMATLAB路径上调用的文件中:

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

描述:

该函数linked_list接受任意大小的矩阵,并使用RESHAPE函数首先将其重新整形为行向量.这成为存储在变量中的初始"链表" data.

接着,结构被创建(使用STRUCT函数),其具有三个要素:display,addAfter,和delete.这些字段中的每一个都将函数句柄存储到嵌套在父函数中的三个函数之一linked_list.这些嵌套函数能够访问data存储在父函数中的变量.

该listObject结构从返回linked_list.只要该结构存在于工作空间中,并且因此只要函数处理它包含存在,那么data即使在函数linked_list返回之后该变量也将保持不变.然后我们可以调用嵌套函数(使用它们的句柄)来修改变量data.这是一个例子......

首先,创建一个链接列表"对象"并显示内容:

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

接下来,在第二个list元素之后添加一个元素"4"并显示:

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

最后,删除第二个列表元素并显示:

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

注意如何嵌套功能add_element和delete_element使用矩阵索引修改的变量data.

您可以扩展此示例以创建许多其他嵌套函数,以便在链接列表上进行操作,向结构添加新字段以存储其函数句柄.

Answer 3

在新的面向对象结构中,在MATLAB中创建链表实际上并不是太糟糕.我认为大多数人都错过的是大多数指针行为都可以通过使用"句柄类"在MATLAB中实现.

那么,从Node类开始......

classdef Node < handle

       properties
           next
           prev
           value
       end

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

然后你的链表类看起来像这样......

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

我很快把它扔到了一起,所以我不知道这是否会像写的一样.但是,如果您只对MATLAB链接列表的结构感兴趣,我相信这足以让您入门.

这里的关键概念是句柄超类.无论何时创建类的类handle,都会得到该类的"指针".该指针可以传递给其他函数或类,从而可以使列表的节点指向其他节点.

你可以在这里找到更多相关信息.

Answer 4

我认为您（或我）无法在 MATLAB 中处理动态数据结构。我们必须使用 MATLAB OO 功能和 MATLAB 类。由于我认为这些工具实际上是 Java 的 MATLAB 包装器，因此我大胆声称这些工具位于 MATLAB 之外。我承认，这是一个语义问题。如果你想用MATLAB做动态数据结构，你必须使用OO和类，你不能用我认为的核心语言来做到这一点，它缺乏用户级别的指针。