shiyan01.cpp

功能强大

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
struct BILL
{
	int row,col;
	BILL * r,*d;	
	union
	{
		int val;
		BILL* next;	
	}tag;
};
int num;						//全局变量，非零元素个数
BILL * Creat();					//创建十字链表
BILL * Insert( BILL * hb);		//插入节点
BILL * Delete( BILL * hb);		//删除节点
void Print (BILL * hb);			//输出矩阵到屏幕
int FindV(BILL * hb);			//按值查找
int FindP(BILL * hb);			//按位置查找
void Save (BILL * hb);			//矩阵存盘
void Read ();					//从文件中恢复（读出）矩阵


void main ()
{
	int choice;
	BILL * hb;
	hb= Creat();
	do
	{
		cout<<"///////////////////////////////////////////////////////////////////////////"<<endl;
		cout<<"请选择：(1)创建新十字链表    (2)节点删除    (3)节点插入    (4)打印十字链表"<<endl;    
		cout<<"        (5)存盘  (6)文件中恢复(读出)矩阵  (7)检索指定矩阵元素(关键字是行列下标) "<<endl;
		cout<<"        (8)检索一个指定矩阵元素(关键字是矩阵元素值)      (0)退出"<<endl;
		cin>>choice;
		
		switch (choice)
		{
		case 1: hb= Creat();			break;
		case 2: hb= Delete(hb);			break;
		case 3: hb= Insert(hb);			break;
		case 4: Print (hb);				break;
		case 5: Save (hb);				break;
		case 6: Read ();				break;
		case 7:  FindP(hb);				break;
		case 8:  FindV(hb);				break;
		case 0:							break;	
		default: cout<<"wrong choice!";	break;
		}

	}while (choice!=0);
}

BILL * Creat()							//创建十字链表
{
	cout<<"///////////////////////进入创建十字链表操作!///////////////////////"<<endl;
	int n,m,s,i,r,c,v;
	BILL * h[100],*p,*q;				//h[100]是十字链表每行表头的数组(局部变量)
	cout<<"请输入行数m、列数n、非零元素个数num：";
	cin>>m>>n>>num;
	p=(BILL * )malloc(sizeof (BILL) ) ;					
	h[0]=p;								//十字链表头总指针
	p->row=m;											
	p->col=n;			
	s=m>n?m:n;							//s为m,n中大者
	for (i=1;i<=s;i++)
	{
		p=(BILL * )malloc(sizeof(BILL));							
		h[i]=p;							//每行的表头指针
		h[i-1]->tag.next=p;
		p->row=p->col=0;				
		p->d=p;							//p->d=p说明此列尚无链接节点
		p->r=p;							//p->r=p说明此行尚无链接节点
	}
	h[s]->tag.next=h[0];				//构成循环表头节点链
	
	for (i=1;i<=num;i++)
	{
		cout<<"请输入行号r、列号c、元素值v："<<endl;
		cin>>r>>c>>v;	
		p=(BILL *)malloc(sizeof(BILL));							
		p->row=r;
		p->col=c;
		p->tag.val=v;

		q=h[r];							//插入到行
		while (q->r!=h[r] && q->r->col < c) q=q->r;
		p->r=q->r;						//指针链接
		q->r=p;

		q=h[c];							//插入到列
		while (q->d!=h[c] && q->d->row < r) q=q->d;
		p->d=q->d;
		q->d=p;	
	}
	return h[0];
}


void Print (BILL * hb)					//输出矩阵到屏幕
{
	BILL * p,*q;
	cout<<"///////////////////////按行输出矩阵元素:///////////////////////"<<endl;
	cout<<"此矩阵行数="<<hb->row<<" 列数="<<hb->col<<endl;
	p=hb->tag.next;						//p指向h[1]
	while (p!=hb)						//p==hb说明已遍历完矩阵（头节点构成循环链）
	{
		q=p->r;
		while (p!=q)					//p==q说明p指向的一行已遍历完，或该行无链接节点
		{
			printf("(%d,%d)%d   ",q->row,q->col,q->tag.val);
			q=q->r;
		}
		cout<<endl;
	p=p->tag.next;						//p指向矩阵的下一行
	}
}

int FindV(BILL * hb)					//按值查找
{
	cout<<"///////////////////////进入按值查找操作!///////////////////////"<<endl;
	int x;
	cout<<"请输入要查找节点元素的值：";
	cin>>x;
	BILL * p,*q;
	p=hb->tag.next;
	cout<<"查找该节点所走过的元素下标序列为：";
	while(p!=hb)						//p==hb说明已遍历完矩阵
	{	
		q=p->r;							//q依次指向同一行的各个节点
		while(p!=q)						//p==q说明p指向的一行已遍历完，或该行无链接节点
		{
			cout<<"("<<q->row<<','<<q->col<<")  ";
			if(q->tag.val==x)			//找到x了
			{
				cout<<endl<<"查找节点所在的行号="<<q->row<<"  列号="<<q->col<<endl;
				return 1;
			}
			q=q->r;
		}
		p=p->tag.next;					//p指向下一个头节点
	}
	cout<<"查无此元素！"<<endl;
	return 0;
}

int FindP(BILL * hb)					//按位置查找
{
	cout<<"///////////////////////进入按位置查找操作!///////////////////////"<<endl;
	BILL * p,*q;
	int r,c;
	cout<<"请输入要查找节点的位置下标："<<endl;
	cin>>r>>c;
	if(r>hb->row || c>hb->col)  {cout<<"输入位置有误！"<<endl;  return 0;}	
	
	p=hb->tag.next;
	cout<<"查找该节点所走过的元素下标序列为：";
	q=p->r;
	while(p!=hb && q->row < r)			//p==hb说明已遍历完矩阵
	{							
		cout<<'('<<q->row<<','<<q->col<<")  ";
		p=p->tag.next;					//p指向下一个头节点	
		q=p->r;	
	}//q->row == r(已移动到待查行)
							
	while(p!=q)							//p==q说明p指向的一行已遍历完，或该行无链接节点
	{
		cout<<'('<<q->row<<','<<q->col<<')';
		if( q->col==c)					//已移动到待查列,找到要查找的位置了
			{
				cout<<endl<<"查找节点值="<<q->tag.val<<endl;
				return 1;
			}
		q=q->r;
	}	
	cout<<"查无此位置！"<<endl;
	return 0;
}

BILL * Insert( BILL * hb)				//插入节点
{
	cout<<"///////////////////////进入插入节点操作!///////////////////////"<<endl;
	BILL * p,*q,*q1,*pn;
	int r,c,v;
	cout<<"请依次输入要插入节点的位置下标r、c，及元素的值v："<<endl;
	cin>>r>>c>>v;
	
	pn=(BILL * )malloc(sizeof (BILL) ) ;//pn指向待插节点
	pn->row=r;
	pn->col=c;
	pn->tag.val=v;

	if(r>hb->row || c>hb->col)		cout<<"输入位置超出当前矩阵的大小！"<<endl; 	
	else 
	{		
		p=hb;
		for(int i=1;i<=r;i++)
			p=p->tag.next;							//p已移动到待插行
		q=p->r;
		if(p==q||q->col > c)  {p->r=pn;pn->r=q;}	//若该行无链接节点(p==q)，或待插节点列数为此行最小,则直接插入待插节点
		else
		{
			while(q->col < c && p!=q)				//p==q说明p指向的一行已遍历完
			{q1=q;q=q->r;}							//q1是q的前驱		
			pn->r=q1->r;							//插入待插节点
			q1->r=pn;		
		}
		num++;										//非零元素个数加一
	}
	return hb;
}

BILL * Delete( BILL * hb)							//删除节点
{
	cout<<"///////////////////////进入删除节点操作!///////////////////////"<<endl;
	BILL * p,*q,*q1;
	int r,c;
	cout<<"请输入要删除节点的位置下标r，c"<<endl;
	cin>>r>>c;
	if(r>hb->row || c>hb->col)		cout<<"输入位置错误！"<<endl; 	
	else 
	{		
		p=hb;
		for(int i=1;i<=r;i++)
			p=p->tag.next;							//p已移动到待删除节点所在行
		q=p->r;
		if(p==q)  cout<<"输入位置错误！"<<endl; 	//若该行无链接节点(p==q)，则不删除
		else
		{
			if(q->col == c )						//要删节点是此行的第一个时
				{p->r=q->r;free(q);num--;}
			else 
			{
				while(q->col != c && p!=q)			//p==q说明p指向的一行已遍历完
					{q1=q;q=q->r;}					//q1是q的前驱	
				if (q->col==c)						//找到要删节点q了
				{
					q1->r=q->r;
					free(q);
					num--;							//非零元素个数减一

				}	
				else cout<<"输入位置错误！"<<endl;
			}	
		}
	}
	return hb;
}

void Save (BILL * hb)			//矩阵存盘
{
	cout<<"///////////////////////进入存盘操作!////////////////////////"<<endl;
	BILL *p,*q;
	FILE * fp;
	int i=1,j=1;
	if ( (fp=fopen("BILL_list","wb"))==0)		//打开文件"BILL_list"
	{
		cout<<"cannot open!"<<endl;
		return;
	}	

	p=hb->tag.next;	
	do											//p==hb说明已遍历完矩阵（头节点构成循环链）
	{
		q=p->r;
		do			
		{	
			if( fwrite (q,sizeof(BILL),1,fp) !=1 ) //向文件中写矩阵
			cout<<"file write error!"<<endl;
			q=q->r;
		}while (p!=q);	//p==q->r说明p指向的一行已遍历完，或该行无链接节点
	
		p=p->tag.next;							//p指向矩阵的下一行
	}while (p!=hb);
	fclose(fp);

}

void Read ()									//从文件中恢复（读出）矩阵
{
	cout<<"///////////////////////进入读盘操作!///////////////////////"<<endl;
	int i=1,j=1;
	BILL *p,*q,*hb;
	FILE * fp;
	fp=fopen("BILL_list","rb");					//打开文件"BILL_list"
	q=(BILL * )malloc(sizeof (BILL) ) ;
	for(int m=1;m<=num;m++)
	{
		fread (q,sizeof(BILL),1,fp);			//从文件中依次读矩阵各节点	
		printf("(%d,%d)%d   ",q->row,q->col,q->tag.val);//打印到屏幕
		q=q->r;	
	}
	fclose(fp);
}