دسته : رشته مهندسی کامپیوترتاریخ: ۱۳۹۳/۱۱/۰۱
ساختمان داده

عنوان مقاله:ساختمان داده

Sequential representation

successive nodes of the data object are stored a fixed distance apart

order of elements is the same as in ordered list

adequate for functions such as accessing an arbitrary node in a table

operations such as insertion and deletion of arbitrary elements from ordered lists become expensive

Linked representation

successive items of a list may be placed anywhere in memory

order of elements need not be the same as order in list

each data item is associated with a pointer (link) to the next item

To insert GAT between FAT and HAT

(۱) get a node N that is currently unused ; let its address be x

(۲) set the data field of N to GAT

(۳) set the link field of N to point to the node after FAT, which contains HAT

(۴) set the link field of the node containing FAT to x

To delete GAT

find the element that immediately precedes GAT, which is FAT

set the link field of FAT to the position of HAT

۴٫۲٫۲ Designing a list in C++

Design approach

use a class ThreeLetterList corresponding to the entire list data structure

ThreeLetterList supports member functions for list manipulation operations

use a composite of two classes, ThreeLetterNode and ThreeLetterList

ThreeLetterList HAS-A ThreeLetterNode

Definition

 a data object of type A HAS-A data object of type B if A conceptually contains B