2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教学使用 e To dispose of a Cell object, at the end of its lifetime, we must remember the corresponding pointer Therefore, the List member will store pointers to cells rather than the cells themselves. This is called an indirect list Indirect Linked List of Cells P 420 Each node of the List contains two pointers: one to a Cell and one to the next node of the list The Hash Table P 420 Entries of the hash table will be pointers to cells, as in the List he coordinates of the cells, which are determined by the pointers, are the corresponding keys We must decide between open addressing and chaining The entries to be stored in the table need little space: Each entry need only store a pointer to a Cell. Since the table entries are small, there are few space considerations to advise our decision With chaining, the size of each record will increase 100 percent to accommodate the necessary pointer, but the hash table itself will be smaller and can take a higher load factor than with open addressing With open addressing, the records are smaller, but more room must be left vacant in the hash table to avoid long searches and possible overflow For flexibility, let us decide to use a chained hash table class Hash table Error code insert( Cell *new entry) bool retrieve(int row, int col)const private List<Cell * table hash size; o A Hash table comes with a default constructor and destructor, which we shall rely on 99.3 The Life Class P 421 o In the life class, to facilitate the replacement of a configur ation by an updated version, we shall store the data members indirectly, as pointers P.421 The auxiliary member functions retrieve and neighbor count determine the status of a cell by applying hash-table retrieval Auxiliary function insert creates a dynamic Cell object and inserts it into both the hash table and the list of cells of a Life obj 9.9.4 Updating the Configuration P 422-423 update starts with one Life configuration and determines the configuration at the next generation With an unbounded grid, we must limit our attention to the cells that may be ali These include the living and the dead cells with living neighbors. P 422>ve in the coming generation. e In the method update, a local variable Life new configuration is thereby gradually built up to represent the upcoming configuration. e We loop over all the(living) cells from the current configuration, and we also loop over all the(dead) cells At the end of update, we swap the list and Hash table members between the current configuration and new configuration. This exchange also ensures that the destructor that will automatically be applied to the local variable Life new configuration ng:P423-424 Creation and insertion of new cells: P 424 Construction and destruction of Life objects: P. 424-425 The hash function: P 425-426 Pointers and pitfalls 9 items P. 426-427 Errata p.396,"Uses: "line: Delete comma and Record. The"to"Key and Record,the" after "List 05, " Uses: line: Change Key p. 408, line-5, and p 410, line 5: Change "Key type"to"Key2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ To dispose of a Cell object, at the end of its lifetime, we must remember the corresponding pointer. Therefore, the List member will store pointers to cells rather than the cells themselves. This is called an indirect list. ◼ Indirect Linked List of Cells P. 420 ◼ Each node of the List contains two pointers: one to a Cell and one to the next Node of the List. The Hash Table P. 420 ⚫ Entries of the hash table will be pointers to cells, as in the List. ⚫ The coordinates of the cells, which are determined by the pointers, are the corresponding keys. ⚫ We must decide between open addressing and chaining. ⚫ The entries to be stored in the table need little space: Each entry need only store a pointer to a Cell. Since the table entries are small, there are few space considerations to advise our decision. ⚫ With chaining, the size of each record will increase 100 percent to accommodate the necessary pointer, but the hash table itself will be smaller and can take a higher load factor than with open addressing. ⚫ With open addressing, the records are smaller, but more room must be left vacant in the hash table to avoid long searches and possible overflow. ⚫ For flexibility, let us decide to use a chained hash table. class Hash table { public: Error code insert(Cell *new entry); bool retrieve(int row, int col) const; private: List<Cell *> table[hash size]; }; ⚫ A Hash table comes with a default constructor and destructor, which we shall rely on. 9.9.3 The Life Class P. 421 ⚫ In the Life class, to facilitate the replacement of a configuration by an updated version, we shall store the data members indirectly, as pointers. P. 421 ⚫ The auxiliary member functions retrieve and neighbor _count determine the status of a cell by applying hash-table retrieval. ⚫ Auxiliary function insert creates a dynamic Cell object and inserts it into both the hash table and the list of cells of a Life object. 9.9.4 Updating the Configuration P. 422-423 ⚫ update starts with one Life configuration and determines the configuration at the next generation. ⚫ With an unbounded grid, we must limit our attention to the cells that may be alive in the coming generation. These include the living cells and the dead cells with living neighbors. P. 422 ⚫ In the method update, a local variable Life new configuration is thereby gradually built up to represent the upcoming configuration. ⚫ We loop over all the (living) cells from the current configuration, and we also loop over all the (dead) cells that are neighbors of these (living) cells. ⚫ At the end of update, we swap the List and Hash table members between the current configuration and new configuration. This exchange also ensures that the destructor that will automatically be applied to the local variable Life new configuration. Printing: P.423-424 Creation and insertion of new cells: P.424 Construction and destruction of Life objects: P.424-425 The hash function: P.425-426 Pointers and Pitfalls 9 items P.426-427 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 396, "Uses:" line: Delete comma "," after "List". p. 405, "Uses:" line: Change "Key, and Record. The" to "Key and Record, the". p. 408, line -5, and p. 410, line 5: Change "Key_type" to "Key". -------------------------------------------------------------------------------------------------------------------------------