// Sparse Array Assignment.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
using namespace std;
struct node{
int row;
int col;
int value;
node* next_in_row;
node* next_in_col;
};
class MultiLinkedListSparseArray {
private:
char *logfile;
node** rowPtr;
node** colPtr; // used in constructor
node* find_node(node* out);
node* ins_node(node* ins,int col);
node* in_node(node* ins,node* z);
node* get(node* in,int row,int col);
bool exist(node* so,int row,int col);
node* dummy;
int rowd,cold;
//add anything you need
public:
MultiLinkedListSparseArray(int rows, int cols);
~MultiLinkedListSparseArray();
void setCell(int row, int col, int value);
int getCell(int row, int col);
void display();
void log(char *s);
void dump();
};
MultiLinkedListSparseArray::MultiLinkedListSparseArray(int rows,int cols){
rowPtr=new node* [rows+1];
colPtr=new node* [cols+1];
for(int n=0;n<=rows;n++)
rowPtr[n]=NULL;
for(int i=0;i<=cols;i++)
colPtr[i]=NULL;
rowd=rows;cold=cols;
}
MultiLinkedListSparseArray::~MultiLinkedListSparseArray(){
cout<<"array is deleted"<<endl;
for(int i=rowd;i>=0;i--){
for(int j=cold;j>=0;j--){
if(exist(rowPtr[i],i,j))
delete get(rowPtr[i],i,j);
}
} // it stops in the last loop & doesnt show the done word
cout<<"done"<<endl;
delete [] rowPtr;
delete [] colPtr;
delete dummy;
}
void MultiLinkedListSparseArray::log(char *s){
logfile=s;
}
void MultiLinkedListSparseArray::setCell(int row,int col,int value){
if(exist(rowPtr[row],row,col)){
(*get(rowPtr[row],row,col)).value=value;
}
else{
if(rowPtr[row]==NULL){
rowPtr[row]=new node;
(*rowPtr[row]).value=value;
(*rowPtr[row]).row=row;
(*rowPtr[row]).col=col;
(*rowPtr[row]).next_in_row=NULL;
(*rowPtr[row]).next_in_col=NULL;
}
else if((*find_node(rowPtr[row])).col<col){
node* out;
out=find_node(rowPtr[row]);
(*out).next_in_row=new node;
(*((*out).next_in_row)).col=col;
(*((*out).next_in_row)).row=row;
(*((*out).next_in_row)).value=value;
(*((*out).next_in_row)).next_in_row=NULL;
}
else if((*find_node(rowPtr[row])).col>col){
node* ins;
ins=in_node(rowPtr[row],ins_node(rowPtr[row],col));
node* g=(*ins).next_in_row;
(*ins).next_in_row=new node;
(*((*ins).next_in_row)).col=col;
(*(*ins).next_in_row).row=row;
(*(*ins).next_in_row).value=value;
(*(*ins).next_in_row).next_in_row=g;
}
}
}
int MultiLinkedListSparseArray::getCell(int row,int col){
return (*get(rowPtr[row],row,col)).value;
}
void MultiLinkedListSparseArray::display(){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
if(exist(rowPtr[i],i,j))
cout<<(*get(rowPtr[i],i,j)).value<<" ";
else cout<<"0"<<" ";
}
cout<<endl;
}
}
node* MultiLinkedListSparseArray::find_node(node* out)
{
while((*out).next_in_row!=NULL)
out=(*out).next_in_row;
return out;
}
node* MultiLinkedListSparseArray::ins_node(node* ins,int col){
while(!((*ins).col>col))
ins=(*ins).next_in_row;
return ins;
}
node* MultiLinkedListSparseArray::in_node(node* ins,node* z){
while((*ins).next_in_row!=z)
ins=(*ins).next_in_col;
return ins;
}
node* MultiLinkedListSparseArray::get(node* in,int row,int col){
dummy=new node;
dummy->value=0;
while((*in).col!=col){
if((*in).next_in_row==NULL){
return dummy;
}
in=(*in).next_in_row;
}
return in;
}
bool MultiLinkedListSparseArray::exist(node* so,int row,int col){
if(so==NULL)
return false;
else{
while((*so).col!=col){
if((*so).next_in_row==NULL)
return false;
else
so=(*so).next_in_row;
}
return true;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
MultiLinkedListSparseArray a(5, 5);
a.setCell(1, 5, 4);
a.setCell(2, 1, 2);
a.setCell(2, 2, 3);
a.setCell(3, 4, 5);
a.setCell(4, 1, 7);
a.setCell(4, 5, 8);
a.setCell(5, 2, 6);
cout << "X[4, 1] = " << a.getCell(4, 1) << endl;
cout << "X[4, 5] = " << a.getCell(4, 5) << endl;
cout << "X[2, 2] = " << a.getCell(2, 2) << endl;
cout << "X[5, 1] = " << a.getCell(5, 1) << endl;
a.display();
a.setCell(3, 4, 0);
a.setCell(1, 5, 0);
cout<<a.getCell(1,5)<<endl;
a.setCell(2, 2, 0);
a.setCell(5, 2, 0);
a.setCell(4, 5, 0);
//a.setCell(2, 5, 7); // problem WHY????????!!!!!!!!!!!!!!!
a.setCell(5, 3, 8);
a.setCell(2, 3, 5);
a.setCell(2, 5, 3);
a.setCell(2, 1, 0);
a.setCell(4, 2, 4);
a.setCell(4, 2, 2);
a.setCell(4, 2, 0);
a.setCell(4, 1, 0);
a.setCell(2, 3, 0);
a.setCell(2, 5, 0);
a.setCell(5, 3, 0);
a.display();
return 0;
}
1 个解决方案
#1
3
Things obviously go wrong, because get method (which, as I assume should be marked as const) makes memory allocation. I don't get the reason why this should be done and you should think about it.
事情显然是错的,因为get方法(我假设应该标记为const)进行内存分配。我不明白为什么要这样做,你应该考虑一下。
So, your get methods allocates memory for dummy every time it is called (this is a leak). But, what is even worse, if sequence of user actions with your class doesn't have one or more calls to get, your dummy remains simply an uninitialized pointer. Then, when you call your destructor, you will get an error, because you can't dispose memory pointed by a garbage pointer.
因此,每次调用时,你的get方法都会为虚拟机分配内存(这是一个泄漏)。但是,更糟糕的是,如果您的类的用户操作序列没有一个或多个调用get,则您的虚拟对象仍然只是一个未初始化的指针。然后,当您调用析构函数时,您将收到错误,因为您无法处置垃圾指针指向的内存。
Try to rethink, refactor or even rewrite your code.
尝试重新思考,重构甚至重写代码。
#1
3
Things obviously go wrong, because get method (which, as I assume should be marked as const) makes memory allocation. I don't get the reason why this should be done and you should think about it.
事情显然是错的,因为get方法(我假设应该标记为const)进行内存分配。我不明白为什么要这样做,你应该考虑一下。
So, your get methods allocates memory for dummy every time it is called (this is a leak). But, what is even worse, if sequence of user actions with your class doesn't have one or more calls to get, your dummy remains simply an uninitialized pointer. Then, when you call your destructor, you will get an error, because you can't dispose memory pointed by a garbage pointer.
因此,每次调用时,你的get方法都会为虚拟机分配内存(这是一个泄漏)。但是,更糟糕的是,如果您的类的用户操作序列没有一个或多个调用get,则您的虚拟对象仍然只是一个未初始化的指针。然后,当您调用析构函数时,您将收到错误,因为您无法处置垃圾指针指向的内存。
Try to rethink, refactor or even rewrite your code.
尝试重新思考,重构甚至重写代码。