《数据结构》期末提纲之顺序表

1.顺序表简介

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。（百度百科）

2.顺序表的基本操作

• 插入值
  在进行插值操作时，插入位置的后端元素需要整体后移一位，再进行插入，如图所示：
  
• 删除值
  进行删除值操作时，从被删除元素下一位开始，依次前移，如图所示：
  
• 遍历
  顺序表时基于数组的，直接使用for循环对数据域进行遍历即可，不赘述。

顺序表几乎所有操作都是与插入，删除，遍历相关的。

3.顺序表的C++实现

• 类型构造

template <class DataType>
class SeqList //顺序表类
{
   
public:
    SeqList(); //无参数构造
    SeqList(DataType a[],int n); //将数组转化构造
    ~SeqList(); //析构
    int length(); //返回长度
    DataType get(int i); //按位查值
    int locate(DataType x); //按值查位
    void insert(int i,DataType x); //插值
    void del_loc(int i); //按位删值
    void del_data(DataType x); //按值删值
    void clear(); //清空
protected: //使用protected方便栈与队列类继承
    DataType *data; //数据域
    int len; //长度
};

• 构造与析构

template <class DataType>
SeqList<DataType>::SeqList() //无参数构造
{
   
    cout << "SeqList Constructed!" << endl;
    len