1.线性表：由n（n >= 0 ）个数据特性相同的元素构成的有限序列成为线性表，元素个数n定义为线性表的长度，n=0时称为空表；
a,存在唯一被称为“第一个”的数据元素
b,存在唯一被称为“最后一个”的数据元素
c,除第一个外，结构中的每个数据元素均只有一个前驱
d,除最后一个外，结构中的每个数据元素均只有一个后继
2,线性表的顺序表示：是用一组地址连续的存储单元依次存储线性表的数据元素， 这种存储结构的线性表为顺序表逻辑上相邻的数据元素， 其物理次序也是相邻的
3,线性表链式存储结构：用一组任意的存储单元存储线性表的数据元素（单元可连续、可不连续），除了存储本身信息外，还需存储一个指示后继存储位置的信息，这两部分组成数据元素的结点(node)，其中包括存储数据元素信息的 数据域 和 存储直接后继存储位置的 指针域 ，指针域中存储的信息称作 指针 或 链，n个结点链结成一个链表（线性表的链式存储结构），此链表的每个结点只包含一个指针域，故称 线性链表/单链表;
4.单链表
a.单链表初始化
i.构造一个空的链表
ii.生成新节点作为头节点，用头指针指向头结点
iii.头结点指针域置空
Status InitList(LinkList &L) { L = new LNode; L->next = NULL; return ok; }
b.取值：和顺序表不同，链表中逻辑相邻的节点并没有存储在物理相邻的单元中，只能从链表的首元结点出发，顺着链域next逐个结点向下访问;
i.用指针p指向首元结点，用j做计数器初始值赋为1;
ii.从首元结点开始依次顺着链域 next 向下访问，只要指向当前结点的指针 p 不为NULL, 并且没有到达序号为i的结点，则循环执行:
1.p指向下一个结点；
2.计数器j相应加1。
iii.退出循环时， 如果指针p为空， 或者计数器j>i, 说明指定的序号i值不合法; 否则取值成功， 此时j=i时，p所指的结点就 是要找的第i个结点;
/ /在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值 Status GetElem(LinkList L, int i, ElemType &e) { p = L->next; j = 1; while(p && j<i) { p = p->next; ++j; } if(!p || j>i) { return ERROR; } e = p->data; return OK; }
c.查找
i.用指针p指向首元结点 ;
ii.从首元结点开始依次顺着链域next向下查找， 只要指向当前结点的指针p不为空， 并且p所指结点的数据域不等千给定值e, 则循环执行以下操作： p指向下一个结点 ;
ii.返回p,若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL
LNode *LocateELem(LinkList L, Elemtype e) ｛ p=L->next; while(p && p->data!=e) p=p->next; return p; }
d.插入
i.查找结点a, 并由指针p指向该结点的前一结点
ii.生成一个新结点*s
iii.将新结点*s 的数据域置为 e
iv.将新结点*s 的指针域指向结点a
v.将结点*p 的指针域指向新结点*s
Status ListInsert(LinkList &L, int i, ElemType e) { p = L; j = 0; while(p && (j<i-1)) { p = p->next; ++j; } if(!p || j>i-1) return ERROR; s = new LNode; s->data = e; s->next = p->next; p->next = s; return OK; }
e.删除
i.查找结点a并由指针p指向该结点的前一结点
ii.临时保存待删除结点a的地址在q中 ，以备释放
iii.将结点*p的指针域指向a的直接后继结点
iv释放结点a的空间
Status ListDelect(LinkList &L, int i, ElemType e) { p = L; j = 0; while(p->next && j<i-1) { p = p->next; ++j; } if(!p->next || j>i-1) return ERROR; q = p->next; p->next = q->next; delect q; return OK; }
f.前插法
i.创建一个只有头结点的空链表
ii.根据待创建链表元素个数n, 循环n次
iii.生成一个新结点*p
iv.输入元素值赋给新结点*p的数据域
v.将新结点*p插入到头结点之后
void CreateList_H(LinkList &L, int n) { L = new LNode; L->next = NULL; for(int i = 0; i < n; i++) { p = new LNode; cin >> p->data; p->next = L->next; L->next = p; } }
g.后插法
i.创建一个只有头结点的空链表
ii.尾指针r初始化， 指向头结点
iii.根据创建链表包括的元素个数n, 循环n次
1.生成一个新结点*p
2.输入元素值赋给新结点*p 的数据域
3.将新结点*p 插入到尾结点*r之后
4.尾指针r指向新的尾结点*p
void CreateList_R(LinkList &L, int n) { L = new LNode; r = L; for(int i = 0; i < n; i++) { p = new LNode; cin >> p->data; p->next = NULL; r->next = p; r = p; } }
5.循环链表：最后一个节点的指针域指向头节点，整个链表形成一个环，判别终止条件从指针域是否指向NULL 变为 是否指向L(头结点)
6.双向链表：在双向链表的结点中有两个指针域，一个指向直接后继，一个指向直接前驱;
typedef struct DuLNode { ElemType data; //数据域 struct DuLNode *prior //直接前驱 struct DuLNode *next //直接后继 }DuLNode, *DuLinkList;
a.双向链表的插入
//在双向链表L中第i个位置之前插入元素e Status ListInsert_DuL(DuLinkList &L, int n, ElemType e) { if (1 (p=GetElem_DuL (L, i))) //在L中确定第i个元素的位置指针p return ERROR; //p为 NULL 时，第i个元素不存在 s = new DuLNode; s->data = e; s->prior = p->prior; //将结点*s插入L中 p->prior->next = s; s->next = p; p->prior = s; return OK; }
b.双向链表的删除
//删除双向链表L中的第i个元素 Status ListDelete_DuL(DuLinkList &L,int i) { if (!(p=GetElem_DuL(L, i))) //在L中确定第i个元素的位置指针p return ERROR; //p为 NULL 时，第i个元素不存在 p->prior->next = p->next; //修改被删结点的前驱结点的后继指针 p->next->prior = p->prior; //修改被删结点的后继结点的前驱指针 delete p; //释放被删结点的空间 return OK; }
7.空问性能
a.顺序表的存储空间必须预先分配，链表不需要为其预先分配空间,当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。
b.链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，如果每个元素数据域占据的空间较小，则指针的结构性开销就占用了整个结点的大部分空间，当线性表的长度易于事先确定其大小时，宜采用顺序表作为存储结构。
8.时间性能
a.顺序表是由数组实现，指定任意一个位置序号i都可以接存取该位置上的元素;
b.链表是一种顺序存取结构，访问链表中第i个元素时，只能从表头开始依次向后遍历链表;
c.对于链表，在确定插入或删除的位置后只需要修改指针；
d.对于顺序表，进行插入或删除时，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观；
e.对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构；很少做插入或删除时宜采用顺序表作为存储结构。
