对外经济贸易大学《C++程序设计》课件-lecture12-13.pptVIP

CS 1031lecture12: Applications of BSTs and Linked ListsReview the project onlineDetermine requirementsCome up with an overall designCarry out the implementation对外经济贸易大学《C++程序设计》 CS 1032A Class PersonThe community is a group of individualsFor each individual (i.e., person), we are provided a lot of personal information. Also, many of the queries can be answered directly from the provided personal informationTHEREFORE: It make a lot of sense to define a class called PersonIt should have the data pieces provided in the paragraph of a given person in the input file It should provide accessors (get functions) to return the values of the data pieces. CS 1033The Person Class (Contd.)The variable members should then be: SSN, firstName, lastName, the father’s SSN, the mother’s SSN, and the list of friends (more on the list of friends later)The constructor should take as input the data pieces provided in the input fileThe accessors: getSSN( ), getFullName( ), getFatherSSN( ), getMotherSSN( ), getFriends( ). CS 1034The Community Data StructureNearly all of the queries (all but one) specify the SSN of the person in questionTo be able to answer such queries, the Person (object) whose SSN is the specified SSN must be searched forTherefore, the Persons of the community must be organized into some data structure that provides efficient operations for search (and for insert, because insert is used to fill the data structure) CS 1035The Community Data Structure (Contd.)We studied two structures that support general insert and search operationsLinked listsBinary search trees (BSTs)So, you can use either one of them. In either case, each node should store one Person instance, and the key of each node should be the SSN of the corresponding PersonNote that we also learned that searching in BSTs is a lot faster than in linked listsTherefore, it is better to represent the community (group of persons) as a BST. CS 1036The Community as a BSTIf you decide to use a BST to represent the comm