数据结构描述数据元素的集合及元素间的关系和运算。在数据结构中，元素之间的相互关系称为数据的逻辑结构。按照逻辑关系的不同将数据结构分为线性结构和非线性结构，其中，线性结构包括线性表、栈、队列、串，非线性结构主要包括树和图。数据元素及元素之间关系的存储形式称为存储结构，有顺序存储和链接存储两种基本方式。
线性结构的特点是数据元素之间是一种线性关系，即数据元素“一个接一个地排列”，这种数据结构主要用于描述具有单一前驱和后继的数据关系。

数据类型通常用来执行相对应的算法。

1. 线性表

线性表是最基本的线性结构的一种抽象，主要的基本运算有插入、删除和查找，常采用顺序存储和链式存储两种存储方式来实现。

1.1 定义

由n个元素构成的有限序列（n>=0）,可表示为（a1,a2…an）。对于长度大于0的线性表，其特点有：

1. 存在唯一的第一个元素；
2. 存在唯一的最后一个元素；
3. 除第一个元素外，序列中每个元素均只有一个直接前驱；
4. 除最后一个元素外，序列中每个元素均只有一个直接后继。

1.2 线性表的存储结构

顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的数据元素，从而使逻辑上相邻的两个元素在物理位置上也相邻。在这种存储方式下，元素间的逻辑关系无须占用额外的存储空间来表示。

以 LOC(a_1)表示线性表中第一个元素的存储位置，d表示每个元素所占存储单元的个数，则在顺序存储结构中，第个元素 a的存储位置为:
$$LOC(a_i)=LOC(a_1)+(i-1)\times d$$
顺序存储的优点是：可以随机存取表中的元素，按序号查找的速度很快。
缺点是：插入和删除需要移动后续的元素。
等概率下插入一个元素时平均的移动元素数目是：(可以插入n+1个位置)
$$E_{insert}=\sum _{i=1}^{n+1}{P}_i\times (n-i+1)=\frac{1}{n+1}\sum _{i=1}^{n+1}(n-i+1)=\frac{n}{2}$$
等概率下删除一个元素时平均的移动元素数目是：（可以删除n个元素）
$$E_{delete}=\sum _{i=1}^n{q}_i\times (n-1)=\frac{1}{n}\sum _{i=1}^n(n-i)=\frac{n-1}{2}$$

链式存储

在链式存储方式下，用结点来存储数据元素，表中元素的结点地址可以连续，也可以不连续，因此，数据元素和元素之间的逻辑关系都要存储。其中数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或(和)直接后继的位置信息，指针域中的信息称为指针(或链)。

若结点只有一个指针域，则称为线性链表。

数据结构：

typedef struct node{int data;            //数据域struct node *next;   //指针域
}NODE, *LinkList;

• 插入数据
  
  将指针域进行赋值，然后串联起来。

s->next = p->next;
p->next = s;

• 删除数据
  
  删除某个结点时需要先备份。

q = p->next;   //备份被删除结点的指针
p->next = p->next->next;
free(q);

线性表采用链表作为存储结构时，只能顺序地访问元素，而不能对元素进行随机存取。但其优点是插入和删除操作不需要移动元素。
根据结点中指针域的设置方式，还有双向链表、循环链表和静态链表等链表结构。

1. 双向链表:每个结点包含两个指针，分别指示当前元素的直接前驱和直接后继，可在两个方向上遍历链表中的元素。
2. 循环链表:表尾结点中的指针指向链表的第一个结点，可从表中任意结点开始遍历整个链表。
3. 静态链表:借助数组来描述链式存储结构。

2. 栈和队列

栈和队列的逻辑结构与线性表相同，其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作，故称运算受限的线性表。

2.1 栈

定义

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出(FIO，或后进先出)的线性表。在栈中，进行插入和删除操作的一端称为栈顶(Top)，相应地，另一端称为栈底(Bottom)。不含数据元素的栈称为空栈。(数据输入则压入，所有的操作针对栈顶的元素进行处理。)
栈的基本运算：

1. 初始化栈：创建一个空栈；
2. 判栈空：当栈S为空栈时返回真，否则返回假；
3. 入栈：将元素x放入栈顶，并更新栈顶指针；
4. 出栈：将栈顶元素从栈中删除，并更新栈顶指针；
5. 读栈顶元素：返回栈顶元素的值，但不修改栈顶指针。

存储结构

1. 顺序存储。将一组数据存放在连续的存储单元中，同时设置指针top指示栈顶元素的位置。需要预先定义存储的空间，当栈满时，则发生上溢现象。
2. 链式存储。为了克服上溢现象，因此采用链式存储。用链表作为存储结构的栈称为链栈。由于栈中的元素操作仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。

栈的应用

栈的典型应用包括表达式求值、括号匹配等。在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要作用。

计算后缀表达式时，从左至右扫描表达式:若遇到运算对象，则压入中;遇到运算符，则从栈顶弹出运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式结束。

2.2 队列

定义

两端处理数据，一端输入、一端输出。
队列是一种先进先出(FIFO)的线性表，只允许在队列的一端插入元素，而在另一端删除元素。在队列中,允许插入元素的一端称为队尾(Rear),允许删除元素的一端称为队头(Front)。
基本运算如下：

1. 初始化队列；
2. 判队空；
3. 入队；
4. 出队；
5. 读队头元素。

存储结构

1. 顺序存储
   在操作数据时，改变头尾指针的指向即可。队尾插入数据，队头读取数据。
   
   循环队列：顺序队列假想成环状结构。
   

2. 链式存储
   队列的链式存储也称为链队列。为了便于操作，可给链队列添加一个头结点，并令头指针指向头结点。在这种情况下，队列为空的判定条件是头指针和尾指针相同，且均指向头结点。
   

队列应用

队列常应用于需要排队的场合，如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

3. 串

字符串是一串文字和符号的简称，是一种线性表。字符串中的元素是字符。

3.1 串的定义和运算

串是仅由字符构成的有限序列，是取值受限的线性表。一般记为 $S{=}^{\prime }{a}_1{a}_2\dots a_n^{\prime }$，其中S是串名，单引号括起来的字符序列是串值。

• 串长:即串的长度，指字符串中的字符个数。
• 空串:长度为0的串，空串不包含任何字符。
• 空格串:由一个或多个空格组成的串。虽然空格是一个空白符，但它也是一个字符,计算串长度时要将其计算在内
• 子串:由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串的位置。空串是任意串的子串。
• 串相等:指两个串长度相等且对应序号的字符也相同。
• 串比较:两个串比较大小时以字符的 ASCI码值作为依据。比较操作从两个串的第个字符开始进行，字符的 ASCI码值大者所在的串为大;若其中一个串结束，则以较长的串为大。

串的基本操作：

1. 赋值操作 StrAssign(s,t):将串t的值赋给串 s。
2. 连接操作 Concat(s,t):将串t接续在串s的尾部，形成一个新串。
3. 求串长 StLength(s):返回串s的长度。
4. 串比较 StrCompare(s,t):比较两个串的大小，返回值-1、0 和1分别表示 s<t、 s=t 和s>t 三种情况。
5. 求子串 SubString(s,start,len):返回串s中从 stant 开始的、长度为 len 的字符序列。

3.2 串的存储结构

1. 顺序存储：用一组地址连续的存储单元来存储串值的字符串列。
2. 链式存储：利用链表来存储。需要考虑存储密度问题。