1.使用C++封装一个链表类LinkList



使用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.的，如果是则肯定没有，直接返回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; // _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;       //的节点的地址     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; }

运行结果：