数组实现与链式描述相比在不同操作下的时间复杂度不一样
操作 | 数组 | 链表(单向) |
随机访问 | 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();
}
Comments 8 条评论
博主 匿名
吱吱我好爱
博主 匿名
@匿名 吱吱我好爱
博主 匿名
@匿名 吱吱我好爱
博主 匿名
@匿名 ???吱吱我好爱
博主 卿非山谷
@匿名 ????
博主 匿名
@匿名 我好爱你吱吱?
博主 你这瓜保熟吗
来这里踩一踩。?
博主 嘉然今天学什么
:han: