浅谈十字链表在电力系统潮流计算中的应用

　　电力系统由发电、变电、输电、配电和用电等环节组成的电能生产与消费系统。它的功能是将自然界的能源通过发电动力装置（主要包括锅炉、汽轮机、发电机及电厂辅助生产系统等）转化成电能，再经输、变电系统及配电系统将电能供应到各负荷中心，通过各种设备再转换成动力、热、光等不同形式的能量，为地区经济和人民生活服务。由于电源点与负荷中心多数处于不同地区，也无法大量储存，故其生产、输送、分配和消费都在同一时间内完成，并在同一地域内有机地组成一个整体，电能生产必须时刻保持与消费平衡。因此，电能的集中开发与分散使用，以及电能的连续供应与负荷的随机变化，就制约了电力系统的结构和运行。据此，电力系统要实现其功能，就需在各个环节和不同层次设置相应的信息与控制系统，以便对电能的生产和输运过程进行测量、调节、控制、保护、通信和调度，确保用户获得安全、经济、优质的电能。

　　在上海电力局2020年规划设计中，要对多种运行方式及网架结构进行计算。在计算过程中发现：如果采用通常的压缩数组存储方法，需要进行大量的修改工作。因此本文提出十字链表方法，将网络的拓扑结构与数值信息存于十字链表中，使其独立于计算，能保证数据的可重用性和灵活性。这种方法适用于与拓扑相关密切的电力系统计算，本文就潮流计算作简单介绍。

　　1十字链表

　　1.1十字链表简介

　　十字链表（Orthogonal List）是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧都有一个结点，对应于每个定顶点也有一个结点。

　　稀疏矩阵的十字链表（orthogonallinkedlist）是用链表模拟矩阵的行（或者列，这可以根据个人喜好来定），然后，再构造代表列的链表，将每一行中的元素节点插入到对应的列中去。十字链表的逻辑结构就像是一个围棋盘（没见过，你就想一下苍蝇拍，这个总见过吧），而非零元就好像是在棋盘上放的棋子，总共占的空间就是，确定那些线的表头节点和那些棋子代表的非零元节点。，我们用一个指针指向这个棋盘，这个指针就代表了这个稀疏矩阵。稀疏矩阵中的每一个非零元素用一个结点来表示。一般结点由5个域组成。行（row）、列（col）、值域（val）分别表示某非零元素所在行号、列号和数值。向下指针（down）用以链接同一列中表示下一个非零元素的结点，向右指针（right）用以链接同一行中表示下一个非零元素的结点。这样表示每一行中非零元素的结点之间构成一个循环链表，表示每一列中的非零元素的结点之间也构成一个循环链表。同时，每行、每列的循环链接表都有一个表头结点，以利于结点的插入和删除等操作。每一个表头结点的向下指针链接对应列的非零元素结点，向右指针用以链接相应行的非零元素结点。整个表有一个总的空表头指针，在一般结点标以行号、列号处标以矩阵行数m、列数n。有一个指针（root）指向这个总表头结点。由于总表头结点链接着各行列的表头结点，所以由这个指向总表头结点的指针就可以逐步访问到此矩阵的所有非零元素。

　　1.2潮流中十字链表的形成

　　在潮流计算中，考虑到电力系统的特殊性，对十字链表进行了部分简化。

　　（1）每个链表为单向链表，链表中的非零元素按其行号大小排序。

　　（2）非零元素省略其向下指针及行值，省略列表头结点。

　　（3）行表头结点省略其行、列及值域，增加对角元指针指向矩阵对角元，总表头结点就是行表头结点链表的表头。

　　结点有3个成员，指针mpRight指向下一个与本行表头结点相关联的结点，Data包含着与这种关联对应的数值或某种结构体。本文中包含导纳，mnCol则是此非零元素结点的结点号。

　　2十字链表潮流方法

　　2.1导纳矩阵的形成

　　在一般的潮流计算中，形成导纳矩阵的要预先在程序中开出足够大的数组。虽然采用了压缩存储技术，但是静态数组的缺点无法克服。程序无法确切知道所需内存空间的大小，只得开出比较大的数组。十字链表的优点在于，所有结点所需内存都是动态申请的，包括表头结点和非零元素结点。

　　在此矩阵中，对角元的Data为节点自导纳，非对角元的Data为该非零元素对应节点与其表头结点对应节点之间的互导。

　　读入节点数之后，程序即对表头结点链表初始化。表头结点数目比节点数大一，一个表头结点链接的链表存储节点对地导纳。随后每读入一个节点，就在对应的表头结点后插入一个对角元，并将对角元指针指向它；每读入一条支路，就在此支路的每一个节点对应的表头结点后都插入一个对应另一个节点的非零元素结点，然后修改这两个节点的互导，否则直接修改互导。所有互导形成完后，就可计算每个节点的自导了。方法是累加本表头结点后的链表中的所有非零元素的Data值，然后乘以-1。root指针指向总表头结点即表头结点链表中的个结点。

　　这个导纳矩阵中包含了网架的拓扑结构和与此相关的数值。原始数据存储在这个矩阵中具有相对独立性。

　　2.2B1，B2的形成

　　本文中潮流计算采用PQ分解法。

　　PowerQuest PartitionMagic（简称PQ）是一个硬盘分区管理工具。该工具可以在不损失硬盘中已有数据的前提下对硬盘进行重新分区、格式化分区、复制分区、移动分区、隐藏/重现分区、从任意分区引导系统、转换分区（如FAT<-->FAT32 ）结构属性等。

　　矩阵B1是原导纳矩阵去掉松弛节点形成的矩阵，B1矩阵的所有数据均取自原导纳矩阵，所不同的是节点的行号。导纳矩阵中节点的行号是原有节点的节点号，而B1矩阵中节点的行号是导纳矩阵中去掉松弛节点后重新排成的节点号。程序必须记录这种节点号的对应关系。矩阵B2是原导纳矩阵去掉松弛节点和PQ节点后形成的矩阵。同理，程序也必须记录B2矩阵的节点号与原导纳矩阵节点号的对应。

　　PQ分解法中B1，B2矩阵每次只需形成。实际上如果使用牛顿法，每次都需要形成雅可比矩阵，这时导纳矩阵的相对独立性就显得较有优势。

　　十字链表法把网架拓扑结构与相关数值一起存储，其存储结构提供了将数学上的解方程方法与网络分析相分离的基矗以下几个步骤就是纯数学问题了。

　　2.3排序及其它一些问题

　　排序与其它存储结构的方法原理是一致的，但注入元的处理方法不一样。静态数组的压缩存储对注入元的处理方法是每行末尾预留空间，其缺陷也在于预留空间大小的设定。在十字链表方法中，注入元的处理就十分方便了。如果排序时产生了注入元，只需在对应行各插入一个新的结点就可以了。

　　当B1，B2矩阵形成并排过序后，就需要解方程了。主要是因子表的形成与消元和回代。可以采用LU分解法求因子表。原理相同，只需注意十字链表的存储结构。形成了因子表并消元回代之后，方程解出了。

　　然后按照流程，进行反复迭代。功率偏差量小于收敛时，就可结束计算了。

　　3算例

　　根据IEEE14节点模型计算的导纳矩阵，原始数据中没有计入第9号节点的对地导纳。

　　如上所示，导纳矩阵输出时先输出对角元，其后的数据是按照十字链表中的顺序输出的。

　　4结论

　　通常的数组存储方法属于静态数据结构，必须在程序的说明部分给出其类型定义或变量说明。某些程序中使用malloc函数或new操作符动态申请数组，但其数组仍然是空间预留的一种实现，也就仍然存在静态数组的缺点。十字链表中结点的数目是在程序执行时动态增长的，导纳矩阵随着数据的输入逐步形成。

　　对应于电力系统中节点、线路的增加或删除等的结点操作，利用十字链表法比静态数组实现起来要方便而且快速。十字链表法中导纳矩阵的形成本身就是结点的插入操作的结果。

　　通常的处理方法是将拓扑结构与网架数据分开存储在两个数组里。再利用另一个数组作为索引来访问拓扑结构和数据。十字链表的存储方法将网架的拓扑结构与数据存储在一起。于是，潮流计算中系统分析方法与数学处理方法就能分离开来，各种数据的处理实现模块化。

　　如果在C++中封装十字链表，可以把对十字链表的访问变得如同访问一个二维数组一样方便。封装的十字链表将具有很强的可重用性，作为一种自定义的数据类型，可使程序具有很强的可读性，便于程序的编制和维护。