23王道數(shù)據(jù)結(jié)構(gòu)代碼題全解（一）-創(chuàng)新互聯(lián)

計劃更新23王道數(shù)據(jù)結(jié)構(gòu)所有課后代碼習(xí)題的實(shí)現(xiàn)，雖然考試寫的一般都是偽代碼，但是強(qiáng)迫癥的我還是全部實(shí)現(xiàn)了一遍，倉庫在這里
專注于為中小企業(yè)提供成都網(wǎng)站制作、成都網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)隴南免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了千余家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
代碼全部是用 C++ 寫的，都可以編譯運(yùn)行，包含暴力解和最優(yōu)解。
持續(xù)更新，目前更新進(jìn)度：
線性表 7/14
…
僅供參考！會包含一些考試不讓寫的語法，可能也會有一些錯誤。

順序表結(jié)構(gòu)體

考試直接使用，一般不會讓你寫出結(jié)構(gòu)體

#define ElemType int
#define MaxSize 50

typedef struct {ElemType data[MaxSize];
  int length;
}SqList;

2.2.3, 1

暴力解法一般就是循環(huán)，循環(huán)一次不行，就來兩次，兩次不行三次 …
時間復(fù)雜度 O(n)，空間復(fù)雜度O(1)

int del_min(SqList &list) {if (list.length == 0) {cout<< "Error!"<< endl;
    return -1;
  }

  // 1.假設(shè)0號元素最小
  int min = list.data[0]; 
  int pos = 0;

  // 2.循環(huán)找出最小元素并記錄位置, 從1開始
  for (int i = 1; i< list.length; i++) {if (list.data[i]< min) {  min = list.data[i];
      pos = i;
    }
  }

  // 3.刪除最小元素并用最后一個元素替換
  list.data[pos] = list.data[list.length - 1];
  list.length--; 

  return min;
}

2.2.3, 2

暴力就是再整一個數(shù)組，原數(shù)組從末尾循環(huán)遍歷放到新數(shù)組里
要求空間復(fù)雜度O(1)的話，從頭循環(huán)到中間，交換頭尾元素
偶數(shù)或者奇數(shù)個元素，循環(huán)到中間，都是< length/2，因?yàn)槿绻L度為4或者5，都是循環(huán)到下標(biāo)為1即停，為5的時候最中間的元素（下標(biāo)為2）不需要移動。
時間復(fù)雜度O(n)

void reverse(SqList &list) {for (int i = 0; i< list.length / 2; i++) {// 不讓用swap()的話，可以定義一個輔助變量來交換
    swap(list.data[i], list.data[list.length - 1 - i]);
  }
}

2.2.3, 3

暴力就是再整一個數(shù)組，循環(huán)遍歷把不等于x的元素都放入新數(shù)組
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)就要求一次循環(huán)內(nèi)解決
把所有等于x的元素都扔到最后，然后 length 減掉就可以了
也就是把所有不等于x的元素扔到前面，后面自然就是等于x的元素了

void del_x(SqList &list, int x) {int k = 0;
  for (int i = 0 ; i< list.length ; i++) {// 1.把所有要保存的值都放在前面
    if (list.data[i] != x) {  list.data[k++] = list.data[i];
    }
  }
  // 2.直接扔掉后面的元素
  list.length = k;
}

一次循環(huán) ->雙指針
類似快排，從兩端向中間移動，將左邊的x與右邊的非x交換

// 太麻煩了，不如上一個方法
void del_x_2(SqList &list, int x) {int i = -1, j = list.length, k = 0;
  while (i< j) {while (list.data[++i] != x); 
    while (list.data[--j] == x) k++;
    if (i< j) {  swap(list.data[i], list.data[j]);
      k++;
    }
  }
  list.length -= k;
}

2.2.3, 4

跟第3題一樣的解法
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)

void del_st(SqList &list, int s, int t) {if (s >= t || list.length == 0) {cout<< "ERROR!"<< endl;
    return;
  }

  // 1.要保存的值都放在前面
  int k = 0; 
  for (int i = 0; i< list.length; i++) {if (list.data[i]< s || list.data[i] >t) {  list.data[k++] = list.data[i];
    }
  }
  
  // 2.直接扔掉后面的值
  list.length = k;
}

王道答案：自找麻煩的做法
有序 ->從頭循環(huán)找>= s，繼續(xù)找>t的元素
一次循環(huán)，或者找t從后往前再循環(huán)一次
while+++真的非常好用，最好像我這樣：先-1然后用前++
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)

void del_st2(SqList &list, int s, int t) {if (s >= t || list.length == 0) {cout<< "ERROR!"<< endl;
    return; 
  }

  // 1.找到大于等于s的值
  int i = -1;
  while (list.data[++i]< s);

  // 2.如果全部元素均小于s
  if (i >= list.length) {cout<< "ERROR!"<< endl;
    return; 
  }

  // 3.找到大于t的元素
  int j = i-1;
  while (list.data[++j]<= t);

  // 4.前移，直接占住被刪元素的位置
  while(j< list.length) {list.data[i++] = list.data[j++];
  }
  list.length = i;
}

2.2.3, 5

與第4題只差了不是有序表，但3，4題的解法仍然可以用
只要把要保存的值放在前面，再扔掉后面的值就可以了
不要被答案限制了你的思路?
時間復(fù)雜度O(n)，空間復(fù)雜度O(1)

void del_st(SqList &list, int s, int t) {if (s >= t || list.length == 0) {cout<< "ERROR!"<< endl;
    return;
  }

  // 1.要保存的值都放在前面
  int k = 0; 
  for (int i = 0; i< list.length; i++) {if (list.data[i]< s || list.data[i] >t) {  list.data[k++] = list.data[i];
    }
  }
  
  // 2.直接扔掉后面的值
  list.length = k;
}

王道答案的做法非常麻煩，不推薦！

2.2.3, 6

有序列表 ?? 相同元素排列在一起
暴力，新開一個數(shù)組，將不同元素存入
需要兩個指針分別操作兩個數(shù)組
時間復(fù)雜度O(n)，空間復(fù)雜度O(n)

void del_same(SqList &list) {if (list.length == 0) return;
  
  // 1.新開一個數(shù)組
  SqList copied = list;
  copied.data[0] = list.data[0];

  // 2.把不同元素存入
  int k = 0;
  for (int i = 1; i< list.length; i++) {if (list.data[k] != copied.data[i]) {  copied.data[++k] = list.data[i];
    }
  }

  // 3.新?lián)Q舊
  copied.length = k + 1;
  list = copied;
}

仔細(xì)想想，其實(shí)并不需要兩個數(shù)組，雙指針就可以
前一個存儲，后一個判斷

void del_same2(SqList &list) {if (list.length == 0) return;

  int k = 0;
  for (int i = 1; i< list.length; i++) {if (list.data[k] != list.data[i]) {  list.data[++k] = list.data[i];
    }
  }
  list.length = k + 1;
}

2.2.4, 7

這種題太典型了，合并有序順序表以及合并有序鏈表，建議全文背誦hh
循環(huán)，取下兩個之中的較小的放入結(jié)果表中
最后那個表還有剩余就把剩下的部分全部加入結(jié)果表

SqList merge(SqList A, SqList B) {SqList C;
  if (A.length + B.length >MaxSize) {cout<< "ERROR!"<< endl;
    return C;
  }

  int i = 0, j = 0, k = 0;
  // 1.兩兩比較，小的存入結(jié)果表
  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++];
  }

  // 2.剩下的全部加入結(jié)果表，兩個循環(huán)只會有一個運(yùn)行
  while (i< A.length) 
    C.data[k++] = A.data[i++];
  while (i< B.length) 
    C.data[k++] = B.data[j++];

  // 3.返回結(jié)果表
  C.length = k;
  return C;
}

補(bǔ)充一下歸并排序

void merge_sort(int l, int r) {if (l >= r) return;

  int mid = (l+r) >>1;
  merge_sort(l, mid);
  merge_sort(mid+1, r);		

  int k = 0, i = l, j = mid+1;
  while (i<= mid && j<= r) {if (q[i]<= q[j]) 
      tmp[k++] = q[i++];
    else 
      tmp[k++] = q[j++];
  }
  
  while (i<= mid) 
    tmp[k++] = q[i++];
  while (j<= r) 
    tmp[k++] = q[j++];

  for (i = l, j = 0; i<= r; i++, j++) 
    q[i++] = tmp[j++];
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：23王道數(shù)據(jù)結(jié)構(gòu)代碼題全解（一）-創(chuàng)新互聯(lián)
新聞來源：http://weahome.cn/article/eocgi.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

23王道數(shù)據(jù)結(jié)構(gòu)代碼題全解（一）-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管