C++语言实现线性表之链表实例
作者:司青 发布时间:2023-06-20 22:21:20
标签:C++,线性表,链表
本文实例讲述了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++程序设计有所帮助。


猜你喜欢
- 参考文献:https://www.jb51.net/article/232858.htm使用springboot 2 构建项目,调试代码的时
- CyclicBarrier线程同步java.util.concurrent.CyclicBarrier提供了一种多线程彼此等待的同步机制,可
- springboot默认读取的配置文件名字是:“application.properties”和&a
- springboot整合tkmapper1.导入pom依赖1.1 导入springboot的parent依赖<parent> &
- 前言之前写过 Mybatis Plus 的基本配置和使用。Mybatis-Plus 看这一篇就够了当初在进行查询时,虽然没有写硬SQL进行查
- java进行时间转换成unix timestamp的具体代码,供大家参考,具体内容如下import java.text.DateFormat
- Java的反射机制允许我们对一个类的加载、实例化、调用方法、操作属性的时期改为在运行期进行,这大大提高了代码的灵活度。但在运行期进行反射操作
- 实现Struts登录1、jar包拷贝首先是建立java web项目,之后打开我们我们下载好strtus框架,Struts-1.2.9-bin
- 这里在提供C#代码,将PPT转成PDF.直接上代码;要引入Microsoft.Office.Interop.PowerPoint; 版本12
- c语言关闭socket的两种方式一、shutdown()#include<sys/socket.h>int shutdown(i
- 使用java语言用集合存储数据实现学生信息管理系统,在控制台上编译执行可以实现基本的学生信息增加、删除、修改、查询功能IO版可以参考我的另外
- 邮件绑定功能【需求】1、 用户注册时,输入邮箱2、 通过Javamail技术,向用户邮箱发送一封祝贺邮件1、javamail发送邮件1.1、
- 一、环境准备:(根据自己电脑配置来选择安装版本,我的电脑是64位,所以此处选择64位安装)JDK下载:JDK 1.8下载地址: http:/
- 这篇文章主要介绍了MyBatis执行Sql的流程实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的
- 前言众所周知,RxJava2 中当链式调用中抛出异常时,如果没有对应的 Consumer 去处理异常,则这个异常会被抛出到虚拟机中去,And
- 本文实例为大家分享了Android实现毛玻璃效果弹出菜单动画的具体代码,供大家参考,具体内容如下仿ios上屏幕下方向上滑出来的一个模糊菜单,
- 补充使用Spring Cloud Config加密功能需要下载JCE扩展,用于生成无限长度的密文。链接:http://www.oracle.
- 首先我们应该清楚的是JDK1.6和JDK1.7中String类的intern方法还是有差别的: JDK1.6中的int
- centos下搭建GitLab+Jenkins持续集成环境,供大家参考,具体内容如下1、安装JDKyum install -y java2、
- 效果和代码都非常直观:实例1:TimePicker<RelativeLayout xmlns:android="http:/