开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《数据结构、算法与应用C++语言描述》线性表-链表描述 -> 正文阅读

[数据结构与算法]《数据结构、算法与应用C++语言描述》线性表-链表描述

_11 《数据结构、算法与应用C++语言描述》线性表-链表描述

11表示第11篇博文，6表示在数据结构算法与应用C++语言描述书中所在章节。

本文包含了《数据结构、算法与应用C++语言描述》第六章主要练习题答案，给出了线性表链表描述完整测试代码。

6.1 线性表数据结构

6.1.1 定义

线性表(linear list)也称有序表(ordered list)，它的每一个实例都是元素的一个有序集合。每一个实例的形式为( $e_0$ , $e_1$ ,…, $e_{n-1}$ )，其中n是有穷自然数， $e_i$ 是线性表的元素，i是元素 $e_i$ 的索引，n是线性表的长度或大小。元素可以被看做原子，它们本身的结构与线性表的结构无关。当n=0时，线性表为空；当n>0时， $e_0$ 是线性表的第0个元素或首元素， $e_{n-1}$ 是线性表的最后一个元素。可以认为 $e_{0}$ 先于 $e_{1}$ ， $e_{1}$ 先于 $e_{2}$ ，等等。除了这种先后关系之外，线性表不再有其他关系。

6.1.2 举例

1)一个班级的学生按姓名的字母顺序排列的列表；
2)按非递减次序排列的考试分数表；
3)按字母顺序排列的会议列表；
4)奥林匹克男子篮球比赛的金牌获得者按年代次序排列的列表。

6.1.3 线性表的抽象数据类型

抽象数据类型(abstract data type，ADT)，既能说明数据结构的实例，也说明对它的操作。抽象数据类型的说明独立于任何程序语言的描述。所有对抽象数据类型的语言描述必须满足抽象数据类型的说明，抽象数据类型的说明保证了程序语言描述的有效性。另外，所有满足抽象数据类型说明的语言描述，都可以在应用中替换使用。

抽象数据类型linearList
{
实例
	有限个元素的有序集合
操作
    empty()：若表空，则返回true，否则返回false 
    size()：返回线性表的大小(表的元素个数)
    get(index)：返回线性表中索引为index的元素
    indexOf(x)：返回线性表中第一次出现的x的索引。若x不存在，则返回-1
    erase(index)：删除索引为index的元素，索引大于index的元素其索引减1
    insert(index，x)：把x插人线性表中索引为index的位置上，索引大于等于index的元素其索引加1
    output()：从左到右输出表元素
}

6.1.4 抽象类linearList

抽象类

一个抽象类包含着没有实现代码的成员函数。这样的成员函数称为纯虚函数(pure virtual function)。纯虚函数用数字0作为初始值来说明，形式如下：

virtual int myPurevirtualFunction(int x)=0;

抽象数据类型不依赖程序语言，C++抽象类依赖程序语言。可以建立抽象类的对象指针。

抽象类的派生类，只有实现了基类的所有纯虚函数才是具体类，否则依然是抽象类而不能实例化。
具体类

具体类是没有纯虚函数的类。只有具体类才可以实例化。也就是说，我们只能对具体类建立实例或对象。

linearList抽象类定义

将抽象类的析构函数定义为虚函数，目的是，当一个线性表的实例离开作用域时需要调用的缺省析构函数时引用对象中数据类型的析构函数。

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			线性表虚类
*/
#pragma once
#ifndef __LINEARLIST_H_
#define __LINEARLIST_H_
#include<iostream>
using std::ostream;

template <class T>
class linearList
{
public:
	virtual ~linearList() {};
	virtual bool empty() const = 0;//返回true 当且仅当线性表为空
	virtual int size() const = 0;//返回线性表的元素个数
	virtual T& get(int theIndex) const = 0;//返回索引为theIndex的元素
	virtual int indexOf(const T& theElement) const = 0;//返回元素theElement第一次出现时的索引
	virtual void erase(int theIndex) = 0;//删除索引为theIndex的元素
	virtual void insert(int theIndex, const T& theElement) = 0;//把元素theElement插入线性表中索引为theIndex的位置上
	virtual void output(ostream& out) const = 0;//把线性表插入输入流out
};
#endif

6.2 链表描述

6.2.1 单链表

设L=( $e_0$ ， $e_1$ ，…， $e_{n-1}$ )是一个线性表。在对这个线性表的一个可能的链式描述中，每个元素都在一个单独的节点中描述，每一个节点都有一个链域，它的值是线性表的下一个元素的位置，即地址。这样一来，元素 $e_{i}$ 的节点链接着元素 $e_{i+1}$ 的节点，0<=i<n-1。元素 $e_{n-1}$ 的节点没有其他节点可链接，因此链域的值为NULL。

每一个节点只有一条链，这种结构称为单链表。

在这里插入图片描述

原则上，数组适合查询比较频繁的数据存储，链表适合插入和删除比较频繁的数据存储，但是由于高速缓存容量的问题，导致单链表的插入和删除操作的运行时间高于数组。

也就是说，对于单表而言，性能比不上数组；但是对于某些特殊应用而言，比如把一个链表的尾节点和另一个链表的首节点链接起来，合并为一个链表，对于链表合并的时间复杂度为O(1)，对于数组的时间复杂度比O(1)大。

在这里插入图片描述

6.2.2 循环链表

1)把线性表描述成一个单向循环链表(singly linked circular list)(简称循环链表)；只要将单向链表的尾节点与头节点链接起来，单向链表就成为循环链表。

2)在链表的前面增加一个节点，称为头节点(header node)。使用头节点的链表非常普遍，这样可以使程序更简洁、运行速度更快。

在这里插入图片描述

6.2.3 双向链表

双向链表(doubly linked list)的每个节点都有两个指针：next 和previous。next指针指向右边节点(如果存在)，previous指针指向左边节点(如果存在)。当双向链表只有一个元素节点p时，firstNode=lastNode=p。当双向链表为空时，firstNode=lastNode=NULL。

在这里插入图片描述

6.3 链表应用

6.3.1 箱子排序

用链表保存班级学生清单。节点的数据域有：学生姓名、社会保险号码、每次作业和考试的分数、所有作业和考试的加权总分。假设分数是0~ 100的整数，要求按总分排序。

箱子排序(bin sort)就是首先把分数相同的节点放在同一个箱子里，然后把箱子链接起来就得到有序的链表。

通用箱子排序步骤：

1)逐个删除输入链表的节点，把删除的节点分配到相应的箱子里；

2)把每一个箱子中的链表收集并链接起来，使其成为一个有序链表。

链表箱子排序步骤：

1)连续删除链表的首元素，并将其插入相应的某个箱子的链表首位；

2)从最后一个箱子开始，逐个删除每个箱子的元素，并将其插人一个初始为空的链表的首位。

在这里插入图片描述

稳定排序(stable sort)：排序方法能够保持同值元素之间的相对次序，箱子排序就是稳定排序。

6.3.2 基数排序

定义

基数排序可以仅在Θ(n)时间内，就可以对0~ $n^c-1$ 之间的n个整数进行排序，其中c>=0是一个整数常量。如果用原来的箱子排序方法对range= $n^{c}$ 来排序，则复杂度为 $Θ(n+range)=O(n^{c})$ 。扩展后的方法与binSort不同，它不直接对数进行排序，而是把数(number)按照某种基数(radix)分解为数字(digit)，然后对数字排序。基数可以根据需要选择。

举例

例6-1 假定对0~999之间的10个整数进行排序。如果使用range=1000的箱子排序方法，那么箱子链表的初始化需要1000个执行步，节点分配需要10个执行步，从箱子中收集节点需要1000个执行步，总的执行步数为2010。而基数排序方法是：
1)利用箱子排序方法，根据最低位数字(即个位数字)，对10个数进行排序。因为每个数字都在0~9之间，所以range=10。

2)利用箱子排序方法，对1)的结果按次低位数字(即十位数字)进行排序。同样有range=10。因为箱子排序是稳定排序，所以次低位数字相同的节点，按最低位数字排序所得到的次序保持不变。因此，现在的链表是按照最后两位数字进行排序的。

3)利用箱子排序方法，对2)的结果按第三位数字(即百位数字)进行排序。小于100的数，第三位数字为0。因为按第三位数字排序是稳定排序，所以第三位数字相同的节点，按最后两位数字排序所得到的次序保持不变。因此，现在的链表是按照后三位数字进行排序的。

在这里插入图片描述

数字分解式

对于一般的基数r，相应的分解式为：

在这里插入图片描述

当使用基数r=n对0~ $n^{c}-1$ 范围内的n个整数进行分解时，每个数可以分解出c个数字。因此，对n个数，可以用c次range=n个箱子排序。因为c是一个常量，所以整个排序时间为Θ(cn)=Θ(n)。

6.4 课后习题–单链表实现

2.编写方法chain::setSize(int theSize)，它使线性表的大小等于theSize。若初始线性表的大小小于theSize，则不增加元素。若初始线性表的大小大于theSize，则删除多余的元素。计算方法的复杂度。测试你的代码。
3.编写方法chain::set(theIndex，theElement)，它用元素theElement替换索引为thelndex的元素。若索引theIndex超出范围，则抛出异常。计算方法的复杂度。测试你的代码。
4.编写方法chain::removeRange(fromIndex，tolndex)，它删除指定索引范围内的所有元素。
计算方法的复杂度。测试你的代码。
5.编写方法chain::lastIndexOf(theElement)，返回值是指定元素最后出现时的索引。若这样的元素不存在，则返回-1。计算方法的复杂度。测试你的代码。
6.重载操作符[]，使得表达式x[i]返回对链表x的第i个元素的引用。若链表没有第i个元素，则抛出异常illegalIndex。语句x[i]=y和y=x[i]按以往预期的方式执行。测试你的代码。
7.重载操作符==，使得表达式x==y返回true，当且仅当两个链表x和y相等，即对所有的i，两个链表的第i个元素相等。测试你的代码。
8.重载操作符！=，使得表达式x！=y返回true，当且仅当两个链表x和y不等(见练习7)。测试你的代码。
9.重载操作符<，使得表达式x<y返回true，当且仅当链表x按字典顺序小于链表y(见练习7)。测试你的代码。
10.编写方法chain::swap(theChain)，它交换链表元素*this和theChain。计算方法的复杂度。测试你的代码。
11.编写一个方法，它把数组线性表转换为链表。这个方法既不是类arrayList的成员函数，也不是类chain的成员函数。使用类arrayList的方法get和类chain的方法insert。计算方法的复杂度。测试你的代码。
12.编写一个方法，它把链表转换为数组线性表。这个方法既不是类arrayList的成员函数，也不是类chain的成员函数。
1)使用类chain的get方法和listSize方法，类arrayList的insert方法。计算方法的复杂度。测试你的代码。
2)使用链表选代器。计算方法的复杂度。设计数据测试你的代码。
13.在类chain中增加转换方法。一个方法是fromList(theList)，它把数组线性表theList转换为链表。另一个方法是toList(theList)，它把链表*this转换为数组线性表theList。计算方法的复杂度。测试你的代码。
14.1)编写方法chain::leftShift(i)，它将表中的元素向左移动i个位置。如果l=[0，1，2，3，4]，那么l.leftShift(2)的结果是1=[2，3，4]。
2)计算方法的复杂度。
3)测试你的代码。
15.1)编写方法chain::reverse，它颠倒*this中的元素的顺序，而且原地完成，不用分配任何新的节点空间。
2)计算方法的复杂度。
3)使用自己的测试数据检验方法的正确性。
18.编写方法chain::meld。它生成一个新的扩展的链表c，它从a的首元素开始，交替地包含a和b的元素。如果一个链表的元素取完了，就把另一个链表的剩余元素附加到新的扩展链表c中。方法的复杂度应与链表a和b的长度具有线性关系。合并后的链表使用的应该是链表a和b的节点空间。合并之后，输入链表a和b是空表。
1)编写方法meld，其复杂度应该与输入链表的长度具有线性关系。
2)证明方法具有线性复杂度。
3)测试代码的正确性。使用自己的测试数据。
20.令a和b的类型为chain。假设a和b的元素类型都定义了操作符<、>、=、==和！=。而且假设a和b是有序链表(从左至右非逆减)。
1)编写一个非成员方法merge，它生成一个新的有序链表c，包含a和b的所有元素。归并之后，两个输入链表a和b为空。
2)计算方法的复杂度。
3)使用自己的测试数据检验方法的正确性。
22.令c的类型为扩展链表chain。
1)编写一个成员方法split(a，b)，它生成两个链表a和b。a包含*this中索引为奇数的元素，b包含*this中其余的元素。调用此方法后*this变为空链表
2)计算方法的复杂度。
3)使用自己的测试数据检验方法的正确性。
23.在一个循环移动的操作中，线性表的元素根据给定的值，按顺时针方向移动。例如L=[0，1，2，3，4]，循环移动2的结果是L=[2，3，4，0，1]。
1)编写方法chain::circularShift(i)，它将线性表的元素循环移动i个位置。
2)测试你的代码。

6.5 单链表完整测试代码

_1myExceptions.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include <string>
#include<iostream>

using namespace std;

// illegal parameter value
class illegalParameterValue 
{
   public:
      illegalParameterValue(string theMessage = "Illegal parameter value")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal input data
class illegalInputData 
{
   public:
      illegalInputData(string theMessage = "Illegal data input")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// illegal index
class illegalIndex 
{
   public:
      illegalIndex(string theMessage = "Illegal index")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds 
{
   public:
      matrixIndexOutOfBounds
            (string theMessage = "Matrix index out of bounds")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// matrix size mismatch
class matrixSizeMismatch 
{
   public:
      matrixSizeMismatch(string theMessage = 
                   "The size of the two matrics doesn't match")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// stack is empty
class stackEmpty
{
   public:
      stackEmpty(string theMessage = 
                   "Invalid operation on empty stack")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// queue is empty
class queueEmpty
{
   public:
      queueEmpty(string theMessage = 
                   "Invalid operation on empty queue")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// hash table is full
class hashTableFull
{
   public:
      hashTableFull(string theMessage = 
                   "The hash table is full")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// edge weight undefined
class undefinedEdgeWeight
{
   public:
      undefinedEdgeWeight(string theMessage = 
                   "No edge weights defined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};

// method undefined
class undefinedMethod
{
   public:
      undefinedMethod(string theMessage = 
                   "This method is undefined")
            {message = theMessage;}
      void outputMessage() {cout << message << endl;}
   private:
      string message;
};
#endif

_2myFunctions.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种非成员函数
*/
#pragma once
#ifndef _MYFUNCTIONS_H_
#define _MYFUNCTIONS_H_
#include<iostream>
#include "_1myExceptions.h"
#include<cmath>
#include <exception>
using std::min;
using std::endl;
using std::cout;
using std::bad_alloc;
/*交换两数据*/
template<class V>
void Swap(V& a, V& b)
{
	V temp = a;
	a = b;
	b = temp;
}
/*
作用：将数组的长度加倍
输入：指针a指向需要改变长度的数组，oldLength表示数组原来的长度，newLength表示需要改变的新长度
结果：将数组扩容/缩容 为newLength
*/
template<class T>
void changeLength(T*& a, int oldLength, int newLength)
{
	if (newLength < 0)
		throw illegalParameterValue("new length must be >= 0");
	T* temp = new T[newLength];
	int number = min(oldLength, newLength);
	copy(a, a + number, temp);
	delete[] a;
	a = temp;
}
/*遍历一维数组*/
template<class T>
void traverse1dArray(T* x, int length)
{
	for (int i = 0; i < length; i++)
		cout << x[i] << " ";
	cout << endl;
}
/*创建二维数组*/
template <class T>
bool make2dArray(T**& x, int numberOfRows, int numberOfColumns)
{
	try {
		//行指针
		x = new T * [numberOfRows];
		//为每一行分配内存
		for (int i = 0; i < numberOfRows; i++)
			x[i] = new int[numberOfColumns];
		return true;
	}
	catch (bad_alloc) { return false; }
}

/*遍历二维数组*/
template<class T>
void traverse2dArray(T**& x, int numberOfRows, int numberOfColumns)
{
	for (int i = 0; i < numberOfRows; i++)
	{
		for (int j = 0; j < numberOfColumns; j++)
		{
			cout.width(4);
			cout << x[i][j] << "  ";
		}
		cout << endl;
	}
}
/*myFunctions的测试函数*/
void myFunctionsTest();
/*汉诺塔的递归解决方案*/
void towersOfHanoiRecursion(int n, int x, int y, int z);
#endif

_4linearList.h–线性表抽象类

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			线性表虚类
*/
#pragma once
#ifndef __LINEARLIST_H_
#define __LINEARLIST_H_
#include<iostream>
using std::ostream;

template <class T>
class linearList
{
public:
	virtual ~linearList() {};
	virtual bool empty() const = 0;//返回true 当且仅当线性表为空
	virtual int size() const = 0;//返回线性表的元素个数
	virtual T& get(int theIndex) const = 0;//返回索引为theIndex的元素
	virtual int indexOf(const T& theElement) const = 0;//返回元素theElement第一次出现时的索引
	virtual void erase(int theIndex) = 0;//删除索引为theIndex的元素
	virtual void insert(int theIndex, const T& theElement) = 0;//把元素theElement插入线性表中索引为theIndex的位置上
	virtual void output(ostream& out) const = 0;//把线性表插入输入流out
};
#endif

_5arrayList.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			数组线性表头文件---单表
*/
#pragma once
#ifndef __ARRAYLIST_H_
#define __ARRAYLIST_H_
/*事实证明，模板与模板是可以不在同一个头文件下的。但是，模板函数声明和定义要在同一个头文件下。*/

#include <algorithm>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstddef>
#include <iterator>
#include "_1myExceptions.h"
#include "_2myFunctions.h"
#include "_4linearList.h"

using std::ostream;
using std::ostringstream;
using std::find;
using std::cout;
using std::copy;
using std::min;
using std::copy_backward;
using std::ostream_iterator;
using std::bidirectional_iterator_tag;
using std::ptrdiff_t;

//由于不能互相包含头文件，因此给出声明
template<class T>
class chain;
void arrayListTest();//arrayList测试函数，测试arrayList所有函数

template<class T>
class arrayList : public linearList<T>
{
public:
	/*构造函数*/
	arrayList(int initialCapacity = 1);
	/*复制构造函数*/
	arrayList(const arrayList<T>&);
	/*使用链表构造数组*/
	arrayList(const chain<T>& theChain);
	/*析构函数*/
	~arrayList() { delete[] element; }

	/*其他成员函数*/
	bool empty() const { return arraySize == 0; }
	int size() const { return arraySize; }
	T& get(int theIndex) const;
	int indexOf(const T& theElement) const;
	void erase(int theIndex);
	void insert(int theIndex, const T& theElement);
	void insert(int theIndex, const T& theElement,int size);
	void output(ostream& out) const;
	/*练习题5 时间复杂度为O(1)*/
	void trimToSize();
	
	int capacity() const { return arrayLength; }
	/*练习题11*/
	void push_back(const T& theElement);//将元素theElement插入数组的最右端
	/*练习题12*/
	T pop_back();//删除数组最右端元素，并返回该元素
	/*练习题13*/
	void swap(arrayList<T>& theList);
	/*练习题14*/
	void reserve(int theCapacity);
	/*练习题15*/
	void set(int theIndex, const T& theElement);
	/*练习题16*/
	void clear();
	/*练习题17*/
	void removeRange(int theIndex1, int theIndex2);
	/*练习题18*/
	int lastIndexOf(T theElement);
	/*练习题22*/
	void reverse();
	/*练习题23*/
	void leftShift(int num);
	/*练习题24*/
	void circularShift(int i);
	/*练习题25*/
	void half();
	/*练习题28*/
	void meld(arrayList<T>& a, arrayList<T>& b);
	/*练习题29*/
	void merge(arrayList<T>& a, arrayList<T>& b);
	/*练习题30*/
	void split(arrayList<T>& a, arrayList<T>& b);
	void reSet(int capacity);

	/*迭代器相关*/
	//问题：扩展迭代器，使之成为随机访问迭代器，这个暂时不太会。
	class iterator
	{
	public:
		//用C++的typedef语句实现双向迭代器
		//这一小段typedef暂时不太懂
		typedef bidirectional_iterator_tag iterator_category;//双向迭代器
		typedef T value_type;
		typedef ptrdiff_t difference_type;//是一个与机器相关的数据类型，通常用来保存两个指针减法操作的结果。
		typedef T* pointer;
		typedef T& reference;

		//构造函数
		iterator(T* thePosition = 0) { position = thePosition; }
		//解引用操作符
		T& operator*() const { return *position; }
		//指针操作符->
		T* operator->() const { return &*position; }
		//迭代器的值增加
		iterator& operator++()//前加
		{
			++position;
			return *this;
		}
		iterator operator++(int)//后加
		{
			iterator old = *this;
			++position;
			return old;
		}
		//迭代器的值减少
		iterator& operator--()//前减
		{
			--position;
			return *this;
		}
		iterator operator--(int)//后减
		{
			iterator old = *this;
			--position;
			return old;
		}
		//测试是否相等
		bool operator!=(const iterator right) const
		{
			return position != right.position;
		}
		bool operator==(const iterator right) const
		{
			return position == right.position;
		}
	protected:
		T* position;
	};
	iterator begin() { return iterator(element); }
	iterator end() { return iterator(element + arraySize); }//返回的是最后一个元素后面的一个位置

	/*重载操作符*/
	/*练习题7*/
	T& operator[](int i);
	const T& operator[](int i) const;
	/*练习题8*/
	bool operator==(arrayList<T> right) const;
	/*练习题9*/
	bool operator!=(arrayList<T> right) const;
	/*练习题10*/
	bool operator<(arrayList<T> right) const;

	/*排序*/
	void bubbleSort();
	void rankSort();
	int indexOfMax();
	void selectionSort();
	void insertSort();

	/*友元函数*/
	//这个函数用于一次性输入很多元素到线性表
	friend istream& operator>> <T>(istream& in, arrayList<T>& m);//已测

protected:
	void checkIndex(int theIndex) const;//若索引theIndex无效，则抛出异常
	/*setLength()函数没有重新分配内存*/
	/*setLength(),setSize(),setElement()函数只应用于swap()函数*/
	void setLength(int Length) { arrayLength = Length; }
	void setSize(int Size) { arraySize = Size; }
	void setElement(T* theElement) { element = theElement; }
	T* address() const { return element; }
	T* element;//存储线性表元素的一维数组
	int arrayLength;//一维数组的容量
	int arraySize;//线性表的元素个数
};

/*构造函数*/
template<class T>
arrayList<T>::arrayList(int initialCapacity)
{
	//检查初始数组大小是否符合要求
	if ( initialCapacity < 1 )
	{
		ostringstream s("");
		s << "Initial capacity = " << initialCapacity << "Must be > 0";
		throw illegalParameterValue(s.str());
	}
	//初始化数组私有元素
	arrayLength = initialCapacity;
	element = new T[arrayLength];
	arraySize = 0;
}

/*复制构造函数*/
template<class T>
arrayList<T>::arrayList(const arrayList<T>& theList)
{
	arrayLength = theList.arrayLength;
	arraySize = theList.arraySize;
	//为新数组分配内存
	element = new T[arrayLength];
	//将旧数组中的元素复制到新数组
	copy(theList.element, theList.element + arraySize, element);
}

/*使用chain初始化数组,使用了迭代器*/
template<class T>
arrayList<T>::arrayList(const chain<T>& theChain)
{
	arraySize = theChain.size();
	arrayLength = arraySize;
	element = new T[arraySize];//使得数组的长度和容量相等
	//首先定义一个链表迭代器指向链表首地址
	/*这里为什么要是有typename?原因是不使用typename将会引发错误：
	  错误	C7510	“iterator”: 类型 从属名称的使用必须以“typename”为前缀。
	  只有加上typename才可解决这个问题，具体原因暂时不清楚。

	  原因：typename是class的同义词；这里使用typename或class都可通过编译。
	  目的在于告诉编译器chain<T>::iterator是一个类型而非变量，本程序中为了解决
	  头文件互相引用的问题，只声明了chain是一个类，编译器在此处并不知道chain的
	  成员iterator是类型还是变量，因此为解决二义性问题必须使用typename或class声
	  明iterator是类型。
	*/
	typename chain<T>::iterator pointer = theChain.begin();
	int i = 0;
	while (pointer != nullptr)
	{
		*(element + i) = *pointer;
		pointer++;
		i++;
	}
}

/*检查索引是否有效*/
template<class T>
void arrayList<T>::checkIndex(int theIndex) const
{
	if (theIndex < 0 || theIndex >= arraySize)
	{
		ostringstream s("");
		s << "index = " << theIndex << "size = "<<arraySize;
		throw illegalIndex(s.str());
	}
}

/*返回索引为theIndex的元素；若此元素不存在，则抛出异常*/
template<class T>
T& arrayList<T>::get(int theIndex) const
{
	checkIndex(theIndex);
	return element[theIndex];
}

/*返回元素theElement第一次出现时的索引；若该元素不存在，则返回-1*/
template<class T>
int arrayList<T>::indexOf(const T& theElement) const//const表示此函数不更改形参的内容
{
	int theIndex = (int)(find(element, element + arraySize, theElement) - element);
	if (theIndex == arraySize)
		return -1;
	else
		return theIndex;
}

/*如果数组元素数量为0，则将其容量设置为1*/
template<class T>
void arrayList<T>::trimToSize()
{
	if (arraySize == 0)
	{
		//数组中无元素时，将数组容量设置为1
		changeLength(element, arrayLength, 1);
		arrayLength = 1;
	}
}

/*删除索引为theIndex的元素；如果该元素不存在，则抛出illegalIndex异常*/
template<class T>
void arrayList<T>::erase(int theIndex)
{
	checkIndex(theIndex);
	copy(element + theIndex + 1, element + arraySize, element + theIndex);
	element[--arraySize].~T();//调用析构函数，更安全
	trimToSize();
	//如果数组所存数据太少，使得arraySize<= arrayLength / 4，以下语句将缩小数组大小
	while (arraySize < arrayLength / 4)
	{
		changeLength(element, arrayLength, arrayLength / 2);
		arrayLength /= 2;
	}
}

/*在索引theIndex的位置上插入一个元素theElement*/
template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement)
{
	/*判断是否为有效索引*/
	if(theIndex != 0 && theIndex != arraySize)
		checkIndex(theIndex);
	//有效索引，确定是否数组已满
	if (arraySize == arrayLength)
	{
		//数组空间已满，数组长度倍增
		changeLength(element, arrayLength, 2 * arrayLength);
		arrayLength *= 2;
	}
	copy_backward(element + theIndex, element + arraySize, element + arraySize + 1);
	element[theIndex] = theElement;
	arraySize += 1;
}

/*在索引theIndex的位置上插入一个元素theElement,如果指定size，当数组空间满时将数组的容量设定为size*/
template<class T>
void arrayList<T>::insert(int theIndex, const T& theElement,int size)
{
	/*判断是否为有效索引*/
	if(theIndex != 0 && theIndex != arraySize)
		checkIndex(theIndex);
	//有效索引，确定是否数组已满
	if (arraySize == arrayLength)
	{
		//数组空间已满，数组长度设置为size
		changeLength(element, arrayLength, size);
		arrayLength = size;
	}
	copy_backward(element + theIndex, element + arraySize, element + arraySize + 1);
	element[theIndex] = theElement;
	arraySize += 1;
}

/*数组元素输出*/
template<class T>
void arrayList<T>::output(ostream& out) const
{
	copy(element, element + arraySize, ostream_iterator<T>(cout, " "));
}

/*在数组最右端插入元素theElement*/
template<class T>
void arrayList<T>::push_back(const T& theElement)
{
	//有效索引，确定数组已满
	if (arraySize == arrayLength)
	{
		//数组空间已满，数组长度设置为size
		changeLength(element, arrayLength, arrayLength*2);
		arrayLength = arrayLength * 2;
	}
	*(element + arraySize) = theElement;
	arraySize++;
}

/*删除数组最右端元素并返回该元素*/
template<class T>
T arrayList<T>::pop_back()
{
	checkIndex(arraySize-1);
	T temp = element[arraySize - 1];
	arraySize--;
	trimToSize();//如果数组中无元素，则将数组的容量置为1
	//如果数组所存数据太少，使得arraySize<= arrayLength / 4，以下语句将缩小数组大小
	while (arraySize < arrayLength / 4)
	{
		changeLength(element, arrayLength, arrayLength / 2);
		arrayLength /= 2;
	}
	return temp;
}

/*交换两数组的元素,传递的参数必须是引用*/
template<class T>
void arrayList<T>::swap(arrayList<T>& theList)
{
	T* temp = element;
	int thisLength = arrayLength;
	int thisSize = arraySize;

	element = theList.address();
	arraySize = theList.size();   
	arrayLength = theList.capacity();

	theList.setSize(thisSize);
	theList.setLength(thisLength);
	theList.setElement(temp);
}

/*将数组的容量改编为当前容量和theCapacity的较大者*/
template<class T>
void arrayList<T>::reserve(int theCapacity)
{
	if (arrayLength < theCapacity)
	{
		T* temp = new T[theCapacity];
		for (int i = 0; i < arraySize; i++)
		{
			temp[i] = element[i];
		}
		delete[] element;
		element = temp;
		arrayLength = theCapacity;
	}
}
/*用元素theElement替换索引为theIndex的元素*/
template<class T>
void arrayList<T>::set(int theIndex, const T& theElement)
{
	checkIndex(theIndex);
	element[theIndex] = theElement;
}
/*清空数组*/
template<class T>
void arrayList<T>::clear()
{
	arraySize = 0;
	trimToSize();
}

/*删除[theIndex1,theIndex2]指定索引范围内的元素*/
template<class T>
void arrayList<T>::removeRange(int theIndex1, int theIndex2)
{
	//首先检查索引是否有效
	checkIndex(theIndex1);
	checkIndex(theIndex2);
	for (int i = theIndex1; i < arraySize - (theIndex2 - theIndex1); i++)
	{
		element[i] = element[i + theIndex2 - theIndex1 + 1];
	}
	arraySize -= theIndex2 - theIndex1 + 1;
}

/*返回值为指定元素最后出现时的索引；如果元素不存在，则返回-1。*/
template<class T>
int arrayList<T>::lastIndexOf(T theElement)
{
	for (int i = arraySize - 1; i >= 0; i--)
	{
		if (element[i] == theElement)
			return i;
	}
	return -1;
}

/*原地颠倒线性表元素的顺序*/
template<class T>
void arrayList<T>::reverse()
{
	for (int i = 0; i < arraySize / 2; i++)
		Swap<T>(element[i], element[arraySize - i - 1]);
}

/*将线性表的元素向左移动i个位置*/
template<class T>
void arrayList<T>::leftShift(int num)
{
	//首先检查索引是否有效
	checkIndex(num-1);
	for (int i = 0; i < arraySize - num + 1; i++)
	{
		element[i] = element[i + num];
	}
	arraySize -= num;
}

/*将线性表的元素循环左移i位*/
template<class T>
void arrayList<T>::circularShift(int num)
{
	for(int i = 0; i < num; i++)
		push_back(element[i]);
	leftShift(num);
}

/*将线性表的元素隔一个删除一个*/
template<class T>
void arrayList<T>::half()
{
	for (int i = 1; i <= (arraySize+1) / 2; i++)
		element[i] = element[2 * i];
	arraySize = (arraySize+1) / 2;
}

/*
创建一个新的线性表，该表包含了a和b中的所有元素，其中a和b的元素轮流出现，表中的首
元素为a中的第一个元素。在轮流排列元素时，如果某个表的元素用完了，则把另一个表的其
余元素依次添加在新表的后部。代码的复杂性应与两个输入表的长度呈线性比例关系。
归并后的线性表是调用对象*this
*/
template <class T>
void arrayList<T>::meld(arrayList<T>& a, arrayList<T>& b)
{
	(*this).clear();
	int i = 0;
	while (i < a.size() && i < b.size())
	{
		push_back(a[i]);
		push_back(b[i]);
		i++;
	}
	while (i < a.size())
	{
		push_back(a[i]);
		i++;
	}
	while (i < b.size())
	{
		push_back(b[i]);
		i++;
	}
}

/*有序列表a,b，合并生成一个新的有序列表，新列表为(*this)*/
template<class T>
void arrayList<T>::merge(arrayList<T>& a, arrayList<T>& b)
{
	(*this).clear();
	int i = 0;
	int j = 0;
	while ((i < a.size()) && (j < b.size()))
	{
		if (a[i] < b[j])
		{
			push_back(a[i]);
			i++;
		}
		else if (a[i] == b[j])
		{
			push_back(a[i]);
			push_back(b[j]);
			i++;
			j++;
		}
		else
		{
			push_back(b[j]);
			j++;
		}			
	}
	while (i < a.size())
	{
		push_back(a[i]);
		i++;
	}
	while (j < b.size())
	{
		push_back(b[j]);
		j++;
	}
}

/*生成两个线性表a和b，a包含*this中索引为奇数的元素，b包含其余的元素*/
template<class T>
void arrayList<T>::split(arrayList<T>& a, arrayList<T>& b)
{
	a.clear();
	b.clear();
	for (int i = 0; i < arraySize; i++)
	{
		if (i % 2 == 0)
			a.push_back(element[i]);
		else
			b.push_back(element[i]);
	}
}
/*将数组的容量设置为capacity,并将数组的大小设置为capacity,只用于sparseMatrix类*/
template<class T>
void arrayList<T>::reSet(int capacity)
{
	if (capacity < 0)
		throw illegalParameterValue("capacity must be >= 0");
	T* temp = new T[capacity];
	delete[] element;
	element = temp;
	arraySize = capacity;
}

/*友元函数 重载>>操作符*/
template<class T>
istream& operator>>(istream& in, arrayList<T>& m)
{
	int numberOfElement = 0;
	cout << "Please enter the number of elements:" << endl;
	while (!(in >> numberOfElement)) {//如果输入类型不匹配，则执行循环体
		in.clear(); // reset input设置标志位为有效
		while (in.get() != '\n') //删除没有用的输入
			continue; // get rid of bad input
		cout << "Please enter the number of elements:" << endl;
	}
	T inElement = 0;
	for (int i = 0; i < numberOfElement; i++)
	{
		cout << "Please enter the element: " << (i + 1) << endl;
		while (!(in >> inElement)) {//如果输入类型不匹配，则执行循环体
			in.clear(); // reset input设置标志位为有效
			while (in.get() != '\n') //删除没有用的输入
				continue;
			cout << "Please enter the element: " << (i + 1) << endl;
		}
		m.push_back(inElement);
	}
	return in;
}

/*重载<<操作符*/
template<class T>
ostream& operator<<(ostream& out, const arrayList<T>& x)
{
	x.output(out);
	return out;
}

/*重载[]操作符*/
template<class T>
T& arrayList<T>::operator[](int i)
{
	return element[i];
}
template<class T>
const T& arrayList<T>::operator[](int i) const
{
	return element[i];
}

/*重载==操作符*/
template<class T>
bool arrayList<T>::operator==(arrayList<T> right) const
{
	if (arraySize == right.size())
	{
		for (int i = 0; i < arraySize; i++)
		{
			if ((*this)[i] != right[i])
				return false;//遇到不相等直接返回false
		}
		return true;//都相等时返回true
	}
	else
		return false;
}

/*重载!=操作符*/
template<class T>
bool arrayList<T>::operator!=(arrayList<T> right) const
{
	if (arraySize == right.size())
	{
		for (int i = 0; i < arraySize; i++)
		{
			if ((*this)[i] != right[i])
				return true;//遇到不相等直接返回true
		}
		return false;//都相等时返回false
	}
	else
		return true;//元素数量不相等返回true
}

/*重载<操作符*/
//当left的长度小于右边时，比较left和right的元素;如所有left元素按字典顺序小于对应的right元素，则返回true，反之返回false
//当left的长度大于右边时，返回false
template<class T>
bool arrayList<T>::operator<(arrayList<T> right) const
{
	if (arraySize <= right.size())
	{
		for (int i = 0; i < arraySize; i++)
		{
			if ((*this)[i] >= right[i])
				return false;//遇到大于直接返回false
		}
		return true;//都小于时返回false
	}
	else
		return false;//元素数量不相等返回true
}

/*排序*/
/*功能：及时终止的冒泡排序,时间复杂度为n(n-1)/2*/
template<class T>
void arrayList<T>::bubbleSort()
{
	bool is_sorted = true;
	for (int i = arraySize; is_sorted && i > 1; i--)
	{
		is_sorted = false;//先设置为未交换，如果交换了就会被设置为交换。
		for (int j = 0; j < i - 1; j++)
		{
			if (element[j] > element[j + 1])
			{
				Swap<T>(element[j], element[j + 1]);
				is_sorted = true;
			}
		}
	}
}

/*按名次排序*/
template<class T>
void arrayList<T>::rankSort()
{
	int* r = new int[arraySize];
	//初始化名次
	for (int i = 0; i < arraySize; i++)
		r[i] = 0;
	//计算名次
	for (int i = arraySize - 1; i >= 0; i--) //从右往左拿出每个元素与其他元素比较
	{
		for (int j = 0; j < i ; j++)
		{
			if (*(element + i) > *(element + j))
				r[i]++;
			else
				r[j]++;
		}
	}
	//按名次排序
	for (int i = 0; i < arraySize; i++)
	{
		if (i != r[i])
		{
			Swap<T>(element[i], element[r[i]]);
			Swap<T>(r[i], r[r[i]]);
		}
	}
	delete[] r;
}

/*返回整个数组中最大元素的索引*/
template<class T>
int arrayList<T>::indexOfMax()
{
	int indexMax = 0;
	for (int i = 1; i < arraySize; i++)
	{
		if (element[i] > element[indexMax])
		{
			indexMax = i;
		}
	}
	return indexMax;
}
/*选择排序*/
template<class T>
void arrayList<T>::selectionSort()
{
	bool is_sorted = false;
	for (int i = arraySize; i > 1 && !is_sorted; i--)
	{
		is_sorted = true;
		int indexMax = 0;
		for (int j = 1; j < i; j++)
		{
			if (element[j] > element[indexMax])
				indexMax = j;
			else
				is_sorted = false;
		}
		Swap<T>(element[i - 1], element[indexMax]);
	}
}
/*原地插入排序*/
template<class T>
void arrayList<T>::insertSort()
{
	int temp = 0;
	for (int i = 1; i < arraySize; i++)
	{
		temp = element[i];//存住要插入的元素
		//如果它前面的元素都大于该元素的话，就将它前面的元素后移一位
		int j = 0;
		for (j = i - 1; temp < element[j]; j--)
		{
			element[j + 1] = element[j];
		}
		element[j + 1] = temp;
	}
}

#endif

_6chainNode.h–链表节点

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日22点06分
Last Version:			V1.0
Descriptions:			链表的结点
*/
#pragma once
#ifndef _CHAINNODE_H_
#define _CHAINNODE_H_
template <class T>
struct chainNode
{
	//数据成员
	T element;
	chainNode<T>* next;
	//方法
	chainNode() {}
	chainNode(const T& element)
	{
		this->element = element;
		this->next = nullptr;
	}

	chainNode(const T& element, chainNode<T>* next)
	{
		this->element = element;
		this->next = next;
	}
};
#endif

_6chain.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			链表线性表头文件---单链表
*/
#pragma once
#ifndef _CHAIN_H_
#define _CHAIN_H_
#include<iostream>
#include<sstream>
#include<cmath>
#include "_1myExceptions.h"
#include "_2myFunctions.h"
#include "_4linearList.h"
#include "_5arrayList.h"
#include "_6chainNode.h"

using std::ostream;
using std::ostringstream;
using std::find;
using std::cout;
using std::forward_iterator_tag;
using std::ptrdiff_t;
using std::endl;

void chainTest();//测试函数，函数定义在chain.cpp中。

template<class T>
class chain : public linearList<T>
{
public:

	/*构造函数*/
	chain(int initialCapacity = 10);
	/*复制构造函数*/
	chain(const chain<T>&);
	/*数组构造链表*/
	chain(const arrayList<T>& arrayTo);//直接使用构造函数--使用数组初始化链表
	/*析构函数*/
	~chain();

	//抽象数据类型ADT方法
	bool empty() const { return listSize == 0; }
	int size() const { return listSize; }
	T& get(int theIndex) const;
	int indexOf(const T& theElement) const;
	void erase(int theIndex);
	void insert(int theIndex, const T& theElement);
	void output(ostream& out) const;
	void clear();
	void push_back(const T& theElement);
	/*习题2*/
	void setSize(int theSize);
	/*习题3*/
	void set(int theIndex, const T& theElement);
	/*习题4*/
	void removeRange(int fromIndex, int toIndex);
	/*习题5*/
	int lastIndexOf(const T& theElement);
	/*习题10*/
	void swap(chain<T>& theChain);
	/*习题13*/
	void toArray(arrayList<T>& theArray);
	/*习题14*/
	void leftShift(int i);
	/*习题15*/
	void reverse();
	/*习题18*/
	void meld(chain<T>& a, chain<T>& b);
	/*习题20*/
	void merge(chain<T>& a, chain<T>& b);
	/*习题22*/
	void split(chain<T>& a, chain<T>& b);
	/*习题23*/
	void circularShift(int i);

	/*迭代器*/
	class iterator
	{
	public:
		//向前迭代器所需要的typedef
		typedef forward_iterator_tag iterator_category;
		typedef T value_type;
		typedef ptrdiff_t difference_type;
		typedef T* pointer;
		typedef T& reference;
		/*构造函数*/
		iterator(chainNode<T>* theNode = nullptr) { node = theNode; }
		/*解引用操作*/
		T& operator*() const { return node->element; }
		T* operator->() const { return &node->element; }
		/*迭代器加法操作*/
		iterator& operator++() //前加
		{
			node = node->next; return *this;
		}
		iterator& operator++(int) //后加
		{
			iterator old = *this;
			node = node->next;
			return old;
		}
		/*相等检验*/
		bool operator!=(const iterator right) const { return node != right.node; }
		bool operator==(const iterator right) const { return node == right.node; }
	protected:
		chainNode<T>* node;
	};
	iterator begin() const { return iterator(firstNode); }
	iterator end() const { return iterator(nullptr); }

	/*重载操作符*/
	/*习题6*/
	T& operator[](int i);
	const T& operator[](int i) const;
	/*习题7*/
	bool operator==(chain<T>& right) const;
	/*习题8*/
	bool operator!=(chain<T>& right) const;
	/*习题9*/
	bool operator<(chain<T>& right) const;

	/*排序*/
	void bubbleSort();
	void rankSort();
	T maxOfList();
	void selectionSort();
	void insertSort();
	/*箱子排序*/
	void binSort(int range);
	/*基数排序*/
	void baseBinSort(int range);
	
	/*友元函数*/
	friend istream& operator>> <T>(istream& in, chain<T>& m);//已测
protected:
	void checkIndex(int theIndex) const;
	//如果索引无效，抛出异常
	chainNode<T>* firstNode;//指向链表第一个节点的指针
	int listSize;//线性表的元素个数
};

/*友元函数 重载>>操作符*/
template<class T>
istream& operator>>(istream& in, chain<T>& m)
{
	int numberOfElement = 0;
	cout << "Please enter the number of elements:" << endl;
	while (!(in >> numberOfElement)) {//如果输入类型不匹配，则执行循环体
		in.clear(); // reset input设置标志位为有效
		while (in.get() != '\n') //删除没有用的输入
			continue; // get rid of bad input
		cout << "Please enter the number of elements:" << endl;
	}
	T inElement = 0;
	for (int i = 0; i < numberOfElement; i++)
	{
		cout << "Please enter the element: " << (i + 1) << endl;
		while (!(in >> inElement)) {//如果输入类型不匹配，则执行循环体
			in.clear(); // reset input设置标志位为有效
			while (in.get() != '\n') //删除没有用的输入
				continue;
			cout << "Please enter the element: " << (i + 1) << endl;
		}
		m.push_back(inElement);
	}
	return in;
}

/*构造函数：实质上initialCapacity没有意义的，但是为了与类arrayList相容*/
template<class T>
chain<T>::chain(int initialCapacity)
{
	//构造函数
	if (initialCapacity < 1)
	{
		ostringstream s("");
		s << "Initial capacity = " << initialCapacity << "Must be > 0";
		throw illegalParameterValue(s.str());
	}
	firstNode = nullptr;
	listSize = 0;
}

/*复制构造函数*/
template<class T>
chain<T>::chain(const chain<T>& theList)
{
	listSize = theList.listSize;
	if (listSize == 0)
	{
		firstNode = nullptr;
		return;
	}
	//指向要复制的元素位置
	chainNode<T>* sourceNode = theList.firstNode;
	firstNode = new chainNode<T>(sourceNode->element);//复制链表theList的首元素
	sourceNode = sourceNode->next;
	//指向要复制的元素位置之前的位置
	chainNode<T>* targetNode = firstNode;
	while (sourceNode != nullptr)
	{
		targetNode->next = new chainNode<T>(sourceNode->element);
		targetNode = targetNode->next;
		sourceNode = sourceNode->next;
	}
}

/*使用arrayList初始化链表的构造函数*/
template<class T>
chain<T>::chain(const arrayList<T>& arrayTo)
{
	listSize = arrayTo.size();
	if (listSize == 0)
	{
		firstNode = nullptr;
	}
	else
	{
		int data = arrayTo.get(0);
		firstNode = new chainNode<T>(data);
		chainNode<T>* currentNode = firstNode;
		for (int i = 1; i < listSize; i++)
		{
			data = arrayTo.get(i);
			currentNode->next = new chainNode<T>(data);
			currentNode = currentNode->next;
		}
	}	
}

/*析构函数*/
template<class T>
chain<T>::~chain()
{
	while (firstNode != nullptr)
	{
		chainNode<T>* nextNode = firstNode->next;
		delete firstNode;
		firstNode = nextNode;
	}
}

/*检查索引是否有效*/
template<class T>
void chain<T>::checkIndex(int theIndex) const
{
	if (theIndex < 0 || theIndex >= listSize)
	{
		ostringstream s("");
		s << "index = " << theIndex << "size = " << listSize;
		throw illegalIndex(s.str());
	}
}

/*获取索引为theIndex的元素*/
template<class T>
T& chain<T>::get(int theIndex) const
{
	checkIndex(theIndex);
	chainNode<T>* currentNode = firstNode;
	for (int i = 0; i < theIndex; i++)
		currentNode = currentNode->next;
	return currentNode->element;
}

/*返回元素theElement首次出现时的索引，若该元素不存在，则返回-1。*/
template<class T>
int chain<T>::indexOf(const T& theElement) const
{
	//搜索链表寻找元素theElement
	chainNode<T>* currentNode = firstNode;
	int index = 0;
	while (currentNode != NULL && currentNode->element != theElement)
	{
		index++;
		currentNode = currentNode->next;
	}
	if (index == listSize)
		return -1;
	else
		return index;
}

/*删除索引为theIndex的元素；若该元素不存在，则抛出异常*/
template<class T>
void chain<T>::erase(int theIndex)
{
	checkIndex(theIndex);
	chainNode<T>* deleteNode = nullptr;
	if (theIndex == 0)
	{
		deleteNode = firstNode;
		firstNode = firstNode->next;
	}
	else
	{
		chainNode<T>* currentNode = firstNode;
		for (int i = 0; i < theIndex - 1; i++)
		{
			currentNode = currentNode->next;
		}
		deleteNode = currentNode->next;
		currentNode->next = currentNode->next->next;
	}
	delete deleteNode;
	listSize--;
}

/*插入元素theElement并使其索引为theIndex*/
template<class T>
void chain<T>::insert(int theIndex, const T& theElement)
{
	//无效索引
	if (theIndex < 0 || theIndex > listSize)
	{
		ostringstream s("");
		s << "index = " << theIndex << "size = " << listSize;
		throw illegalIndex(s.str());
	}
	//在链表头插入
	if (theIndex == 0)
		firstNode = new chainNode<T>(theElement, firstNode);
	else
	{
		//寻找新元素的前驱
		chainNode<T>* p = firstNode;
		for (int i = 0; i < theIndex - 1; i++)
			p = p->next;
		//在p之后插入
		p->next = new chainNode<T>(theElement, p->next);
	}
	listSize++;
}

/*方法output*/
template<class T>
void chain<T>::output(ostream& out) const
{
	for (chainNode<T>* currentNode = firstNode; 
			currentNode != nullptr; 
			currentNode = currentNode->next)
		out << currentNode->element << " ";
}

/*重载<<操作符*/
template<class T>
ostream& operator<<(ostream& out, const chain<T>& x)
{
	x.output(out);
	return out;
}

/*清空链表*/
template<class T>
void chain<T>::clear()
{
	chainNode<T>* nextNode = nullptr;
	while (firstNode != nullptr)
	{
		nextNode = firstNode->next;
		delete firstNode;
		firstNode = nextNode;
	}
	listSize = 0;
}

/*在链表末尾插入元素theElement的节点*/
template<class T>
void chain<T>::push_back(const T& theElement)
{
	chainNode<T>* newNode = new chainNode<T>(theElement, nullptr);
	if (firstNode == nullptr)
		firstNode = newNode;
	else
	{
		chainNode<T>* currentNode = firstNode;
		while (currentNode->next != nullptr)
			currentNode = currentNode->next;
		currentNode->next = newNode;
	}
	listSize++;
}

/*
* 习题2
* 使得线性表的大小等于theSize;若初始线性表的大小小于theSize,则不增加元素；
* 若初始线性表的大小大于theSize，则删除多余的元素。
*/
template<class T>
void chain<T>::setSize(int theSize)
{
	if (listSize > theSize)
	{
		chainNode<T>* currentNode = firstNode;
		for (int i = 0; i < theSize-1; i++)
			currentNode = currentNode->next;//使得currentNode指向第theSize个元素

		chainNode<T>* deleteNode = currentNode->next;
		currentNode->next = nullptr;//将第theSize个元素指向nullptr
		//删除所有多余的元素，重复利用了currentNode，可行
		while (deleteNode != nullptr)
		{
			currentNode = deleteNode->next;
			delete deleteNode;			
			deleteNode = currentNode;
		}
		listSize = theSize;
	}
}

/*
* 习题3
* 用元素theElement替换索引为theIndex的元素；若索引theIndex超出范围，则抛出异常
*/
template<class T>
void chain<T>::set(int theIndex, const T& theElement)
{
	checkIndex(theIndex);
	chainNode<T>* currentNode = firstNode;
	for (int i = 0; i < theIndex - 1; i++)
		currentNode = currentNode->next;
	currentNode->element = theElement;
}

/*
* 习题4
* 删除指定索引范围内的所有元素:(fromIndex,toIndex)---前开后开
* 如果给定范围超出链表范围，则抛出异常。
*/
template<class T>
void chain<T>::removeRange(int fromIndex, int toIndex)
{
	checkIndex(fromIndex+1);
	checkIndex(toIndex-1);
	chainNode<T>* fromNode = firstNode;
	int i = 0;
	for (i = 0; i < fromIndex; i++)
		fromNode = fromNode->next;//存住fromIndex的指针
	chainNode<T>* toNode = fromNode->next;//不删除fromIndex的结点
	i++;
	chainNode<T>* deleteNode = nullptr;
	//存住toIndex的指针并delete其间的结点
	while (i < toIndex)
	{
		deleteNode = toNode;
		toNode = toNode->next;
		delete deleteNode;//要注意后删，不然toNode会指向nullptr
		i++;
	}
	fromNode->next = toNode;
	listSize = listSize - (toIndex - fromIndex - 1);
}

/*
* 习题5
* 返回值是指定元素最后出现时的索引；若这样的元素不存在，则返回-1。
*/
template<class T>
int chain<T>::lastIndexOf(const T& theElement)
{
	int index = -1;
	int loc = 0;
	chainNode<T>* currentNode = firstNode;
	while (currentNode != nullptr)
	{
		//找到就更新index，没找到就不更新
		if (currentNode->element == theElement)
			index = loc;
		currentNode = currentNode->next;
		loc++;
	}
	return index;
}

/*
* 习题10：
* 交换链表*this和theChain的所有元素
*/
template<class T>
void chain<T>::swap(chain<T>& theChain)
{
	chainNode<T>* temp = firstNode;	
	firstNode = theChain.firstNode;
	theChain.firstNode = temp;

	int tempnum = listSize;
	listSize = theChain.listSize;
	theChain.listSize = tempnum;
}

/*
* 习题13：
* 将链表*this转换为数组theArray
* 将数组转换为链表我使用了构造函数实现
*/
template<class T>
void chain<T>::toArray(arrayList<T>& theArray)
{	
	theArray.clear();//首先要清空数组
	chainNode<T>* currentNode = firstNode;
	for (int i = 0; i < listSize; i++)
	{
		theArray.push_back(currentNode->element);
		currentNode = currentNode->next;
	}
}

/*习题14：将表中的元素向左移动i个位置*/
template<class T>
void chain<T>::leftShift(int i)
{
	if (listSize > i)
	{
		chainNode<T>* deleteNode = nullptr;
		for (int j = 0; j < i && j < listSize; j++)
		{
			deleteNode = firstNode;
			firstNode = firstNode->next;
			delete deleteNode;
		}
		listSize -= i;
	}
	else
		throw illegalIndex();
}

/*习题15：颠倒*this中的元素的顺序*/
template<class T>
void chain<T>::reverse()
{
	/*让第二个节点指向第一个节点*/
	chainNode<T>* beforeNode = nullptr;
	chainNode<T>* currentNode = firstNode;
	chainNode<T>* temp;
	/*让第二个节点以后，最后一个节点以前的所有节点指向它前面的节点*/
	while (currentNode != nullptr)
	{
		temp = currentNode->next;
		currentNode->next = beforeNode;
		beforeNode = currentNode;
		currentNode = temp;
	}
	/*firstNode指向最后一个节点*/
	firstNode = beforeNode;
}

/*
* 习题18：
meld()：*this为新的扩展的链表,它从a的首元素开始，交替地包含a和b的元素。
如果一个链表的元素取完了，就把另一个链表的剩余元素附加到新的扩展链表c中。
合并后的链表使用的应该是链表a和b的节点空间，合并之后，输入链表a和b是空表
*/
template<class T>
void chain<T>::meld(chain<T>& a, chain<T>& b)
{
	//先清空本链表
	(*this).clear();
	chainNode<T>* currentNode = nullptr;
	/*当前a,b链表都不为nullptr时*/
	while (a.firstNode != nullptr && b.firstNode != nullptr)
	{
		if (listSize == 0)
		{
			//如果a,b链表都不为空，则在c中先插入a,b的一个元素
			firstNode = a.firstNode;
			a.firstNode = (a.firstNode)->next;
			(a.listSize)--;
			firstNode->next = b.firstNode;
			b.firstNode = (b.firstNode)->next;
			(b.listSize)--;
			listSize += 2;
			currentNode = firstNode->next;//当前结点指向第二个元素
		}
		else
		{
			currentNode->next = a.firstNode;
			a.firstNode = (a.firstNode)->next;
			(a.listSize)--;
			listSize++;
			currentNode = currentNode->next;
			currentNode->next = b.firstNode;
			b.firstNode = (b.firstNode)->next;
			(b.listSize)--;
			listSize++;
			currentNode = currentNode->next;
		}
	}
	/*当前b链表为nullptr时*/
	if (a.firstNode != nullptr)
	{
		if (listSize == 0)
		{
			//如果当前a链表不为空，则在c中插入a的所有元素
			firstNode = a.firstNode;
			a.firstNode = nullptr;
			listSize += a.listSize;
			a.listSize = 0;
		}
		else
		{
			currentNode->next = a.firstNode;
			listSize += a.listSize;
			a.firstNode = nullptr;
			a.listSize = 0;
		}
	}
	/*当前a链表为nullptr时*/
	if (b.firstNode != nullptr)
	{
		if (listSize == 0)
		{
			//如果当前a链表不为空，则在c中插入a的所有元素
			firstNode = b.firstNode;
			b.firstNode = nullptr;
			listSize += b.listSize;
			b.listSize = 0;
		}
		else
		{
			currentNode->next = b.firstNode;
			b.firstNode = nullptr;
			listSize+=b.listSize;
			b.listSize = 0;
		}
	}	
}

/*
* 习题20
* merge():有序链表a和b,合并生成有序链表(*this),此后a,b链表都为空表
*/
template<class T>
void chain<T>::merge(chain<T>& a, chain<T>& b)
{
	//先清空本链表
	(*this).clear();
	chainNode<T>* currentNode = nullptr;
	/*当前a,b链表都不为nullptr时*/
	while (a.firstNode != nullptr && b.firstNode != nullptr)
	{
		//首先解决第一个元素
		if (listSize == 0)
		{
			//如果a,b链表都不为空，则在c中首先插入a,b中小的一个元素
			if ((a.firstNode)->element <= (b.firstNode)->element)
			{
				firstNode = a.firstNode;
				a.firstNode = (a.firstNode)->next;
				listSize++;
				a.listSize--;
				currentNode = firstNode;//当前结点指向第一个元素
			}
			else
			{   //如果a,b链表都不为空，则在c中首先插入a,b中小的一个元素
				firstNode = b.firstNode;
				b.firstNode = (b.firstNode)->next;
				listSize++;
				b.listSize--;
				currentNode = firstNode;//当前结点指向第一个元素
			}
		}
		//然后解决后面的元素
		else
		{
			if ((a.firstNode)->element <= (b.firstNode)->element)
			{
				currentNode->next = a.firstNode;
				a.firstNode = (a.firstNode)->next;
				listSize++;
				a.listSize--;
				currentNode = currentNode->next;
			}
			else
			{
				currentNode->next = b.firstNode;
				b.firstNode = (b.firstNode)->next;
				listSize++;
				b.listSize--;
				currentNode = currentNode->next;
			}
		}
	}
	/*当前b链表为nullptr时*/
	if (a.firstNode != nullptr)
	{
		if (listSize == 0)
		{
			//如果当前a链表不为空，则在c中插入a的所有元素
			firstNode = a.firstNode;
			a.firstNode = nullptr;
			listSize += a.listSize;
			a.listSize = 0;
		}
		else
		{
			currentNode->next = a.firstNode;
			listSize += a.listSize;
			a.firstNode = nullptr;
			a.listSize = 0;
		}
	}
	/*当前a链表为nullptr时*/
	while (b.firstNode != nullptr)
	{
		if (listSize == 0)
		{
			//如果当前a链表为空，则在c中插入b的所有元素
			firstNode = b.firstNode;
			b.firstNode = nullptr;
			listSize += b.listSize;
			b.listSize = 0;
		}
		else
		{
			currentNode->next = b.firstNode;
			b.firstNode = nullptr;
			listSize += b.listSize;
			b.listSize = 0;
		}
	}
}

/*
* 练习22
* split():生成两个扩展链表a和b,a包含*this中索引为奇数的元素，b包含*this中其他的元素,此后*this链表为空表
*/
template<class T>
void chain<T>::split(chain<T>& a, chain<T>& b)
{
	chainNode<T>* currentNodeA = nullptr;
	chainNode<T>* currentNodeB = nullptr;
	for (int i = 0; i < listSize; i++)
	{
		if (i % 2 == 0)
		{
			if (b.listSize == 0)
			{
				b.firstNode = firstNode;
				firstNode = firstNode->next;
				(b.listSize)++;
				currentNodeB = b.firstNode;
			}
			else
			{
				currentNodeB->next = firstNode;
				firstNode = firstNode->next;
				(b.listSize)++;
				currentNodeB = currentNodeB->next;
			}
		}
		else
		{
			if (a.listSize == 0)
			{
				a.firstNode = firstNode;
				firstNode = firstNode->next;
				(a.listSize)++;
				currentNodeA = a.firstNode;
			}
			else
			{
				currentNodeA->next = firstNode;
				firstNode = firstNode->next;
				(a.listSize)++;
				currentNodeA = currentNodeA->next;
			}
		}
	}
	listSize = 0;
	currentNodeA->next = nullptr;
	currentNodeB->next = nullptr;
}

/*
* 练习23：
* 循环移动 [0,1,2,3,4]循环移动两位是[2,3,4,0,1]
*/
template<class T>
void chain<T>::circularShift(int i)
{
	//存住原始第一个节点
	chainNode<T>* originalNode = firstNode;
	chainNode<T>* lastNode = nullptr;
	//找到循环移动结束后的第一个节点
	for (int j = 0; j < i; j++)
	{
		firstNode = firstNode->next;
		//找到循环移动结束后的最后一个节点
		if (j == i - 2)
			lastNode = firstNode;
	}
	chainNode<T>* currentNode = firstNode;
	//找到原始链表的最后一个节点
	while (currentNode->next != nullptr)
		currentNode = currentNode->next;
	//原始链表的最后一个结点指向原始链表的第一个结点
	currentNode->next = originalNode;
	//循环结束后的最后一个结点指向nullptr
	lastNode->next = nullptr;
}

/*重载操作符*/

/*
* 习题6
* 重载[]操作符
*/
template<class T>
T& chain<T>::operator[](int i)
{
	checkIndex(i);
	chainNode<T>* currentNode = firstNode;
	for (int j = 0; j < i; j++)
		currentNode = currentNode->next;//先获取到地址
	return currentNode->element;//然后返回元素
}
template<class T>
const T& chain<T>::operator[](int i) const
{
	checkIndex(i);
	chainNode<T>* currentNode = firstNode;
	for (int j = 0; j < i; j++)
		currentNode = currentNode->next;//先获取到地址
	return currentNode->element;//然后返回元素
}

/*习题7：重载==操作符*/
template<class T>
bool chain<T>::operator==(chain<T>& right) const
{
	if (listSize == right.listSize)
	{
		int i = listSize;
		chainNode<T>* leftNode = firstNode;
		chainNode<T>* rightNode = right.firstNode;
		while (i--)
		{
			//只要有不相等就返回false
			if (leftNode->element != rightNode->element)
				return false;
			leftNode = leftNode->next;
			rightNode = rightNode->next;
		}
		//只有全部相等时才返回true
		return true;
	}
	else  //长度不相等直接返回false
		return false;	
}

/*习题8：重载!=操作符*/
template<class T>
bool chain<T>::operator!=(chain<T>& right) const
{
	if (listSize == right.listSize)
	{
		int i = listSize;
		chainNode<T>* leftNode = firstNode;
		chainNode<T>* rightNode = right.firstNode;
		while (i--)
		{
			//只要有不相等就返回true
			if (leftNode->element != rightNode->element)
				return true;
			leftNode = leftNode->next;
			rightNode = rightNode->next;
		}
		//只有全部相等时才返回false
		return false;
	}
	else  //长度不相等直接返回true
		return true;
}

/*习题9；重载<操作符,要求左边链表所有的元素都小于右边链表的元素*/
template<class T>
bool chain<T>::operator<(chain<T>& right) const
{
	//左边链表长度大于右边链表时，直接返回false
	if (listSize > right.listSize)
		return false;
	else
	{
		chainNode<T>* leftNode = firstNode;
		chainNode<T>* rightNode = right.firstNode;
		for (int i = 0; i < listSize; i++)
		{
			//存在左边链表的元素大于右边链表的元素时，直接返回false
			if (leftNode->element >= rightNode->element)
				return false;
			leftNode = leftNode->next;
			rightNode = rightNode->next;
		}
		return true;
	}
}

/*排序*/
/*冒泡排序*/
template<class T>
void chain<T>::bubbleSort()
{
	for (int i = listSize; i > 1; i--)
	{
		int j = 1;
		chainNode<T>* currentNode = firstNode;
		while (j < i)
		{
			if (currentNode->element > currentNode->next->element)
				Swap<T>(currentNode->element, currentNode->next->element);
			currentNode = currentNode->next;
			j++;
		}
	}
}

/*按名次排序*/
template<class T>
void chain<T>::rankSort()
{
	int* r = new int[listSize];
	//初始化名次
	for (int i = 0; i < listSize; i++)
		r[i] = 0;
	//计算名次
	for (int i = listSize - 1; i >= 0; i--) //从右往左拿出每个元素与其他元素比较
	{
		for (int j = 0; j < i; j++)
		{
			if ((*this)[i]>(*this)[j])
				r[i]++;
			else
				r[j]++;
		}
	}
	//按名次排序
	for (int i = 0; i < listSize; i++)
	{
		if (i != r[i])
		{
			Swap<T>((*this)[i], (*this)[r[i]]);
			Swap<T>(r[i], r[r[i]]);
		}
	}
	delete[] r;
}

/*返回链表的最大元素*/
template<class T>
T chain<T>::maxOfList()
{
	chain<T>::iterator it = (*this).begin();
	T tempMax = *it;//存储最大元素
	for (int i = 1; i < listSize; i++)
	{
		it++;
		if ((*it) > tempMax)
		{
			tempMax = *it;
		}
	}
	return tempMax;
}

/*选择排序*/
template<class T>
void chain<T>::selectionSort()
{
	int indexMax = 0;
	bool is_sorted = false;
	for (int i = listSize; i > 1 && !is_sorted; i--)
	{
		is_sorted = true;
		indexMax = 0;
		chain<T>::iterator it = (*this).begin();
		T tempMax = *it;//存储最大元素
		for (int j = 1; j < i; j++)
		{
			it++;
			if ((*it) > tempMax)
			{
				tempMax = *it;
				indexMax = j;
			}
			else
				is_sorted = false;
		}
		Swap<T>((*this)[i - 1], (*this)[indexMax]);
	}
}

/*插入排序*/
template<class T>
void  chain<T>::insertSort()
{
	for (int i = 1; i < listSize; i++)
	{
		chainNode<T>* currentNode = firstNode;
		int tempData = (*this)[i];
		int j = 0;
		for (j = 0; j < i ; j++)
		{
			if (tempData < currentNode->element)
				break;
			else
				currentNode = currentNode->next;
		}
		if (j != i)
		{
			(*this).insert(j, tempData);
			(*this).erase(i + 1);
		}
	}
}

/*箱子排序,range指定了链表元素的最大范围,适合数据集中的情况*/
template<class T>
void chain<T>::binSort(int range)
{
	//对链表中的结点排序
	//创建初始化箱子
	chainNode<T>** bottom, ** top;//bottom指向箱子的底部，top指向箱子的顶部
	bottom = new chainNode<T>*[range + 1];
	top = new chainNode<T>*[range + 1];
	for (int b = 0; b <= range; b++)
		bottom[b] = nullptr;

	//把链表的结点分配到箱子
	for (; firstNode != nullptr; firstNode = firstNode->next)
	{//把首结点firstNode加入到箱子中
		int data = firstNode->element;//元素类型转换为整型
		if (bottom[data] == nullptr) //箱子为空
			bottom[data] = top[data] = firstNode;
		else  //箱子不空
		{
			top[data]->next = firstNode;
			top[data] = firstNode;
		}
	}

	//把箱子中的结点收集到有序链表
	chainNode<T>* y = nullptr;
	for (int bin = 0; bin <= range; bin++)
	{
		if (bottom[bin] != nullptr)
		{
			if (y == nullptr)  //第一个非空箱子
				firstNode = bottom[bin];
			else
				y->next = bottom[bin];
			y = top[bin];
		}		
	}
	if (y->next != nullptr)
		y->next = nullptr;
	delete[] bottom;
	delete[] top;
}

/*基数排序*/
template<class T>
void chain<T>::baseBinSort(int range)
{
	//对链表中的结点排序
	chainNode<T>** bottom, ** top;//bottom指向箱子的底部，top指向箱子的顶部
	bottom = new chainNode<T>*[range + 1];
	top = new chainNode<T>*[range + 1];
	//获取链表中数据的最大值
	int maxData = maxOfList();
	int binNum = 1;//计算要进行箱子排序的次数
	while (maxData / (range + 1))
	{
		maxData /= (range + 1);
		binNum++;
	}		
	for(int i = 0;i< binNum;i++)
	{
		//每一次都要初始化箱子
		for (int b = 0; b <= range; b++)
			bottom[b] = nullptr;

		//把链表的结点分配到箱子
		for (; firstNode != nullptr; firstNode = firstNode->next)
		{//把首结点firstNode加入到箱子中
			int data = int((firstNode->element)/pow(10,i)) % 10;//元素类型转换为整型
			if (bottom[data] == nullptr) //箱子为空
				bottom[data] = top[data] = firstNode;
			else  //箱子不空
			{
				top[data]->next = firstNode;
				top[data] = firstNode;
			}
		}

		//把箱子中的结点收集到有序链表
		chainNode<T>* y = nullptr;
		for (int bin = 0; bin <= range; bin++)
		{
			if (bottom[bin] != nullptr)
			{
				if (y == nullptr)  //第一个非空箱子
					firstNode = bottom[bin];
				else
					y->next = bottom[bin];
				y = top[bin];
			}
		}
		if (y->next != nullptr)
			y->next = nullptr;
		cout << "(*this) = " << *this << endl;
	}	
	delete[] bottom;
	delete[] top;
}


/*非成员方法*/
/*meld()：生成一个新的扩展的链表c,它从a的首元素开始，交替地包含a和b的元素。
如果一个链表的元素取完了，就把另一个链表的剩余元素附加到新的扩展链表c中。*/
template<class T>
void meld(chain<T>& a, chain<T>& b, chain<T>& c)
{
	c.clear();//先清空链表C
	typename chain<T>::iterator pointerA = a.begin();
	typename chain<T>::iterator pointerB = b.begin();
	while (pointerA != nullptr && pointerB != nullptr)
	{
		c.push_back(*pointerA);
		pointerA++;
		c.push_back(*pointerB);
		pointerB++;
	}
	while (pointerA != nullptr)
	{
		c.push_back(*pointerA);
		pointerA++;
	}
	while (pointerB != nullptr)
	{
		c.push_back(*pointerB);
		pointerB++;
	}
}

/*方法merge()---生成一个新的有序链表c,包含了a和b的所有元素,且函数后a,b链表不为空*/
template<class T>
void merge(chain<T>& a, chain<T>& b, chain<T>& c)
{
	c.clear();//先清空链表C
	typename chain<T>::iterator pointerA = a.begin();
	typename chain<T>::iterator pointerB = b.begin();
	while (pointerA != nullptr && pointerB != nullptr)
	{
		/*插入小的那一个*/
		if (*pointerA > *pointerB)
		{
			c.push_back(*pointerB);
			pointerB++;
		}
		else
		{
			c.push_back(*pointerA);
			pointerA++;
		}		
	}
	while (pointerA != nullptr)
	{
		c.push_back(*pointerA);
		pointerA++;
	}
	while (pointerB != nullptr)
	{
		c.push_back(*pointerB);
		pointerB++;
	}
}

/*生成两个链表a和b,a包含c中索引为奇数的元素，b包含c中其他的元素，且函数后c链表不为空*/
template<class T>
void split(chain<T>& a, chain<T>& b, chain<T>& c)
{
	//先清空链表a和链表b
	a.clear();
	b.clear();
	typename chain<T>::iterator pointerC = c.begin();
	for (int i = 0; i < c.size(); i++)
	{
		if (i % 2 == 1)
		{
			a.push_back(*pointerC);
			pointerC++;
		}
		else
		{
			b.push_back(*pointerC);
			pointerC++;
		}
	}
}

#endif

_7arrayAndChain.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			数组线性表和链表线性表交互的头文件
*/
#pragma once
#ifndef _ARRAYANDCHAIN_H_
#define _ARRAYANDCHAIN_H_
#include "_6chain.h"
#include "_5arrayList.h"
/*第六章习题11：将数组转换为链表，返回链表*/
template<class T>
chain<T> arrayToChain(const arrayList<T>& arrayTo)
{
	chain<T> toChain;
	int size = arrayTo.size();
	T data = 0;
	for (int i = 0; i < size; i++)
	{
		data = arrayTo.get(i);
		toChain.insert(i, data);
	}
	return toChain;
}

/*第六章习题12：将链表转换为数组，返回值为数组。*/
template<class T>
arrayList<T> chainToArray(const chain<T>& chainTo)
{
	arrayList<T> toArray;
	int size = chainTo.size();
	T data = 0;
	for (int i = 0; i < size; i++)
	{
		data = chainTo.get(i);
		toArray.insert(i, data);
	}
	return toArray;
}
#endif

_1main.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			main()函数，控制运行所有的测试函数
*/
#include <iostream>
#include "_6chain.h"

int main()
{
	chainTest();
	return 0;
}

_6chain.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_6chain.h头文件中的所有函数
*/
#include "_5arrayList.h"
#include "_6chain.h"
#include "_7arrayAndChain.h"
using std::cout;
using std::endl;

void chainTest()
{
	cout << endl << "**********************************chainTest()函数开始*****************************************" << endl;
	cout << "测试成员函数*********************************************" << endl;
	//测试构造函数
	cout << "测试构造函数******************" << endl;
	chain<int> data;
	//测试insert()成员函数
	cout << "测试insert()成员函数**********" << endl;
	data.insert(0, 99);
	data.insert(0, 88);
	data.insert(0, 77);
	data.insert(0, 66);
	//测试输出
	cout << "测试输出**********************" << endl;
	cout << "data = " << data << endl;//data = 66 77 88 99
	//测试复制构造函数
	cout << "测试复制构造函数**************" << endl;
	chain<int> data1(data);
	cout << "data1 = " << data1 << endl;//data1 = 66 77 88 99
	//测试使用arrayList初始化链表的构造函数
	cout << "测试使用arrayList初始化链表的构造函数" << endl;
	arrayList<int> arrayData2;
	arrayData2.push_back(1);
	arrayData2.push_back(2);
	arrayData2.push_back(3);
	chain<int> chainData1(arrayData2);
	cout << "chainData1 = " << chainData1 << endl;//chainData1 = 1 2 3
	//测试get()成员函数
	cout << "测试get()成员函数*************" << endl;
	cout << "data.get(0) = " << data.get(0) << endl;//data.get(0) = 66
	//测试indexOf()成员函数
	cout << "测试indexOf()成员函数*********" << endl;
	cout << "data.indexOf(99) = " << data.indexOf(99) << endl;//data.indexOf(99) = 3
	//测试erase()成员函数
	cout << "测试erase()成员函数***********" << endl;
	data.erase(0);
	cout << "data = " << data << endl;//data = 77 88 99
	//测试clear()成员函数
	cout << "测试clear()成员函数***********" << endl;
	data1.clear();
	cout << "data1 = " << data1 << endl;//data1 =
	//测试push_back()成员函数
	cout << "测试push_back()成员函数*******" << endl;
	data1.push_back(99);
	cout << "data1 = " << data1 << endl;//data1 = 99
	data.push_back(66);
	cout << "data = " << data << endl;//data = 77 88 99 66
	//测试setSize()成员函数
	cout << "测试setSize()成员函数*********" << endl;
	data.setSize(5);
	cout << "data = " << data << endl;//data = 77 88 99 66
	data.setSize(3);
	cout << "data = " << data << endl;//data = 77 88 99
	data.setSize(2);
	cout << "data = " << data << endl;//data = 77 88
	//测试set()成员函数
	cout << "测试set()成员函数*************" << endl;
	data.insert(0, 5);
	data.insert(0, 9);
	data.insert(0, 8);
	data.insert(0, 2);
	cout << "data = " << data << endl;//data = 2 8 9 5 77 88
	data.set(0, 99);
	cout << "data = " << data << endl;//data = 99 8 9 5 77 88
	cout << "测试removeRange()成员函数*****" << endl;
	data.removeRange(1, 3);
	cout << "data = " << data << endl;//data = 99 8 5 77 88
	cout << "测试lastIndexOf()成员函数*****" << endl;
	cout << "data.lastIndexOf(8) = " << data.lastIndexOf(8) << endl;//data.lastIndexOf(8) = 1
	cout << "data.lastIndexOf(2) = " << data.lastIndexOf(2) << endl;//data.lastIndexOf(2) = -1
	cout << "测试swap()成员函数************" << endl;
	chain<int> data3(data1);
	chain<int> data4(data);
	cout << "data3 = " << data3 << endl;//data3 = 99
	cout << "data4 = " << data4 << endl;//data4 = 99 8 5 77 88
	data3.swap(data4);
	cout << "data3 = " << data3 << endl;//data4 = 99 8 5 77 88
	cout << "data4 = " << data4 << endl;//data4 = 99
	cout << "测试toArray()成员函数*********" << endl;
	arrayList<int> arrayData3;
	cout << "arrayData3 = " << arrayData3 << endl;//arrayData3 =
	data3.toArray(arrayData3);
	cout << "arrayData3 = " << arrayData3 << endl;//arrayData3 = 99 8 5 77 88
	cout << "测试leftShift()成员函数*********" << endl;
	cout << "data3 = " << data3 << endl;//data3 = 5 77 88 10 66
	data3.leftShift(2);
	cout << "data3 = " << data3 << endl;//data3 = 5 77 88
	cout << "测试reverse()成员函数***********" << endl;
	data3.push_back(10);
	data3.push_back(66);
	cout << "data3 = " << data3 << endl;//data3 = 5 77 88 10 66
	data3.reverse();
	cout << "data3 = " << data3 << endl;//data3 = 66 10 88 77 5
	cout << "测试meld()成员函数**************" << endl;
	data4.push_back(68);
	chain<int> data5;
	chain<int> data6(data3);
	chain<int> data7(data4);
	chain<int> data8(data3);
	cout << "data3 = " << data3 << endl;//data3 = 66 10 88 77 5
	cout << "data4 = " << data4 << endl;//data4 = 99 68
	data5.meld(data3, data4);
	cout << "data5.meld(data3, data4)之后**" << endl;
	cout << "data3 = " << data3 << endl;//data3 =
	cout << "data4 = " << data4 << endl;//data4 =
	cout << "data5 = " << data5 << endl << endl;//data5 = 66 99 10 68 88 77 5

	cout << "data7 = " << data7 << endl;//data7 = 99 68
	cout << "data6 = " << data6 << endl;//data6 = 66 10 88 77 5
	data5.meld(data7, data6);
	cout << "data5.meld(data7, data6)之后**" << endl;
	cout << "data7 = " << data7 << endl;//data7 =
	cout << "data6 = " << data6 << endl;//data6 =
	cout << "data5 = " << data5 << endl << endl;//data5 = 99 66 68 10 88 77 5

	chain<int> data9;
	cout << "data8 = " << data8 << endl;//data8 = 66 10 88 77 5
	cout << "data9 = " << data9 << endl;//data9 =
	data5.meld(data8, data9);
	cout << "data5.meld(data8, data9)之后**" << endl;
	cout << "data8 = " << data8 << endl;//data8 =
	cout << "data8.size() = " << data8.size() << endl;//data8.size = 0
	cout << "data9 = " << data9 << endl;//data9 =
	cout << "data9.size() = " << data9.size() << endl;//data9.size = 0
	cout << "data5 = " << data5 << endl;//data5 = 66 10 88 77 5
	cout << "data5.size() = " << data5.size() << endl;//data5.size() = 5
	cout << "测试merge()成员函数*************" << endl;
	chain<int> data10(data5);
	data10.erase(0);
	chain<int> data11;
	cout << "data5 = " << data5 << endl;//data5 = 5 10 66 77 88
	cout << "data10 = " << data10 << endl;//data10 = 10 66 77 88
	cout << "data11 = " << data11 << endl;//data11 =
	data11.merge(data5, data10);
	cout << "data11.merge(data5, data10)之后" << endl;
	cout << "data5 = " << data5 << endl;//data5 =
	cout << "data5.size() = " << data5.size() << endl;//data5.size() = 0
	cout << "data10 = " << data10 << endl;//data10 =
	cout << "data10.size() = " << data10.size() << endl;//data10.size() = 0
	cout << "data11 = " << data11 << endl;//data11 = 5 10 10 66 66 77 77 88 88
	cout << "data11.size() = " << data11.size() << endl;//data11.size() = 9
	cout << "测试split()成员函数*************" << endl;
	cout << "测试circularShift()成员函数*****" << endl;
	data11.split(data5, data10);
	cout << "data5 = " << data5 << endl;//data5 = 5 10 66 77 88
	cout << "data5.size() = " << data5.size() << endl;//data5.size() = 5
	cout << "data10 = " << data10 << endl;//data10 = 10 66 77 88
	cout << "data10.size() = " << data10.size() << endl;//data10.size() = 4
	cout << "data11 = " << data11 << endl;//data11 =
	cout << "data11.size() = " << data11.size() << endl;//data11.size() = 0
	cout << "测试circularShift()成员函数*****" << endl;
	data5.circularShift(2);
	cout << "data5 = " << data5 << endl;//data5 = 66 77 88 5 10

	cout << endl << "重载操作符************************************************" << endl;
	cout << "测试[]操作符******************" << endl;
	cout << "data = " << data << endl;
	cout << "data[0] = " << data[0] << endl;//data[0] = 99
	cout << "data[1] = " << data[1] << endl;//data[1] = 8
	cout << "data[2] = " << data[2] << endl;//data[2] = 5
	data[0] = 88;
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	cout << "测试==操作符******************" << endl;
	chain<int> data2(data);
	cout << "data2 = " << data2 << endl;//data2 = 88 8 5 77 88
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	cout << "data1 = " << data1 << endl;//data1 = 99
	cout << "(data2 == data) = " << (data2 == data) << endl;//(data2 == data) = 1
	cout << "(data2 == data1) = " << (data2 == data1) << endl;//(data2 == data1) = 0
	data2[4] = 9;
	cout << "data2 = " << data2 << endl;//data2 = 88 8 5 77 9
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	cout << "(data2 == data) = " << (data2 == data) << endl;//(data2 == data) = 0
	cout << "测试!=操作符******************" << endl;
	cout << "data2 = " << data2 << endl;//data2 = 88 8 5 77 9
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	cout << "data1 = " << data1 << endl;//data1 = 99
	cout << "(data2 != data) = " << (data2 != data) << endl;//(data2 != data) = 1
	cout << "(data2 != data1) = " << (data2 != data1) << endl;//(data2 != data1) = 1
	data2[4] = 88;
	cout << "data2 = " << data2 << endl;//data2 = 88 8 5 77 88
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	cout << "(data2 != data) = " << (data2 != data) << endl;//(data2 != data) = 0
	cout << "测试<操作符*******************" << endl;
	cout << "data2 = " << data2 << endl;//data2 = 88 8 5 77 88
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	data1[0] = 66;
	cout << "data1 = " << data1 << endl;//data1 = 66
	cout << "(data2 < data) = " << (data2 < data) << endl;//(data2 < data) = 0
	cout << "(data1 < data2) = " << (data1 < data2) << endl;//(data1 < data2) = 1
	data2[0] = 1;
	data2[1] = 1;
	data2[2] = 1;
	data2[3] = 1;
	data2[4] = 1;
	cout << "data2 = " << data2 << endl;//data2 = 1 1 1 1 1
	cout << "data = " << data << endl;//data = 88 8 5 77 88
	cout << "(data2 < data) = " << (data2 < data) << endl;//(data2 < data) = 1

	cout << endl << "测试非成员函数******************************************" << endl;
	arrayList<int> arrayData;
	arrayData.push_back(9);
	arrayData.push_back(999);
	arrayData.push_back(99);
	cout << "测试arrayToChain()函数********" << endl;
	cout << "arrayData = " << arrayData << endl;//arrayData = 9 999 99
	chain<int> chainData(arrayToChain(arrayData));
	cout << "chainData = " << chainData << endl;//chainData = 9 999 99
	cout << "测试chainToArray()函数********" << endl;
	arrayList<int> arrayData1(chainToArray(chainData));
	arrayData1.push_back(88);
	cout << "arrayData1 = " << arrayData1 << endl;//arrayData1 = 9 999 99 88
	cout << "测试meld()函数****************" << endl;
	chain<int> chainData3(arrayToChain(arrayData));
	chain<int> chainData4;
	cout << "chainData = " << chainData << endl;//chainData = 9 999 99
	cout << "chainData3 = " << chainData3 << endl;//chainData3 = 9 999 99
	meld(chainData, chainData3, chainData4);
	cout << "chainData4 = " << chainData4 << endl << endl;//chainData4 = 9 9 999 999 99 99
	chainData3.insert(0, 68);
	chainData3.insert(0, 98);
	cout << "chainData = " << chainData << endl;//chainData = 9 999 99
	cout << "chainData3 = " << chainData3 << endl;//chainData3 = 98 68 9 999 99
	meld(chainData, chainData3, chainData4);
	cout << "chainData4 = " << chainData4 << endl<<endl;//chainData4 = 9 98 999 68 99 9 999 99
	meld(chainData3, chainData, chainData4);
	cout << "chainData4 = " << chainData4 << endl<<endl;//chainData4 = 98 9 68 999 9 99 999 99
	chain<int> chainData5;
	meld(chainData3, chainData5, chainData4);
	cout << "chainData3 = " << chainData3 << endl;//chainData3 = 98 68 9 999 99
	cout << "chainData5 = " << chainData5 << endl;//chainData5 =
	cout << "chainData4 = " << chainData4 << endl << endl;//chainData4 = 98 68 9 999 99
	meld(chainData5, chainData3, chainData4);
	cout << "chainData5 = " << chainData5 << endl;//chainData5 =
	cout << "chainData3 = " << chainData3 << endl;//chainData3 = 98 68 9 999 99
	cout << "chainData4 = " << chainData4 << endl << endl;//chainData4 = 98 68 9 999 99
	cout << "测试split()函数**************" << endl;
	chain<int> chainData6;
	chain<int> chainData7;
	cout << "chainData6 = " << chainData6 << endl;//chainData6 =
	cout << "chainData7 = " << chainData7 << endl;//chainData7 =
	cout << "chainData4 = " << chainData4 << endl;//chainData4 = 98 68 9 999 99
	split(chainData6, chainData7, chainData4);
	cout << "split(chainData6, chainData7, chainData4)之后" << endl;
	cout << "chainData6 = " << chainData6 << endl;//chainData6 =
	cout << "chainData6.size() = " << chainData6.size() << endl;//chainData6 =
	cout << "chainData7 = " << chainData7 << endl;//chainData7 =
	cout << "chainData7.size() = " << chainData7.size() << endl;//chainData7 =
	cout << "chainData4 = " << chainData4 << endl;//chainData4 = 98 68 9 999 99
	cout << "chainData4.size() = " << chainData4.size() << endl;//chainData7 =

	cout << endl << "排序****************************************************" << endl;
	cout << "测试bubbleSort()成员函数********" << endl;
	data5.bubbleSort();
	cout << "data5 = " << data5 << endl;//data5 = 5 10 66 77 88
	cout << "测试rankSort()成员函数**********" << endl;
	data5.reverse();
	cout << "data5 = " << data5 << endl;//data5 = 5 10 66 77 88
	data5.rankSort();
	cout << "data5 = " << data5 << endl;//data5 = 5 10 66 77 88

	cout << "maxOfList()*******************************" << endl;
	cout << "data5.maxOfList() = " << data5.maxOfList() << endl;//data5.maxOfList() = 4
	cout << "selectionSort()排序***********************" << endl;
	data5.reverse();
	cout << "data5 = " << data5 << endl;//data5 = 88 77 10 10 5
	data5.selectionSort();
	cout << "data5 = " << data5 << endl;//data5 = 5 10 10 77 88
	cout << "insertSort()排序**************************" << endl;
	data5.reverse();
	data5.insert(1, 99);
	cout << "data5 = " << data5 << endl;//data5 = 88 99 77 10 10 5
	data5.insertSort();
	cout << "data5 = " << data5 << endl;//data5 = 5 10 10 77 88 99
	cout << "binSort()排序****************************" << endl;
	chain<int> data12;
	data12.push_back(0);
	data12.push_back(5);
	data12.push_back(3);
	data12.push_back(4);
	data12.push_back(2);
	data12.push_back(5);
	cout << "data12 = " << data12 << endl;//data12 = 0 5 3 4 2 5
	data12.binSort(5);
	cout << "data12 = " << data12 << endl;//data12 = 0 2 3 4 5 5
	cout << "baseBinSort()排序************************" << endl;
	chain<int> data13;
	data13.push_back(216);
	data13.push_back(521);
	data13.push_back(425);
	data13.push_back(116);
	data13.push_back(91);
	data13.push_back(515);
	data13.push_back(124);
	data13.push_back(34);
	data13.push_back(96);
	data13.push_back(24);
	cout << "data13 = " << data13 << endl;
	data13.baseBinSort(9);
	cout << "data13 = " << data13 << endl;

	cout << endl << "友元函数***********************************************************************" << endl;
	cout << "cin>>*************************************" << endl;
	chain<int> cindata;
	cin >> cindata;
	cout << "cindata = " << cindata << endl;

	cout << "**********************************chainTest()函数结束*****************************************" << endl;
}