Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
十字链表存储图_链式存储设计时,存储单元的地址,希望能够帮助你!!!。

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

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。