数据结构（2）线性表-链式描述

数组实现与链式描述相比在不同操作下的时间复杂度不一样

操作	数组	链表（单向）
随机访问	O(1)	O(N)
头部插入元素	O(N)	O(1)
头部删除元素	O(N)	O(1)
尾部插入元素	O(1)	O(N)
尾部删除元素	O(1)	O(N)
在theIndex插入或删除	O(listSize-theIndex)	O(theIndex)

链表首先需要定义一个结构chainNode，节点包含自身的值和指向下一个节点的指针，包含两种构造函数。

template<class T>
struct chainNode {
	T element;
	chainNode<T>* next;

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

之后就是定义类chain，除了一堆函数之外，主要就是第一个节点的位置以及链表的长度

template<class T>
class chain
{
public:
	chain(int initialCapacity = 10);
	chain(const chain<T>&);
	~chain();

	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() const;

protected:
	void checkIndex(int theIndex) const;
	chainNode<T>* firstNode;
	int listSize;
};

首先来写构造函数，同样还是函数重载，一种新建一种复制

//新建的很简单，没啥说的
template<class T>
chain<T>::chain(int initialCapacity) {
	firstNode = NULL;
	listSize = 0;
}

//复制的复杂一点，首先判断要复制的链表是否为空
template<class T>
chain<T>::chain(const chain<T>& theList) {
	listSize = theList.listSize;
	if (listSize == 0) {
		firstNode = NULL;
		return;
	}

//如果链表不空，首先新建指针sourceNode指向被复制链表的首节点
	chainNode<T>* sourceNode = theList.firstNode;
	firstNode = new chainNode<T>(sourceNode->element);//使用节点的构造函数新建新链表的首节点，使firstNode指向它
	sourceNode = sourceNode->next;//sourceNode指向第二个节点
	chainNode<T>* targetNode = firstNode;//新建targetNode指向首节点
	while (sourceNode != NULL) {//实际上sourceNode比targetNode快一步，以完成新节点的构造以及指针指向下一个节点，且source一直指向的被复制的链表里的节点，而targetNode指向的都是新链表的节点
		targetNode->next = new chainNode<T>(sourceNode->element);
		targetNode = targetNode->next;
		sourceNode = sourceNode->next;
	}
	targetNode->next = NULL;
}

析构函数也不能空在那里，要一个一个节点的删完

template<class T>
chain<T>::~chain() {
	while (firstNode != NULL) {
		chainNode<T>* nextNode = firstNode->next;//新建节点指针指向下一个节点
		delete firstNode;
		firstNode = nextNode;
	}
} 

有一个检查函数，看看索引在不在范围内

template<class T>
void chain<T>::checkIndex(int theIndex) const {
	int a = 1;
	if (theIndex < 0 || theIndex >= listSize) {
		a = 0;
	}
	assert(a==1);
}

之后是返回指定索引theIndex的元素，实质上就是顺着指针往后数theIndex个，取出节点的element值。注意函数是返回引用。

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;
}

之后是查找某一元素，返回第一次出现的索引；没啥难点，主要是要考虑到不存在的情况

template<class T>
int chain<T>::indexOf(const T& theElement) const {//若不存在返回-1
	chainNode<T>* currentNode = firstNode;
	int index = 0;
	while (currentNode->element != theElement && currentNode != NULL) {
		currentNode = currentNode->next;
		index++;
	}
	if (currentNode == NULL)
		return -1;
	else
		return index;
}

之后是对链表的修改，包括插入元素和删除元素。

template<class T>
void chain<T>::insert(int theIndex, const T& theElement) {
	if (theIndex < 0 || theIndex>listSize) {
		cout << "超出范围" << endl;
	}
	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;
		}
		chainNode<T>* t = new chainNode<T>(theElement, p->next);//这句好妙啊，从右向左执行，先新建了节点，next指针指向p->next，然后再把p->next指向这个新节点，要我写肯定要写个temp中转一下
		p->next = t;
	}
	listSize++;//不要忘了修改listSize
}

template<class T>
void chain<T>::erase(int theIndex) {
	checkIndex(theIndex);
	chainNode<T>* deleteNode;
	if (theIndex == 0) {
		deleteNode = firstNode;
		firstNode = firstNode->next;
	}
	else {
		chainNode<T>* p = firstNode;
		for (int i = 0; i < theIndex-1; i++)
			p = p->next;
		deleteNode = p->next;
		p->next = p->next->next;
	}
	listSize--;
	delete deleteNode;
}

最后是输出链表每个元素

template<class T>
void chain<T>::output() const {
	for (chainNode<T>* currentNode = firstNode;
		currentNode != NULL;
		currentNode = currentNode->next)
		cout << currentNode->element << " ";
	cout << endl;
}

在main函数里测试一下

#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
using namespace std;
int main()
{
	chain<int> *a = new chain<int>;
	for (int i = 0; i < 10; i++) {
		a->insert(i, i);
	}
	cout << a->size() << endl;;
	a->erase(2);
	a->output();
	cout << a->get(3) << endl;;
	cout<<a->indexOf(4)<<endl;
}

最后觉得这个循环插入浪费性能了，可以再写一个构造函数使用数组赋值

/*----------链表构造函数（数组）-----------------*/
template<class T>
chain<T>::chain(const T *array,int length) {
	firstNode = new chainNode<T>(array[0], NULL);
	chainNode<T>* c = firstNode;
	for (int i = 1; i < length; i++) {
		c->next = new chainNode<T>(array[i], NULL);
		c = c->next;
	}
	listSize = length;
}
/*-------------main.cpp-----------------*/
#include <iostream>
#include "shuzu.h"
#include "shuzu.cpp"
using namespace std;
int main()
{
	int* ar = new int[5]{ 1,2,3,4,5 };
	chain<int> *a = new chain<int>(ar,5);
	cout << a->size() << endl;;
	a->output();

}