在Forth中对字符串数组进行排序

Question

我曾经用来CREATE创建一个字符串数组:

create mystringarray s" This" , s" is" , s" a", s" list" ,

我想按升序排序.我在线发现了汇编语言的一些教程,但我想在Forth中完成.什么是最佳实践方法？

Answer 1

您需要首先确保您的数据表示准确.

Forth中的文字字符串是使用单词获得的s",因此您可以编写,例如:

s" This"  ok

输入后,如果这样做.s,您将看到两个值:

.s <2> 7791776 4  ok

这是指向实际字符串(字符数组)的指针,以及字符串中字符数的计数.Forth中的某些单词理解这个字符串表示.type是其中之一.如果您现在输入type,则会在显示屏上输入字符串:

type This ok

所以现在你知道你需要两个单元来表示由它获得的字符串s".您create需要考虑到这一点并使用2,单词来存储每个条目2个单元格,而不是,只存储一个单元格:

create myStringArray
    s" This" 2,
    s" is" 2,
    s" an" 2,
    s" array" 2,
    s" of" 2,
    s" strings" 2,

这是字符串的地址/计数对数组.如果要访问其中一个,可以按如下方式访问:

: myString ( u1 -- caddr u1 )  \ given the index, get the string address/count
    \ fetch 2 cells from myStringArray + (sizeof 2 cells)*index
    myStringArray swap 2 cells * + 2@ ;

打破这一点,您需要获取数组变量的基础,myStringArray并向其添加正确的偏移量到您想要的字符串地址/计数.该偏移量是索引(在数据堆栈上)的数组条目(2个单元格)的大小.因此,表达,myStringArray swap 2 cells * +.接下来是2@检索该位置的双字(地址和计数).

投入使用......

3 myString type array ok
0 myString type This ok

等等...

现在您已经了解了索引数组的基础知识,那么排序的"最佳实践"将遵循为您希望排序的数组类型选择排序算法的常规最佳实践.在这种情况下,冒泡排序可能适用于非常小的字符串数组.您可以使用compare该词来比较两个字符串.例如:

s" This" 0 myString compare .s <1> 0  ok

结果0意味着字符串是相等的.

Answer 2

对数组进行排序的最佳实践方法是使用一些现有的库。如果现有的库不能满足您的需求，或者您的主要目的是学习 \xe2\x80\x94 \n，那么实现您自己的库是有意义的。

\n\n

使用库

\n\n

例如，The Forth Foundation Library ( FFL ) 中的Cell array 模块可用于对任何项目的数组进行排序。

\n\n

代码示例

\n\n

include ffl/car.fs\ninclude ffl/str.fs\n\n0 car-new value arr  \\ new array in the heap\n\n\\ shortcut to keep -- add string into our \'arr\' array\n: k ( a1 u1 -- ) str-new dup arr car-push str-set ;\n\n\\ set compare method\n:noname ( a1 a2 -- n ) >r str-get r> str-get compare ; arr car-compare!\n\n\\ dump strings from the array\n: dump-arr ( -- ) arr car-length@ 0 ?do i arr car-get str-get type cr loop ;\n\n\\ populate the array\ns" This" k s" is" k s" a" k s" list" k\n\n\\ test sorting\ndump-arr cr\narr car-sort \ndump-arr cr\n

\n\n

输出

\n\n

This\nis\na\nlist\n\nThis\na\nis\nlist\n

\n\n

使用裸 Forth

\n\n

如果您只需要一个简单的 Forth 解决方案来学习，请查看冒泡排序示例。

\n\n

字符串数组应仅包含字符串地址。琴弦本身应该保存在其他地方。在本例中使用计数字符串格式 \xe2\x80\x94 很有用，因此我们使用c"word 来表示字符串文字。为了保留字符串本身，我们将初始化代码放入定义中（:noname在本例中） \xe2\x80\x94 它将把字符串保留在字典空间中。

\n\n

冒泡排序从数字变体改编为字符串变体，只是替换了比较项的单词。请注意，2@word 返回顶部最低地址的值。

\n\n

代码示例

\n\n

\\ some helper words\n: bounds ( addr1 u1 -- addr1 addr2 ) over + swap ;\n: lt-cstring ( a1 a2 -- flag ) >r count r> count compare -1 = ;\n\n\\ create an array of counted strings\n:noname ( -- addr cnt )\n  here\n    c" This" , c" is" , c" a" , c" list" ,\n  here over - >cells\n; execute constant cnt constant arr\n\n\\ dump strings from the array  \n: dump-arr ( -- ) cnt 0 ?do i cells arr + @ count type cr loop ;\n\n\\ bubble sort\n: sort-arr ( -- )\n  cnt 2 u< if exit then\n  cnt 1 do true\n    arr cnt i - cells bounds do\n      i 2@ ( a2 a1 ) lt-cstring if i 2@ swap i 2! false and then\n    cell +loop\n    if leave then\n  loop\n;\n\n\\ test sorting\ndump-arr cr\nsort-arr\ndump-arr cr\n\n\\ the output is the same as before\n

\n