数据结构概念

《数据结构概念》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构概念用计算机解决问题时的主要步骤：分析问题，抽象出一个数据模型：基本数据元素以及它们之间的逻辑关系；解决问题需要在上述集合上实现的运算；实现数据元素集合的存储和运算。抽象数据类型在实际软件开发过程中把数据模型与运算“打包”起来形成一个“抽象数据类型”抽象数据类型的实现成为一个工具或者构件，称为数据结构；抽象数据类型也是这个工具的实现者（制造者）和使用者的一个协议，使得使用者和实现者可以独立工作，互不影响，只要他们遵守这个协议。抽象数据类型在C++中，一个ADT与其实现构成一个class,或者说抽象数据类型可以由C++的类来描述，ADT的每个运算对应一个成员函数。例如，表示圆

2、的classclassCircle{private:floatr,x,y;public:Circle(floatv1,floatv2,floatv3);floatarea()={returnpi*r*r};…};算法算法的概念与特点；算法设计的一般要求；复杂度的估算与表示；Chapter2栈（Stacks）栈的规格说明（StackSpecifications）栈的实现（ImplementationofStacks）栈的应用（Application:Bracketmatching）抽象数据类型及其实现（AbstractDataTypesandTheirImplementations）

3、YoutakeoneonthetopYouputoneonthetopImagethatyouwanttohaveaprogramthatreadsalistofintegersandthenoutputtheminthereverseorder.Howdoyouprogramit?Stacks(栈)一个栈是一些元素的线形列表，其中元素的插入和删除均在表的同一端进行。插入和删除发生的一端称为栈顶（thetopofthestack）。栈的两个基本操作插入和删除分别称为push(入栈)andpop(出栈)。栈的特点是“后进栈的元素先出栈”（lastin,firstout），故栈又称为后

4、进先出表（LIFO）。StacksinSTLTheStandardTemplateLibrary(STL)aC++library.agenericlibrary:itscomponentsareheavilyparameterized,i.e.almosteverycomponent(classes,functions)isatemplate.TheSTLstackimplementationItisaclasstemplate.Itsfirstparameterspecifieswhatsortofitemsthestackcontains.Ithasasecondparamet

5、erthathasadefaultvalue.Thesecondparametercontrolswhatsortofstackimplementationwillbeused.MethodsinStacks–voidstack::push(value):thismemberplacesvalueatthetopofthestack.–voidstack::pop():thismemberremovestheelementatthetopofthestack.Notethatthepoppedelementisnotreturnedbythismember.Nothinghappe

6、nsifpop()isusedwithanemptystack.Stackmethods-boolstack::empty():thismemberreturnstrueifthestackcontainsnoelements.–unsignedstack::size():thismemberreturnsthenumberofelementsinthestack.–Type&stack::top():thismemberreturnsareferencetothestack’stop(andonlyvisible)element.Itistheresponsibilityofth

7、eprogrammertousethismemberonlyifthestackisnotempty.UsingStacksExample:ReversingalistofnumbersUsingSTLstackimplementationAlwaysspecifypreconditons,postconditionsoftheprogram!ReversingalistChapter2栈（Stacks）栈的规格说明（StackSpecifications）栈的实现（