# 稀疏矩陣及其表示| 系列 2（使用列表和鍵字典） > 原文： [https://www.geeksforgeeks.org/sparse-matrix-representations-using-list-lists-dictionary-keys/](https://www.geeksforgeeks.org/sparse-matrix-representations-using-list-lists-dictionary-keys/) 先決條件：[稀疏矩陣及其表示集 1（使用數組和鏈接列表）](https://www.geeksforgeeks.org/sparse-matrix-representation/) 本文討論了稀疏矩陣表示的其他兩種方法。 1. 清單清單 2. 字典 **列表（LIL）** 稀疏矩陣的一種可能表示形式是列表列表（LIL）。 其中一個列表用于表示行，每行包含**三元組的列表：列索引，Value（非零元素）和地址字段，**用于非零元素。 為了獲得最佳性能，兩個列表均應按升序存儲。 [](https://media.geeksforgeeks.org/wp-content/uploads/Sparse-Matrix-List-of-Lists2.png) ``` // C program for Sparse Matrix Representation // using List Of Lists #include<stdio.h> #include<stdlib.h> #define R 4 #define C 5 // Node to represent row - list struct row_list { ????int row_number; ????struct row_list *link_down; ????struct value_list *link_right; }; // Node to represent triples struct value_list { ????int column_index; ????int value; ????struct value_list *next; }; // Function to create node for non - zero elements void create_value_node(int data, int j, struct row_list **z) { ????struct value_list *temp, *d; ????// Create new node dynamically ????temp = (struct value_list*)malloc(sizeof(struct value_list)); ????temp->column_index = j+1; ????temp->value = data; ????temp->next = NULL; ????// Connect with row list ????if ((*z)->link_right==NULL) ????????(*z)->link_right = temp; ????else ????{ ????????// d points to data list node ????????d = (*z)->link_right; ????????while(d->next != NULL) ????????????d = d->next; ????????d->next = temp; ????} } // Function to create row list void create_row_list(struct row_list **start, int row, ????????????????????int column, int Sparse_Matrix[R][C]) { ????// For every row, node is created ????for (int i = 0; i < row; i++) ????{ ????????struct row_list *z, *r; ????????// Create new node dynamically ????????z = (struct row_list*)malloc(sizeof(struct row_list)); ????????z->row_number = i+1; ????????z->link_down = NULL; ????????z->link_right = NULL; ????????if (i==0) ????????????*start = z; ????????else ????????{ ????????????r = *start; ????????????while (r->link_down != NULL) ????????????????r = r->link_down; ????????????r->link_down = z; ????????} ????????// Firstiy node for row is created, ????????// and then travering is done in that row ????????for (int j = 0; j < 5; j++) ????????{ ????????????if (Sparse_Matrix[i][j] != 0) ????????????{ ????????????????create_value_node(Sparse_Matrix[i][j], j, &z); ????????????} ????????} ????} } //Function display data of LIL void print_LIL(struct row_list *start) { ????struct row_list *r; ????struct value_list *z; ????r = start; ????// Traversing row list ????while (r != NULL) ????{ ????????if (r->link_right != NULL) ????????{ ????????????printf("row=%d \n", r->row_number); ????????????z = r->link_right; ????????????// Traversing data list ????????????while (z != NULL) ????????????{ ????????????????printf("column=%d value=%d \n", ?????????????????????z->column_index, z->value); ????????????????z = z->next; ????????????} ????????} ????????r = r->link_down; ????} } //Driver of the program int main() { ????// Assume 4x5 sparse matrix ????int Sparse_Matrix[R][C] = ????{ ????????{0 , 0 , 3 , 0 , 4 }, ????????{0 , 0 , 5 , 7 , 0 }, ????????{0 , 0 , 0 , 0 , 0 }, ????????{0 , 2 , 6 , 0 , 0 } ????}; ????// Start with the empty List of lists ????struct row_list* start = NULL; ????//Function creating List of Lists ????create_row_list(&start, R, C, Sparse_Matrix); ????// Display data of List of lists ????print_LIL(start); ????return 0; } ``` 輸出： ``` row = 1 column = 3 value = 3 column = 5 value = 4 row = 2 column = 3 value = 5 column = 4 value = 7 row = 4 column = 2 value = 2 column = 3 value = 6 ``` **鍵字典** 稀疏矩陣的另一種表示形式是 Dictionary。 對于字典的關鍵字段，使用行和列索引對，它們與矩陣的非零元素映射。 這種方法可以節省空間，但是順序訪問項目成本很高。 在 C++ 中，字典定義為 STL（標準模板庫）的地圖類。 要了解有關地圖的更多信息，請單擊下面的鏈接： [地圖基礎](http://quiz.geeksforgeeks.org/map-associative-containers-the-c-standard-template-library-stl/) ## [Recommended: Please try your approach on ***{IDE}*** first, before moving on to the solution.](https://ide.geeksforgeeks.org/) ``` // C++ program for Sparse Matrix Representation // using Dictionary #include<bits/stdc++.h> using namespace std; #define R 4 #define C 5 // Driver of the program int main() { ????// Assume 4x5 sparse matrix ????int Sparse_Matrix[R][C] = ????{ ????????{0 , 0 , 3 , 0 , 4 }, ????????{0 , 0 , 5 , 7 , 0 }, ????????{0 , 0 , 0 , 0 , 0 }, ????????{0 , 2 , 6 , 0 , 0 } ????}; ????/* Declaration of map where first field(pair of ???????row and column) represent key and second ???????field represent value */ ????map< pair<int,int>, int > new_matrix; ????for (int i = 0; i < R; i++) ????????for (int j = 0; j < C; j++) ????????????if (Sparse_Matrix[i][j] != 0) ????????????????new_matrix[make_pair(i+1,j+1)] = ????????????????????????????????Sparse_Matrix[i][j] ; ????int c = 0; ????// Iteration over map ????for (auto i = new_matrix.begin(); i != new_matrix.end(); i++ ) ????{ ????????if (c != i->first.first) ????????{ ????????????cout << "row = " << i->first.first << endl ; ????????????c = i->first.first; ????????} ????????cout << "column = " << i->first.second <<" "; ????????cout << "value = " << i->second << endl; ????} ????return 0; } ``` Output: ``` row = 1 column = 3 value = 3 column = 5 value = 4 row = 2 column = 3 value = 5 column = 4 value = 7 row = 4 column = 2 value = 2 column = 3 value = 6 ``` 參考文獻： [維基百科](https://en.wikipedia.org/wiki/Sparse_matrix)