2008级计算机专业数据结构课 内部资料,仅供课堂教学使用 Chapter 4 LINKED STACKS AND QUEUES P49 1. Pointers and Linked Structures 4. Linked Queues 2. Linked Stacks 5. Application: Polynomial Arithmetic 3. Linked Stacks with Safeguards 6. Abstract Data Types and Implementations [4. 1] Pointers and Linked Structures Pointers and a linked list P114 4.1.1 Key terms Overflow: Running out of space. P113 Pointer: An object, often a variable, that stores the location( that is the machine address) of some other object, typically of a structure containing data that we wish to manipulate. Also sometimes called a link rence) P 1 13 Linked list: A list in which each entry contains a pointer giving the location of the next entry. P 1 14 Contiguous: Next to each other, touching, adjoining; used in contrast to linked. P. 15 e Automatic object: An object that exists as long as the block of program declaring it is active; referenced by giving it a name when writing the program. P 116 Dynamic object: An object that is created (and perhaps destroyed) while the program is running accessed indirectly via pointers. P1 16 4.1.2 Pointers in C++ Notation: C++ uses an asterisk* to denote a pointer. If Item is a type, then a pointer to such an Item object has the type Item *. For example, Item *item ptr; declares item ptr as a pointer variable to an Item object. P116 Creating dynamic objects: item ptr new Item; creates a new dynamic object of type Item and assigns its location to the pointer variable item ptr. The dynamic objects that we create are kept in an area of computer memory called the free store (or the heap). P 117 Deleting dynamic objects: delete item ptr; disposes of the dynamic object to which item ptr points and returns the space it occupies to the free store so it can be used again. After this delete statement is executed, the pointer variable item ptr is undefined and so should not be used until it is assigned a new value. P117 Following pointers: "item ptr denotes the object to which item ptr points. The action of taking *item ptr is called"dereferencing the pointer *item ptr. P 117-118 NULL pointers: If a pointer variable item ptr has no dynamic object to which it currently refers, then it should be given the special value item ptr= NULL, In diagrams we reserve the electrical ground symbol for NULL pointers. The value NULL is used as a constant for all pointer types and is generic in that the same value can be assigned to a variable of any pointer type. P 1 19 Undefined pointers versus NULL pointers: item ptr -NULL means that item ptr currently points to no dynamic object. If the value of item ptr is undefined, then item ptr might point to any random P.I19 Programming Precept: Uninitialized or random pointer objects should always be reset to NULL. After deletion, a pointer object should be reset to NULL. P 119 Dynamically Allocated Arrays: The declaration item array new Item [array size]; creates a dynamic array of Item objects, indexed from O up to array size- 1. Consider, for example int size, *dynamic array, i cout << "Enter an array size: < flush cin > size dynamic array new int[size for (i=0; i< size; i ++ dynamic array[i=i r value and p is a pointer to an Item, then p+i is an expression of type Item * The value of p+i gives the memory address offset from p by iltem objects. That is, the expression p+i actually yields the address p+nxi where n is the number of bytes of storage occupied by a simple object of type Item Addresses of automatic objects: If x is a variable of type Item, then &x is a value of type Item that2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 4 LINKED STACKS AND QUEUES P.49 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. Pointers and Linked Structures 2. Linked Stacks 3. Linked Stacks with Safeguards 4. Linked Queues 5. Application: Polynomial Arithmetic 6. Abstract Data Types and Implementations [4.1] Pointers and Linked Structures Pointers and a Linked List P.114 4.1.1 Key Terms ⚫ Overflow: Running out of space. P.113 ⚫ Pointer: An object, often a variable, that stores the location (that is the machine address) of some other object, typically of a structure containing data that we wish to manipulate. (Also sometimes called a link or a reference) P.113 ⚫ Linked list: A list in which each entry contains a pointer giving the location of the next entry. P.114 ⚫ Contiguous: Next to each other, touching, adjoining; used in contrast to linked. P.115 ⚫ Automatic object: An object that exists as long as the block of program declaring it is active; referenced by giving it a name when writing the program. P.116 ⚫ Dynamic object: An object that is created (and perhaps destroyed) while the program is running; accessed indirectly via pointers. P.116 4.1.2 Pointers in C++ ⚫ Notation: C++ uses an asterisk * to denote a pointer. If Item is a type, then a pointer to such an Item object has the type Item *. For example, Item *item_ptr; declares item_ptr as a pointer variable to an Item object. P.116 ⚫ Creating dynamic objects: item_ptr = new Item; creates a new dynamic object of type Item and assigns its location to the pointer variable item_ptr. The dynamic objects that we create are kept in an area of computer memory called the free store (or the heap). P.117 ⚫ Deleting dynamic objects: delete item_ptr; disposes of the dynamic object to which item ptr points and returns the space it occupies to the free store so it can be used again. After this delete statement is executed, the pointer variable item_ptr is undefined and so should not be used until it is assigned a new value. P.117 ⚫ Following pointers: *item_ptr denotes the object to which item_ptr points. The action of taking *item_ptr is called “dereferencing the pointer *item_ptr.” P.117-118 ⚫ NULL pointers: If a pointer variable item_ptr has no dynamic object to which it currently refers, then it should be given the special value item_ptr = NULL; In diagrams we reserve the electrical ground symbol for NULL pointers. The value NULL is used as a constant for all pointer types and is generic in that the same value can be assigned to a variable of any pointer type. P.119 ⚫ Undefined pointers versus NULL pointers: item_ptr ==NULL means that item_ptr currently points to no dynamic object. If the value of item_ptr is undefined, then item_ptr might point to any random location in memory. P.119 Programming Precept: Uninitialized or random pointer objects should always be reset to NULL. After deletion, a pointer object should be reset to NULL. P.119 ⚫ Dynamically Allocated Arrays: The declaration item_array = new Item[array_size]; creates a dynamic array of Item objects, indexed from 0 up to array_size − 1. Consider, for example: int size, *dynamic array, i; cout << "Enter an array size: " << flush; cin >> size; dynamic array = new int[size]; for (i = 0; i < size; i ++) dynamic_array[i] = i; The statement delete [ ]dynamic_array; returns the storage in dynamic_array to the free store. If i is an integer value and p is a pointer to an Item, then p+i is an expression of type Item *. The value of p+i gives the memory address offset from p by i Item objects. That is, the expression p+i actually yields the address p+n×i , where n is the number of bytes of storage occupied by a simple object of type Item. P.119-120 ⚫ Addresses of automatic objects: If x is a variable of type Item, then &x is a value of type Item* that