本文共 6177 字，大约阅读时间需要 20 分钟。
#include #include #include #include using namespace std;/*问题:在地理数据库中存储邻居的系统。共有两千个邻居，编号范围是0~1999，每个邻居在地图张用一个点来描述。 系统允许用户通过触摸输入板的方式访问其中任意一点。程序将选定的物理位置转换为0~199范围内的一对整数 x和y，然后使用(x,y)对支出用户选中了“2000”个点中的哪一个点。 在一台具有上百兆字节内存的计算机上表示一个具有100万个活跃项的10 000 * 10 000的矩阵。分析：本质上是一个稀疏矩阵。我们知道稀疏矩阵的一种表示方法是三维组: 实现1：用数组表示列，数组上每一个元素是一个链表，链表来表示同一列上不同行号的元素。例如:列 行 值 行 值 行 值 0 ->2 17->5 538 -> 126 1053 1 ->1 98->138 152实现2：如果不能采用结构体，就使用3个数组表示，。数组col[matrixSize] : 下标表示:列号， 数组元素的值表示：该下标对应的列对应的行号在行号数组的下标数组row[elementSize]: 下标表示：行号数组中行号下标（被列号数组指向） ， 数组元素的值表示：行号,新的一列对应的起始行号数组num[elementSize]: 对应行号的元素值例如:num:元素 17 538 1053 98 15row:元素 2 5 126 138 11 ... 111 67col:元素 0 3 5 5 ... 1998 2000 下标 0 1 2 3 ... 199 200输入:200(矩阵的行长度，列长度) 5(矩阵中的元素个数n，接下来有n行)2 0 17(第一个元素是行号，第二个元素是列号，第三个元素是值)5 0 538126 0 10531 1 98138 1 15输出:(输出所有元素)2 0 175 0 538126 0 10531 1 98138 1 15关键:1 本质上是一个稀疏矩阵。我们知道稀疏矩阵的一种表示方法是三维组: 实现1：用数组表示列，数组上每一个元素是一个链表，链表来表示同一列上不同行号的元素。例如:列 行 值 行 值 行 值 0 ->2 17->5 538 -> 126 1053 1 ->1 98->138 152实现2：如果不能采用结构体，就使用3个数组表示，。数组col[matrixSize] : 下标表示:列号， 数组元素的值表示：该下标对应的列对应的行号在行号数组的下标数组row[elementSize]: 下标表示：行号数组中行号下标（被列号数组指向） ， 数组元素的值表示：行号,新的一列对应的起始行号数组num[elementSize]: 对应行号的元素值例如:num:元素 17 538 1053 98 15row:元素 2 5 126 138 11 ... 111 67col:元素 0 3 5 5 ... 1998 2000 下标 0 1 2 3 ... 199 200*/typedef struct Node{ Node():_next(NULL),_value(-1),_rowNumber(-1){} Node* _next; int _value; int _rowNumber;}Node;//const int MAXSIZE = 10000;//Node* gNodeArray[MAXSIZE];//稀疏矩阵表示:用一个链表数组表示，数组的下标：表示列号，数组中的元素：链表的结点，结点中包含：行号，值，指向下一个结点的指针void print(Node** nodeArray , int matrixSize){ if(NULL == nodeArray || matrixSize <= 0) { cout << "no result" << endl; return; } for(int i = 0 ; i < matrixSize ; i++) { Node* node = nodeArray[i]; if(NULL == nodeArray[i]) { continue; } while(node) { cout << node->_rowNumber << " " << i << " " << node->_value << endl; node = node->_next; } }}//释放链表数组的内存void releaseList(Node** nodeArray , int matrixSize){ if(NULL == nodeArray) { return; } //先删除每个结点对应的链表，再删除链表数组指针 for(int i = 0 ; i < matrixSize; i++) { if(NULL == nodeArray[i]) { continue; } Node* node = nodeArray[i]; while(node) { Node* tempNode = node->_next; delete node; node = tempNode; } } delete[] nodeArray;}//矩阵元素，包含：行号，列号，值typedef struct MatrixElement{ MatrixElement(int rowNum , int colNum , int value):_rowNum(rowNum),_colNum(colNum),_value(value){} int _rowNum; int _colNum; int _value; bool operator < (const MatrixElement& element) const { if(_colNum != element._colNum) { return _colNum < element._colNum; } else { return _rowNum < element._rowNum; } }}MatrixElement;void storeSparseMatrix_ByListArray(vector & matrixElements , int matrixSize){ if(matrixElements.empty() || matrixSize <= 0) { return; } int elementSize = matrixElements.size(); Node** nodeArray = new Node*[matrixSize]; memset(nodeArray , NULL , sizeof(nodeArray) * matrixSize); //输入三元组 <行号，列号，值> ：并进行存储 for(int i = 0 ; i < elementSize ; i++) { MatrixElement matrixElement = matrixElements.at(i); int rowNum = matrixElement._rowNum; int colNum = matrixElement._colNum; int value = matrixElement._value; Node* node = new Node(); node->_rowNumber = rowNum; node->_value = value; //如果对应的列还没有存储，就新建结点 if(NULL == nodeArray[colNum]) { nodeArray[colNum] = node; } //列已经存在，就采用尾插法，插入在尾部 else { Node* previousNode = NULL; Node* curNode = nodeArray[colNum]; while(curNode) { previousNode = curNode; curNode = curNode->_next; } previousNode->_next = node; } } //输出结果 print(nodeArray , matrixSize); releaseList(nodeArray , matrixSize);}void printSparseMatrix_ByThreeArray(int* colArray , int colSize , int* rowArray , int* pointNumArray , int elementSize){ if((!colArray) || (!rowArray) || (!pointNumArray) || colSize <= 0 || elementSize <= 0) { cout << "no result" << endl; } int j = 0; for(int i = 1 ; i < colSize ; i++) { int rowIndex = colArray[i-1]; //如果新的一列元素的行的起始位置小于0，说明该列上没有元素，无需处理 if(rowIndex < 0) { continue; } int nextRowIndex = colArray[i]; for(j = rowIndex ; j < nextRowIndex ; j++) { cout << rowArray[j] << " " << i -1 << " " << pointNumArray[j] << endl; } } //最后一列的元素行号起始下标到最后元素个数需要打印 int rowIndex = colArray[colSize - 1]; for(j = rowIndex ; j >= 0 && j < elementSize ; j++) { cout << rowArray[j] << " " << colSize - 1 << " " << pointNumArray[j] << endl; }}//采用三个数组存储稀疏矩阵元素void storeSparseMatrix_ByThreeArray(vector & matrixElements , int matrixSize){ if(matrixElements.empty() || matrixSize <= 0) { return; } int elementSize = matrixElements.size(); if(elementSize <= 0) { return; } int* colArray = new int[matrixSize]; memset(colArray , -1 , sizeof(colArray) * matrixSize);//初始化所有指向新的一列元素的行的起始位置为-1 int* rowArray = new int[elementSize]; int* pointNumArray = new int[elementSize]; //存储每个稀疏矩阵元素中新的一列对应的行号起始位置，这样需要统计属于同一列的所有元素：这样的话，需要事先按照列号进行排序 sort(matrixElements.begin() , matrixElements.end()); int previousColNum; int j = 0; for(int i = 0 ; i < elementSize ; i++) { MatrixElement element = matrixElements.at(i); int rowNum = element._rowNum; int colNum = element._colNum; int value = element._value; if(0 == i) { previousColNum = colNum; colArray[j++] = 0;//第一个列对应的起始行号肯定为0 } rowArray[i] = rowNum; pointNumArray[i] = value; //如果当前元素的列号和上一个元素的列号不同，那么将当前元素的计数下标作为新的一列起始的行号行号下标 if(previousColNum != colNum) { colArray[j++] = i;//记录新的一列对应的起始元素所在行号下标 previousColNum = colNum; } } //元素全部存储好了之后，打印 printSparseMatrix_ByThreeArray(colArray , j , rowArray , pointNumArray , elementSize); delete[] rowArray; delete[] colArray; delete[] pointNumArray;}void process(){ int matrixSize; int elementSize; int rowNum; int colNum; int value; vector matrixElements; //输入矩阵长度，元素个数 while(cin >> matrixSize >> elementSize) { matrixElements.clear(); //实例化一个数组，用于存储，由于矩阵长度为matrixSize,因此，数组大小为matrix。 这里建立的指针数组，对象数组会有问题 Node** nodeArray = new Node*[matrixSize]; memset(nodeArray , NULL , sizeof(nodeArray) * matrixSize); //输入三元组 <行号，列号，值> ：并进行存储 for(int i = 0 ; i < elementSize ; i++) { cin >> rowNum >> colNum >> value; MatrixElement matrixElement(rowNum , colNum , value); matrixElements.push_back(matrixElement); } //storeSparseMatrix_ByListArray(matrixElements , matrixSize); storeSparseMatrix_ByThreeArray(matrixElements , matrixSize); }}int main(int argc , char* argv[]){ process(); getchar(); return 0;}
转载地址：http://chofn.baihongyu.com/