链表的学习

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成。

 节点

每个结点包括两个部分：一个是存储数据元素的数据域(data)，另一个是存储下一个结点地址的指针域(next)。

注意:

1. 首元结点是指链表中储存第一个数据元素a1的结点。
   

   
   

2. 头结点是在首元节点之前附设的一个结点，其指针域指向首元结点。
   

   
   

   头结点的数据域可以不存储任何信息,也可存储与数据元素类型相同的其他信息。
   

   
   

 图形表示

 用单链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。

换句话说,指针为数据元素之间的逻辑关系的映像,则逻辑上相邻的两个数据元素其储存的物理位置不要求相邻,由此,这种存储结构为非顺序映像或链式映像。

单链表的存储结构

typedef struct LNode
{
    ElemType data;            //结点的数据域
    struct LNode *next;       //结点的指针域
}LNode,*LinkList;            //LinkList为指向结构体LNode的指针类型

 这里定义的是单链表中每个结点的存储结构,它包括两部分:存储结点的数据域data,其类型用通用类型标识符ElemType表示;存储后继结点位置的指针域next,其类型为指向结点的指针类型LNode*。

 链表增加头结点的作用:

1. 便于首元结点的处理:增加了头结点后,首元结点的地址保存在头结点(即其"前驱"结点)的指针域中,则对链表的第一个数据元素的 *** 作与其他数据元素相同,无需进行特殊处理。
   

   
   

2. 便于空表和非空表的统一处理

 单链表基本 *** 作的实现 1.初始化

方法:

1.生成新结点作为头结点

2.头结点的指针域置空

Status InitList(LinkList &L)
{
    L=new LNode;
    L->next=NULL;
    return OK;
}

 2.取值     O(n)

方法:

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)
{
    p=L->next;    //初始化,p指向首元结点
    j=1;        //计数器j初值附为1
    while(p&&jnext;    //p指向下一个结点
        ++j;        //计数器j相应加1
    }    
    if(!p||j>i) return ERROR;  //i值不合法i>n或i<=0
    e=p->data;        //取第i个结点的数据域
    return OK;
}

 3.查找     O(n)

方法:

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

2.从首元结点开始依次顺着链域next向下查找,只要指向当前结点的指针p不为空,并且p所指结点的数据域不等于给定值e,则循环执行以下 *** 作:p指向下一个结点

3.返回p。

若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL

LNode *LocateElem(LinkList L,ElemType e)
{
    p=L->next;        //初始化,p指向首元结点
    while(p && p->data != e)
        p=p->next;
    return p;
}

 4.插入      O(n)

方法:

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

2.生成一个新结点*s

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

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

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

Status ListInsert(LinkList &L,int i,ElemType e)
{
    p=L;j=0;
    while(p &&(jnext;
        ++j;
    }
    if(!p||j>i-1) return ERROR;    //i>n+1或者i<1
    s=new LNode;        //生成新结点*s
    s->data=e;        //将结点*s的数据域置为e
    s->next=p->next;    //将结点*s的指针域指向结点ai
    p->next=s;        //将结点*p的指针域指向结点*s
    return OK;
}

 5.删除

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

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

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

4.释放结点ai的空间

Status ListDelete(LinkLIst &L,int i)
{
    p=L;
    j=0;
    while((p->next)&&(jnext;
        ++j;
    }
    if(!(p->next)||(j>i-1)) return ERROR;
    q=p->next;        //临时保存背删结点的地址以备释放
    p->next=q->next;    //改变删除结点前驱结点的指针域
    delete q;        //释放删除结点的空间
    return OK;
}

以上参考于严蔚敏老师的"数据结构"一书