线性表（线性结构）
同一线性表中的元素属同一数据对象。
一个线性表可记为：
（a1,a2,……,a i-1,ai,a i+1,……,an），n>=0
n为表的长度，当n=0时，称为空表。称i为ai在线性表中的位序。a i-1是ai的直接前驱，a i+1是ai的直接后继。
ADT List{
数据对象：
数据关系：
基本操作：
}ADT List
顺序存储（随机存取）
表中逻辑上相邻的元素在存储位置上也是相邻的。“物理位置相邻”
在内存中用地址连续的一块存储空间依次存放线性表的数据元素。
用这种存储形式存储的线性表称为顺序表。
假设每个数据元素占d个存储单元，且将ai的存储地址表示为Loc(ai)，则有如下关系：
Loc(ai)=Loc(a1)+i*d
Loc(ai)是线性表的第一个数据元素a1的存储地址，通常称为线性表的基地址。只要确定了线性表的基地址，线性表中任一数据元素都可随机存取。
顺序表的类型定义：
假定线性表的数据元素的类型为 ElemType （根据实际定义为int、char等等）
#define MAXSIZE 100 //顺序表的容量
//常量MAXSIZE称为顺序表的容量，表示线性表实际可能达到的最大长度，其值通常根据具体问题的需要而定
typedef struct
{
ElemType data[MAXSIZE]; //存放顺序表的元素。数据域data是一个一维数组
int len; //顺序表的实际长度
}SqList; //顺序存储结构类型为SqList线性表基本运算在顺序表上的实现：
注意：C语言中数组的下标从“0”开始。若L是SqList类型的顺序表，则表中第i个元素是L.data[i-1]
1.初始化线性表运算
void InitList(SqList &sq)
{
sq.len=0;
}2.求线性表长度运算
int ListLength(SqList sq)
{
return(sq.len);
}3.求线性表中第i个元素运算
ElemType GetElem(SqList sq,int i)
{
if(i<1||i>sq.len) //i值不合法
return 0;
else
return(sq.data[i-1];
}4.按值查找运算
int LocateElem(SqList sq,ElemType e)
{
int i=0;
while(i<sq.len)&&(sq.data[i]!=e) i++; //将表中元素逐个与e比较
if(i>=sq.len)
return 0;
else
return i+1;
}5.插入元素运算
时间复杂度O(n)
//在表的第i(1<=i<=n+1)个位置上，插入一个新结点e sq.data[i-1]
//需要将第n至第i个元素向后移动一个位置。表长+1
int ListInsert(SqList &sq,int i,ElemType e)
{
int j;
if(i<1||i>sq.len+1) return 0; //i值不合法
for(j=sq.len;j>=i;j--) //①插入位置及之后的元素右移
sq.data[j]=sq.data[j-1];
sq.data[i-1]=e; //②插入e
sq.len++; //③表长增1
return 1;
}6.删除元素运算
时间复杂度O(n)
//删除表中第i(1<=i<=n+1)个位置上的元素 sq.data[i-1]
//将第i+1至第n个元素向前移动一个位置。表长-1
int ListDelete(SqList &sq,int i)
{
int j;
if(i<1||i>sq.len) return 0; //i值不合法
for(j=i;j<sq.len;j++) //①被删除元素之后的元素左移
sq.data[j-1]=sa.data[j];
sq.len--; //②表长-1
return 1;
}数组定义：
//数组静态分配
typedef struct{
ElemType data[MAXSIZE];
int length;
}SqList; //顺序表类型
//数组动态分配
typedef struct{
ElemType *data;
int length
}SqList; //顺序表类型
SqList L;
L.data=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);C语言的内存动态分配
需要加载头文件：<stdlib.h>
malloc(m)函数：开辟m字节长度的地址空间，并返回这段空间的首地址
sizeof(x)运算：计算变量x的长度
free(p)函数：释放指针p所指变量的存储空间，即彻底删除一个变量
C++的动态存储分配：
new 类型名T (初值列表)
int *p1=new int; 或 int *p1=new int(10);
功能：申请用于存放T类型对象的内存空间，并依初值列表赋以初值
结果值：成功：T类型的指针，指向新分配的内存。失败：0（NULL)
delete 指针p;
功能：释放指针p所指向的内存。p必须是new操作的返回值.
C++中的参数传递：
- 函数调用时传送给形参表的实参必须与形参三个一致：类型、个数、顺序
- 参数传递有两种方式：传值方式（参数为整型、实型、字符型等）
传地址：参数为指针变量、参数为引用类型、参数为数组名
线性表的链式存储结构（链表）
用一组任意的存储单元来依次存放线性表的结点。逻辑次序和物理次序不一定相同。
单链表（非随机存取）：每一个结点只有一个指针域
单链表结点结构： data next
data域是数据域，用来存放结点的值。next是指针域（也称链域），用来存放结点的直接后继的地址（或位置）。通过每个结点的指针域将线性表的n个结点按其逻辑次序连接在一起。
整个单链表的存取必须从头结点开始进行，头指针head指向第一个结点。最后一个节点无后继，指针域为空NULL。
若单链表的头指针为“空”（head=NULL），则表示线性表为“空”表，其长度为0.
为了便于一些运算的实现，在单链表的首结点之前附设一个结点，称为“头结点”。单链表的头指针指向头结点。
头结点的数据域可以不存储任何信息，也可以存储一些附加信息（如线性表的长度）。线性表非空时，头结点的指针域存储指向第一个结点的指针；线性表为空时，头结点的指针域为空。
单链表可由头指针唯一确定，在C/C++语言中，可用“结构指针”来描述。
单链表结点类型定义：
typedef struct LNode
{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;有了上述的类型定义，可以用LNode或LinkList来声明单链表头指针的类型：
LNode *head; //更常用
//或
LinkList head;
//定义链表：
LinkList L;线性表基本运算在单链表上的实现
1.初始化线性表
//创建一个空的单链表
//先创建一个头结点，并将单链表的头指针指向该头结点，然后将头结点的next域置为空，data域不设任何值。
void InitList(LinkList &h)
{
h=(LNode*)malloc(sizeof(LNode)); //c++:h=new LNode;
h->next=NULL;
}2.判断链表是否为空
int ListEmpty(LinkList L)
{
if(L->next) return 0; //非空
else return 1;
}3.清空链表
//链表仍存在，但表中无元素，称为空链表（头指针和头结点仍在）