p93_96.cpp
上传用户:chaiyuqiu
上传日期:2022-08-03
资源大小:27k
文件大小:5k
源码类别:

数据结构

开发平台:

C/C++

  1. #include <iostream.h>
  2.                 #include <stdio.h>
  3. enum Boolean { False, True };
  4. struct Triple { int row, col;  float value; }; //三元组类的定义
  5. class Matrix; //稀疏矩阵类的前视声明
  6. class MatrixNode { //矩阵结点类的定义
  7. friend class Matrix;
  8. friend istream & operator >> ( istream &, Matrix & ); //矩阵读入
  9.                 friend ostream & operator << ( ostream &, Matrix & );
  10. private:
  11.    MatrixNode *down, *right; //列/行链表指针
  12.    Boolean head; //结点类型
  13.    union { Triple triple;  MatrixNode *next; }; //无名联合
  14.    MatrixNode ( Boolean, Triple* ); //构造函数
  15. };
  16. MatrixNode::MatrixNode ( Boolean b, Triple *t ){ //构造函数
  17.    head = b; //结点类型
  18.    if ( b ) { right = next = this; } //各行/列链表的表头结点
  19.    else triple = *t; //头结点链表的表头或非零元素结点
  20. }
  21. typedef MatrixNode *MatrixNodePtr; //一个指针数组
  22. class Matrix { //稀疏矩阵的类定义
  23. friend istream & operator >> ( istream &, Matrix & );
  24.                 friend ostream & operator << ( ostream &, Matrix & );
  25. public:
  26.    ~Matrix ( ); //析构函数
  27. private:
  28.    MatrixNode *headnode;  //稀疏矩阵的表头
  29. };
  30. istream & operator >> ( istream & is, Matrix & matrix ) //读入稀疏矩阵, 建立它的链表表示
  31. {
  32.    Triple s;  int p;
  33.    is >> s.row >> s.col >> s.value;  //读入矩阵行数、列数和非零元素个数
  34.    if ( s.row > s.col ) p = s.row; //确定行/列链表表头结点个数p
  35.    else p = s.col; // p = max { s.row, s.col }
  36.    matrix.headnode = new MatrixNode ( False, &s ); //创建表的表头结点
  37.    if ( !p ) { matrix.headnode->right = matrix.headnode;  return is; } //至少一行或一列
  38.    MatrixNodePtr *H = new MatrixNodePtr [ p ]; //初始化表头指针数组,指向各链表头
  39.    for ( int i=0; i<p; i++ ) H[i] = new MatrixNode ( True, 0 ); //指向各链表头结点
  40.    int CurrentRow = 0;
  41.    MatrixNode *last = H[0]; //last为当前行的最后结点指针
  42.    for ( i=0; i<s.value; i++ ) { //输入三元组, s.value给出三元组个数
  43.  Triple t;
  44.  is >> t.row >> t.col >> t.value; //输入三元组
  45.  if ( t.row > CurrentRow ) { //行号大于当前行号,闭合当前行
  46.     last->right = H[CurrentRow]; //在行的方向向表头结点拉链
  47.     CurrentRow = t.row;  last = H[CurrentRow]; //当前行改变为新的一行
  48.  }
  49.  last = last->right = new MatrixNode ( False, &t ); //新结点链入行链表,last跟上
  50.  H[t.col]->next = H[t.col]->next->down = last; //链入列链表,next记下该结点地址
  51.    }
  52.    last->right = H[CurrentRow]; //闭合最后一行
  53.    for ( i=0; i<s.col; i++ ) H[i]->next->down = H[i]; //闭合所有列链表
  54.    for ( i=0; i<p-1; i++ ) H[i]->next = H[i+1]; //所有表头结点链接在一起
  55.    H[p-1]->next = matrix.headnode;  matrix.headnode->right = H[0];
  56.    delete [ ] H;
  57.    return is;
  58. }
  59.       /* if ( first != NULL ) { //链表不空
  60.    CircListNode<Type> *second = first->link; //循环链表的第二个结点
  61.    first->link = av;    av = second; //第一个结点链接到av
  62.    first = NULL;
  63. }
  64. if ( av == NULL ) newnode = new CircListNode<Type>; //可利用空间表为空,动态分配
  65. else { newnode = av;  av = av->link; } //不空,从可利用空间表分配
  66. */
  67.                 MatrixNode *av;
  68. Matrix::~Matrix ( ) {
  69. //将所有结点回收到可利用空间表中, 这个表是用right域链接的。av是一个具有MatrixNode*
  70. //类型的全局变量, 且指向它的前端第一个结点。
  71.    if ( headnode == NULL ) return; //空链表, 无法回收
  72.    MatrixNode *x = headnode->right, *y;
  73.    headnode->right = av;  av = headnode; //回收表头结点的循环链表
  74.    while ( x != headnode ) { //按行回收各行的循环链表
  75.       y = x->right;  x->right = av;  av = y; //回收行 (循环) 链表
  76.       x = x->next; //下一行
  77.    }
  78.    headnode = NULL;
  79. }
  80. ostream & operator << ( ostream & os, Matrix & matrix )
  81. {
  82.     MatrixNode *current = matrix.headnode , *temp;
  83.     cout << "row:  " << current->triple.row << endl;
  84.     cout << "column: " << current->triple.col << endl;
  85.     cout << "nonzero: " << current->triple.value << endl;
  86.     cout << "order in column:" << endl;
  87.     temp = current = current->right;
  88.     for (int column = 0 ; column < matrix.headnode->triple.col; column++) {
  89. cout << "column " << column << " : " ;
  90. temp = temp->down ;
  91. while ( temp != current ) {
  92.     cout << "(" << temp->triple.row << ",";
  93.     cout << temp->triple.col << ",";
  94.     cout << temp->triple.value << ") ";
  95.     temp = temp->down;
  96. };
  97. cout << endl;
  98. temp = current = current->next;
  99.     }
  100.     cout << "order in row:" << endl;
  101.     temp = current = current->right;
  102.     for (int row = 0; row < matrix.headnode->triple.row; row++) {
  103. cout << "row " << row << " : " ;
  104. temp = temp->right ;
  105. while ( temp != current ) {
  106.     cout << "(" << temp->triple.row << ",";
  107.     cout << temp->triple.col << ",";
  108.     cout << temp->triple.value << ") ";
  109.     temp = temp->right;
  110. };
  111. cout << endl;
  112. temp = current = current->next;
  113.     }
  114.     return os;
  115. }