Catalog
  1. 1. 问题描述
    1. 1.0.1. 对一个稀疏矩阵进行转置
    2. 1.0.2. 要求用十字链表存储
  2. 1.1. 运行界面
数据结构实验四

问题描述

对一个稀疏矩阵进行转置

要求用十字链表存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct OLNode{
int i, j;
ElemType e;
struct OLNode *right, *down;
}OLNode, *OLink;
typedef struct CrossList{
OLink *rhead, *chead;
int mu, nu, tu;
}CrossList, *pCrossList;

void CreateSMatrix_OL(pCrossList M)
{
//输入行数列数以及非零元个数
printf("请输入行数,列数,非零元素个数:\n");
scanf("%d%d%d", &M->mu, &M->nu, &M->tu);
if (M->tu * 20 > M->mu * M->nu)
printf("非稀疏矩阵,不建议使用此方法!\n");

//动态申请行和列指针数组
M->rhead = (OLink *)malloc(sizeof(OLink)*M->mu);
if (M->rhead == NULL)
return;
M->chead = (OLink *)malloc(sizeof(OLink)*M->nu);
if (M->chead == NULL){
free(M->rhead);
return;
}

//初始化两个数组
int i, j;
for (i = 1; i <= M->mu; i++)
M->rhead[i] = NULL;
for (j = 1; j <= M->nu; j++)
M->chead[j] = NULL;

//创建节点并连接到十字链表上
for (i = 1; i <= M->tu; i++){
OLink p = (OLink)malloc(sizeof(OLNode));
if (p == NULL)
return;
printf("请输入非零元素的行,列,值\n");
scanf("%d%d%d", &p->i, &p->j, &p->e);
p->down = NULL;
p->right = NULL;

//连接行
//如果该行并没有连接任何节点(NULL)或者该行连接的第一个节点的列值大于当前待连接的节点则直接将当前节点连接到该行第一个节点的位置
if (M->rhead[p->i] == NULL || M->rhead[p->i]->j > p->j){
p->right = M->rhead[p->i];
M->rhead[p->i] = p;
}
//否则遍历该行找到合适的位置插入
else {
OLink q = M->rhead[p->i];//指向第一个节点,从第一个节点开始遍历
while (q->right != NULL && q->right->j < p->j)//遍历到前一个节点
q = q->right;
p->right = q->right;
q->right = p;
}
//连接列
if (M->chead[p->j] == NULL || M->chead[p->j]->i > p->i) {
p->down = M->chead[p->j];
M->chead[p->j] = p;
}
else {
OLink pNodeTravel = M->chead[p->j];
while (pNodeTravel->down != NULL && pNodeTravel->down->i < p->i)
pNodeTravel = pNodeTravel->down;
p->down = pNodeTravel->down;
pNodeTravel->down = p;
}
}
}

void TransSMatrix_OL(CrossList M, CrossList *T)
{
T->mu = M.nu;
T->nu = M.mu;
T->tu = M.tu;

//Q的头节点的初始化
if (!(T->rhead = (OLink *)malloc((T->mu + 1) * sizeof(OLink)))) {printf("内存空间申请失败!");return;}
if (!(T->chead = (OLink *)malloc((T->nu + 1) * sizeof(OLink)))) { printf("内存空间申请失败!"); return; }

for (int i = 1; i <= T->mu; i++)
T->rhead[i] = NULL;
for (int i = 1; i <= T->nu; i++)
T->chead[i] = NULL;

if (!M.tu)
return;

OLink p, q, q_row, q_col;
for (int i = 1; i <= M.nu; i++){
if (M.chead[i]) {
for (q = M.chead[i]; q;) {
if (!(p = (OLink)malloc(sizeof(OLNode)))){
printf("内存空间申请失败!");
return;
}
p->i = q->j;
p->j = q->i;
p->e = q->e;
p->right = p->down = NULL;

q_row = T->rhead[i];
if (NULL == T->rhead[i])
T->rhead[i] = p;
else {
while (q_row->right)
q_row = q_row->right;
q_row->right = p;
}
q_col = T->chead[p->j];
if (T->chead[p->j] == NULL)
T->chead[p->j] = p;
else {
while (q_col->down)
q_col = q_col->down;
q_col->down = p;
}
q = q->down;
}
}
}
return;
}

void OutputSMatrix_OL(pCrossList M, char s[])
{
int i, j;
OLink p;
printf("----------------------\n");
printf("%s矩阵为:\n", s);
for (i = 1; i <= M->mu; i++){
p = M->rhead[i];
for (j = 1; j <= M->nu; j++){
if (p != NULL && p->j == j) {
printf("%d ", p->e);
p = p->right;
}
else
printf("0 ");
}
printf("\n");
}
printf("----------------------\n");
printf("\n");
return;
}
int main()
{
CrossList M, T;
CreateSMatrix_OL(&M);
char s1[] = "原始";
OutputSMatrix_OL(&M, s1);

TransSMatrix_OL(M, &T);
char s2[] = "转置后";
OutputSMatrix_OL(&T, s2);
return 0;
}

运行界面

sy

Author: Christopher Shen
Link: https://www.pasxsenger.com/2019/10/21/数据结构实验四/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付寶