使用C++封装一个链表类LinkList。写出相应一个测试用例
链表需要提供 添加 修改删除 除重 合并 排序创建 销毁等接口。
不能调用库函数或者使用STL等类库
题目延伸***********逆置链表**********
| LinkNode.h |
| #ifndef LINKNODE_H #define LINKNODE_H #include <iostream>
class LinkNode { public: int m_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"
/** * @brief LinkList::LinkList */ LinkList::LinkList() { //init m_head and m_tail this->m_head = NULL; this->m_tail = NULL; std::cout << "LinkNode constructor" << std::endl; }
/** * @brief LinkList::~LinkList */ LinkList::~LinkList() { std::cout << "~LinkNode" << std::endl; }
/** * @brief LinkList::ListInsertIndex,这里方法默认是在节点的后面插入参数 * @param value 要插入的值 * @return 返回开始节点 */ void LinkList::ListInsertIndex(int index,int value) { //先查找到第一次出现value的位置 LinkNode *pNode = this->ListFindIndex(index); LinkNode* pNewNode = new LinkNode; 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; } }
/** * @brief LinkList::ListInsertHead 前插数据 * @param value插入的值 */ void LinkList::ListInsertHead(int value) { //1.创建一个新的LinkNode节点 LinkNode *pNode = new LinkNode(); 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; } }
/** * @brief LinkList::ListInsertTail 尾部插入值 * @param value 要插入的值 */ void LinkList::ListInsertTail(int value) { //1.创建一个新的LinkNode节点pNode LinkNode *pNode = new LinkNode(); 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; } }
/** * @brief LinkList::ListSort 对链表进行排序 * @param flag 当表示true的时候降序，当false的时候升序 * @return */ void LinkList::ListSort(bool flag) { 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) { LinkNode pNode; 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) { LinkNode pNode; pNode.m_idata = p1->m_idata; p1->m_idata = p2->m_idata; p2->m_idata = pNode.m_idata; } } } } }
/** * @brief LinkList::ListRemove 删除指定的元素 * @param index 要删除的节点 */ void LinkList::ListRemove(int index) { //找到要删除的节点 LinkNode* pNode = this->ListFindIndex(index);
//如果没有找到要删除节点，则直接返回 if(pNode == NULL) { return; } else { if(pNode == this->m_head) { this->m_head = this->m_head->m_pnext; delete pNode; pNode = NULL; return ; } //遍历链表 LinkNode* pTemp = this->m_head; while(pTemp->m_pnext != NULL) { //如果这个节点的下一个节点恰好是要删除的节点 if(pTemp->m_pnext == pNode) { pTemp->m_pnext = pNode->m_pnext; //删除节点 delete pNode; pNode = NULL; break; } //这个临时的节点向下移动 pTemp = pTemp->m_pnext; }
//如果是最后一个节点 if(pTemp == pNode) { pTemp->m_pnext = pNode->m_pnext; delete pNode; pNode = NULL; return ; } } }
/** * @brief LinkList::ListShow 遍历链表 */ void LinkList::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; } }
/** * @brief ListFindIndex 查找第index个元素的值 * @param index 这里的index表示第index这个元素 * @return 返回第index个元素的地址 */ LinkNode * LinkList::ListFindIndex(int index) { //1.判断index是否是小于0的，如果是则肯定没有，直接返回NULL if(index <= 0) { std::cout << "index is out of range" << std::endl; return NULL; } else { //判断链表是否是空的，如果是空的，输出结果提示结果然后返回 if(this->m_head == NULL) { std::cout << "The lenght of LinkList is zero!!" << std::cout << std::endl; return NULL; } else { LinkNode *pTemp = this->m_head; int _tempIndex = 1; while (pTemp->m_pnext != NULL) { //当进来了之后先判断，如果查的标记刚好是这个，则直接返回 if(index == _tempIndex) { return pTemp; } pTemp = pTemp->m_pnext; //临时计数加1 _tempIndex++; } //这里表示恰好这个是最后一个节点 if(index == _tempIndex) { return pTemp; } else { std::cout << "index is out of range!!" << endl; return NULL; } } } }
/** * @brief LinkList::ListFindValue * @param value 要查找的值 * @return 要查找的值地址 */ LinkNode* LinkList::ListFindValue(int value) { //判断头节点是否为空，如果为空，则直接返回 if(this->m_head == NULL) { return NULL; } else { //定义一个临时的节点 LinkNode *pTemp = this->m_head;
//循环遍历链表，直到最后一个节点 while(pTemp->m_pnext != NULL) { // 判断要查找的值和当前值是否相等，如果相等直接返回 if(pTemp->m_idata == value) { return pTemp; } else { //指针向后移动 pTemp = pTemp->m_pnext; } }
//判断最后一个节点的值是否和要查找的值相等 if(pTemp->m_idata == value) { return pTemp; } } }
/** * @brief LinkList::ListUpdate * @param index 要更改的值 * @param value */ void LinkList::ListUpdate(int index, int value) { 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; } |
运行结果： |
