C語言數據結構創建及遍歷十字鏈表
本文需要讀者有一定的代碼基礎,瞭解指針,鏈表,數組相關知識。
一、十字鏈表是什麼?
十字鏈表常用於表示稀疏矩陣,可視作稀疏矩陣的一種鏈式表示,因此,這裡以稀疏矩陣為背景介紹十字鏈表。不過,十字鏈表的應用遠不止稀疏矩陣,一切具有正交關系的結構,都可用十字鏈表存儲。
二、十字鏈表的存儲結構
1.用於總結點的存儲結構
m
:總行數
n
:總列數
len
:總元素個數
row_head
:行指針數組(通過行指針數組可以快速定位到某一行)
col_head
:列指針數組
2.用於單個節點的存儲結構
row
:行數
col
:列數
value
:存儲的元素值
right
:右指針域
down
:下指針域
3.對於每一行,通過指針數組記錄下每一行的頭節點位置,對於列來說相同
4.通過對某一行,某一列的元素可以快速訪問
三、代碼實現
1.引入頭文件並定義結構體
#include <stdio.h> #include<stdlib.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 out_M(CrossList M); void CreateCrossList(CrossList* M);
2.建立十字鏈表
void CreateCrossList(CrossList* M) { int m, n, t, i, j, e; OLNode* p;//單元的結構體指針 OLNode* q; /*采用十字鏈表存儲結構,創建稀疏矩陣M*/ printf("請輸入行數,列數和非零元素的個數\n"); scanf_s("%d%d%d", &m, &n, &t); /*輸入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)); /*初始化行、列頭指針向量,各行、列鏈表為空的鏈表*/ 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; } printf("請輸入第i行,第j列中存儲的元素,以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; /*生成結點*/ /*在十字鏈表中插入節點,對於行指針數組和列指針數組分開看,類似於單鏈表中的插入操作*/ 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; /*完成插入*/ } } }
3.遍歷十字鏈表
void out_M(CrossList M) { /*遍歷十字鏈表的思想:可采用雙重for循環實現,對於每一行中的每一列進行遍歷輸出*/ int i; OLNode* p; char ch; /* 輸出矩陣的總行數、總列數、非零元素總個數 */ printf("\n 總行數有%d 總列數有%d 非零元素有%d\n", M.m,M.n,M.len); for (i = 1; i <= M.m; i++) { p = M.row_head[i]; /* 指向第i行 */ if (p) { printf("\n 第%d行的數據如下\n", i); while (p) { printf(" (%3d%3d%4d) ", p->row, p->col, p->value); p = p->right; } } printf("\n"); } }
4.調用函數
void out_M(CrossList M) { /*遍歷十字鏈表的思想:可采用雙重for循環實現,對於每一行中的每一列進行遍歷輸出*/ int i; OLNode* p; char ch; /* 輸出矩陣的總行數、總列數、非零元素總個數 */ printf("\n 總行數有%d 總列數有%d 非零元素有%d\n", M.m,M.n,M.len); for (i = 1; i <= M.m; i++) { p = M.row_head[i]; /* 指向第i行 */ if (p) { printf("\n 第%d行的數據如下\n", i); while (p) { printf(" (%3d%3d%4d) ", p->row, p->col, p->value); p = p->right; } } printf("\n"); } }
以上就是C語言數據結構創建及遍歷十字鏈表的詳細內容,更多關於C語言數據結構的資料請關註WalkonNet其它相關文章!