这篇文章主要介绍了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语言数据结构的资料请关注编程学习网其它相关文章!
沃梦达教程
本文标题为:C语言数据结构创建及遍历十字链表
基础教程推荐
猜你喜欢
- C/C++编程中const的使用详解 2023-03-26
- C++详细实现完整图书管理功能 2023-04-04
- C语言 structural body结构体详解用法 2022-12-06
- C++中的atoi 函数简介 2023-01-05
- 如何C++使用模板特化功能 2023-03-05
- 一文带你了解C++中的字符替换方法 2023-07-20
- C语言基础全局变量与局部变量教程详解 2022-12-31
- C++使用easyX库实现三星环绕效果流程详解 2023-06-26
- C利用语言实现数据结构之队列 2022-11-22
- 详解c# Emit技术 2023-03-25