2.3线性表的链式存储结构及实现链式存储分配的特点：

根据线性表的长度动态的申请存储空间，以解决顺序存储中存在的存储空间难以确定的问题。 链式存储结构的实现： 单链表 双向链表 循环链表等

指针变量的特点： 变量的三要素： 名字，内存地址，值 变量的左值，右值： 左值指变量的内存地址 右值：值 在赋值表达式中，赋值号左边需要左值，右边需要右值；如a=a+100 指针变量： 指针变量的右值本身又是一个左值。

2.3.1单链表

通过指针把它的一串存储结点链接成一个链 存储结点由两部分组成： data字段 link字段 链表节点数据类型的定义：`

template <typename T> struct Node { 　　T data; 　　Node<T> *next; //此处<T>也可以省略 }; 单链表的实现： 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; // 单链表的头指针 , <T>可以省略 };

头插法： 建空表——申请新结点并赋值——插入第一个结点——插入第n个结点

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; } } 不带头结点的单链表的构造：

头插法：

template <class T> LinkList<T>:: LinkList(T a[ ], int n) { first=NULL; for(int i=0;i<n;i++) { s=new node<T>; s->data=a[i]; s->next=first; first=s; } }

尾插法：

template <class T> LinkList<T>:: LinkList(T a[ ], int n) { node<T> *r; head=NULL; if（n<=0）return; s=new node<T>; s->data=a[0]; s->next=head; head=s; r=head; for(int i=1;i<n;i++) { s=new node<T>; s->data=a[i]; r->next=s; r=s; } }

按位置查找： 算法： 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; } }

不带头结点的插入：

Insert(int i, T x){ Node<T> *p; int j; if（i<=0） throw “位置非法”； if （i==1 ）{ s=new Node<T>;s->next=head;head=s;return} p=first ; j=1; //工作指针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; } }

删除： 算法： 1、工作指针p初始化；累加器j清零； 2、查找第i-1个结点并使工作指针p指向该节点； 3、若p不存在或p的后继结点不存在，抛出位置异常；否则， 3、1 暂存被删结点和被删元素； 3、2 摘链，将结点p的后继结点从链表上摘下； 3、3 释放被删结点； 3、4 返回被删元素值；

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; } }

2.5.1循环链表

特点： 首尾相接的链表。 可以从任一节点出发，访问链表中的所有节点。 判断循环链表中尾结点的特点： 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; } }

2.5.2双链表

由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立： p->llink->rlink = p = p->rlink->llink 实现：

template <class T> struct DNode{ T data; DNode<T> *llink; DNode <T>*rlink; }; 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> DoubleLink <T>::DoubleLink(){ head=new Node<T>; head->rlink=NULL; head->llink=NULL; }

头插法构造：

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; } }