matrix 基于十字链表的稀疏矩阵 C语言

//matrix.c #include "matrix.h" Matrix Matrix_Construct(unsigned long row_size, unsigned long col_size)//用行数和列数初始化矩阵大小 { unsigned i=0; unsigned long size=(row_size>col_size ? row_size : col_size);//取较大的数分配空间 Matrix headers=(Matrix)malloc(sizeof(Matrix_Node*)*size);//分配头结点指针数组 for (i=0; i<size; ++i) //各头结点分配空间和初始化 { headers[i] = (Matrix_Node*)malloc(sizeof(Matrix_Node)); headers[i]->left = headers[i]->right = headers[i]; headers[i]->up = headers[i]->down = headers[i]; headers[i]->row_index = row_size; //存储整个矩阵行数 headers[i]->col_index = col_size; //存储整个矩阵列数 } return headers; } bool Matrix_Destruct(Matrix headers) //析构矩阵，输入参数为头结点指针数组 { unsigned long row_size=0,col_size=0,size=0; unsigned long i=0; if (NULL==headers) //如果已经为空，则返回失败。 return false; row_size = headers[0]->row_index; //记录相关信息 col_size = headers[0]->col_index; size = row_size>col_size ? row_size : col_size; Matrix_Clear(headers); //清空数据结点 for (i=0; i<size; ++i) //清空头结点 free(headers[i]); free(headers); //清空头结点指针数组 return true; } bool Matrix_Clear(Matrix headers) //清空矩阵，输入参数为头结点指针数组 { unsigned long i=0; Matrix_Node* delNode=NULL; Matrix_Node* nextNode=NULL; unsigned long row_size=0,col_size=0; if (NULL==headers) //如果已经为空，返回失败 return false; row_size = headers[0]->row_index; //记录相关信息 col_size = headers[0]->col_index; for (i=0; i<row_size; ++i) //一行一行地删除 { delNode = headers[i]->right; while (delNode!=headers[i]) { nextNode = delNode->right; free(delNode); delNode = nextNode; } } for (i=0; i<col_size; ++i) //维护列指针 headers[i]->up = headers[i]->down = headers[i]; return true; } Matrix_Node* Matrix_LeftNode(Matrix_Node* currNode)//获取输入结点左边的结点 { if (NULL==currNode) //如果当前结点为空，则返回空指针 return NULL; else //否则返回左边的结点 return currNode->left; } Matrix_Node* Matrix_RightNode(Matrix_Node* currNode)//获取输入结点右边的结点 { if (NULL==currNode) //如果当前结点为空，则返回空指针 return NULL; else //否则返回右边的结点 return currNode->right; } Matrix_Node* Matrix_UpNode(Matrix_Node* currNode)//获取输入结点上边的结点 { if (NULL==currNode) //如果当前结点为空，则返回空指针 return NULL; else //否则返回上边的结点 return currNode->up; } Matrix_Node* Matrix_DownNode(Matrix_Node* currNode)//获取输入结点下边的结点 { if (NULL==currNode) //如果当前结点为空，则返回空指针 return NULL; else //否则返回下边的结点 return currNode->down; } Matrix_Node* Matrix_RowHeader(Matrix headers, unsigned long row_index)//获取指定行的头结点 { if (NULL==headers || row_index>=Matrix_RowSize(headers))//如果当前结点为空或下标越界，则返回空指针 return NULL; else //否则返回该行的头结点指针 return headers[row_index]; } Matrix_Node* Matrix_ColHeader(Matrix headers, unsigned long col_index)//获取指定列的头结点 { if (NULL==headers || col_index>=Matrix_ColSize(headers))//如果当前结点为空或下标越界，则返回空指针 return NULL; else //否则返回该列的头结点指针 return headers[col_index]; } unsigned long Matrix_RowSize(Matrix headers) //获取矩阵行数 { if (NULL==headers) //如果头结点为空指针，则认为大小为0 return 0; else //否则返回构造时记录的行数 return headers[0]->row_index; } unsigned long Matrix_ColSize(Matrix headers) //获取矩阵列数 { if (NULL==headers) //如果头结点为空指针，则认为大小为0 return 0; else //否则返回构造时记录的列数 return headers[0]->col_index; } bool Matrix_SetValue(Matrix headers, unsigned long row_index, unsigned long col_index, VALUE_TYPE val)//插入数值 { Matrix_Node* leftNode=NULL; Matrix_Node* rightNode=NULL; Matrix_Node* upNode=NULL; Matrix_Node* downNode=NULL; Matrix_Node* currNode=NULL; if (NULL==headers) //如果矩阵头指针为空，则插入操作失败 return false; if (row_index>=Matrix_RowSize(headers) || col_index>=Matrix_ColSize(headers))//如果下标越界，则操作失败 return false; //查找是否在该位置已经存在结点 currNode=headers[row_index]->right; while (currNode!=headers[row_index]) //查找是否已经存在该结点 { if (currNode->col_index==col_index) break; currNode = currNode->right; } if (currNode!=headers[row_index]) //如果已经在该位置存在结点 { currNode->value = val; //覆盖原来的结点存储值 return true; //操作成功 } //如果不存在该结点，就要进行结点插入动作 //定位左右邻居(同一行) rightNode = headers[row_index]->right; while (rightNode!=headers[row_index] && rightNode->col_index<col_index) rightNode = rightNode->right; leftNode = rightNode->left; //定位上下邻居(同一列) downNode = headers[col_index]->down; while (downNode!=headers[col_index] && downNode->row_index<row_index) downNode = downNode->down; upNode = downNode->up; //初始化结点 currNode = (Matrix_Node*)malloc(sizeof(Matrix_Node)); currNode->row_index = row_index; currNode->col_index = col_index; currNode->value = val; //插入结点 currNode->left = leftNode; currNode->right = rightNode; currNode->up = upNode; currNode->down = downNode; leftNode->right = currNode; rightNode->left = currNode; upNode->down = currNode; downNode->up = currNode; return true; } bool Matrix_GetValue(Matrix headers, unsigned long row_index, unsigned long col_index, VALUE_TYPE* val_addr)//根据位置查找值 { Matrix_Node* currNode=NULL; if (NULL==headers) //如果头结点数组为空，则矩阵为空，查找失败 return false; if (row_index>=Matrix_RowSize(headers) || col_index>=Matrix_ColSize(headers))//如果下标越界，则操作失败 return false; currNode=headers[row_index]->right; while (currNode!=headers[row_index]) //查找是否已经存在该结点 { if (currNode->col_index==col_index) { *val_addr = currNode->value; //查找到结点，为目标地址赋值 return true; //查找成功 } currNode = currNode->right; } return false; //没有查找到 } VALUE_TYPE* Matrix_ValueAt(Matrix headers, unsigned long row_index, unsigned long col_index)//根据位置信息查找值 { Matrix_Node* currNode=NULL; if (NULL==headers) //如果头结点数组为空，则矩阵为空，查找失败 return NULL; if (row_index>=Matrix_RowSize(headers) || col_index>=Matrix_ColSize(headers))//如果下标越界，则操作失败 return NULL; currNode=headers[row_index]->right; while (currNode!=headers[row_index]) //查找是否已经存在该结点 { if (currNode->col_index==col_index) return &currNode->value; //查找到结点，返回value的地址 currNode = currNode->right; } return NULL; //没有查找到