重庆大学数据结构09_linear+list_05.ppt

Data Structure Linear Lists_05 Data Structure 01 Course Overview Data Structure College of Computer Science, CQU Unit9 Lists seminar 1. In the linked list implementation presented in Section 4.1.2, the current position is implemented using a pointer to the element ahead of the logical current node. The more “natural” approach might seem to be to have curr point directly to the node containing the current element. However, if this was done, then the pointer of the node preceding the current one cannot be updated properly because there is no access to this node from curr. An alternative is to add a new node after the current element, copy the value of the current element to this new node, and then insert the new value into the old current node. (a) What happens if curr is at the end of the list already? Is there still a way to make this work? Is the resulting code simpler or more complex than the implementation of Section 4.1.2? (b) Will deletion always work in constant time if curr points directly to the current node? In particular, can you make several deletions in a row? Subjects 2. Write a function that reverses the order of the elements on the list(stored by array_based list and singly link list). Your algorithm should run in O(1) space complexity. 3. Write a function to merge two lists list(stored by array_based list and singly link list). The input lists have their elements in sorted order, from lowest to highest. The output list should also be sorted from lowest to highest. Subjects 4. A circular linked list is one in which the next ?eld for the last link node of the list points to the ?rst link node of the list. This can be useful when you wish to have a relative positioning for elements, but no concept of an absolute ?rst or last position. (a) Modify the code of Figure 4.8 to implement circular singly linked lists. (b) Modify the code of Figure 4.14 to implement circular doubly linked lists. 5. Implement Josephues problem use circular linked list Subjec