隨機(jī)稀疏矩陣鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的探討

魏斐翡+沈華

摘要：隨機(jī)稀疏矩陣的壓縮存儲(chǔ)是數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容之一。隨機(jī)稀疏矩陣的壓縮存儲(chǔ)有兩類實(shí)現(xiàn)：順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式。在數(shù)據(jù)結(jié)構(gòu)課程中討論隨機(jī)稀疏矩陣順序存儲(chǔ)結(jié)構(gòu)相對(duì)較多，缺少對(duì)其鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的詳細(xì)介紹和深入討論。為了彌補(bǔ)這個(gè)不足，深入討論了隨機(jī)稀疏矩陣的三種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、分析了它們之間的關(guān)系和特點(diǎn)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；隨機(jī)稀疏矩陣；壓縮存儲(chǔ)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

中圖分類號(hào)：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2017）36-0191-02

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的基礎(chǔ)核心課程，它對(duì)于外圍課程的知識(shí)與經(jīng)驗(yàn)具有遷移性、衍生性，對(duì)學(xué)生自學(xué)知識(shí)和獲取實(shí)踐經(jīng)驗(yàn)具有基礎(chǔ)性、發(fā)展性[1-6]。隨著計(jì)算機(jī)應(yīng)用的發(fā)展，出現(xiàn)了許多用計(jì)算機(jī)處理高階矩陣的問題，這類問題對(duì)內(nèi)存要求較高，因此研究矩陣的壓縮存儲(chǔ)是非常必要的[7]。本文重點(diǎn)討論隨機(jī)稀疏矩陣壓縮存儲(chǔ)的三種鏈?zhǔn)酱鎯?chǔ)。

一、隨機(jī)稀疏矩陣及其壓縮存儲(chǔ)

隨機(jī)稀疏矩陣是一種非零元比零元少得多（即稀疏性）且非零元在矩陣中的分布不具有一定規(guī)律性（即隨機(jī)性）的矩陣[7-8]。其壓縮存儲(chǔ)目標(biāo)是，壓縮掉對(duì)零元的存儲(chǔ)，只存儲(chǔ)非零元。因?yàn)榉橇阍姆植际请S機(jī)的，所以它需要用一個(gè)三元組（元素所在的行，元素所在的列，元素的值）來唯一確定。因此，一個(gè)稀疏矩陣對(duì)應(yīng)一個(gè)三元組集合。三元組集合給出了所有非零元的分布和值，但是只給出了部分零元的分布，從而不能確定一個(gè)稀疏矩陣[7]。如果同時(shí)有稀疏矩陣的規(guī)模信息（即行數(shù)和列數(shù)），那么我們就可以知道零元的所有分布，從而可以唯一確定一個(gè)稀疏矩陣[7]。綜上所述，一個(gè)稀疏矩陣可以用其對(duì)應(yīng)的三元組集合和它的行數(shù)、列數(shù)唯一確定。如果三元組集合中的元素以行序?yàn)橹餍颍敲次覀兊玫搅艘粋€(gè)三元組線性表。三元組線性表的順序存儲(chǔ)是隨機(jī)稀疏矩陣的一種壓縮存儲(chǔ)表示法——三元組順序表。三元組線性表的鏈?zhǔn)酱鎯?chǔ)是隨機(jī)稀疏矩陣的另一種壓縮存儲(chǔ)表示法，因?yàn)樵谶@種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)非零元位于一個(gè)行鏈表和一個(gè)列鏈表的交匯處，就像一個(gè)“十字”，因此該鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)被形象地稱為“十字鏈表”。

二、隨機(jī)稀疏矩陣鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)

十字鏈表除了要存放非零元的信息（row，col，val），還需要存放它與同行、同列非零元之間的關(guān)系，因此需要存放兩個(gè)指針：一個(gè)是行指針rnext，用來指向同行的下一個(gè)非零元；另一個(gè)是列指針cnext，用來指向同列的下一個(gè)非零元。非零元的三個(gè)屬性信息和行、列指針信息就構(gòu)成了十字鏈表的存儲(chǔ)映像。

（一）不純粹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

對(duì)于一個(gè)規(guī)模為m×n的稀疏矩陣而言，它有m個(gè)行鏈表和n個(gè)列鏈表，如何組織這m+n個(gè)（不帶頭結(jié)點(diǎn)的）鏈表的頭指針呢？一種簡(jiǎn)單的處理方法是，用兩個(gè)大小分別為m和n的指針數(shù)組分別存放m個(gè)行鏈表的頭指針和n個(gè)列鏈表的頭指針。圖1給出了一個(gè)隨機(jī)稀疏矩陣實(shí)例，圖2給出了該實(shí)例的如上所述鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖。此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)之所以不純粹是因?yàn)樗雰蓚€(gè)指針數(shù)組。能否不引入指針數(shù)組解決存儲(chǔ)m+n個(gè)鏈表的頭指針問題呢？回答是肯定的，我們可以僅僅利用十字鏈表的存儲(chǔ)結(jié)點(diǎn)來解決這個(gè)問題。

（二）純粹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

隨機(jī)稀疏矩陣更純粹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是：稀疏矩陣每一行的非零元信息用一個(gè)帶頭結(jié)點(diǎn)的單鏈環(huán)存儲(chǔ)、每一列的非零元信息也用一個(gè)帶頭結(jié)點(diǎn)的單鏈存儲(chǔ)。頭結(jié)點(diǎn)的結(jié)構(gòu)和表結(jié)點(diǎn)的結(jié)構(gòu)相同。可以用m+n個(gè)頭結(jié)點(diǎn)分別來擔(dān)當(dāng)m+n個(gè)單鏈環(huán)的頭結(jié)點(diǎn)的角色。接下來需要思考的是這m+n個(gè)頭結(jié)點(diǎn)該如何來組織的問題。本文選擇用單鏈環(huán)來解決這個(gè)問題：m個(gè)行頭結(jié)點(diǎn)、n個(gè)列頭結(jié)點(diǎn)分別構(gòu)成一個(gè)單鏈環(huán)。同時(shí)，我們?cè)僖胍粋€(gè)總頭結(jié)點(diǎn)，它既作為m個(gè)行頭結(jié)點(diǎn)單鏈環(huán)的頭結(jié)點(diǎn)又作為n個(gè)列頭結(jié)點(diǎn)單鏈環(huán)的頭結(jié)點(diǎn)。此外，可以用總頭結(jié)點(diǎn)的非指針域存儲(chǔ)稀疏矩陣的規(guī)模信息。指向總頭結(jié)點(diǎn)的指針成為整個(gè)十字鏈表的唯一入口。隨機(jī)稀疏矩陣C對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)示意圖如圖3所示。

（三）存儲(chǔ)效率更高的純粹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

上述十字鏈表存儲(chǔ)結(jié)構(gòu)需要m+n個(gè)頭結(jié)點(diǎn)，能否將頭結(jié)點(diǎn)減少為max（m，n）個(gè)？本文選擇用單鏈環(huán)的形式來組織這max（m，n）個(gè)頭結(jié)點(diǎn)。同樣，我們需要再引入一個(gè)總頭結(jié)點(diǎn)，它是max（m，n）個(gè)頭結(jié)點(diǎn)構(gòu)成的單鏈環(huán)的頭結(jié)點(diǎn)。用總頭結(jié)點(diǎn)的rnext指針域指向第一頭結(jié)點(diǎn)，用總頭結(jié)點(diǎn)的非指針域存儲(chǔ)稀疏矩陣的規(guī)模信息。指向總頭結(jié)點(diǎn)的指針是整個(gè)十字鏈表的唯一入口。為了得到稀疏矩陣這種效率更高的純粹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，我們需要將頭結(jié)點(diǎn)原來的一個(gè)非指針域改造為指針域。隨機(jī)稀疏矩陣C對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)示意圖如圖4所示。

三、結(jié)束語

矩陣是一種在科學(xué)與工程計(jì)算問題中常用的數(shù)學(xué)對(duì)象，高階矩陣對(duì)內(nèi)存容量要求較高，矩陣的壓縮存儲(chǔ)是一個(gè)值得研究的課題。本文主要討論隨機(jī)稀疏矩陣的壓縮存儲(chǔ)問題，重點(diǎn)討論了它的三種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。深化了數(shù)據(jù)結(jié)構(gòu)課程中數(shù)組相關(guān)內(nèi)容的教學(xué)和學(xué)習(xí)，加強(qiáng)了對(duì)學(xué)生計(jì)算思維（如何將邏輯關(guān)系映射到存儲(chǔ)器）的訓(xùn)練。

參考文獻(xiàn)：

[1]余艷.數(shù)據(jù)結(jié)構(gòu)實(shí)踐教學(xué)內(nèi)容設(shè)置的分析與思考[J].實(shí)驗(yàn)技術(shù)與管理，2014，31（4）：170-173.

[2]董麗薇.“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)方法的改進(jìn)[J].沈陽師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，30（2）：307-309.

[3]楊程，劉濤，范勇等.基于虛擬現(xiàn)實(shí)的數(shù)據(jù)結(jié)構(gòu)三維動(dòng)態(tài)教學(xué)系統(tǒng)[J].實(shí)驗(yàn)技術(shù)與管理，2012，1（1）：74-78.

[4]沈華.數(shù)據(jù)結(jié)構(gòu)課內(nèi)實(shí)踐教學(xué)方案[J].實(shí)驗(yàn)室研究與探索，2013，32（10）：396-400.

[5]沈華.數(shù)據(jù)結(jié)構(gòu)、算法和程序之間關(guān)系的探討[J].計(jì)算機(jī)教育，2013，（04）：58-61.

[6]沈華.數(shù)據(jù)結(jié)構(gòu)入門教學(xué)中的實(shí)例法[J].計(jì)算機(jī)教育，2013，（24）：64-66.

[7]沈華，楊曉艷，馬馳，等.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用：C語言描述[M].北京：機(jī)械工業(yè)出版社，2011.

[8]Korsh J F，Garrett L J.Data structures，algorithms and program style using c [M].Boston，PWS-Kent Publishing Co，US，1986.endprint