当前位置: 代码迷 >> Web前端 >> 数组的十字链表储存
  详细解决方案

数组的十字链表储存

热度:316   发布时间:2013-12-13 00:50:19.0
数组的十字链表存储
#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
  相关解决方案