7.4orthlink.cpp

矩阵的一些算法应用

#include<iostream.h>
#include "..\.\data_structure.h"


void Create(Node **hdnode)                         //建立稀疏矩阵的十字链表
{
  int n,m,r,p,i;
  Node* x;
  cout<<"input n,m,r:"<<endl;        //读入n，m，r，代表矩阵的行数，列数和非零个数
  cin>>n>>m>>r;
  if(m>n)
    p=m;
  else
    p=n;
  for(i=0;i<=p;i++)            //为行和列取得p个表头节点，并初始化，节点的value域指向其本身
  {  x=new Node;
     hdnode[i]=x;
     x->row=0;x->col=0;
     x->right=x;x->value=x;
  }

  int current_row=1;                  //current_row指示当前行
  Node* last=hdnode[1];               //last指示当前行最后一个节点
  for(i=1;i<=r;i++)                   //读入三元组，产生节点
  {
    int rrow,ccol,val;
    cout<<"please enter row,col,value:"<<endl;
    cin>>rrow;
    cin>>ccol;
    cin>>val;
    if(rrow>current_row)                     //当前行完成，关闭它，开始另一行
    {
      last->right=hdnode[current_row];
      current_row=rrow;
      last=hdnode[rrow];
    }
    x=new Node;                               //产生新节点
    x->row=rrow; x->col=ccol; x->value=(Node*)val;     //将三元组存入新节点
    last->right=x; last=x;                     //连入行表
//    (hdnode[ccol]->value)->down=x;             //连入列表
	hdnode[ccol]->down=x;
    hdnode[ccol]->value=x;                     //利用value指向该列的最后一个节点
  }
  if(r!=0)                                     //关闭最后一行
    last->right=hdnode[current_row];
  for(i=1;i<=m;i++)                            //关闭所有的列
//    (hdnode[i]->value)->down=hdnode[i];
	hdnode[i]->down=hdnode[i];	
  hdnode[0]->row=n;                            //存入头节点信息
  hdnode[0]->col=m;
  for(i=0;i<=p-1;i++)                          //建立通过value域相连的头节点表
    hdnode[i]->value=hdnode[i+1];
  if(p==0)
     hdnode[0]->value=hdnode[0];
  else
  {  hdnode[p]->value=hdnode[0];
     hdnode[0]->value=hdnode[1];
  }
}

void Show(Node **head)                      //显示建立的初始十字链表
{
	Node *c1=NULL;
	cout<<endl;
	for(int i=1;i<=head[0]->row;i++)
   {
		c1=head[i]->right;
//		for(j=1;j<c1->col;j++)
//			cout<<"**";
		int j=1;
		while(c1!=head[i])
      {
			for(;j<=c1->col;j++)
				if(j<c1->col)
					cout<<"**";
				else
					cout<<int(c1->value)<<"*";
			c1=c1->right;
		}
		cout<<endl;
	}
}

void Delete(Node **hdnode)
{                                              //删除十字链表
 	Node *c1=NULL;
	cout<<endl;
	for(int i=1;i<=hdnode[0]->row;i++)          //从第一行开始直到结束
   {
		c1=hdnode[i]->right;
		while(c1!=hdnode[i])                      	//删除一列
      {
			Node *temp=c1;
			c1=c1->right;
			cout<<"("<<temp->row<<","<<temp->col<<"):"<<int(temp->value)<<"--deleted!"<<endl;
			delete temp;
		}
		cout<<endl;
	}
}

void main(void)
{
	Node* hdnode[10];
	Create(hdnode);							//建立稀疏矩阵的十字链表
	Show(hdnode);							//显示建立的初始十字链表
	Delete(hdnode);							//删除稀疏矩阵的十字链表
}