更新时间:2022-08-21 15:57:20
使用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;
}
运行结果: