十字鏈表在電力系統(tǒng)潮流計算中的應用

在上海電力局2020年規(guī)劃設計中，要對多種運行方式及網架結構進行計算。在計算過程中發(fā)現：如果采用通常的壓縮數組存儲方法，需要進行大量的修改工作。因此本文提出十字鏈表方法，將網絡的拓撲結構與數值信息存于十字鏈表中，使其獨立于計算，能保證數據的可重用性和靈活性。這種方法適用于與拓撲相關密切的電力系統(tǒng)計算，本文就潮流計算作簡單介紹。

1十字鏈表

1.1十字鏈表簡介

稀疏矩陣的十字鏈表（orthogonallinkedlist）表示法是用多重鏈表來存儲稀疏矩陣的。稀疏矩陣中的每一個非零元素用一個結點來表示。一般結點由5個域組成。如圖1（a）所示，其中行（row）、列（col）、值域（val）分別表示某非零元素所在行號、列號和數值。向下指針（down）用以鏈接同一列中表示下一個非零元素的結點，向右指針（right）用以鏈接同一行中表示下一個非零元素的結點。這樣，表示每一行中非零元素的結點之間構成一個循環(huán)鏈表，表示每一列中的非零元素的結點之間也構成一個循環(huán)鏈表。同時，每行、每列的循環(huán)鏈接表都有一個表頭結點，以利于結點的插入和刪除等操作。表頭結點的行號、列號以及數值域都沒有用。為節(jié)約存儲，可將這兩組空表頭結點合用。每一個表頭結點的向下指針鏈接對應列的非零元素結點，向右指針用以鏈接相應行的非零元素結點。此外，借用數值域來作為將各個空表頭結點也鏈接成一個鏈表的指針。整個表有一個總的空表頭指針，在一般結點標以行號、列號處標以矩陣行數m、列數n。有一個指針（root）指向這個總表頭結點。由于總表頭結點鏈接著各行列的表頭結點，所以由這個指向總表頭結點的指針就可以逐步訪問到此矩陣的所有非零元素。

1.2潮流中十字鏈表的形成

在潮流計算中，考慮到電力系統(tǒng)的特殊性，對十字鏈表進行了部分簡化。

（1）每個鏈表為單向鏈表，鏈表中的非零元素按其行號大小排序。

（2）非零元素省略其向下指針及行值，省略列表頭結點。

（3）行表頭結點省略其行、列及值域，增加對角元指針指向矩陣對角元，總表頭結點就是行表頭結點鏈表的表頭。

如果表頭結點在表頭結點鏈表中的位置為nCol,則此行鏈接的非零元素鏈表中的結點都是與第nCol結點相關聯的。

表頭結點中有兩個非零元素結點的指針和一個表頭結點指針。第一個非零元素結點指針mpRight指向本行鏈表中第一個非零元素，第二個非零元素結點指針mpCorner指向本行鏈表中與對應行具有相同行號的非零元素，即對角元。表頭結點指針指向下一行的表頭結點。

結點有3個成員，指針mpRight指向下一個與本行表頭結點相關聯的結點，Data包含著與這種關聯對應的數值或某種結構體。本文中包含導納，mnCol則是此非零元素結點的結點號。

2十字鏈表潮流方法

2.1導納矩陣的形成

在一般的潮流計算中，形成導納矩陣的要預先在程序中開出足夠大的數組。雖然采用了壓縮存儲技術，但是靜態(tài)數組的缺點無法克服。程序無法確切知道所需內存空間的大小，只得開出比較大的數組。這樣節(jié)點數比較小時，內存空間浪費了；節(jié)點數大時，程序無法處理。十字鏈表的優(yōu)點在于，所有結點所需內存都是動態(tài)申請的，包括表頭結點（其多少由節(jié)點數決定）和非零元素結點（其多少由支路數決定）。

在此矩陣中，對角元的Data為節(jié)點自導納，非對角元的Data為該非零元素對應節(jié)點與其表頭結點對應節(jié)點之間的互導。

讀入節(jié)點數之后，程序即對表頭結點鏈表初始化。表頭結點數目比節(jié)點數大一，最后一個表頭結點鏈接的鏈表存儲節(jié)點對地導納。隨后每讀入一個節(jié)點，就在對應的表頭結點后插入一個對角元，并將對角元指針指向它；每讀入一條支路，如果是一條新的支路，就在此支路的每一個節(jié)點對應的表頭結點后都插入一個對應另一個節(jié)點的非零元素結點，然后修改這兩個節(jié)點的互導，否則直接修改互導。所有互導形成完后，就可計算每個節(jié)點的自導了。方法是累加本表頭結點后的鏈表中的所有非零元素的Data值，然后乘以-1。節(jié)點的對地導納可將這一部分計算在內。root指針指向總表頭結點即表頭結點鏈表中的第一個結點。

這個導納矩陣中包含了網架的拓撲結構和與此相關的數值。程序中這個矩陣是基本不變的。原始數據存儲在這個矩陣中具有相對獨立性。

2.2B1，B2的形成

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

矩陣B1是原導納矩陣去掉松弛節(jié)點形成的矩陣，B1矩陣的所有數據均取自原導納矩陣，所不同的是節(jié)點的行號。導納矩陣中節(jié)點的行號是原有節(jié)點的節(jié)點號，而B1矩陣中節(jié)點的行號是導納矩陣中去掉松弛節(jié)點后重新排成的節(jié)點號。程序必須記錄這種節(jié)點號的對應關系。矩陣B2是原導納矩陣去掉松弛節(jié)點和PQ 節(jié)點后形成的矩陣。同理，程序也必須記錄B2矩陣的節(jié)點號與原導納矩陣節(jié)點號的對應。若考慮節(jié)點的對地導納，只需訪問表頭結點鏈表中對地導納對應的鏈表，按行號搜尋即可得到相應的對地導納。

PQ分解法中B1，B2矩陣每次只需形成一次。實際上如果使用牛頓法，每次都需要形成雅可比矩陣，這時導納矩陣的相對獨立性就顯得較有優(yōu)勢。

十字鏈表法把網架拓撲結構與相關數值一起存儲，其存儲結構提供了將數學上的解方程方法與網絡分析相分離的基矗以下幾個步驟就是純數學問題了。

2.3最優(yōu)排序及其它一些問題

最優(yōu)排序與其它存儲結構的方法原理是一致的，但注入元的處理方法不一樣。靜態(tài)數組的壓縮存儲對注入元的處理方法是每行末尾預留空間，其缺陷也在于預留空間大小的設定。在十字鏈表方法中，注入元的處理就十分方便了。如果排序時產生了注入元，只需在對應行各插入一個新的結點就可以了。這樣對注入元的處理只需在排序時考慮，而無需在形成矩陣或在系統(tǒng)分析時考慮了。

當B1，B2矩陣形成并排過序后，就需要解方程了。主要是因子表的形成與消元和回代。可以采用LU分解法求因子表。原理相同，只需注意十字鏈表的存儲結構。形成了因子表并消元回代之后，方程解出了。

然后按照流程，進行反復迭代。功率偏差量小于收斂精度時，就可結束計算了。

3算例

根據IEEE14節(jié)點模型計算的導納矩陣（只列出部分，導納矩陣實部略），原始數據中沒有計入第9號節(jié)點的對地導納。

如上所示，導納矩陣輸出時先輸出對角元（訪問對角元指針即可得），其后的數據是按照十字鏈表中的順序輸出的。

4結論

通常的數組存儲方法屬于靜態(tài)數據結構，必須在程序的說明部分給出其類型定義或變量說明。某些程序中使用malloc函數或new操作符動態(tài)申請數組，但其數組仍然是空間預留的一種實現，也就仍然存在靜態(tài)數組的缺點。十字鏈表屬于動態(tài)數據結構，它的規(guī)模大小在程序執(zhí)行時是可以變化的。十字鏈表中結點的數目是在程序執(zhí)行時動態(tài)增長的，導納矩陣隨著數據的輸入逐步形成。使用十字鏈表的存儲可使存儲的分配較為靈活，更充分的利用內存。

對應于電力系統(tǒng)中節(jié)點、線路的增加或刪除等的結點操作，利用十字鏈表法比靜態(tài)數組實現起來要方便而且快速。十字鏈表法中導納矩陣的形成本身就是結點的插入操作的結果。例如添加線路的方法與讀入數據時添加線路的方法就是完全一樣的。

通常的處理方法是將拓撲結構與網架數據分開存儲在兩個數組里。再利用另一個數組作為索引來訪問拓撲結構和數據。十字鏈表的存儲方法將網架的拓撲結構與數據存儲在一起。于是，潮流計算中系統(tǒng)分析方法與數學處理方法就能分離開來，各種數據的處理實現模塊化。

如果在C++中封裝十字鏈表，可以把對十字鏈表的訪問變得如同訪問一個二維數組一樣方便。封裝的十字鏈表將具有很強的可重用性，作為一種自定義的數據類型，可使程序具有很強的可讀性，便于程序的編制和維護。