大家好，又见面了，我是你们的朋友全栈君。
本来是想用二维数组实现的，但是想了一下发现，如果数据是稀疏矩阵的话，用二维数组存就会造成很多的空间浪费，而且遍历的时候也很浪费时间。学数据结构的时候书上教我们使用十字链表来存储稀疏矩阵，于是就想着用十字链表来实现。然后我发现我忘了十字链表的代码实现了…默默地去翻书，捣置了好久，终于写好了，乐滋滋的去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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/150328.html原文链接：https://javaforall.net
