【免费】c语言实现循环链表的源代码资源-CSDN文库

共4个文件

h：2个

c：2个

需积分: 0 32 浏览量 2023-03-24 10:29:00 上传评论收藏 5KB RAR 举报

循环链表是数据结构中的一种，它在链表的基础上增加了一个特性，即最后一个节点的指针指向了链表的第一个节点，形成一个环状结构。在C语言中，我们可以使用结构体来表示链表的节点，并通过指针操作来实现各种链表操作。下面将详细介绍循环链表的定义、初始化、节点插入、删除、查找、判空以及遍历等知识点。 1. **循环链表的定义** 在C语言中，循环链表的节点通常定义为一个结构体，包含数据域和指针域两部分。例如，可以定义一个存储整数的节点类型如下： ```c typedef struct Node { int data; // 数据域，存储实际信息 struct Node* next; // 指针域，指向下一个节点 } Node; ``` 循环链表的概念则可以通过让`next`指针指向链表的头部来实现。 2. **循环链表的初始化** 初始化一个空的循环链表，需要创建一个头节点，其`next`指针指向自身，表示链表为空。代码如下： ```c Node* createCircularList() { Node* head = (Node*)malloc(sizeof(Node)); head->data = 0; // 可以根据需要设置初始值 head->next = head; // 形成环状 return head; } ``` 3. **节点的插入** 在循环链表中插入节点，首先要确定插入位置（头节点前、尾节点后或中间某个位置），然后调整插入节点和相邻节点的`next`指针。例如，在链表末尾插入节点的代码： ```c void insertTail(Node* head, int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = head->next; head->next = newNode; } ``` 4. **节点的删除** 删除节点时，需要找到待删除节点的前一个节点，然后更新前一个节点的`next`指针。例如，删除指定值的节点： ```c void deleteNode(Node* head, int value) { Node* current = head; Node* prev; do { prev = current; current = current->next; if (current->data == value) { prev->next = current->next; free(current); break; } } while (current != head); } ``` 5. **节点的查找** 查找循环链表中的节点，通常采用线性搜索的方式，从头节点开始直到找到目标节点或回到头节点。例如： ```c Node* findNode(Node* head, int value) { Node* current = head; do { if (current->data == value) { return current; } current = current->next; } while (current != head); return NULL; // 如果没找到，返回NULL } ``` 6. **判断链表是否为空** 判断链表是否为空，只需要检查头节点的`next`指针是否指向自身即可： ```c int isCircularListEmpty(Node* head) { return head->next == head; } ``` 7. **链表的遍历** 遍历循环链表，由于是环状结构，需要特别注意避免无限循环。通常从头节点开始，每次移动到下一个节点，直到再次到达头节点为止。例如： ```c void traverseCircularList(Node* head) { Node* current = head; do { printf("%d ", current->data); current = current->next; } while (current != head); } ``` 以上就是关于循环链表在C语言中的实现和操作的基本知识点。在实际编程中，还需要考虑内存管理、错误处理等方面，以确保程序的健壮性和效率。

资源推荐

资源详情

资源评论

收起资源包目录

循环链表.rar （4个子文件）

循环链表

ElemType.h 936B

CircularLinkedList.h 4KB

CircularLinkedList.c 8KB

main.c 3KB

// // Created by zhang on 2023/1/9. // /****************************************************************************** 版权所有 (C), 2023-2023，zhang ****************************************************************************** 文件名 : CircularLinkedList.c 版本号 : 初稿作者 : zhang 生成日期 : 2023/1/9 功能描述 : 1. 功能 : 2. 描述 : ******************************************************************************/ #include "CircularLinkedList.h" //初始化 void InitCircularLinkedList(CircularLinkedList * circularLinkedList, Course * array, int length) { circularLinkedList->head = NULL; circularLinkedList->length = 0; if(length < 0 || !array){ printf("初始化失败！\n"); return; } for (int i = 0; i < length; ++i) { InsertElement(circularLinkedList, i+1, array[i]); } } /** * 在循环链表的指定位置插入 * 需要考虑两种情况： * 1. 链表的长度为0：node->next = node * 2. 链表的长度不为0：node->next = head; lastNode->next->node */ void InsertElement(CircularLinkedList * circularLinkedList, int pos, Course course) { if((circularLinkedList->length+1) < pos){ printf("位置超出链表长度，插入失败！\n"); return; } //1. 创建一个新的结点 CirNode * node = (CirNode *) malloc(sizeof(CirNode)); node->course = course; node->next = NULL; //2. pos = 1 if(pos == 1){ node->next = circularLinkedList->head; //如果链表为空 if(!node->next){ node->next = node; } else { CirNode * lastNode = circularLinkedList->head; for(int i = 1; i < circularLinkedList->length; ++i){ lastNode = lastNode->next; } lastNode->next = node; } circularLinkedList->head = node; circularLinkedList->length++; return; } //3. pos不为1 //找到第pos-1个结点 CirNode * current = circularLinkedList->head; for (int i = 1; current && i < (pos-1); ++i) { current = current->next; } if(current){ node->next = current->next; current->next = node; circularLinkedList->length++; if(pos == circularLinkedList->length){ // TODO 这里current->next 已经指向了头结点，为了更加清晰步骤，强调此时node为最后一个结点，它的next应该指向头结点 node->next = circularLinkedList->head; } } } //查找 //按位查找 Course GetElementByPosition(CircularLinkedList * circularLinkedList, int pos) { Course course; course.id = NO_EXIST_ID; if(pos < 0 || pos > circularLinkedList->length || !circularLinkedList->head){ printf("查找失败！\n"); return course; } CirNode * current = circularLinkedList->head; for (int i = 1; i < pos; ++i) { current = current->next; } course = current->course; return course; } //按值查找 int GetPositionByElement(CircularLinkedList * circularLinkedList, Course course) { int pos = 1; CirNode * current = circularLinkedList->head; while (current){ Course cur_course = current->course; if((course.id == cur_course.id) && (course.name == cur_course.name) && (course.teacher == cur_course.teacher) && (course.type == cur_course.type)) return pos; pos++; current = current->next; } return NO_FOUND; } //根据元素内容返回对应的结点 CirNode * GetCircularLinkedListNode(CircularLinkedList * circularLinkedList, Course course) { CirNode * current = circularLinkedList->head; do { Course curCourse = current->course; if((course.id == curCourse.id) && (strcmp(course.name, curCourse.name) == 0) && (strcmp(course.teacher, curCourse.teacher) == 0) && (strcmp(course.type, curCourse.type) == 0)) return current; current = current->next; } while (current != circularLinkedList->head); return NULL; } //返回前驱结点 Course GetPriorNode(CircularLinkedList * circularLinkedList, Course course) { Course prior_course; int pos = GetPositionByElement(circularLinkedList, course); CirNode * prior_node = circularLinkedList->head; if(pos == 1){ for (int i = 1; i < circularLinkedList->length; ++i) { prior_node = prior_node->next; } } else { for (int i = 1; i < pos-1; ++i) { prior_node = prior_node->next; } } prior_course = prior_node->course; return prior_course; } //返回后继结点 Course GetNextNode(CircularLinkedList * circularLinkedList, Course course) { Course next_course; CirNode * next_node = circularLinkedList->head; int pos = GetPositionByElement(circularLinkedList, course); for (int i = 0; i < pos; ++i) { next_node = next_node->next; } next_course = next_node->course; return next_course; } //删除结点 Course DeleteElem(CircularLinkedList * circularLinkedList, int pos) { Course course; course.id = NO_EXIST_ID; if(pos < 0 || pos > circularLinkedList->length || !circularLinkedList->head){ printf("删除失败！\n"); return course; } CirNode * node = circularLinkedList->head; CirNode * current = circularLinkedList->head; if(pos == 1){ //记录结点 course = node->course; //移动头指针 circularLinkedList->head = node->next; //尾结点指向头结点 for (int i = 1; i < circularLinkedList->length; ++i) { current = current->next; } current->next = circularLinkedList->head; circularLinkedList->length--; } else { //找到第pos-1个结点 for (int i = 1; i < pos-1; ++i) { current = current->next; } //记录结点 node = current->next; course = node->course; current->next = node->next; circularLinkedList->length--; } free(node); return course; } //链表的长度 int GetLength(CircularLinkedList * circularLinkedList) { if(!circularLinkedList->head){ return EMPTY; } return circularLinkedList->length; } //判空 int IsEmpty(CircularLinkedList * circularLinkedList) { return circularLinkedList->length == 0 ? TRUE : FALSE; } //清空循环链表 void ClearCircularLinkedList(CircularLinkedList * circularLinkedList) { CirNode * current = circularLinkedList->head; CirNode * priorNode = NULL; //应该选择for循环，经过特定的次数将链表中每个结点都释放内存，最后将头结点置为NULL，长度置0 /* while(current->next){ priorNode = current; current = current->next; free(priorNode); }*/ for (int i = 0; i < circularLinkedList->length; ++i) { priorNode = current; current = current->next; free(priorNode); } circularLinkedList->head = NULL; circularLinkedList->length = 0; } //打印链表 void PrintList(CircularLinkedList * circularLinkedList) { if(circularLinkedList->length == 0 || !circularLinkedList->head){ printf("链表为空！\n"); circularLinkedList->length = 0; return; } CirNode * current = circularLinkedList->head; for (int i = 0; current && i < circularLinkedList->length; ++i) { printf("[%d, %s, %s, %s]\n", current->course.id, current->course.name, current->course.teacher, current->course.type); current = current->next; } } //根据循环链表的某个结点遍历整个循环链表 void VisitCircularLinkedList(CirNode * node) { if(!node){ printf("内容为空！\n"); return; } CirNode * current = node; do { PrintNode(current->course); current = current->next; } while (current != node); } //打印节点 void PrintNode(Course course) { printf("该结点内容：[%d, %s, %s, %s]\n", course.id, course.name, course.teacher, course.type); }

评论收藏

内容反馈