Shulou(Shulou.com)06/03 Report--

This article will explain in detail how to create and traverse the cross list in C language. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

What is a cross-linked list?

The cross-linked list is often used to represent the sparse matrix and can be regarded as a linked representation of the sparse matrix. Therefore, the cross-linked list is introduced in the context of the sparse matrix. However, the application of cross-linked list goes far beyond sparse matrix, and all structures with orthogonal relations can be stored in cross-linked list.

Second, the storage structure of the cross list

1. Storage structure for summarizing points

M: total rows

N: total number of columns

Len: total number of elements

Row_head: an array of row pointers (you can quickly navigate to a row through an array of row pointers)

Col_head: array of column pointers

two。 Storage structure for a single node

Row: number of Lin

Col: number of columns

Value: stored element value

Right: right pointer domain

Down: lower pointer domain

3. For each row, record the position of the header node of each row through an array of pointers, which is the same for the column

4. Through a row, the elements of a column can be quickly accessed

Third, code implementation 1. Introduce the header file and define the structure # include # include/* the summary point structure type of the cross-linked list is defined as follows: * / typedef struct OLNode {int row, col; / * row and column subscript of non-zero elements * / int value; struct OLNode* right; / * row table of non-zero elements, successor link field of the list * / struct OLNode* down;} OLNode, * OLink / * the structure type of a single node is defined as follows: * / typedef struct {OLink* row_head; / * header pointer vector of row and column list * / OLink* col_head; int m, n, len; / * number of rows, columns, number of non-zero elements * /} CrossList;void out_M (CrossList M); void CreateCrossList (CrossList* M); 2. Establish a cross-linked list void CreateCrossList (CrossList* M) {int m, n, t, I, j, e; OLNode* pbank / unit structural pointer OLNode* Q-position hand * use the cross-linked list storage structure to create a sparse matrix M / printf ("Please enter the number of rows, columns and the number of non-zero elements\ n") Scanf_s ("% d%d%d", & m, & n, & t); / * enter the number of rows, columns and non-zero elements of M * / M-> m = m; M-> n = n; M-> len = t; M-> row_head = (OLink*) malloc ((m + 1) * sizeof (OLink)) M-> col_head = (OLink*) malloc ((n + 1) * sizeof (OLink)); / * initialize row and column header pointer vectors, linked lists with empty row and column lists * / for (int h = 0; h)

Row_ head [h] = NULL;} for (int t = 0; t

Col_ [t] = NULL;} printf ("Please enter the element stored in row I, column j, ending with 0\ n"); for (scanf_s ("% d%d%d", & I, & j, & e); I! = 0 Scanf_s ("% d%d%d", & I, & j, & e) {p = (OLNode*) malloc (sizeof (OLNode)); p-> row = I; p-> col = j; p-> value = e / * generate a node * / * insert a node in a cross-linked list. For a row pointer array and a column pointer array, it is similar to the insertion operation in a single linked list * / if (M-> row_ [I] = = NULL) {M-> row_ [I] = p; p-> right = NULL } else {/ * find the insertion position in the row table * / for (Q = M-> row_ head [I]; Q-> right & & Q-> right- > col

Right); / * empty loop body * / p-> right = Q-> right; Q-> right = p; / * finish inserting * /} if (M-> col_ [j] = = NULL) {M-> col_ [j] = p P-> down = NULL;} else {/ * find the insertion position in the list * / for (Q = M-> col_ head [j]; Q-> down & & Q-> down- > row

Down); / * empty loop body * / p-> down = Q-> down; Q-> down = p; / * complete insertion * /}} 3. Traversing the cross list void out_M (CrossList M) {/ * the idea of traversing the cross list: it can be implemented with a double for loop, traversing the output * / int I for each column in each row; OLNode* p; char ch / * Total number of rows, total columns, total number of non-zero elements of the output matrix * / printf ("\ nTotal rows% d total columns% d non-zero elements% d\ n", M.m. Magi M.n ·M.len); for (I = 1; I row, p-> col, p-> value); p = p-> right } printf ("\ n");}} 4. The idea of calling the function void out_M (CrossList M) {/ * traversing the cross-linked list: it can be implemented with a double for loop, traversing the output * / int I for each column in each row; OLNode* p; char ch / * Total number of rows, total columns, total number of non-zero elements of the output matrix * / printf ("\ nTotal rows% d total columns% d non-zero elements% d\ n", M.m. Magi M.n ·M.len); for (I = 1; I row, p-> col, p-> value); p = p-> right }} printf ("\ n");}} this is the end of the article on "how to create and traverse the Cross list in C language". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.