首页 > 代码库 > 复习下C 链表操作(双向循环链表,查找循环节点)
复习下C 链表操作(双向循环链表,查找循环节点)
双向循环链表 和 单向循环链表 查找循环节点 思路都是一样。 快慢指针查找法。 理论可参考
c 链表之 快慢指针 查找循环节点
typedef struct Student_Double{ char name[10]; int point; struct Student_Double *preStu; struct Student_Double *nextStu;} StudentDouble;StudentDouble * CreateDoubleCircleLink_Table(){ int i = 0; StudentDouble *head = NULL; head=(StudentDouble *)malloc(sizeof(StudentDouble)); head->name[0]=‘\0‘; head->point = 0; head->nextStu = NULL; head->preStu = NULL; //循环节点 StudentDouble *cirleStu = NULL; StudentDouble *temp = NULL; StudentDouble *currentNode = head; while (i<=9) { temp = (StudentDouble *)malloc(sizeof(StudentDouble)); strncpy(temp->name,"Node",sizeof(temp->name)); temp->point = i; temp->nextStu = NULL; temp->preStu = currentNode; currentNode->nextStu = temp; currentNode = temp; if (i==3) { cirleStu = currentNode; } i++; } //最后 合并循环节点 currentNode->nextStu=cirleStu; return head;}//已知循环节点情况查询循环 链表,验证是否可用void SelectDoubleLinkTable(StudentDouble *student){ StudentDouble *next = student->nextStu; int i = 0; StudentDouble *circleStu = NULL; while (next) { if (circleStu!=NULL&&next->point == circleStu->point) { printf("循环节点%d,结束循环\n",next->point); break; } if (i==3) { circleStu = next; } printf("index %d; studentName is %s; point is %d\n",i,next->name,next->point); i++; next = next->nextStu; }}//未知情况查询循环节点StudentDouble * SelectCircleNodeInDoubleLinkTable(StudentDouble *head){ //快慢指针查询 StudentDouble *fast = head; StudentDouble *slow = head; while (fast) { fast = fast->nextStu->nextStu; slow = slow->nextStu; if (fast==NULL) {//不是循环链表推出 break; } if (fast==slow) {//快慢指针相遇 break; } } if (fast == NULL) { printf("该链表 不是循环链表\n"); return NULL; } //查找循环节点 fast = head; while (fast!=slow) { fast=fast->nextStu; slow=slow->nextStu; } printf("=====找到循环链表循环节点为%d\n",fast->point); return fast;}int main(void){ char sf[15]; //创建双向循环链表 StudentDouble *head = NULL; printf("创建双向循环链表Y|N\n"); scanf("%s",sf); if (strcmp(sf,"Y")==0) { head = CreateDoubleCircleLink_Table(); } printf("已知情况查询循环链表Y|N \n"); scanf("%s",sf); if (strcmp(sf,"Y")==0) { SelectDoubleLinkTable(head); } printf("未知情况查询循环链表Y|N \n"); scanf("%s",sf); if (strcmp(sf,"Y")==0) { SelectCircleNodeInDoubleLinkTable(head); } return 0;}
复习下C 链表操作(双向循环链表,查找循环节点)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。