链表.cpp

十字链表

#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <fstream>
using namespace std;

typedef struct node
		{
			int col,row,val;
			struct node *down,*right;
		}NODE;

NODE *initialization (int *,int *,int *);		//建立链表时的初始化			
int	 dls_delete (NODE *,int,int,int);			//删除节点
int	 dls_insert (NODE *,NODE *,int,int);		//插入节点
NODE *dls_create(NODE *,int *,int *,int *,int *);	//建立链表
void dls_printer(NODE *s);						//打印某个节点
void dls_bianli (NODE *,int,int);				//输出矩阵
void dls_saver  (NODE *,int);					//保存至文件
int  dls_search (NODE *,int,int,int,int);		//链表检索
NODE *dls_loader(NODE *,int,int,int);			//从文件恢复链表

int main (void)
{
	NODE *cp,*w;
	int m,n,t=0,s;
	cp=initialization(&m,&n,&s);
	char choice='x';
	do
	{
		cout  << "\t\t\t  *=========>十字链表<=========*" << endl;
		cout << "=============================================================================="<<endl;
		cout << "\t\t\t      (0)    建 立 链 表" << endl;
		cout << "\t\t\t      (1)    节 点 插 入" << endl;
		cout << "\t\t\t      (2)    节 点 删 除" << endl;
		cout << "\t\t\t      (3)    遍 历 链 表" << endl;
		cout << "\t\t\t      (4)    链 表 检 索" << endl;
		cout << "\t\t\t      (5)    链 表 存 盘" << endl;
		cout << "\t\t\t      (6)    恢 复 链 表" << endl;
		cout << "\t\t\t      (7)    退       出" << endl;
		cout << "=============================================================================="<<endl;
		cout << "请输入您的选择：";
		choice=getche();
		cout << endl;
		switch(choice)
		{
			case '0':
				{
					cp=dls_create(cp,&t,&s,&n,&m);
					cout<<"建立链表成功!"<<endl;
					break;
				}
			case '1':
				{
					w=(NODE *)malloc(sizeof(NODE));
					cout<<"请输入矩阵元素的行、列数和数值:  ";
					cin>>(w->row)>>(w->col)>>(w->val);
					if (dls_insert(w,cp,n,m)) cout<<"插入元素成功!"<<endl;
					break;
				}
			case '2':
				{
					if (dls_delete(cp,s,n,m)) cout<<"删除成功!"<<endl;
					break;
				}
			case '3':
				{
					cout<<"当前矩阵如下:"<<endl;
					dls_bianli(cp,s,m);
					break;
				}
			case '4':
				{
					if (!dls_search(cp,t,s,n,m)) cout<<"元素未找到!"<<endl;
					break;
				}
			case '5':
				{
					dls_saver(cp,s);
					break;
				}
			case '6':
				{
					cp=dls_loader(cp,s,n,m);
					if (cp) cout<<"恢复成功!"<<endl;
					break;
				}
			case '7':
					break;
			default:
				{
					cout << "输入错误，请按任意键重新输入！";
					getche();
					break;
				}
		}
	}
	while (choice!='7');
	return(0);
}
NODE *initialization (int *n,int *m,int *s)
{
	int i;
	NODE *cp;
	cout<<"请输入矩阵的行、列数: ";
	cin>>*n>>*m;
	if (*m>*n) *s=*m;
	else *s=*n;
	cp=(NODE *)malloc((*s+1)*sizeof(NODE));
	(*cp).row=*m;
	(*cp).col=*n;
	for (i=1;i<=*s;i++)
	{
		(*(cp+i)).row=0;
		(*(cp+i)).col=0;
		(*(cp+i)).down=cp+i;
		(*(cp+i)).right=cp+i;
		(*(cp+i)).val=0;
	};
	return(cp);
}
NODE *dls_create (NODE *cp,int *t,int *s,int *n,int *m)
{
	int i;
	NODE *temp1,*temp2,*w;
	for (i=1;i<=*s;i++)
	{
		temp1=(*(cp+i)).right;
		temp2=(*temp1).right;
		while (temp2!=cp+i)
		{
			free(temp1);
			temp1=temp2;
			temp2=temp2->right;
		};
		if (temp1!=cp+i)free(temp1);
	};
	free(cp);
	cp=NULL;				//把原有的链表free掉，重建链表
	cp=initialization(m,n,s);
	cout<<"请输入非零元素个数: ";
	fflush(stdin);
	cin>>*t;
	for (i=0;i<*t;i++)
	{
		w=(NODE *)malloc(sizeof(NODE));
		cout<<"请输入第"<<i+1<<"个矩阵元素的行、列和数值:  ";
		cin>>(w->row)>>(w->col)>>(w->val);
		if (!dls_insert(w,cp,*n,*m)) i--;
	};
	return(cp);				//返回头节点
}
int	 dls_delete (NODE *cp,int s,int n,int m)
{
	int r,c,k;
	NODE *p,*q;
	cout<<"请输入矩阵元素的坐标: ";
	cin>>r>>c;
	if (r>n || c>m || r<1 || c<1) 
	{
		cout<<"行、列数错误!"<<endl;
		return(0);
	};
	k=0;
	p=cp+r;
	q=(*(cp+r)).right;
	while (k==0 && q!=cp+r)
	{
		if (q->row==r && q->col==c)
		{
			p->right=q->right;
			k=1;
		};
		p=q;
		q=q->right;
	};
	if (!k) return(0);
	p=cp+c;
	q=(*(cp+c)).down;
	while (q!=cp+c)
	{
		if (q->row==r && q->col==c)
		{
			p->down=q->down;
			free(q);
			return(1);
		};
		p=q;
		q=q->down;
	};
	return(0);
}
int dls_insert(NODE *s,NODE *cp,int n,int m)
{
	NODE *q,*p;
	if (s->row>n || s->col>m || s->row<1 || s->col<1) 
	{
		cout<<"行、列数错误!"<<endl;
		return(0);
	};
	q=(*(cp+(s->row))).right;			//插入的行
	if (q==(cp+(s->row)))
	{
		s->right=(cp+(s->row));
		(*(cp+(s->row))).right=s;		//插入头节点
	}
	else
	{
		p=cp+(s->row);
		while ((q!=(cp+(s->row))) && ((q->col)<=(s->col)))
		{
			if (q->row==s->row && q->col==s->col)
			{
				cout<<"("<<s->row<<","<<s->col<<")"<<"已经输入过了，是否覆盖(Y/N) : ";
				char choice;
				cin>>choice;
				if (choice=='n' || choice=='N') return(0);
				else 
				{
					q->val=s->val;
					return(0);
				};
			};
			p=q;
			q=q->right;					//查找插入列位置
		};
		s->right=q;
		p->right=s;						//插入节点
	};
	q=(*(cp+(s->col))).down;			//插入的列
	if (q==(cp+(s->col)))
	{
		s->down=(cp+(s->col));
		(*(cp+(s->col))).down=s;		//插入到头节点
	}
	else
	{
		p=cp+(s->col);
		while ((q!=(cp+(s->col))) && ((q->row)<=(s->row)))
		{
			p=q;
			q=q->down;					//查找插入行位置	
		};
		s->down=q;
		p->down=s;						//插入节点
	};
	return(1);
}
void dls_printer (NODE *s)
{	
	cout<<" ("<<s->row<<","<<s->col<<")";
	cout<<"  "<<s->val<<endl;
}
void dls_bianli (NODE *cp,int s,int m)
{
	NODE *temp;
	int i,j,l,k=0;
	for (i=1;i<=s;i++)
	{
		j=1;
		temp=(*(cp+i)).right;
		if ( temp!=cp+i )
		{
			do
			{
				for (l=j;l<temp->col;l++) cout<<"0 ";	//补上0
				cout<<temp->val<<" ";		//打印非零元素
				j=temp->col+1;
				k=1;
				temp=temp->right;
			}
			while ( temp!=cp+i );
		};
		for (l=j;l<=m;l++) cout<<"0 ";
		cout<<endl;
	};
	if (!k) cout<<"链表为空!"<<endl;
}
int  dls_search (NODE *cp,int t,int s,int n,int m)
{
	char choice='x';
	int lov=0;
	NODE *temp;
	do
	{
		cout << "\t\t\t     (0)   输入行列下标" << endl;
		cout << "\t\t\t     (1)   输入元素数值" << endl;
		cout<<"请选择: ";
		choice=getche();
		cout<<endl;
		if (choice!='0' && choice!='1')
			cout << "输入错误，请重新输入!"<<endl;
	}
	while (choice!='0' && choice!='1');
	switch (choice)
	{
	case '0':				//按坐标检索
		{
			int r,c;
			cout<<"请输入所要查找的坐标: ";
			cin>>r>>c;
			if (r>n || c>m || r<1 || c<1) 
			{
				cout<<"行、列数错误!"<<endl;
				return(0);
			};
			cout<<"检索该节点所走过的元素下标序列:"<<endl;
			temp=(*(cp+r)).right;
			while (temp!=cp+r)
			{
				if (temp->row==r && temp->col==c)
				{
					cout<<"("<<temp->row<<","<<temp->col<<")"<<endl;
					cout<<"元素已找到: ";
					dls_printer(temp);
					return(1);
				};
				cout<<"("<<temp->row<<","<<temp->col<<")";
				if (temp->right!=cp+r) cout<<"->";
				else cout<<endl;
				temp=temp->right;
			};
			return(0);
			break;
		};
	case '1':			//按元素值检索
		{
			int i,v;
			cout<<"请输入矩阵元素值: ";
			cin>>v;
			for (i=1;i<=s;i++)
			{
				temp=(*(cp+i)).right;
				if ( temp!=cp+i )
				{
					do
					{
						if (temp->val==v)
						{
							lov=1;
							cout<<"元素已找到: ";
							cout<<"("<<temp->row<<","<<temp->col<<")"<<endl;
							cout<<"检索该节点所走过的元素下标序列:"<<endl;
							int j,k=0;
							NODE *temp1;
							for (j=1;j<=s;j++)
							{
								temp1=(*(cp+j)).right;
								if ( temp1!=cp+j )
								{
									do
									{
										if (temp1->row==temp->row && temp1->col==temp->col)
										{
											cout<<"("<<temp1->row<<","<<temp1->col<<")"<<endl;
											k=1;
										};
										if (k) break;
										cout<<"("<<temp1->row<<","<<temp1->col<<")"<<"->";
										temp1=temp1->right;
									}
									while (temp1!=cp+j);
								};
								if (k) break;
							};
						};
						temp=temp->right;
					}
					while ( temp!=cp+i );
				};
			};
			break;
		};
	default:
		{
			cout << "输入错误!"<<endl;
			break;
		};
	};
	if (!lov)
	{
		int i;
		cout<<"检索该节点所走过的元素下标序列:"<<endl;
		for (i=1;i<=s;i++)
		{
			temp=(*(cp+i)).right;
			if ( temp!=cp+i )
			{
				do
				{
					cout<<"("<<temp->row<<","<<temp->col<<")";
					if (temp->row==n && temp->right==cp+i) cout<<endl;
					else cout<<"->";
					temp=temp->right;
				}
				while ( temp!=cp+i );
			};
		};
	};
	return(lov);
}
void dls_saver  (NODE *cp, int s)
{
	ofstream fout;
	const char *saver="saved.dat";

	fout.open(saver,ios::out|ios::binary);			//打开文件
	if(!fout.is_open())
	{
		cout << "打开文件" << saver << "失败！" << endl;
		exit(1);
	};

	NODE *temp;
	int i;
	for (i=1;i<=s;i++)
	{
		temp=(*(cp+i)).right;
		if ( temp!=cp+i )
		{
			do
			{
				fout.write((char *)temp,sizeof(NODE));
				temp=temp->right;
			}
			while ( temp!=cp+i );
		};
	};
	fout.close();		//关闭文件
	cout<<"保存成功!"<<endl;
}
NODE *dls_loader(NODE *cp,int s,int n,int m)
{
	int i;
	NODE *temp1,*temp2;
	for (i=1;i<=s;i++)
	{
		temp1=(*(cp+i)).right;
		temp2=(*temp1).right;
		while (temp2!=cp+i)
		{
			free(temp1);
			temp1=temp2;
			temp2=temp2->right;
		};
		if (temp1!=cp+i)free(temp1);
	};
	free(cp);
	cp=NULL;				//把原有的链表free掉，重建链表
	cp=(NODE *)malloc((s+1)*sizeof(NODE));
	(*cp).row=m;
	(*cp).col=n;
	for (i=1;i<=s;i++)
	{
		(*(cp+i)).row=0;
		(*(cp+i)).col=0;
		(*(cp+i)).down=cp+i;
		(*(cp+i)).right=cp+i;
		(*(cp+i)).val=0;
	};

	ifstream fin;
	const char *saver="saved.dat";
	NODE *w;
	fin.open(saver,ios::in|ios::binary);	//打开文件
	if (!fin.is_open())
	{
		cout << "\t\t系统加载文件 " << saver <<" 失败。" 
			 << endl << "请检查数据文件是否完整或向系统管理员咨询！" 
			 << endl;
		exit(1);
	};
	w=(NODE *)malloc(sizeof(NODE));
	if(!w)												//申请不成功则退出
	{	
		cout << "申请空间失败！" << endl 
		     << "存储空间不足，请扩充您的存储设备！"<< endl;
		exit(-1);
	};
	while ( fin.read( (char *)w,sizeof(NODE) ) )
	{
		dls_insert(w,cp,n,m);
		w=(NODE *)malloc(sizeof(NODE));
		if(!w)											//申请不成功则退出
		{	
			cout << "申请空间失败！" << endl 
			     << "存储空间不足，请扩充您的存储设备！"<< endl;
			exit(-1);
		};
	};
	return(cp);
}