循环链表

在这里插入图片描述

// 两个头指针为 LA,LB 的循环单链表合并为一个循环单链表 
Linklist merge_1(Linklist LA,Linklist LB){
	Linklist RA=LA;
	Linklist RB=LB;
	while(RA->next!=LA) RA=RA->next;		// 此时 RA,RB 为尾指针 改变其 next 指向就可完成合并。 
	while(RB->next!=LB) RB=RB->next;
	RA->next=LB->next;
	RB->next=LA;
	free(LB);
	return LA;
}

在这里插入图片描述

// 两尾指针为 RA,RB 的循环单链表合并 
Linklist Merge_2(Linklist RA,Linklist RB){
	LInklist P=RA->next;			// 预存 
	RA->next=RB->next->next;
	free(RB->next);
	RB->next=P;
	return RB;
}

有尾指针很容易找到头指针，但是有头指针不是很方便找尾指针。
所以循环单链表一般习惯带尾指针。

双向链表

在单链表中，查找前驱节点不方便。

// 在每个节点里增加一个指向其前驱的指针域 prior 
typedef int Datatype;
typedef struct node{
	Datatype data;
	struct node *prior,*next;
}Node,*Linklist;

在这里插入图片描述

创建

建立前驱关系

尾插

// r 是尾指针
r->next=pNew;				// 建立后继关系 
pNew->prior=r;			// 建立前驱关系 
r=pNew;			// 更新 r

插入

前插操作
在P结点之前插入

p->prior->next=pNew;
p->prior=pNew;
pNew->prior=p->prior;
pNew->next=p;

删除

删除P指向的节点。

p->prior->next=p->next;
p->next->prior=p->prior;
free(p);

静态链表

有些语言并没有提供指针这种数据类型，想要使用链表结构，可以采用数组来模拟实现链表。
在这个数组里，物理上相邻的数据元素逻辑上并不一定相邻。
定义一个较大的数组作为节点空间的存储池。

# define Maxsize 10
typedef int Datatype;
typedef struct SNode{
	Datatype data;
	int next;
}Snode,StaticList[Maxsize+1]; 
// Staticlist代表的是 struct SNode [11] 类型, 数组中每个元素都是一个 struct SNode

StaticList L;

L[8].next=6		// 说明 后驱为 L[6]

在这里插入图片描述

静态链表中，还需要有一条连接各个空闲位置的链表，称为备用链表。

查找

// 以 body 为头节点的链表,查找 数值域为 elem 的节点在数组中的位置 
int find_data(StaticList L,int body,char elem){
	while(L[body].next){
		if(L[body].data==elem){
			return body;
		}
		body=L[body].next;
	}
	return -1; 			// 表示没找到 
}