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

常见的算术表达式,称为中缀表达式,例如:

5 + ( 6 – 4 / 2 ) * 3

数据结构 第九章 查找

9.1 基本概念

(1)列表
同一类型的数据元素(或记录)构成的集合,可利用任意数据结构实现。

(2)关键字
数据元素的某个数据项的值,用它可以标识列表中的一个或一组数据元素。

如果一个关键字可以唯一标识列表中的一个数据元素,则称其为主关键字,否则为次关键字。 当数据元素仅有一个数据项时,数据元素的值就是关键字。

数据结构 第八章 排序

8.1 基本概念

有n个记录的序列{R1,R2,…,Rn},其相应关键字的序列是{K1,K2, …,Kn },相应的下标序列为1,2,…,n

通过排序,要求找出当前下标序列1,2,…, n的一种排列p1,p2, …,pn,使得相应关键字满足如下的**非递减(或非递增)**关系,即:Kp1≤ Kp2≤…≤ Kpn ,这样就得到一个按关键字有序的记录序列:{Rp1,Rp2, …, Rpn}

数据结构 第七章 图

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)。

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

5.1 数组的定义

在 C 语言中,一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型,也就是说:

typedef elemtype array2[m][n];

等价于:

typedef 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)。

空栈:当栈中没有元素。