数据结构与算法 Data Structures and AlgorithmsData structure and algorithm of Data Structures and Algorithms

1、CHAPTER 4 LINKED STACKS & QUEUES AND LISTS 【学习内容】 BASIC CONCEPTSPointers and Linked StructuresLinked StacksLinked Stacks with SafeguardsLinked QueuesApplication: Polynomial ArithmeticAbstract Data Types and ImplementationsPointersArrayLinked ListLocations of elements can be easily computedElements m

2、ay be placedanywhere in memoryMoving elements in anordered list can be expensiveFinding an element maybe expensiveReview the relevant materials in C+if you dont know what I am talking about.Pointers指针是一种特殊的变量。具有一般变量的三要素：名字、类型、值指针的名字：与一般变量的命名相同指针的值:指针是一种用来存放某个变量的地址值的变量。一个指针存放了哪个变量的地址值，该指针就指向哪个变量。指针与它

3、所指向变量的关系例： int a(5); int *pa=&a;:地址值51000Ha1000H:2000Hpa指针pa指向变量a*pa的值？*pa=10;a=10;指针：存放对象的存储地址，例如 int i = 5;int *p; *p = i; *p = NULL; /空指针 int *np; /np为一个指向整型量的指针 np = &i; /把整型变量 i 的地址赋给它 /np 成为指向整型变量 i 的指针 int k = *np; /k中存入np所指地址i的内容引用：它用来给一个对象提供一个替代的名字。例如 int i = 5; int& j = i; i = 7; cout“i =

4、“i“ j = ” jendl ; 此时, j 是一个引用类型, 它代表 i 的一个替代名。当 i 的值改变时, j 的值也跟着改变。当 printf 语句执行后, 打印出的 i 和 j 的值都是7。C+的动态存储分配Dynamic Memory Allocationstack stored_numbers;/自动分配Item *p= new Item;/动态分配Item *p;p=new Item;delete p;p is a pointer to Item objectCreates a new dynamic object of type Item and assigns its th

5、e pointer p If p is a pointer to a dynamic object of type Item,the statement disposes of the object Figure4.4 Modifying dereferenced pointersNULL pointers:If a pointer variable item p has no dynamic object to which it currently refers, then it should be given the special value Item *p; p = NULL; if

6、(p!=NULL) In diagrams we reserve the electrical ground symbolNULL 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.Actually ,the value NULL is not part of the C+,but it is defined,as 0,in stand

7、ard header files such as that we include in our utility header file. 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.Dynamically Alloca

8、ted Arraysitem_array = new Itemarray_size;for example:int size, *dynamic_array, i;cout Enter an array size: size;dynamic_array = new intsize;for (i = 0; i as a shorthand, so we can replace the epression (*p).the data by the equivalent, but more convenient, expression p-the data.p-numberator=0Linked

9、StructuresFigure 4.2 A linked listThe Basics of Linked StructuresA linked structure is made up of nodes, each containing both theinformation that is to be stored as an entry of the structure anda pointer telling where to find the next node in the structure.We shall use a struct rather than a class t

10、o implement nodes.(a)Structure of a Node(b)Machine storage representation of a Nodestruct Node / data members Node_entry entry; Node *next; / constructors Node( ); Node(Node entry item, Node *add on = NULL); Node( ); Node(Node entry item, Node *add on = NULL);OVERLOADExample:Node first_node(a); / No

11、de firrst node stores data a .Node *p0 = &first_node; / p0 points to first_Node .Node *p1 = new Node(b); / A second node storingb is created.p0-next = p1; / The secondNode is linked afterrst node .Node *p2 = new Node(c, p0); / A thirdNode storing c is created. / The thirdNode links back to the first

12、 node,*p0 .p1-next = p2; / The thirdNode is linked after the secondNode .Node ConstructorsNode : Node( ) next = NULL;Node : Node(Node_entry item, Node *add_on) entry = item; next = add_on; The first constructor does nothing except to set next to NULL as a safeguard for error checkong.The second cons

13、tructor is used to set the data members of a Node to the values specified as parameters4.2 Linked StacksFigure 4.9 The linked form of a stackClass Declaration for Linked Stackclass Stack public:Stack( );bool empty( ) const;Error_code push(const Stack_entry &item);Error_ code pop( );Error_code top(St

14、ack_entry &item) const;protected:Node *top_node;Dynamically Linked Stacks STACKNULLitemitemitemtop Push:itemtoptemp temp-next = top top = tempRead Program on next pageabout implementation of push and pop Pop: temp = top top = top-nexttop item = temp-item delete tempitem return item top:Pushing a Lin

15、ked StackError_code Stack : push(const Stack entry &item)/* Post: Stack entry item is added to the top of the Stack ; returns success or returns a code of overflow if dynamic memory is exhausted.*/Node *new_top = new Node(item, top_node);if (new_top = NULL) return overflow;top_node = new_top;return

16、success;Poping a Linked StackError code Stack : pop( )/* Post: The top of the Stack is removed. If the Stack is empty the method returns underflow; otherwise it returns success . */Node *old_top = top_node;if (top_node = NULL) return underflow;top_node = old_top-next;delete old_top;return success;Li

17、nked Stacks with SafeguardsProblem Examplefor (int i = 0; i 1000000; i+) Stack small;small.push(some_data);Question: Why will the data in the Stack object small become garbage when small goes out of scope?When a object goes out of scope, the data members will automaticallybe destroyed. That is, the

18、node pointed by top_node is released.destructorsC+ provides three devices(additional class methods)to alleviate problems: destructors, copy constructors, overloaded assignment operators.The DestructorStack : Stack( ) / Destructor/* Post: The Stack is cleared. */while (!empty( )pop( );Dangerous in As

19、sigmentStack outer_stack;for (int i = 0; i next = temp temp-next = NULLNULL rear = temprearServer_retrieve: temp = fronttemp front = temp-nextfront item = temp-itemitem delete temp return itemabout implementation of pushQ and popQLinked Queue ConstructorOperations on a Linked Queue Append: rear = ne

20、w_next old_front = front front = old_front -next delete old_frontold_frontnew_rear new_rear-next = NULL rear-next = new_nextServe:Linked Queue MethodExtended Linked QueuesApplication: Polynomial ArithmeticGiven:Reverse Polish Calculator for polynomialsPurpose of the ProjectWe develop a program that

21、simulates a calculator that does addition, subtraction, multiplication, division, and other operations for polynomials rather than numbers.We model a reverse Polish calculator whose operands (polynomials) are entered before the operation is specied. The operands are pushed onto a stack. When an oper

22、ation is performed, it pops its operands from the stack and pushes itsresult back onto the stack.We reuse the conventions of Section 2.3: ? denotes pushing an operand onto the stack, + , , * , / represent arithmetic operations, and = means printing the top of the stack (but not popping it off).Appli

23、cation: Polynomial ArithmeticSimulate a reverse Polish calculator that does addition, subtraction, multiplication, division, and other operations for polynomials rather than numbers.Conventions: ? denotes pushing an operand onto the stack, +,-, * , / represent arithmetic operations, = means printing

24、 the top of the stack (but not popping it off).The Main ProgramPerforming CommandsStubs and TestingWe need a stub class declaration that uses real numbers inplace of polynomials:1. Representing Polynomials as Singly Linked ListsGiven:Data structures for PolynomialsWe represent each term as a node ex

25、poncoefnext For Example: A(x)=3x5-2x3+x2+4Data structures for Polynomials2. Adding PolynomialsExample Add a ( x ) = 5x4 + 2x2 4x + 1 and b ( x ) = 6x3 + 3x2 + 4x54224110Na633241Nbfrontrear save the node in temptemp rear-next = temp rear = temprearrearab52rear63abab10Nrearatempfront54attach ( coef, e

26、xpon, &rear )Specification for PolynomialsAdding a PolynomialsWriting a Polynomialvoid Polynomial : print( ) const /* Post: ThePolynomial is printed tocout . */ Node *print node = front; bool rst term = true; while (print node != NULL) Term &print term = print node-entry; if (rst term) / In this cas

27、e, suppress printing an initial 0+0 . rst term = false; if (print 0) cout ; else if (print 0) cout ; else cout = 0) ? print : (print ); if (r != 1) cout 1) cout X print ; if (print = 1) cout X; if (r = 1 & print = 0) cout next;if (rst term) cout 0; / Print0 for an emptyPolynomial .cout endl;Reading a PolynomialsGroup Project Responsibilities1. Allocation of tasks2. Determining capabilities and specifications3. Timetable4. Stubs, drivers, and testing5. Modifications, extensions, and revisions6. Coordination and supervision7. Documentation and reportingCompl