数据结构与解析技术：列表、树及表达式处理

### 数据结构与解析技术：列表、树及表达式处理 #### 1. 列表结构的定义与操作 列表是一种常见的链式结构，可通过自定义数据类型来构建特定类型的列表，进而推广到通用列表。 - **整数链表**：定义整数链表的数据类型，包含空列表和整数节点及指向下一节点的链接。 ```sml datatype ilist = icons of int * ilist | INIL; ``` 示例：创建一个包含 1、2、3 的整数链表。 ```sml icons(1, icons(2, icons(3, INIL))); ``` 计算整数链表元素之和的函数： ```sml fun isum INIL = 0 | isum (icons(v, l)) = v + isum l; ``` - **字符串链表**：类似地，定义字符串链表的数据类型。 ```sml datatype slist = scons of string * slist | SNIL; ``` 示例：创建一个包含 "ape"、"bat"、"cat" 的字符串链表。 ```sml scons("ape", scons("bat", scons("cat", SNIL))); ``` 将字符串链表元素连接成一个字符串的函数： ```sml fun implode SNIL = "" | implode (scons(s, l)) = s ^ implode l; ``` - **通用列表**：通过引入类型变量，可将特定类型的列表推广为通用列表。 ```sml datatype 'a list = cons of 'a * 'a list | NIL; ``` 示例：创建整数列表和字符串列表。 ```sml cons(1, cons(2, cons(3, NIL))); cons("ape", cons("bat", cons("cat", NIL))); ``` 计算列表长度的函数： ```sml fun length NIL = 0 | length (cons(h, t)) = 1 + length t; ``` 对列表中的每个元素应用函数的函数： ```sml fun map f NIL = NIL | map f (cons(h, t)) = cons(f h, map f t); ``` #### 2. 列表的效率问题 列表结构在访问元素时效率较低。对于一个包含 N 个元素的列表，最坏情况下需要跳过 N - 1 个元素才能访问到最后一个元素，平均需要扫描 N/2 个元素。 | 元素编号 | 需跳过元素数量 | | ---- | ---- | | 1 | 0 | | 2 | 1 | | 3 | 2 | | 4 | 3 | | 5 | 4 | 以 5 个元素的列表为例，依次访问每个元素总共需要跳过 10 个元素，平均每个元素需要跳过 2 个元素，接近 N/2。对于长列表，这种开销会变得非常大。 #### 3. 树结构的引入与特性 对于有元素顺序的数据，树结构可以在增加存储需求的代价下实现更快的访问。 - **有序二叉树**：每个节点最多有两个分支，左分支上的所有值小于节点值，右分支上的所有值大于节点值。 例如，从值 7、3、1、5、10、8、12 构建的二叉树： ```plaintext 7 / \ 3 10 / \ / \ 1 5 8 12 ``` 有序二叉树的层数与节点数量的关系为：层数 = (log₂ N) + 1。对于包含 7 个节点的树，层数为 (log₂ 7) + 1 = 3。在该树中查找 12 只需要 3 步，而在等效的有序线性列表中需要 7 步。 #### 4. 二叉树的数据类型与操作 - **整数二叉树**：定义整数二叉树的数据类型。 ```sml datatype itree = iempty | inode of int * itree * itree; ``` 示例：构建上述二叉树。 ```sml inode(7, inode(3, inode(1, iempty, iempty), inode(5, iempty, iempty)), inode(10, inode(8, iempty, iempty), inode(12, iempty, iempty))); ``` 向二叉树中添加值的函数： ```sml fun iadd v iempty = inode(v, iempty, iempty) | iadd v (inode(iv, l, r)) = if v <= iv then inode(iv, iadd v l, r) else inode(iv, l, iadd v r); ``` 中序遍历二叉树生成升序列表的函数： ```sml fun itrav iempty = [] | itrav (inode(v, l, r)) = (itrav l) @ (v :: itrav r); ``` - **多态二叉树**：通过引入类型变量，将整数二叉树推广为多态二叉树。 ```sml datatype 'a tree = empty | node of 'a * 'a tree * 'a tree; ``` 向多态二叉树中添加值的函数： ```sml fun add less v empty = node (v, empty, empty) | add less v (node(nv, l, r)) = if less v nv then node(nv, add less v l, r) else node(nv, l, add less v r); ``` 中序遍历多态二叉树的函数： ```sml fun trav empty = [] | trav (node(v, l, r)) = trav l @ v :: trav r; ``` #### 5. 语法规则与解析 以英文句子为例，可通过一组规则来描述句子的结构。 - **英语句子语法规则**： ```plaintext <sentence> ::= <noun phrase> <verb> <noun phrase> <noun phrase> ::= <article> <noun part> <noun part> ::= <adjective> <noun> | <noun> <article> ::= a | the <noun> ::= cat | mouse | peach <adjective> ::= big | small <verb> ::= saw | ate ``` - **解析函数**：编写 SML 函数来解析句子。 ```sml datatype symbol = art of string | adj of string | n of string | v of string | sfail fun article (art a :: t) = (true, t) | article s = (false, s) and adjective (adj a :: t) = (true, t) | adjective s = (false, s) and noun (n nn :: t) = (true, t) | noun s = (false, s) and verb (v w :: t) = (true, t) | verb s = (false, s) and nounpart [] = (false, []) | nounpart s = let val (a, r1) = adjective s in if not a then let val (nn, r2) = noun s in if not nn then (false, s) else (true, r2) end else let val (nn, r2) = noun r1 in if not nn then (false, s) else (true, r2) end end and nounphrase [] = (false, []) | nounphrase s = let val (a, r1) = article s in if not a then (false, s) else let val (np, r2) = nounpart r1 in if not np then (false, r1) else (true, r2) end end and sentence [] = (false, []) | sentence s = let val (np1, r1) = nounphrase s in if not np1 then (false, s) else let val (vv, r2) = verb r1 in if not vv then (false, r1) else ```