单链表的基本操作
线性表的链式描述
单链表的插入操作
单链表的删除操作
单链表的实现
单链表类的实现：
//chain.hpp//-线性表链式描述//-单链表#pragma once#include#include #include #include "linearList.h"#include "illegalIndex.hpp"//链表节点的结构定义template struct chainNode { T element; chainNode *next; //methods chainNode() {} chainNode(const T& element) { this->element = element; } chainNode(const T& element, chainNode * next) { this->element = element; this->next = next; }};//单链表chain类template class chain : linearList {public: //constructor chain(); chain(const chain &); ~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 clear(); void insert(int theIndex, const T& theElement); void insert_back(const T& theElement); void output(std::ostream& out) const;private: void checkIndex(int theIndex) const; chainNode *firstNode, *lastNode; int listSize;};template chain ::chain() :listSize(0), firstNode(NULL), lastNode(NULL){}//复制构造函数template chain ::chain(const chain & theList){ this->listSize = theList.listSize; //链表为空 if (listSize == 0) { firstNode = lastNode = NULL; return; } //链表非空 //复制首元素 chainNode * sourceNode = theList.firstNode; firstNode = new chainNode (sourceNode->element); sourceNode = sourceNode->next; chainNode * targetNode = firstNode; //复制剩余元素 while (sourceNode != NULL) { targetNode->next = new chainNode (sourceNode->element); targetNode = targetNode->next; sourceNode = sourceNode->next; } targetNode->next = NULL; lastNode = targetNode;}//链表析构函数，删除链表所有节点template chain ::~chain() { while (firstNode != NULL) { chainNode * nextNode = firstNode->next; delete firstNode; firstNode = nextNode; }}//确定索引theIndex在0和listSize-1之间template void chain ::checkIndex(int theIndex) const{ if (theIndex < 0 || theIndex >= listSize) { throw illegalIndex("theIndex out of range"); }}//return an element of theIndex//if not exists, throw exceptiontemplate T& chain ::get(int theIndex) const{ checkIndex(theIndex); chainNode * currentNode = firstNode; for (int i = 0; i < theIndex; ++i) { currentNode = currentNode->next; } return currentNode->element;}//return index of the element that first appeared//if element not exist,return -1template int chain ::indexOf(const T& theElement) const{ chainNode * currentNode = firstNode; int index = 0; while (currentNode != NULL && currentNode->element != theElement) { currentNode = currentNode->next; index++; } if (currentNode == NULL) { return -1; } else { return index; }}//删除索引为theIndex的元素//若不存在，则抛出异常template void chain ::erase(int theIndex){ checkIndex(theIndex); chainNode * deleteNode; if (theIndex == 0) { deleteNode = firstNode; firstNode = firstNode->next; } else { //用p指向要删除节点的前驱节点 chainNode * p = firstNode; for (int i = 0; i < theIndex - 1; ++i) { p = p->next; } deleteNode = p->next; p->next = p->next->next; if (theIndex == (listSize - 1)) { lastNode = p; } } listSize--; delete deleteNode;}//删除所有的节点template void chain ::clear(){ while (firstNode != NULL) { chainNode * nextNode = firstNode->next; delete firstNode; firstNode = nextNode; } lastNode = firstNode; listSize = 0;}//在索引为TheIndex的位置上插入元素TheElementtemplate void chain ::insert(int theIndex, const T& theElement){ //索引无效 if (theIndex < 0 || theIndex > listSize) { ostringstream s; s << "error: list size = " << listSize; throw illegalIndex(s.str()); } if (theIndex == 0) { firstNode = new chainNode (theElement, firstNode); lastNode = firstNode; } else { //寻找新元素前驱 chainNode * p = firstNode; for (int i = 0; i < theIndex - 1; ++i) { p = p->next; } p->next = new chainNode (theElement, p->next); if (theIndex == listSize) { lastNode = p->next; } else { } } listSize++;}//在链表末尾插入元素为TheElement的节点template void chain ::insert_back(const T& theElement){ chainNode * newNode = new chainNode (theElement, NULL); if (firstNode == NULL) { firstNode = lastNode = newNode; } else { lastNode->next = newNode; lastNode = newNode; } listSize++;}//把链表放入输入流template void chain ::output(std::ostream& out) const{ for (chainNode * currentNode = firstNode; currentNode != NULL; currentNode = currentNode->next) { out << currentNode->element << " "; }}//重载< std::ostream& operator<< (std::ostream& out, const chain & x){ x.output(out); return out;}
线性表的抽象类：
//linearList.h//-线性表的抽象类#pragma once#includetemplate class linearList {public: //return ture, only if the linear list is empty virtual bool empty() const = 0; //return the numbers of element of linear list virtual int size() const = 0; //return an element of index for theIndex virtual T& get(int theIndex) const = 0; //return an index of the theElement for first appearence positon virtual int indexOf(const T& theElement) const = 0; //delete an element of index for theIndex virtual void erase(int theIndex) = 0; //delete all node of a list virtual void clear() = 0; //insert theElement into position for index is theIndex in the linear list virtual void insert(int theIndex, const T& theElement) = 0; //insert the linearlist into the ostream out virtual void output(std::ostream& out) const = 0;};
异常处理：
//illegalIndex.hpp//-索引异常类#pragma once#include#include class illegalIndex{public: illegalIndex() { std::cerr << "illegal index value" << std::endl; } illegalIndex(std::string theMessage) { std::cerr << theMessage << std::endl; }};
带头节点的循环链表