一个人在学校的日子有些寂寞，但是st说男人要耐得住寂寞，做学问也是如此吧。今天看了线性表、栈和队列的内容。以下是学习记录。

线性表（list）

    1.定义：0个或多个数据元素的有限序列，元素有且只有一个直接后继和一个直接前驱；基本操作ListLength、GetElem、LocateElem、ListInsert等，并集Union的实现。

    2.线性表的顺序存储结构

      指用一段地址连续的存储单元依次存储数据元素（c语言中用数组实现改结构）；数组长度>=线性表的长度；对于任意位置的存入或取出的所需时间相同O(1)：随机存储结构

      顺序结构的插入与删除的算法实现（注意考虑异常的判断），整体移动，平均（n-1）/2，时间复杂度O（n）；顺序结构的优点：快速存取，无需指针的开销；缺点：移动大量的元素，难以确定线性表的空间容量。

    3.线性表的链式存储结构

      改进顺序结构的缺点；由结点（Node）构成，每个结点分为数据域和指针域；头指针和头结点的区别。

      单链表的插入（修改p和p->next指针），malloc：生成一个新的结点；结点的删除，free。单链表的整表创建，头插法和尾插法，单链表整表删除；查找：顺序O（1），单链O（n）；插入删除：顺序O（n），单链O（1）。

      静态链表：用数组（每个数组元素由data和cur游标组成）描述的链表，用游标cur和数组下标实现指针的功能；适用于没有指针的高级语言实现单链表结构。

      循环链表：将单链表中的终端结点由空指针改为指向头结点；与单链的区别：p->next为空或者指向头结点来终止循环。

      双向链表：在单链的结点中再设指向前驱结点的指针域。

栈（stack）

    1.定义：是限定只在表尾（栈顶top）插入和删除的线性表，即LIFO的线性表。

    2.栈的插入（进栈、压栈 push）；栈的删除（出栈、弹栈 pop）;空栈：top == -1。

    3.栈的顺序存储结构

     空栈：top == -1；push和pop的实现通过修改栈顶指针top来实现；一个数组存储两个栈，分别在数组两端，栈空与栈满（两个栈顶指针相差1），要求两个栈的空间需求有相反关系时运用此数据结构有意义。

    4.栈的链式存储结构

      栈链：不需要头节点，栈空top = NULL；push和pop操作通过修改top指针实现；若元素个数变化大则用链栈，反之则用顺序栈。

    5.栈的应用——递归:必须有递归的终止条件；递归算法是选择结构，易读和理解，但大量的递归调用会建立大量的函数副本，耗时间和内存；迭代是循环结构。

      栈的应用——四则运算（后缀、逆波兰表示法）：中缀表达式（标准四则运算）与中缀表达式的转换与计算。

队列（queue）

   1.定义：是只允许在一端（队尾）插入，在另一端（队头）删除的线性表，即FIFO的线性表。

    2.队列的顺序存储结构

      一般的顺序存储存在假溢出的问题，对其改进得到循环队列（首位相连的顺序存储结构队列）；循环队列满条件：（rear+1）%QueueSize == front(保留一个元素空间)，循环队列长度公式：（raer-front+QueueSize）%QueueSize；循环队列的插入与删除操作的算法实现；循环队列缺点：数组可能溢出。

    3.队列的链式存储结构

      简称链队列，就是线性表的单链表（只能尾进头出而异）；队满和队空的判断；入队（改rear指针）与出队（改front指针）操作的算法实现

    4.循环队列必须有一个固定长度，可能存在浪费；链队列不存在这个问题，但会增加指针存储的空间开销。