《2022年2022年链表类 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年链表类 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 链表类/Node.h #ifndef NODE_H #define NODE_H /结点类模板的定义template class Node private: Node* next; public: T data; Node(const T &data,Node *next=0); void insertAfter(Node *p); Node* deleteAfter(); Node* nextNode(); const Node* nextNode() const; ; /结点类模板的实现部分/构造函数template Node:Node(const T&data,Node*next):
2、data(data),next(next) /返回后继结点的指针template Node* Node:nextNode() return next; /返回后继结点的指针template const Node* Node:nextNode()const return next; /在当前结点之后插入一个结点p template void Node:insertAfter(Node*p) p-next=next; next=p; /删除当前结点的后继结点，并返回其地址template Node* Node:deleteAfter() 名师资料总结 - - -精品资料欢迎下载 - - - - -
3、 - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 2 Node* tempPtr=next; if(next=0) return 0; next=tempPtr-next; return tempPtr; #endif /LinkedList.h #ifndef LINKEDLIST_H #define LINKEDLIST_H #include Node.h template class LinkedList private: Node*front,*rear;/表头和表尾指针Node
4、*prevPtr,*currPtr;/记录表当前遍历位置的指针，由插入和删除操作更新int size; /表中元素的个数int position;/ 当前元素在表中的位置序号。由函数reset 使用/生成新结点，数据域为item，指针域为ptrNext; Node* newNode(const T &item,Node* ptrNext=NULL); /释放结点void freeNode(Node*p); /将链表 L 复制到当前辈 (假设当前表位空) /被复制构造函数和“operator=”调用void copy(const LinkedList&L); public: LinkedList
5、(); LinkedList(const LinkedList&L); LinkedList(); int getSize() const;/ 返回链表中元素的个数bool isEmpty() const;/ 链表是否为空void reset(int pos=0);/ 初始化游标的位置void next(); /使游标移动到下一个结点bool endOfList()const;/ 游标是否到了链尾int currentPosition(void) const;/ 返回游标的当前位置void insertFront(const T&item);/在表头插入结点void insertRear(co
6、nst T& item);/ 在表尾插入结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 3 void insertAt(const T& item);/在当前结点之前插入结点void insertAfter(const T& item);/在当前结点之后插入结点void deleteFront();/ 删除头结点void deleteCurrent(); /删除当前结点T& data();/ 返回对当前结点数据成员的引用c
7、onst T&data()const;/ 返回对当前结点数据成员的常引用/清空链表：释放所有结点的内存空间。被析构函数和operator= 调用void clear(); ; /私有成员函数的实现template Node* LinkedList:newNode(const T&item,Node* ptrNext) return (new Node(item,ptrNext); template void LinkedList:freeNode(Node *p) delete p; /公有成员函数的实现/无参构造函数的实现template LinkedList:LinkedList() fr
8、ont=NULL; rear=NULL; prevPtr=front; currPtr=front; size=0; position=0; /复制构造函数的实现template LinkedList:LinkedList(const LinkedList& L) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 4 front=NULL; rear=NULL; prevPtr=NULL; currPtr=NULL; Node*
9、tempcurr=L.currPtr; while(tempcurr!=NULL) Node *temPtr=new Node(tempcurr-data); if(front=NULL) front=temPtr; rear=temPtr; prevPtr=front; currPtr=front; else prevPtr=currPtr; (*currPtr).insertAfter(temPtr); currPtr=temPtr; tempcurr=(*tempcurr).nextNode(); /析构函数的实现template LinkedList:LinkedList() clea
10、r(); /返回链表中元素的个数template int LinkedList:getSize() const return size; /判断链表是否为空template bool LinkedList:isEmpty() const if(front=NULL&rear=NULL) return true; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 5 else return false; /初始化游标的位置temp
11、late void LinkedList:reset(int pos) currPtr=front; prevPtr=front; /position=0; /使游标移动到下一个结点template void LinkedList:next() prevPtr=currPtr; currPtr=(*currPtr).nextNode(); /判断游标是否到了链尾template bool LinkedList:endOfList() const if(currPtr=NULL) return true; else return false; /返回游标当前的位置template int Lin
12、kedList:currentPosition() const return position; /在表头插入结点template void LinkedList:insertFront(const T &item) Node *temPtr=new Node(item,front); if(rear=NULL) front=temPtr; rear=temPtr; currPtr=front; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - -
13、 - - - - 6 prevPtr=front; else front=temPtr; currPtr=front; prevPtr=front; size+; position+; /在表尾插入结点template void LinkedList:insertRear(const T &item) Node *temPtr=new Node(item); if(front=NULL) front=temPtr; rear=temPtr; prevPtr=front; currPtr=front; else prevPtr=currPtr; (*currPtr).insertAfter(te
14、mPtr); currPtr=temPtr; size+; /在当前结点之前插入结点template void LinkedList:insertAt(const T& item) Node *temPtr=new Node(item); if(front=NULL) front=temPtr; rear=temPtr; prevPtr=front; currPtr=front; size+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - -
15、- - - - 7 else (*prevPtr).insertAfter(temPtr); currPtr=temPtr; size+; /在当前结点之后插入结点template void LinkedList:insertAfter(const T& item) Node *temPtr=new Node(item); if(front=NULL) front=temPtr; rear=temPtr; prevPtr=front; currPtr=front; size+; else if(currPtr=NULL) (*prevPtr).insertAfter(temPtr); size
16、+; prevPtr=prevPtr-nextNode(); currPtr=NULL; else (*currPtr).insertAfter(temPtr); currPtr=temPtr; size+; position+; /删除头结点template void LinkedList:deleteFront() Node* temPtr=front; front=(*front).nextNode(); prevPtr=front; currPtr=front; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整
17、理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 8 size-; freeNode(temPtr); /删除当前结点template void LinkedList:deleteCurrent() if(currPtr=front) deleteFront(); else currPtr=prevPtr; size-; freeNode(prevPtr-deleteAfter(); /返回对当前结点数据成员的引用template T& LinkedList:data() return currPtr-data; /返回对当前结点数据成员的常引用te
18、mplate const T& LinkedList:data() const return currPtr-data; /清空链表：释放所有结点的内存空间。被析构函数和operator= 调用template void LinkedList:clear() currPtr=front; Node* temPtr=currPtr; while(currPtr!=NULL) currPtr=(*currPtr).nextNode(); freeNode(temPtr); temPtr=currPtr; #endif 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
19、 - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 9 /9.7.cpp #include #include LinkedList.h using namespace std; int main() LinkedList list; /输入 10 个整数依次向表头插入for(int i=0;iitem; list.insertFront(item); /输出链表coutList ; list.reset(); while(!list.endOfList() coutlist.data() ; list.nex
20、t(); coutendl; /输入要删除的整数int key; coutkey; /查找并删除结点list.reset(); while(!list.endOfList() if(list.data()=key) list.deleteCurrent(); list.next(); /输出链表coutList: ; list.reset(); /输出各结点数据，直到链表尾while(!list.endOfList() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 10 coutlist.data() ; list.next(); coutendl; return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -