DATA STRUCTURES
1.1 INTRODUCTION
This chapter introduces the subject of data structures and presents an overview of the content of the text. Basic terminology and concepts will be defined and relevant examples provided. An overview of data organization and certain data structures will be covered along with a discussion of the. different operations which are applied to these data structures. Last, we will introduce the notion of an algorithm and its complexity, and we will discuss the time-space tradeoff that may occur in choosing a particular algorithm and data structure for a given problem.
1.2 BASIC TERMINOLOGY; ELEMENTARY DATA ORGANIZATION
Data are simply values or sets of values. A data item refers to a single unit of values. Data items that are divided into subitems are called group items; those that are not are called elementary items. For example, an employee's name may be divided into three subitems-first name, middle initial and last name-but the social security number would normally be treated as a single item. Collections of data are frequently organized into a hierarchy of fields, records and files. order to make these terms more precise, we introduce some additional terminology. An entity is something that has certain attributes or properties which may be assigned values In The values themselves may be either numeric or nonnumeric. For example, the following are possible attributes and their corresponding values for an entity, an employee of a given organization:
Attributes: Name Age Sex Social Security Number
Values: ROHLAND, GAIL 34 F 134-24-5533
Each record in a file may contain many(a) (b) Suppose an automobile dealership maintains an inventory file where each record contains the following data: Serial Number, Type, Year, Price, Accessories The Serial Number field can serve as a primary key for the file, since each automobile has a unique serial number. Suppose an organization maintains a membership file where each record contains the following data: Name, Address, Telephone Number, Dues Owed field items, but the value in a certain field may uniquely determine the record in the file. Such a field K is called a primary key, and the values k1, k2,... in such a field are called keys or key values.
Example 1.1
(a) Suppose an automobile dealership maintains an inventory file where each record contains the following data:
Serial Number, Type, Year, Price, Accessories
The Serial Number field can serve as a primary key for the file, since each automobile has a unique serial number.
(b)Suppose an organization maintains a membership file where each record contains the following data: Name, Address, Telephone Number, Dues Owed
Name and Address may be group items. Here the Name field is a primary key. Note that the Address and Telephone Number fields may not serve as primary keys, since some members may belong to the same family and have the same address and telephone number.
Records may also be classified according to length. A file can have fixed-length records or variable-length records. In fixed-length records, all the records contain the same data items with the same amount of space assigned to each data item. In variable-length records, file records may contain different lengths. For example, student records usually have variable lengths, since different students take different numbers of courses. Usually, variable-length records have a minimum and a maximum length.
1. Logical or mathematical description of the structure
2. Implementation of the structure on a computer
3. Quantitative analysis of the structure, which includes determining the amount of memory needed to store the structure and the time required to process the structure.
The next section introduces us to some of these data structures.
