在上海電力局2020年規(guī)劃設(shè)計中，要對多種運行方式及網(wǎng)架結(jié)構(gòu)進行計算,。在計算過程中發(fā)現(xiàn)：如果采用通常的壓縮數(shù)組存儲方法,，需要進行大量的修改工作。因此本文提出十字鏈表" title="鏈表">鏈表方法,，將網(wǎng)絡的拓撲結(jié)構(gòu)" title="拓撲結(jié)構(gòu)">拓撲結(jié)構(gòu)與數(shù)值信息存于十字鏈表中,，使其獨立于計算，能保證數(shù)據(jù)的可重用性和靈活性,。這種方法適用于與拓撲相關(guān)密切的電力系統(tǒng)計算,，本文就潮流計算作簡單介紹。
1十字鏈表
1.1十字鏈表簡介
稀疏矩陣的十字鏈表（orthogonallinkedlist）表示法是用多重鏈表來存儲稀疏矩陣的,。稀疏矩陣中的每一個非零" title="非零">非零元素用一個結(jié)點來表示,。一般結(jié)點由5個域組成,。如圖1（a）所示,，其中行（row）,、列（col）、值域" title="值域">值域（val）分別表示某非零元素所在行號" title="行號">行號,、列號和數(shù)值,。向下指針（down）用以鏈接同一列中表示下一個非零元素的結(jié)點，向右指針（right）用以鏈接同一行中表示下一個非零元素的結(jié)點,。這樣,，表示每一行中非零元素的結(jié)點之間構(gòu)成一個循環(huán)鏈表，表示每一列中的非零元素的結(jié)點之間也構(gòu)成一個循環(huán)鏈表,。同時,，每行、每列的循環(huán)鏈接表都有一個表頭結(jié)點,，以利于結(jié)點的插入和刪除等操作,。表頭結(jié)點的行號、列號以及數(shù)值域都沒有用,。為節(jié)約存儲,，可將這兩組空表頭結(jié)點合用。每一個表頭結(jié)點的向下指針鏈接對應列的非零元素結(jié)點,，向右指針用以鏈接相應行的非零元素結(jié)點,。此外，借用數(shù)值域來作為將各個空表頭結(jié)點也鏈接成一個鏈表的指針,。整個表有一個總的空表頭指針,，在一般結(jié)點標以行號、列號處標以矩陣行數(shù)m,、列數(shù)n,。有一個指針（root）指向這個總表頭結(jié)點。由于總表頭結(jié)點鏈接著各行列的表頭結(jié)點,，所以由這個指向總表頭結(jié)點的指針就可以逐步訪問到此矩陣的所有非零元素,。
1.2潮流中十字鏈表的形成
在潮流計算中，考慮到電力系統(tǒng)的特殊性,，對十字鏈表進行了部分簡化,。
（1）每個鏈表為單向鏈表，鏈表中的非零元素按其行號大小排序,。
（2）非零元素省略其向下指針及行值,，省略列表頭結(jié)點。
（3）行表頭結(jié)點省略其行,、列及值域,，增加對角元指針指向矩陣對角元,，總表頭結(jié)點就是行表頭結(jié)點鏈表的表頭。
如果表頭結(jié)點在表頭結(jié)點鏈表中的位置為nCol,則此行鏈接的非零元素鏈表中的結(jié)點都是與第nCol結(jié)點相關(guān)聯(lián)的,。
表頭結(jié)點中有兩個非零元素結(jié)點的指針和一個表頭結(jié)點指針,。第一個非零元素結(jié)點指針mpRight指向本行鏈表中第一個非零元素，第二個非零元素結(jié)點指針mpCorner指向本行鏈表中與對應行具有相同行號的非零元素,，即對角元,。表頭結(jié)點指針指向下一行的表頭結(jié)點。
結(jié)點有3個成員,，指針mpRight指向下一個與本行表頭結(jié)點相關(guān)聯(lián)的結(jié)點,，Data包含著與這種關(guān)聯(lián)對應的數(shù)值或某種結(jié)構(gòu)體。本文中包含導納,，mnCol則是此非零元素結(jié)點的結(jié)點號,。
2十字鏈表潮流方法
2.1導納矩陣的形成
在一般的潮流計算中，形成導納矩陣的要預先在程序中開出足夠大的數(shù)組,。雖然采用了壓縮存儲技術(shù),，但是靜態(tài)數(shù)組的缺點無法克服。程序無法確切知道所需內(nèi)存空間的大小,，只得開出比較大的數(shù)組,。這樣節(jié)點數(shù)比較小時，內(nèi)存空間浪費了,；節(jié)點數(shù)大時,，程序無法處理。十字鏈表的優(yōu)點在于,，所有結(jié)點所需內(nèi)存都是動態(tài)申請的,，包括表頭結(jié)點（其多少由節(jié)點數(shù)決定）和非零元素結(jié)點（其多少由支路數(shù)決定）。
在此矩陣中,，對角元的Data為節(jié)點自導納,，非對角元的Data為該非零元素對應節(jié)點與其表頭結(jié)點對應節(jié)點之間的互導。
讀入節(jié)點數(shù)之后,，程序即對表頭結(jié)點鏈表初始化,。表頭結(jié)點數(shù)目比節(jié)點數(shù)大一，最后一個表頭結(jié)點鏈接的鏈表存儲節(jié)點對地導納,。隨后每讀入一個節(jié)點,，就在對應的表頭結(jié)點后插入一個對角元，并將對角元指針指向它,；每讀入一條支路,，如果是一條新的支路，就在此支路的每一個節(jié)點對應的表頭結(jié)點后都插入一個對應另一個節(jié)點的非零元素結(jié)點,，然后修改這兩個節(jié)點的互導,，否則直接修改互導,。所有互導形成完后，就可計算每個節(jié)點的自導了,。方法是累加本表頭結(jié)點后的鏈表中的所有非零元素的Data值,，然后乘以-1。節(jié)點的對地導納可將這一部分計算在內(nèi),。root指針指向總表頭結(jié)點即表頭結(jié)點鏈表中的第一個結(jié)點,。
這個導納矩陣中包含了網(wǎng)架的拓撲結(jié)構(gòu)和與此相關(guān)的數(shù)值。程序中這個矩陣是基本不變的,。原始數(shù)據(jù)存儲在這個矩陣中具有相對獨立性。
2.2B1,，B2的形成
本文中潮流計算采用PQ分解法,。
矩陣B1是原導納矩陣去掉松弛節(jié)點形成的矩陣，B1矩陣的所有數(shù)據(jù)均取自原導納矩陣,，所不同的是節(jié)點的行號,。導納矩陣中節(jié)點的行號是原有節(jié)點的節(jié)點號，而B1矩陣中節(jié)點的行號是導納矩陣中去掉松弛節(jié)點后重新排成的節(jié)點號,。程序必須記錄這種節(jié)點號的對應關(guān)系,。矩陣B2是原導納矩陣去掉松弛節(jié)點和PQ 節(jié)點后形成的矩陣。同理,，程序也必須記錄B2矩陣的節(jié)點號與原導納矩陣節(jié)點號的對應,。若考慮節(jié)點的對地導納，只需訪問表頭結(jié)點鏈表中對地導納對應的鏈表,，按行號搜尋即可得到相應的對地導納,。
PQ分解法中B1，B2矩陣每次只需形成一次,。實際上如果使用牛頓法,，每次都需要形成雅可比矩陣，這時導納矩陣的相對獨立性就顯得較有優(yōu)勢,。
十字鏈表法把網(wǎng)架拓撲結(jié)構(gòu)與相關(guān)數(shù)值一起存儲,，其存儲結(jié)構(gòu)" title="存儲結(jié)構(gòu)">存儲結(jié)構(gòu)提供了將數(shù)學上的解方程方法與網(wǎng)絡分析相分離的基矗以下幾個步驟就是純數(shù)學問題了。
2.3最優(yōu)排序及其它一些問題
最優(yōu)排序與其它存儲結(jié)構(gòu)的方法原理是一致的,，但注入元的處理方法不一樣,。靜態(tài)數(shù)組的壓縮存儲對注入元的處理方法是每行末尾預留空間，其缺陷也在于預留空間大小的設(shè)定,。在十字鏈表方法中,，注入元的處理就十分方便了。如果排序時產(chǎn)生了注入元,，只需在對應行各插入一個新的結(jié)點就可以了,。這樣對注入元的處理只需在排序時考慮,，而無需在形成矩陣或在系統(tǒng)分析時考慮了。
當B1,，B2矩陣形成并排過序后,，就需要解方程了。主要是因子表的形成與消元和回代,?？梢圆捎肔U分解法求因子表。原理相同,，只需注意十字鏈表的存儲結(jié)構(gòu),。形成了因子表并消元回代之后，方程解出了,。
然后按照流程,，進行反復迭代。功率偏差量小于收斂精度時,，就可結(jié)束計算了,。
3算例
根據(jù)IEEE14節(jié)點模型計算的導納矩陣（只列出部分，導納矩陣實部略）,，原始數(shù)據(jù)中沒有計入第9號節(jié)點的對地導納,。
如上所示，導納矩陣輸出時先輸出對角元（訪問對角元指針即可得）,，其后的數(shù)據(jù)是按照十字鏈表中的順序輸出的,。
4結(jié)論
通常的數(shù)組存儲方法屬于靜態(tài)數(shù)據(jù)結(jié)構(gòu)，必須在程序的說明部分給出其類型定義或變量說明,。某些程序中使用malloc函數(shù)或new操作符動態(tài)申請數(shù)組,，但其數(shù)組仍然是空間預留的一種實現(xiàn)，也就仍然存在靜態(tài)數(shù)組的缺點,。十字鏈表屬于動態(tài)數(shù)據(jù)結(jié)構(gòu),，它的規(guī)模大小在程序執(zhí)行時是可以變化的。十字鏈表中結(jié)點的數(shù)目是在程序執(zhí)行時動態(tài)增長的,，導納矩陣隨著數(shù)據(jù)的輸入逐步形成,。使用十字鏈表的存儲可使存儲的分配較為靈活，更充分的利用內(nèi)存,。
對應于電力系統(tǒng)中節(jié)點,、線路的增加或刪除等的結(jié)點操作，利用十字鏈表法比靜態(tài)數(shù)組實現(xiàn)起來要方便而且快速,。十字鏈表法中導納矩陣的形成本身就是結(jié)點的插入操作的結(jié)果,。例如添加線路的方法與讀入數(shù)據(jù)時添加線路的方法就是完全一樣的。
通常的處理方法是將拓撲結(jié)構(gòu)與網(wǎng)架數(shù)據(jù)分開存儲在兩個數(shù)組里。再利用另一個數(shù)組作為索引來訪問拓撲結(jié)構(gòu)和數(shù)據(jù),。十字鏈表的存儲方法將網(wǎng)架的拓撲結(jié)構(gòu)與數(shù)據(jù)存儲在一起,。于是，潮流計算中系統(tǒng)分析方法與數(shù)學處理方法就能分離開來,，各種數(shù)據(jù)的處理實現(xiàn)模塊化,。
如果在C++中封裝十字鏈表，可以把對十字鏈表的訪問變得如同訪問一個二維數(shù)組一樣方便,。封裝的十字鏈表將具有很強的可重用性,，作為一種自定義的數(shù)據(jù)類型，可使程序具有很強的可讀性,，便于程序的編制和維護,。