三、(3)单链表_牛客博客

1.定义：

用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

2.单链表图解：

3.单链表的存储结构：

"递归定义:"
typedef struct LNode{
	ElemType data;		//结点的数据域
	struct LNode * next; 	//结点的指针域 
}LNode,*LinkList;		//LinKlIST为指向结构体LNode的指针类型

结构体指针类型：LinkList 与 LNode *，两者本质上是等价的。

LNode*p与LinkList p 的习惯用法:
LinkList p强调定义的是某个单链表的头指针;
LNode * p强调定义指向单链表中任意结点的指针变量。

4.operation：

①初始化

Status InitList(LinkList &L)
{
	L=new LNode;		//生成新结点作为头结点，用头指针L指向头结点
	L->next=NULL;		//头结点指针域置空
	return OK; 
}

②取值：(根据下标取得元素)

Status GetElem(LinkList L,int i,ElemType &e)
{
	LNode *p=L->next;		//p指向首元结点， 
	int j=1;		        //计数器赋值为1 
	while(p&&j<i)			//当p不为空 且 输入的i值合法时
	{	
		p=p->next;		//p指向下一个结点 
		j++;			//计数器++ 
	}
	if(!p||j>i)			//p指向NULL 或 i值不合法
		return ERROR;
	e=p->data;			//取第i个结点的数据域 
	return OK;
}O(n)

③查找:(根据元素值得到下标)

LNode *LocateElem(LinkList L,ElemType e)
{
	//在头结点的单链表L中查找值为e的元素
	LNode *p=L->next;		//初始化，p指向首元结点
	while(p&&p->data!=e)		//顺链表向后遍历，直到p为空或者找到与e相等的结点时结束循环 
	{
		p=p->next;		//p指向下一个结点 
	}		
	return p;		        //查找成功返回e的结点地址p，查找失败p为NULL 
}

④插入:

Status ListInsert(LinkList &L,int i,ElemType e)
{
	//在带头结点的单链表L中第i个位置插入值为e的新结点
	LNode *p=L;
	int j=0;
	while(p&&(j<i-1))		//查找第i-1个结点，p指向该结点 
	{
		p=p->next;
		j++;	
	} 
	if(!p||j>i-1)
		return ERROR;		//i>表长或者i<1 
	LNode *s=new LNode;		//生产新结点*s 
	s->data=e;			//将结点*s的数据域置为 e 
	s->next=p->next;		//将结点*s的指针域指向结点 
	p->next=s;			//将结点*p的指针域指向结点 *s 
	return OK;
}O(n)

⑤删除:

Status ListDelete(LinkList &L,int i)
{
	//在带头结点的单链表L中，删除第i个元素
	LNode *p=L;
	int j=0;
	while(p->next&&j<i-1)	        //查找第i-1个结点，p指向该结点 
	{
		p=p->next;
		j++;	
	} 
	if(!(p->next)||j>i-1)	
		return ERROR;
	LNode *q=p->next;		//临时保存被删结点以备释放 
	p->next=q->next;		//改变删除结点的前驱结点的指针域 
	delete q;			//释放被删除结点空间 
	return OK; 
}O(n)

⑥创建单链表:
a.前插法创建单链表:

void CreateList_H(LinkList &L,int n)
{
	L=new LNode;		//先建立一个带有头结点的空链表
	L->next=NULL;		
	for(int i=0;i<n;i++)
	{
		LNode *p=new LNode;		//生成新结点*p
		cin >> p->data;			//输入元素赋值给*p的数据域
		p->next=L->next;		
		L->next=p;	 		//将新结点*p插入到头结点之后 
	} 
} O(n)

b.后插法创建单链表:

void CreateList_R(LinkList &L,int n)
{
	L=new LNode;
	L->next=NULL;
	LNode *r=L;		//尾指针r指向头结点
	for(int i=0;i<n;i++)
	{
		LNode *p=new LNode;			//生成新结点
		cin >> p->data;
		p->next=NULL;
		r->next=p;
		r=p;	
	} 
 } O(n)

⑦清空

Status ClearList(LinkList & L){
  // 将L重置为空表 
   LinkList p,q;
   p=L->next;   //p指向第一个结点
   while(p)       //没到表尾 
      {  q=p->next; delete p;     p=q;   }
   L->next=NULL;   //头结点指针域为空 
   return OK;
 }

⑧销毁

Status DestroyList_L(LinkList &L){
    LinkList p;
       while(L)
        {
            p=L;  
            L=L->next;
            delete p;  
        }
     return OK;
 }