线性表

• 线性表(linear list)是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。线性表主要由顺序表示或链式表示。在实际应用常以栈、队列、字符串等特殊形式使用。
• 顺序表示:物理位置上相邻
• 链式表示:逻辑关系上相邻

顺序存储方式

const int maxn = 100;　　// 数组的最大长度
struct seq_list{
    ElemType data[maxn];
    int len;　　　       // 当前线性表的长度,应初始化为0
};
// 查取第i个元素 主要是注意表的状态以及参数的合法性
// 线性表非空 + 索引i 是第i个, 故而范围 [1, L.len]
bool get_elem(seq_list L, int i, ElemType *e) {
    if(i < 1 || i > L.len)
        return false;
    *e = L.data[i - 1];
    return true;
}

// 往第i个位置插入元素e
// 插入得: 线性表未满 + i ∈ [1, L.len + 1] 并且,若不是在尾巴后插入元素,元素需往前调整
bool insert_elem(seq_list& L, int i, ElemType e){
    if(L.len == maxn || i < 1 || i > L.len + 1)
        return false;
    if(i != L.len + 1){
        for(int j = L.len - 1; j >= i - 1; --j){
            L.data[j + 1] = L.data[j]; 
        }
    }

    L.data[i - 1] = e;
    ++L.len;
    return true;
}

// 删除第i个元素,同理,需:线性表非空 + i ∈ [1, L.len]
// 如果删除的并非最后一个元素,删除之后（这里可以不做真实的删除操作，直接覆盖并且控制Ｌ．len即可
// 删除之后需要调整，从第 i + 1个到第　Ｌ．len个元素，都往前挪一个位置　并且 --L.len
bool delete_elem(seq_list& L, int i, ElemType *e){
    if(L.len == 0 || i < 1 || i > L.len)  return false;
    *e = L.data[i - 1];
    if(i != L.len){
        for(int j = i; j < L.len; ++j){
            L.data[j - 1] = L.data[j];
        }
    }
    --L.len;
    return true;
}

带头结点的单链表

struct Node{
    int data;
    struct Node* next;
};
typedef Node* link_list;    //　头结点

// 其实增删改３个算法，　最关键的是明确范围，　和跳跃的次数
// 获取第i个元素，那么判断当前指针存在的同时，从L->next也就是第１个元素开始，跳 i -1 次即可
bool get_elem(link_list L, int i, int* e){
    Node* pcur = L->next;
    int j = 1;
    while(pcur && j < i){
        pcur = pcur->next;
        ++j;
    }
    if(!pcur || j > i) return false;
    // 如果跳了i - 1次的位置指针不存在或者　j > i 其实会有疑惑，为什么需要判断j > i ?
    // 毕竟有while的条件保证，j == i便一定跳出循环嘛．．但是这样会漏了一种情况
    // 如果别人给的参数i非正数呢？　这样并不会进入while循环...那直接写成 (!pcur || i <＝ 0)
    // 不也可以吗？　可以的．．我是为了和while循环的条件形成相反的关系好记忆而已
    *e = pcur->data;
    return true;
}

// 在第i个位置插入一个元素
// 留意，我的pcur和get_elem(...)不同，是从Ｌ开始的，插入，需要跳跃到第i - 1个结点
// 相当于跳跃i - 1次，然后只要第i - 1个结点存在，那么直接套路插入即可
// 这里是无所谓第ｉ个结点的情况的，即使第i个结点是null，插入算法也是可以兼容的，但是后面的delete不行

bool insert_elem(link_list L, int i, int e){
    Node* pcur = L;
    int j = 1;
    while(pcur && j < i){
        pcur = pcur->next;
        ++j;
    }           // 定位到第ｉ个元素的前一个元素
    if(!pcur || j > i)  return false;
    Node* p_new_node = new Node();
    p_new_node->data = e;
    p_new_node->next = pcur->next;
    pcur->next = p_new_node;
    return true;
}
/*
* 删除第i个元素，并且值放入e
* 和插入算法一样的地方是：删除需要先跳到第i - 1个结点，但是在判断这个删除算法是否有效的时候
* insert_elem是 if(!pcur || j > i)
* 而delete_elem　是if(!(pcur->next) || j > 1)　就是说，我要删除第i个结点，那么
* 第i - 1个结点的next，即第i 个结点必须得存在阿..
* 且要先判断 j > i，即是否能达到第i - 1个元素,否则 pcur->next会发生空引用
*/
bool delete_elem(link_list L, int i, int* e){
    Node* pcur = L;
    int j = 1;
    while(pcur && j < i){
        pcur = pcur->next;
        ++j;
    }
    if(j > i || !(pcur->next))  return false;

    Node* pi = pcur->next;
    pcur->next = pi->next;
    *e = pi->data;
    delete pi;
    return true;
}

// 单链表的整表删除，其实就是1.得到一个结点指针 2.保存该结点的next指针 3.才能删除该结点
void clear_list(link_list L){
    Node* p1, *p2;
    p1 = L->next;
    while(p1){
        p2 = p1->next;
        delete p1;
        p1= p2;
    }
    L->next = NULL;
}