王道数据结构练习题代码

本文记录王道数据结构每小节练习题中的代码

Ch2

2.2 线性表的顺序表示

No.1
问题：从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值，空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
解答：
算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。
本题代码如下：

bool Del_Min(SqList &L, ElemType &value) {
  //删除顺序表L中最小值元素结点，并通过引用型参数value返回其值
  //若删除成功，则返回true；否则返回false
  if(L.length == 0)
    return false;                               //表空，中止操作返回
  value = L.data[0];
  int pos = 0;                                  //假定0号元素的值最小
  for(int i = 1; i < L.length; i++)             //循环，寻找具有最小值的元素
    if(L.data[i] < value) {                     //让value记忆当前具有最小值的元素
      value = L.data[i];
      pos = i;
    }
  L.data[pos] = L.data[L.length-1];             //空出的位置由最后一个元素填补
  L.length--;
  return true;                                  //此时，value即为最小值
}

注意：本题也可用函数返回值返回，两者的区别是：函数返回值只能返回一个值，而参数返回（引用传参）可以返回多个值。
No.2
问题：设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)。
解答：
算法思想：扫描顺序表L的前半部分元素，对于元素L.data[i]（0 <= i < L.length/2），将其与后半部分的对应元素L.data[L.length-i-1]进行交换。
本题代码如下：

void Reverse(SqList &L) {
  ElemType temp;                    //辅助变量
  for(int i = 0; i < L.length/2; i++) {
    temp = L.data[i];               //交换L.data[i]与L.data[L.length-i-1]
    L.data[i] = L.data[L.length-i-1];
    L.data[L.length-i-1] = temp;
  }
}

No.3
问题：对长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。
解答：
解法一：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数），边扫描L边统计k，并将不等于x的元素向前移动k个位置，最后修改L的长度。
本题代码如下：

void del_x_1(SqList &L, ElemType x) {
  //本算法实现删除顺序表L中所有值为x的数据元素
  int k = 0;                          //记录值不等于x的元素个数
  for(int i = 0; i < L.length; i++)
    if(L.data[i] != x) {
      L.data[k] = L.data[i];
      k++;                            //不等于x的元素增1
    }
  L.length = k;                       //顺序表L的长度等于k
}

解法二：用k记录顺序表L中等于x的元素个数，边扫描L边统计k，并将不等于x的元素迁移k个位置，最后修改L的长度。
本题代码如下：

void del_x_2(SqList &L, ElemType x) {
  int k = 0, i = 0;                     //k记录值等于x的元素个数
  while(i < L.length) {
    if(L.data[i] == x)
      k++;
    else
      L.data[i-k] = L.data[i];          //当前元素前移k个位置
    i++;
  }
  L.length = L.length - k;              //顺序表L的长度递减
}

此外，本题还可以考虑设头、尾两个指针（i = 1, j = n），从两端向中间移动，在遇到最左端值x的元素时，直接将最右端值非x的元素左移至值为x的数据元素位置，直到两指针相遇。但这种方法会改变原表中元素的相对位置。
No.4
问题：从顺序表中删除其值在给定值s与t之间（包含s和t，要求s < t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
解答：
算法思想：从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数（初始时k=0）。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则执行k++。由于这样每个不在s到t之间的元素仅移动一次，因此算法效率高。
本题代码如下：

bool Del_s_t(SqList &L, ElemType s, ElemType t) {
  //删除顺序表L中值在给定值s与t（要求s < t）之间的所有元素
  int i, k = 0;
  if(L.length == 0 || s >= t)
    return false;                       //线性表为空或s、t不合法，返回
  for(i = 0; i < L.length; i++) {
    if(L.data[i] >= s && L.data[i] <= t)
      k++;
    else
      L.data[i-k] = L.data[i];          //当前元素前移k个位置
  }   //for
  L.length -= k;                        //长度减小
  return true;  
}

注意：本题也可从后向前扫描顺序表，每遇到一个值在s到t之间的元素，则删除该元素，其后的所有元素全部前移。但移动次数远大于前者，效率不够高。
No.5
问题：从有序顺序表中删除其值在给定值s与t之间（要求s < t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
解答：
注意：本题与上一题存在区别。因为是有序表，所以删除的元素必然是相连的整体。
算法思想：先寻找值大于等于s的第一个元素（第一个删除的元素），然后寻找值大于t的第一个元素（最后一个删除的元素的下一个元素），要将这段元素删除，只需直接将后面的元素前移。
本题代码如下：

bool Del_s_t2(SqList &L, ElemType s, ElemType t) {
  //删除有序顺序表L中值在给定值s与t之间的所有元素
  int i, j;
  if(s >= t || L.length == 0)
    return false;
  for(i = 0; i < L.length && L.data[i] < s; i++);     //寻找值大于等于s的第一个元素
  if(i >= L.length)
    return false;                                     //所有元素值均小于s，返回
  for(j = i; j < L.length && L.data[j] <= t; j++);    //寻找值大于t的第一个元素
  for(; j < L.length; i++, j++)                       //前移，填补被删元素位置
    L.data[i] = L.data[j];
  L.length = i;
  return true;
}

No.6
问题：从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。
解答：
算法思想：注意是有序顺序表，值相同的元素一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，若相同，则继续向后判断，若不同，则插入前面的非重复有序表的最后，直至判断到表尾为止。
本题代码如下：

bool Delete_Same(SqList &L) {
  if(L.length == 0)
    return false;
  int i, j;                               //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;
}

No.7
问题：将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。
解答：
算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。
本题代码如下：

bool Merge(SqList A, SqList B, SqList &C) {
  //将有序顺序表A和B合并为一个新的有序顺序表C
  if(A.length + B.length > C.MaxSize)         //大于顺序表的最大长度
    return false;
  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;
}

No.8
问题：已知在一维数组A[m+n]中依次存放两个线性表（a₁,a₂,a₃,…,a_m）和（b₁,b₂,b₃,…,b_n）。试编写一个函数，将数组中两个顺序表的位置互换，即将（b₁,b₂,b₃,…,b_n）放在（a₁,a₂,a₃,…,a_m）的前面。
解答：
算法思想：先将数组A[m+n]中的全部元素（a₁,a₂,a₃,…,a_m,b₁,b₂,b₃,…,b_n）原地逆置为（b_n,b_n-1,b_n-2,…,b₁,a_m,a_m-1,a_m-2,…,a₁），再对前n个元素和后m个元素分别使用逆置算法，即可得到（b₁,b₂,b₃,…,b_n,a₁,a₂,a₃,…,a_m），从而实现顺序表的位置互换。
本题代码如下：

typedef int DataType;
void Reverse(DataType A[], int left, int right, int arraySize) {
  //逆转(aleft, aleft+1, aleft+2,..., aright)为(aright, aright-1,..., aleft)
  if(left >= right || right >= arraySize)
    return;
  int mid = (left + right) / 2;
  for(int i = 0; i <= mid - left; i++) {
    DataType temp = A[left+i];
    A[left+i] = A[right-i];
    A[right-i] = temp;
  }
}
void Exchange(DataType A[], int m, int n, int arraySize) {
  /*数组A[m+n]中，从0到m-1存放顺序表(a1,a2,a3,...,am)，从m到m+n-1存放顺序表(b1,b2,b3,...,bn)，算法将这两个表的位置互换*/
  Reverse(A, 0, m+n-1, arraySize);
  Reverse(A, 0, n-1, arraySize);
  Reverse(A, n, m+n-1, arraySize);
}

No.9
问题：线性表（a₁,a₂,a₃,…,a_n）中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将其插入表中并使表中元素仍递增有序。
解答：
算法思想：顺序存储的线性表递增有序，可以顺序查找，也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找法。
本题代码如下：

void SearchExchangeInsert(ElemType A[], ElemType x) {
  int low = 0, high = n-1, mid;               //low和high指向顺序表下界和上界的下标
  while(low <= high) {
    mid = (low + high) / 2;                   //找中间位置
    if(A[mid] == x) break;                    //找到x，退出while循环
    else if(A[mix] < x) low = mid + 1;        //到中点mid的右半部去查
    else high = mid - 1;                      //到中点mid的左半部去查
  }             //下面两个if语句只会执行一个
  if(A[mid] == x && mid != n-1) {     //若最后一个元素与x相等，则不存在与其后继交换的操作
    t = A[mid];
    A[mid] = A[mid+1];
    A[mid+1] = t;
  }
  if(low > high) {                              //查找失败，插入数据元素x
    for(i = n-1; i > high; i--) A[i+1] = A[i];  //后移元素
    A[i+1] = x;                                 //插入x
  }                                             //结束插入
}

本题的算法也可写成三个函数：查找函数、交换后继函数与插入函数。写成三个函数的优点是逻辑清晰、易读。
No.10
问题：设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0 < p < n)个位置，即将R中的数据由(X₀,X₁,…,X_n-1)变换为(X_p,X_p+1,…,X_n-1,X₀,X₁,…,X_p-1)。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
解答：
1）算法的基本设计思想：可将这个问题视为把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a^-1b，再将b逆置得到a^-1b^-1，最后将整个a^-1b^-1逆置得到(a^-1b^-1)^-1 = ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：
Reverse(0, p-1)得到cbadefgh；
Reverse(p, n-1)得到cbahgfed；
Reverse(0, n-1)得到defghabc；
注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。
2）使用C语言描述算法如下：

void Reverse(int R[], int from, int to) {
  int i, temp;
  for(i = 0; i < (to-from+1)/2; i++) {
    temp = R[from+i];
    R[from+i] = R[to-i];
    R[to-i] = temp;
  }
} //Reverse
void Converse(int R[], int n, int p) {
  Reverse(R, 0, p-1);
  Reverse(R, p, n-1);
  Reverse(R, 0, n-1);
}

3）上述算法中三个Reverse函数的时间复杂度分别为O(p/2)、O((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。

另解，借助辅助数组来实现。算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。时间复杂度为O(n)，空间复杂度为O(p)。

No.11
问题：一个长度为L(L >= 1)的升序序列S，处在第 L/2(向上取整) 个位置的数称为S的中位数。例如，若序列S₁ = (11, 13, 15, 17, 19)，则S₁的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S₂ = (2, 4, 6, 8, 20)，则S₁和S₂的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。
解答：
1）算法的基本设计思想如下。
分别求两个升序序列A、B的中位数，设为a和b，求序列A、B的中位数过程如下：

若a = b，则a或b即为所求中位数，算法结束。
若a < b，则舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求两次舍弃的长度相等。
若a > b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求两次舍弃的长度相等。
在保留的两个升序序列中，重复过程1.、2.、3.，直到两个序列中均只含一个元素为止，较小者即为所求的中位数。

No.12
问题：已知一个整数序列A = (a₀,a₁,…,a_n-1)，其中 0 <= a_i < n (0 <= i < n)。若存在a_p1 = a_p2 = … = a_pm = x 且 m > n/2 (0 <= p_k < n , 1 <= k <= m)，则称x为A的主元素。例如A = (0,5,5,3,5,7,5,5)，则5为主元素；又如A = (0,5,5,3,5,1,5,7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

No.13
问题：给定一个含n(n >= 1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5, 3, 2, 3}中未出现的最小整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。

No.14
问题：定义三元组(a, b, c)（a、b、c均为正数）的距离D = |a-b| + |b-c| + |c-a|。给定3个非空整数集合S₁、S₂和S₃，按升序分别存储在3个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组(a, b, c) （a属于S₁，b属于S₂，c属于S₃）中的最小距离。例如S₁ = {-1, 0, 9}，S₂ = {-25, -10, 10, 11}， S₃ = {2, 9, 17, 30, 41}，则最小距离为2，相应的三元组为(9, 10, 9)。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C语言或C++语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度和空间复杂度。