一. 存储结构

线性表的存储结构可以分为顺序存储和链式存储

顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

struct SeqList
{
    DataType data[ListSize]; //用数组存储线性表中的元素
    DataType length; //顺序表中元素的个数
};

链式存储指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

struct LNodeType
{
    DataType data; //数据域
    LNodeType* next; //指针域
}

补充知识：指针

什么是指针

它是一个特殊的变量，它里面存储的数值是内存里的一个地址。

指针的好处

1. 指针使程序的不同部分能够共享数据
2. 利用指针，能在程序执行过程中预留新的内存空间
3. 指针可以用来记录数据项之间的关系
4. 指针允许你以更简洁的方式引用大的数据结构
5. ......

二. 应用

(一). 栈

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性 表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压 栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或 退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 习题 题目描述 给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes ，否则输出 No 。 输入输出格式

第一行一个整数 表示序列长度； 第二行 个整数表示入栈序列； 第二行 个整数表示出栈序列；

输入格式

输出 Yes 或者 No

样例 输入

5
1 2 3 4 5
5 4 3 2 1

输出

Yes

(二). 队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后 端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队 尾，进行删除操作的端称为队头。

题目描述 存在一个翻译软件，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英 文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。 假设内存中有 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 ，软件会将新单词存入一个未使用的内存单元；若内存中已存入 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。 假设一篇英语文章的长度为 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

第一行为两个正整数 代表内存容量和文章的长度。

第二行为 个非负整数，按照文章的顺序，每个数大小不超过 1000 ）代表一个英文单词。文章中

两个单词是同一个单词，当且仅当它们是相同数字的时候。

输出格式

对于查询操作时，输出答案。

样例

输入

3 7
1 2 1 5 4 4 1

输出

5