$\color{#A96648}{顺序表Sqlist}$

#include <iostream>
using namespace std;
#define maxsize 100
typedef struct
{
  int data[maxsize];
  int length;
} Sqlist;

/*01.给定一个递增有序的顺序表，插入元素x，依然保证有序
    找到该元素的位置，执行插入基本操作。*/
int Find(Sqlist L, int x)
{
  int i = 0;
  for (; i < L.length; ++i)
  {
    if (x < L.data[i])
      break;
  }
  return i;
}

void Insert(Sqlist &L, int x)
{
  int j, p;
  p = find(L, x);
  for (j = L.length - 1; j >= p; --j)
    L.data[j + 1] = L.data[j];
  L.data[p] = x;
  (L.length)++; //别遗漏
}

/*02.用顺序表最后一个元素覆盖整个顺序表中最小元素，并返回该最小元素
    遍历去找到最小的元素。用pos记录位置，该题意思用最后一个元素去覆盖，len--*/
int Del_Min(Sqlist &L)
{
  int min = L.data[0];
  int pos = 0;
  for (int i = 0; i < L.length; ++i)
    if (L.data[i] < min)
    {
      min = L.data[i];
      pos = i;
    }
  L.data[pos] = L.data[L.length - 1];
  L.length--;
  return min;
}

/*03.将顺序表中的元素逆置
    重要！0和len-1调换，i++，j-- 直到i<=len/2*/
void Swap(int &a,int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
void Reverse(Sqlist &L)
{
    int i = 0;
    int j = L.length-1;
    for (;i <= L.length / 2; i++,j--)
    {
        swap(L.data[i],L.data[j]);
    }
}

/*04.将（a1,a2,a3……am,b1,b2,……bn）转换成( b1,b2,……bn,a1,a2,a3,……am )
    只需a1-am 反转一次，b1-bn反转一次。整体在反转一次。
    change(A,0,m-1);
    change(A,m,m+n-1);
    change(A,0,m+n-1);
    */

void change(int A[],int m,int n)
{
    int mid = (m + n) / 2;
    for (int i = m, int j = n; i <= mid / 2; i++ ,j--)
    {
        Swap(A[i],A[n]);
    }
}

/*05.删除顺序表中所有值为 x 的元素(两种方法)
    法一，删去为x的元素，等价于保留不为x的元素
    */

void Del1(Sqlist &L,int x)
{
    int k = 0;
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] != x)
        {
            L.data[k] = L.data[i]
            k++;
        }
    }
    L.length = k;
}

void Del2(Sqlist &L, int x)
{
  int k = 0;
  for (int i = 0; i < L.length; ++i)
  {
    if (L.data[i] == x)
      k++; //在i之前已经有多少个x的个数
    else
      L.data[i - k] = L.data[i]; //前面删了k个x，赋值的时候前进k位
  }
  L.length = L.length - k;
} 

/*06.从顺序表中删除给定值在 s 到 t 之间（包含 s 和 t）的所有元素
    思想同05题*/

void Del1(Sqlist &L,int s,int t)
{
  if (L.length == 0 || s >= t)
    return false;
    int k = 0;
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] < s || L.data[i] > t)
        {
            L.data[k] = L.data[i]
            k++;
        }
    }
    L.length = k;
}

/*07.从有序表中删除所有值重复的元素---依旧是覆盖*/
bool del(Sqlist &L)
{
  int i, j;
  for (i = 0, j = 1; j < L.length; ++j)
    if (L.data[i] != L.data[j])
      L.data[++i] = L.data[j];
  L.length = i + 1;
  return true;
}

/*08.两个递增有序表合并成一个递增有序表*/
bool merge(Sqlist A, Sqlist B, Sqlist &C)
{
  int i = 0, j = 0, k = 0;
  while (i < A.length && j < B.length)
  {
    if (A.data[i] < B.data[j])
      C.data[k++] = A.data[i++];
    else
      C.data[k++] = B.data[j++];
  }
  //接着写把长的没遍历完的后面全放进去
  while (i < A.length)
    C.data[k++] = A.data[i++];
  while (j < B.length)
    C.data[k++] = B.data[j++];
  C.length = k;
  return true;
}

*/09.求两个递增序列合并后的中位数(两种方法) 用法一 法二不写了图一乐。同08*/
int Find(Sqlist &A, Sqlist &B)
{
  int i, j, k;
  i = j = k = 0;
  Sqlist C;
  while (i < A.length && j < B.length)
    if (A.data[i] < B.data[j])
      C.data[k++] = A.data[i++];
    else
      C.data[k++] = B.data[j++];
  while (i < A.length)
    C.data[k++] = A.data[i++];
  while (j < B.length)
    C.data[k++] = B.data[j++];
  return C.data[(A.length + B.length - 1) / 2];
} //减去1是因为奇数偶数的问题。3+3/2 3+4-1/2

*/10.设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数
    思想 通过另一个等长的数组，通过B的数组下标 记录保存A[i]是否出现*/

// B中的置1的位置 表明了改位置B[i]=1,i+1在A中存在i+1 这个元素。
int find(int A[], int n)
{
  int i;
  int *B = new int[n];
  for (int k = 0; k < n; ++k)
    B[k] = 0;
  for (i = 0; i < n; ++i)
    if (A[i] > 0 && A[i] <= n) //细节大于n！大于数组长度的元素都没有必要放进去，
      B[A[i] - 1] = 1;
  for (i = 0; i < n; ++i)
    if (B[i] == 0)
      break;
  delete[] B;
  return i + 1;
}

/*11.若一个整数序列中有过半相同元素，则称其为主元素，设计算法找出数组A( a0,a1……an-1 )的主元素。
（其中 0<ai<n）若存在主元素则输出，否则返回-1
思想同10！*/
int find(int A[], int n)
{
  int i;
  int *B = new int[n];
  for (int k = 0; k < n; ++k)
    B[k] = 0;
  for (i = 0; i < n; ++i)
    if (A[i] > 0 && A[i] <= n) 
      B[A[i] - 1]++;
  for (i = 0; i < n; ++i)
    if (B[i] > n / 2)
    (
        delete[] B;
        return i + 1;
    )
  return -1;  
}