@1405010304geshuaishuai 2017-07-22T10:56:12.000000Z 字数 4725 阅读 439

线性表的链式表示和实现

数据结构 线性表 链式表示

线性表的链式表示和实现

链式存储结构，由于它不要求逻辑上相邻的元素在物理位置上相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。

1. 线性链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据单元（这组存储单元可以是连续的，也可以是不连续的）。
指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此，这种存储结构为非顺序映像或链式映像。
单链表可由头指针惟一确定，在C语言中可用“结构指针”来描述。

//------线性表的单链表存储结构
typedef struct LNode {
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

单链表是非随机存取的存储结构。
函数GetElem在单链表中的实现：

Status GetElem_L(LinkList L, int i, ElemType &e) {
    //L为带头节点的单链表的头指针
    //当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
    p = L->next; j=i;  //初始化，p指向第一个结点，j为计数器
    while(p&&j<i) { //顺时针向后查找，直到p指向第i个元素或p为空
    p = p->next; ++j;
    }
    if(!p||j>i) return ERROR;  //第i个元素不存在
    e = p->data; //取第i个元素
    return OK;
} //GetElem_L

算法的基本操作是比较j和i并后移指针p,while循环体中的语句频度与被查元素在表中位置有关，若1<=i<=n，则频度为i-1，否则频度为n。

为插入数据元素x,首先是生成一个数据域为x的结点，然后插入在单链表中。
假设d为指向结点x的指针。
s->next=p->next; p->next=s;
反之，在线性表中删除元素b时，为在单链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为p->next = p->next->next;
ListInsert算法如下：

Status ListInsert(LinkList &L, int i, ElemType e) {
    //在带头结点的单链表L中第i个位置之前插入元素e
    p=L; j=0;
    while(p&&j<i-1) {p=p->next;++j;}  //寻找第i-1个结点
    if(!p||j>i) return ERROR; //i小于1或者大于表长加1
    s=(LinkList)malloc(sizeof(LNode));  //生成新节点
    s->data=e; s->next=p->next;  //插入L中
    p->next=s;
    return OK;
}//ListInsert_L

Status ListDelete_L(LinkList &L, int i, ElemType &e) {
    //在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
    p = L; j = 0;
    while(p->next && j<i-1){ //寻找第i个结点，并令p指向其前赴
    p=p->next; ++j;
    }
    if(!(p->next)||j>i-1) return ERROR;  //删除位置不合理
    q=p->next; p->next=q->next;
    e=q->data; free(q);
    return OK;
} //ListDelete_L

引用C语言中的两个标准函数malloc和free。在设有“指针”数据类型的高级语言中均存在与其相应的过程或函数。假设p和q是LinkList型的变量，则执行p=(LinkList)malloc(sizeof(LNode))的作用时由系统生成一个LNode型的结点，同时将该结点的其实位置赋给指针变量p；反之，执行free(q)的作用是由系统回收一个LNode型的结点，回收后的空间可以备作再次生成结点时用。因此，单链表和顺序存储结构不同，它是一种动态结构。建立线性表的链式存储结构的过程时一个动态生成链表的过程。

void CreateList_L(LinkList &L, int n){
    //逆为序输入n个元素的值，建立带表头结点的单链线性表L。
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for(i=n;i>0;--i){
        p = (LinkList)malloc(sizeof(LNode));  //生成新节点
        scanf(&p->data);  //输入元素值
        p->next = L->next;  
        L->next = p;  //插入到表头
    }
}//CreateList_L

将两个有序链表并为一个有序链表。
算法描述：
假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，现要归并La和Lb得到单链表Lc,需要设立3个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa->data≤pb->data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。显然，指针的初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一个循环执行的条件时pa和pb皆非空，当其中一个为空时，说明有一个表的元素已归并完，则只要将另一个表的剩余段链接在pc所指结点之后即可。
算法如下：

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
    //移植单链线性表La和Lb的元素按值非递减排列。
    //归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列
    pa = La->next;
    pb = Lb->next;
    Lc = pc = La; //用La的头结点作为Lc的头结点
    while(pa&&pb) {
        if(pa->data<=pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        pc->next = pa? pa:pb;  //插入剩余段
        free(Lb);  //释放Lb的头结点
}//MergeList_L

有时，也可借用一维数组来描述线性链表，其类型说明如下所示：

//-----线性表的静态单链表存储结构----
#define MAXSIZE 1000 //链表的最大长度
typedef struct {
    ElemType data;
    int cur;
}component, SLinkList[MAXSIZE];

这种描述方法便于在不设“指针”类型的高级程序涉及语言中使用链表结构。数组中的一个分量表示一个结点，同时用游标（指示器cur)代替指针指示结点在数组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。这种存储结构仍然需要预先分配一个较大的空间，但在作线性表的插入和删除操作时不需要移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。
在链表中，数组的一个分量表示一个结点，同时用游标（指示器cur)代替指针指示结点在数组中的相对位置。数组的第零分量可看成头结点，其指针域指示链表的第一个结点。例如下图是一个线性表在插入数据元素“SHI”和删除数据元素“ZHENG”之后的状况。为了和指针型描述的线性链表相区别，我们给这种用数组描述的链表起名叫静态链表。
static_list
假设S为SLinkList型变量，则S[0].cur指示第一个结点在数组中的位置，若设i=S[0].cur,则S[i].data存储线性表的第一个数据元素，且S[i].cur指示第二个结点在数组中的位置。一般情况下，若第i个分量表示链表的第k个结点，则S[i].cur指示第k+1个结点的位置。因此在静态链表中实现线性表的操作和动态链表相似，以整型游标i代替动态指针p，i=S[i].cur的操作实为指针后移（类似于p=p->next），例如，在静态链表中实现的定位函数LocateElem如算法：

int LocateElem_SL(SLinkList S, ElemType e) {
    //在静态单链线性表L中查找第1个值为e的元素。
    //若找到，则返回它在L中的位序，否则返回0。
    i = S[0].cur;  //i表示表中第一个结点
    while(i&&S[i].data!=e) i=S[i].cur;  //在表中顺链查找
    return i;
} //LocateElem_SL

2.循环链表

循环链表（circular linked list）是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是他们是否等于头指针。但有的时候，若在循环链表中设立尾指针二不设头指针，可使某些操作简化。

3.双向链表

在单链表中，NextElem的执行时间为O(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点，可利用双向链表（double linked list)。
在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋，在C语言中可描述如下：

//-----线性表的双向链表存储结构-----
typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList;

双向链表也可以有循环表，在双向链表中，若d为指向表中某一结点的指针（即d为DuLinkList型变量），则显然有d->next->prior=d->prior->next=d这个表示恰当地反映了这种结构地特性。

在双向链表中删除结点
ListDelete_DL

Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {
    //删除带头结点地双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
    if(!(p=GetElemP_DuL(L,i)))  //在L中确定第i个元素的位置指针p
        return ERROR;
    e = p->data;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    free(p);
    return OK;
}//ListDelete_DuL

在双向链表中插入结点
ListInsert_DL

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
    //在带头结点的双链循环线性表L中第i个位置之前出入元素e，
    //i的合法值为1≤i≤表长+1.
    if(!(p = GetElemP_DuL(L,i)))  //在L中确定插入位置
        return ERROR;    //p=NULL,即插入位置不合法
    if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}//ListInsert_DuL

由于链表在空间的合理利用上和插入、删除时不需要移动等的优点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在着现实某些基本操作，如求线性表的长度不如顺序存储结构的缺点；另一方面，由于在链表中，结点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念已淡化，而被数据元素在线性链表中的“位置”所代替。

线性表的链式表示和实现