顺序表的操作

这里先定义个顺序表

#include <iostream>

using namespace std;

#define MAXSIZE 100

typedef struct{
  int *elems;
  int length;
  int size;
}Sqlist;

Sqlist list;

顺序表初始化

• 定义bool类型函数 initList() ，初始化成功为true，失败为false

//初始化顺序表，创建一个空表
bool initList(Sqlist &L)    //L本身要改变所以为引用型
{
    L.elems = new int[MAXSIZE]; //为顺序表分配内存空间
    if(!L.elems) return false;  //存储分配失败返回false
  
    //分配成功则初始化
    L.length = 0;
    L.size = MAXSIZE;
    return true;                //成功并返回true
}

• 定义函数 outputInfoList() 用于输出顺序表信息

//输出数据表信息
void outputInfoList(Sqlist &L)
{
    cout << "顺序表储存空间" << L.size << ",已经保存元素个数" << L.length << endl;
    for(int i = 0; i <= L.length - 1;i++){
        cout << L.elems[i] << " ";
    }
    cout << endl;
}

找查元素

• 定义函数 findElem() 在顺序表中找查一个等于e的元素

/*
* 用于找查顺序表中的元素
* 参数e为要找查的元素
* 若找到则返回元素下标
* 若没找到则返回-1
*/
int findElem(Sqlist L, int e)        //这里我们不改变L，所以不用引用类型
{
  for(int i = 0; i < L.length; i++){
    if(e == L.elems[i])
      return i;                                    //若找到则返回元素下标
  }
  return -1;                                        //若没找到则返回-1
}

插入元素

尾部添加元素

在尾部添加元素要考虑以下几点

• 顺序表是否已满
• 添加成功后长度要加1
• 故定义函数 listAppend()

/*
* 在顺序表尾部插入元素
* 参数e为要插入到尾部的元素
* 若成功则返回true，失败（顺序表已经满了）则返回false
*/
bool listAppend(Sqlist &L, int e)
{
    if(L.length == L.size)
        //顺序表满了
        return false;
  //没满则尾部插入元素并返回true
    L.elems[L.length] = e;
    L.length++;
    return true;
}

在特定位置插入元素

在特定位置插入要考虑以下几点

• 顺序表是否已满
• 添加成功后长度要加1
• 要移动后面的元素而不能移动前面的元素，否则后面的元素会被前面的覆盖

定义如下

//在顺序表p位置（0 <= p <= length）上插入元素e
bool insertElem(Sqlist &L, int p, int e)
{
  if(p < 0 || p > L.length || L.length == MAXSIZE)
    /*
    * 如果位置错误
    * 或者表长已经达到最大允许值
    * 此时插入不成功并返回false
    */
    return false;
  for(int i = L.length - 1; i >= p; --i)
    //从后往前将元素相后方移动一个位置
    L.elems[i+1] = L.elems[i];
  L.elems[p] = e;    //插入元素e到p位置
  L.length++;
  
  return true;        //成功返回true  
}

删除元素

删除元素要考虑以下几点

• 顺序表位置是否正确
• 成功后长度要减去1
• 后方元素向前移动一个位置

//删除p位置的元素
bool delElem(Sqlist &L, int p, int &e)
{
  //位置错误返回false
  if(p < 0 || p > L.length - 1) return false;
  e = L.elems[p];    //将被删除的元素赋值给e
  for(int i = p; i < L.length - 1; i++)
  {
    //从p开始后方元素向前移动一个位置
    L.elems[i] = L.elems[i+1];
  }
  
  L.length--;        //长度减去1
  return true;    //成功返回true
  
}

顺序表的销毁

• 在初始化函数中，用了new来分配内存，所以在销毁时要释放内存

void destroy(Sqlist &L)
{
  //内存存在则释放内存
  if(L.elems) delete []L.elems;
  L.length = 0;
  L.size = 0;
}