@TOC

链式存储相关概念

• 用一组物理地址任意的存储单元来存放线性表的数据元素；
• 这组存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置；
• 链表中元素的逻辑次序和物理次序不一定相同。

结点：数据元素的存储映像。由数据域和指针两部分组成。
链表：n个结点由指针链组成一个链表。
它是线性表的链式存储映像，称为线性表的链式存储结构。

单链表、双链表、循环链表：

• 结点只有一个指针域的链表，称为单链表或线性链表
• 结点有两个指针域的链表，称为双链表
• 收尾相连的链表称为循环链表

头指针、头结点和首元结点：

• 头指针：是指向链表中第一个结点的指针
• 首元结点：是指链表中存储第一个数据元素a~1~的结点
• 头结点：是在链表的首元结点之前附设的一个结点

链表（链式存储结构）的特点

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻；
• 访问是只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花的时间不等。

单链表

单链表的存储结构

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

例如，存储学号、姓名、成绩的单链表结点类型定义如下：

typedef Struct {
    char num[8];  //数据域
    char name[8];  //数据域
    int score;    //数据域
}ElemType;

typedef struct Lnode {
    ElemType data ;     //结点的数据域
    struct LNode *next;  //指针域
}    

单链表的操作

单链表的初始化

即构造一个空表

Status InitList_L(LinkList &L) {
    L = new LNode;   //或L = (LinkList)malloc (sizeof(LNode))
    L->next = NULL;
    return OK;
}

销毁单链表L

Status DeleteList_L(LinkList &L){
    LNode *p;
    while(L){
        p=L;
        L=L->next;
        delete p;
    }
}

清空链表L

Status ClearList_L(LinkList &L){   //将L重置为空表
    LNode *p,*q;
    p = L->next;
    while(p){
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;
    return OK;
}

求单链表的表长

int ListLength_L(LinkList L){   //返回L中元素个数
    LinkList p;
    p = L->next;
    i=0;
    while(p){
        i++;
        p = p->next;
    }
    return i;
}

查找第i个元素

Status GetElem_L(LinkList L,int i,ElenType &e){
    //获取线性表L中第i个元素的内容，通过变量e返回
    p = L->next;
    j = 1;
    while(p&&j<i){
        p = p->next;
        j++;
    }
    if(!p||j>i){
        return ERROR;
    }
    e = p->data;
    return OK;
}

安值查找

int LocateElem_L(LinkList L,ElenType e){
//在线性表L中查找值为e的数据元素的位置序号
    p = L->next;
    j=1;
    while(p&&p->data!=e){
        p = p->next;
        j++;
    }
    if(p) return j;
    else return 0;
}

单链表的插入

Status ListInsert_L(LinkList &L,int i,ElemType e){
//在L中第i个元素前插入数据元素e
    p = L;
    j = 0;
    while(p&&j<i-1){
        p = p->next;
        j++;
    }
    if(p||j>i-1) return ERROR;
    s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
}

单链表的删除

Status ListDelete_L(LinkList &L,int i,ElemType &e){
//将L中第i个数据元素删除
    p = L;
    j = 0;
    while(p&&j<i-1){
        p = p->next;
        j++;
    }
    if(p->next||j>i-1) return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    delete q;
    return OK;
}

头插法建立链表

void CreateList_H(LinkList &l,int n){
    L = new LNode;
    L->next = NULL;
    for(i = n;i>0;i--){
        p = new LNode;
        cin>>p->data;
        p->next = L->next;
        L->next = p;
    }
}

尾插法建立链表

void CreateList_R(LinkList &l,int n){
    L = new LNode;
    L->next = NULL;
    r = L;
    for(i = 0;i<n;i++){
        p = new LNode;
        cin>>p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

循环链表

一种头尾相连的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。
从表中任一结点出发均可找到表中其他结点。

双向链表

在单链表的每个结点里在增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链。

双向链表的存储结构

typede struct DuLNode {
    ElemType data;
    struct DuLNode *prior,*next;
}DuLNode,*DulLinkList;

双向链表的操作

双向链表的插入

void ListInsert_DuL(DuLinkList &L,int i,ElemType e){
    //在带头结点的双向链表L中第i个位置之前插入元素e
    if(!(p = GetElemP_DuL(L,i))) return ERROR;   //得到第i个位置的结点p
    s = new DuLNode;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

双向链表的删除

void ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
    //删除带头结点的双向链表L的第i个元素，并用e返回
    if(!(p = GetElemP_DuL(L,i))) return ERROR;   //得到第i个位置的结点p
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}

链式存储总结

优点：

• 结点空间可以动态申请和释放；
• 数据元素的逻辑次序靠结点的指针指示，插入和删除时不需要移动元素。

缺点：
-存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大；
链式存储结构是非随机存取结构。对任一结点的操作都要从头指针链查到该结点，这增加了算法的复杂度。

顺序表和链表的比较