稀疏矩阵压缩存储实现-三组1数据结构设计和头文件创建1.1数据结构设计1.2数据结构实现1.3核心代码创建2.1数据结构基本操作测试2.2核心代码测试*3头文件完全定义
1数据结构设计和头文件创建
这里太懒了，把代码都塞进了文件里。 如果需要的话，把它简单地分割就可以了。
1.1数据结构设计
如上所述，需要设计存储从稀疏矩阵转换的三维节目记录的三维节目数据节点。 具体设计如下(采用单链表-链式存储结构) :
//数据元素-数据类型typedef int ElemType； /***三元组节点*/typedefstructtuplenode { int rowindex； //节点行号int colIndex； //节点列号ElemType value； //节点值struct tupleNode* next； //指针字段}tupleNode，tupleTable； 针对三元组的基本操作，设计如下。
//初始化三维节目表(提供不存储任何数据的头节点) intinittupletable (tuple table * * ptable )； //获取三元节目表长度的inttupletablelength (tuple table * ptable ) /确定三元节目表是否为空的inttupletableempty (tuple table * ptable ) /打印三元节目表voidid 插入三元组节点(尾插法) intaddtuplenode (tuple table * * ptupletable，int row，int col， ElemType e ) /删除三元组节点intremovetupler tuple node * ptuplenode (1.2数据结构实现# include stdio.h # include stdlib.h//数据/***三元组节点*/typedefstructtuplenode { int rowindex； //节点行号int colIndex； //节点列号ElemType value； //节点值struct tupleNode* next； //指针字段}tupleNode，tupleTable； /**初始化三元节目表(提供不存储任何数据的头节点)/intinittupletable (tuple table * * ptable ) ptable=(tuple node * ) malloc ) sizeof if(ptable==null ) return 0； (*pTable )-rowIndex=-1； (*pTable )-colIndex=-1； (*可移植)-value=0； (*pTable )-next=NULL； 返回1； }/***三元组表的长度*/inttupletablelength (tuple table * ptable ) {int len=0； tupleTable* pt=NULL； //辅助指针//确定三元组表是否为空if(ptable==null )返回len的pt=pTable-next； wile(pt！=NULL ) {len； pt=pt-next； }返回len； }/***判断三元节目表是否为空的*/inttupletableempty (tuple table * ptable ) {return pTable-next==NULL？ 1:0； }/***三元组表*/voidprinttupletable ({ tupletable*ptable ) ) tuple table * pt； //判断三元节目表中是否存在if(ptable==null ) return的pt=pTable-next； //打印元素值printf(rowtcoltvaluen )； wile(pt！=NULL ) printf('%dt%dt%dn '，pt-rowIndex，pt-colIndex，pt-value )； pt=pt-next； }返回； (}/***插入三元组节点(尾插)/intaddtuplenode ) tupletable**ptupletable，int row，int col，ElemType e ) tuple node * ptable=null(ptable=ptable-next； //新的三元组节点pnode=(tuplenode* ) malloc (sizeof ) tuplenode )； if(pnode==null ) return 0； pNode-rowIndex=row； pNode-colIndex=col； pNode-val
ue=e;pNode->next=NULL;//插入新的结点pNode->next=pTable->next;pTable->next=pNode;return 1;}/*** 删除三元组的结点*/int RemovetupleNode(tupleTable** ptupleTable,tupleNode* ptupleNode){tupleNode *pTable=*ptupleTable,//辅助指针*pNodePre=NULL,*pNode=NULL;//要被删除的结点//判断三元组表是否存在if (pTable==NULL) return 0;//判断三元组表是否为空if (TupleTableEmpty(pTable)) return 0;//查找最后一个结点pNodePre=pTable;pNode=pNodePre->next;while (pNode->next!=NULL) {pNodePre=pNode;pNode=pNode->next;}//记录要被删除的结点值(*ptupleNode).rowIndex=pNode->rowIndex;(*ptupleNode).colIndex=pNode->colIndex;(*ptupleNode).value=pNode->value;//删除节点pNodePre->next=NULL;free(pNode);return 1;} 1.3 核心代码编写 核心代码即为稀疏矩阵转为三元组表的操作，算法设计如下，
【1】逐行逐列遍历n阶矩阵中的数据元素，判断其值是否有效（此处元素值为0为无效值）；
【2】若元素值有效，调用AddtupleNode方法将其入表；若元素值无效，则进行下一个元素值的判断，直到全部数据元素遍历完毕。
其时间复杂度为O(n^2)。
测试三元组的插入、删除、获取长度、打印等基本操作。
#include "Practice345.h"void test_basic();int main(int argc,char** argv){test_basic();return 0;}void test_basic(){//定义三元组tupleTable* tTable=NULL;tupleNode tNode={-1,-1,0,NULL};//初始化三元组InitTupleTable(&tTable);printf("row=%d,col=%d,value=%d,next=%dn",tTable->rowIndex,tTable->colIndex,tTable->value,tTable->next);printf("tupleTable is Empty?%dn",TupleTableEmpty(tTable));//添加结点AddtupleNode(&tTable,0,0,12);AddtupleNode(&tTable,0,1,13);AddtupleNode(&tTable,0,2,14);printf("n");printTupleTable(tTable);printf("n");printf("tupleTable is Empty?%dn",TupleTableEmpty(tTable));printf("tupleTableLength=%dn",TupleTableLength(tTable));RemovetupleNode(&tTable,&tNode);RemovetupleNode(&tTable,&tNode);RemovetupleNode(&tTable,&tNode);printf("row=%d,col=%d,value=%d,next=%dn",tNode.rowIndex,tNode.colIndex,tNode.value,tNode.next);printf("tupleTableLength=%dn",TupleTableLength(tTable));} 2.2 核心代码测试测试稀疏数组转化为三元组，及其转化结果的打印。
#include "Practice345.h"/*** 给定稀疏矩阵*/ElemType sparseMatrix[4][4]={{4,0,0,0},{0,0,6,0},{0,9,0,0},{0,23,0,0}} ;//主函数int main(int argc,char** argv){//定义三元组tupleTable* pRes=NULL;//稀疏矩阵转为三元组表pRes=sparseMatrixTotupleTable(sparseMatrix,4);printf("tupleTable is Empty?%dn",TupleTableEmpty(pRes));printf("tupleTableLength=%dn",TupleTableLength(pRes));printTupleTable(pRes);return 0;} *3 头文件完整定义 #include <stdio.h>#include <stdlib.h>//数据元素-数据类型typedef int ElemType;/*** 定义三元组结点*/typedef struct tupleNode{int rowIndex;//结点行号int colIndex;//结点列号ElemType value;//结点值struct tupleNode* next;//指针域}tupleNode,tupleTable;/*** 初始化三元组表[提供头结点,不存储任何数据]*/int InitTupleTable(tupleTable** pTable){*pTable=(tupleNode*)malloc(sizeof(tupleNode));if (pTable==NULL) return 0;(*pTable)->rowIndex=-1;(*pTable)->colIndex=-1;(*pTable)->value=0;(*pTable)->next=NULL;return 1;}/*** 获取三元组表的长度*/int TupleTableLength(tupleTable* pTable){int len=0;tupleTable* pt=NULL;//辅助指针//判断三元组表是否为空if (pTable==NULL) return len;pt=pTable->next;while (pt!=NULL){len++;pt=pt->next;}return len;}/*** 判断三元组表是否为空*/int TupleTableEmpty(tupleTable* pTable){return pTable->next==NULL?1:0;}/*** 打印三元组表*/void printTupleTable(tupleTable* pTable){tupleTable* pt;//判断三元组表是否存在if (pTable==NULL) return;pt=pTable->next;//打印元素值printf("rowtcoltvaluen");while (pt!=NULL){printf("%dt%dt%dn",pt->rowIndex,pt->colIndex,pt->value);pt=pt->next;}return;}/*** 插入三元组结点[尾插法]*/int AddtupleNode(tupleTable** ptupleTable,int row,int col,ElemType e){tupleNode *pTable=*ptupleTable,//辅助指针*pNode=NULL;//新节点//判断三元组表是否存在if (pTable==NULL) return 0;//查找尾结点while (pTable->next!=NULL)pTable=pTable->next;//创建新的三元组结点pNode=(tupleNode*)malloc(sizeof(tupleNode));if (pNode==NULL) return 0;pNode->rowIndex=row;pNode->colIndex=col;pNode->value=e;pNode->next=NULL;//插入新的结点pNode->next=pTable->next;pTable->next=pNode;return 1;}/*** 删除三元组的结点*/int RemovetupleNode(tupleTable** ptupleTable,tupleNode* ptupleNode){tupleNode *pTable=*ptupleTable,//辅助指针*pNodePre=NULL,*pNode=NULL;//要被删除的结点//判断三元组表是否存在if (pTable==NULL) return 0;//判断三元组表是否为空if (TupleTableEmpty(pTable)) return 0;//查找最后一个结点pNodePre=pTable;pNode=pNodePre->next;while (pNode->next!=NULL) {pNodePre=pNode;pNode=pNode->next;}//记录要被删除的结点值(*ptupleNode).rowIndex=pNode->rowIndex;(*ptupleNode).colIndex=pNode->colIndex;(*ptupleNode).value=pNode->value;//删除节点pNodePre->next=NULL;free(pNode);return 1;}/*** n阶稀疏矩阵转为三元组*/tupleTable* sparseMatrixTotupleTable(ElemType sMatrix[][4],int n ){int i,j;//定义三元组表tupleTable* pTable;InitTupleTable(&pTable);//处理稀疏矩阵for (i=0;i<n;i++){for (j=0;j<n;j++){if (sMatrix[i][j]!=0){printf("%d ",sMatrix[i][j]);AddtupleNode(&pTable,i,j,sMatrix[i][j]);}}printf("n");}//printTupleTable(pTable);return pTable;}