波兰表达式与逆波兰表达式

常见的算术表达式,称为中缀表达式,例如: 15 + ( 6 – 4 / 2 ) * 3 波兰表达式波兰表达式也称为前缀表达式,以上面的例子为例,其波兰表达式为: 1+ 5 * - 6 / 4 2 3 中缀表达式转换前缀表达式的操作过程为: (1)首先设定一个操作符栈,从右到左顺序扫描整个中缀表达式: 如果是操作数,则直接归入前缀表达式; 如果是括号:如果是右括号,则直接将其入栈;如果是左括号,...

数据结构 第九章 查找

9.1 基本概念(1)列表由同一类型的数据元素(或记录)构成的集合,可利用任意数据结构实现。 (2)关键字数据元素的某个数据项的值,用它可以标识列表中的一个或一组数据元素。 如果一个关键字可以唯一标识列表中的一个数据元素,则称其为主关键字,否则为次关键字。 当数据元素仅有一个数据项时,数据元素的值就是关键字。 (3)查找根据给定的关键字值,在特定的列表中确定一个其关键字与给定值相同的数据元素,并返...

数据结构 第八章 排序

8.1 基本概念有n个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2, …,Kn },相应的下标序列为1,2,…,n。 通过排序,要求找出当前下标序列1,2,…, n的一种排列p1,p2, …,pn,使得相应关键字满足如下的非递减(或非递增)关系,即:Kp1≤ Kp2≤…≤ Kpn ,这样就得到一个按关键字有序的记录序列:{Rp1,Rp2, …, Rpn}。 (1)内部排序与...

数据结构 第七章 图

7.1 图的基本概念7.1.1 概念图G由一个非空项点集V和一个顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:$G=(V, E)$。 7.1.2 有向图和无向图在图中,若用箭头标明了边是有方向性的,则称这样的图为有向图,否则称为无向图。 在无向图中,一条边(x, y)与(y, x)表示的结果相同,用圆括号表示。 在有向图中,一条边< x,y >与< y,x...

数据结构 第六章 树和二叉树

6.1 树6.1.1 树的定义树(tree)是n(n≥0)个结点的有限集T。如果n=0,则称空树;如果n>0(非空树),则: 有且仅有一个特定的结点,称为根(root) ; 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree)。 6.1.2 树的特点在非空树中至少有一个结点——根,树中各...

数据结构 第五章 数组和广义表

5.1 数组的定义在C语言中,一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型,也就是说: 1typedef elemtype array2[m][n]; 等价于: 12typedef elemtype array1[n];typedef array1 array2[m]; 数组一旦被定义,它的维数和维界就不再改变。因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操...

数据结构 第四章 串

4.1 串的基本概念4.1.1 串的概念串(String)是零个或多个字符组成的有限序列。一般记作 S=“a1a2a3…an”,其中S是串名,用双引号括起来的字符序列是串值;ai(1≦i≦n)可以是字母、数字或其它字符。串中所包含的字符个数称为该串的长度。 (1)主串和子串 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字符对应...

数据结构 第三章 栈和队列

3.1 栈3.1.1 栈的定义栈作为一种限定性线性表,是只允许在同一端进行插入和删除操作的线性表。 栈顶:通常将表中允许进行插入、删除操作的一端称为栈顶 (Top),因此栈顶的当前位置是动态变化的,它由一个称为栈顶指针的位置指示器指示。 栈底:同时表的另一端被称为栈底 (Bottom)。 空栈:当栈中没有元素。 满栈:无法申请到栈区可用空间。 上溢:栈已满仍要入栈。 下溢:栈已空仍要出栈。 栈...

数据结构 第二章 线性表

2.1 线性表的概念和运算2.1.1 线性表的概念线性表是 n (n≥0) 个类型相同的数据元素组成的有限序列。其中数据元素的个数n为线性表的长度,当n=0时称为空表。 对于非空的线性表,有且仅有一个开始结点和一个终端结点。 开始结点没有直接前趋,有且仅有一个直接后继;终端结点没有直接后继,有且仅有一个直接前趋;其余任何结点有且仅有一个直接前趋和一个直接后继。 2.1.2 线性表的特点(1)同一性...

数据结构 第一章 概论

1.1 数据结构的定义和分类1.1.1 数据结构的定义数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 数据结构是带有结构的数据元素的集合,数据元素之间的相互关系,即数据的组织形式。数据的组织方法与效率密切相关,采用不同数据的组织方法其处理效率也不同,对问题找出合适的数据组织方法十分重要。 1.1.2 数据结构包括的内容(1)逻辑结构:数据元素之间的逻辑...
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×