数据结构与程序设计-链式栈和队列

《数据结构与程序设计-链式栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教育部高等教育司推荐国外优秀信息科学与技术系列教学用书数据结构与程序设计——C++语言描述（影印版）DataStructuresandProgramDesigninC++RobertL.KurseAlexandeerJ.Ryba主讲：中山大学计算机系高集荣E_mail:Gao_jr@21cn.comPDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn第4章链式栈和链式队列4.1指针与链式结构(PointersandLinkedStructures)4.2链式栈(LinkedStacks)4.3带保护的链栈(LinkedStackswit

2、hSafeguards)4.4链式队列(LinkedQueues)4.5应用:多项式的表示和实现(Application:PolynomialArithmetic)4.6抽象数据类型及其实现(AbstractDataTypesandImplementations)2004-4-3《数据结构与算法》讲义2PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn4.1指针与链式结构4.1.1指针n指针类型（也称为存取类型，或访问类型，或引用类型）是这样的数据类型，其值集由指向其它数据对象的指针（即地址）构成。指针的概念最初是在PL／I语言提出的

3、，目前已被广泛地用于各种高级程序设计语言，如Pascal、C、Modula、Ada等语言。n用指针类型可以建立和使用任意复杂的数据结构，动态地分配内存，从而提高程序执行效率。但指针类型的使用使得程序的可读性有所降低，并且使得程序可靠性降低。n在许多高级程序设计语言中，对指针的定义与引用都是类似的。在C++中，一个指针也被称为一个链(link),或一个引用(reference)。2004-4-3《数据结构与算法》讲义3PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cnn1.指针变量的定义n在Ｃ语言中，指针变量是通过单目运算符"*"来定义

4、的。指针定义的一般形式为:n<类型名>*<指针变量名>n2.指针变量的引用n在Ｃ语言中，有关指针的运算符有两个单目运算符"*"及"＆"。n单目运算符"*"称为指针运算符，或称为间接访问运算符，其运算对象只能是地址或指针。它的功能是对它所操作的地址空间的间接引用，即表示引用其后的地址或指针所指的单元内容n3.指针变量的应用n用指针变量可以构造链表。在链表是使用过程中，要应用到动态“存储分配”的概念。2004-4-3《数据结构与算法》讲义4PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn2004-4-3《数据结构与算法》讲义5PDF文件

5、使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn主要术语n溢出overflow§超出空间限制n指针pointer§一种对象(通常为变量)，它存放了其它变量的地址n链表linkedlist§组成表的每个元素都包含指向下一个元素的地址。2004-4-3《数据结构与算法》讲义6PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn主要术语n连续的Contiguous§一个接一个、的相邻的，与链式的相对n自动对象Automaticobject§一旦在程序中被声明就存在的对象，可直接通过其名字引用n动态对象Dy

6、namicobject§在程序运行时才存在，必须通过指针间接引用2004-4-3《数据结构与算法》讲义7PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn4.1.2C++指针n指针变量定义declareapointerItem*item_ptr;声明了一个指向对象Item的指针变量item_ptrn建立动态对象Creatingdynamicobjects:item_ptr=newItem;生成了一个Item类型的新动态对象n删除动态对象Deletingdynamicobjects:deleteitem_ptr;回收由item_ptr指

7、向的动态对象。该语句执行完以后，item_ptr的值没有定义，故不可用于赋值2004-4-3《数据结构与算法》讲义8PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn4.1.2C++指针n跟随指针Followingpointers*item_ptr代表item_ptr所指的对象n空指针NULLpointers一个不指向任何对象的指针，可以被赋值为空指针，即：item_ptr=NULLn未定义指针Undefinedpointers含一个