数据结构实验：基于十字链表的稀疏矩阵转置_* 十字链表的稀疏矩阵转置 */ void transmatrix(crosslist *a, cr

采用C++编程，基于十字链表完成转置。

思想为改变行列指针指向。 

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
#define ERROR -1
#define OK 1
typedef int ElemType;
typedef int Status;
typedef struct OLNode
{
	int i, j;//矩阵非零元素的行、列值
	ElemType e;//非零元素的值
	OLNode* right, * down;//行列后继域
}OLNode, * Olink;
typedef struct
{
	Olink rhead, chead;//行、列 表指针基址
	int mu, nu, tu;//矩阵的行、列、非零元素个数
}CrossList;
Status insert(Olink h, int i, int j, int e)//插入结点
{
	int m = h->i, n = h->j;
	if (i < 0 || i >= m || j < 0 || j >= n) return ERROR;//结点坐标不合法则返回ERROR
	Olink p = new OLNode; if (!p) return ERROR;//建立新结点
	p->i = i;p->j = j;p->e = e;
	Olink qr = &h->down[i], q = qr->right;
	while (q != &h->down[i] && j > q->j)//找到结点插入位置
	{
		qr = q;q = q->right;
	}
	qr->right = p;p->right = q;
	qr = &h->right[j];q = qr->down;
	while (q != &h->right[j] && i > q->i)
	{
		qr = q;q = q->down;
	}
	qr->down = p;
	p->down = q;
	cout << i << '\t' << j << '\t' << e << endl;
	return OK;
}
Status init(Olink h)//从文件中获取数据初始化十字链表
{
	fstream data;
	data.open("data.txt");
	data >> h->i >> h->j;//建立总头节点，头结点内存储行列数与行列基址
	int t;
	data >> t;
	h->e = t;
	h->down = new OLNode[h->i];//创建行头数组
	if (!h->down) return ERROR;//返回NULL表示创建失败
	h->right = new OLNode[h->j];//创建列头数组
	if (!h->right) return ERROR;
	for (int i = 0;i < h->i;i++)//初始化行列头结点
	{
		h->down[i].i = i;
		h->down[i].right = &h->down[i];
	}
	for (int j = 0;j < h->j;j++)
	{
		h->right[j].j = j;
		h->right[j].down = &h->right[j];
	}
	int m = h->i, n = h->j;
	for (;t > 0;t--)
	{
		int i, j, e;
		data >> i >> j >> e;
		insert(h, i, j, e);
	}
	data.close();
	return OK;
}
Status Transpose(Olink h)//矩阵转置
{
	fstream data;
	data.open("out.txt");
	int mid=h->i;
	h->i = h->j;
	h->j = mid;
	Olink pn;
	data << h->i << '\t' << h->j << '\t' << h->e << endl;
	for (int i = 0;i<h->i;i++)//从列数组遍历，改变down指针与right指针的指向
	{
		Olink p = &h->right[i];
		p->right = p->down;
		p = h->right[i].down;
		while(p!=&h->right[i])
		{
			pn = p->down;
			p->down = p->right;
			p->right = pn;
			mid = p->i;
			p->i = p->j;
			p->j = mid;
			data<< p->i << '\t' << p->j << '\t' << p->e << endl;//写入文件
			p = pn;
		}
	}
	for (int i = 0;i < h->j;i++)//改变行头数组的指向
	{
		Olink p = &h->down[i];
		p->down = p -> right;
	}
	Olink q = h->right;
	h->right = h->down;
	h->down = q;
	for (int i = 0;i < h->i;i++)
	{
		Olink p = h->down[i].right;
		while (p != &h->down[i])
		{
			cout << p->i << '\t' << p->j << '\t' << p->e << endl;
			p = p->right;
		}
	}
	data.close();
	return OK;
}
int main()
{
	OLNode h;
	init(&h);
	cout << endl;
	Transpose(&h);
}