[数据结构与算法]数据结构与算法（第二章）——线性表

注：本学习资料依据教材《数据结构（C语言版|第2版）》（严蔚敏 李冬梅 吴伟民 著）

导语：

在本章的学习中，要注意基本概念、基本原理，熟悉线性表的两种存储方式（顺序存储和链式存储）以及对应的操作实现（初始化、取值、查找、插入、删除），要会写出关键代码段，还要结合第一章的算法分析，会计算每个操作的复杂度。学习过程中可以通过对比学习法掌握两种存储结构的区别。

2.1 线性表的定义和表示

1、定义：由n(n≥0)各数据特性相同的元素构成的有限序列称为线性表。

2、特点：

a.存在唯一首元素。

b.存在唯一尾元素。

c.除首元素外，其余元素均只有一个前驱。

d.除尾元素外，其余元素均只有一个后继。

2.2 线性表的顺序表示和实现

1、线性表的顺序存储表示：用一组地址连续的存储单元依次存储线性表的数据元素。其特点是：逻辑上相邻，物理次序也相邻。

线性表中第i+1个元素与第i个元素的位置关系：

? LOC（ai+1） = LOC（ai）+ l

?线性表的第i个数据元素ai的存储位置为：

LOC（ai） = LOC（a1）+（i-1）* /

2、顺序表中基本操作的实现

（1）初始化：

Status InitList(SqList &L)
{
    L.elem = new ElemType[MAXSIZE];
    if(!L.elem) exit(OVERVIEW);    //若L.elem = 0，即未成功开辟空间，则执行if(!L.elem)语句
    L.length = 0;    //初始化表为空表，则表长为0
    return OK;
}

?（2）取值（根据位置i获取相应位置数据元素的内容）

Status GetElem(SqList L,int i,ElemType &e)
{
    if(i<1 || i>L.length) return ERROR;    //对i的合理性进行判断，体现健壮性
    e = L.elem[i-1];
    return OK;
}

? ?(3)查找

int LocateElem(SqList L,ElemType e)
{
    for (i=0;i<L.length;i++)
        if(L.elem[i]==e) return i+1;    //i+1表示被查找元素的序号
    return 0;
}

?（4）插入

Status ListInsert(SqList &L,int i,ElemType e)
{
    if( (i<1) || (i>L.length + 1) ) return ERROR;    //i的取值范围为[1.L.length+1]
    if( L.length == MAXSIZE ) return ERROR;    //空间已满无法存储
    for(j=L.length-1;j>=i-1;j--)
        L.elem[j+1] = L.elem[j];
    L.elem[i-1] = e;
    ++L.length;    //注意插入后表长一定要+1，易忽略点
    return OK;
}

? （5）删除

Status ListDelete(SqList &L,int i)
{
    if( (i<1) || (i>L.length) ) return ERROR;    //i的取值范围为[1,L.length]
    for(j=i;j<=L.length-1;j++)
        L.elem[j-1] = L.elem[j];    //直接覆盖，向前移
    --L.length;    //删除后表长一定要-1，易忽略点
    return OK;
}

?2.3 线性表的链式表示和实现

?1、单链表的定义和表示

（1）结点：包括数据域和指针域。

（2）单链表：每个结点只包含一个指针域的链表。

（3）特点：相邻元素逻辑上相邻，但物理上不一定相邻。

2、单链表基本操作的实现

（1）初始化

Status InitList(LinkList &L)
{
    L = new LNode;
    L -> next = NULL;    //头结点的指针域置空，从而初始化链表
    return OK;
}

（2）取值

Status GetElem(LinkList L,int i,ElemType &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;
}

?（3）查找

LNode *LocateElem(LinkList L,ElemType e)
{
    p = L -> next;
    while(p && p -> data != e)
        p = p -> next;
    return p;    //查找成功返回e的地址p
}

（4）插入

Status ListInsert(LinkList &L,int i, ElemType 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;
    return OK;
}

（5）删除

Status ListDelete(LinkList &L,int i)
{
    p = L;
    j = 0;
    while( (p->next) && (j<i-1) )
    {
        p = p->next;
        ++j;
    }
    if( !(p->next) || (j>i-1)  return ERROR;
    q = p->next;
    p->next = q->next;
    delete q;
    return OK;
}

3、循环链表的合并

ListConnect(LinkList s, Linklist t)
{
    p = s->next;
    s->next = t->next->next;
    delete t->next;
    t->next = p;
    return t;
}

要求合并后无重复数据的算法
if(a->data == b->data)
{
    c->next = a;
    c = a;
    a = a->next;
    q = b->next;
    delete b;
    b = q;
}