欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【数据结构】双链表和循环链表的相关操作--创建-插入-删除-查找

程序员文章站 2022-03-22 19:52:39
...

双链表与循环链表

双链表

单链表 VS 双链表

  • 单链表:无法逆向检索,有时候不太方便
  • 双链表:可进可退,存储密度更低一点
  • 总结:单链表结点中,只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。为了克服单链表此缺点,引入了双链表,双链表结点两个指针分别指向其前驱结点和后继结点。

双链表的初始化(带头结点)

typedef struct DNode {
	ElemType data;
	struct DNode *prior,*next;
}DNode,*DLinklist;

//初始化双链表
bool InitDLinklist (DLinklist &L) {
	L = (DNode *)malloc(sizeof(DNode));	//分配一个头结点
	if (L == NULL) {				  	//内存不足,分配失败 
		return false;
	} 
	L -> prior = NULL;					//头结点的prior永远指向NULL 
	L -> next = NULL;					//头结点之后暂时没有结点 
	return true;
}

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L) {
	if (L -> next == NULL) {
		return true;
	}else {
		return false;
	}
} 

双链表的插入

  • 因为双链表在单链表的基础上,为结点增加了前驱结点指针,故在进行插入操作时,也要根据链的变化对前驱结点指针进行修改,关键是保证在修改的过程中不断链。
//双链表的插入操作 
//在p结点之后插入s结点 
bool InsertNextDNode (DNode *p, DNode *s) {
	if (p == NULL || s == NULL) {		//非法参数 
		return false;
	}
	s -> next = p -> next;
	if (p -> next != NULL) {			//若p结点有后继结点 
		p -> next -> prior = s; 
	}
	s -> prior = p;
	p -> next = s;
	return true;
}
  • 前插操作:由于双链表的结点有两个指针,分别指向该结点的前驱结点和后继结点,故要进行前插操作时,只需找到其前驱结点,并对其前驱结点实施后插操作,即可达到对结点的前插操作。

双链表的删除

//双链表的删除 
//删除p结点的后继结点
bool DeleteNextDNode (DNode *p) {
	if (p == NULL) {
		return false;
	}
	DNode *q = p -> next;		//找到p的后继结点q 
	if (q == NULL) {
		return false;			//p没有后继结点 
	}
	p -> next = q -> next;
	if (q -> next != NULL) {	//q结点不是最后一个结点 
		q -> next -> prior = p;
	}
	free(q);					//释放结点空间 
	return true;
} 

//销毁一个双链表
void Destory (DLinklist &L) {
	//循环释放各个数据结点
	while (L -> next != NULL) {
		DeleteNextDNode(L);
	} 
	free(L);	//释放头结点 
	L = NULL;	//头结点指向NULL 
} 

双链表的遍历

//后向遍历 
while (p != NULL) {
	//对结点p作相应处理
	p = p -> next; 
}

//前向遍历
while (p != NULL) {
	//对结点p做相应处理 
	p = p -> prior; 
} 

//前向遍历(跳过头结点)
while (p -> prior != NULL) {
	//对结点p做相应处理
	p = p -> prior; 
} 

循环链表

循环单链表

  • 循环单链表:将单链表尾结点的next指针指向NULL改为指向单链表的头结点
  • 从一个结点出发可以找到其他任何一个结点
typedef struct LNode {  //定义单链表结点类型 
	ElemType data;	    //每个结点存放一个数据元素 
	struct LNode *next;	//指针指向下一个结点 
}LNode,*LinkList;	    //强调为结点和强调为单链表 

//初始化一个空的循环单链表
bool InitLink(LinkList &L) {
	L = (LNode *)malloc(sizeof(LNode));	//分配一个头结点
	if(L == NULL) {	                    //内存不足,分配失败 
		return false; 
	}
	L->next = L;	                    //头结点next指针指向头结点 
	return true;
} 

//判断循环单链表是否为空
bool Empty(LinkList L) {
	if(L->next == L) {
		return true;
	}else {
		return false;
	}
}

//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p) {
	if(p->next == L) {
		return true;
	}else {
		return false;
	}
}

循环双链表

  • 将双链表表尾结点的next指向头结点,将头结点的prior指向表尾结点,形成了循环
typedef struct DNode {
	ElemType data;
	struct DNode *prior,*next;
}DNode,*DLinklist;

//初始化双链表
bool InitDLinklist (DLinklist &L) {
	L = (DNode *)malloc(sizeof(DNode));	//分配一个头结点
	if (L == NULL) {				  	//内存不足,分配失败 
		return false;
	} 
	L -> prior = L;					//头结点的prior指向头结点
	L -> next = L;					//头结点的next指向头结点 
	return true;
}

//判断双链表是否为空(带头结点)
bool Empty(DLinklist L) {
	if (L -> next == L) {
		return true;
	}else {
		return false;
	}
} 

静态链表

静态链表的创建

  • 静态链表借助数组来描述线性表的链式存储结构,结点也有数据域data和指针域next,与之前的链表指针不同的是,今天链表的指针是结点的相对地址(数组下标),又称作游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。
#define MaxSize 50		//静态链表的最大长度 
typedef struct {		//静态链表结构类型的定义 
	ElemType data;		//存储数据元素 
	int next;			//下一个元素的数组下标 
}SLinkList [MaxSize]; 

#define MaxSize 50		//静态链表的最大长度 
struct Node {		//静态链表结构类型的定义 
	ElemType data;		//存储数据元素 
	int next;			//下一个元素的数组下标 
};
typedef struct Node SLinkList [MaxSize];