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();
void addSubVector(const SparseVector &sv, bool add);
void removeZeros();
void checkZeros();
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);
bool operator==(const SparseVector &sv)const;
bool operator!=(const SparseVector &sv)const;
SparseVector& operator+=(const SparseVector &sv);
SparseVector& operator-=(const SparseVector &sv);
const SparseVector& operator+(const SparseVector &sv)const;
const SparseVector& operator-(const SparseVector &sv)const;
};
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;
} bool SparseVector::operator==(const SparseVector &sv)const
{
if(size != sv.size)//先判断是不是size不等，直接排除
{
return false;
}
else//每个结点依次判断index和value
{
node *current = start;
node *otherCurrent = sv.start;
while(current != && otherCurrent != )
{
if(current->index != otherCurrent->index || current->value != otherCurrent->value)
{
return false;
}
current = current->next;
otherCurrent = otherCurrent->next;
}
if(current == && otherCurrent == )//看看还有没有哪个剩余结点
{
return true;
}
else
{
return false;
}
}
} bool SparseVector::operator!=(const SparseVector &sv)const
{
return !(*this == sv);//调用等号，结果取反
} void SparseVector::addSubVector(const SparseVector &sv, bool add)
{
node *current = start;
node *otherCurrent = sv.start;
node *prev = ;
int sign = (add ? : -);//注意符号处理方式 if(current == )//两个链表合并时，一定不能忽略被合并链表为空的情况：（a+=b，其中a为空）
{
if(otherCurrent == )//（ab均为空）
{
return;
}
else
{
while(otherCurrent != )//（a为空b不为空）参考直接插入法形成一个新链表
{
node *addTo = new node(otherCurrent->index, sign * otherCurrent->value, );
if(prev == )
{
start = addTo;
prev = addTo;
current = addTo;
}
else
{
current->next = addTo;
current = addTo;
}
otherCurrent = otherCurrent->next;
}
return;
}
}
else//合并时均非空的情况
{
while(current != && otherCurrent != )//都顺序遍历，直到某一链表结束
{
if(current->index > otherCurrent->index)//插入的
{
if(prev == )//初始结点
{
node *addTo = new node (otherCurrent->index, sign * otherCurrent->value, current);
start = addTo;
prev = addTo;
otherCurrent = otherCurrent->next;
}
else//非初始结点
{
node *addTo = new node(otherCurrent->index, sign * otherCurrent->value, current);
prev->next = addTo;
prev = addTo;
otherCurrent = otherCurrent->next;
}
}
else if(current->index == otherCurrent->index)//直接加减的
{
current->value += sign * otherCurrent->value;
prev = current;
current = current->next;
otherCurrent = otherCurrent->next;
}
else if(current->index < otherCurrent->index)//不插入的
{
prev = current;
current = current->next;
}
}
if(otherCurrent == )//处理剩余的结点
{
return;
}
else//把剩余的插入到原来的
{
while(otherCurrent != )
{
node *addTo = new node(otherCurrent->index, sign * otherCurrent->value, current);
prev->next = addTo;
prev = addTo;
otherCurrent = otherCurrent->next;
}
}
return;
}
} void SparseVector::removeZeros()
{
node *current = start;
node *prev = ;
while(current != )//非0状态
{
if(current->value != )
{
prev = current;
current = current->next;
}
else//为0状态
{
if(prev == )//如果初始结点为0
{
prev = current;
current = current->next;
delete prev;
start = current;
prev = ;
}
else//非初始结点为0
{
node *temp = current;
current = current->next;
delete temp;
prev->next = current;
}
}
}
} SparseVector& SparseVector::operator+=(const SparseVector &sv)
{
addSubVector(sv, true);
removeZeros();
node * current = start;
size = ;
while(current != )//最后还要把size弄好
{
++size;
current = current->next;
}
return *this;
} SparseVector& SparseVector::operator-=(const SparseVector &sv)
{
addSubVector(sv, false);
removeZeros();
size = ;
node *current = start;
while(current != )//最后还要把size弄好
{
++size;
current = current->next;
}
return *this;
} const SparseVector& SparseVector::operator+(const SparseVector &sv)const
{
SparseVector *newSp = new SparseVector(*this);
*newSp += sv;
return *newSp;
} const SparseVector& SparseVector::operator-(const SparseVector &sv)const
{
SparseVector *newSp = new SparseVector(*this);
*newSp -= sv;
return *newSp;
} void SparseVector::checkZeros()
{
node *current = start;
while(current != )
{
if(current->value == )
{
cout<<"number "<<current->index<<" "<<current->value<<endl;
current = current->next;
}
}
}