欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言数据结构创建及遍历十字链表

程序员文章站 2022-03-10 09:11:24
目录本文需要读者有一定的代码基础,了解指针,链表,数组相关知识。一、十字链表是什么?十字链表常用于表示稀疏矩阵,可视作稀疏矩阵的一种链式表示,因此,这里以稀疏矩阵为背景介绍十字链表。不过,十字链表的应...

本文需要读者有一定的代码基础,了解指针,链表,数组相关知识。

一、十字链表是什么?

十字链表常用于表示稀疏矩阵,可视作稀疏矩阵的一种链式表示,因此,这里以稀疏矩阵为背景介绍十字链表。不过,十字链表的应用远不止稀疏矩阵,一切具有正交关系的结构,都可用十字链表存储。

二、十字链表的存储结构

1.用于总结点的存储结构

C语言数据结构创建及遍历十字链表

m:总行数

n:总列数

len:总元素个数

row_head:行指针数组(通过行指针数组可以快速定位到某一行)

col_head:列指针数组

2.用于单个节点的存储结构

C语言数据结构创建及遍历十字链表

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语言数据结构的资料请关注其它相关文章!