数据结构、算法与应用 习题6.1 p124
本页的练习在无特殊说明时一律按照 单右向循环 链表为准。
1. L=(a,b,c,d,e) 作图 pass
2. setSize
复杂度O(n)
template <class T>
void chain<T>::theSize( int n ){
chainNode<T> current = firstNode();
int i=0, max = _size < n ? _size : n;
// 由于不是双向链表，所以需要先到达n的极点
while( i < max ){
current = current->next();
i++;
}
chainNode<T> tmp;
// 如果有多余的
while( _size > n ){
tmp = current->next();
delete current; // 系统会执行element析构
current = tmp;
}
_size = n;
}3. set()
复杂度O(n) 在实际使用的时候，链表一般不用index表示法来获取或设置元素。因为每次都相当于O(n)的复杂度。
template <class T>
void chain<T>::checkIndex( int theIndex ){
if( theIndex <0 || theIndex >= _size ){
throw illegalIndex("Out of range");
}
}
template <class T>
void chain<T>::set( int theIndex, T& theElement ){
checkIndex(theIndex);
chainNode<T>* current = firstNode();
int i = 0;
while( i < _size ){
current = current->next();
}
current->element.~T(); // 析构
current->element = theElement;
}4. removeRange
复杂度O(n) 和上面的setSize类似，做一次遍历，之后将切割掉的部分接起来即可。
template <class T>
void chain<T>::setSize( int fromIndex, int toIndex ){
checkIndex(fromIndex);
checkIndex(toIndex);
chainNode<T>* current = firstNode();
int i=0;
// fromIndex的极点
while( i < fromIndex ){
current = current->next();
i++;
}
chainNode<T>* tmp;
while( i < toIndex ){
tmp = current->next();
delete current; // 系统会执行element析构
current = tmp;
}
_size -= toIndex-fromIndex +1; // 考虑左右闭区间
}5. lastIndex()
复杂度O(n) 遍历元素并比对，不即时返回。
template <class T>
int chain<T>::lastIndex( T& theElement ) const{
if( empty() ) return -1;
chainNode<T>* current = firstNode();
int i = 0, lastIndex = -1;
while( i< _size ){
if( current->element == theElement ){
lastIndex = i;
}
current = current->next();
i++;
}
return lastIndex;
}
6. 重载[]
复杂度O(n) 实际上重载应该包含两种，分别是提供左值，右值返回。
template <class T>
const T& chain<T>::operator[](int n) const{ } // 右值
T& chain<T>::operator[]( int n) const{ // 左值
int i = 0;
chainNode<T>* current = firstNode();
while( i < n ){
current = current->next();
}
return current->element;
}7. 重载==
复杂度O(n) 同步遍历两个链表元素，一旦发现不同元素返回false。
template <class T>
bool chain<T>::operator==( chain<T>& c) const{
if( size() != c.size() ) return false;
chainNode<T>* current = firstNode();
chainNode<T>* target = c.firstNode();
int i = 0;
while( i < size() ){
if( current->element !== target->element ) return false;
current = current->next();
target = target->next();
}
return true;
}8. 重载!=
复杂度O(n)
template <class T>
bool chain<T>::operator!=( chain<T>& c) const{
return !*this == c;
}9. 重载<
复杂度O(n) 略微需要注意的是，除了最后一项的值完全相等以外，其他的相等 都不能判断非<。 所以在遍历的靠前阶段，== 都应该算成功，只有最后一项相等判断非小于。
template <class T>
bool chain<T>::operator<( chain<T>& c) const{
if( size() > c.size() ) return false;
chainNode<T>* current = firstNode();
chainNode<T>* target = c.firstNode();
int i = 0;
while( i < size() ){
if( current->element > target->element ){
return false;
}else{
current = current->next();
target = target->next();
}
}
if( current->element == target->element ) return false;
return true;
}
最近回复