线性表：链表
链式存储分配的特点：
根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题。
链式存储结构的实现： 单链表 ， 双向链表 ，循环链表等 。
指针变量：
变量三要素：名字，内存，地址。
变量的左值，右值 ：左值指变量的内存地址 ； 右值：值
单链表
单链表是用一组任意的存储单元存储线性表的元素，这组存储单元可以连续也可以不连续，每个单元存储数据元素的同时，还必须存储其后继元素所在的地址信息，如图：
数据域和指针域组成了数据元素的存储映象，称为节点。
结点结构定义(采用模板)：
template <typename T>
struct Node
{
T data; //数据域
Node<T> *next; //指针域
};
单链表中的每个节点的存储地址存放在其前驱节点的next域中，而第一个元素无前驱，所以设头指针指向第一个元素所在的节点(称为开始节点)，整个单链表的存取必须从头指针开始进行，因而头指针具有标识一个链表的作用，由于最后一个节点无后继，所以最后一个节点(尾结点)的指针域为空，用^表示。
通常为了减少程序的复杂性和出现bug的机会，在链表的开始节点之前附设一个类型相同的结点，称为头结点。
指针变量，指针，指针所指的结点，结点的值：设p是一个指针变量，则p的值是一个指针；p是指向某个Node类型的结点，则该结点用*p表示，*p为结点变量。
在单链表中指针p由两个域组成，指针域：*p.(next)；数据域：*p.(data)；c++提供了运算符->，即可用p->data和p->next 。
单链表的实现：
template <class T>
class LinkList {
public:
LinkList ( ) {first=new Node<T>; first -> next= NULL ;}
LinkList ( T a[ ], int n ) ;
~LinkList ( ) ;
int Length ( ) ;
T Get ( int i ) ;
int Locate ( T x ) ;
void Insert ( int i, T x ) ;
T Delete ( int i ) ;
void PrintList ( ) ;
private:
Node<T> *first; };
单链表的构造-头插法：
实现代码：
template <class T>
LinkList<T>:: LinkList(T a[ ], int n) {
first=new Node<T>; //生成头结点
first->next=NULL;
Node<T> *s;
for (int i=0; i<n; i++){
s=new Node<T>;
s->data=a[i]; //为每个数组元素建立一个结点
s->next=first->next;
first->next=s;
}
}
单链表的构造-尾插法：
将新建的节点插入到链表的最后
实现代码：
template <class T>
LinkList<T>:: LinkList(T a[ ], int n) {
Node<T> *r,*s; //尾指针
first=new Node<T>; //生成头结点
r=first;
for (int i=0; i<n; i++) {
s=new Node<T>;
s->data=a[i]; //为每个数组元素建立一个结点
r->next=s; r=s; //插入到终端结点之后
}
r->next=NULL; //单链表建立完毕，将终端结点的指针域置空
}
单链表的遍历：
template <class T>
LinkList<T>:: PrintList()
{
Node<T> *p;
p=first->next;
while(p)
{
cout<<p->data;
p=p->next;
}
}
单链表中按位置查找：
查找算法：
1 工作指针P初始化，计数器初始化
2 执行下列操作，直到p为空或指向第i个节点
2.1 工作指针后移
2.2 计数器增1
3 若p为空，则第i个元素不存在，抛出位置异常；否则查找成功，返回节点p的数据元素、
实现代码：
template <class T>
T LinkList<T>::Get(int i) {
Node<T> *p; int j;
p=first->next; j=1; //或p=first; j=0;
while (p && j<i) {
p=p->next; //工作指针p后移
j++;
}
if (!p) throw "位置";
else return p->data;
}
单链表的插入操作（按位置进行插入）：
1 工作指针p初始化，计数器初始化
2 查找第i-1个节点，并使工作指针p指向该节点
3 若查找不成功（P==NULL），说明位置错误，抛出位置异常，否则
3.1 生成一个元素值为x的新节点s
3.2 将s插入到p之后
实现代码：
template <class T>
void LinkList<T>::Insert(int i, T x){
Node<T> *p; int j;
p=first ; j=0; //工作指针p初始化
while (p && j<i-1) {
p=p->next; //工作指针p后移
j++;
}
if (!p) throw "位置";
else {
Node<T> *s;
s=new Node<T>;
s->data=x; //向内存申请一个结点s，其数据域为x
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
}
}
单链表中节点的删除（删除编号是i的结点):
template <class T>
T LinkList<T>::Delete(int i){
Node<T> *p; int j;
p=first ; j=0; //工作指针p初始化
while (p && j<i-1) { //查找第i-1个结点
p=p->next;
j++;
}
if (!p || !p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在
else {
Node<T> *q; T x;
q=p->next; x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q;
return x;
}
}
析构函数：
template <class T>
LinkList<T>:: ~LinkList()
{
Node<T> *q;
while (first)
{
q=first->next;
delete first;
first=q;
}
}
若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。
对于频繁进行插入和删除的线性表， 宜采用链表做存储结构。
存储密度=结点数据本身所占的存储量/结点结构所占的存储总量
当线性表的长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
循环链表：
将单链表或者双链表的头尾结点链接起来，就是一个循环链表。从循环表中任一结点出发，都能访问到表中其他结点。
判断循环链表中尾结点的特点： q->next==first
循环链表的定义：
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class CycleLinkList{
public:
CycleLinkList( );
CycleLinkList(T a[ ], int n);
CycleLinkList(T a[ ], int n,int i);
~CycleLinkList();
int Length();
T Get(int i);
void Insert(int i, T x);
T Delete(int i);
void PrintList( );
private:
Node<T> *first;
};
空表的构造：
template <class T>
CycleLinkList<T>:: CycleLinkList( )
{
first=new Node<T>; first->next=first;
}
尾插法构造循环链表：
template <class T>
CycleLinkList<T>:: CycleLinkList(T a[ ], int n) {
first=new Node<T>; //生成头结点
Node<T> *r,*s;
r=first; //尾指针初始化
for (int i=0; i<n; i++) {
s=new Node<T>;
s->data=a[i];
r->next=s;
r=s;
}
r->next=first; //单链表建立完毕，将终端结点的指针域指向头结点
}
头插法构造循环链表：
template <class T>
CycleLinkList<T>:: CycleLinkList(T a[ ], int n,int k)
{
first=new Node<T>; //生成头结点
first->next=first;
Node<T> *s;
for (int i=1; i<n; i++)
{
s=new Node<T>;
s->data=a[i]; //为每个数组元素建立一个结点
s->next=first->next;
first->next=s;
}
}
将非循环的单链表改造成循环的单链表：
p=first;
while(p->next)
{
p=p->next;
}
p->next=first;
双链表
单链表的主要不足之处是：link字段仅仅指向后继结点，不能有效地找到前驱
双链表弥补了上述不足之处：增加一个指向前驱的指针
双链表的结点结构 ：
template <class T>
struct DNode{
T data;
DNode<T> *llink;
DNode <T>*rlink;
};
first->rlink=NULL;
first->llink=NULL;
Last=first;
双向链表的删除操作:
p->llink->rlink=p->rlink;
p->rlink->llink=p->rlink;
delete(p);
双向链表的实现:
template <class T>
class DoubleLink {
private:
Node<T> *head;
public:
DoubleLink() ；
~DoubleLink();
void Append(T data);
void Display();
void Insert(int locate , T data);
T Get(int locate);
T Delete(int locate);
};
头插:
template <class T>
void DoubleLink<T>::Append(T data){
Node<T> *s;
s=new Node<T>;
s->data=data;
s->rlink=head->rlink;
head->rlink=s;
s->llink=head;
if (s->rlink)
s->rlink->llink=s;
return;
}
遍历
template <class T>
void DoubleLink<T>::Display(){
Node <T> *p;
p=head->rlink;
while(p) {
cout<<p->data<<" ";
p=p->rlink;
}
cout<<endl;
return;
}
析构
template <class T>
DoubleLink<T>::~DoubleLink(){
Node<T> *p,*q;
p=head;
while(p)
{
q=p->rlink;
delete p;
p=q;
}
}