链表

链表属于线性表中的一种数据结构，它由若干个节点组成(每个节点代表一个元素)，且节点在内存中的存储位置通常是不连续的。这里我们先来了解动态链表，动态链表的两个节点之间一般通过一个指针来从一个节点指向另一个节点 ，因此动态链表的节点一般由两部分构成，即数据域和指针域：

struct node{
    int data;
    node* next;
};

(1)创建一个动态链表：

#include "stdafx.h"
#include<iostream>
#include<stdlib.h>
using namespace std;

struct node {
    int data;
    node* next;
};

node* create(int Array[]) {
    node *p, *pre, *head;//pre保存当前节点的前驱节点，head为头结点
    head = new node;//创建头结点
    head->next = NULL;//头结点不需要数据，且指针域指向NULL
    pre = head;//记录pre为head
    for (int i = 0;i < 5;i++) {
        p = new node;//新建节点
        p->data = Array[i];//将Array[i]赋给新建的节点作为数据域，也可以cin输入
        p->next = NULL;//新节点的指针域设为NULL
        pre->next = p;//前驱节点的指针域设为当前新建节点的地址
        pre = p;//把p设为pre，作为下一个节点的前驱节点
    }
    return head;//返回头结点指针
}

int main() {
    int Array[5] = { 5,3,6,1,2 };
    node* L = create(Array);//新建链表，返回头指针head给L
    L = L->next;//从第一个节点开始有数据域
    while (L != NULL) {
        cout << L->data << endl;//输出每个节点的数据域
        L = L->next;
    }
    system("pause");
    return 0;
}

(2)动态链表查找元素：

int search(node* head, int x) {
    int count = 0;//计数器
    node* p = head->next;//指向链表的第一个节点
    while (p != NULL) {//遍历整个链表
        if (p->data == x) count++;//当节点数据域为x时，则count++
        p = p->next;//指向下一个节点
    }
    return count;
}

(3)动态链表插入元素：

void insert(node* head, int pos, int x) {
    node* p = head;//指向链表的头节点
    for (int i = 0;i < pos - 1;i++) {//遍历到链表的pos-1的位置，即插入位置的前一个节点位置
        p = p->next;
    }
    node* q = new node;//新建节点
    q->data = x;//其数据域为x
    q->next = p->next;//新节点的下一个节点指向原先插入位置的节点
    p->next = q;//前一个位置的节点指向新节点
}

(4)动态链表删除元素：

void del(node* head, int x) {
    node* p = head;//指向链表的头结点
    node* q = p->next;//指向链表的第一个节点
    while (q != NULL) {
        if (q->data == x) {//数据域为x，删除q节点
            p->next = q->next;//删除q节点
            delete(q);//释放内存空间
            q = p->next;
        }else {//数据域不为x，p、q节点同时后移一位
            p = q;
            q = q->next;
        }
    }
}

以上所述都是动态链表的范畴，需要指针来建立节点之间的连接关系。而对于有些问题来说，节点的地址是比较小的整数(例如5位数的地址)，这样就没有必要去建立动态链表，而应该使用方便得多的静态链表。静态链表的实现原理是hash，即通过建立一个结构体数组，并令数组的下标直接表示节点的地址，以此来达到直接访问数组中的元素就能访问节点的效果。需要注意的是：在使用静态链表时，尽量不要把结构体类型名和结构体变量名取成相同的名字。其定义方法如下：

struct Node{
    typename date;//数据域
    int next;//指针域
    XXX;//节点的某个性质，不同的题目会有不同的设置
}node[maxn];

其中的next是一个int型的整数，用来存放下一个节点的地址(事实上就是数组下标)，例如：如果初始节点的地址为11111，第二个节点的地址为22222，第三个节点的地址为33333，且第三个节点为链表末尾，那么整个静态链表的节点就可以通过下面的写法连接起来：

node[11111].next=22222;
node[22222].next=33333;
node[33333].next=-1;//-1对应动态链表中的NULL，表示没有后继节点

一般来说，静态链表的初始化需要对定义中的XXX进行初始化，将其定义为正常情况下达不到的数字(而常常需要小于所能达到的数字)，例：

for(int i=0;i<maxn;i++){
    node[i].XXX=0;
}

一般的题目都会给出一条静态链表的首节点的地址，因此我们可以依据这个地址来遍历得到整条链表。这一步同时也是对节点性质XXX进行标记，并且对有效节点的个数进行计数的时候，例如对节点是否在链表上这个性质来说，当我们遍历链表时，就可以把XXX置为1。

int p=begin,count=0;
while(p!=-1){//-1代表静态链表结束
    XXX=1;
    count++;
    p=node[p].next;
}

由于使用静态链表时时直接采用地址映射的方式，这就会使得数组小标的不连续。而很多时候题目给出的节点并不都是有效节点(即不在静态链表上的节点)。为了能够可控地访问有效节点，一般都需要对数组进行排序来把有效节点移动到数组的左端。这里我们用到上面所提及的XXX，这也就是为什么在XXX进行初始化时要取比正常取值要小的值。因为无效节点并不会执行XXX=1这一步，因此一定比有效节点的XXX小。于是在写sort函数的排序函数cmp时就可以在cmp的两个参数节点中有无效节点时按XXX从大到小排序，这样就能把有效节点全部移动到数组左端。当然，在cmp函数中还可以有第二级的排序，例如：题目可能要求把链表按节点顺序排序，此时就需要在cmp函数中建立第二级的排序：

bool cmp(Node a,Node b){
    if(a.XXX==-1||b.XXX==-1){//如果有节点是无效节点，就把它放到数组的后端
        return a.XXX>b.XXX;
    }else{//否则就按节点的数据域从大到小排序
        return a.data>b.data;
    }
}