专业编程基础技术教程

网站首页 > 基础教程 正文

数据结构——顺序表操作

ccvgpt 2024-09-11 02:31:59 基础教程 137 ℃

顺序表初始化

顺序表结构体中length是表的长度，是顺序表的一个属性，所以可以通过返回length的值，实现求表长的操作。通过判断length的值是否为0来判断表是否为空，这些操作算法的时间复杂度都是O(1)。顺序表的初始化操作就是构造一个空的顺序表。

【算法步骤】

数据结构——顺序表操作

  • 为顺序表List分配固定大小的数组空间。
  • 顺序表的当前长度设为0。

【代码描述】

Status InitSqList(SqList& List)
{
  for (int i = 0; i < MAX_SIZE; ++i)
  {
    List.data[i] = 0;
  }
  List.length = 0;
  return OK;
}

获取元素操作

获取顺序表中的元素是根据指定的位置序号i，获取顺序表中第i个数据元素的值。由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到，也就是将第i-1下标的值返回即可。

【算法步骤】

  • 判断指定的位置序号i值是否合理 ()，若不合理，返回ERROR。
  • 若i在范围内，则将第i个元素data[i-1]赋给参数elem，通过elem返回第i个数据元素的传值。

【代码描述】

Status GetElem(const SqList List, int i, ElemType& elem)
{
  if (i < 1 || i > List.length)
  {
    std::cout << "输入位置错误" << std::endl;
    return ERROR;
  }
  elem = List.data[i - 1];
  return OK;
}

顺序表元素的查找

查找操作是根据指定的元素值elem，查找顺序表中与elem相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。

【算法步骤】

  • 从第一个元素起，依次和elem相比较，若找到与elem相等的元素data[i]，则返回序号i+1。
  • 若遍历整个顺序表没有找到，则查找失败，返回ERROR。

【代码描述】

Status LocateElem(const SqList List, ElemType elem)
{
  for (int i = 0; i < List.length; ++i)
  {
    if (List.data[i] == elem) //查找成功，返回序号i + 1
    {
      return i + 1;
    }
  }
  return ERROR;	//查找失败，返回ERROR
}

【算法分析】

  • 最好情况：查找的元素在表头，仅需比较一次，时间复杂度为O(1)。
  • 最坏情况：查找元素在表尾或不存在，需要比较n次，时间复杂度为O(n)。
  • 平均情况：在和给定值进行比较的数据元素个数的期望值，称为查找算法在查找成功时的平均查找长度（Average Search Length, ASL）。假设是查找第i个元素的概率，则在长度n的顺序表中查找elem元素所需比较的平均次数为：

由此可见，顺序表按值查找算法的平均时间复杂度为O(n)。

顺序表插入元素

顺序表的插入操作是指在表的第i个位置插入一个新的元素elem，使长度为n的顺序表变成长度为n+1的顺序表。如图所示，一个顺序表在插入前后，数据元素在存储空间中的位置变化。为了在顺序表的第5个位置插入一个为25的元素，则需将第5个至第8个元素依次向后移动一个位置。

【算法步骤】

  • 判断指定的位置序号i值是否合理 ()，若不合理，返回ERROR。
  • 判断顺序表的存储空间是否已满，若已满则返回ERROR。
  • 将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置。如果是在表尾插入，则无需移动。
  • 将要插入的新元素elem放到第i个位置。
  • 顺序表长度加1。

【代码表述】

Status InsertElem(SqList& List, int i, ElemType elem)
{
  if (List.length == MAX_SIZE) /*顺序线性表已满*/
  {
    std::cout << "顺序线性表已满" << std::endl;
    return ERROR;
  }
  
  if (i < 1 || i  > List.length + 1) /*当i不在范围内时*/
  {
    std::cout << "输入位置错误" << std::endl;
    return ERROR;
  }

  if (i <= List.length) /*若插入数据不在表尾*/
  {
    for (int k = List.length - 1; k >= i - 1; --k) /*将要插入位置后的数据元素向后移动一位*/
    {
      List.data[k + 1] = List.data[k];
    }
  }
  List.data[i - 1] = elem;/*将新元素插入*/
  List.length++;
  return OK;
}

【算法分析】

  • 最好情况：在表尾插入，元素后移动语句将不执行，时间复杂度为O(1)。
  • 最坏情况: 在表头插入，元素后移动语句执行n次，时间复杂度为O(n)。
  • 平均情况: 假设是在第i个元素之前插入一个元素的概率，顺序表的任何位置上插入元素都是等概率的。 是在长度为n的顺序表中插入一个元素时移动元素次数的期望值（平均数），则：

由此可见，顺序表插入算法的平均时间复杂度为O(n)。

顺序表删除元素

顺序表的删除操作是指将表的第i个元素删除，将长度为n的顺序表变成长度为n-1的顺序表。

数据元素ai-1、ai和ai+1之间的逻辑关系发生了变化，同样需要移动元素。如图所示，为了删除第4个数据元素，必须将第5个至第8个元素都依次向前移动一个位置。


一般情况下，删除第i个元素时需将第i+1个至第n个元素(共n-i个元素)依次向前移动一个位置(i=n时无需移动)。

【算法步骤】

  • 判断指定的位置序号i值是否合理 ()，若不合理，返回ERROR。
  • 判断顺序表的存储空间是否已满，若满则返回ERROR。
  • 将第i+1个至第n个位置的元素依次向前移动一个位置(i=n时无需移动)。
  • 顺序表长减1。

【代码表述】

Status DeleteElem(SqList& List, int i)
{
  if (i < 1 || i > List.length)
  {
    std::cout << "输入位置错误" << std::endl;
    return ERROR;
  }

  for (int k = i - 1; k < List.length - 1; ++k) /*被删除元素之后的元素前移一位*/
  {
    List.data[k] = List.data[k + 1];
  }
  List.length--;
  return OK;
}

【算法分析】

  • 最好情况：删除表尾元素（），无需移动元素，时间复杂度为O(1)。
  • 最坏情况: 删除表头元素()，需要移动头元素外的所有元素，时间复杂度为O(n)。
  • 平均情况: 假设是删除第i个元素的概率。是在长度为n的顺序表中删除一个元素时移动元素次数的期望值（平均数），则：

由此可见，顺序表删除算法的平均时间复杂度为O(n)。

总结

顺序表可以随机存取表中任一元素，其存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。另外由于数组有长度相对固定的静态特性， 当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然会导致存储空间的浪费。所有这些问题，都可以通过线性表的另一种表示方法——链式存储结构来解决。

完整代码

Github：https://github.com/MrYuxiangZhu/DataStructure/tree/master/01.%20LinkedList

Tags：

猜你喜欢

最近发表
标签列表