算法5.4 建立稀疏矩阵十字链表.txt

数据结构课件

MLink CreatMLink( ) /* 返回十字链表的头指针*/
｛
　　MLink H;
    Mnode *p,*q,*hd[s+1];  
    int i,j,m,n,t;
    datatype v; 
    scanf(“%d,%,%d”,&m,&n,&t); 
    H=malloc(sizeof(MNode));　　/*申请总头结点*/
    H->row=m; H->col=n;
    hd[0]=H;
    for(i=1; i<S; i++)
    {  p=malloc(sizeof(MNode));  /*申请第i个头结点*/
       p->row=0; p->col=0;
       p->right=p; p->down=p;
       hd[i]=p;
       hd[i-1]->v_next.next=p;
    }
    hd[S]->v_next.next=H; /*将头结点们形成循环链表*/
    for (k=1;k<=t;k++)
    {   scanf (“%d,%d,%d”,&i,&j,&v);  /*输入一个三元组，设值为int*/
        p=malloc(sizeof(MNode));
        p->row=i ; p->col=j; p->v_next.v=v
              /*以下是将*p插入到第i行链表中去，且按列号有序*/
        q=hd[i];
        while ( q->right!=hd[i]  &&  (q->right->col)<j )　/*按列号找位置*/
            q=q->right;
        p->right=q->right;　/*插入*/
        q->right=p;
              /*以下是将*p插入到第j行链表中去，且按行号有序*/
        q=hd[i];
        while ( q->down!=hd[j]  &&  (q->down->row)<i )　 /*按行号找位置*/
            q=q->down;
        p-> down =q-> down; /*插入*/
        q-> down =p;
    } /*for k*/
    return H;
}  /* CreatMLink */
算法5.4  建立稀疏矩阵的十字链表