498
十字鏈表的定義及C語言描述
十字鏈表常用於表示稀疏矩陣，可視作稀疏矩陣的一種鏈式表示，因此，這裏以稀疏矩陣為背景介紹十字鏈表。不過，十字鏈表的應用遠不止稀疏矩陣，一切具有正交關係的結構，都可用十字鏈表存儲。
1、存儲方式
(a)稀疏矩陣中每個非0元素對應一個十字鏈表結點，每個結點的結構為
其中各字段的含意為：
row──元素在稀疏矩陣中的行號
col──元素在稀疏矩陣中的列號
val──元素值
down──指向同列中下一個非0元素結點
right──指向同行中下一個非0元素結點
(b)每行/列設一個表頭結點（結構同元素結點），以down/right為鏈構成循環鏈表，即第i列頭結點的down指向該列上第1個非0元素，第i行頭結點的right指向該行第1個非0元素。第i列/行上最後一個結點的down/right指向該列/行的頭結點。若某列/行中無非0元素，則令它的頭結點down/right域指向自己。
(c)設一個總頭結點（結構同元素結點），令總頭結點和各個列/行頭結點用val字段，按列/行序構成一個循環單鏈表。
(d)可令總頭結點的row，col與val分別表示矩陣的最大行號、列號與非0元素個數，而down/right指向第1列/行的頭結點。該總頭結點可作為整個十字鏈表的代表。
(e)由於行與列的頭結點分別使用right域與down域(不同時使用)，故第i列與第i行頭結點可合用同一個頭結點（對所有可能的i），以節省存儲空間。
(f)有時，為了快速訪問行/列頭結點，設置一個一維數組headNodes[]，使headNodes[i]指向i行/列的頭結點。但這並不是必須的，因為各行/列的頭結點已形成了一個循環單鏈表，故若已知十字鏈表總頭結點，即可搜索到任一頭結點。
設有一個如下形式的矩陣，它所對應的十字鏈表如下圖所示。
稀疏矩陣的十字鏈表存儲表示：
#include <malloc.h>
#include <stdio.h>
/*十字鏈表的結構類型定義如下：*/
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; /*稀疏矩陣的行數、列數、非零元素的個數*/
}CrossList;
/*建立稀疏矩陣的十字鏈表的算法*/
void CreateCrossList(CrossList *M)
{
int m, n, t, i, j, e;
OLNode* p;
OLNode* q;
/*采用十字鏈表存儲結構，創建稀疏矩陣M*/
scanf("%d%d%d", &m,&n,&t); /*輸入M的行數,列數和非零元素的個數*/
M->m=m;
M->n=n;
M->len=t;
if(!(M->row_head=(OLink *)malloc((m+1)*sizeof(OLink))))
exit(OVERFLOW);
if(!(M->col_head=(OLink * )malloc((n+1)*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);i!=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; /*生成結點*/
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); /*空循環體*/
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); /*空循環體*/
p->down=q->down;
q->down=p; /*完成插入*/
}
}
}
最後更新：2017-04-03 05:39:11