使用C++封装一个链表类LinkList。写出相应一个测试用例
链表需要提供
添加
修改删除
除重
合并 排序创建
销毁等接口。
不能调用库函数或者使用STL等类库
题目延伸***********逆置链表**********
|
LinkNode.h |
|
#ifndef #define #include class { public: int LinkNode* }; #endif |
|
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::LinkList() { //init this->m_head this->m_tail std::cout } /** * */ LinkList::~LinkList() { std::cout } /** * * * */ void { //先查找到第一次出现value的位置 LinkNode LinkNode* pNewNode->m_idata pNewNode->m_pnext if(pNode { this->m_head->m_pnext this->m_tail } else { //新建一个节点 pNewNode->m_pnext pNode->m_pnext } } /** * * */ void { //1.创建一个新的LinkNode节点 LinkNode pNode->m_idata pNode->m_pnext //判断链表是否为空 if(this->m_head { this->m_head this->m_tail } else { pNode->m_pnext this->m_head } } /** * * */ void { //1.创建一个新的LinkNode节点pNode LinkNode pNode->m_idata pNode->m_pnext //2.判断链表是否为空 if(this->m_head { this->m_head //m_tail表示最后一个节点 this->m_tail } else { //尾部节点的下一个节点是新创建的这个节点 this->m_tail->m_pnext this->m_tail } } /** * * * */ void { if(!flag) { //升序 for(LinkNode* { for(LinkNode { if(p1->m_idata { LinkNode pNode.m_idata p1->m_idata //交换数据 p2->m_idata } } } } else { //降序 for(LinkNode { for(LinkNode { if(p1->m_idata { LinkNode pNode.m_idata p1->m_idata p2->m_idata } } } } } /** * * */ void { //找到要删除的节点 LinkNode* //如果没有找到要删除节点，则直接返回 if(pNode { return; } else { if(pNode { this->m_head delete pNode return } //遍历链表 LinkNode* while(pTemp->m_pnext { //如果这个节点的下一个节点恰好是要删除的节点 if(pTemp->m_pnext { pTemp->m_pnext //删除节点 delete pNode break; } //这个临时的节点向下移动 pTemp } //如果是最后一个节点 if(pTemp { pTemp->m_pnext delete pNode return } } } /** * */ void { //判断头节点是否也是空，如果也是空，则返回 if(this->m_head { return; } else { //1.定义一个临时的节点 LinkNode //2.循环，直到最后一个节点 while(pTemp->m_pnext { //输出参数值 std::cout //将临时节点指针向后移 pTemp } std::cout } } /** * * * */ LinkNode { //1.的，如果是则肯定没有，直接返回NULL if(index { std::cout return } else { //判断链表是否是空的，如果是空的，输出结果提示结果然后返回 if(this->m_head { std::cout return } else { LinkNode int while { //当进来了之后先判断，如果查的标记刚好是这个，则直接返回 if(index { return } pTemp // _tempIndex++; } //这里表示恰好这个是最后一个节点 if(index { return } else { std::cout return } } } } /** * * * */ LinkNode* { //判断头节点是否为空，如果为空，则直接返回 if(this->m_head { return } else { //定义一个临时的节点 LinkNode //循环遍历链表，直到最后一个节点 while(pTemp->m_pnext { // if(pTemp->m_idata { return } else { //指针向后移动 pTemp } } //判断最后一个节点的值是否和要查找的值相等 if(pTemp->m_idata { return } } } /** * * * */ void { LinkNode //如果是空，表示没有找到要修改的值 if(pNode { return; } else { pNode->m_idata } } |
#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; } |
运行结果： |