《(2.4.1)--ch2-04循环链表.pdf》由会员分享，可在线阅读，更多相关《(2.4.1)--ch2-04循环链表.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构与算法Data Structures and Algorithms循环链表 Circularly Linked ListData Structures and AlgorithmsData Structures and AlgorithmsCHAPTER2 Linear List2.4 Circularly Linked ListApplications：The Question of Josephus Ring which was put forward by Joseph,a historian in ancient Rome。The description of the pro
2、blem is that people numbered from 1 to n sit around the round table，and then each person holds a password。At the beginning each person chooses a positive integer as the maximum value m，From the first person the counting starts from 1 in a clockwise direction，stops at counting at m，and the person who
3、 gives number m leaves，then using his password as the new m-value and moves from the next in a clockwise direction.The person starts counting again from 1 and the person counting to m leaves.Again and again,until the last one remains.Data Structures and AlgorithmsData Structures and Algorithms3CHAPT
4、ER2 Linear ListCircular Linked List：Is a linked list end to endFeatures:Change the pointer field of the last node of the singly-linked list from NULL to point to the head node or the first node in the linear list,and get a singly-linked circular linked list,which is called a circular singly-linked l
5、ist.In a circular singly linked list,all nodes in the table are chained on a ring.LEmpty circular linked list with leading nodea1a2ai-1aianLCircular singly linked list with head pointera1a2ai-1aianCircular singly linked list with tail pointerrearData Structures and AlgorithmsData Structures and Algo
6、rithms4CHAPTER2 Linear ListCircular Linked ListExample 1:If there are two circularly linked lists LA and LB with header，and an algorithm is written,to merge the two lists into a single list,its header pointer is LAfirst you need to find the tail pointers of the two lists，which are indicated by the p
7、 and q pointer respectively，Then we connect the tail pointer of the first list to the first node of the second list.a1a2ai-1aianLAb1b2bi-1bibnLBpq p-next=LB-next;q-next=LA;free(LB);Data Structures and AlgorithmsData Structures and Algorithms5CHAPTER2 Linear List2.4 Chain storage of linear listsCircu
8、lar Linked List Algorithm Implementation 1LinkList merge_1(LinkList LA,LinkList LB)LNode*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;while(q-next!=LB)q=q-next;p-next=LB-next;free(LB);q-next=LA;return(LA);Time Complexity O(n)Data Structures and AlgorithmsData Structures and Algorithms6CHAPTER2 Linear Li
9、st2.4 Chain storage of linear listsCircular Linked List(with tail pointer)Example 1:If there are two circularly linked lists LA and LB with header，and an algorithm is written，to merge the two lists into a single list，its header pointer is LAUsing a circular linked list with a tail pointer,the execut
10、ion time can be reduced to O(1).a1a2ai-1aianRAb1b2bi-1bibnRBpRA-next=RB-next-next;RB-next=p;free(RB-next);Data Structures and AlgorithmsData Structures and Algorithms7CHAPTER2 Linear List2.4 Chain storage of linear listsCircular Linked List Algorithm implementation 2LinkList merge_2(LinkList RA,Link
11、List RB)LNode*p;p=RA-next;RA-next=RB-next-next;free(RB-next);RB-next=p;return(RB);O(1)Data Structures and AlgorithmsData Structures and Algorithms8CHAPTER2 Linear List2.4 Chain storage of linear listsTo summarize the characteristics of a circularly linked list:1.It is possible to access any nodes in
12、 the list no matter where you start from2.The circularly list is symmetrical，so in generalto determine the starting position,we need to set up a header,we can combine the operation of empty lists and non-empty lists.3.The operation of the circular linked list is basically the same as that of the lin
13、ear linked list,which can sometimes simplify some operations.after-school exercise：Application：achieve the problem of Joseph RingData Structures and AlgorithmsData Structures and Algorithms9CHAPTER2 Linear List Implementation hints for the problem of Josephus：Algorithm analysis:using a circularly li
14、nked list Node structure：The basic steps to solve the problem are as follows：1.Establish a circularly linked list of n nodes(headless nodes).2.Counting from the first node of the linked list to find the mth node.3.Output the id value of the node,use the password of the node as the new m value,and delete the node.4.Continue to delete nodes from the linked list according to the value of m until the linked list is empty.ThanksD Da at ta a S St tr ru uc ct tu ur re es s a an nd d A Al lg go or ri it th hm ms s