单链表及其相关算法

1.单链表
　　为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域，其中的指针指向表中下一个元素所在的单元。例如，如果表是a1,a2,…,an ，那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n-1)。含有an的那个单元中的指针是空指针null。此外，通常我们还为每一个表设置一个表头单元head，其中的指针指向开始元素中所在的单元，但表头单元head中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。
　　上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链表。　　

2.单链表的类定义
typedef int ElemType;　　　//假设结点的数据类型为整型
struct NodeType　　　　　//结点类型定义
{ ElemType data;　　　　 //结点的数据域
NodeType*next;　　　　　//结点的指针域
};
【算法2.1】
void LinkList::creat()            //初建一个非空链表
{  NodeType*s;
   ElemType x;
   cout<<"请按倒序输入数据，以-999为结束。"<   cout<<"data=?"; cin>>x;        //输入第一个数据元素：a_n-1
   while(x!=-999)
   {   s=new NodeType;
       s->data=x;
       s->next=Head->next;            //Head为头结点的指针
       Head->next=s;
       cout<<"data=?"; cin>>x;      //逐个输入其他元素a_n-2，…，a₀
   }
   cout<<"插入结束。链表建成。"<}
　　算法2.1可以建立链表。在空链表的基础上，即将线性表的数据元素一一输入，不断产生各结点并建立起前后相链的关系。在这个算法中从表的最后一个数据元素开始输入，然后按顺序逐一输入，最后以-999为结束标志。由上述算法可见，建立线性表的链式存储结构的过程是一个动态生成链表的过程，即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表，其时间复杂度为O(n)。

 

3.单链表的插入
（1）思想方法
插入操作大致分为如下三种：
　　①在已知P指针所指向的结点后插入一个元素x。
　　②在p指针所指向的结点前插入一个元素x。
　　③在线性表中值为y的元素插入一个值为x的数据元素。
    　大致算法思想：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a_i-1与a_i之间。
大致步骤：
    　（1）找到a_i-1存储位置p
    　（2）生成一个数据域为x的新结点*s
    　（3）令结点*p的指针域指向新结点
    　（4）新结点的指针域指向结点a_i。

2）具体算法实现

①在已知P指针所指向的结点后插入一个元素x。
{  s=new NodeType;
   s->data=x;
   s->next=p->next;
   p->next=s;
}
②在p指针所指向的结点前插入一个元素x。
{ q=head;
  while(q->next!=p)q=q->next;
  s=new NodeType;
  s->data=x;
  s->next=p->next;
  q->next=s;
}
③在线性表中值为y的元素插入一个值为x的数据元素。
{ q=head; p=q->next;
  while((p!=NULL)&&(p->data!=X))
  { q=p;
    p=p->next;
  }
  s=new NodeType;
  s->data=x;
  s->next=p->next;
  q->next=s;
}

（3）算法分析
    　算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。

4.单链表的删除
（1）思想方法
删除操作大致分为如下三种：
　　①删除p所指向结点的后继结点（假设存在）
　　②删除p所指向的结点。
　　③删除线性表中值为x的数据元素。
    　大致算法思想：删除运算是将表的第i个结点删去。
具体步骤：
   　（1）找到a_i-1的存储位置p（因为在单链表中结点a_i的存储地址是在其直接前趋结点a_i-1的指针域next中）
   　（2）令p-＞next指向a_i的直接后继结点（即把a_i从链上摘下）
   　（3）释放结点a_i的空间，将其归还给"存储池"。

（2）具体算法实现

①删除p所指向结点的后继结点（假设存在）
{ q=p->next;
  p->next=q->next;
  delete q;
}
②删除p所指向的结点。
{ q=head
  while(q->next!=p)
  q++;
  q->next=p->next;
  delete p;
}
③删除线性表中值为x的数据元素
{q=head;p=q->next;
while((p!=NULL)&&(p->data!=x)
{ q=p;
p++;}
q->next=p->next;
delete p;
}
注意：
    　设单链表的长度为n，则删去第i个结点仅当1≤i≤n时是合法的。
   　 当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p！=NULL）且*p不是终端结点（即p-＞next！=NULL）时，才能确定被删结点存在。

（3）算法分析
    　算法的时间复杂度也是O（n）。
    　链表上实现的插入和删除运算，无须移动结点，仅需修改指针。