这篇文章主要介绍了C++语言实现线性表之链表,实例分析了C++实现线性表中链表的原理与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下
本文实例讲述了C++语言实现线性表之链表实现方法。分享给大家供大家参考。具体分析如下：
插入、删除结点的代码有点多，但这样提高了代码的可读性，且不增加时间复杂度，不会影响程序性能
#include using namespace std; template class CList; template class Node { friend CList; private: T m_data; Node *m_pNext; }; template 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 *m_pHead; Node *m_pEnd; int m_len; void Create(); void Destroy(); }; //为头结点分配空间 template void CList::Create() { m_pHead = new Node; m_pEnd = new Node; m_pHead->m_pNext = NULL; m_pEnd->m_pNext = m_pHead->m_pNext; m_len = 0; } template CList::CList() { Create(); } //删除所有结点 template void CList::Destroy() { Node *pF = m_pHead->m_pNext; Node *pT; while(pF) { pT = pF; pF = pF->m_pNext; delete pT; } } template CList::~CList() { Destroy(); } //判断是否为空 template bool CList::IsEmpty() { if(!m_pHead->m_pNext) { return true; } else { return false; } } //从表的最后加入一个元素 template void CList::Append(const T &data) { Node *pT = new Node; 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 void CList::Delete(const int &pos) { if(pos <0 || pos < m_len) { cout<<"位置不合法"<<endl; return; } node *pPre = NULL;//存放前一个结点 Node *pBehind = NULL;//存放后一个结点 Node *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 void CList::Print() { Node *pT = m_pHead->m_pNext; while(pT) { cout<m_data<m_pNext; } cout<<endl; } template int CList::GetLength() { return m_len; } //查找数据 template T CList::Find(const int &pos) { if(pos <= 0) { cout<<"输入不合法"< m_len) { cout<<"超出表长"<<endl; return NULL; } int i = 0; Node *pT = m_pHead->m_pNext; while(pT) { ++i; if(i == pos) { return pT->m_data; } pT = pT->m_pNext; } return NULL; } template void CList::Insert(const int &pos,const T &data) { if(pos m_len) { cout<<"输入不合法"<<endl; return; } int i = 0; Node *pT = m_pHead->m_pNext; Node *pPre = NULL; Node *pBehind = NULL; while(pT) { ++i; if(i == pos - 1) { pPre = pT; } if(i == pos) { pBehind = pT->m_pNext; break; } pT = pT->m_pNext; } Node *pNew = new Node; 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是<mark style="color:transparent">来源gaodaimacom搞#^代%!码网</mark>指最后一个元素 { m_pEnd->m_pNext = pNew; } pPre->m_pNext = pNew; pNew->m_pNext = pT; ++m_len; }
希望本文所述对大家的C++程序设计有所帮助。
以上就是C++语言实现线性表之链表实例的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++语言实现线性表之链表实例
转载请注明原文链接：C++语言实现线性表之链表实例
