作者在 2008-10-18 14:17:53 发布以下内容
1.循环链表
(1)循环链表的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。
(2)循环链表的判空的条件 L->next=L
(3)有些时候在循环链表中设立尾结点而不设头结点（两个循环链表的合并）
Linklist union（La，Lb）//将rb链接到rb后
{linklist ra,rb，p; //尾结点p为表Lb的头结点
p=rb->next;
rb->next=ra->next;
ra->next=p->next；
free（p）；
}
2.双链表
(1)判空条件 L->next=L->prior=L;
(2)双链表的存储结构
typedef struct DuLNode
{elemtype data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode;*Dulinklist;
(3)插入第i个元素之前
DuLinkList ListInsert_DuL(DuLinkList &L, int i, ElemType e)
{ // 在带头结点的双链循环线性表L中第i个位置之前插入元素e，
// i的合法值为1≤i≤表长+1。
if(!(p=GetElemP_DuL(L,i))) // 在L中确定插入位置指针p
return ERROR; // i等于表长加1时，p指向头结点；i大于表长加1时，p=NULL。
if((s=(DuLinkList)malloc(sizeof(DuLNode))==NULL)
return ERROR;
s->data=e;
s->next=p->next;
// i的合法值为1≤i≤表长+1。
if(!(p=GetElemP_DuL(L,i))) // 在L中确定插入位置指针p
return ERROR; // i等于表长加1时，p指向头结点；i大于表长加1时，p=NULL。
if((s=(DuLinkList)malloc(sizeof(DuLNode))==NULL)
return ERROR;
s->data=e;
s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
return OK;
}
return OK;
}
(4)删除第i个元素
Dulinklist ListDelete_DuL(DuLinkList &L, int i, ElemType &e)
{ // 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
if(!(p=GetElemP_DuL(L,i))) // 在L中确定第i个元素的位置指针p
return ERROR; // p=NULL,即第i个元素不存在
e=p->data;
p->next=p->next->next;
if(!(p=GetElemP_DuL(L,i))) // 在L中确定第i个元素的位置指针p
return ERROR; // p=NULL,即第i个元素不存在
e=p->data;
p->next=p->next->next;
p->next->p->prior=p;
free(p); return OK;
}
}