数据结构——基本概念

数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素、数据项：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

基本概念——三要素

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

• 集合：各个元素同属一个集合，别无其他关系。
• 线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。
• 树形结构：数据元素之间是一对多的关系。图结构：数据元素之间是多对多的关系。
• 
  

算法——什么是算法

• 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
• 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
• 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
• 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法—算法效率的度量

线性表

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：

	L = (a1, a2, . , ai , ai+1, . , an)

几个概念：

• ai是线性表中的“第i个”元素线性表中的位序。
• a1是表头元素；an是表尾元素。
• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
• 

线性表——存储结构

线性表——插入删除操作

• 顺序存储：插入元素前要移动元素以挪出空的存储单元，然后再插入元素。删除元素时同样需要移动元素，以填充被删除元素的存储单元。
• 链式存储：
• 

栈和队列

• 线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：

  L = (a1, a2, . , ai , ai+1, . , an)

• 栈（Stack）是只允许在一端进行插入或删除操作的线性表。
  

• 队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一-端称为队尾（Rear)，允许删除元素的一-端称为队头（Front）。
  

串

串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S=‘a1a2~~~an’，其中S是串名，a1a2an是串值。

（1）空串：长度为零的串，空串不包含任何字符。
（2)空格串：由一个或多个空格组成的串。
（3）子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
（4）串相等：指两个串长度相等且对应位置上的字符也相同。
(5)串比较：两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCII码值大者所在的串为大；若其中一一个串先结束，则以串长较大者为大。

1、对串进行的基本操作有以下几种。

（1）赋值操作StrAssign(s,）：将串t的值赋给串s。
（2）连接操作Concat(s,t):将串t接续在串s的尾部，形成一个新串。
(3）求串长StrLength(s)：返回串s的长度。
（4)串比较StrCompare(s,t)：比较两个串的大小。
(5)求子串SubString(,tart,len):返回串s中从start开始的、长度为len的字符序列。

2、串的存储结构

（1）串的顺序存储：定长存储结构
(2）串的链式存储：块链子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

数组

稀疏矩阵

广义表