C語言如何創(chuàng)建及遍歷十字鏈表

這篇文章將為大家詳細(xì)講解有關(guān)C語言如何創(chuàng)建及遍歷十字鏈表，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

一、十字鏈表是什么？

十字鏈表常用于表示稀疏矩陣，可視作稀疏矩陣的一種鏈?zhǔn)奖硎荆虼?，這里以稀疏矩陣為背景介紹十字鏈表。不過，十字鏈表的應(yīng)用遠(yuǎn)不止稀疏矩陣，一切具有正交關(guān)系的結(jié)構(gòu)，都可用十字鏈表存儲。

二、十字鏈表的存儲結(jié)構(gòu)

1.用于總結(jié)點的存儲結(jié)構(gòu)

m:總行數(shù)

n:總列數(shù)

len:總元素個數(shù)

row_head:行指針數(shù)組（通過行指針數(shù)組可以快速定位到某一行）

col_head:列指針數(shù)組

2.用于單個節(jié)點的存儲結(jié)構(gòu)

row :行數(shù)

col:列數(shù)

value:存儲的元素值

right :右指針域

down:下指針域

3.對于每一行，通過指針數(shù)組記錄下每一行的頭節(jié)點位置，對于列來說相同

4.通過對某一行，某一列的元素可以快速訪問

三、代碼實現(xiàn)

 1.引入頭文件并定義結(jié)構(gòu)體

#include <stdio.h> 
#include<stdlib.h>
/*十字鏈表的總結(jié)點結(jié)構(gòu)類型定義如下：*/
typedef struct OLNode
{
	int row, col; /*非零元素的行和列下標(biāo)*/
	int value;
	struct OLNode* right; /*非零元素所在行表、列表的后繼鏈域*/
	struct OLNode* down;
}OLNode,  *OLink;
 
/*單個節(jié)點結(jié)構(gòu)類型定義如下：*/
typedef struct
{
	OLink* row_head; /*行、列鏈表的頭指針向量*/
	OLink* col_head;
	int m, n, len; /*稀疏矩陣的行數(shù)、列數(shù)、非零元素的個數(shù)*/
}CrossList;
void out_M(CrossList M);
void CreateCrossList(CrossList* M);

2.建立十字鏈表

void CreateCrossList(CrossList* M)
{
	int m, n, t, i, j, e;
	OLNode* p;//單元的結(jié)構(gòu)體指針  
	OLNode* q;
/*采用十字鏈表存儲結(jié)構(gòu)，創(chuàng)建稀疏矩陣M*/
	printf("請輸入行數(shù),列數(shù)和非零元素的個數(shù)\n");
	scanf_s("%d%d%d", &m, &n, &t); /*輸入M的行數(shù),列數(shù)和非零元素的個數(shù)*/
	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結(jié)束\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; /*生成結(jié)點*/
		/*在十字鏈表中插入節(jié)點，對于行指針數(shù)組和列指針數(shù)組分開看，類似于單鏈表中的插入操作*/
		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); /*空循環(huán)體*/
			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); /*空循環(huán)體*/
			p->down = q->down;
			q->down = p; /*完成插入*/
		}
	}
}

3.遍歷十字鏈表

void out_M(CrossList M)
{
	/*遍歷十字鏈表的思想：可采用雙重for循環(huán)實現(xiàn)，對于每一行中的每一列進(jìn)行遍歷輸出*/
	int i;
	OLNode* p;
	char ch;
	/*  輸出矩陣的總行數(shù)、總列數(shù)、非零元素總個數(shù) */
	printf("\n  總行數(shù)有%d    總列數(shù)有%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行的數(shù)據(jù)如下\n", i);
			while (p) {
				printf("  (%3d%3d%4d) ", p->row, p->col, p->value);
				p = p->right;
			}
		}
		printf("\n");
	}
}

4.調(diào)用函數(shù)

void out_M(CrossList M)
{
	/*遍歷十字鏈表的思想：可采用雙重for循環(huán)實現(xiàn)，對于每一行中的每一列進(jìn)行遍歷輸出*/
	int i;
	OLNode* p;
	char ch;
	/*  輸出矩陣的總行數(shù)、總列數(shù)、非零元素總個數(shù) */
	printf("\n  總行數(shù)有%d    總列數(shù)有%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行的數(shù)據(jù)如下\n", i);
			while (p) {
				printf("  (%3d%3d%4d) ", p->row, p->col, p->value);
				p = p->right;
			}
		}
		printf("\n");
	}
}

關(guān)于“C語言如何創(chuàng)建及遍歷十字鏈表”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。