基本数据结构总结.docxVIP

基本数据结构算法及其应用长沙市一中 杨曜嘉【摘要】首先,数据结构是一门计算机语言学的基础学科，它不属于任何一门语言，其体现的是几乎所有标准语言的算法的思想。而且数据结构对于竞赛来说，也是其考察的重点。就我个人的理解，数据结构是认为赋予数据其他的意义，给予程序更高的运行效率与储存效率；可以说，数据结构给予了数据以生命。本文将对基本数据结构进行一定的说明，介绍其算法与应用，加以总结。让我们对数据结构有一个基本的认识。【关键字】基本数据结构，栈，队列，树，图【目录】线性数据结构栈(Stack)及其应用栈的操作栈的基本应用队列(Queue)及其应用队列的操作队列的基本应用其他的线性结构树形结构树的定义二叉树特殊的树图形结构图的定义概念图的遍历图的算法欧拉路/欧拉回路最短路最小生成树拓扑排序总结【正文】一． 线性数据结构定义：简单地说，线性结构是n个数据元素的有序（次序）集合。栈(Stack)及其应用概念栈(Stack)是限定仅在表尾进行插入与删除运算的线性表。这里表尾称为栈顶(top),相应的表头称为栈底(bottom)。当栈中没有元素时，称为空栈。例如给定栈S=(a1,a2,….,an)，则a1为栈底元素，an为栈顶元素。栈中元素是按 a1,a2,….,an的顺序进栈。但退栈的第一个元素是an。也就是说，栈遵守后进先出的原则。因此，栈也称为后进先出表(Last In Fist Out,简称LIFO)。栈的操作建立一个空栈：建立一个空的栈S。进栈(push) : 在栈的顶部插入元素。出栈(pop)：删除栈顶元素。取栈顶元素(top)：取得栈顶元素，但并不会删除。判断栈是否为空(empty) ：如果栈为空着返回1，否则返回0。在对栈的操作过程中，我们是用数组和一个指向栈顶元素的“指针”(可以是真指针也可以是模拟的数组下标的指针)来完成对栈的操作。在实际操作过程中，在进栈时可能出现“上溢”(及数组已经装满了)与出栈时“下溢” (及数组已经空了)的现象。这是我们需要对这种情况做特殊处理，或给出溢出信息，或停止操作等。下溢可以作为程序转移的特殊标志，是十分有用的。而上溢是十分危险的，会导致程序错误(RE)。由于在C++中，stack库提供了栈这个类，所以我们实际编程中不太需要手写栈，它提供了比较方便的操作。Stack库作用stackType name定义一个类型为Type，名为name的栈bool empty()判断栈是否为空int size()返回栈的大小Type top()返回栈顶元素void push(Type a)把元素a插入栈顶Void pop()删除栈顶元素Void swap(stack a)与栈a交换元素栈的基本应用①表达式求值表达式求值是程序设计中一个运用栈的典型问题。我们用栈来实现“算符优先法”计算表达式。要正确求出表达式的值，我们得先“翻译”表达式，看明白优先运算什么，然后运算什么。算符优先法就是根据运算符优先关系来实现对表达式的编译或解释执行的。在这里我们以:4 + 2 * ( 15 – 10 ) / 5 来作为例子分析任何表达式都是由操作数(operand)，运算符(operator)和界限符(delimiter)组成的，我们称他们为单词。一般的，操作数是指常量或变量或变量的标识符，在上面例子中，就是4,2,15,10,5。运算符可以分为算数运算符，关系运算符和逻辑运算符。在这里，我们就仅仅讨论算数运算符，读者不难把其推广到其他运算符。+，*，-，/就是上面式子的运算符。界限符就是指左右括号啦。我们可以开两个栈，一个是操作数的OVS，另一个是运算符与界限符的OPS。编译程序从左至右扫描表达式到语句结束，其处理原则是:凡是遇到操作数，一律入操作数栈。当遇到运算符时，则将运算符的优先级与运算符中栈顶元素的优先级比较；如果该运算符的优先级较大，就进栈；反之，取出栈顶运算符，再操作数栈中连续取出两个栈顶的操作数作为对象进行运算，并将结果闯入操作数栈然后继续比较该运算符与栈顶运算符(一直比到栈顶运算符优先级小于当前运算符)。如果读到左括号(左括号的优先级最低)，则入栈。读到右括号，就弹出运算符栈的运算符进行运算，直到弹出的为一个左括号为止。为了方便运算，我们可以在表达式上认为添加一个又括号在上面的例子中，栈的变化是这样的。读入的单词操作数栈运算符栈说明44空4入栈+4++入栈24 2+2入栈*4 2+ **入栈(4 2+ * ((入栈154 2 15+ * (15入栈-4 2 15+ * ( --入栈104 2 15 10+ * ( -10入栈)4 2 5+ * -出栈，15-10入栈/4 2 5+ * *出栈，2*5入栈，/入栈54 10 5+ /5入栈)（结尾人为的右括号）6空/出栈，1