杭电 1142 十字链表存储

全栈程序员-用户IM • 2022年6月18日下午1:36 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

　　本来是想用二维数组实现的，但是想了一下发现，如果数据是稀疏矩阵的话，用二维数组存就会造成很多的空间浪费，而且遍历的时候也很浪费时间。学数据结构的时候书上教我们使用十字链表来存储稀疏矩阵，于是就想着用十字链表来实现。然后我发现我忘了十字链表的代码实现了…默默地去翻书，捣置了好久，终于写好了，乐滋滋的去oj提交代码，结果时间超限……

　　哎~ 把代码贴上来，就当加深一下十字链表的记忆吧~~

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
using namespace std;
multiset<int> s;
typedef struct lei
{ 
   
	int row,col;
	struct lei *right;   //行指针
	struct lei *down;    //列指针
	union                //共用体结构
	{ 
   
		int value;       //数据域
		struct lei *link;//头结点指针域
	}tag;
}lei;
lei *h[1001];
void Init(lei *&mh,int n,int m)   //初始化
{ 
   
	lei *r;
    mh=(lei *)malloc(sizeof(lei));//十字链表的入口
	mh->row=n;                             
	mh->col=m;                               
	r=mh;
	for(int i=0;i<10;i++)         //建立一个列表，其每个结点即为行表的头结点，也为列表的头结点，通过i（right）,j（down）来判断此时是用行，还是列）
	{ 
   
		h[i]=(lei *)malloc(sizeof(lei));
		h[i]->down=h[i]->right=h[i];   //成环
		r->tag.link=h[i];              //说明他是一个头结点
		r=h[i];
	}
	r->tag.link=mh;                    //成环
}
void Push(int x,int y,int t)//插入元素
{ 
   
	lei *p,*q;              //r为第一个头结点
    p=(lei *)malloc(sizeof(lei));
	p->row=x;
	p->col=y;
	p->tag.value=t;
	q=h[x-1];               //h[x-1]为第x行的头结点
	while(q->right!=h[x-1] && q->right->col<y)//行表插入
	{ 
   
		q=q->right;
	}
	p->right=q->right;
    q->right=p;
	q=h[y-1];              //h[j-1] 为第y列的头结点
	while(q->down!=h[y-1] && q->down->row<x)//列表插入
	{ 
   
		q=q->down;
	}
	p->down=q->down;
	q->down=p;
}
lei* zhao(int x,int y)//找关于对角线对称的元素
{ 
   
	lei *r;
	r=h[x-1]->right;
	while(r->col!=y) //找列
		r=r->right;
	return r;
}
void cha(int x,int sum)//链表入口，下条路横坐标，总路程
{ 
   
	lei *p,*q,*r;
	int k;
	r=h[x-1]; //找行头结点
	p=r;             //第 x 行的头指针
	r=r->right;      //第 x 行的第一个元素
	while(r!=p)
	{ 
   
		if(r->tag.value==0||r->col==1)
		{ 
   
			r=r->right;
			continue;
		}
		if(r->col==2)
		{ 
   
			s.insert(sum+r->tag.value);
			r=r->right;
			continue;
		}
		k=r->tag.value;
        q=zhao(r->col,r->row);
		q->tag.value=0;
		r->tag.value=0;       //标记，已经走过了
		cha(r->col,sum+k);    //递归
		r->tag.value=k;
		q->tag.value=k;       //取消标记
		r=r->right;
	}
}
void shi(lei *mh)         //释放空间
{ 
   
    lei *p,*q,*r;
    p=mh->tag.link;
    while (p!=mh)
    { 
   
        q=p->right;
        while (p!=q)
        { 
   
			r=q;
            q=q->right;
			free(r);
        }
        p=p->tag.link;
    }
}
int main()
{ 
   
    lei *mh;
	int n,m;
	start=clock();
	while(scanf("%d",&n),n!=0)
	{ 
   
		scanf("%d",&m);
        Init(mh,n,m);
    	int x,y,t;
    	for(int i=0;i<m;i++)
		{ 
   
    		scanf("%d %d %d",&x,&y,&t);
	    	Push(x,y,t);
			if(y!=2)
	         	Push(y,x,t);
		}
		cha(1,0);
		printf("%d\n",s.count(*s.begin()));
	}
	shi(mh);
    return 0;
}