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）。