1000_(1)顺序表

顺序表的基本操作实现

先言：深入掌握任何一种数据的存储结构前提都需要熟练掌握它基本操作的实现，算法题千变万化，唯一不变的就是底层的存储结构和算法的设计思想，好久不写手的确会生疏------------所有基础内容全部参考严蔚敏版教材实现
ps:由于c++代码更加清晰、简洁；并且大纲要求可以选用c/c++描述伪码，所以将课本中的c伪码改写为c++实现，但核心思想不变

顺序表的基本操作

• 顺序表需要一块连续的存储单元，类似数组也可以说用数组来实现顺序表，结构声明

typedef struct{
    ElementType *data; // 指针类型 指向一片连续的存储空间 
    int MaxSize, length; // 数组最大容量 长度 
} SeqList;

• 基本操作的定义

#define InitSize 100 // 表初始长度
using ElementType = int; // 存储元素类型 
void InitList(SeqList &L); // 构造一个空表
bool ListInsert(SeqList &L, int i, ElementType e); // 指定位置插入元素
bool ListDelete(SeqList &L, int i, ElementType &e); // 指定位置删除元素
int LocateElem(SeqList L, ElementType e); // 按值查找 -- 返回索引序
int Length(SeqList L); // 求表长
bool Empty(SeqList L); // 判空 

• 具体实现--需要注意的数组存储下标从0开始，自定义顺序表结构下标从1开始；相关操作注意下标的转换，详见代码及注释

/*
    初始化空表 
*/
void InitList(SeqList &L){
    // 分配连续内存空间 
    L.data = new ElementType[InitSize];
    L.length = 0;
    L.MaxSize = 100;    
}

/*
    时间复杂度O(n) 
    指定位置插入元素 需要注意的是
    位置从1开始 而数组下标从0开始 
*/
bool ListInsert(SeqList &L, int i, ElementType e){
    if(i < 1 || i > L.length + 1){ // 注意思考非法输入条件
        cout << "非法的插入位置" << endl; 
        return false; 
    }
    // 从最后一个节点 到插入位置元素后移
    for(int j = L.length; j >= i; j--){ // 因为真正数组的最后一个元素下标为L.length-1 
        L.data[j] = L.data[j-1];
    }
    
    L.data[i-1] = e;
    L.length++;
    
    return true;
}

void PrintList(SeqList L){
    if(L.length <= 0)
        return;
    for(int i = 0; i < L.length; i++){
        if(i == L.length-1){
            cout << L.data[i] << endl;
            return;
        }           
        cout << L.data[i] << "->";
    }
        
}

/*
    删除指定位置的元素 并且用e来接收
    注意元素位置 和 数组下标的转换 
*/
bool ListDelete(SeqList &L, int i, ElementType &e){
    if(i < 1 || i > L.length){
        return false;
    }
    
    // 从当前位置的下一个元素依次向前挪 O(n) 
    e = L.data[i-1];
    for(int j = i; j < L.length; j++){
        L.data[j-1] = L.data[j];
    }
    L.length--;
    return true;
}

/*
    顺序查找 -- 返回元素所在位序 
    加深对顺序表的理解 
*/
int LocateElem(SeqList L, ElementType e){
    int len = L.length;
    for(int i = 0; i < len; i++){
        if(L.data[i] == e)
            return i+1; // 位序与数组下标的转换 
    }
    return -1; // 没找到 
    
}

int Length(SeqList L){
    return L.length;
}

bool Empty(SeqList L){
    return L.length == 0 ? true : false;
}

小结：顺序表和链表是考研算法题考察的核心，彻底弄懂一个数据结构就是能快速准确的实现它的基本操作