线性表

1 线性表的特点

  1. 线性表中n表示线性表的长度，当n=0时称为空表
  2. 对非空线性表的特点是
    • 1）存在唯一的一个被称为“第一个”的数据元素
    • 2）存在唯一的一个被成为“最后一个”的数据元素
    • 3）除第一个元素外每个元素都有且只有一个前驱
    • 4）除最后一个元素外每个元素都有且只有一个后继

2 线性表功能定义

InitList (&L) 构造一个空的线性表L。

DestroyList(&L) 如果线性表L已存在。 销毁线性表L。

ClearList (&L) 如果线性表L已存在。 将L重置为空表。

ListEmpty(L) 如果线性表L已存在。 若L为空表， 则返回true, 否则返回false。

ListLength(L) 线性表L已存在。 返回L中数据元素个数（长度）。

GetElem(L,i,&e) 线性表L巳存在，且1 <= i <= ListLength(L)。 用e返回L中第i个数据元素的值。

LocateElem(L,e) 线性表L已存在。 返回L中第1个 值与e相同的元素在 L中的位置 。若这样的数据元素不存在 ， 则返回值为0。

PriorElem(L,cur_e,&pre_e) 线性表L已存在。 cur_e是L的元素且不是第一个，则用pre_e返回其前驱，否则操作失败，pre_e无定义。

NextElem(L,cur_e,&next_e) 线性表L已存在。若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败，next_e无定义。

Listinsert(&L,i,e) 线性表L已存在，且1<=i<=ListLength (L) +l。在 L中第i个位置之前插入新的数据元素 e, L的长度加1。
ListDelete(&L,i) 线性表L已存在且非空 ，且且1<=i<=ListLength (L)。删除L的第i个数据元素，L的长度减1。 TraverseList(L) 线性表L已存在。遍历线性表

3 代码实现

3.1

线性表的顺序表示是使用一组地址连续的存储单元一次存储线性表的数据元素。通常这种存储结构成为顺序表。其特点是，逻辑上相邻的数据元素， 其物理次序也是相邻的。 例如每个元素占用空间是5，假设从地址0开始，则第1个元素占用0-4号地址，第2个元素将占用5-9号地址
顺序表存储结构如下,一元多项式举例略，

#define MAXSIZE 100 //图书表最大长度

typedef struct 
{
    char no[20];//图书ISBN
    char name[50];//图书名称
    float price;//图书价格
} Book;//图书的定义

typedef struct 
{
    Book *elem;//存储空间的基地址
    int length;//图书表中当前图书个数
} SqList;//图书表的顺序存储结构类型

3.2 顺序表中基本操作实现

  1. 初始化 InitList
int InitList(SqList *L)
{
    L->elem = (Book*)malloc(MAXSIZE*(sizeof(float)+20+70));
    printf("%p\n", L->elem);
    if (L->elem==NULL)
    {
        return -1;
    }
    L->length = 0;
    return 0;
}