数据结构单链表及其基本函数的基本实现

  用链表存储的线性表如果只有每个节点只有一个指针域，则称为单链表。

  单链表由结点组成，而结点通常由数据域和指针域构成，存储定义代码如下：

struct LNode
{
	int data;
	LNode* next;
	LNode(int value)
	{
		data=value;
		next=nullptr;
	}
};

    单链表的节点的指针域其实可以简单理解为存储着寻找下一个相同类型节点的指针，形成一个简单的套娃。

  单链表的一个重要概念就是头结点和头指针。头结点是链表中的第一个节点，建立一个头结点和头指针，方便对链表进行修改，删除，查询等操作。

class LinkList
{
	private:
	 LNode* head;
	 LNode* rail;
	public:
	LinkList()
	{
		head=new LNode(0);
		rail=head;
	}
}

  创建一个链表最基本的方法有两种——头插法和尾插法。

  头插法：头插法即每次插入节点都在头结点之后，通过头插法创造出来的链表与插入的顺序相反。如图：新建一个结点S，如果想把结点S插入头结点之后，那需要我们先找到头结点后一个的结点，S结点与其进行连接，之后在将头结点与S结点相连接。其中，重要的是不能更换操作顺序，如果先把头结点和S结点相连接，则会导致断链，无法找到原来与头结点相连接的结点。

代码如下：

	void headend(int value)  //头插法 
	{
		LNode* s=new LNode(value);
		s->next=head->next;
		head->next=s;
	}

  尾插法：即将结点每次插入在链表的尾部，利用尾插法构建的链表是顺序。

  尾插法需要我们设置一个表尾指针P，初值指向头结点，每次新建一个结点S，结点插在表尾指针P之后,之后S成为新的表尾。代码如下：

  

	void append(int value)  //尾插法 
	{
		LNode* s=new LNode(value);
		rail->next=s;
		rail=s;
	}

  通过头插法和尾插法构造出链表之后，可以通过指针进行对链表的基础操作，例如查询链表中是否有指定的元素ELEM，其思想主要是通过设置工作指针进行对链表的遍历，代码如下——

  

	bool getElem(int i)
	{
		LNode* d=head->next;
		while(d!=nullptr){
		if(d->data==i)
		return true;
		else
		d=d->next;
	    }
	    return false;
	 } 

  删除和更改链表指定位序的元素——其思想主要是通过指针对指定位序进行定位，之后通过设置新的指针对其数据域进行操作。

  代码如下

	bool deleteElem(int i) //从第0个元素开始计数 
	{
		int j=0;
		LNode* d=head->next;
		while(d->next!=nullptr&&j<i-1) //定位到第i-1个元素 
		{
		d=d->next;
		j++;
     	}
     	if(d->next==nullptr&&j>i-1)
		return false;
		else
		{
		 LNode* q=d->next;
		 d->next=q->next;	
		}      
	}  
	bool ChangeElem(int i,int e)
	{
	  	int j=0;
		LNode* d=head->next;
		while(d->next!=nullptr&&j<i-1) //定位到第i-1个元素 
		{
		d=d->next;
		j++;
     	}
     	if(d->next==nullptr&&j>i-1)
		return false;
		else
		{
	    LNode* q=d->next;
	    q->data=e;
		}

	} 

  全部代码如下：

  

#include <iostream>
using namespace std;
struct LNode
{
	int data;
	LNode* next;
	LNode(int value)
	{
		data=value;
		next=nullptr;
	}
};
class LinkList
{
	private:
	 LNode* head;
	 LNode* rail;
	public:
	LinkList()
	{
		head=new LNode(0);
		rail=head;
	}
	void append(int value)  //尾插法 
	{
		LNode* s=new LNode(value);
		rail->next=s;
		rail=s;
	}
	void headend(int value)  //头插法 
	{
		LNode* s=new LNode(value);
		s->next=head->next;
		head->next=s;
	}
	bool getElem(int i)
	{
		LNode* d=head->next;
		while(d!=nullptr){
		if(d->data==i)
		return true;
		else
		d=d->next;
	    }
	    return false;
	 } 
	bool deleteElem(int i) //从第0个元素开始计数 
	{
		int j=0;
		LNode* d=head->next;
		while(d->next!=nullptr&&j<i-1) //定位到第i-1个元素 
		{
		d=d->next;
		j++;
     	}
     	if(d->next==nullptr&&j>i-1)
		return false;
		else
		{
		 LNode* q=d->next;
		 d->next=q->next;	
		}      
	}  
	bool ChangeElem(int i,int e)
	{
	  	int j=0;
		LNode* d=head->next;
		while(d->next!=nullptr&&j<i-1) //定位到第i-1个元素 
		{
		d=d->next;
		j++;
     	}
     	if(d->next==nullptr&&j>i-1)
		return false;
		else
		{
	    LNode* q=d->next;
	    q->data=e;
		}

	} 
	void print()
	{
		LNode* s=head->next;
		while(s!=nullptr)
		{
			cout<<s->data<<" ";
		    s=s->next;
		}
	}
};
int main() 
{
	LinkList a;
	a.append(12);
	a.append(15);
	a.headend(18);
	a.headend(9);
	a.deleteElem(2);
	a.ChangeElem(2,43);
	a.print();
	if(a.getElem(43))
	{
		cout<<"hello";
	}	
}

  运行结果如下：

  

  运行结果完全正确。