线性表 | 日薄西山

定义

由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表，(n=0)的时候被称为空表。

一个数据元素可以是简单的一个数据，一个符号，也可以是复杂的若干个数据项的组合

类型定义

ADT List{
    数据对象:D={a[i]|a[i]是元素，i=1，2，3,...，n}
    数据关系:R1={<a[i-1]，a[i]> | i=2,...,n}
    基本操作:建立、存取、插入、删除、检索、分解、排序等
} ADTList; #变量名

线性表的顺序实现

线性表的顺序存储又被称为顺序表。
顺序存储表示:用一组地址连续的存储单元依次存储线性表的数据元素的方式，具有顺序存储结构的特点(数据间的逻辑关系和物理关系是一致的)
假设线性表L存储的起始位置为 LOC(A)，sizeof(ElemType)是每个数据元素所占用存储空间的大小，则表L所对应的顺序存储如下图:

注意:线性表中的位序是从1开始的，而数组中元素的下标是从0开始的

线性表的顺序存储结构是一种随机存取的存储结构，即通过首地址和元素序号可以在O(1)时间内找到指定的元素.
由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，在C/C++语言中通常使用动态分配的一维数组表示线性表。

//------顺序表的存储结构------
#define MAXSIZE 100     //顺序表可能达到的最大长度
    typedef struct {
        ElemType *elem; //存储空间的基地址
        int length;     //当前长度
    } sqList;           //顺序表的结构类型为sqList

顺序表的基本操作:初始化
①为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
②将表的当前长度设为0。

Status InitList(sqList &L){
//构造一个空的顺序表L:为顺序表分配一个大小为MAXSIZE的数组空间
    L.elem = new ElemType[MAXSIZE1];
    if(!L.elem) exit(OVERFLOW);     //存储分配失败退出 #代码严谨性
    L.length =0;                    //室表长度为0
    return OK;
}

顺序表的基本操作:取值
①判断指定的位置序号i值是否合理(1≤i≤L.length),若不合理，则返回ERROR。
②若i值合理，则将第i个数据元素 L.elem[i-1]赋给e,通过e返回第i个数据元素的传值。

顺序表的基本操作:按值查找
①从第一个元素起，依次和 e相比较，若找到与 e相等的元素L.elem[i],则查找成功，返回该元素的序号 i+1(数组下标从0开始)。
②若查遍整个顺序表都没有找到，则查找失败，返回0。

线性表的链式实现

链式存储结构的特点:用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)，存放数据元素的结点至少包括两个域(指针域、数据域)，也可以包含若干个指针域和数据域。

基本概念:头指针，空指针，带表头结点的单向链表

链表在内存中的存储:非顺序

关于带头结点的单链表及不带头节点的单链表

首元结点:是指链表中存储第一个数据元素的结点。
头结点:是在首元素结点之前附设的一个结点，其指针指向首元结点。
头指针:是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点,
若链表不设头结点，则头指针所指结点为该线性表的首元结点。

带头结点的单链表为空时:L->next==NULL;

不带头结点的单链表为空时:L=NULL;

初始化
取值

单链表的基本操作:初始化
①生成新结点作为头结点，用头指针L指向头结点。
②头结点的指针域置空

单链表的基本操作:取值
①用指针p指向首元结点，用j做计数器初值赋为1
②从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针p不为空(NULL),并且没有到达序号为i的结点，则循环执行以下操作:
p指向下一个结点; 计数器j相应加 1
③退出循环时，如果指针p为空，或者计数器j大于i,说明指定的序号i值不合法(i大于表长n或i小于等于0)，取值失败返回ERROR;否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保
存当前结点的数据域，返回OK。

Status GetElem(LinkList L, int i, ElemType &e){
//在带头结点的单链表L中根据序号l.获取元素的值，用e返回L中第l.个数据元素的值
    p =L->next;
    j =1;                   //初始化，p指向首元结点，计数器]初值赋为
    while(p && j<i){        //顺链域向后扫描，直到p为空或p指向第l.个元素
        p = p->next;        //p指向下一个结点 
        ++j;                //计数器j相应加1
    }
    if(!p || j>i) return ERROR;        //i佳不台法i>n或i<=0
    e = p->data;                       //取第i个结点的数据域
    return OK;
}
    