2019-02-15

第二章

<1>线性表的定义：

    1.n个类型相同的数据元素构成的有限序列记做a1,a2，....,an；

    2.其中1,2，......，n是元素的序号，表示在表中的位置；

    3.n为元素的总个数；

    4.a1表示线性起点，an表示线性终点；

    5.ai-1是ai的直接前驱，ai+1是ai的直接后继；

    6.当n等于0，成为空表。

线性表的特点：

    1.。同一性——线性表由同类数据元素组成。

    2.有限性——由有限个数据元素组成。

    3.有序性——线性表中的数据有先后顺序。

<2>线性表的存储方式:

    1.顺序表：用顺序方式存储的线性表。

    2.链表：是用链式方式存储的线性表。

顺序存储元素地址计算：

    LOC(ai)=LOC(a1)+(i-1)*d

    d —— 一个元素占用的存储单元个数。

    LOC(ai) —— 线性表第i个元素的起始地址。

    LOC(ai) —— 起始地址，基地址。

顺序存储特点：

    1.逻辑上的相邻。

    2.随机存取。

顺序表的结构体数据类型：

    typedef struct{

       Elem Type  *elem(一维数组)；//存储的是数组的第一个元           素的地址。

        int类型- length；//顺序表的当前长度。

    命名：}SqList；//定义的结构体数据类型SqList，用于表示         顺序表

*Elem Type：抽象表示 可以是int，double，结构体类型（变量）

SqList L；

L.lengh

表达为

    L.elem[1]，L.elem[2]，......，L.elem[L.length]

单变量空间申请：int*p=new int；

单变量空间释放：delete p；

数组空间的申请：

    一维：int*p=new int[5];

    二维：int(*p)[3]=new int[2][3];

释放：delete[ ]p;

赋值：1 *p=...;            2.p[0]=

                p++;                 p[1]=

               *p=...;                 .....

void Initist(SqList  &L)   //L里面是垃圾数据需要引用

{

顺序表的初始化操作：

    L.elem=new Elem Type(MAXSIZE);

    if (L.elem==NULL)

        exita (OVERFLOW);

    else

        L.length=0;

}