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

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时称为空表。

对于非空的线性表,有且仅有一个开始结点和一个终端结点

开始结点没有直接前趋,有且仅有一个直接后继;终端结点没有直接后继,有且仅有一个直接前趋;其余任何结点有且仅有一个直接前趋和一个直接后继

1.1 数据结构的定义和分类

1.1.1 数据结构的定义

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

数据结构是带有结构的数据元素的集合,数据元素之间的相互关系,即数据的组织形式。数据的组织方法与效率密切相关,采用不同数据的组织方法其处理效率也不同,对问题找出合适的数据组织方法十分重要。