数据结构—基础知识（五）：线性表(b)链表中基本操作

数据结构—基础知识（五）：线性表(b)链表中基本操作

一.单链表基本操作的实现

1.单链表的初始化

【算法描述】

1. 生成新节点作为头结点，用头指针L指向头结点。

2. 头结点的指针域置空。

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

2.创建单链表

1.头插法

【算法步骤】

1. 创建一个只有头结点的空链表。

2. 根据待创建链表包括的元素个数n，循环n次执行一下操作：

   • 生成一个新结点*p;
   • 输入元素值赋给新结点*p的数据域；
   • 将新结点*p插入到头结点。

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

2.尾插法

【算法步骤】

1. 创建一个只有头结点的空链表。

2. 为指针r初始化，指向头结点。

3. 根据创建链表包括的元素个数n，循环n次执行以下操作：

   • 生成一个新结点*p;
   • 输入元素值赋值给新结点*p的数据域；
   • 将新结点*p插入到尾结点之后；
   • 尾指针r指向新的尾结点*p。

   viod CreateList_R(LinkList &L,int n)
   {  //正位序输入n个元素的值，建立带表头结点的单链表L
       L=new LNode;
       L->next=NULL;//先建立一个带头结点的空链表
       r=L;//尾指针r指向头结点
       for(i=0;i<n;++i)
       {
           p=new LNode;
           cin>>p->data;//输入元素值赋给新结点*p的数据域
           p->next=NULL;r->next=p;//将新结点*p插入尾结点*r之后
           r=p;//r指向新的尾结点*p
       }
   }
   

3.单链表的取值

【算法步骤】

1. 用指针p指向首元结点，用j作计数器初值赋为1。

2. 从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空(NULL)，并且没有达到序号为i的结点，则循环执行以下操作：

   • p指向下一个结点；
   • 计数器j相应加1。

3. 退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，取值失败返回 ERROR;否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回 OK。

   Status GetElem(LinkList L,int i,ElemType &e)
   {  //在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
       p=L->next;//p指向首元结点。
       j=1;
       while(p&&j<i)//顺链域向后扫描，直到p为空或p指向第i个元素
       {
           p=p->next;
           ++j;
       }
       if(!p||j>i) return ERRPR;//i值不合法i>n或i≤0 返回ERROR
       e=p->data;//取第i个结点的数据域
       return OK;
   }
   

4.单链表的按值查找

【算法步骤】

1. 用指针p指向首元结点。

2. 从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空(NULL)，并且p所指结点的数据域不等于给定值e，则执行操作：p指向下一个结点。

3. 返回p。若查找成功，p此时即为当前结点的地址值，若查找失败，p的值即为NULL。

   LNode *LocateElem(LinkLink L,ElemType e)
   {  //在头结点的单链表L中查找值为e的元素
       p=L->next;
       while(p && p->data!=e)//顺链域向后扫描，直到p为空或p所指结点的数据域等于e
           p=p-next;
       return p;//查找成功返回值为e的结点地址p，查找失败p为NULL。
   }
   

5.单链表的插入

【算法步骤】

1. 查找结点ai-1并由指针p指向该结点。

2. 生成一个新结点*s。

3. 将新结点*s的数据域置为e。

4. 将新结点*s的指针域指向结点ai。

5. 将结点*p的指针域指向新结点s。

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

6.单链表的删除

【算法步骤】

1. 查找结点ai-1并由指针p指向该结点。

2. 临时保存待删除结点ai的地址在q中，以备释放。

3. 将结点*p的指针域指向ai的后继结点。

4. 释放结点ai的空间。

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

二.双向链表

1.双向链表的插入

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{  //在带头结点的双向链表L中第i个位置之前插入元素e
    if(!(p=GetElem_DuL(L,i)))//在L中确定第i个元素的位置指针p
        return ERROR;//p为NULL时，第i个元素不存在
    s=new DuLNode;
    s->data=e;
    s->prior=p->prior;//1
    p->prior->next=s;//2
    s->next=p;//3
    p->prior=s;//4
    return OK;
}

2.双向链表的删除

Status ListDelete_DuL(DuLinkList &L,int i)
{  //删除带头结点的双向链表L中的第i个元素
    if(!(p=GetElem_DuL(L,i)))
         return ERROR;
    p->prior->next=p->next;//1
    p->next->prior=p->prior;//2
    delete p;
    return OK;
}