顺序表的C++实现

1. 顺序表的声明

   typedef int ElemType;//便于代码复用
   typedef struct SqList {
       ElemType* data;//用指针来定义使顺序表可变
       int size;//顺序表的容量
       int length;//数据的数量
   }SqList;
   

2. 初始化顺序表

   bool InitList(SqList& L, int s) {//bool返回值用来判断初始化是否成功
       //s为开辟的容量，L为顺序表指针
       if (s <= 0)s = 10;//s<=0时，默认s=10，开辟容量为10的内存空间
       L.data = new ElemType[s];
       if (L.data == NULL)return false;//开辟失败返回false
       L.size = s;//顺序表的最大容量与开辟空间相同
       L.length = 0;//初始未存储数据时顺序表的长度为0
       return true;//返回true表示开辟成功
   }
   

3. 求顺序表的长度

   int ListLength(const SqList& L) {//使用'const'关键字，表示为常量
       return L.length;//L.length中记录了数据的数量即顺序表长度
   }
   

4. 按值查找

   int Locate(const SqList& L, const ElemType e) {//e为需要查找的值
       //遍历进行查找，找到返回位置，未找到返回-1
       for (int i = 0; i < L.length; i++)
       {
           if (L.data[i] == e)return i + 1;
       }
       return -1;
   }
   

5. 获得第i个元素

   bool GetData(const SqList& L, int i, ElemType& e) {
       if (i >= 1 && i <= L.length) {//判断i是否在有效的范围内,有效范围为1~L.length
           e = L.data[i-1];//顺序表的底层逻辑为数组，计数从0开始，对应关系如下表
           return true;
       }
       return false;
   }
   

   用户逻辑	1	2	3	4	5
   程序逻辑	0	1	2	3	4

6. 在第i个元素前插入一个元素

   bool InsList(SqList& L, int i, const ElemType e) {
       if (i<1 || i>L.length + 1)return false;//判断i是否在有效范围内
       if (L.length == L.size) {//当顺序表长度等于容量时，再进行插入时会导致内存溢出报错，因此重新开辟新的内存空间并将之前的数据拷贝到新的顺序表中
           ElemType* temp = new  ElemType[2 * L.size];//重新申请的内存空间相当于原空间的两倍
           if (temp == NULL)return false;
           for (int k = 0; k < L.length; k++)//将L.data中的数据拷贝到temp中
           {
               temp[k] = L.data[k];
           }
           delete[] L.data;//释放小的顺序表内存
           L.data = temp;//让L.data这个指针指向temp的内存空间
           L.size = L.size * 2;//与扩容操作相对应，容量将翻倍
       }
       for (int k = L.length-1; k >= i-1; k--)
       {
           L.data[k + 1] = L.data[k];
       }//将i之后的元素向后移动一个单位的位置
       L.data[i-1] = e;//在i的位置插入
       L.length += 1;//顺序表长度加1
       return true;//插入完场返回true
   }
   

7. 删除第个i元素

   bool DelList(SqList& L, int i, ElemType& e) {//e记录删除的元素
       if (i >= 1 && i <= L.length) {//判断i是否在有效范围内
           e = L.data[i - 1];//记录即将删除的元素
           for (int k = i - 1; k < L.length-1; k++) {//将i之后的元素向前移动一个单位的位置
               L.data[k] = L.data[k + 1];
           }
           L.length -= 1;//顺序表长度减1
           return true;//删除成功返回true
       }
       return false;//删除失败返回false
   }
   

8. 销毁顺序表

   void DestroyList(SqList& L) {//销毁顺序表只需要释放L.data所占据的内存空间
       delete [] L.data;//释放内存空间
       L.data = NULL;//将L.data指向NULL防止出现野指针，提高程序安全性
       L.size = 0;//顺序表容量置零
       L.length = 0;//顺序表长度置零
   }
   

9. 清空线性表

   void ClearList(SqList& L) {//清空顺序表只需要将顺序表的长度置零
       L.length = 0;
   }
   

10. 判断是否为空表

    bool EmptyList(const SqList& L) {//是否为空表取决于顺序表长度的值，当它为0时为空表，反之不为空表
        if (L.length == 0)return true;
        else return false;
    }
    

11. 遍历顺序表，输出表中的所有元素

void DispList(const SqList& L) {//打印全部数据
    for (int i = 0; i < L.length; i++)
    {
        cout << L.data[i] << " ";
    }
}

#include
using namespace std;
typedef int ElemType;//便于代码复用
typedef struct SqList {
    ElemType* data;
    int size;//顺序表的容量
    int length;//数据的数量
}SqList;
bool InitList(SqList& L, int s = 10);//初始化顺序表
int ListLength(const SqList& L);//求顺序表长度
int Locate(const SqList& L, const ElemType e);//按值查找
bool GetData(const SqList& L, int i, ElemType& e);//获得第i个元素
bool InsList(SqList& L, int i, const ElemType e);//在第i个元素前插入一个元素
bool DelList(SqList& L, int i,ElemType& e);//删除第i个元素
void DestroyList(SqList& L);//销毁顺序表
void ClearList(SqList& L);//清空顺序表
bool EmptyList(const SqList& L);//判断是否是空表
void DispList(const SqList& L);//遍历顺序表，即输出表中所有元素
int main(){
    SqList L;
    InitList(L, 10);
    for (int i = 0; i < 5; i++) {
        InsList(L, 1, i + 1);
    }
    DispList(L);
    ElemType a = -1;
    DelList(L, 2, a);
    cout << endl << a;
    return 0;
}
bool InitList(SqList& L, int s) {
    if (s <= 0)s = 10;
    L.data = new ElemType[s];
    if (L.data == NULL)return false;
    L.size = s;
    L.length = 0;
    return true;
}
int ListLength(const SqList& L) {
    return L.length;
}
int Locate(const SqList& L, const ElemType e) {
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)return i + 1;
    }
    return -1;
}
bool GetData(const SqList& L, int i, ElemType& e) {
    if (i >= 1 && i <= L.length) {
        e = L.data[i-1];
        return true;
    }
    return false;
}
bool InsList(SqList& L, int i, const ElemType e) {
    if (i<1 || i>L.length + 1)return false;
    if (L.length == L.size) {
        ElemType* temp = new  ElemType[2 * L.size];
        if (temp == NULL)return false;
        for (int k = 0; k < L.length; k++)
        {
            temp[k] = L.data[k];
        }
        delete[] L.data;
        L.data = temp;
        L.size = L.size * 2;
    }
    for (int k = L.length-1; k >= i-1; k--)
    {
        L.data[k + 1] = L.data[k];
    }
    L.data[i-1] = e;
    L.length += 1;
    return true;
}
bool DelList(SqList& L, int i, ElemType& e) {
    if (i >= 1 && i <= L.length) {
        e = L.data[i - 1];
        for (int k = i - 1; k < L.length-1; k++) {
            L.data[k] = L.data[k + 1];
        }
        L.length -= 1;
        return true;
    }
    return false;
}
void DestroyList(SqList& L) {
    delete [] L.data;
    L.data = NULL;
    L.size = 0;
    L.length = 0;
}
void ClearList(SqList& L) {
    L.length = 0;
}
bool EmptyList(const SqList& L) {
    if (L.length == 0)return true;
    else return false;
}
void DispList(const SqList& L) {
    for (int i = 0; i < L.length; i++)
    {
        cout << L.data[i] << " ";
    }
}