利用十字链表压缩稀疏矩阵（c++）-- 数据结构

#include<iostream>
using namespace std;

//定义十字链表节点 
typedef struct matrinode{
    int i, j;
    struct matrinode *right, *down;
    union{
        int value;
        struct matrinode *next;
    }tag;
}matrinode;

//创建十字链表
//传入值：头节点指针，原矩阵行数，原矩阵列数 
void createlist(matrinode *&head, int row, int column) 
{
    int max = (row>column)?row:column;//取行列的最大值 
    //定义指针数组（用于表示行列头），p、q、r辅助指针 
    matrinode *h[max], *p, *q, *r;
    head = new matrinode;//申请头节点空间 
    head->i = row;//将行数、列数存入头节点 
    head->j = column;
    
    r = head;
    
    //行列链表头
    int count;
    for(count = 1; count<max+1; count++){//为了表示矩阵的行数和列数，这里从1开始计数 
        h[count] = new matrinode;//给行列链表头申请空间 
        h[count]->down = h[count]->right = h[count];
        h[count]->i = h[count]->j = 0;
        r->tag.next = h[count];//head->h[1]->h[2]->...->h[max] 
        r = h[count];
    }
    r->tag.next = head;//最后一个行列链表头节点指向head 
    
    int num;//非零元素个数 
    int i, j, v;
    cin>>num;
    for(count=1; count<num+1; count++){
        p = new matrinode;
        cin>>i>>j>>v;
        p->i = i;
        p->j = j;
        p->tag.value = v;
        
        
        /*这里插入非零元素有两种情况：（以在某行插入为例） 
        ①当行链表为空（q->right == h[count]）—或改元素列序数最大时 -> 插入到最后；
        ②非以上情况 -> 插入到某两节点中间 
        */
         
        //行插入 
        q = h[count];
        while(q->right != h[count] && q->right->j < j){
            q = q->right;
        }    
        p->right = q->right;
        q->right = p;
        //列插入    
        q = h[count];
        while(q->down != h[count] && q->down->i < i){
            q = q->down;
        }    
        p->down = q->down;
        q->down = p;
    } 
    
}


//查找是否有符合条件的值 
void search(matrinode *head)
{
    int value;//输入需要查找的值 
    cin>>value;
    
    matrinode *h, *p;//定义两个辅助结点
    h = new matrinode;
    p = new matrinode;

    h = head->tag.next;//h指向h[1] 
    p = h->right;//p指向h[1]第一列第一个元素 
    int flag = 0;//flag == 0表示找不到匹配值 
    int i, j;//若找到满足条件的值时，i、j存放该值的行和列 
    
    
    while(h->tag.next != head){//当前列不是最后一列时
        if(p == h){//若该列为空 
           h = h->tag.next;//移到下一列 
           p = h->right;
        }else{//若该列非空 
           if(p->tag.value != value){//若p节点存放的值！=需要查找的值时 
               p = p->right;//p移动到该列下一个 
           }else{//找到满足条件的值时 
               i = p->i;
               j = p->j;
               flag = 1;
               cout<<i<<" "<<j;
               break;
            }  
        }
}    
    if(flag == 0){
        cout<<"ERROR";
    }    
    
    
 } 


int main(){
    matrinode *head;
    int row, column;
    cin>>row>>column;
    createlist(head, row, column);
    
    search(head);
    return 0;
}