数组的十字链表存储
#include <iostream.h>
#include<iomanip.h>
#include<conio.h>
typedef int ElemType;
struct Node
{ int row;int col;
Node *down;
Node *right;
union // 定义公用体以节省空间
{ Node *next;
ElemType val;
};
};
class Linkedmat
{ private:
Node *hm; // 定义十字链表的头指针
public:
void Creat(); //创建一个矩阵十字链表
void Show(); // 输出显示
//……………………
};
void Linkedmat::Creat()
{ int m, n, s, r, c, v,t;
//Node *p，*q，*cp[20];
Node *p;
Node *q; Node *cp[20];
cout << "行维数: "; cin >> m;
cout << "列维数: "; cin >> n;
cout << "非零元素个数: "; cin >>t;
s = m > n ? m : n; //取行列数的大值
p = new Node;
p->row = m; p->col = n;
hm = p; hm->next=hm;
cp[0]=hm;
for ( int i = 1; i <= s; i++ )
// 创建所有行列表头头结点，共 s 个
{ p = new Node;
p->row = 0; p->col = 0;
cp[i] = p;
p->right= p;
p->down = p;
cp[i-1]->next = p;
}
cp[s]->next = hm;
cout << "最大行坐标: " << m << endl;
cout << "最大列坐标: " << n << endl;
cout << "非零元素个数: " <<t << endl;
for( i=0; i<t; i++)
{ cout << "\n 输入三元组:下标从(1,1)开始 "; cin >> r >> c >> v;
p = new Node; //分配新的非零元素结点
p->row = r;
p->col = c;
p->val = v;
q = cp[r]; //在当前行找插入位置
while ( q->right != cp[r] && (q->right->col < c) )
{ q = q->right;}
p->right = q->right;
q->right = p;
q = cp[c]; //在当前列找插入位置
while ( q->down != cp[c] && (q->down->row < r) )
{q = q->down;}
p->down = q->down;
q->down = p;
} //for i=0到t-1;
} //creat建立函数结束
void Linkedmat::Show()
{ //Node *p，* p1;
Node *p;Node *p1;
int i,j;
cout << "\n 十字链表存储的矩阵为:" << endl ;
for ( i = 0; i <= hm->col; i++ )
cout <<setw(6)<< i; // 输出各列的标号
cout << endl << endl;
for ( i = 1, p = hm->next; p != hm; i++ )
{ cout << setw(6) << i; // 输出个行的标号
for ( j = 1, p1 = p->right; p1 != p; j++ )
if ( j == p1->col )
{cout<<setw(6)<<p1->val; p1=p1->right; }
else cout << setw(6)<< " ";
cout << endl; //换行
p = p->next; //找下一个行列表头结点
}
} //输出函数结束
void main()
{
Linkedmat linkedmat;
linkedmat.Creat();
linkedmat.Show ();
}
http://wgyblog.com/html/158.html
