首页 > 代码库 > 复习下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 链表操作(双向循环链表,查找循环节点)