数据结构线性表循环链表的基本功能实现

循环链表的实现

内容全部为我自己学习过程中的自己的感受,如果存在错误的情况希望可以与我交流

由于循环链表与其余链表的剩余功能基本相似,因此只实现了循环链表的初始化,创建,遍历,按位查找以及两链表的连接

循环链表与普通链表的区别在于普通链表判断指向标为节点的终止条件不同,普通链表的终止条件为p->next==NULL而在循环链表中的判断终止条件为p->next==L,其中L为头节点.
使用c语言实现的代码如下所示

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1

/*
实现功能::循环链表的实现 ,循环链表的遍历,循环链表的按位查找,两循环链表的连接 
如果仅仅通过LinkList去创建一个节点的话,此时节点并没有被分配内存空间,此时新建的节点不能被赋予data的值,可以通过LinkList p;  p=new LNode;
去为新建并分配内存空间,也可以直接通过 LinkList p = (Link List)malloc(sizeof(LinkList))去新建并服与内存空间 
*/

typedef int ElemType;

typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

void CreatList(LinkList &L);
void TravelList(LinkList L);
ElemType InitList(LinkList &L);
void LocateList(LinkList L);
void CombineList(LinkList &L1,LinkList &L2);

int main()
{
	//建立链表A 
	LinkList A,B;
	InitList(A);
	CreatList(A);
	TravelList(A);
	
	InitList(B);
	CreatList(B);
	TravelList(B);
	
	CombineList(A,B);
	TravelList(A);
	return 0;
}

ElemType InitList(LinkList &L){
	L=new LNode;
	L->next=L;
	return OK;
}

void CreatList(LinkList &L){
	int n,a;
	//p始终存储头节点,r用来存储插入节点前的最后一个元素,q用来存储新插入的节点 
	
	LinkList Head=L,Move=L;
	
	printf("请输入需要插入的元素的个数:");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		LinkList Insert;
		Insert =new LNode;
//		LinkList Insert = (LinkList)malloc(sizeof(LinkList));
		scanf("%d",&a);
		Insert->data=a;
		Insert->next=Head;
		Move->next=Insert;
		Move=Insert;
	}
}

void TravelList(LinkList L){
	int i=1;
	LinkList p=L->next;
	while(p!=L)
	{
		printf("第%d个元素的值为%d\n",i,p->data);
		i++;
		p=p->next;
	}
}

void LocateList(LinkList L){
	/*
	因为循环链表内不会出现next为空的情况,所以不需要判断p->next会为空的情况
	*/
	int i,j;
	LinkList p=L->next;
	printf("输入需要取出的元素的位置:");
	scanf("%d",&i);
	for(j=i-1;j>0;j--)
	{
		p=p->next;
	}
	printf("第%d个元素的值为%d\n",i,p->data);
}

void CombineList(LinkList &L1,LinkList &L2){
	printf("连接开始...\n");
	//Head1,2分别为两个循环链表的头节点,Tail1,2分别为两个链表的尾结点
	//Bridge用来连接两个循环链表. 
	LinkList Head1=L1,Head2=L2,Tail1=L1,Tail2=L2,Bridge;
	//通过while寻找两链表的尾节点,判断条件为节点的next是否为头节点
	//连接后将 
	while(Tail1->next!=Head1){
		Tail1=Tail1->next;
	}
	while(Tail2->next!=Head2){
		Tail2=Tail2->next;
	}
	
	//存储2链表的第一个元素 
	Bridge=Head2->next;
	//将2链表的最后一个元素指向1链表的头节点 
	Tail2->next=Tail1->next;
	//将1节点的最后一个元素指向2链表的第一个元素 
	Tail1->next=Bridge;
}

[参考文档]
数据结构c语言版