一、Pascal与数据结构的浪漫邂逅
说起Pascal，很多年轻程序员可能觉得这是个"老古董"，但正是这个诞生于1970年的语言，奠定了结构化编程的基础。它的清晰语法特别适合教学，这也是为什么很多大学至今还在用它讲解数据结构。今天我们就用这个经典语言，聊聊那些永恒的数据结构——链表、树和图。
想象一下，Pascal就像一位严谨的数学老师，而数据结构就是它手中的教具。我们先从最简单的链表开始：
{ 单链表节点定义 }
type
PNode = ^TNode; { 定义指针类型 }
TNode = record
data: Integer;
next: PNode; { 指向下一个节点的指针 }
end;
{ 创建新节点 }
function CreateNode(value: Integer): PNode;
var
newNode: PNode;
begin
New(newNode); { 动态内存分配 }
newNode^.data := value;
newNode^.next := nil;
CreateNode := newNode;
end;
这个简单的例子展示了Pascal几个典型特征：^表示指针，record相当于结构体，严格的类型声明。虽然语法看起来有些复古，但这种显式声明的方式反而让数据关系一目了然。
二、链表的艺术：从基础到高级
链表就像一串珍珠项链，每个节点都优雅地牵着下一个节点的手。让我们实现完整的链表操作：
{ 链表插入操作 }
procedure InsertAtHead(var head: PNode; value: Integer);
var
newNode: PNode;
begin
newNode := CreateNode(value);
newNode^.next := head; { 新节点指向原头节点 }
head := newNode; { 更新头节点指针 }
end;
{ 链表遍历 }
procedure PrintList(head: PNode);
var
current: PNode;
begin
current := head;
while current <> nil do
begin
Write(current^.data, ' -> ');
current := current^.next;
end;
Writeln('nil');
end;
在实际工程中，链表特别适合频繁插入删除的场景。比如文本编辑器的撤销操作栈，每个编辑操作都可以作为链表节点，撤销时只需调整指针即可。不过要注意，Pascal需要手动管理内存，记得用Dispose释放节点，否则会内存泄漏。
三、树的舞蹈：二叉搜索树实现
树结构就像公司的组织架构图，CEO在顶端，下面是各部门经理。我们来实现二叉搜索树：
type
PTreeNode = ^TTreeNode;
TTreeNode = record
key: Integer;
left, right: PTreeNode;
end;
{ 插入节点 }
procedure InsertNode(var root: PTreeNode; key: Integer);
begin
if root = nil then
begin
New(root);
root^.key := key;
root^.left := nil;
root^.right := nil;
end
else if key < root^.key then
InsertNode(root^.left, key)
else
InsertNode(root^.right, key);
end;
二叉搜索树在Pascal中的实现展示了递归的优雅。这种结构非常适合字典实现或快速查找场景。但要注意，如果插入顺序不当，可能退化成链表。这时就需要AVL树或红黑树来保持平衡——当然，用Pascal实现这些高级结构会是个有趣的挑战。
四、图的迷宫：邻接表实现
图就像社交网络，每个人是节点，朋友关系是边。我们看看Pascal如何表示：
const
MAX_VERTICES = 100;
type
TAdjList = array[1..MAX_VERTICES] of PNode; { 用链表数组表示邻接表 }
{ 添加边 }
procedure AddEdge(var graph: TAdjList; src, dest: Integer);
var
newNode: PNode;
begin
{ 添加到src的邻接表 }
newNode := CreateNode(dest);
newNode^.next := graph[src];
graph[src] := newNode;
{ 无向图需要反向也添加 }
newNode := CreateNode(src);
newNode^.next := graph[dest];
graph[dest] := newNode;
end;
图的遍历算法（DFS/BFS）在Pascal中实现时，需要用到栈或队列。比如迷宫求解、社交网络好友推荐都会用到这些算法。Pascal的强类型特性在这里反而成了优势，能帮我们在编译期就发现很多连接关系的类型错误。
五、经典算法的Pascal实现
让我们实现一个经典的Dijkstra最短路径算法：
procedure Dijkstra(graph: TAdjList; start: Integer);
var
dist: array[1..MAX_VERTICES] of Integer;
visited: array[1..MAX_VERTICES] of Boolean;
i, count, minDist, u: Integer;
begin
{ 初始化 }
for i := 1 to MAX_VERTICES do
begin
dist[i] := MaxInt;
visited[i] := False;
end;
dist[start] := 0;
{ 主循环 }
for count := 1 to MAX_VERTICES-1 do
begin
{ 找出未访问的最小距离顶点 }
minDist := MaxInt;
for i := 1 to MAX_VERTICES do
if not visited[i] and (dist[i] <= minDist) then
begin
minDist := dist[i];
u := i;
end;
visited[u] := True;
{ 更新邻接顶点距离 }
current := graph[u];
while current <> nil do
begin
if not visited[current^.data] and
(dist[u] <> MaxInt) and
(dist[u] + 1 < dist[current^.data]) then { 假设边权都是1 }
dist[current^.data] := dist[u] + 1;
current := current^.next;
end;
end;
end;
这个实现展示了Pascal处理复杂算法的能力。虽然现代语言有更简洁的语法，但Pascal的清晰结构让算法逻辑一目了然。路由算法、地图导航都是这类算法的典型应用。
六、技术对比与选择建议
与C/C++相比，Pascal实现数据结构有以下特点：
- 优点：更安全的指针操作，更清晰的结构，内置动态数组
- 缺点：缺少现代语言的标准库支持，社区资源较少
选择建议：
- 教学场景：Pascal是绝佳选择
- 嵌入式开发：考虑Turbo Pascal等变体
- 现代项目：建议用Delphi(Object Pascal)获得更好的生态支持
调试技巧：
- 使用
{$R+}开启范围检查 - 用
Writeln输出调试信息 - 善用
assert进行运行时检查
七、总结与展望
通过这次Pascal之旅，我们发现：
- 经典语言的数据结构实现反而更显算法本质
- 指针操作需要格外小心，但也能培养良好的内存管理习惯
- 树和图的Pascal实现具有独特的教学价值
虽然现在用Pascal写生产代码的场景不多，但理解这些底层实现能帮助我们更好地使用现代语言的高级特性。下次当你用Python的list或Java的HashMap时，不妨想想它们背后的Pascal实现原理。
评论