C++语言实现线性表之链表实例
作者:司青 时间:2023-06-20 22:21:20
本文实例讲述了C++语言实现线性表之链表实现方法。分享给大家供大家参考。具体分析如下:
插入、删除结点的代码有点多,但这样提高了代码的可读性,且不增加时间复杂度,不会影响程序性能
#include <iostream>
using namespace std;
template<typename T>
class CList;
template<class T>
class Node
{
friend CList<T>;
private:
T m_data;
Node *m_pNext;
};
template<class T>
class CList
{
public:
CList();
~CList();
bool IsEmpty();
void Append(const T &data);
void Delete(const int &pos);
void Print();
int GetLength();
T Find(const int &pos);
void Insert(const int &pos,const T &data);
private:
Node<T> *m_pHead;
Node<T> *m_pEnd;
int m_len;
void Create();
void Destroy();
};
//为头结点分配空间
template<class T>
void CList<T>::Create()
{
m_pHead = new Node<T>;
m_pEnd = new Node<T>;
m_pHead->m_pNext = NULL;
m_pEnd->m_pNext = m_pHead->m_pNext;
m_len = 0;
}
template<class T>
CList<T>::CList()
{
Create();
}
//删除所有结点
template<class T>
void CList<T>::Destroy()
{
Node<T> *pF = m_pHead->m_pNext;
Node<T> *pT;
while(pF)
{
pT = pF;
pF = pF->m_pNext;
delete pT;
}
}
template<class T>
CList<T>::~CList()
{
Destroy();
}
//判断是否为空
template<class T>
bool CList<T>::IsEmpty()
{
if(!m_pHead->m_pNext)
{
return true;
}
else
{
return false;
}
}
//从表的最后加入一个元素
template<class T>
void CList<T>::Append(const T &data)
{
Node<T> *pT = new Node<T>;
pT->m_data = data;
pT->m_pNext = NULL;
if(!m_pHead->m_pNext)
{
m_pHead->m_pNext = pT;
}
else
{
(m_pEnd->m_pNext)->m_pNext = pT;
}
m_pEnd->m_pNext = pT;
++m_len;
}
//删除一个元素
template<class T>
void CList<T>::Delete(const int &pos)
{
if(pos < 0 || pos < m_len)
{
cout<<"位置不合法"<<endl;
return;
}
Node<T> *pPre = NULL;//存放前一个结点
Node<T> *pBehind = NULL;//存放后一个结点
Node<T> *pT = m_pHead->m_pNext;//目标结点
int ix = -1;
while(pT)
{
++ix;
if(ix == pos - 1 - 1)
{
pPre = pT;
}
else if(ix == pos - 1)
{
pBehind = pT->m_pNext;
break;
}
pT = pT->m_pNext;
}
if(!pPre)//如果指针为空则说明pos是指第一个元素
{
delete pT;
m_pHead->m_pNext = pBehind;
--m_len;
return;
}
if(!pBehind)//如果指针为空则说明pos是指最后一个元素
{
m_pEnd = pPre;
delete pT;
}
pPre->m_pNext = pBehind;
--m_len;
}
//输出所有数据
template<class T>
void CList<T>::Print()
{
Node<T> *pT = m_pHead->m_pNext;
while(pT)
{
cout<<pT->m_data<<",";
pT = pT->m_pNext;
}
cout<<endl;
}
template<class T>
int CList<T>::GetLength()
{
return m_len;
}
//查找数据
template<class T>
T CList<T>::Find(const int &pos)
{
if(pos <= 0)
{
cout<<"输入不合法"<<endl;
return NULL;
}
if(pos > m_len)
{
cout<<"超出表长"<<endl;
return NULL;
}
int i = 0;
Node<T> *pT = m_pHead->m_pNext;
while(pT)
{
++i;
if(i == pos)
{
return pT->m_data;
}
pT = pT->m_pNext;
}
return NULL;
}
template<class T>
void CList<T>::Insert(const int &pos,const T &data)
{
if(pos <= 0 || pos >m_len)
{
cout<<"输入不合法"<<endl;
return;
}
int i = 0;
Node<T> *pT = m_pHead->m_pNext;
Node<T> *pPre = NULL;
Node<T> *pBehind = NULL;
while(pT)
{
++i;
if(i == pos - 1)
{
pPre = pT;
}
if(i == pos)
{
pBehind = pT->m_pNext;
break;
}
pT = pT->m_pNext;
}
Node<T> *pNew = new Node<T>;
pNew->m_data = data;
if(!pPre)//如果指针为空则说明pos是指第一个元素
{
pNew->m_pNext = m_pHead->m_pNext;
m_pHead->m_pNext = pNew;
++m_len;
return;
}
if(!pBehind)//如果指针为空则说明pos是指最后一个元素
{
m_pEnd->m_pNext = pNew;
}
pPre->m_pNext = pNew;
pNew->m_pNext = pT;
++m_len;
}
希望本文所述对大家的C++程序设计有所帮助。
标签:C++,线性表,链表
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Android自定义View实现开关按钮
2021-09-08 08:53:22
![](https://img.aspxhome.com/file/2023/7/138347_0s.gif)
C#使用Socket实现局域网聊天
2021-07-20 02:13:20
![](https://img.aspxhome.com/file/2023/7/119467_0s.jpg)
C# SynchronizationContext以及Send和Post使用解读
2023-10-16 04:27:28
编写Java代码制造一个内存溢出的情况
2022-11-13 07:58:12
Java高级架构之FastDFS分布式文件集群详解
2023-07-23 14:57:50
![](https://img.aspxhome.com/file/2023/0/114060_0s.png)
android仿iphone主题效果的主菜单
2023-04-29 03:56:35
![](https://img.aspxhome.com/file/2023/0/138760_0s.jpg)
Spring Cloud Stream消息驱动组件使用方法介绍
2022-05-30 04:30:52
![](https://img.aspxhome.com/file/2023/2/127222_0s.png)
浅谈JAVA中输入输出流实例详解
2022-10-21 05:20:57
![](https://img.aspxhome.com/file/2023/1/81881_0s.png)
Spring整合SpringMVC与Mybatis(SSM)实现完整登录功能流程详解
2022-07-15 10:19:25
![](https://img.aspxhome.com/file/2023/2/80842_0s.gif)
Java Collection集合的三种遍历方式详解
2023-04-29 08:11:40
Android Studio 3.5版本JNI生成SO文件详解
2022-06-11 19:34:11
![](https://img.aspxhome.com/file/2023/0/137910_0s.png)
javamail 发送邮件的实例代码分享
2021-12-22 15:10:47
Mybatis参数传递示例代码
2023-05-20 09:43:08
android短信管理器SmsManager实例详解
2021-09-03 18:17:18
Android制作漂亮自适布局键盘的方法
2022-08-04 09:14:53
![](https://img.aspxhome.com/file/2023/3/137933_0s.png)
java8 Stream大数据量List分批处理切割方式
2023-02-10 22:34:36
简略分析Android的Retrofit应用开发框架源码
2023-09-17 22:12:30
![](https://img.aspxhome.com/file/2023/4/93304_0s.png)
SpringBoot2.x 集成 Thymeleaf的详细教程
2021-07-31 18:18:23
![](https://img.aspxhome.com/file/2023/1/114041_0s.png)
java 验证用户是否已经登录与实现自动登录方法详解
2021-10-21 13:49:50
Android中fragment与activity之间的交互(两种实现方式)
2021-06-23 13:11:31
![](https://img.aspxhome.com/file/2023/3/139263_0s.gif)