在上海電力局2020年規(guī)劃設計中，要對多種運行方式及網(wǎng)架結(jié)構(gòu)進行計算。在計算過程中發(fā)現(xiàn)：如果采用通常的壓縮數(shù)組存儲方法，需要進行大量的修改工作。因此本文提出十字鏈表方法，將網(wǎng)絡的拓撲結(jié)構(gòu)與數(shù)值信息存于十字鏈表中，使其獨立于計算，能保證數(shù)據(jù)的可重用性和靈活性。這種方法適用于與拓撲相關(guān)密切的電力系統(tǒng)計算，本文就潮流計算作簡單介紹。 1十字鏈表 1.1十字鏈表簡介 稀疏矩陣的十字鏈表（orthogonallinkedlist）表示法是用多重鏈表來存儲稀疏矩陣的。稀疏矩陣中的每一個非零元素用一個結(jié)點來表示。一般結(jié)點由5個域組成。如圖1（a）所示，其中行（row）、列（col）、值域（val）分別表示某非零元素所在行號、列號和數(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)提供了將數(shù)學上的解方程方法與網(wǎng)絡分析相分離的基矗以下幾個步驟就是純數(shù)學問題了。 2.3最優(yōu)排序及其它一些問題 最優(yōu)排序與其它存儲結(jié)構(gòu)的方法原理是一致的，但注入元的處理方法不一樣。靜態(tài)數(shù)組的壓縮存儲對注入元的處理方法是每行末尾預留空間，其缺陷也在于預留空間大小的設定。在十字鏈表方法中，注入元的處理就十分方便了。如果排序時產(chǎn)生了注入元，只需在對應行各插入一個新的結(jié)點就可以了。這樣對注入元的處理只需在排序時考慮，而無需在形成矩陣或在系統(tǒng)分析時考慮了。 當B1，B2矩陣形成并排過序后，就需要解方程了。主要是因子表的形成與消元和回代。可以采用LU分解法求因子表。原理相同，只需注意十字鏈表的存儲結(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ù)類型，可使程序具有很強的可讀性，便于程序的編制和維護。