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

在上海電力局2020年規(guī)劃設(shè)計(jì)中，要對(duì)多種運(yùn)行方式及網(wǎng)架結(jié)構(gòu)進(jìn)行計(jì)算。在計(jì)算過程中發(fā)現(xiàn)：如果采用通常的壓縮數(shù)組存儲(chǔ)方法，需要進(jìn)行大量的修改工作。因此本文提出十字鏈表方法，將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)與數(shù)值信息存于十字鏈表中，使其獨(dú)立于計(jì)算，能保證數(shù)據(jù)的可重用性和靈活性。這種方法適用于與拓?fù)湎嚓P(guān)密切的電力系統(tǒng)計(jì)算，本文就潮流計(jì)算作簡單介紹。

1十字鏈表

1.1十字鏈表簡介

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

1.2潮流中十字鏈表的形成

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

（1）每個(gè)鏈表為單向鏈表，鏈表中的非零元素按其行號(hào)大小排序。

（2）非零元素省略其向下指針及行值，省略列表頭結(jié)點(diǎn)。

（3）行表頭結(jié)點(diǎn)省略其行、列及值域，增加對(duì)角元指針指向矩陣對(duì)角元，總表頭結(jié)點(diǎn)就是行表頭結(jié)點(diǎn)鏈表的表頭。

如果表頭結(jié)點(diǎn)在表頭結(jié)點(diǎn)鏈表中的位置為nCol,則此行鏈接的非零元素鏈表中的結(jié)點(diǎn)都是與第nCol結(jié)點(diǎn)相關(guān)聯(lián)的。

表頭結(jié)點(diǎn)中有兩個(gè)非零元素結(jié)點(diǎn)的指針和一個(gè)表頭結(jié)點(diǎn)指針。第一個(gè)非零元素結(jié)點(diǎn)指針mpRight指向本行鏈表中第一個(gè)非零元素，第二個(gè)非零元素結(jié)點(diǎn)指針mpCorner指向本行鏈表中與對(duì)應(yīng)行具有相同行號(hào)的非零元素，即對(duì)角元。表頭結(jié)點(diǎn)指針指向下一行的表頭結(jié)點(diǎn)。

結(jié)點(diǎn)有3個(gè)成員，指針mpRight指向下一個(gè)與本行表頭結(jié)點(diǎn)相關(guān)聯(lián)的結(jié)點(diǎn)，Data包含著與這種關(guān)聯(lián)對(duì)應(yīng)的數(shù)值或某種結(jié)構(gòu)體。本文中包含導(dǎo)納，mnCol則是此非零元素結(jié)點(diǎn)的結(jié)點(diǎn)號(hào)。

2十字鏈表潮流方法

2.1導(dǎo)納矩陣的形成

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

在此矩陣中，對(duì)角元的Data為節(jié)點(diǎn)自導(dǎo)納，非對(duì)角元的Data為該非零元素對(duì)應(yīng)節(jié)點(diǎn)與其表頭結(jié)點(diǎn)對(duì)應(yīng)節(jié)點(diǎn)之間的互導(dǎo)。

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

這個(gè)導(dǎo)納矩陣中包含了網(wǎng)架的拓?fù)浣Y(jié)構(gòu)和與此相關(guān)的數(shù)值。程序中這個(gè)矩陣是基本不變的。原始數(shù)據(jù)存儲(chǔ)在這個(gè)矩陣中具有相對(duì)獨(dú)立性。

2.2B1，B2的形成

本文中潮流計(jì)算采用PQ分解法。

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

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

十字鏈表法把網(wǎng)架拓?fù)浣Y(jié)構(gòu)與相關(guān)數(shù)值一起存儲(chǔ)，其存儲(chǔ)結(jié)構(gòu)提供了將數(shù)學(xué)上的解方程方法與網(wǎng)絡(luò)分析相分離的基矗以下幾個(gè)步驟就是純數(shù)學(xué)問題了。

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

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

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

然后按照流程，進(jìn)行反復(fù)迭代。功率偏差量小于收斂精度時(shí)，就可結(jié)束計(jì)算了。

3算例

根據(jù)IEEE14節(jié)點(diǎn)模型計(jì)算的導(dǎo)納矩陣（只列出部分，導(dǎo)納矩陣實(shí)部略），原始數(shù)據(jù)中沒有計(jì)入第9號(hào)節(jié)點(diǎn)的對(duì)地導(dǎo)納。

如上所示，導(dǎo)納矩陣輸出時(shí)先輸出對(duì)角元（訪問對(duì)角元指針即可得），其后的數(shù)據(jù)是按照十字鏈表中的順序輸出的。

4結(jié)論

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

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

通常的處理方法是將拓?fù)浣Y(jié)構(gòu)與網(wǎng)架數(shù)據(jù)分開存儲(chǔ)在兩個(gè)數(shù)組里。再利用另一個(gè)數(shù)組作為索引來訪問拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)。十字鏈表的存儲(chǔ)方法將網(wǎng)架的拓?fù)浣Y(jié)構(gòu)與數(shù)據(jù)存儲(chǔ)在一起。于是，潮流計(jì)算中系統(tǒng)分析方法與數(shù)學(xué)處理方法就能分離開來，各種數(shù)據(jù)的處理實(shí)現(xiàn)模塊化。

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