线性表的学习

• 线性表

定义

n个类型相同数据元素的有限序列，记作：a0，a1,a2,a3,...ai-1,ai,ai+1...an-1(这里的0，1，2，3，i-1,i,i+1,n-1都是元素的序号)

特点

除第一个元素无直接前驱。最后一个元素无直接后续，集合中每个元素都有一个直接前驱和一个后续元素

删除和插入元素，再插入或删除位置之后的所有元素都会移动位置

插入元素

删除元素

线性表的链式存储

单链表

链表是一些列存储数据元素的单元通过指针串联起来，每个单元有两个域，一个用于存储数据，一个是指向其他单元的指针。这个单元称为节点。

数据域存储的是数据的引用。指针域存储的是下一节点的引用。

节点的的数据域存储当前节数据的物理地址，指针域存储下一个节点的地址信息

单链表结构

单链表特点

从单链表的结构可以看出，由于链表前一个结点的指针指向后一个结点，所以单链表可以通过前一个元素找到后一个元素，但无法通过后一个结点找到前一个结点。

单链表的查找

单链表的查找只能从首结点开始依次查每个节点的next。

单链表插入

不需要移动所有元素

单链表删除结点

双向链表

双向链表是在单项链表的基础上增加一个域，该域用于指向该结点的前驱结点。

双向链表的结点：

由于双向链表结构特点，结点中存储了前一个结点和后一个结点的指针，所以双向链表可以通过前一个结点查找后一个结点，也可以通过后一个结点查找前一个结点。

双向链表结构

双向链表插入

双向链表的删除

数组，单链表，双链表三种线性表的比较：

基于时间的比较

查找

数组属于顺序存储，可以随机存取，每个元素都有一个存储序号，查找时根据序号查找，查找速度较快。链式存储的双向链表和单向链表查找时需要从头开始查找，依次遍历目标元素之前的元素。所以查找速度低于顺序存储的数组。

因此查找速度：

数组>单项链表/双向链表

插入，删除

对于数组而言，首先需要通过序号定位元素，然后将目标元素插入或者删除，插入或删除位置之后的元素需要改变位置。这些操作可能引起大量元素移动。双向链表和单项链表删除或插入时，只需要在插入位置将前后指针更改即可，因此链表的删除插入操作呢优于数组。

删除，插入性能：

单项链表/双向链表>数组

基于空间的比较

顺序存储空间是预先分配好的，属于静态分配，如果没有使用完成吗，就会造成大量空闲空间。链式结构是动态分配空间，不会存在剩余情况，因此不会造成浪费。

从空间的角度看：

链式存储>顺序存储

链接表

对于链表的删除，插入和空间利用率都比较有优势，但是对于定位元素必须从头或从尾部开始，比较耗时。

• 栈与队列

栈和队列从结构上来说也属于线性结构，区别在于某些操作与上面说的线性结构有区别。

栈：先进后出

队列：先进先出

栈

栈就像一个桶，桶装满东西，只能从入口倒出去，桶的顶端叫栈顶，桶的底端叫栈底。只允许在一端插入和删除，不允许在任何位置查找，删除，插入。栈中没有东西叫空栈，往栈里面放元素叫入栈，删除元素叫出栈，

栈的存储

栈是一种操作受限的线性表，所以可以用线性表来实现栈，可以链式存储也可以顺序存储。顺序存储可以选择数组来实现，选择数组的下标最大的一端作为栈顶，还需要设置一个指针top指向栈顶，如果是空栈，top=-1;

链式存储选择单链表实现，由于链表的特性，链表的头部作为栈顶，可以使用带头结点的链表和不带头结点的链表。

队列

队列也是一种受限的线性结构，队列就像是一根水管（比喻不是很恰当，但大概是这个意思），只能从一端进入，一端出去。因此队列是先进先出。

一般从队列尾部插入元素，从队列首部删除元素。向队尾插入元素叫入队，从队首删除元素叫出队，删除后，后面的元素成为新的队首元素。

队列的顺序存储

队列的顺序存储

队列的顺序存储可以使用数组实现，但数组实现不是很好，删除或插入时，数组的每个元素都需要移动一个为位置，改用循环数组实现。队尾指针指向最后一个元素的下一个单元，队首指针指向队首元素所在的单元。需要入队时，元素直接存入队尾指针指向的单元，队尾指针逆时针转动一位；需要出队时，只需要将队首指针逆时针转动一位即可。

区分队列为空还是满方法：

少使用一个空间，当队尾指针逆时针转动一位指向队首指针时，表示队列已经满了，不能再入队。此时认为已经满了。

或者增加变量size来表示，如果size=maxSize则认为队列满了。

队列的链表实现

可以采用带头结点的单链表实现。选择链表的头部作为队首，链表的尾部作为队尾。需要两个指针，分别是队首指针和队尾指针。

队首指针始终指向链表头结点，即首个元素的前一个没有元素的头结点。队尾指针指向队尾当前队尾元素所在的结点，如果队列为空，队尾指针和队首指针均指向头结点。

堆栈的应用

1.进制转换，如十进制转换为二进制，每次进行除2当时，得到每次的余数，恰好是将最后得到的数先输出。

2023转换为二进制是11111100111。

2.嵌套的括号校验，有了开始的括号，必须要有结束括号与之匹配，才算正确.

如：{[]()}和{[{}][()]}这些是正确的，但如果是{[}],{[(]])}这些是错误的。

3.迷宫就求解