ch04链式栈和队列 (1)

《ch04链式栈和队列 (1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教育部高等教育司推荐国外优秀信息科学与技术系列教学用书数据结构与程序设计计——C++语言描述DataStructuresandProgramDesigninC++RobertL.KurseAlexandeerJ.Ryba主讲：中山大学计算机系高集荣E_mail:Gao_jr@163.com第4章链式栈和链式队列列4.1指针与链式结构(PointersandLinkedStructures)4.2链式栈(LinkedStacks)4.3带保护的链栈(LinkedStackswithSafeguards)4.4链式队列(Linked

2、Queues)4.5应用:多项式的表示和实现(Application:PolynomialArithmetic)4.6抽象数据类型及其实现(AbstractDataTypesandImplementations)4.1指针与链式结构4.1.1指针指针类型(也称为存取类型，或访问类型，或引用类型)是这样的数据类型，其值集由指向其它数据对象的指针(即地址)构成。指针的概念最初是在PL/I语言提出的，目前已被广泛地用于各种高级程序设计语言，如Pascal、C、Modula、Ada等语言。34.1指针与链式结构用指针类型可以建立和使用任

3、意复杂的数据结构，动态地分配内存，从而提高程序执行效率。但指针类型的使用使得程序的可读性有所降低，并且使得程序可靠性降低。在许多高级程序设计语言中，对指针的定义与引用都是类似的。在C++中，一个指针也被称为一个链(link),或一个引用(reference)。41.指针变量的定义在Ｃ++语言中，指针变量是通过单目运算符"*"来定义的。指针定义的一般形式为:<类型名>*<指针变量名>2.指针变量的引用在Ｃ++语言中，有关指针的运算符有两个"*"及"＆"。单目运算符"*"称为指针运算符，或称为间接访问运算符，其运算对象只能是地址或指

4、针。它的功能是对它所操作的地址空间的间接引用，即表示引用其后的地址或指针所指的单元内容。"＆"称为取地址运算符。3.指针变量的应用用指针变量可以构造链表。在链表是使用过程中，要应用到动态“存储分配”的概念。链表结构AlinkedstructureismadeupofnodesentrynextStoredataApointerpointingtothenextnode67主要术语溢出overflow超出空间限制指针pointer一种对象(通常为变量)，它存放了其它变量的地址链表linkedlist组成表的每个元素都包含指向下一个

5、元素的地址。8主要术语顺序的Contiguous一个接一个、的相邻的，与链式的相对自动对象Automaticobject一旦在程序中被声明就存在的对象，可直接通过其名字引用动态对象Dynamicobject在程序运行时才存在，必须通过指针间接引用94.1.2C++指针指针变量定义declareapointerItem*item_ptr;声明了一个指向对象Item的指针变量item_ptr建立动态对象Creatingdynamicobjects:item_ptr=newItem;生成了一个Item类型的新动态对象删除动态对象Del

6、etingdynamicobjects:deleteitem_ptr;回收由item_ptr指向的动态对象。该语句执行完以后，item_ptr的值没有定义，故不可用于赋值。104.1.2C++指针跟随指针Followingpointers*item_ptr代表item_ptr所指的对象空指针NULLpointers一个不指向任何对象的指针，可以被赋值为空指针，即：item_ptr=NULL未定义指针Undefinedpointers含一个随机的内存地址，与空指针不同下图给出了C++的指针与动态内存的关系1112动态数组可用del

7、ete[]dynamic_array；将动态数组所占空间回13链表的结构链表结点的定义我们将用结构struct而不是用类class来描述结点。structNode{//datamembersNode_entryentry;Node*next;//constructorNode();Node(Node_entry,Node*add_on=NULL)};Defaultvalue14下图给出了含有指针的结构15我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点：1.由于开始结点的位置被存放在头结点的指针域中，

8、所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；2.无论链表是否为空，其头指针是指向头结点在的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也就统一了。对链表可以进行创建、插入、删除、查找等操作。164.2链栈栈的链