• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)及相加算法實(shí)現(xiàn)

      2017-04-17 10:42:37鄔恩杰張靜
      電腦知識(shí)與技術(shù) 2016年36期

      鄔恩杰 張靜

      摘要:帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)是稀疏矩陣壓縮存儲(chǔ)的一種實(shí)用的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。文中描述了稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)及基于此鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的相加運(yùn)算算法,并應(yīng)用C++類模板完成矩陣相加算法的具體實(shí)現(xiàn),對(duì)類中參數(shù)的抽象化,提高了程序代碼的復(fù)用性。

      關(guān)鍵詞:稀疏矩陣;行指針數(shù)組;鏈表存儲(chǔ)結(jié)構(gòu);矩陣相加算法

      中圖分類號(hào):TP311 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(2016)36-0035-03

      1稀疏矩陣

      矩陣在科學(xué)計(jì)算中的應(yīng)用十分廣泛,而且隨著計(jì)算機(jī)應(yīng)用的發(fā)展,大量出現(xiàn)處理高階矩陣問(wèn)題,有的甚至達(dá)到幾十萬(wàn)階、幾千億個(gè)元素,這就有點(diǎn)要挑戰(zhàn)計(jì)算機(jī)的內(nèi)存容量了。然而,在大量的高階矩陣問(wèn)題中,絕大部分元素是零值,且非零值的分布沒(méi)有一定的規(guī)律。當(dāng)非零元素所占比例小于等于25%~30%時(shí),我們稱這種含有大量零元素的矩陣為稀疏矩陣。壓縮這種零元素占據(jù)的空間,節(jié)省內(nèi)存同時(shí)能夠避免大量零元素進(jìn)行的無(wú)意義運(yùn)算,大大提高運(yùn)算效率。[1]

      稀疏矩陣壓縮存儲(chǔ)的順序方式有三元組表、偽地址表示法等;鏈?zhǔn)浇Y(jié)構(gòu)有十字鏈表結(jié)構(gòu)、帶行指針數(shù)組的鏈表結(jié)構(gòu)等。本文著重介紹帶行指針數(shù)組的鏈表結(jié)構(gòu)及基于此結(jié)構(gòu)的稀疏矩陣類對(duì)象構(gòu)造、輸入、輸出、相加等基本算法。

      2稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)[2]

      稀疏矩陣中的每行對(duì)應(yīng)一個(gè)單鏈表,每個(gè)單鏈表都有個(gè)表頭指針,為了便于訪問(wèn)每一個(gè)單鏈表,需要使用一個(gè)行指針數(shù)組,該數(shù)組中的第i個(gè)元素用來(lái)存儲(chǔ)矩陣中第i行對(duì)應(yīng)的單鏈表的表頭指針,該指針指向第i行第一個(gè)非零結(jié)點(diǎn),若該行無(wú)非零元,則該指針為空。

      帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)中,把具有相同行號(hào)的三元組結(jié)點(diǎn)按照列號(hào)從小到大的順序鏈接成一個(gè)單鏈表,每個(gè)結(jié)點(diǎn)由3個(gè)域組成:非零元所在列的列號(hào)(col),非零元的值(value)及指向本行下一個(gè)非零元的指針(next)。例如,稀疏矩陣A6×7如圖1及其帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)如圖2所示。

      3稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)類型

      3.1結(jié)點(diǎn)類定義

      稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)中每一個(gè)非零元結(jié)點(diǎn)的類的C++模板如下:[3]

      template

      structTripleNode

      {int col;

      T value;

      TripleNode*next;

      TripleNode& operator=(TripleNode&x)

      {col=x.col;value=x.value;next=NULL;return *this;}}

      3.2帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)表示的稀疏矩陣類

      帶行指針的單鏈表存儲(chǔ)結(jié)構(gòu)表示的稀疏矩陣類包含稀疏矩陣行數(shù)、列數(shù)及非零元個(gè)數(shù)及動(dòng)態(tài)行指針數(shù)組4個(gè)私有成員及稀疏矩陣的構(gòu)造函數(shù)、析構(gòu)函數(shù)、輸入、輸出、轉(zhuǎn)置、相加、相乘等公有成員函數(shù)的聲明,類的C++模板如下:

      template

      classSparseMatrix

      {private:

      int Rows,Cols,Terms;

      TripleNode **PROWS;

      public:

      SparseMatrix(int rc,int cc,int tc);

      ~SparseMatrix(){delete []PROWS;}

      void Add(SparseMatrix&b,SparseMatrix&c);

      void create_SparseMatrix();

      void print_SparseMatrix();};

      4基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)基本運(yùn)算

      4.1構(gòu)造函數(shù)

      template

      SparseMatrix(intrc,intcc,inttc)

      { Rows=rc; Cols=cc; Terms=tc;

      PROWS=newTwo_tuple *[Rows];

      for (intI=0;I

      4.2 建立帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)

      在實(shí)例化稀疏矩陣時(shí)通過(guò)構(gòu)造函數(shù)建立只有行指針數(shù)組的空的稀疏矩陣。在此基礎(chǔ)上按行優(yōu)先,列號(hào)從小到大順序輸入非零元所在行、列和值,申請(qǐng)一個(gè)結(jié)點(diǎn)所需存儲(chǔ)空間,并將非零元的列號(hào)和值存入相應(yīng)域,按列號(hào)從小到大的順序?qū)⒋私Y(jié)點(diǎn)插入到對(duì)應(yīng)行尾部。構(gòu)造函數(shù)及建立鏈表結(jié)構(gòu)代碼:

      template

      voidcreate_SparseMatrix()

      { int r,c;

      T v;

      Two_tuple *p,*q,*s;

      for (int i=0;i

      {cin>>r>>c>>v;

      s=newTwo_tuple;

      s->col=c;s->value=v;s->next=NULL;

      p=PROWS[r];

      q=p;

      while(p)

      { q=p;p=p->next;}

      if (p==q){ PROWS[r]=s;} else { q->next=s;}}}

      4.3 基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)稀疏矩陣相加算法

      兩個(gè)矩陣相加前提條件是兩個(gè)矩陣行數(shù)和列數(shù)分別對(duì)應(yīng)相等。相加的結(jié)果仍是同型矩陣。設(shè)有兩個(gè)m×n矩陣A和B,相加結(jié)果設(shè)為C,也是一個(gè)m×n的矩陣。對(duì)于C中每個(gè)元素C[i][j]有以下三種情況:[4]

      [CIJ=aijbijaij+bijbij=0aij=0aij=0且bij=0 ]

      在帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)稀疏矩陣相加算法思想是:分別建立矩陣A和B的帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)。相加算法從矩陣的第一行起逐行進(jìn)行。對(duì)每一行都從行鏈表的頭指針開(kāi)始,分別找到A和B在該中的第一個(gè)非零元結(jié)點(diǎn)后開(kāi)始比較,然后按不同情況分別處理。設(shè)兩個(gè)指針p和q分別初始化為指向A、B鏈表存儲(chǔ)結(jié)構(gòu)的第一行第一個(gè)非零元結(jié)點(diǎn),當(dāng)p、q都非空時(shí)(意味著p、q所指的當(dāng)前行沒(méi)有遍歷到行尾),生成C中結(jié)點(diǎn)s的三種情況可按如下處理。

      1)若p->col < q->col或者 q==NULL時(shí),則將p結(jié)點(diǎn)數(shù)據(jù)復(fù)制到s,p指針向右移動(dòng),指向本行下一個(gè)非零元。

      2)若p->col > q->col或者 p==NULL時(shí),則將q結(jié)點(diǎn)數(shù)據(jù)復(fù)制到s,q指針向右移動(dòng),指向本行下一個(gè)非零元。

      3)若p->col == q->col且p->value + q->value[≠]0,則將q結(jié)點(diǎn)數(shù)據(jù)復(fù)制到s,s->value=p->value+q->value, p和q指針?lè)謩e向右移動(dòng),指向各自行下一個(gè)非零元。

      同理,如此重復(fù)處理其余每一行,直到所有結(jié)點(diǎn)都被合并到結(jié)果矩陣中。

      template

      voidAdd(SparseMatrix&b,SparseMatrix&C)

      { TripleNode *p,*q,*s,*t;

      int i;

      T v;

      if (Rows != b.Rows||Cols != b.Cols)

      { cerr<<"Incompatible Matrix!"<

      for ( i =0;i

      { p = PROWS[i];

      q = b.PROWS[i];

      while(p && q)

      { s=newTripleNode ;

      if (p->col< q->col)

      { *s=*p;C.insert(i,s); C.Terms++;p=p->next;}

      elseif (p->col> q->col)

      { *s=*q;C.insert(i,s); C.Terms++;q=q->next;}

      else

      {v=p->value+q->value;

      if (v)

      { *s=*p;s->value=v;C.insert(i,s);C.Terms++;}

      p=p->next;q=q->next;}}

      while(p)

      { s=newTripleNode ; *s=*p;

      C.insert(I,s);C.Terms++;p=p->next;}

      while(q)

      { s=newTripleNode ;*s=*q;

      C.insert(i,s);C.Terms++;q=q->next; } }}

      4.4 基于帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)的稀疏矩陣輸出算法

      從行指針數(shù)組的第一行開(kāi)始,逐行遍歷并輸入鏈表中非零元的三元組形式。

      template

      voidprint_SparseMatrix()

      {Two_tuple *p;

      cout<<"rows:"<

      for (int i =0;i

      { p=PROWS[i];

      while(p)

      { cout<<"("<col<<","<value<<')'<

      p=p->next;}}}

      5算法性能分析

      在稀疏矩陣帶行指針數(shù)組的單鏈表存儲(chǔ)結(jié)構(gòu)上,建立單鏈表存儲(chǔ)結(jié)構(gòu)的算法時(shí)間復(fù)雜度是O(Rows+Terms)。相加算法的主要過(guò)程是對(duì)A和B單鏈表逐行進(jìn)行掃描,其時(shí)間性能主要取決于A、B的行數(shù)Rows和非零元素的個(gè)數(shù)Terms,因此,該矩陣相加算法時(shí)間復(fù)雜度為O(2*Rows+A.Terms+B.terms)。當(dāng)稀疏矩陣的非零元素的個(gè)數(shù)Terms遠(yuǎn)遠(yuǎn)小于矩陣的行、列數(shù)時(shí),矩陣相加算法的時(shí)間復(fù)雜度比采用二維數(shù)組存儲(chǔ)時(shí)的時(shí)間復(fù)雜度O(Rows [× ]Cols)要好很多。

      參考文獻(xiàn):

      [1] 李平,王秀英.計(jì)算機(jī)軟件技術(shù)基礎(chǔ)[M].北京:機(jī)械工業(yè)出版社,2015:61-63。

      [2] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程(C/C++描述)[M].北京:清華大學(xué)出版社,2004:98-99.

      [3] 鄭莉,董淵,何江舟.C++語(yǔ)言程序設(shè)計(jì)[M].北京:清華大學(xué)出版社,2010:309-314.

      [4] 張小莉,王苗,羅文劼.數(shù)據(jù)結(jié)構(gòu)與算法[M].3版.北京:機(jī)械工業(yè)出版社,2016:97-98.

      金平| 永安市| 稷山县| 五河县| 兴业县| 基隆市| 紫阳县| 石渠县| 鄢陵县| 仪征市| 台南县| 武鸣县| 涟源市| 长岭县| 乌兰县| 蓝田县| 资兴市| 乌审旗| 崇左市| 乳山市| 雷州市| 怀来县| 武宣县| 苍山县| 陆川县| 新绛县| 蓬莱市| 汉沽区| 新疆| 镇巴县| 太和县| 磐石市| 沁源县| 乐陵市| 通州区| 鄯善县| 扎鲁特旗| 长泰县| 嘉义县| 济宁市| 台山市|