1.使用C++封装一个链表类LinkList
使用C++封裝一個鏈表類LinkList。寫出相應(yīng)一個測試用例
鏈表需要提供 添加 修改刪除 除重 合并 排序創(chuàng)建 銷毀等接口。
不能調(diào)用庫函數(shù)或者使用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: ??? //作為頭節(jié)點 ??? LinkNode *m_head; ??? //作為尾節(jié)點 ??? 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); ??? //查找第一個出現(xiàn)指定值的節(jié)點的地址 ??? 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,這里方法默認(rèn)是在節(jié)點的后面插入?yún)?shù) ?* @param value 要插入的值 ?* @return 返回開始節(jié)點 ?*/ void LinkList::ListInsertIndex(int index,int value) { ??? //先查找到第一次出現(xiàn)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 ??? { ??????? //新建一個節(jié)點 ??????? pNewNode->m_pnext = pNode->m_pnext; ??????? pNode->m_pnext = pNewNode; ??? } } ? /** ?* @brief LinkList::ListInsertHead 前插數(shù)據(jù) ?* @param value插入的值 ?*/ void LinkList::ListInsertHead(int value) { ??? //1.創(chuàng)建一個新的LinkNode節(jié)點 ??? 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.創(chuàng)建一個新的LinkNode節(jié)點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表示最后一個節(jié)點 ??????? this->m_tail = pNode; ??? } ??? else ??? { ??????? //尾部節(jié)點的下一個節(jié)點是新創(chuàng)建的這個節(jié)點 ??????? this->m_tail->m_pnext = pNode; ??????? this->m_tail = this->m_tail->m_pnext; ??? } } ? /** ?* @brief LinkList::ListSort 對鏈表進行排序 ?* @param flag 當(dāng)表示true的時候降序，當(dāng)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; ??????????????????? //交換數(shù)據(jù) ??????????????????? 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 要刪除的節(jié)點 ?*/ void LinkList::ListRemove(int index) { ??? //找到要刪除的節(jié)點 ??? LinkNode* pNode = this->ListFindIndex(index); ? ??? //如果沒有找到要刪除節(jié)點，則直接返回 ??? 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) ??????? { ??????????? //如果這個節(jié)點的下一個節(jié)點恰好是要刪除的節(jié)點 ? ??????????if(pTemp->m_pnext == pNode) ??????????? { ??????????????? pTemp->m_pnext = pNode->m_pnext; ??????????????? //刪除節(jié)點 ??????????????? delete pNode; ??????????????? pNode = NULL; ??????????????? break; ??????????? } ??????????? //這個臨時的節(jié)點向下移動 ???????? ???pTemp = pTemp->m_pnext; ??????? } ? ??????? //如果是最后一個節(jié)點 ??????? if(pTemp == pNode) ??????? { ???????????? pTemp->m_pnext = pNode->m_pnext; ???????????? delete pNode; ???????????? pNode = NULL; ???????????? return ; ??????? } ??? } } ? /** ?* @brief LinkList::ListShow 遍歷鏈表 ?*/ void LinkList::ListShow() { ??? //判斷頭節(jié)點是否也是空，如果也是空，則返回 ??? if(this->m_head == NULL) ??? { ??????? return; ??? } ??? else ??? { ??????? //1.定義一個臨時的節(jié)點 ??????? LinkNode *pTemp = this->m_head; ? ??????? //2.循環(huán)，直到最后一個節(jié)點 ??????? while(pTemp->m_pnext != NULL) ??????? { ??????????? //輸出參數(shù)值 ??????????? std::cout << pTemp->m_idata << "? "; ??????????? //將臨時節(jié)點指針向后移 ??????????? 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 ??? { ??????? //判斷鏈表是否是空的，如果是空的，輸出結(jié)果提示結(jié)果然后返回 ??????? 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) ??????????? { ??????????????? //當(dāng)進來了之后先判斷，如果查的標(biāo)記剛好是這個，則直接返回 ??????????????? if(index == _tempIndex) ??????????????? { ??????????????????? return pTemp; ??????????????? } ??????????????? pTemp = pTemp->m_pnext; ??????????????? //臨時計數(shù)加1 ??????????????? _tempIndex++; ??????????? } ??????????? //這里表示恰好這個是最后一個節(jié)點 ??????????? 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) { ??? //判斷頭節(jié)點是否為空，如果為空，則直接返回 ??? if(this->m_head == NULL) ??? { ??????? return NULL; ??? } ??? else ??? { ??????? //定義一個臨時的節(jié)點 ??????? LinkNode *pTemp = this->m_head; ? ??????? //循環(huán)遍歷鏈表，直到最后一個節(jié)點 ???? ???while(pTemp->m_pnext != NULL) ??????? { ??????????? // 判斷要查找的值和當(dāng)前值是否相等，如果相等直接返回 ??????????? if(pTemp->m_idata == value) ??????????? { ??????????????? return pTemp; ??????????? } ??????????? else ??????????? { ??????????????? //指針向后移動 ??????????????? pTemp = pTemp->m_pnext; ??????????? } ??????? } ? ??????? //判斷最后一個節(jié)點的值是否和要查找的值相等 ??????? 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; ? ??? //查找節(jié)點值為34的節(jié)點的地址 ??? 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; } |
| 運行結(jié)果： |
?
與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖總結(jié)
以上是生活随笔為你收集整理的1.使用C++封装一个链表类LinkList的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 生活常识：如何正确使用电烤鸡架？
- 下一篇： 梭子蟹死了能不能吃了,梭子蟹怎么保存？