美文网首页
1000_(1)顺序表

1000_(1)顺序表

作者: 掌灬纹 | 来源:发表于2020-04-10 07:17 被阅读0次

顺序表的基本操作实现

先言:深入掌握任何一种数据的存储结构前提都需要熟练掌握它基本操作的实现,算法题千变万化,唯一不变的就是底层的存储结构算法的设计思想,好久不写手的确会生疏------------所有基础内容全部参考严蔚敏版教材实现
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;
}

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

相关文章

  • 1000_(1)顺序表

    顺序表的基本操作实现 先言:深入掌握任何一种数据的存储结构前提都需要熟练掌握它基本操作的实现,算法题千变万化,唯一...

  • 数据结构之线性表

    1、线性表-顺序表线性表-顺序表

  • 数据结构导论算法总结

    一、线性表顺序存储 1、顺序表的插入运算* 顺序表的插入运算 InsertSeqlist (SeqList L,D...

  • 顺序头文件

    顺序头文件 //c2-1.h线性表的动态分配顺序存储结构 顺序表基本方法 //bo2-1.cpp顺序表示的线性表的...

  • 数据结构与算法(二,线性表的顺序存储结构,穷举法(冒泡和选择排序

    线性表 顺序表 顺序表的特性 顺序表的元素有前驱和后继 顺序表有size 顺序表的增删改查 顺序表的优缺点优点:尾...

  • 2018-10-11

    0.实现顺序索引表的分块查找 实现顺序表的分级查找算法。基本要求包括: (1)设计顺序表和索引表的存储结构。 (2...

  • MySQL的语句

    语法顺序 执行顺序 FORM: 对FROM的左边的表和右边的表计算笛卡尔积。产生虚表VT1 ON: 对虚表VT1进...

  • 顺序表-动态顺序表

    顺序表是逻辑上相邻的元素物理也相邻的。 静态内存是指在程序开始运行时由编译器分配的内存,它的分配是在程序开始编译时...

  • 顺序表-静态顺序表

    线性表,全名为线性存储结构。将具有“一对一”关系的数据“线性”地存储到物理空间中,这种存储结构就称为线性存储结构(...

  • C语言实现常用数据结构:顺序表(第2篇)

    顺序表 顺序表使用一组连续的物理内存存储地址按照次序存放线性表的元素。 实现要点: 1.顺序表的长度可变。 2.利...

网友评论

      本文标题:1000_(1)顺序表

      本文链接:https://www.haomeiwen.com/subject/jwxlmhtx.html