数据结构练习题解答(三)第三章链表（Data structure Exercises answer (three) third chapters linked list）.doc

数据结构练习题解答(三)第三章链表（Data structure Exercises answer (three) third chapters linked list） Answers to data structure exercises (three) Third chapter linked list 3-2 try to write an algorithm to find the first I node in a single table with header nodes. If found, the function returns the address of the I node; if not found, the function returns 0. [answers] Template class Type ListNode Type * List Type:: GetANode (int i) { Get / / single list to the I node address, I start counting from 0, I 0 pointer 0, I = 0 return header node address. If (I 1) return NULL; ListNode Type * P = first; int k = 0; While (P! = NULL K I) {P = P, link; k++;} Return p; } 3-3 let HA and Hb be two header pointers of non decreasing ordinal single linked list with header nodes, and try to design an algorithm to merge the two ordered linked lists into a non increasing ordered single chained list. The result list still uses the storage space of the original two linked lists, and does not occupy any other storage space. Allow repeated data in the table. [answers] #include iostream.h Template class Type class List; Template class Type class ListNode { Friend class ListType; Public: (ListNode); / / constructor ListNode (const Type item); / / constructor Private: Type data; ListNodeType *link; }; Template class Type class List { Public: List (const Type finishied); / / the establishment of the list Void (Browse); / / print list Void Merge (ListType hb); / / connection list Private: ListNodeType *first, *last; }; The realization of the function of member / / Template class Type ListNodeType:: ListNode (): link (NULL) {} / / constructor, only to initialize the pointer member. Template class Type ListNodeType: ListNode (const Type item) : data (item), link (NULL) {} / / constructor initialization data and pointer members. Template class Type ListType:: List (const Type finishied) { / / create header node with a single linked list, finished is a stop sign input table, All input values in numerical / /