数据结构的练习day2(未完待续)

  • 数据结构的练习day2(未完待续)已关闭评论
  • 41 次浏览
  • A+
所属分类:linux技术
摘要

数据结构线性结构之单向循环链表的基本操作

数据结构线性结构之单向循环链表的基本操作

/********************************************************************************************************  *  *  * 设计单向循环链表的接口  *  *  *  * Copyright (c)  2023-2024   [email protected]   All right Reserved  * ******************************************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <stdbool.h>  // 指的是单向循环链表中的结点有效数据类型,用户可以根据需要进行修改 typedef int DataType_t;  // 构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的 typedef struct CircularLinkedList { 	DataType_t data;								 // 结点的数据域 	struct CircularLinkedList *next; // 结点的指针域  } CircLList_t;  // 遍历链表 bool CircLList_Print(CircLList_t *Head) { 	// 对单向循环链表的头结点的地址进行备份 	CircLList_t *Phead = Head;  	// 判断当前链表是否为空,为空则直接退出 	if (Head->next == Head) 	{ 		printf("current linkeflist is empty!n"); 		return false; 	}  	// 从首结点开始遍历 	while (Phead->next) 	{ 		// 把头结点的直接后继作为新的头结点 		Phead = Phead->next; 		// 输出头结点的直接后继的数据域 		printf("data = %dn", Phead->data);  		// 判断是否到达尾结点,尾结点的next指针是指向首结点的地址 		if (Phead->next == Head->next) 		{ 			break; 		} 	}  	return true; } // 创建一个空单向循环链表,空链表应该有一个头结点,对链表进行初始化 CircLList_t *CircLList_Create(void) { 	// 1.创建一个头结点并对头结点申请内存 	CircLList_t *Head = (CircLList_t *)calloc(1, sizeof(CircLList_t)); 	if (NULL == Head) 	{ 		perror("Calloc memory for Head is Failed"); 		exit(-1); 	}  	// 2.对头结点进行初始化,头结点是不存储数据域,指针域指向自身,体现“循环”思想 	Head->next = Head;  	// 3.把头结点的地址返回即可 	return Head; }  // 创建新的结点,并对新结点进行初始化(数据域 + 指针域) CircLList_t *CircLList_NewNode(DataType_t data) { 	// 1.创建一个新结点并对新结点申请内存 	CircLList_t *New = (CircLList_t *)calloc(1, sizeof(CircLList_t)); 	if (NULL == New) 	{ 		perror("Calloc memory for NewNode is Failed"); 		return NULL; 	}  	// 2.对新结点的数据域和指针域进行初始化 	New->data = data; 	New->next = NULL;  	return New; }  // 头插 bool CircLList_HeadInsert(CircLList_t *Head, DataType_t data) { 	if (Head == NULL) 	{ 		printf("链表为空!n"); 		return false; 	} 	// 创建一个指针代替Head 	CircLList_t *phead = Head; 	// 新建一个结点 	CircLList_t *newNode = CircLList_NewNode(data); 	// 让新建的结点指向原来的首结点 	newNode->next = phead->next; 	// 让头结点指向新建的结点 	phead->next = newNode; 	return true; }  // 尾插 bool CircLList_TailInsert(CircLList_t *Head, DataType_t data) { 	if (Head == NULL) 	{ 		printf("链表为空!n"); 		return false; 	} 	// 创建一个指针代替Head 	CircLList_t *phead = Head->next; 	// 新建一个结点 	CircLList_t *newNode = CircLList_NewNode(data);  	while (phead->next != Head) 	{ 		phead = phead->next; 		if (phead->next == Head->next) 		{ 			break; 		} 	} 	//  尾结点指向新结点 	phead->next = newNode; 	// 新结点指向首结点 	newNode->next = Head->next; 	return true; }  // 指定位置插入(后插) bool CircLList_DestInsert(CircLList_t *Head, DataType_t destval, DataType_t data) { 	if (Head == NULL) 	{ 		printf("链表为空!n"); 		return false; 	} 	// 创建一个指针代替Head 	CircLList_t *phead = Head; 	// 新建一个结点 	CircLList_t *newNode = CircLList_NewNode(data); 	while (phead) 	{ 		// 找到目标结点的上前结点 		if (phead->next->data == destval) 		{ 			break; 		} 		phead = phead->next; 	} 	newNode->next = phead->next; 	phead->next = newNode; }  // 头删 bool CircLList_HeadDel(CircLList_t *Head) { 	// 对单向循环链表的首结点的地址进行备份 	CircLList_t *Phead = Head->next; 	while (Phead->next != Head) 	{ 		if (Phead->next == Head->next) 		{ 			break; 		} 		Phead = Phead->next; 	} 	Phead->next = Head->next->next; 	Phead = Head->next; 	Head->next = Head->next->next; 	Phead->next = NULL; 	free(Phead); 	return true; }  // 尾删 bool CircLList_TailDel(CircLList_t *Head) { 	// 对单向循环链表的首结点的地址进行备份 	CircLList_t *phead = Head->next; 	// 找到尾结点的前一个结点 	while (phead->next->next != Head) 	{ 		if (phead->next->next == Head->next) 		{ 			break; 		} 		phead = phead->next; 	} 	phead->next->next = NULL; 	free(phead->next); 	phead->next = Head->next;  	return true; }  // 指定数据的结点删除(后删) bool CircLList_DestDes(CircLList_t *Head, DataType_t destval) { 	// 对单向循环链表的首结点的地址进行备份 	CircLList_t *phead = Head->next; 	// 前结点 	CircLList_t *preNode = Head; 	// 要删除的结点 	CircLList_t *delNode = Head->next; 	while (phead->next != Head) 	{ 		if (delNode->data == destval) 		{ 			break; 		} 		preNode = delNode; 		delNode = delNode->next; 	} 	preNode->next = delNode->next; 	delNode->next = NULL; 	free(delNode); 	return true; } int main(int argc, char const *argv[]) { 	CircLList_t *Head = CircLList_Create();  	CircLList_HeadInsert(Head, 40); 	CircLList_HeadInsert(Head, 30); 	CircLList_HeadInsert(Head, 20); 	CircLList_HeadInsert(Head, 10);  	CircLList_TailInsert(Head, 50); 	CircLList_DestInsert(Head, 30, 15); 	CircLList_HeadDel(Head); 	CircLList_Print(Head); 	CircLList_TailDel(Head); 	CircLList_DestDes(Head, 20); 	CircLList_Print(Head); 	return 0; }