基本介紹
- 中文名：十字鍊表
- 外文名：Orthogonal List
- 屬於：有向圖的另一種鏈式存儲結構
- 優點：達到高效的存取效果
十字鍊表的構成,十字鍊表,舉例,
十字鍊表的構成
用鍊表模擬矩陣的行（或者列，這可以根據個人喜好來定），然後，再構造代表列（或者是行）的鍊表，將每一行中的元素節點插入到對應的列中去。十字鍊表的邏輯結構就像是一個圍棋盤（沒見過，你就想一下蒼蠅拍，這個總見過吧!），而非零元就好像是在棋盤上放的棋子，總共占的空間就是，確定那些線的表頭節點和那些棋子代表的非零元節點。最後，我們用一個指針指向這個棋盤，這個指針就代表了這個稀疏矩陣。
十字鍊表
十字鍊表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鍊表。在十字鍊表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。
十字鍊表之於有向圖，類似於鄰接表之於無向圖。
舉例
#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*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; /*生成結點*/ 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; /*完成插入*/ } }}