c语言实现循环链表的源代码

// // 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); }