本课主题: 循环链表和双向链表
教学目: 掌握循环链表概念掌握双向链表表示和实现
教学重点: 双向链表表示和实现
教学难点: 双向链表存储表示
授课内容:
、复习线性链表存储结构

2、循环链表存储结构
循环链表是加种形式链式存储结构它特点是表中最后个结点指针域指向头结点

循环链表操作和线性链表基本致差别仅在于算法中循环条件不是p或p->next是否为空而是它们是否等于头指针
3、双向链表存储结构

提问:单向链表缺点是什么？
提示:如何寻找结点直接前趋
双向链表可以克服单链表单向性缺点
在双向链表结点中有两个指针域其指向直接后继另指向直接前趋
1、线性表双向链表存储结构
typedef struct DulNode{
struct DulNode *prior;
ElemType data;
struct DulNode *next;
}DulNode,*DuLinkList;
对指向双向链表任结点指针d有下面关系:
d->next->priou=d->priou->next=d
即:当前结点后继前趋是自身当前结点前趋后继也是自身
2、双向链表删除操作

Status ListDelete_DuL(DuLinkList &L, i,ElemType &e){
(!(p=GetElemP_DuL(L,i)))
 ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->pror;
free(p);
 OK;
}//ListDelete_DuL
3、双向链表插入操作

Status ListInsert_DuL(DuLinkList &L, i,ElemType &e){
(!(p=GetElemP_DuL(L,i)))
 ERROR;
(!(s=(DuLinkList)malloc((DuLNode))))  ERROR;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
 OK;
}//ListInsert_DuL
4、个完整带头结点线性边表类型定义:
typedef struct LNode{
ElemType data;
struct LNode *next;
}*Link,*Position;

typedef struct{
Link head,tail;
 len;
}LinkList;

Status MakeNode(Link &p,ElemType e);
//分配由p指向值为e结点并返回OK；若分配失败则返回ERROR
void FreeNode(Link &p);
//释放p所指结点
Status InitLinst(LinkList &L);
//构造个空线性链表L
Status DestroyLinst(LinkList &L);
//销毁线性链表LL不再存在
Status ClearList(LinkList &L);
//将线性链表L重置为空表并释放原链表结点空间
Status InsFirst(Link h,Link s);
//已知h指向线性链表头结点将s所指结点插入在第个结点的前
Status DelFirst(Link h,Link &q);
//已知h指向线性链表头结点删除链表中第个结点并以q返回
Status Append(LinkList &L,Link s);
//将指针s所指(彼此以指针相链)串结点链接在线性链表L最后个结点
//的后并改变链表L尾指针指向新尾结点
Status Remove(LinkList &L,Link &q);
//删除线性链表L中尾结点并以q返回改变链表L尾指针指向新尾结点
Status InsBefore(LinkList &L,Link &p,Link s);
//已知p指向线性链表L中个结点将s所指结点插入在p所指结点的前
//并修改指针p指向新插入结点
Status InsAfter(LinkList &L,Link &p,Link s);
//已知p指向线性链表L中个结点将s所指结点插入在p所指结点的后
//并修改指针p指向新插入结点
Status SetCurElem(Link &p,ElemType e);
//已知p指向线性链表中个结点用e更新p所指结点中数据元素值
ElemType GetCurElem(Link p);
//已知p指向线性链表中个结点返回p所指结点中数据元素值
Status ListEmpty(LinkList L);
//若线性链表L为空表则返回TRUE,否则返回FALSE
 ListLength(LinkList L);
//返回线性链表L中元素个数
Position GetHead(LinkList L);
//返回线性链表L中头结点位置
Position GetLast(LinkList L);
//返回线性链表L中最后个结点位置
Position PriorPos(LinkList L,Link p);
//已知p指向线性链表L中个结点返回p所指结点直接前趋值
//若无前趋返回NULL
Position NextPos(LinkList L,Link p);
//已知p指向线性链表L中个结点返回p所指结点直接后继值
//若无后继返回NULL
Status LocatePos(LinkList L, i,Link &p);
//返回p指示线性链表L中第i个结点位置并返回OK,i值不合法时返回ERROR
Position LocateElem(LinkList L,ElemType e,
Status(*compare)(ElemType,ElemType));
//返回线性链表L中第1个和e满足compare判定关系元素位置
//若下存在这样元素则返回NULL
Status ListTraverse(LinkList L,Status(*visit));
//依次对L每个元素visit旦visit失败则操作失败
5、整理总结本课内容
循环链表存储结构
双向链表存储结构