数据结构学习笔记——线性表

二、线性表

2.0 线性结构的特点

特点：在数据元素非空的有限集中：

        （1）存在唯一的一个被称做“第一个”的数据元素；

        （2）存在唯一的一个被称做“最后一个”的数据元素；

        （3）出第一个外，集合中的每个数据元素均只有一个前驱；

        （4）除最后一个外，集合中每个数据元素均只有一个后继；

2.1线性表的类型定义

线性表：是n个数据元素的有限序列；

记录：一个数据元素由若干个数据项组成

文件：含有大量记录的线性表

直接前驱：当i=1，2，……，n-1，ai有且仅有一个直接后继，当i=2，3，……，n时，ai有且仅有一个直接前驱。

线性表的长度：线性表中元素的个数n；

2.1.1算法

例1：

将LA和LB中的数据元素按值非递减有序排列

代码：

void MergeList(List La, List Lb, List &Lc){
    InitList(Lc);//构造一个新的线性表Lc
    i=j=1;
    k=0;
    La_len = ListLength(La);//La表的长度
    Lb_len = ListLength(Lb);//Lb表的长度
    while((i<=La_len) && (j<=Lb_len)){
        GetElem(La,i,ai);
        GetElem(Lb,j,bj);
        //用ai、bj返回线性表中的i、j位置的值
        if(ai<bj){
            ListInsert(Lc,++k,ai);//在线性表的i位置插入新的数据元素，长度加一
            ++i;
        }else{
            ListInsert(Lc,++k,bj);
            ++j;
        }
    }
    while(i<=La_len){
        GetElem(La,i++,ai);
        ListInsert(Lc,++k,ai);
    }
    while(j<=Lb_len){
        GetElem(Lb,j++,bj);
        ListInsert(Lc,++k,bj);
    }
}

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

2.2.1定义：

定义：用一组地址连续的存储单元依此存储线性表的数据元素

2.2.2位置表示

第i+1个数据元素存储位置：
$LOC(i+1)=LOC(i)+l$
第i个数据元素的存储位置为：
$LOC(i)=LOC(1)+(i-1)*l$
其中
$LOC(1)$
是第一个数据元素的存储位置，又叫起始位置或者基地址。

线性表的这种机内表示叫做顺序存储结构或顺序映像，这种表叫做顺序表

2.2.3顺序存储结构特点：

线性表的顺序存储结构是一种随机存储的存储结构

2.2.4优缺点

优点：

随机存取表中任一元素，存储位置可以用一个简单、直观的公式表示；

缺点：

在插入或删除操作时需要移动大量元素。

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

2.3.1链式存储结构的特点

特点：

用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）

单链表是非随机存储的存储结构

2.3.2线性表链式存储结构定义及相关术语

结点由指针域和数据域构成，指针域中存储的信息称作指针或链想，n个结点链结成一个链表，即为线性表的链式存储结构

静态链表

                用数组描述的链表

循环链表

                表中最后一个结点的指针域指向头结点，整个链表形成一个环。

                有时候会在循环链表中设立尾指针，不设头指针，可以简化某些操作

双向链表

                在双向链表的结点中有两个指针域，其一指向直接后继，另一个指向直接前趋

双向链表的插入操作

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;
}

双向链表的删除操作

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;//p=null，即为第i个元素不存在
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}

2.3.4链表优缺点

链表优点：在空间的合理利用上和插入、删除时不需要移动等

成为线性表的首选存储结构

缺点：求表长麻烦，淡化了“位序”概念

2.4一元多项式的表示及相加

一元多项式
$Pn(x)=p0+p1x+p2x^2+……+pnx^n$
对于次数不高的多项式相加，可以采用顺序存储结构

对于次数很高的多项式相加，采用链式存储结构（便于插入和删除数据）

两个一元多项式相乘的算法，可以利用两个一元多项式相加算法来实现。