西安建筑科技大学：《数据结构与算法》课程教学资源（PPT电子教案）第二部分 栈、队列、递归方法_链式栈与队列 Chapter 4 Linked Stacks and Queues（英文）

Chapter 4 Linked Stacks and Queues I1 Pointers and Linked Structures I 2. Linked Stacks 3. Linked Stacks with Safeguards 4. Linked Queues 5. Application: Polynomial Arithmetic 6. Abstract Data Types and Implementations 7. Pointers and Pitfalls

Chapter 4 Linked Stacks and Queues 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 7. Pointers and Pitfalls

4.1 Pointers and a Linked List A Linked list is a Lynn sequence of zero o Jack more elements called nodes each containing Q Dave two kinds of Marsha information: some data and one or more FRed Jackie links called pointers to 367-2205 2950603 Jan 28 Feb 18 other nodes of the Carol Rene linked list 628-5100 3425153 Feb23 Mar. 15

A Linked List is a sequence of zero or more elements called nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list. 4.1 Pointers and a Linked List

Head 日-[a[a→…→a囚 Head Head an Head

Key Terms ◆ Overflow Running out of space ◆ 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) ◆ Linked list: A list in which each entry contains a pointer giving the location of the next entry

Key Terms  Overflow: Running out of space.  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)  Linked list: A list in which each entry contains a pointer giving the location of the next entry

◆ Contiguous Next to each other, touching, adjoining; used in contrast to linked ◆ 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 ◆ Dynamic object An object that is created (and perhaps destroyed) while the program is running accessed indirectly via pointers

 Contiguous: Next to each other, touching, adjoining; used in contrast to linked.  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.  Dynamic object: An object that is created (and perhaps destroyed) while the program is running; accessed indirectly via pointers

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 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

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.  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 for the heap). 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

The dynamic objects that we create are kept in an area of computer memory called the free store (or the heap).  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

◆ Following pointers item _ptr denotes the object to which item_ptr points. The action of taking item ptr is called referencing the pointer *item_ptr. ◆ 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

 Following pointers: *item_ptr denotes the object to which item_ptr points. The action of taking “ *item_ptr is called *referencing the pointer *item_ptr.”  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

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

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. important data Random pointer p=new Item 19 884 0 important data 1375 p=1375 p=0 Random pointer 0 G→ ??? p= NULL Random pointer =0 delete p Please modify Pgll8 Figure 4.3 code is c, not c++

 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. Please modify Pg118 Figure4.3 code is c,not c++