~~~~????有需求才有供應(yīng)，很多東西，都是為了解決實際問題才出現(xiàn)的，項目中出現(xiàn)了很多稀疏矩陣，而且需要對他們進行運算，而十字鏈表就是為了解決稀疏矩陣而出現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)。

稀疏矩陣

~~~~????稀疏矩陣（英語：sparse matrix），在數(shù)值分析中，是其元素大部分為零的矩陣。反之，如果大部分元素都非零，則這個矩陣是稠密的，通常這個系數(shù)被認為是5%。在科學(xué)與工程領(lǐng)域中求解線性模型時經(jīng)常出現(xiàn)大型的稀疏矩陣。
~~~~????在使用計算機存儲和操作稀疏矩陣時，經(jīng)常需要修改標準算法以利用矩陣的稀疏結(jié)構(gòu)。由于其自身的稀疏特性，通過壓縮可以大大節(jié)省稀疏矩陣的內(nèi)存代價。更為重要的是，由于過大的尺寸，標準的算法經(jīng)常無法操作這些稀疏矩陣。

三元組

~~~~????對于矩陣，我們第一想法就是使用二維數(shù)組來存儲，但是稀疏矩陣的元素大部分都是零，而且稀疏矩陣的尺寸一般都比較大，這個時候我們?nèi)绻苯邮褂枚S數(shù)組，會浪費很多的空間，所有通常我們需要對稀疏矩陣進行壓縮，三元組就是一種稀疏矩陣壓縮保存的方法。
~~~~????三元組是指形如$((x,y),z)$的集合（這就是說，三元組是這樣的偶，其第一個射影亦是一個偶），常簡記為$(x,y,z)$。
~~~~????三元組是計算機專業(yè)的一門公共基礎(chǔ)課程——數(shù)據(jù)結(jié)構(gòu)里的概念。主要是用來存儲稀疏矩陣的一種壓縮方式，也叫三元組表。
~~~~????三元組有不同的實現(xiàn)方法，假設(shè)以順序表存儲結(jié)構(gòu)來表示三元組，稱為三元組順序表。
結(jié)構(gòu)如下

#defube NAXSIZE 2500 typedef struct{int i, j; //該非零元的行下標和列下標ElemType e; }Triple; typedef struct{Triple data[MAXSIZE + 1];//非零三元數(shù)組標，data[0]沒有使用int mu, nu, tu;//矩陣的行數(shù)，列數(shù)，非零元個數(shù) }TSMatrix;

~~~~????注意，data域中表示非零元的三元組是以行序為主序順序排列的，如果不排序，你會發(fā)現(xiàn)你操作和訪問數(shù)據(jù)時，時間基本都花在查詢數(shù)據(jù)上了。對于三元組，我們可以進行一些運算，都是很容易實現(xiàn)的，比如轉(zhuǎn)置，相加，相減。
~~~~????三元組相比十字鏈表的缺點（暫時只能想到這些）

• 1、增加或減少矩陣中的非零元素，都需要進行數(shù)據(jù)的移動
• 2、大小固定，非零數(shù)據(jù)很少時，會浪費很多的空間，過多時無法保存
• 3、查找元素比較慢（時間復(fù)雜度）
• 4、矩陣的運算數(shù)據(jù)較慢（時間復(fù)雜度）

十字鏈表

~~~~????十字鏈表（英語：Orthogonal linked list）是計算機科學(xué)中的一種高級數(shù)據(jù)結(jié)構(gòu)，在Linux內(nèi)核中應(yīng)用廣泛。具體說，一個二維十字鏈表是鏈表的元素同時鏈接左右水平鄰結(jié)點與上下垂直鄰結(jié)點。
~~~~????當(dāng)稀疏矩陣的非零元個數(shù)和位置在操作過程中變化較大時，就不宜使用順序表存儲結(jié)構(gòu)的三元組來保存稀疏矩陣；這個時候我們采用的時十字鏈表。
十字鏈表節(jié)點結(jié)構(gòu)

typedef struct OLNode { int LineNumber, ColumneNumber; //行號與列號 ElemType value; //值 struct OLNode *right, *down; //同行、同列下一個元素的指針 }OLNode, *OList; typedef struct{OList *rhead, *chead; //行和列鏈表頭指針向量基址int mu,nu,tu; //稀疏矩陣的行數(shù)，列數(shù)和非零元個數(shù) }CrossList;

~~~~????每一個非零元可用一個含5個域的節(jié)點表示，其中i，j和e這3個域分別表示該非零元所在的行、列和非零元的值，向右域right用以鏈接同一行中下一個非零元，向下域down用來鏈接同一列下一個非零元，同一行的非零元通過right鏈接形成一個線性鏈表，同一列的非零元通過down鏈接形成一個線性表，每個非零元既是某個行鏈表中的節(jié)點，也是某一個列鏈表中的節(jié)點，整個矩陣構(gòu)成了一個十字交叉的鏈表，而樣的鏈表存儲結(jié)構(gòu)稱為十字鏈表。

附上十字鏈表實現(xiàn)（百度抄的）

#include <malloc.h> #include <stdio.h> /*十字鏈表的結(jié)構(gòu)類型定義如下：*/ typedef struct OLNode {int row,col; /*非零元素的行和列下標*/int value;struct OLNode *right; /*非零元素所在行表、列表的后繼鏈域*/struct OLNode *down; } OLNode, *OLink; typedef struct {OLink *row_head; /*行、列鏈表的頭指針向量*/OLink *col_head;int m,n,len; /*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/ } CrossList; /*建立稀疏矩陣的十字鏈表的算法*/ void CreateCrossList(CrossList *M) {int m, n, t, i, j, e;OLNode* p;OLNode* q;/*采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣M*/scanf("%d%d%d", &m,&n,&t); /*輸入M的行數(shù),列數(shù)和非零元素的個數(shù)*/M->m=m;M->n=n;M->len=t;if(!(M->row_head=(OLink *)malloc(m*sizeof(OLink))))exit(OVERFLOW);if(!(M->col_head=(OLink * )malloc(n*sizeof(OLink))))exit(OVERFLOW);/*初始化行、列，頭指針指向量，各行、列鏈表為空的鏈表*/for(int h=0; h<m+1; h++){M->row_head[h] = NULL;}for(int t=0; t<n+1; t++){M->col_head[t] = NULL;}for( scanf("%d%d%d", &i,&j,&e); e!=0; scanf("%d%d%d", &i,&j,&e)){if(!(p=(OLNode *)malloc(sizeof(OLNode))))exit( OVERFLOW);p->row=i;p->col=j;p->value=e; /*生成結(jié)點*/if(M->row_head[i]==NULL)M->row_head[i]=p;p->right=NULL;else{/*尋找行表中的插入位置*/for(q=M->row_head[i]; q->right&&q->right->col<j; q=q->right); /*空循環(huán)體*/p->right=q->right;q->right=p; /*完成插入*/}if(M->col_head[j]==NULL)M->col_head[j]=p;p->down=NULL;else{/*尋找列表中的插入位置*/for(q=M->col_head[j]; q->down&&q->down->row<i; q=q->down); /*空循環(huán)體*/p->down=q->down;q->down=p; /*完成插入*/}} }

總結(jié)

以上是生活随笔為你收集整理的十字链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。