前言:
循环链表:是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成了一个环。因此,从表中任意节点出发均可找到表中的其他结点。
双向链表:前讨论的链式存储结构中个,每个结点都只有一个指示其后继元素的指针域,那么找下一个元素(NextElem) 的时间复杂度 为 O(1)。但是寻找直接前继元素必须要从头结点开始找,PriorElem 的时间复杂度为 O(n)。为了克服单链表的这种单向性缺点,我们在此使用一种新的链式存储结构:双向链表。
目录:
1.线性表的链式表示和实现
1.1线性链表
单链表(指针型线性链表)
静态链表
1.2循环链表
1.3双向链表
正文:
1.2循环链表(circular linked list)
循环链表的操作 和 链表的操作基本一致,差别在于循环的结束条件,链表:p->next 是否为NULL 循环链表:p->next 是否等于头指针。
但是,很多时候在循环链表中设置 尾指针 而不是 头指针,可以简化某些操作。例如:合并两个线性表时,仅需将一个表的表尾和另一个表的表头连接即可。
1.3双向链表(double linked list)
顾名思义,双向链表的结点中包含两个指针域,一个指向直接前驱,另一个指向直接后继。
在C语言中可描述如下:
typedef struct DuLNode{
ElemType data;
struct DuLNode * prior;
struct DuLNode * next;
}DuLNode, * DuLinkList;
双向链表也可以有循环链表:
若d 为指向双向链表一个元素的指针 (即d 为 DuLinkList类型) ,则有:
d->next->prior=d->prior->next=d;
在双向链表中,有些操作如:ListLenght ,GetElem 和LocateElem等仅需要一个方向的指针,则他们的算法描述和 线性表的操作相同。
但是在插入 和删除时会有很大的不同,此时要同时修改两个方向上的指针。
代码实现:(双向链表的插入和删除,由于插入或删除可能需要同时修改前驱和后继的指向,因此非常容易出错)
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//链表的最大长度
#define MAXSIZE 100
//Status是函数的类型,其值是函数结果状态码
typedef int Status;
typedef int ElemType;
typedef struct DuLNode{
ElemType data;
struct DuLNode * prior;
struct DuLNode * next;
}DuLNode, * DuLinkList;
//插入操作
Status ListInsert_DuL(DuLinkList &Dul,int i,ElemType e){
DuLNode *q=Dul; //q指向头结点
int j=0;
while(q->next&&j<(i-1)){
q=q->next;
j++;
}
if(!q||i<0)
return ERROR;
//此时 q 指向 i 的直接前驱
DuLNode * node=(DuLinkList)malloc(sizeof(DuLNode));
node->data=e;
//注意:如果 i 不是追加的尾部,则需要修改 i 处元素的 前驱指针
if(q->next){
q->next->prior=node;
}
node->next=q->next;
node->prior=q;
q->next=node;
return OK;
}
//删除操作
Status ListDelete_DuL(DuLinkList &Dul,int i,ElemType &e){
DuLNode *q=Dul; //q指向头结点
int j=0;
while(q->next&&j<i){
q=q->next;
j++;
}
if(!q||i<0)
return ERROR;
//执行删除操作
q->prior->next=q->next;
//注意:如果 i 不是追加的尾部,则需要修改 i 处元素的 前驱指针
if(q->next)
q->next->prior=q->prior;
free(q);
return OK;
}
//打印所有元素
void PrintAllValues(DuLinkList &Dul){
DuLNode *q=Dul; //q指向头结点
while(q->next){
printf("前驱:%d,",q->next->prior);
printf("值:%d,",q->next->data);
printf("后继:%d
",q->next->next);
q=q->next;
}
}
void main(){
DuLNode * Dul;
Dul=(DuLinkList)malloc(sizeof(DuLNode));
Dul->next=NULL;
ListInsert_DuL(Dul,1,7);
ListInsert_DuL(Dul,1,5);
ListInsert_DuL(Dul,1,4);
ListInsert_DuL(Dul,1,1);
PrintAllValues(Dul);
ElemType e;
ListDelete_DuL(Dul,3,e);
printf("%s
","删除第3个元素");
PrintAllValues(Dul);
}
运行结果:
1、错误实例:
错误原因:虽然成功的删除了双向链表的 第 3 个元素,但是 忘记修改第 4 个元素的 前驱指针。
2.正确为: