1
2
template
void chain::setSize(int theSize)
{
if (listSize > theSize)
{
chainNode* deleteNode;
for (int i = theSize; i < listSize; ++i)
{
chainNode* p = firstNode;
for (int j = 0; j < theSize - 1; ++j)
p = p->next;
deleteNode = p->next;
p->next = p->next->next;
}
delete deleteNode;
//erase(theSize);
}
else
return;
listSize = theSize;
}
3
template
void chain::set(int theIndex, const T& theElement)
{
checkIndex(theIndex);
if (theIndex == 0)
firstNode->element = theElement;
else
{
chainNode* currentNode = firstNode;
for (int i = 0; i < theIndex; ++i)
currentNode = currentNode->next;
currentNode->element = theElement;
}
}
4
template
void chain::removeRange(int fromIndex, int toIndex)
{//reomve[fromIndex,toIndex)
if (fromIndex<0 || toIndex > listSize)
throw illegalIndex();
if (toIndex <= fromIndex)
return;
chainNode* p = firstNode;
chainNode* deleteNode;
int number = toIndex - fromIndex;
if (fromIndex == 0)
{
for (int i = 0; i < number; ++i)
{
deleteNode = firstNode;
firstNode = firstNode->next;
delete deteleNode;
}
}
else
{
for (int i = 0; i < fromIndex - 1; ++i)
p = p->next;
for (int i = 0; i < number; ++i)
{
deleteNode = p->next;
p->next = p->next->next;
delete deleteNode;
}
}
listSize -= number;
}
5
template
int chain::lastIndexOf(const T& theElement) const
{
chainNode* currentNode = firstNode;
int pos = -1,index = 0;
do
{
if (currentNode->element == theElement)
pos = index;
currentNode = currentNode->next;
++index;
} while (currentNode !=nullptr);
return pos;
}
6
template
T& chain::operator[](int theIndex)
{
return get(theIndex);
}
7
template
bool chain::operator==(const chain& rhs)
{
if (listSize != rhs.listSize)
return false;
chainNode* leftNode = firstNode;
chainNode* rightNode = rhs.firstNode;
for (int i = 0; i < listSize; ++i)
{
if (leftNode->element != rightNode->element)
return false;
leftNode = leftNode->next;
rightNode = rightNode->next;
}
return true;
}
8
template
bool chain::operator!=(const chain& rhs)
{
return !(*this == rhs);
}
9
template
bool chain::operator<(const chain& rhs)
{
bool state;
chainNode* leftNode = firstNode;
chainNode* rightNode = rhs.firstNode;
for (int i = 0; i < listSize && i < rhs.listSize; ++i)
{
if (leftNode->element > rightNode->element)
return false;
leftNode = leftNode->next;
rightNode = rightNode->next;
}
return true;
}
10
template
void chain::swap(chain& theList)
{
std::swap(listSize, theList.listSize);
std::swap(firstNode, theList.firstNode);
}
11
12
13
14
template
void chain::leftShift(int number)
{
chainNode* deleteNode;
for (int i = 0; i < number; ++i)
{
deleteNode = firstNode;
firstNode = firstNode->next;
delete deleteNode;
}
listSize -= number;
}
15
template
void chain::reverse()
{
if (listSize < 2)
return;
if (listSize == 2)
{
chainNode* tempNode = firstNode;
firstNode = firstNode->next;
firstNode->next = tempNode;
tempNode->next = nullptr;
return;
}
chainNode* prevNode = firstNode;//前驱
firstNode = firstNode->next;
prevNode->next = nullptr;
chainNode* nextNode = firstNode->next;
for (int i = 0; i != listSize - 3; ++i)
{
firstNode->next = prevNode;
prevNode = firstNode;
firstNode = nextNode;
nextNode = firstNode->next;
}
firstNode->next = prevNode;
nextNode->next = firstNode;
firstNode = nextNode;
}
16
template
friend void reverse(chain& theList);
template
void reverse(chain& theList)
{
for (int i = 0; i < theList.listSize / 2; ++i)
{
//1
//std::swap(theList.get(i), theList.get(theList.listSize - i - 1));
//2
T& lhsElement = theList.get(i);
T& rhsElement = theList.get(theList.listSize-i-1);
theList.set(i, rhsElement);
theList.set(theList.listSize - i - 1,lhsElement);
}
//3
//theList.reverse();
}
17
template
void extendedChain::meld(extendedChain& a, extendedChain& b)
{
clear();
a.checkIndex(a.size() - 1);
b.checkIndex(b.size() - 1);
int minIndex = std::min(a.size(), b.size());
int index = 0;
for (; index < minIndex; ++index)
{
push_back(a.get(index));
push_back(b.get(index));
}
if (a.size() > b.size())
{
for (int i = index; i < a.size(); ++i)
push_back(a.get(i));
}
else if (a.size() < b.size())
{
for (int i = index; i < b.size(); ++i)
push_back(b.get(i));
}
listSize = a.size() + b.size();
}
18
template
void chain::meld(chain& a, chain& b)
{
a.checkIndex(a.size() - 1);
b.checkIndex(b.size() - 1);
int minIndex = std::min(a.size(), b.size());
int index = 0;
chainNode* aNode;
chainNode* bNode;
chainNode* cNode;
chainNode* tempNode;
firstNode = a.firstNode;
aNode = a.firstNode->next;
firstNode->next = b.firstNode;
bNode = b.firstNode->next;
cNode = firstNode->next;
for (; index < minIndex - 1; ++index)
{
cNode->next = aNode;
tempNode = aNode->next;
aNode->next = bNode;
aNode = tempNode;
cNode = bNode;
bNode = bNode->next;
}
if (a.size() > b.size())
{
while (aNode != nullptr)
{
cNode->next = aNode;
aNode = aNode->next;
cNode = cNode->next;
}
}
else if (a.size() < b.size())
{
while (bNode != nullptr)
{
cNode->next = bNode;
bNode = bNode->next;
cNode = cNode->next;
}
}
a.firstNode = nullptr;
b.firstNode = nullptr;
listSize = a.size() + b.size();
}
19
template
void extendedChain::merge(extendedChain& a, extendedChain& b)
{
clear();
a.checkIndex(a.size() - 1);
b.checkIndex(b.size() - 1);
chainNode* aNode = a.firstNode;
chainNode* bNode = b.firstNode;
while (aNode != nullptr && bNode != nullptr)
{
if (aNode->element <= bNode->element)
{
push_back(aNode->element);
aNode = aNode->next;
}
else
{
push_back(bNode->element);
bNode = bNode->next;
}
}
if (aNode == nullptr)
{
while (bNode != nullptr)
{
push_back(bNode->element);
bNode = bNode->next;
}
}
if (bNode == nullptr)
{
while (aNode != nullptr)
{
push_back(aNode->element);
aNode = aNode->next;
}
}
listSize = a.size() + b.size();
}
20
template
void chain::merge(chain& a, chain& b)
{
a.checkIndex(a.size() - 1);
b.checkIndex(b.size() - 1);
chainNode* aNode = a.firstNode;
chainNode* bNode = b.firstNode;
chainNode* cNode = firstNode;
if (aNode->element <= bNode->element)
{
firstNode = cNode = aNode;
aNode = aNode->next;
}
else
{
firstNode = cNode = bNode;
bNode = bNode->next;
}
while (aNode != nullptr && bNode != nullptr)
{
if (aNode->element <= bNode->element)
{
cNode->next = aNode;
cNode = cNode->next;
aNode = aNode->next;
}
else
{
cNode->next = bNode;
cNode = cNode->next;
bNode = bNode->next;
}
}
if (aNode == nullptr)
{
while (bNode != nullptr)
{
cNode->next = bNode;
cNode = cNode->next;
bNode = bNode->next;
}
}
if (bNode == nullptr)
{
while (aNode != nullptr)
{
cNode->next = aNode;
cNode = cNode->next;
aNode = aNode->next;
}
}
a.firstNode = nullptr;
b.firstNode = nullptr;
listSize = a.size() + b.size();
}
21
template
void extendedChain::split(extendedChain& a, extendedChain& b)
{
a.clear();
b.clear();
while (firstNode != nullptr)
{
if (firstNode->element & 1)
{//奇数
a.push_back(firstNode->element);
firstNode = firstNode->next;
}
else
{//偶数
b.push_back(firstNode->element);
firstNode = firstNode->next;
}
}
}
22
template
void chain::split(chain& a, chain& b)
{
chainNode* aNode = nullptr;
chainNode* bNode = nullptr;
while (firstNode != nullptr)
{
if (firstNode->element & 1)
{
if (a.size() == 0)
{
aNode = a.firstNode = firstNode;
firstNode = firstNode->next;
++a.listSize;
continue;
}
aNode->next = firstNode;
firstNode = firstNode->next;
aNode = aNode->next;
aNode->next = nullptr;
++a.listSize;
}
else
{
if (b.size() == 0)
{
bNode = b.firstNode = firstNode;
firstNode = firstNode->next;
++b.listSize;
continue;
}
bNode->next = firstNode;
firstNode = firstNode->next;
bNode = bNode->next;
bNode->next = nullptr;
++b.listSize;
}
}
}
23
template
void extendedChain::circularShift(int number)
{
checkIndex(number);
lastNode->next = firstNode;
for (int i = 0; i < number ; ++i)
lastNode = lastNode->next;
firstNode = lastNode->next;
lastNode->next = nullptr;
}
24
25
26
template
void chain::insertSort()
{
if (!firstNode || !firstNode->next)
return;
chainNode* dummyNode = new chainNode(INT_MIN);
chainNode* prevNode, * currNode, * tempNode;
dummyNode->next = firstNode;
prevNode = firstNode;
currNode = firstNode->next;
while (currNode != nullptr)
{
if (currNode->element < prevNode->element)
{
tempNode = dummyNode;
while (tempNode->next->element < currNode->element)
{
tempNode = tempNode->next;
}
prevNode->next = currNode->next;
currNode->next = tempNode->next;;
tempNode->next = currNode;
currNode = prevNode->next;
}
else
{
prevNode = prevNode->next;
currNode = currNode->next;
}
}
firstNode = dummyNode->next;
}
27
template
void chain::bubbleSort()
{
if (!firstNode || !firstNode->next)
return;
chainNode* dummyNode, * prevNode, * currNode, * tailNode, * tempNode;
dummyNode = new chainNode(-1, firstNode);
prevNode = dummyNode->next;
currNode = prevNode->next;
tailNode = firstNode->next;
while (tailNode != nullptr)
tailNode = tailNode->next;
while (prevNode->next != tailNode)
{
tempNode = dummyNode;
while (currNode != tailNode)
{
if (currNode->element < prevNode->element)
{
prevNode->next = currNode->next;
currNode->next = prevNode;
tempNode->next = currNode;
tempNode = tempNode->next;
currNode = prevNode->next;
}
else
{
prevNode = prevNode->next;
currNode = currNode->next;
tempNode = tempNode->next;
}
}
tailNode = prevNode;
prevNode = dummyNode->next;
currNode = prevNode->next;
}
firstNode = dummyNode->next;
}
template
void chain::selectSort()
{
if (!firstNode || !firstNode->next)
return;
chainNode* maxNode, * maxPrevNode;
chainNode* currNode, * currPrevNode;
chainNode* dummyNode, * tailNode;
dummyNode = maxPrevNode = currPrevNode = new chainNode(INT_MIN, firstNode);
currNode = maxNode = firstNode;
tailNode = firstNode->next;
while (tailNode != nullptr)
tailNode = tailNode->next;;
while (maxNode->next != tailNode)
{
while (currNode->next != tailNode)
{
if (maxNode->element < currNode->element)
{
maxNode = currNode;
maxPrevNode = currPrevNode;
}
currNode = currNode->next;
currPrevNode = currPrevNode->next;
}
currPrevNode->next = maxNode;
maxPrevNode->next = currNode;
currNode->next = maxNode->next;
maxNode->next = tailNode;
//初始化尾节点和firstNode
tailNode = maxNode;
firstNode = dummyNode->next;
//初始化新一轮状态
maxNode = dummyNode->next;
currNode = maxNode->next;
maxPrevNode = dummyNode;
currPrevNode = maxPrevNode->next;
}
}
template
void chain::countSort()
{
if (!firstNode || !firstNode->next)
return;
chainNode* p, * pr;
chainNode* dummyNode = new chainNode(INT_MIN, firstNode);
p = firstNode->next;
int* r = new int[listSize];
for (int i = 0; i < listSize; ++i)
r[i] = 0;
int i = 1, j = 0;
while (p!=nullptr)
{
pr = dummyNode->next;
j = 0;
while (pr!=p)
{
if (pr->element <= p->element)
++r[i];
else
++r[j];
pr = pr->next;
++j;
}
p = p->next;
++i;
}
chainNode* pb = dummyNode->next;
int k = 0, t;
T temp;
while (pb!=nullptr)
{
int i = 0;
chainNode* pd = dummyNode->next;
while (k!=r[i])
{
pd = pd->next;
++i;
}
if (k != r[k])
{
temp = pb->element;
pb->element = pd->element;
pd->element = temp;
t = r[i];
r[i] = r[k];
r[k] = t;
}
pb = pb->next;
++k;
}
delete[] r;
}