SparseVector.hh
class SparseVector
{
private:
//结构体不一定会用到，不用初始化
struct node
{
int index;
int value;
node *next; node(int index, int value, node *next = ) : index(index), value(value), next(next) {}
};
//这些才是真正的数据成员，要初始化的
int size;
node *start; void clear();
void copyList(const SparseVector &sv);
void setNonzeroElem(int index, int value);
void removeElem(int index);
void checkListOrder();
public:
SparseVector(int size);
const int getSize()const; ~SparseVector();
SparseVector(const SparseVector &sv);
SparseVector & operator= (const SparseVector &sv);
int getElem(int idx);
void setElem(int index, int value); };
SparseVector.cc
#include "SparseVector.hh"
#include <cassert>
#include <iostream>
using namespace std;
//单参数构造函数
SparseVector::SparseVector(int size):size(size)
{
start = ;
} const int SparseVector::getSize()const
{
return size;
}
//成员函数都默认带有this指针，所以默认对调用这个函数的对象进行操作，所以不用再传本对象的地址了。
void SparseVector::clear()
{
node *next;
node *current;
current = start;
while(current != )
{
next = current->next;
delete current;
current = next;
}
start = ;
}
//对本对象进行操作，调用成员行数也是默认对本对象进行操作，不用传本对象地址。
SparseVector::~SparseVector()
{
clear();
} void SparseVector::copyList(const SparseVector &sv)
{
size = sv.getSize();
node *current;
node *otherCurrent =sv.start;
node *prev = ; while(otherCurrent != )
{
current = new node(otherCurrent->index, otherCurrent->value);
if(prev == )
{
start = current;
prev = current;
}
prev->next = current;
prev = current;
otherCurrent = otherCurrent->next;
}
} SparseVector::SparseVector(const SparseVector &sv)
{
copyList(sv);
}
//注意自赋值，并且直接调用私有帮助函数。
SparseVector & SparseVector:: operator= (const SparseVector &sv)
{
if (this == &sv)
{
return *this;
}
clear();
copyList(sv);
return *this;
}
//难点
int SparseVector::getElem(int idx)
{
node *current = start;
while(current != && current->index < idx)//过滤，两个条件
{
current = current->next;
}
if(current == )//注意判断条件先后次序，先排除current为0情况
{
return ;
}
else if(current->index == idx)//如果先执行这个，则current为0时，会直接产生段错误
{
return current->value;
}
else
{
return ;
}
}
//难点，分种情况讨论：1,初始为空。2,插到最后面。3,插到最前面。4，插到中间。
void SparseVector::setNonzeroElem(int index, int value)
{
assert(value != );
node *current = start;
node *prev = ; if(start == )//容易遗漏，链表初始为空的情况。（1）
{
start = new node(index, value);
}
else//除此情况外（2,3,4）
{
while(current != && current->index < index)//过滤，两个条件，保证current指向应该指的结点，或其之后的结点。prev指向值小于应该的结点。
{
prev = current;
current = current->next;//别忘了自增
}
/*2选1
* if(current == start)//插到最前面，current所指结点大于等于它
{
if(current->index == index)//等于
{
current->value = value;
}
else//大于
{
node *other = new node(index, value, start);
start = other;
}
}
else if(current == 0)//插到最后面，current所指结点小于它
{
node *other = new node(index, value, 0);
prev->next = other;
}
else//插到中间，current所指结点大于等于它
{
if(current->index == index)//current所指结点等于它
{
current->value = value;
}
else//current所指结点结点大于它
{
node *other = new node(index, value, current);
prev->next = other;
}
}
*/
if(current == )//插到最后边
{
node *other = new node(index, value);
prev->next = other;
}
else if(current -> index == index)//current所指结点等于它的值
{
current->value =value;
}
else if(current == start)//在最开始的地方
{
node *other = new node(index, value, start);
start = other;
}
else //在中间
{
node *other = new node(index, value, current);
prev->next = other;
}
}
} void SparseVector::removeElem(int index)
{
node *current = start;
node *prev = ;
while(current != && current->index < index)//过滤
{
prev = current;
current = current->next;
}
if(current->index == index)//如果是这个结点
{
if(current == start)//是开始结点
{
prev = current;
current = current->next;
delete prev;
start = current;
return;
}
else//是中间结点或者是后边的节点（相同的）
{
prev->next = current->next;
delete current;
return;
}
}
else
{
return;
}
} void SparseVector::setElem(int index, int value)
{
if(value != )
{
setNonzeroElem(index, value);
}
else
{
removeElem(index);
}
} void SparseVector::checkListOrder()
{
node *current = start;
while(current != )
{
cout<<"("<<current->index<<" | "<<current->value<<")"<<endl;
current = current->next;
}
return;
}