首页 > 代码库 > 03.线性表(二)链式存储结构.单链表1

03.线性表(二)链式存储结构.单链表1

链式存储结构.单链表1
1.基本概念
    为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)
(1)数据域存储线性表数据元素数据信息的域称为数据域;
(2)指针域:把存储直接后继位置(下一个数据元素的地址)的域称为指针域,指针域中存储的信息为指针或链;
(3)结点(Node):数据域和指针域两部分信息组成数据元素ai的存储映像,称为结点。
(4)头指针:把链表中第一个结点的存储位置叫做头指针,因此整个链表的存取就必须从头指针开始进行。
(5)头结点:为了更加方便地对链表进行操作,我们在单链表的第一个结点前附设一个结点,即为头结点。头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针。

升华笔记一:头指针和头结点的异同?
头指针:
a.头指针是指链表指向第一个结点的存储位置指针,若链表有头结点,则是指向头结点的指针。
b.头指针具有标识作用,所以常用头指针冠以链表的名字
c.无论链表是否为空,头指针均不为空。头指针是链表的必要元素
头结点:
a.头结点是为了操作的统一和方便而设立的,放在第一个元素的结点之前,其数据域一般无意义(也可以存放链表的长度);
b.有了头结点,对在第一元素结点前插入结点和删除第一结点,其操作与其他结点的操作就同一了;
c.头结点不一定是链表必要素

2.单链表
     n个结点(ai的存储映像)链结成一个链表,即为线性表(a1,a2....an)的链式存储结构,因为此链表的每个结点只包含一个指针域,所以称之为单链表。
技术分享
3.链式存储结构指针代码示例
/*线性表的单链表存储结构
  *    结点由存放数据元素的数据域和存放后继结点地址的指针域组成*/
typedef int ElemType; 
typedef struct Node
{
    ElemType data;            //int类型成员变量,作为结点的数据域
    struct Node *next;        //struct Node类型成员指针变量,作为结点的指针域
}Node;
typedef struct Node *LinkList;    //定义LinkList
注释:
(1)Node相当于struct Node结构体;*LinkList相当于struct Node结构体
(2)假设指针p是指向线性表第i个元素的指针,则结点ai数据域和指针域为p->data、p->next即:
     p->data的值为该结点ai的数据域,内容是一个数据元素;
     p->next的值是一个指针,指向第(i+1)个元素(结点)的存储地址,即指向ai+1的指针
p->data=http://www.mamicode.com/ai>
技术分享
4.单链表的读取、插入与删除操作
(1)单链表的读取操作
实现操作 GetElem(LinkList L,int i,ElemType *e),从单链表L中取出第i个数据元素,存放到指针变量i指向的地址空间中
算法思路:不像线性表的顺序存储结构可以很容易的从任意位置读取一个元素,单链表的数据元素读取必须从头开始找,即工作指针p后移
a.声明一个结点p指向链表第一个结点,初始化j从1开始遍历
b.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1,直到链表末尾p为空。则说明第i个元素不存在
c.如果p为空结点或者遍历位置超过i,抛出异常
d.查找成功,返回结点p的数据。
源码实现
/*初始条件:顺序线性表L已存在,1=《i<=ListLength(L)
 *操作结构:用e返回L中第i个数据元素的值*/
#define OK 1
#define ERROR 0
typedef int Status; 
typedef int ElemType; 
typedef struct Node *LinkList;    //定义LinkList
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;        //声明一个结点p
    p=p->next;         //让结点p指向链表L的第一个结点
    j=1;
    while(p&&j<i)     //从链表第一个结点开始遍历,直到j=i-1,让p指向存储i-1位置所在的结点
    {
        p=p->next;     //让p指向下一个结点
        j++;
    }
    if(!p || j>i)
        return ERROR;
    *e=p->data;        //查找成功,将链表中的第i个元素的数据存储到指针e指向的空间
    return OK;
}
注释:p为新定义的一个结点,while(p&&j<i)的作用是使结点p从链表第一个结点开始遍历,直到j=i-1,让p指向存储i-1位置所在的结点,直到链表末尾p为空是说明第i个元素不存在。

(2)单链表插入操作
实现操作 ListInsert(LinkList *L,int i,ElemType e),将数据元素e插入到单链表L第i个位置
算法思路: s->next =p->next; p->next=s;      
a.声明一个结点p指向链表第一个结点,初始化j从1开始遍历
b.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1,直到链表末尾p为空,则说明第i个元素不存在。
c.如果p为空结点或者遍历位置超过i,抛出异常
d.如果查找成功,
    -在系统中生成一个空结点s
    -将数据元素e赋值给s->data;
    -单链表的插入标准语句s->next=p->next,p->next=s
源码实现
/*初始条件:顺序线性表L已存在,1=《i<=ListLength(L)
 *操作结构:将数据元素e插入到单链表L第i个位置*/
#define OK 1
#define ERROR 0
typedef int Status; 
typedef int ElemType; 
typedef struct Node *LinkList;    //定义LinkList
Status ListInsert(LinkList *L,int i,ElemType e)
{
    int j;
    LinkList p,s;        //声明一个结点p
    p=*L;         
    j=1;
    while(p&&j<i)     //从链表第一个结点开始遍历,直到j=i-1,让p指向存储i-1位置所在的结点
    {
        p=p->next;     //让p指向下一个结点
        j++;
    }
    if(!p || j>i)
        return ERROR;
    s=(LinkList)malloc(sizeof(Node));    //生成新结点,即在内存中找了一小块空地,准备用来存放e数据s结点
    s->data=http://www.mamicode.com/e; //关键1:查找成功,将数据元素e赋值给s结点的数据域
   s->next =p->next;//关键2:将结点p的后继结点赋值给s的后继(p->next为指向结点p下一个存储地址所在的结点)
    p->next=s;        //关键3:设置结点p的后继结点为结点s
    return OK;
}
注释:p为新定义的一个结点,while(p&&j<i)的作用是使结点p从链表第一个结点开始遍历,直到j=i-1,让p指向存储i-1位置所在的结点,直到链表末尾p为空是说明第i个元素不存在。
(3)单链表删除操作
实现操作 ListDelete(LinkList *L,int i,ElemType *e),删除单链表L中第i个数据元素,并将数据存放至指针e指向的空间中
算法思路p->next=p->next->next(或者q=p->next;p->next=q->next) }   
a.声明一个结点p指向链表第一个结点,初始化j从1开始遍历
b.当j<i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1,直到链表末尾p为空,则说明第i个元素不存在。
c.如果p为空结点或者遍历位置超过i,抛出异常
d.如果查找成功
    -将欲删除的结点p->next赋值给q
    -设置结点p的后继结点为q->next,即p->next=q->next;
    -将结点q的数据域数据存放至e
e.释放q结点,返回成功标识
源码实现
/*初始条件:顺序线性表L已存在,1=《i<=ListLength(L)
 *操作结构:删除单链表L中第i个数据元素,并将数据存放至指针e指向的空间中*/
#define OK 1
#define ERROR 0
typedef int Status; 
typedef int ElemType; 
typedef struct Node *LinkList;    //定义LinkList
Status ListInsert(LinkList *L,int i,ElemType *e)
{
    int j;
    LinkList p,q;        //声明一个结点p
    p=*L;        
    j=1;
    while(p->next&&j<i)     //从链表第一个结点开始遍历,直到j=i-1,让p指向存储i-1位置所在的结点
    {
        p=p->next;     //让p指向下一个结点
        j++;
    }
    if(!p || j>i)
        return ERROR;
    q=p->next;            //设置q为p的后继结点
    p->next=q->next;   //将q的后继结点设置为p的后继结点
    *e=q->data;    //将q结点中的数据给e
    free(q);           //设置完成后,让系统回收此结点,释放内存
    return OK;
}


升华笔记二:s、p、s->data、s->next、p->next辨析?
(1)LinkList p,s:声明两个结点p、s,包含数据域和指针域;
(2)s->data:为结点s的数据域,其值为一个数据
(3)s->next::为结点s的指针域,其值为下一个结点存储地址
(4)s->next=p->next:将结点p的下一个结点存储地址赋值给s结点指针域
(5)p->next=s; 将结点s设置为p的下一个结点
事实上,(4)(5)我们可以这样理解:
    假设初始链表相连两个结点p、q,即......-p-q-......,现在我们需要在结点p、q之间插入一个结点s,则
    方法如下:由于p->next=q
                        则s->next=q        //结点s后继为q
                            p->next=s        //结点p后继为s,此时即可形成......-p-s-q-......

5.顺序存储结构性能分析
(1)查找:最好情况时间复杂度为O(1),最坏情况事件复杂度为O(2)
(2)删除、插入:单链表的插入和删除主要由两部分组成:第一部分是遍历查询第i个元素;第二部分就是插入和删除元素
    从整个算法来说,我们很容易推导出:它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置,单链表数据结构在插入和删除操作上,与线性表的顺序存储解雇是没有太大的优势。但是如果我们希望从第i个位置,插入10个元素,对于顺序存储结构意味着,每一次插入都需要移动n-i个元素,每次都是O(n)。而对于单链表,我们只需要在第一次找到第i个位置的指针,此时为O(n),接下来只是简单地通过赋值移动指针而已,时间复杂度都是O(1)
总结:对于插入或删除数据越频繁的操作,单链表的效率优势就越明显。

03.线性表(二)链式存储结构.单链表1