杭电 1142 十字链表存储

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

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