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

目录
  • 一、十字链表是什么?
  • 二、十字链表的存储结构
  • 三、代码实现
    • 1.引入头文件并定义结构体
    • 2.建立十字链表
    • 3.遍历十字链表
    • 4.调用函数

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

一、十字链表是什么?

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

二、十字链表的存储结构

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

(0)

相关推荐

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言编程数据结构线性表之顺序表和链表原理分析

    目录 线性表的定义和特点 线性结构的特点 线性表 顺序存储 顺序表的元素类型定义 顺序表的增删查改 初始化顺序表 扩容顺序表 尾插法增加元素 头插法 任意位置删除 任意位置添加 线性表的链式存储 数据域与指针域 初始化链表 尾插法增加链表结点 头插法添加链表结点 打印链表 任意位置的删除 双向链表 测试双向链表(主函数) 初始化双向链表 头插法插入元素 尾插法插入元素 尾删法删除结点 头删法删除结点 doubly-Linked list.c文件 doubly-Linkedlist.h 线性表的定

  • 举例讲解C语言程序中对二叉树数据结构的各种遍历方式

    二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF 2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后输

  • C语言基于考研的栈和队列

    目录 栈 栈的基本操作 三角矩阵 总结 栈 栈的基本操作 InitStack(&S):初始化 StackEmpty(S):判空,空则true,非空则false Push(&S,x):入栈 Pop(&S,&x):出栈,并用x返回元素内容 GetTop(S,&x):读栈顶元素 DestroyStack(&S):销毁并释放空间 栈是一种受限的线性表,只允许在一端操作 栈若只能在栈顶操作,则只可能上溢 采用非递归方式重写递归时,不一定要用栈,比如菲波那切数列只要用循

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

    目录 一.十字链表是什么? 二.十字链表的存储结构 三.代码实现 1.引入头文件并定义结构体 2.建立十字链表 3.遍历十字链表 4.调用函数 本文需要读者有一定的代码基础,了解指针,链表,数组相关知识. 一.十字链表是什么? 十字链表常用于表示稀疏矩阵,可视作稀疏矩阵的一种链式表示,因此,这里以稀疏矩阵为背景介绍十字链表.不过,十字链表的应用远不止稀疏矩阵,一切具有正交关系的结构,都可用十字链表存储. 二.十字链表的存储结构 1.用于总结点的存储结构 m:总行数 n:总列数 len:总元素个数

  • C语言数据结构与算法之单链表

    目录 基本概念 读取数据元素 获取第i个结点的数据元素 插入数据元素  初始化链表 打印链表 顺序表查空 顺序表的删除  删除第i个结点及其数据元素 情况1:当删除的是第一个元素 情况2:除第一个结点外 完整代码 删除单链表整表 单链表VS顺序表 基本概念 链表的每一个结点中只包含一个指针域 优点 : 储存空间利用高效 举例来说: typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Studen

  • C语言数据结构超详细讲解单向链表

    目录 1.链表概况 1.1 链表的概念及结构 1.2 链表的分类 2. 单向链表的实现 2.1 SList.h(头文件的汇总,函数的声明) 2.2 SList.c(函数的具体实现逻辑) 2.2.1 打印链表 2.2.2 搞出一个新节点(为其他函数服务) 2.2.3 链表尾插 2.2.4 链表头插 2.2.5 链表尾删 2.2.6 链表头删 2.2.7 查找节点 2.2.8 在pos位置之前插入 2.2.9 在pos位置之后插入 2.2.10 删除pos位置 2.2.11 删除pos之后位置 2.

  • C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

  • C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构与算法之图的遍历(一)

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构之二叉链表创建二叉树

    目录 一.思想(先序思想创建) 二.创建二叉树 (1)传一级参数方法 (2)传二级参数方法 一.思想(先序思想创建) 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向NULL,结束本次左子树递归,返回这个节点的上一个节点,开始创建右子树,然后又开始以当下这个节点,继续递归创建左子树,左子树递归创建完,就递归创建右子树,直到递归结束返回到上一级指针节点(也就是根节点下),此时根节点左边子树创建完毕,开始创建右

  • C语言创建和操作单链表数据结构的实例教程

    1,为什么要用到链表 数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性.但数组也同样存在一些弊病.如数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个大小的数组,有时需要5 0个数组的大小,难于统一.我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费. 我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要.链表就是我们需要的动态数组.它是在程序的执行过程中根据需要有数据存储就向系统要求

  • C语言 数据结构链表的实例(十九种操作)

    C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

随机推荐