数据结构（线性表-队列）

1. 数据结构的基本概念

采用建模-算法-编程-调试的步骤，可解决数值计算问题，对数据要求不高，但对更多的非数值运算，无法直接用函数，过程求解必须研究新算法，考虑新结构。

• 每列叫一个字段，存储一种属性。
• 每行是一条记录，每条记录结构相同，只是值不同。
• 对象间存在先后顺序，每个学生后面紧跟一个学生，前面也仅连一个学生。此类关系成为一对一的线性关系

基本概念：

数据结构是一门研究非计算程序设计问题中操作对象及他们的关系的学科。研究数据的逻辑结构和物理结构，定义相应的运算和操作

数据： 是对信息的一种符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包含数据，字符串，声音，图像等。

数据元素： 在计算机程序中作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位

存储结构：

1. 顺序存储： 把逻辑上相邻的元素存储在相邻的数据单元中，用其存储位置来表示其逻辑关系
2. 链式存储：逻辑上相邻的元素在存储器中不一定相邻。用附加地址表示数据元素之间的逻辑关系
3. 索引存储：结构在存储结点信息的同时，还建立附加的索引表。存取数据时，都必须依赖索引
4. 散列存储：根据结点的值确定结点的存储位置。通过某个函数（散列函数）计算出其存储地址。它只存储结点的数值而不存储结点间的关系

数据运算就是施加于数据的操作。随着类型的不同有各种不同的操作。例如表格可有增删改查等操作

数据类型需要通过固有数据类型来实现

2. 线性表的基本概念

线性表特征

1. 非空的线性表，有且仅有一个开始结点

2. 有且仅有一个终端结点a,它没有直接后继，而仅有一个直接前趋

3. 其余的内部结点都有且仅有一个直接前趋和一个直接后继

线性表的基本运算： 初始化，保存，输出，插入，删除

InitList(L) 初始化：构造一个空的线性表L

ListLength(L) 求长度： 返回表L的数据元素个数。

GetElem(L,i,e) 取值：返回第i个数据元素e.

Locat(L,x) 定位： 返回值x所在位置的序号i.

InsElem(L,i,x) 插入： 在线性表L的第i个元素之前插入数据元素x,表长加1

DelElem(L,i) 删除： 在给定的线性表L中，删除第i个元素。线性表L长度减1

DispList(L) 输出： 依次显示表值

3. 线性表的顺序存储和链式存储

把线性表的结点按逻辑顺序依次放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表

优点：

1. 可以随机存取其中的任意元素

2. 实现简单

3. 节省存储空间

缺点：

1. 最大个数需预先确定

2. 插入，删除运算的效率低（需要移动数据元素）

3. 存储空间不便于扩充

线性表的链式存储称链表，

为线性表的每个元素都申请相同的存储单元，存储单元由两部分组成： 一部分存数据元素值，成为数据域；另一部分存直接后继（前趋）结点的地址，成为指针域。将结点串起来，就形成链表。只有一个指针域的链表成为单链表

链表是一个动态的结构，不需要预先分配空间，因此生成链表的过程是一个节点逐个插入的过程。

从空链表开始，将保存数据元素的新存储结点插入到当前已部分创建好的链表的尾结点后面，为此必须增加一个尾指针，使其指向当前链表的尾结点

优点：

1. 最大个数不需要预先指定

2. 插入，删除运算，不需要移动别的元素，效率高

3. 存储空间便于扩充

缺点：

1. 不可以随机存取其中的任意元素，需要从头结合next指针进行访问

2. 利用指针，实现较复杂

3. 需要额外空间存储结点的指针

如何选择存储结构

1. 基于存储的考虑，当长度或存储规模难以估计时，不宜采用顺序表

2. 基于运算的考虑，在链表中插入，删除，操作主要是改变指针，不需要移动元素。

但是查询时，链表需要从头遍历

3. 基于环境的考虑 链表操作基于指针，编程较困难

4. 队列和栈

栈是限制仅能在一端进行插入与删除的线性表。没元素的栈为空栈。

允许插入和删除的一端称为栈顶，另一端称为栈底

栈是按后进先出的原则进行的。因此栈又称为后进先出表

栈的特性：

1. 栈属于加了限制条件的线性结构

2. 栈是后进先出的线性表

1. 进栈和出栈只能从栈顶进行
2. 栈中的元素个数可以是0
3. 栈的元素个数不能是无穷多个
4. 每个栈中的元素类型相同

栈的应用

1. 数制转换

2. 表达式求值

3. 迷宫求解

队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是操作受限的线性表

允许删除的一端叫做队头，允许插入的一端叫队尾

特点： 先进先出

队列的顺序存储及基本运算

队列的顺序存储结构可以简称为顺序队列，用一组地址连续的存储单元依次存放队列中的数据元素。设立两个指示器。指向队头元素的指示器front,指向队尾的元素位置的指示器rear

当前队列并未占满，但队列中元素出队后让出的实际可用空间却不能得以使用，因此把这种溢出现象称为“假溢出”

解决办法之一： 将队列元素存放数组首尾相接，形成循环队列