数据结构-顺序表的相关算法实现

题目1：删除最小值

题目：

从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

具体实现

// 删除顺序表中最小值的元素
bool SqListDeleteMinimun(SqList *L,ElemType *e)
{
  //判断顺序表是否为空
  if (L->length == 0)
  {
    return false;
  }
  // 用于存放最小值
  ElemType minValue = *(L->data + 0);
  // 用于存放最小值的索引
  int index = 0;
  for (size_t i = 0; i < L->length - 1; i++)
  {
    if(*(L->data + i) > *(L->data + i + 1)){
        minValue = *(L->data + i + 1);
        index = i+1;
    }
  }
  //将删除的元素由最后一个元素填补
  *(L->data + index) = *(L->data + (L->length -1)); 
  //返回删除的值
  *e = minValue;
  return true;
}

上方是通过for循环实现，时间复杂度为O(n)。

题目2：逆置顺序表

题目：

设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。

// 逆置顺序表
void SqListReverse(SqList *L)
{
  int left = 0;
  int right = L->length - 1;
  while (left < right)
  {
    //将元素进行交换
    ElemType tmp = L->data[left];
    L->data[left] = L->data[right];
    L->data[right] = tmp;
    left++;
    right--;
  }
}

中间元素交换部分也可以采用异或的方式来实现，当然循环部分也可以使用for(int i = 0; i< L->length / 2; i++)来通过进行前一半元素和后一半元素的交换来实现。

while (left < right)
  {
    //当两个值不相同时交换位置
    if (L->data[left]!=L->data[right])
    {
      L->data[left] = (L->data[left]) ^ (L->data[right]);
      L->data[right] = (L->data[left]) ^ (L->data[right]);
      L->data[left] = (L->data[left]) ^ (L->data[right]);
    }
    left++;
    right--;
  }

异或实现原理：

//注释表示二进制形式 异或是同位相同则为0 不相同则为1
int a = 4; //4的二进制形式为    00000000 00000000 00000000 00000100
int b = 5; //5的二进制形式为    00000000 00000000 00000000 00000101
​
a = a^b; //通过异或运算后此时a为 00000000 00000000 00000000 00000001 
b = a^b; //通过异或运算后此时b为 00000000 00000000 00000000 00000100  这里的b是和已经异或过的a重新再一次进行异或运算
a = a^b; //通过异或运算后此时a为 00000000 00000000 00000000 00000101

经过异或运算就将二进制位进行了交换从而实现元素交换。

题目3：删除顺序表中值为x的数据元素

题目：

对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

//这题用的王道书的解法
void SqListDeleteX(SqList *L,ElemType x){
    int i = 0;
    //计算不为x的元素
    int k = 0;
    for(i = 0; i < L->length ; i++)
    {
        //查询表中所有不为x的元素，并将这些元素重新排放
        if(L->data[i] != x){
            L->data[k] = L->data[i];
            k++;
        }
    }
    L->length = k;//将长度改为不包含的x元素的k，之后的元素就无法通过顺序表查询到，就达到了删除的效果
}

题目4：删除指定区间内的元素

题目：

从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。

// 删除指定区间的元素
bool SqListDeleteDomain(SqList *L, ElemType s, ElemType t)
{
  // 用来存储s的索引值
  int sIndex = -1;
  // 用来存储t的索引值
  int tIndex = -1;
  // 判断行为是否合法
  if (s >= t || L->length == 0)
  {
    return false;
  }
​
  for (size_t i = 0; i < L->length; i++)
  {
    // 若值为s则将索引值赋值给sIndex
    if (L->data[i] == s)
    {
      sIndex = i;
    }
    // 若值为t则将索引值赋值给tIndex
    else if (L->data[i] == t)
    {
      tIndex = i;
    }
    // 若s和t的索引值都已找到就提前结束循环
    if (sIndex >= 0 && tIndex > 0)
    {
      break;
    }
  }
​
  // 走这条说明s或t没有在顺序表中找到
  if (!sIndex && !tIndex)
  {
    return false;
  }
​
  // t若为最后一个元素则直接减少长度
  if (L->data[tIndex] == L->data[L->length - 1])
  {
    L->length -= tIndex - sIndex;
    return true;
  }
  // 临时存储s的索引值
  int tmp = sIndex;
​
  // 将t往后的数据前移
  for (size_t i = tIndex; i < L->length; i++)
  {
    L->data[tmp] = L->data[i + 1];
    tmp++;
  }
  L->length = L->length - (tIndex - sIndex + 1);
  return true;
}