数据结构cpp实现——单链表
单链表
采用链接存储方式的线性表称之为线性链表，最简单的线性链表结构为单链表。单链表的每一个元素用一个结点存储。data域用来存放数据，next域用来存放指向下一个元素的地址。
一般规定^表示指针指向空。利用单链表存储数据，在删减或增加元素时不需要移动元素，相比于顺序表，可以更高效地实现插入和删除操作。 对于不带头结点的单链表，在第i个节点前插入数据可以分为三种情况
1)在i=1时，表示在单链表最前面插入元素，即原来第一个元素之前。
2)在1<i≤n时，新结点插入在原链表的a(i-1)和ai之间。
3)在i=n+1时，新节点插入在原链表表尾。
删除操作：相比于顺序表的移动前后元素，单链表的删除操作相当简单。删除当前结点后，把前一个结点的指针指向赋值为下一个即可。
如果删除的结点为头结点，则需要修改头指针指向。 单链表的结点类模版定义和实现template<class T>
struct Node
{
T data;//数据域
Node<T> *next;//指针域
Node(){next= nullptr;};//默认无参构造函数
Node(T e,Node<T> *link= nullptr){data=e;next= link;};//有参构造函数
}; 单链表的类模版定义和实现template<class T>
class LinkList {
private:
Node<T> *head;//头结点指针
int length;//元素个数长度
public:
LinkList(){head= new Node<T>;length=0;};//无参构造器
LinkList(T arr[],int n);//第一个参数为初始化数据的数组，第二个参数为对应的长度
~LinkList();//析构函数
int GetLength() const{return length;};//返回单链表长度
bool IsEmpty() const{return length==0;};//单链表是否为空
void clear();//清空线性表
void traverse() const;//遍历打印线性表
int LocateElem(const T &e);//求e元素在线性表中的位置
bool GetElem(int i, T &e) const;//获取第i个结点的数据赋值给e返回true，若失败则返回false
bool SetElem(int i, const T &e);//修改第i个结点的值
bool DeleteElem(int i, const T &e);//删除第i个结点，并将数据域返回给e
bool insert(int i, const T &e);//在原链表的第i个结点之前插入e
bool insert(const T&e);//在链表尾部插入结点
};
template<class T>
LinkList<T>::LinkList(T *arr, int n) {
Node<T> *p;
p=head=new Node<T>;
assert(head);//头结点构造失败则终止程序
for(int i=0;i<n;i++)
{
p->next=new Node<T>(arr[i], nullptr);
assert(p->next);
p=p->next;//逐级向下遍历
}
this->length=n;
}
template<class T>
LinkList<T>::~LinkList() {
clear();
delete head;
}
template<class T>
void LinkList<T>::clear() {
Node<T> *p=head->next;
while(p!= nullptr)
{
head->next=p->next;
delete p;
p=head->next;
}
length=0;
}
template<class T>
void LinkList<T>::traverse() const {
Node<T> *p=head->next;
while(p!= nullptr)
{
std::cout<<p->data<<" ";
p=p->next;
}
}
template<class T>
int LinkList<T>::LocateElem(const T &e) {
Node<T> *p=head->next;
int position=1;
while(p!= nullptr)
{
if(p->data==e)
return position;
position++;
p=p->next;
}
return 0;
}
template<class T>
bool LinkList<T>::GetElem(int i, T &e) const {
if(i<1||i>length)
return false;//元素取值位置非法
else
{
Node<T> *p=head->next;
for(int count=1;count<i;count++)
p=p->next;
e=p->data;
return true;
}
}
template<class T>
bool LinkList<T>::SetElem(int i, const T &e) {
if(i<1||i>length)
return false;
else
{
Node<T> *p=head->next;
for(int count=1;count<i;count++)
p=p->next;
p->data=e;
return true;
}
}
template<class T>
bool LinkList<T>::DeleteElem(int i, const T &e) {
if(i<1||i>length)
return false;
else
{
Node<T> *p=head,*q;
for(int count=1;count<i;count++)
p=p->next;//p实际指到了要删除的元素的前一个结点
e=p->next->data;//将第i个元素返回给e
q=p->next;
p->next=q->next;//将第i-1个节点的next指针指向下下个结点
delete q;
length--;
return true;
}
}
template<class T>
bool LinkList<T>::insert(int i, const T &e) {
if(i<1||i>length+1)
return false;
else
{
Node<T> *p=head,*q;
for(int count=1;count<i;count++)
p=p->next;//定位到第i-1个结点
q=new Node<T>(e, p->next);
assert(q);
p->next=q;
length++;
return true;
}
}
template<class T>
bool LinkList<T>::insert(const T &e) {
Node<T> *p,*q;
q=new Node<T> (e, nullptr);
for(p=head;p->next!= nullptr;p=p->next);
p->next=q;//表尾指针指向新加入的结点q
length++;
return true;
}单链表相比于顺序表更加节省内存空间，并且在删除和插入操作方面，明显优于顺序表。缺点是不支持随机访问(像数组一样直接定位元素位置)，必须通过头结点，依次遍历到所需要的结点。