线性表

线性表指零个或多个数据元素的有限序列。
在非空表中每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的次序。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。

比起顺序存储结构每个数据元素只需要存储一个位置就可以了。现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

我们把存储数据元素信息的领称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点（node）。

我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点为空。头结点的数据域一般不存储任何信息。

头指针

• 头指针是指链表比指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
• 头指针具有标识作用，所以常用头指针冠以链表的名字（指针变量的名字）。
• 无论链表是否为空，头指针均不为空。
• 头指针是链表的必要元素。

  头结点

• 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义（但也可以用来存放链表的长度）。
• 有了头结点，对在第一元素结点前插入结点和删除第一结点起操作与其他结点的操作统一了。
• 头结点不一定是链表的必要元素。

头插法建立单链表

头插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。

尾插法建立单链表

尾插法从一个空表开始，生成新结点，读取数据存放到新结点的数据域中，然后将新结点插入到当前链表的表尾上，再用新结点来赋值给暂存结点，以达到每次暂存结点都是尾结点的目的。

单链表结构与顺序存储结构优缺点

存储分配方式：

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。
  时间性能
• 查找
  • 顺序存储结构O(1)
  • 单链表O(n)
• 插入和删除
  • 顺序存储结构需要平均移动表长一半的元素，时间为O(n)
  • 单链表再计算出某位置的指针后，插入和删除时间仅为O(1)
• 空间性能
  • 顺序存储结构需要预分配存储空间，分大了，，容易造成空间的浪费，分小了，容易发生溢出。
  • 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

总之，线性表若需要频繁的查找，很少进行插入和删除操作时，宜采用顺序存储结构。如果需要频繁插入和删除时，宜采用单链表结构。

静态链表

用数组描述的链表叫做静态链表。

• 我们对数组的第一个和最后一个元素做特殊处理，他们的data不存放数据。
• 我们通常把未使用的数组元素成为备用链表。
• 数组的第一个元素，即下标为0的那个元素的cur就存放备用链表的第一个结点的下标。
• 数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素下标，相当于单链表中头结点的作用。
  静态链表的插入，每当进行插入操作时，便可以从备用链表上取得第一个结点作为待插入的新结点。

静态链表的删除。每当进行删除操作时，将指定元素上一位的下标改为下一位元素的下标，再将第一个元素的游标改为删除的下标。

静态链表的优缺点

• 优点
  • 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了再顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
• 缺点
  • 没有解决连续存储分配数组带来的表长难以确定的问题
  • 失去了顺序存储结构随机存取的特性。
    总之，静态链表其实时为了给没有指针的编程语言设计的一种实现单链表功能的方法。尽管我们可以用单链表就不用静态链表了，但这样的思考方式时非常巧妙的，应该理解其思想，以备不时之需。

双链表

在线性表的链式存储结构中，每个物理节点增加一个指向后继节点的指针域和一个指向前驱节点的指针域。优点：从任一节点出发可以快速找到其前趋节点和后继节点，从任一节点出发可以访问其他节点。

//双链表的定义
typedef struct DNode{
    ElemType data;
    struct DNode *prior; //指向前趋节点
    struct DNode *next; //指向后继节点
} DLinkList;

广义表

广义表是线性表的推广，对于线性表而言，n个元素都是基本的单元素。广义表中这些元素不仅可以使单元素也可以是另一个广义表。

//广义表的定义
typedef struct GNode *GList;
struct GNode{
    int Tag;    //标志域：0表示结点是单元素，1表示结点是广义表。
    union{  //子表指针区域Sublist与单元素数据域Data复用，即共用存储空间
        ElementType Data;
        GList SubList;
    }URegion;
    GList Next; //指向后继结点
};

多重链表：链表中的节点可能同时隶属于多个链。多重链表中节点的指针域会有多个，如上面的广义表包含了Next和SubList两个指针域。但是包含多个指针域的链表并不一定是多重链表，比如双向链表。另外树、图这样相对复杂的数据结构都可以采用多重链表的方式实现存储。

栈

栈是限定仅在表尾进行插入和删除操作的线性表。栈元素具有线性关系，即前驱后继关系。

栈的结构定义

typedef int SElemType   //SElemType根据实际情况而定，这里假设为int。
typedef struct{
    SElemType data[MAXSIZE];
    int top;   //用于栈顶指针
}SqStack;

堆栈：具有一定操作约束的线性表，旨在一端（栈顶，Top）做插入、删除操作。插入数据：入栈（Push）。删除数据出栈（Pop）。后入先出原则。

入栈

void Push(Stack Ptrs,ElementType item){
    if(Ptrs->Top == MaxSize-1){
        printf("堆栈满"):return;
    }
    else{
        Ptrs->Data[++(Ptrs->Top)] = item;
        return;
    }
}

出栈

Sratus Pop(SqStack *S,SElemType *e){
    if (S->top==-1)
        return ERROE;
    *e = S->data[S->top];  //将要删除的栈顶元素赋值给*e
    S->top--;    //栈顶指针减1
    return OK;
}

两栈共享空间结构就是让栈底在数组的两端，这样两栈如果增加元素就是往中间靠拢。这样可以最大程度利用空间。

链栈是指栈的链式存储结构，栈顶放在单链表的头部。如果栈在使用过程中元素变化不可预料，那麽最好使用链栈，反之则使用顺序栈更好一些。

递归

我们把一个直接调用自己或经过一系列的调用语句间接地调用自己地函数称作递归函数。每个递归定义必须至少有一个条件，满足条件时递归不再进行，否则就会造成栈溢出。在递归前行阶段，对于每一层递归，函数的局部变量、参数值和返回地址被push。在退回阶段，位域栈顶的局部变量、参数值和返回地址被pop，用于返回调用层次中执行代码的其余部分也就是恢复了调用状态。

队列

队列是只允许在一段进行插入操作，而在在另一端进行删除操作的线性表。队列是一种先进先出的线性表，允许插入的一段称为队尾，允许删除的一端称为队头。

循环队列，循环队列是为了解决假溢出问题。我们把队列的这种头尾相接的顺序存储结构称为循环队列。