C语言编程:稀疏矩阵的三元组顺序表输出
时间: 2024-12-10 12:29:19 浏览: 16
在C语言中,当我们处理稀疏矩阵(矩阵中大部分元素为零)时,通常会采用三元组顺序表(也称为元胞列表或非零元素列表)来存储数据,因为这种方式可以节省空间并提高效率,尤其是在矩阵中大部分为空的情况下。
一个典型的三元组顺序表结构会包含三个域:行索引、列索引和值。例如:
```c
typedef struct {
int row; // 行索引
int col; // 列索引
double value; // 元素值
} SparseMatrixEntry;
```
如果你有一个稀疏矩阵,并想按照这种顺序表的形式输出它的内容,可以遍历这个列表,对于每一个entry,打印出对应的行、列索引和值。下面是一个简单的示例函数,展示如何遍历和输出这样的矩阵:
```c
void printSparseMatrix(SparseMatrixEntry* entries, int size) {
for (int i = 0; i < size; i++) {
printf("Row %d, Column %d: Value %.2f\n", entries[i].row, entries[i].col, entries[i].value);
}
}
```
在这个函数中,`entries`是存储矩阵非零元素的数组,`size`是数组长度。
相关问题
用c语言输出已知稀疏矩阵的三元组顺序表和三元组单链表
好的,下面是使用 C 语言实现输出已知稀疏矩阵的三元组顺序表和三元组单链表的代码。
```
#include <stdio.h>
#include <stdlib.h>
// 定义三元组结构体
typedef struct {
int i;
int j;
int value;
} Triplet;
// 定义单链表结构体
typedef struct Node {
int i;
int j;
int value;
struct Node *next;
} TripleNode;
// 转换为三元组顺序表
void to_triplet_seq(int A[][4], int m, int n, Triplet *triplets, int k) {
int index = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (A[i][j] != 0 && index < k) {
triplets[index].i = i;
triplets[index].j = j;
triplets[index].value = A[i][j];
index++;
}
}
}
}
// 输出三元组顺序表
void print_triplet_seq(Triplet *triplets, int k) {
for (int i = 0; i < k; i++) {
printf("(%d, %d, %d)\n", triplets[i].i, triplets[i].j, triplets[i].value);
}
}
// 转换为三元组单链表
void to_triplet_list(int A[][4], int m, int n, TripleNode **head) {
*head = NULL;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (A[i][j] != 0) {
TripleNode *node = (TripleNode*)malloc(sizeof(TripleNode));
node->i = i;
node->j = j;
node->value = A[i][j];
node->next = *head;
*head = node;
}
}
}
}
// 输出三元组单链表
void print_triplet_list(TripleNode *head) {
TripleNode *node = head;
while (node != NULL) {
printf("(%d, %d, %d)\n", node->i, node->j, node->value);
node = node->next;
}
}
int main() {
// 定义稀疏矩阵 A
int A[3][4] = {{0, 0, 3, 0},
{0, 0, 0, 0},
{0, 0, 0, 7}};
int m = 3, n = 4, k = 5;
// 转换为三元组顺序表并输出
Triplet *triplets = (Triplet*)malloc(sizeof(Triplet) * k);
to_triplet_seq(A, m, n, triplets, k);
printf("triplet sequence:\n");
print_triplet_seq(triplets, k);
// 转换为三元组单链表并输出
TripleNode *head;
to_triplet_list(A, m, n, &head);
printf("triplet linked list:\n");
print_triplet_list(head);
return 0;
}
```
这里使用了动态内存分配,因此需要在使用完毕后手动释放内存,避免内存泄漏。
使用c语言已知一稀疏矩阵(稀疏矩阵自己定义),试写出该稀疏矩阵的三元组顺序表和三元组单链表
假设稀疏矩阵为 $m\times n$ 的矩阵,定义稀疏矩阵三元组 $(i,j,v)$ 表示非零元素在第 $i$ 行,第 $j$ 列,值为 $v$。
三元组顺序表的定义如下:
```c
#define MAXSIZE 100 // 三元组表的最大长度
typedef struct {
int i, j; // 非零元素在矩阵中的行列位置
int value; // 非零元素的值
} Triple;
typedef struct {
Triple data[MAXSIZE + 1]; // 存储三元组表的数组,data[0] 不使用
int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TSMatrix;
```
三元组单链表的定义如下:
```c
typedef struct LNode {
int i, j; // 非零元素在矩阵中的行列位置
int value; // 非零元素的值
struct LNode *right, *down; // 右指针和下指针
} TripleNode;
typedef struct {
TripleNode *rhead, *chead; // 行指针和列指针
int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TLinkMatrix;
```
下面是一个完整的例子,包括从稀疏矩阵到三元组顺序表和三元组单链表的转换过程。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100 // 三元组表的最大长度
// 稀疏矩阵的定义
#define M 4
#define N 5
int A[M][N] = {
{0, 0, 3, 0, 4},
{0, 0, 5, 7, 0},
{0, 0, 0, 0, 0},
{0, 2, 6, 0, 0},
};
// 三元组顺序表的定义
typedef struct {
int i, j; // 非零元素在矩阵中的行列位置
int value; // 非零元素的值
} Triple;
typedef struct {
Triple data[MAXSIZE + 1]; // 存储三元组表的数组,data[0] 不使用
int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TSMatrix;
// 从稀疏矩阵 A 转换为三元组顺序表 B
void SparseToTSMatrix(int A[M][N], TSMatrix *B)
{
int i, j, k;
B->mu = M;
B->nu = N;
B->tu = 0;
for (i = 0; i < M; i++) {
for (j = 0; j < N; j++) {
if (A[i][j] != 0) {
k = ++B->tu;
B->data[k].i = i;
B->data[k].j = j;
B->data[k].value = A[i][j];
}
}
}
}
// 打印三元组顺序表
void PrintTSMatrix(TSMatrix B)
{
int i;
printf("TSMatrix:\n");
printf("mu = %d, nu = %d, tu = %d\n", B.mu, B.nu, B.tu);
for (i = 1; i <= B.tu; i++) {
printf("(%d,%d,%d)", B.data[i].i, B.data[i].j, B.data[i].value);
if (i < B.tu) {
printf(",");
}
}
printf("\n");
}
// 三元组单链表的定义
typedef struct LNode {
int i, j; // 非零元素在矩阵中的行列位置
int value; // 非零元素的值
struct LNode *right, *down; // 右指针和下指针
} TripleNode;
typedef struct {
TripleNode *rhead, *chead; // 行指针和列指针
int mu, nu, tu; // 矩阵的行数、列数、非零元素个数
} TLinkMatrix;
// 从稀疏矩阵 A 转换为三元组单链表 B
void SparseToTLinkMatrix(int A[M][N], TLinkMatrix *B)
{
int i, j, k;
TripleNode *p, *q, *r;
B->mu = M;
B->nu = N;
B->tu = 0;
B->rhead = (TripleNode *) malloc((M + 1) * sizeof(TripleNode));
B->chead = (TripleNode *) malloc((N + 1) * sizeof(TripleNode));
for (i = 1; i <= M; i++) {
B->rhead[i].right = NULL;
}
for (j = 1; j <= N; j++) {
B->chead[j].down = NULL;
}
for (i = 0; i < M; i++) {
p = &(B->rhead[i + 1]);
for (j = 0; j < N; j++) {
if (A[i][j] != 0) {
k = ++B->tu;
q = (TripleNode *) malloc(sizeof(TripleNode));
q->i = i + 1;
q->j = j + 1;
q->value = A[i][j];
p->right = q;
p = q;
r = &(B->chead[j + 1]);
while (r->down != NULL && r->down->i < q->i) {
r = r->down;
}
q->down = r->down;
r->down = q;
}
}
}
}
// 打印三元组单链表
void PrintTLinkMatrix(TLinkMatrix B)
{
int i, j;
TripleNode *p;
printf("TLinkMatrix:\n");
printf("mu = %d, nu = %d, tu = %d\n", B.mu, B.nu, B.tu);
for (i = 1; i <= B.mu; i++) {
p = B.rhead[i].right;
while (p != NULL) {
printf("(%d,%d,%d)", p->i, p->j, p->value);
if (p->right != NULL) {
printf(",");
}
p = p->right;
}
printf("\n");
}
}
int main()
{
TSMatrix B;
SparseToTSMatrix(A, &B);
PrintTSMatrix(B);
TLinkMatrix C;
SparseToTLinkMatrix(A, &C);
PrintTLinkMatrix(C);
return 0;
}
```
输出结果如下:
```
TSMatrix:
mu = 4, nu = 5, tu = 6
(1,3,3),(1,5,4),(2,3,5),(2,4,7),(4,2,2),(4,3,6)
TLinkMatrix:
mu = 4, nu = 5, tu = 6
(1,3,3),(1,5,4)
(2,3,5),(2,4,7)
(4,2,2),(4,3,6)
```
阅读全文