1.1 概念

线性表是一种简单的线性结构，特点是在非空的有限集合中，且第一个元素没有直接前驱元素，最后一个元素没有直接后继元素，其他元素都有唯一的前驱和后继元素。线性表有顺序存储结构和链式存储结构。

1.2顺序存储结构

是指将线性表中的各个元素依次存放在一组地址连续的存储单元中，通常将这种方法存储的线性表称为顺序表。

假设，线性表的每个元素需占用m个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个元素的存储位置location(ai+1)和第i个元素的存储位置location(ai)之间满足关系location(ai+1)=location（ai）+m。线性表中第i个元素的存储位置与第一个元素的a1的存储位置满足以下关系，location(ai) =location(a1)+(i-1)*m。其中，第一个元素的位置location(a1)称为起始地址或基地址。

顺序表逻辑上相邻的元素在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。只要确定了第一个元素的起始位置，线性表中的任一个元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。由于C语言的数组具有随机存储特别，因此采用数组来描述顺序表。如下所示：

//顺序表结构设计
typedef struct {
    ElemType * data;
    int length;
} Sqlist;

其中，ElemType表示数据元素类型，data用于存储线性表中的数据元素的首地址，length用来表示线性表中数据元素的个数，Sqlist是结构体类型名。定义一个顺序表代码：Sqlist L; 指向顺序表的指针：Sqlist *L;

顺序表的基本运算如下：

（1）初始化线性表：

//1.1 顺序表初始化
Status InitList(Sqlist *L) {
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data =  malloc(sizeof(ElemType) *MAXSIZE);
    //存储分配失败退出
    if (!L->data) exit(ERROR);
    //空表长度为0
    L->length = 0;
    return OK;
}

（2）线性表非空判断:

int ListEmpty(Sqlist L) {
  if(L.length == 0)
    return 1;
  else
    return 0;
}

（3）按序号查找

//1.3 顺序表的取值
Status GetElem(Sqlist L, int i, ElemType *e) {
  //判断i值是否合理, 若不合理,返回ERROR
  if(i<1|| i > L.length)return  ERROR;
  //data[i-1]单元存储第i个数据元素.
  *e = L.data[i-1];
  returnOK;
}

（4）按内容查找

int GetElem(Sqlist L, ElemType e) {
  int i = 0;
  for (i=0; i<L.length; i++) {
    if L.data[I] == e
    return i+1;
   }
  return 0;
}

（5）插入操作：

//1.5顺序表的插入
/*
 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 */
Status ListInsert(Sqlist *L, int i, ElemType e) {
  //i值不合法判断
  if ((i<1) || (i>L->length+1)) return ERROR;
  //存储空间已满
  if(L->length == MAXSIZE )return ERROR;
  //插入数据不在表尾,则先移动出空余位置
  if(i <= L->length) {
    for(intj = L->length-1; j>=i-1; j--) {
      //插入位置以及之后的位置后移动1位
      L->data[j+1] = L->data[j];
    }
  }
  //将新元素e 放入第i个位置上
  L->data[i-1] = e;
  //长度+1;
  ++L->length;
  returnOK;
}

（6）删除操作

//1.6 顺序表删除
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果: 删除L的第i个数据元素,L的长度减1
 */
Status ListDelete(Sqlist *L, int i) {
  //线性表为空
  if (L->length==0)return ERROR;
  //i值不合法判断
  if ((i<1) || (i>L->length)) return ERROR;
  for(intj = i; j < L->length; j++) {
    //被删除元素之后的元素向前移动
    L->data[j-1] = L->data[j];
  }
   //表长度-1;
  L->length--;
  returnOK;
}

（7）清空操作

//1.7清空顺序表
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L) {
  L->length=0;
  return OK;
  return ERROR;
}

总结：顺序表的优缺点。
（1）优点：无须关心表中元素之间的关系，所以不用增加额外的存储空间；可以快速地取表中任意位置的元素。
（2）缺点：插入和删除操作需要移动大量元素。使用前需事先分配好内存空间，当线性表长度变化较大时，难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费，分配的空间过小，难以适应问题的需求。

1.3 线性表的链式存储

在解决实际问题时，有时并不适合采用线性表的顺序存储结构，例如两个一元多项式的相加、相乘，这就需要另一种存储结构——链式存储。它是采用一组任意的连续或非连续存储单元存储线性表的元素。为了表示每个元素ai与其直接后继ai+1的逻辑关系，链式存储不仅需要存储元素本身，还要存储一个指向其直接后继元素的地址。这种存储结构被称之为结点（node）。存储元素的叫数据域，存储地址的叫指针域。结点元素的逻辑顺序称之为线性链表或单链表。
因为第一个结点没有直接前驱结点，因此需要一个头指针指向它。为了方便操作放在第一个元素结点之前一个结点称之为头结点，头指针变成指向头结点，其数据域可以存放如线表长度等信息，而指针域则存放第一个元素结点的地址信息。若该链表为空，则头结点指针域为空。
因为，最后一个元素没有直接后继元素，所以将其指针域设置为“Null”空。
单链表的存储结构用C语言描述：

//定义结点
typedef struct Node {
  ElemType data;
  structNode*next;
} Node, *LinkList;

其中，Node是链表的结点类型，structNode是指向链表结点的指针类型。定义为：LinkList L = Node *L。

单链表的基本运算如下：

（1）初始化单链表：

//2.1 初始化单链表线性表
Status InitList(LinkList *header){
  //产生头结点,并使用L指向此头结点
  *header = (LinkList)malloc(sizeof(Node));
  //存储空间分配失败
  if(*header ==NULL)returnERROR;
  //将头结点的指针域置空
  (*header)->next=NULL;
  returnOK;
}

（2）单链表非空判断：

Status listEmpty(LinkList *header) {
  if (header->next == NULL )
  retrun OK;
  retrun ERROR;
}

（3）按序号查询操作：

//2.3 单链表取值
/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
  //j: 计数.
  intj;
  //声明结点p;
  LinkList p;
  //将结点p 指向链表L的第一个结点;
  p = L->next;
  //j计算=1;
  j =1;
  //p不为空,且计算j不等于i,则循环继续
  while(p && j<i）
    //p指向下一个结点
    p = p->next;
    ++j;
  }
  //如果p为空或者j>i,则返回error
  if(!p || j > i)returnERROR;
  //e = p所指的结点的data
  *e = p->data;
  returnOK;
}

（4）按内容查找操作：

LinkList LocateElem(LinkList header, ElemType e) {
  Node * p;
  p = header->next;
  while(p) {
    if(p->data != e) {
      p = p->next;
    } else {
      break;
    }
    return p;
  }    
}

（5）插入新数据元素e：

//2.5 单链表插入
/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
 */
Status ListInsert(LinkList *L, int i, ElemType e) {
    intj;
    LinkList p,s;
    p = *L;
    j =1;
    //寻找第i-1个结点
    while(p && j<i)
        p = p->next;
        ++j;
    }
    //第i个元素不存在
    if(!p || j>i)returnERROR;
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data= e;
    //将p的后继结点赋值给s的后继
    s->next= p->next;
    //将s赋值给p的后继
    p->next= s;
    returnOK;
}

（6）删除第i个结点：

//2.6 单链表删除元素
/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */
Status ListDelete(LinkList *L,int i,ElemType *e){
    intj;
    LinkList p,q;
    p = (*L)->next;
    j =1;
    //查找第i-1个结点,p指向该结点
    while(p->next&& j<(i-1)) {
        p = p->next;
        ++j;
    }
    //当i>n 或者 i<1 时,删除位置不合理
    if(!(p->next) || (j>i-1))return  ERROR;
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next= q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    returnOK;
}

1.4单链表与顺序表的对比

（1）存储方式：顺序表用一组连续的存储单元依次存储线性表的数据元素；而单链表用一组任意的存储单元存放线性表的数据元素。
（2）时间性能：采用循序存储结构时查找的时间复杂度为O(1)，插入和删除需要移动平均一半的数据元素，时间复杂度为O(n)。采用单链表存储结构的查找时间复杂度为O(n)，插入和删除不需要移动元素，时间复杂度仅为O(1）。
（3）空间性能：采用顺序存储结构时需要预先分配存储空间，分配空间过大会造成浪费，过小会造成问题。采用单链表存储结构时，可根据需要进行临时分配，不需要估计问题的规模大小，只要内存够就可以分配，还可以用于一些特殊情况，如一元多项的表示。