首页 > 代码库 > 1.使用C++封装一个链表类LinkList
1.使用C++封装一个链表类LinkList
使用C++封装一个链表类LinkList。写出相应一个测试用例
链表需要提供添加 修改删除除重 合并 排序创建销毁等接口。
不能调用库函数或者使用STL等类库
题目延伸***********逆置链表**********
LinkNode.h |
#ifndefLINKNODE_H #defineLINKNODE_H #include<iostream>
classLinkNode { public: intm_idata; LinkNode*m_pnext; };
#endif//LINKNODE_H |
LinkList.h |
#ifndef LINKLIST_H#define LINKLIST_H#include <iostream>#include "LinkNode.h" using namespace std; class LinkList{public: //作为头节点 LinkNode *m_head; //作为尾节点 LinkNode *m_tail;public: LinkList(); ~LinkList(); void ListInsertIndex(int index,int value); //前插 void ListInsertHead(int value); //尾插 void ListInsertTail(int value);// int ListMerge(LinkList &srclist); //对链表进行排序 void ListSort(bool flag); void ListRemove(int index); //显示所有 void ListShow(); LinkNode * ListFindIndex(int index); //查找第一个出现指定值的节点的地址 LinkNode * ListFindValue(int value); void ListUpdate(int index,int value); //void ListRemoveSame();}; #endif // LINKLIST_H |
LinkList.cpp |
#include"LinkList.h"
/** *@briefLinkList::LinkList */ LinkList::LinkList() { //initm_headandm_tail this->m_head=NULL; this->m_tail=NULL; std::cout<< "LinkNodeconstructor" << std::endl; }
/** *@briefLinkList::~LinkList */ LinkList::~LinkList() { std::cout<< "~LinkNode"<< std::endl; }
/** *@briefLinkList::ListInsertIndex,这里方法默认是在节点的后面插入参数 *@paramvalue要插入的值 *@return返回开始节点 */ voidLinkList::ListInsertIndex(intindex,intvalue) { //先查找到第一次出现value的位置 LinkNode*pNode=this->ListFindIndex(index); LinkNode*pNewNode=newLinkNode; pNewNode->m_idata=value; pNewNode->m_pnext=NULL;
if(pNode==this->m_head) { this->m_head->m_pnext=pNewNode; this->m_tail=pNewNode; } else { //新建一个节点 pNewNode->m_pnext=pNode->m_pnext; pNode->m_pnext=pNewNode; } }
/** *@briefLinkList::ListInsertHead前插数据 *@paramvalue插入的值 */ voidLinkList::ListInsertHead(intvalue) { //1.创建一个新的LinkNode节点 LinkNode*pNode=newLinkNode(); pNode->m_idata=value; pNode->m_pnext=NULL;
//判断链表是否为空 if(this->m_head==NULL&&this->m_tail==NULL) { this->m_head=pNode; this->m_tail=pNode; } else { pNode->m_pnext=this->m_head; this->m_head=pNode; } }
/** *@briefLinkList::ListInsertTail尾部插入值 *@paramvalue要插入的值 */ voidLinkList::ListInsertTail(intvalue) { //1.创建一个新的LinkNode节点pNode LinkNode*pNode=newLinkNode(); pNode->m_idata=value; pNode->m_pnext=NULL;
//2.判断链表是否为空 if(this->m_head==NULL&&this->m_tail==NULL) { this->m_head=pNode; //m_tail表示最后一个节点 this->m_tail=pNode; } else { //尾部节点的下一个节点是新创建的这个节点 this->m_tail->m_pnext=pNode; this->m_tail=this->m_tail->m_pnext; } }
/** *@briefLinkList::ListSort对链表进行排序 *@paramflag当表示true的时候降序，当false的时候升序 *@return */ voidLinkList::ListSort(boolflag) { if(!flag) { //升序 for(LinkNode*p1=this->m_head;p1!=NULL;p1=p1->m_pnext) { for(LinkNode*p2=this->m_head;p2!=NULL;p2=p2->m_pnext) { if(p1->m_idata>p2->m_idata) { LinkNodepNode; pNode.m_idata=p1->m_idata; p1->m_idata=p2->m_idata; //交换数据 p2->m_idata=pNode.m_idata; } } } } else { //降序 for(LinkNode*p1=this->m_head;p1!=NULL;p1=p1->m_pnext) { for(LinkNode*p2=this->m_head;p2!=NULL;p2=p2->m_pnext) { if(p1->m_idata<p2->m_idata) { LinkNodepNode; pNode.m_idata=p1->m_idata; p1->m_idata=p2->m_idata; p2->m_idata=pNode.m_idata; } } } } }
/** *@briefLinkList::ListRemove删除指定的元素 *@paramindex要删除的节点 */ voidLinkList::ListRemove(intindex) { //找到要删除的节点 LinkNode*pNode=this->ListFindIndex(index);
//如果没有找到要删除节点，则直接返回 if(pNode==NULL) { return; } else { if(pNode==this->m_head) { this->m_head=this->m_head->m_pnext; deletepNode; pNode=NULL; return; } //遍历链表 LinkNode*pTemp=this->m_head; while(pTemp->m_pnext!=NULL) { //如果这个节点的下一个节点恰好是要删除的节点 if(pTemp->m_pnext==pNode) { pTemp->m_pnext=pNode->m_pnext; //删除节点 deletepNode; pNode=NULL; break; } //这个临时的节点向下移动 pTemp=pTemp->m_pnext; }
//如果是最后一个节点 if(pTemp==pNode) { pTemp->m_pnext=pNode->m_pnext; deletepNode; pNode=NULL; return; } } }
/** *@briefLinkList::ListShow遍历链表 */ voidLinkList::ListShow() { //判断头节点是否也是空，如果也是空，则返回 if(this->m_head==NULL) { return; } else { //1.定义一个临时的节点 LinkNode*pTemp=this->m_head;
//2.循环，直到最后一个节点 while(pTemp->m_pnext!=NULL) { //输出参数值 std::cout<< pTemp->m_idata<< " "; //将临时节点指针向后移 pTemp=pTemp->m_pnext; } std::cout<< pTemp->m_idata<< std::endl; } }
/** *@briefListFindIndex查找第index个元素的值 *@paramindex这里的index表示第index这个元素 *@return返回第index个元素的地址 */ LinkNode*LinkList::ListFindIndex(intindex) { //1.判断index是否是小于0的，如果是则肯定没有，直接返回NULL if(index<=0) { std::cout<< "indexis outof range"<< std::endl; returnNULL; } else { //判断链表是否是空的，如果是空的，输出结果提示结果然后返回 if(this->m_head==NULL) { std::cout<< "Thelenght of LinkListis zero!!"<< std::cout<< std::endl; returnNULL; } else { LinkNode*pTemp=this->m_head; int_tempIndex=1; while(pTemp->m_pnext!=NULL) { //当进来了之后先判断，如果查的标记刚好是这个，则直接返回 if(index==_tempIndex) { returnpTemp; } pTemp=pTemp->m_pnext; //临时计数加1 _tempIndex++; } //这里表示恰好这个是最后一个节点 if(index==_tempIndex) { returnpTemp; } else { std::cout<< "indexis outof range!!"<< endl; returnNULL; } } } }
/** *@briefLinkList::ListFindValue *@paramvalue要查找的值 *@return要查找的值地址 */ LinkNode*LinkList::ListFindValue(intvalue) { //判断头节点是否为空，如果为空，则直接返回 if(this->m_head==NULL) { returnNULL; } else { //定义一个临时的节点 LinkNode*pTemp=this->m_head;
//循环遍历链表，直到最后一个节点 while(pTemp->m_pnext!=NULL) { //判断要查找的值和当前值是否相等，如果相等直接返回 if(pTemp->m_idata==value) { returnpTemp; } else { //指针向后移动 pTemp=pTemp->m_pnext; } }
//判断最后一个节点的值是否和要查找的值相等 if(pTemp->m_idata==value) { returnpTemp; } } }
/** *@briefLinkList::ListUpdate *@paramindex要更改的值 *@paramvalue */ voidLinkList::ListUpdate(intindex,intvalue) { LinkNode*pNode=this->ListFindIndex(index); //如果是空，表示没有找到要修改的值 if(pNode==NULL) { return; } else { pNode->m_idata=value; } } |
#include <iostream>#include "LinkList.h" using namespace std; int main(){ LinkList* linkList = new LinkList(); //向链表的尾部插入值 linkList->ListInsertTail(1); linkList->ListInsertTail(2); linkList->ListInsertTail(3); //向链表的头部插入值 linkList->ListInsertHead(34); linkList->ListInsertHead(105); linkList->ListInsertIndex(5,125); linkList->ListShow(); //显示链表中的值 linkList->ListShow(); std::cout << endl; //查找节点值为34的节点的地址 LinkNode* pTargetNode = linkList->ListFindValue(3); //显示出地址 printf("address = %p,data = %d \n",pTargetNode,*pTargetNode); linkList->ListShow(); LinkNode* pTargetNode2 = linkList->ListFindIndex(4); printf("pTargetNode2 address = %p,data = %d \n",pTargetNode2,*pTargetNode2); linkList->ListUpdate(1,30); linkList->ListShow(); linkList->ListUpdate(3,30); linkList->ListShow(); linkList->ListRemove(5); linkList->ListShow(); linkList->ListSort(false); linkList->ListShow(); return 0;} |
运行结果： |
1.使用C++封装一个链表类LinkList