2021年3月18日-3月21日学习笔记

数据结构与算法线性表

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;
  for(i=0;i<L.length;i++)
    if(L.data[i]<value){
      value=L.data[i];
      pos=i
    }
  L.data[pos]=L.data[L.length-1];
  L.length--;
  return true;
}
           

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

void Reverse(Sqlist &L){
  Elemtype temp;    //辅助变量
  for(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;
  }
}
           

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

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

//解法二
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的长度递减
}
           

4.从有序顺序表中删除其值在定值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++);
  if(i>L.length)
    return false;
  for(j=i;j<L.length&&L.data[j]<=t;j++);
  for(;j<L.length;i++,j++)
    L.data[i]=L.data[j];
  L.length=i;
  return true;
}

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++);
  if(i>L.length)
     return false;
  for(j=i;j<=L.length&&L.data[j]<=t;j++);
  for(;j<L.length;i++,j++)
    L.data[i]=L.data[j];
  L.length=i;
  return true
}
           

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

bool Del_s_t(Sqlist &L,ElemType s,ElemType t){
   //删除有序顺序表L中值在给定值s与t之间的所有元素
  int i,k=0;
  if(L.length==0||s>=t)
    return false;
  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];
  }
  L.length-=k
  return true
}
           

6.从有序顺序表中删除所有其值重复的元素，使表中的元素均不同。

bool Delete_Same(SeqList &L){
  if(L.length==0)
    return false;
  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;
}
           

7.将两个有序顺序表合并为一个新的有序顺序表，并由函数返回结果顺序表。

bool Merge(SeqList A,SeqList B, SeqList &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[i++];
  }
  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;
}
           

8.已知在一维数组A[m+n]中依次存放两个线性表（a1，a2，a3，…,am）和（b1，b2，b3，…，bn）。试编写一个函数，将数组中的两个顺序表的位置互换，即将（b1，b2，b3，…，bn）放在（a1，a2，a3，…,am）的前面。

Typedef int DataType;
void Reverse(DataType A[],int left,int right,int arraySize){
  if(left>=right||right>=arraySize)
     return;
  int mid=(left+right)/2;
  for(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){
  Reverse(A,0,m+n-1,arraySize);
  Reverse(A,0,n-1,arraySize);
  Reverse(A,n,m+n-1,arraySize);
}
           

9.线性表（a1，a2，a3，…,an）中的元素递增有序且按照顺序存储于计算机内。要求设计一个算法，完成用最少的时间在表中查找数值为x的元素，若找到，即将其与后继元素位置想交换，若找不到，则将其插入表中并使表中元素仍递增有序。

void SearchExchangeInsert(ElemType A[],ElemType x){
  int low=0,high=n-1,mid;
  if(low<=high){
    mid=(low+high)/2
    if(A[mid]==x) break;
    else if(A[mid]<x) low=mid+1;
    else high=mid-1
  }
  if(A[mid]==x&&mid!=n-1){
    t=A[mid];A[mid]=A[mid+1];A[mid+1]=t
  }
  if(low>high){
    for(i=n-1;i>high;i--) A[i+1]=A[i];
    A[i+1]=x;
  }
}
           

10.设将n（n>1）个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由（X0，X1，X2，…，Xn-1）变换为（Xp，Xp+1，…，Xn-1，X0，X1，X2，…，Xp-1）。要求：

1）给出算法的基本设计思想

可将这个问题视为把数组ab转换成数组ba（a代表前p个元素，b代表后n-p个元素），先将a逆置，再将b逆置，最后对整个拟置，过程如下：
Reverse(0,p-1)
Reverse(p,n-1)
Reverse(0,n-1)
           

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释

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;
  }
}
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）  
           

11.一个长度为L（L>=1）的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=（11，13，15，17，19），则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=（2，4，6，8，20），则S1和S2的中位数为11.现在有两个等长升序序列A和B，试设计一个在时间和空间两方面尽可能高效的算法，找出两个序列A和B的中位数。要求：

1）给出算法的基本设计思想

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

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释

int M_Search(int A[],int B[]，int n){
  int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
  //分别表示序列A和B的首位数、末位数和中位数
  while(s1!=d1||s2!=d2){
    m1=(s1+d1)/2;
    m2=(s2+d2)/2;
    if(A[m1]==B[m2])
      return A[m1];
    if(A[m1]<B[m2]){
      if((s1+m1)%2==0){   //元素个数为奇数
        s1=m1;
        d2=m2;
      }
      else{               //元素个数为偶数
        s1=m1+1;
        d2=m2;
      }
    }
    else{
      if((s1+m1)%2==0){   //元素个数为奇数
        d1=m1;
        s2=m2;
      }
       else{             //元素个数为偶数
        d1=m1;
        s2=m2+1;
      }
    }
  }
  return A[s1]<A[s2]?A[s1]:A[s2];
}
           

3）说明你所设计的算法时间复杂度和空间复杂度

算法的时间复杂度为O（log2n） 空间复杂度为O（1）
           

1）给出算法的基本设计思想

1.选取候取的主元素。依次扫描数组中的每个整数，降低一个遇到的整数保存到c中，记录出现的次数NUM为1.若遇到下一个整数仍为NUM，则计数加一，否则计数减一；当计数为0时，将遇到的下一个整数保存到c中，计数重新为1，开始新一轮计数，直到扫描所有的数组元素。
           

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释

int Majority(intA[],int n){
  int i,c,count=1;  //c用来保存候选主元素，count用来计数
  c=A[0];
 for(i=1;i<n;i++){
   if(A[i]==c)
     count++;
   else
     if(count>0)
       count--;
     else{
       c=A[i];
       count=1;
     }
 }
  if(count>0)
    for(i=count=0;i<n;i++)
      if(A[i]==c)
        count++;
  if(count>n/2) return c
  else return -1;
}
           

3）说明你所设计的算法时间复杂度和空间复杂度

时间复杂度为O（n），空间复杂度为O（1）
           

1）给出算法的基本设计思想

要求时间上尽可能高效，因此采用空间换时间的方法。分配一个用于标记的数组B[n]用来记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0.由于A中含有n个整数，因此可能返回的值是1～n+1，当A中n个数恰好为1～n时返回n+1。当数组A中出现了小于等于0或大于n的值时，会导致1～n中出现空余位置，返回结果必然在1～n中，因此对于A中出现了小于等于0或大于n的值，不采取任何操作。
  
经过上述的分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n,则令B[A[i]-1]=1;否则不做操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数1～n之间。若B[i]全部不为0，返回i+1(跳出循环时i=n，i+1=n+1)，此时说明A中未出现的最小正整数是n+1。
           

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释

int findMissMin(int A[],int n){
  int i,*B;      //标记数组
  B=(int *)malloc(sizeof(int)*n);  //分配空间
  memset(B,0,sizeof(int)*n);   //赋初值为0
  for(i=0;i<n;i++)
    if(A[i]>0&&A[i]<=n)
      B[A[i]-1]=1;
  for(i=0;i<n;i++)
    if (B[i]==0) break;
  return i+1;
}
           

3）说明你所设计的算法时间复杂度和空间复杂度

时间复杂度：O（n）
空间复杂度：O（n）
           

1）给出算法的基本设计思想

分析。由D=｜a-b｜+｜b—c｜+｜c—a｜>=0有如下结论。
  1.当a=b=c时，距离最小。
  2.其余情况不失一般性，假设a<=b<=c,观察下面的数轴：
  L1=｜a-b｜
  L2=｜b-c｜
  L3=｜c-a｜
  D=｜a-b｜+｜b-c｜+｜c-a｜=L1+L2+L3=2L3
  由D的表达式可知，事实上决定D大小的关键是a和c之间的距离，于是问题就可以简化为每次固定c找一个a，使得L3=｜c-a|最小。
  
（1）使用Dmin记录所有已处理的三元组的最小距离，初值为一个足够大的整数
（2）集合S1、S2和S3分别保存在数组A、B、C中。数组的下标变量i=j=k=0，当i<｜S1｜、j<｜S2｜且k<｜S3｜时（｜S｜表示集合S中的元素个数），循环执行下面的a）～c）。
  a）计算（A[i]、B[j]、C[k]）的距离D；（计算D）
  b）若D<Dmin,则Dmin=D；（更新D）
  c）将A[i]、B[j]、C[k]中的最小值的下标+1；（对照分析：最小值a，最大值为c，这里c不变而更新a，试图寻找更小的距离D）
（3）输出Dmin，结束。
  
  
           

2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释

#define INT_MAX 0x7fffffff		
int abs_(int a){//计算绝对值
  if(a<0) return -a;
  else return a;
}
bool xls_min(int a,int b,int c){//a是否是三个数中的最小值
  if(a<=b&&a<=c) return true;
  return false;
}
int findMinofTrip(int A[],int n,int B[],int m,intC[],int p){
  //D_min用于记录三元组的最小距离，初值赋为INT_MAX
  int i=0,j=0,k=0,D_min=INT_MAX,D;
  while(i<n&&j<m&&k<p&&D_min>0){
   D=abs_(A[i]-B[j])+abs_(B[j]-C[k])+abs_(C[k]-A[i]); //计算D
   if(D<D_min) D_min=D; //更新D
   if(xls_min(A[i],B[j],C[k])) i++;
   else if(xls_min(B[j],C[k],A[i])) j++;
   else k++;
  }
  return D_min;
}
           

3）说明你所设计的算法时间复杂度和空间复杂度

设n=（｜S1｜+｜S2｜+｜S3｜），时间复杂度为O（n），空间复杂度为O（1）。