算法类问题
木棒三角形
（枚舉）
#include <iostream> #include<stdlib.h> using namespace std; int main()//木棒三角形 有n根木棍 挑出其中三根構成直角三角形 輸出面積最大的三角形面積 輸入n再輸入每根三角形長度,n<100 {int n;//輸入n根木棍 再分別輸入每根木棍的長度 限制了n數量小于100int len[110];//每個數組元素儲存木棍長度 且要求長度由小到大給出while (scanf("%d", &n) != EOF) {for (int i = 0; i < n; i++)cin >> len[i];double ans = -1;for (int i = 0; i < n ; i++)//枚舉最短木棍for (int j = i + 1; j < n ; j++)for (int z = j + 1; j < n ; j++){//讓i < j < k,這樣棍子就不會被重復選中了if(len[i]*len[i] + len[j]*len[j]==len[z]*len[z]){if ((len[i] * len[i] + len[j] * len[j] + len[z] * len[z]) > ans)ans = 0.5 * len[i] * len[j];}}if (ans == -1)cout << "no !";elsecout << ans;} }順序查找
/順序查找 從第一個開始查找 關鍵字與給定值相比較 如果相等則退出int order(int array[], int n, int key){int i;array[n] = key;//監視哨for (i = 0; array[i] != key; i++);//分號不可少return (i < n ? i : -1);}折半查找
也叫二分查找 可以在最壞的情況下用O(logn)完成任務
int binarysearch(int array[], int key, int n) {int left = 0;int right = n - 1;while (left <= right){int middle = (left + right) / 2;if (array[middle] == key)return middle;if (left > array[middle])left = middle + 1;if (right < array[middle])right = middle - 1;}return -1; }二分查找:
二分搜索算法每次將候選區間減小至大約原來的一半。因此，要判斷長度為"的有序數組A中是否 包含x,只要反復執行約log?”次就完成了。二分查找的復雜度是O(log”)時間的，我們稱這種階的 運行時間為對數時間。即便n變得很大時，對數時間的算法依然非?？焖佟?/p> int n,x,k; int k[100]; bool binary(int x){ int l = 0,r = n; while(r - l>=1) { int i = (r+l)/2; if(k[i] == x)return true; else if(k[i] < x) l = i+1; else r = i;.} return true; }
/字符串統計
每組測試輸出兩個正整數 第一個是表示重復的次數，第二次是在該重復次數下有幾種不同的字符串
using namespace std; struct abc {char str[20];///int num; }que[20000]; int cmp(const void* a, const void* b) {abc* f1 = (abc*)a;abc* f2 = (abc*)b;return strcmp(f1->str, f2->str);//排序函數用于在qsort函數中將字符串從小到大排序 可以根據cmp的寫法來確定從大到小還是從小到大 } //qsort函數的基本用法：qsort(que,n,sizeof(que[0]),cmp)que為需要排序的序列首地址 //n為序列的元素 sizeof為序列中單個元素所占空間的大小 cmp為排序過程中用到的比較函數 有-1、0、1三種返回值 int main() {int count[20000];//存放種類數 其中[]中的數值是重復的次數int n;int number = 1;while (cin >> n){for (int i = 0; i < n; i++){cin >>que[i].str;count[i] = 0;}qsort(que, n, sizeof(que[0]), cmp);如果后一個元素等于前一個元素則出現次數加一int i = 1;//while(i < n)for (int i = 0; i < n - 1; i++){if (strcmp(que[i].str, que[i+1].str) == 0)//比較兩個字符串是否相等 不要用=={number++;continue;}count[number]++;//如果不相等了 再加上最后這一位本身number = 1;//恢復number}count[number]++;//for (int i = 1; i < n; i++){cout << i << " :" << count[i] << "";cout << endl;}}}遞歸:
//求解組合問題 1~n中任取r個數 求所有組合 //輸出一個組合 int r;//全局變量 void display(int a[]) {for (int i = 0; i < r; i++)cout << a[i]<<" ";cout << endl; } void mm(int a[], int n, int r) {for (int i = n; i >= r; i--){a[r - 1] = i;if (r > 1)mm(a, i - 1, r - 1);elsedisplay(a);} }int main() {int n;int a[8];cin >> n >> r;mm(a, n, r);}n皇后問題
using namespace std; //n皇后問題 //每個皇后不能同行不能同列且不能同對角線 const int N = 20;//最多的皇后數 int q[N];//存放皇后的列好 i是行數q[i]是列數即第i個皇后所在的列號place(k,n)是指【已經在1~k-1行上 //放好了k-1個皇后，現要在k~n上放n-k+1個皇后，則place（k+1,n）指已經在1~k行上放了k個皇后，要在k+1~n行 //放n-k個皇后 即place(k+1,n)比place(k,n)少放一個皇后，前者是小問題，后者是大問題 //當同對角線時 即等腰直角三角形 行的絕對值之差=列的絕對值之差 //本代碼i從1開始取，最大下標是n int ccount = 0;//解的個數 void display(int n) {ccount++;cout << "第" << ccount << "個解：";for (int i = 1; i <= n; i++)cout << i << " " << q[i]<<".";cout << endl;} //已經放好了k-1個皇后 考慮第k個皇后 它只能放第k行 j是傳進來的值 bool iff(int k, int j)//判斷（k,j)能否放皇后 已經放好的皇后是（i,q[i]) i為1~k-1 {int i = 1;while (i < k)//前面k-1行已經放了皇后{if (q[i] == j ||fabs(j - q[i]) == fabs(k - i))return false;i++;}return true; } void place(int k, int n) {if (k > n)display(n);//此時所有皇后放置結束elsefor (int j = 1; j <= n; j++)//在K行上窮舉每一個位置{if (iff(k, j))//找到了合適的位置（k,j)時{q[k] = j;place(k + 1, n);}} } int main() {int n;//實際的皇后數cin >> n;place(1, n); }[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-zna7DOv7-1604131085348)(C:\Users\14172\OneDrive\圖片\屏幕快照\2020-10-23 (3)].png)
數組。
設計算法高效將數組的奇數元素移到偶數元素后面
//設計算法盡可能高效地將所有奇數元素移動到偶數元素前面 //設置兩個指針 ij i=0,j = n-1,當ij不相等時循環 a[i]找偶數元素 a[j]找奇數元素 當i!=j時發生交換void swapp(int a[], int n) {int i = 0, j = n - 1;int temp;while (i != j){j--;if (a[j] % 2 == 1){for (; i != j; i++){if (a[i] % 2 == 0 && a[j] % 2 == 1 && i != j){temp = a[i];a[i] = a[j];a[j] = temp;i++;break;}}}} } int main() {m1 = 3;int m[] = { 1,2,3,4,4,5,6 };swapp(m, 7);for (int i = 0; i < 7; i++)cout << m[i];}以第一個元素為基準 大于該基準的移到后面
//以a[0]為基準將所有大于a[0]的元素移到該基準后面 小于等于的元素移到該基準前面 得到一個新的數組 void swapp(int a[], int n) {int temp;int num = a[0];int j = n - 1;//a[j]掃描小于a[0]的 a[i]掃描大于a[0]的 兩者發生交換int i = 0;while (i != j) {j--;if(a[j] < num)for (; i != j; i++){if (a[i] >= num){temp = a[i];a[i] = a[j];a[j] = temp;i++;break;}}} }//刪除一個已排序好的整數數組的重復元素 返回a
//刪除一個已排序好的整數數組的重復元素 返回a[](算法效率問題) //重建法 int* delee(int a[], int n) {int k = 0;for (int i = 0; i < n; i++){if (a[i] != a[i + 1//如果a[i]不是重復的元素則將a[i]重新插入到a中{a[k] = a[i];k++;//保留的元素增一}}return a; }//刪除給定的有序整數數組 兩個或兩個以上的 重復元素僅僅保留兩個
#include<iostream> using namespace std; int* delee(int a[], int& n) {//刪除給定的有序整數數組 兩個或兩個以上的 重復元素僅僅保留兩個int k = 0;int b[30] = { 0 };for (int i = 0; i < n-1; i++){if (a[i] != a[i + 1]){a[k] = a[i];k++;//保留的元素增一}if (a[i] == a[i + 1] && a[i] != a[i + 2] ){a[k] = a[i];a[k+1] = a[i + 1];k += 2;i += 1;}}n = k;//更新數組的個數 用引用傳遞 這樣在主函數中可以獲得新數組的大小return a; } int main() {int a[20] = { 2,2,2,2,3,3,3,4,5,6,7,7,8,8,8 };int k = 16;int* b= delee(a,k);for (int i = 0; i < k; i++)cout << b[i] << " "; }//假設數組a中有m+n個元素空間其中0~m-1存放m個升序 數組b存放n個降序整數 不借助其他數組將這些元素升序存放到a中
//采用二路歸并產生升序數組，用i從a[m-1]的元素開始向前掃描 j從前向后掃描 k=m+n-1指向最后一個位置 void shengxu(int a[], int m,int b[], int n) {int l = 0;int r = m - 1;int k = m+n-1;while (r >= 0 && l < n){if (b[l] > a[r])//如果b更大{a[k] = b[l];k--;l++;}else{a[k] = a[r];r--;k--;}while (r >= 0)//此時a的前半部分沒有掃完{a[k] = a[r];k--;r--;}while (l < n)//b的后部分沒有掃完{a[k] = b[l];l++;k--;} }} //上述算法時間復雜度為m+n空間復雜度為o(1) int main() {int a[31] = { -2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,20,21 };int b[10] = { 8,7,6,5,4,3,2,1,-3,-4};shengxu(a, 20, b, 10);for (int i = 0; i < 30; i++)cout << a[i] << " "; }高效判斷兩個數組是否存在相同元素
//采用二路歸并產生升序數組，用i從a[m-1]的元素開始向前掃描 j從前向后掃描 k=m+n-1指向最后一個位置 bool shengxu(int a[], int m,int b[], int n) {int i = 0, j = 0;while (i < m && j < n){if (a[i] == b[j])return true;else if (a[i] > b[j])j++;elsei++;}return false; }深度優先搜索算法
油田問題
//油田問題 一個油田是由m*n個單元組成的矩形，有些里面有石油，一個采油機可以把與該單元油田相連的油田采完，問至少 //需要多少臺采油機 //@表示有石油 //采用深度優先搜索算法 設變量many表示采油機 把整個地圖搜索完畢 當遇到沒有標號的油田時用深度優先搜索把與這塊油田相連 //的其他油田全部進行標號 #include <iostream>using namespace std; int dfs(int i, int j); int mmap[55][55] = { 0 }; char s[50][50] = { '0' }; int main() {int m, n;cin >> m >> n;for(int i = 0;i < m;i++)for (int j = 0; j < n; j++){cin >> s[i][j];}int many = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){if (mmap[i][j] == 0 && s[i][j] == '@')many += dfs(i, j);}cout << many; } int dfs(int i, int j) {mmap[i][j] = 1;//搜索過的地方置為1if (mmap[i + 1][j] == 0 && s[i + 1][j] == '@')dfs(i + 1, j);if (mmap[i][j + 1] == 0 && s[i][j + 1] == '@')dfs(i, j + 1);if (mmap[i - 1][j] == 0 && s[i - 1][j] == '@')dfs(i - 1, j);if (mmap[i][j - 1] == 0 && s[i][j - 1] == '@')dfs(i, j - 1);//將該點周圍上下左右四個點全部搜索并且標記為1return 1;//搜到一個符合條件的點時加一}螺旋矩陣 子矩陣之和（遞歸和非遞歸算法）
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ippBV9Ih-1604131085354)(C:\Users\14172\Pictures\數組.jpg)]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-lYFDRNjU-1604131085357)(C:\Users\14172\Pictures\數組2.jpg)]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-m0Tdomap-1604131085360)(C:\Users\14172\Pictures\子矩陣.jpg)]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-m8YyYCcW-1604131085364)(C:\Users\14172\Pictures\子矩陣解答.jpg)]
求一個a矩陣以（i,j)和(m,n)為對角線的子矩陣元素之和
//求一個a矩陣以（i,j)和(m,n)為對角線的子矩陣元素之和 int a[][100]; void sum(int a[][100], int b[][100], int m, int n) {b[0][0] = a[0][0];for (int i = 1; i < m; i++)b[0][i] = b[0][i - 1] + a[0][i];for (int i = 1; i < m; i++)b[i][0] = b[i - 1][0] + a[i][0];for (int i = 1; i < m; i++)for (int j = 1; j < n; i++)b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];//引入數組b b(i,j)存儲的是以a[0][0] a[i][j]//為對角線的矩陣元素之和 } int ziju(int b[][100], int s, int t, int m, int n){if(m == 0 && n == 0)return b[m][n];int sum = b[m][n] - b[m][t - 1] - b[s - 1][n] + b[s - 1][t - 1];return sum; }遞歸和非遞歸創建螺旋矩陣
//創建一個n階螺旋矩陣并輸出 //對于左上角（ix,iy)右下角(ex,ey)起始元素為start的那一圈，通過調用函數1產生 函數2用于創建整個螺旋矩陣 //設f(x,y,start,n)用于創建左上角為(x,y)起始元素為start的n階螺旋矩陣，是大問題，則f(x+1,y+1,start,n-2)是小問題 //（去掉最外面一大圈后剩下的部分） //有遞歸算法和非遞歸算法 int a[15][15] = { 0 }; void create(int& start,int ix,int iy,int ex,int ey)//最外面的大圈 {if (ix == ex)a[ix][iy] = start++;//當該圈只有一個元素時else{int curl = iy;while (curl != ey)a[ix][curl++] = start ++;curl = ix;while (curl != ex)a[curl++][ey] = start++;curl = ey;while (curl != iy)a[ex][curl--] = start++;curl = ex;while (curl != ix)a[curl--][iy] = start++;}} void spira(int x,int y,int n,int start)//遞歸調用螺旋矩陣 {if (n <= 0)//退出遞歸條件return;if (n == 1){a[x][y] = start;//矩陣大小為1時return;}else{for (int i = y; i < y+n-1; i++)//上一行a[x][i] = start++;for (int i = x; i < x+n-1; i++)//右一列a[i][x +n-1] = start++;for (int i = x +n-1;i > y; i--)//下一行a[x + n-1][i] = start++;for (int i =x+ n-1; i > x; i--)//左一列a[i][y] = start++;spira(x+1,y + 1, n-2,start);//遞歸調用自身}} void spira2(int n)//非遞歸調用螺旋矩陣 {int start = 1;int i = 0, j = 0, ex = n - 1, ey = n - 1;while (i <= ex)create(start, i++, j++, ex--, ey--);// 不斷循環調用創建最外圈元素的函數} void display(int n) {for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++)cout << a[i][j] << " ";cout << endl;//輸出} }[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-a8ZB6NYe-1604131085367)(C:\Users\14172\Pictures\屏幕截圖 2020-10-28 210335.png)]
//有兩個有序數組ab 元素個數m,n 設計一個高效算法求a和b的差集
//設a-b的元素數組為c int a[5], b[5]; int c[8] = { 0 }; void chaji(int m,int n,int a[],int b[]) {int i = 0, k = 0, j = 0;//k來維護c中元素個數while (i < m && j < n)//注意這個while循環很重要不能遺漏否則無法得到正確結果{if (a[i] < b[j]){c[k] = a[i];i++;k++;//只將a中較小的元素放入c中}else if (a[i] > b[j])//如果b中元素更小則跳過{j++;}else//如果元素相等 不能放入C中 下標加一{i++;j++;}}while (i < n)//注意要將如果a沒有遍歷完則全部放入C中{c[k] = a[i];i++;k++;}} int main() {int a[5] = { 3,4,9,10,77};int b[5] = { 2,3,5,6,4 };chaji(5, 5, a, b);for (int i = 0; i < 8; i++)cout << c[i]<<" "; }基于鏈表的算法設計
-
通常單鏈表是帶頭結點的結構，單鏈表如果有頭結點，通常用頭結點的地址即頭指針來標識整個單鏈表，第一個數據結點稱為首結點，指向首結點的指針稱為首指針，
-
頭結點是在鏈表的首元結點之前附設的一個結點；數據域內只放空表標志和表長等信息，它不計入表長度。
首元結點是指鏈表中存儲線性表第一個數據元素a０的結點。
其中頭指針只是指針，它指向頭結點或首元結點所對應的地址，在程序中，并沒有給它分配固定的內存；而頭結點和首元結點卻對應著固定的內存。頭結點和首元結點的區別在于數據域中是否存放了數據元素，頭結點中的數據域為空，或存放表長信息，引入它是為了方便鏈表的插入和刪除操作；而首元結點的數據域中會存儲第一個數據元素的值。 -
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-zTAyLxHh-1604131085370)(C:\Users\14172\Pictures==.png)]
-
Head指針為單鏈表的頭指針，單鏈表L：L既是單鏈表的名字，也是其頭指針。鏈表中的最后一個結點的指針域定義為空指針(NULL)。那么什么是頭指針呢？我們把指向第一個結點的指針稱為頭指針，那么每次訪問鏈表時都可以從這個頭指針依次遍歷鏈表中的每個元素，例如：
-
struct node first;
struct node *head = &first;這個head指針就是頭指針。
示例如下：#include <stdio.h> struct node { int data; struct node *next; }; int main(void) { struct node *head, first, second; head = &first; first.data = 1; first.next = &second; second.data = 2; second.next = NULL; while (head) { printf("%d\n", head->data); head = head->next; } return 0; }
這個頭指針的意義在于，在訪問鏈表時，總要知道鏈表存儲在什么位置（從何處開始訪問），由于鏈表的特性（next指針），知道了頭指針，那么整個鏈表的元素都能夠被訪問，也就是說頭指針是必須存在的。示例如下需要著重注意的是while那部分（通過頭指針遍歷完整個鏈表）。
單鏈表有帶頭結點和不帶頭結點之分。
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-GD3ESMcw-1604131085373)(C:\Users\14172\Pictures\111.jpg)]
那么什么又是頭結點呢？很多時候，會在鏈表的頭部附加一個結點，該結點的數據域可以不存儲任何信息，這個結點稱為頭結點，
頭結點的指針域指向第一個結點，例如：
struct node head, first;
head.next = &first;
那么這里的頭指針又是誰呢，不再是指向第一個結點的指針，而是指向頭結點的指針，例如：
struct node *root = &head;即root指針才是頭指針。示例如下：
1.刪除非空鏈表中值最大的結點
struct linklist {int data;linklist* next; }; void shanchu(linklist* p) {linklist* head = new linklist;p = head->next; linklist* L = head;//p的前驅結點int max = p->data;while (p != NULL)//查找最大的結點{p = p->next;if (p->data > max)max = p->data;}p = head->next;while (p != NULL){if (p->data == max){L->next = p->next;delete p;p = L->next;//讓p繼續指向L結點的后繼結點}else{L = p;p = p->next;//L和p都同時前移}} }2.將兩個遞增有序單鏈表合并為一個遞減有序單鏈表
空間復雜度為o(1)的頭插法:
struct linknode {int data;linknode* next; }; void guibing(linknode* &L1, linknode* &L2, linknode*& L3) {linknode* p1 = L1->next,*p2 = L2->next,*p3;delete L1;//釋放L1頭結點并置為NULLdelete L2;L1 = NULL;L2 = NULL;L3 = new linknode;L3->next = NULL;while (p1 != nullptr && p2 != nullptr){if (p1->data > p2->data){p3 = p1->next;//臨時保存p1結點的后繼結點p1->next = L3->next;//采用頭插法將p1插入到L3中L3->next = p1;p1 = p3;//p1指向下一個結點}else{p3 = p2->next;p2->next = L3->next;L3->next = p2;p2 = p3;}}if (p2 != nullptr){p1 = p2;//如果p2沒有掃完 讓p1指向p2結點}while (p1 != nullptr){p3 = p1->next;//臨時保存p1結點的后繼結點p1->next = L3->next;//采用頭插法將p1插入到L3中L3->next = p1;p1 = p3;//p1指向下一個結點} }[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-gduDJdnF-1604131085375)(C:\Users\14172\Pictures\22.jpg)]
將長度為n的單鏈表連接在長度為m的單鏈表之后，時間復雜度為m.（先通過遍歷找到尾結點p 再讓p結點的指針域指向長度為n的單鏈表首結點。）
3.遞歸算法逆置非空單鏈表
struct linknode {int data;linknode* next; }; //注意下面這個函數參數是值參數(對應的實參不變）而不是引用參數。如果改為引用是錯誤的 linknode* nizhi(linknode* first)//first為不帶頭結點的 {linknode* p;if (first == nullptr || first->next == nullptr)return first;p = nizhi(first->next);first->next->next = first;//first結點連接到first->next結點的后面 注意二者順序first->next = NULL;//first結點作為逆置后的尾結點return p; } //引用作為參數 void nizhi1(linknode* &L)//L為帶頭結點的單鏈表 {L->next = nizhi(L->next);//L->next為不帶頭結點的單鏈表 調用第一個函數 }4.逆置單鏈表中序號為i到j的結點
注意ij參數可能錯誤
struct linknode {int data;linknode* next; }; //逆置非空單鏈表中序號從i到j的結點 //為了防止i與j超過范圍要先求出長度 且第二個函數為bool型 int length(linknode* m) {int k = 0;linknode* p = m;while (p != nullptr){p = p->next;k++;}return k;//先求出單鏈表長度 } bool nizhiij(linknode* &L,int i,int j) {linknode* r;int len = length(L);if (i < 0 || i > len || j < 0 || j> len)return false;else{int n = 0;linknode* p = L,*q;while (n < i - 1 && p != NULL){n++;p = p->next;}//p為第i-1個結點linknode* m = p;linknode*r = p->next;p1 = r;//用p1保存逆置的第一個結點p->next = NULL;//斷開第i和第i-1個結點while (n < j && r != NULL){n++;q = r->next;//不斷將r結點到第j個結點采用頭插法插入到m結點之后r->next = m->next;m->next = r;r = q;}p1->next = q;//將第j個結點的后繼結點接到p1結點之后return true;} }5.對于一個帶頭結點的單鏈表以第一個結點為基準 將所有小于其值的結點移動到它前面 將所有大于等于其值的結點移動到它后面
void yidong(linknode* a) {linknode* p = a->next;//p指向首結點int data1 = p->data;//cache指向其后繼結點 如果cache值小于p值 通過p將cache刪除linknode* cache = p->next;if (a != nullptr || a->next == nullptr)return;while (cache != nullptr){int da2 = cache->data;//da2存放基準值if (da2 >= data1)//此時p和cache同步后移{p = cache;cache = p->next;}else{p->next = cache->next;//如果cache結點的值小于基準值 刪除cache結點 頭插法查到表a中cache->next = a->next;a->next = cache;cache = p->next;//cache繼續指向p結點的后繼結點}} }6.設計一個算法求非空單鏈表中間位置結點
(1,2,3,4)的中間位置是結點2 （1，2，3，4，5）中間位置是5
//方法：用快慢兩個指針 快指針一次移動兩個結點 循環結束后slow指向的結點即目標結點 linknode* middle(linknode* L) {if (L == nullptr)return NULL;if (L->next == nullptr)return L;linknode* fast = L->next,*slow = L->next;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;}return slow;}尾插法
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-bnZG9Yhq-1604131085377)(C:\Users\14172\Pictures\untitled.png)]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-cj2lzHkD-1604131085380)()]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-07qYDuBg-1604131085386)(C:\Users\14172\Pictures\21.png)]
注意是r->next = L1->next;(注意這兩個鏈表都有頭結點)
7.將一個非空單鏈表（a1,a2,…an,b1,b2…bn)重新排列為(a1,b1,a2,b2…,an,bn)
//空間復雜度為O(1) //采用尾插法 建立新表L r作為尾指針 利用上一題求中間結點的函數找到中間結點 void rearrange(linknode* &L) {if (L == NULL)return;linknode* mid = middle(L);//此題結點個數是偶數linknode* r = L;//新鏈表的尾結點linknode* p = r->next;//p指向結點a1linknode* q = mid->next;//q指向結點b1while (p != nullptr && q != nullptr){r->next = p;//p結點鏈接到新鏈表的表尾r = p;r->next = q;r = q;p = p->next;q = q->next;}r->next = NULL;//尾結點的指針域置空（盡管這里不需要，但這是一個好習慣）}8.設計一個算法判斷一個非空單鏈表是否為回文
//非遞歸算法 找到中間結點 后半部分構成帶頭結點的單鏈表p 將p逆置 然后依次按照結點順序判斷數據是否相等bool ispal(linknode* L) {if (L->next == nullptr || L->next->next == nullptr)return true;linknode *q,*q2,* p = new linknode;linknode* mid = middle(L);//中間結點p->next = mid->next;//將后半部分結點構成帶頭結點的單鏈表reverse(p);//逆置帶頭結點的單鏈表mid->next = p->next;//重新連接q = p->next;q2 = L->next;while (q != nullptr && q2 != mid->next){if (q->data !=q2->data)return false;q = q->next;q2 = q2->next;}return true; }9.判斷序列B是否是A序列的子序列
//先在A中找到與B結點值相等的結點pa,pb指向B的首結點然后比較值是否相等 相等則同步后移 bool subseq(linknode* A, linknode* B) {linknode* pa = A->next;while (pa != nullptr){linknode* pb = B->next;//每次循環開始pb都是指向B的首結點while(pa->next != nullptr && pa->data != pb->data)//只用來求出與B第一個結點相等的A中結點pa {pa = pa->next;}linknode* q = pa;//用q來保存pa ,以便pa進行下一輪循環（如果進入下一輪循環仍要匹配A中與B第一個結點相等的其他結點）while (q != nullptr && pb != nullptr && q->data == pb->data){q = q->next;//如果值相等同步移動pb = pb->next;}if (pb == nullptr)return true;else if(pa->next != nullptr)//如果A序列沒有遍歷完 ，則從下一個結點開始重復進行{pa = pa->next;}}return false; }不同顏色排列（數量未知） 【有無頭結點的寫法】
L有頭結點 L1,L2無
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-GqV607iS-1604131085390)(C:\Users\14172\Pictures\untitled.png)]
= nullptr)
return true;
linknode q,q2, p = new linknode;
linknode mid = middle(L);//中間結點
p->next = mid->next;//將后半部分結點構成帶頭結點的單鏈表
}
## 9.判斷序列B是否是A序列的子序列```c++ //先在A中找到與B結點值相等的結點pa,pb指向B的首結點然后比較值是否相等 相等則同步后移 bool subseq(linknode* A, linknode* B) {linknode* pa = A->next;while (pa != nullptr){linknode* pb = B->next;//每次循環開始pb都是指向B的首結點while(pa->next != nullptr && pa->data != pb->data)//只用來求出與B第一個結點相等的A中結點pa {pa = pa->next;}linknode* q = pa;//用q來保存pa ,以便pa進行下一輪循環（如果進入下一輪循環仍要匹配A中與B第一個結點相等的其他結點）while (q != nullptr && pb != nullptr && q->data == pb->data){q = q->next;//如果值相等同步移動pb = pb->next;}if (pb == nullptr)return true;else if(pa->next != nullptr)//如果A序列沒有遍歷完 ，則從下一個結點開始重復進行{pa = pa->next;}}return false; }不同顏色排列（數量未知） 【有無頭結點的寫法】
L有頭結點 L1,L2無
[外鏈圖片轉存中…(img-GqV607iS-1604131085390)]
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-zNQL42cZ-1604131085393)(C:\Users\14172\Pictures\00.png)]
二叉樹
求以二叉鏈存儲的二叉樹兩個結點的最大距離
三種情況：
代碼實現：
從根結點到葉結點所有結點值之和為sum的路徑
//每個結點儲存一個整數，求從根結點到葉結點路徑上所有結點之和等于sum的路徑 void disppath(vector<int> path) {vector<int>:: iterator ite;for( ite = path.begin(); ite != path.end(); ite++){cout<<*ite<<" ";} } void allpathsum(btnode *b, int sum, vector<int> path) {if(b == NULL) return;path.push_back(b->data);if(b -> lchild == NULL && b -> rchild == NULL){if(b -> data == sum)disppath(path);}//如果左子樹右子樹并非都空allpathsum(b->lchild,sum - b->data, path);//左右子樹中查找 allpathsum(b->rchild, sum- b->data, path) ;}對于一個給定的的結點值x,輸出所有從x到根結點的逆路徑
//每個結點儲存一個整數，對于一個給定的的結點值x,輸出所有從x到根結點的逆路徑 //逆路徑用棧保存 void display(stack<int>path)//輸出一條逆路徑 {while(!path.empty()){cout<<path.top()<<" ";path.pop();}} void allpath(btnode *b, int x,stack<int>path){if(b == NULL) return;path.push(b->data);//注意要先將b的值推入棧中再進行判斷 因為值為x的結點也要輸出 if(b->data == x)//當找到一個為x的結點，逆向輸出 display(path);allpath(b->lchild,x,path);allpath(b->rchild,x,path);//在左右子樹中查找 }求二叉樹最大路徑和（即路徑上所有結點之和的最大值）
如圖，藍色的一條路徑為最大值：
路徑和為某一個值的所有路徑 這里的路徑是從根結點出發
//給定二叉樹 二叉樹中尋找路徑和為某一個值的所有路徑 路徑從根結點出發 temsum存放臨時和（初始為0） vector<btnode *>path; void display(vector<btnode *> path) {for(int i = 0;i < path.size(); i++)cout<<path[i]->data<<" ";cout << endl; } void findpath(btnode *b, int sum, int temsum, vector<btnode *>path) {if(b == NULL) return;path.push_back( b );if(temsum + b->data == sum) display(path);findpath(b->lchild,sum , temsum + b->data,path);findpath(b->rchild,sum, temsum + b->data, path);}btnode *pa, *pb, *pc, *pd, *pe, *pg, *pf, *ph;btnode* creat(){pa = new btnode;pa->data = 2;pb = new btnode;pb->data = 3;pc = new btnode;pc->data = 1;pd = new btnode;pd->data = -1;pe = new btnode;pe->data = 4;pg = new btnode;pg->data = -6;pf = new btnode;pf->data = 6;ph = new btnode;ph->data = 20;pa->lchild = pb; pa->rchild = pc;pb->lchild = pd; pb->rchild = pe;pc->lchild = pg; pc->rchild = pf;pd->lchild = NULL; pd->rchild = NULL;pe->lchild = NULL; pe->rchild = NULL;pf->lchild = NULL; pf->rchild = NULL;pg->lchild = NULL; pg->rchild = ph;ph->lchild = NULL;ph->rchild = NULL;//這句話一定要寫 經過調試如果這句話沒有則無輸出 所以一定要設置ph左右子樹為空 return pa; }void clear(){//銷毀二叉樹delete pa;delete pb;delete pc;delete pe;delete pd;delete pf;delete pg;} int main() {btnode*m = creat(); int tmp = 0; findpath(m, 9, tmp, path);}3.21在每個結點中增加一個next指針，用于指向同一層的右兄弟或者堂兄弟， 設計算法實現
//先序和層次遍歷兩種方法 #include<queue> using namespace std; #define maxn 100 typedef struct node {char data;struct node* lchild;struct node* rchild;node* next; }btnode; //假設一顆二叉樹 在每個結點中增加一個next指針，用于指向同一層的右兄弟或者堂兄弟，如圖所示，設計一個算法實現這種 轉化 void trans(btnode* b, btnode* sibling) {//先序遍歷，用sibling指向當前結點b的兄弟 若b不空，修改其next指針指向siblingif (b == nullptr) return;elseb->next = sibling;//如果b不空，修改b的next trans(b->lchild, b->rchild);//遞歸處理左子樹，b左子樹的兄弟為b右子樹if (sibling != nullptr){trans(b->rchild, sibling);//當前結點b的兄弟不為空時 右孩子的next改為兄弟的左孩子}elsetrans(b->rchild, nullptr);//如果當前結點b的兄弟為空，右孩子的next為空 } //層次遍歷方式，按照h = 1,2,3...處理，將每一層的k個結點放到lnode數組中，當一層遍歷完畢后，將lnode數組中的結點用next指針鏈接 typedef struct {int lno;//結點的層次btnode* p;//結點指針 }qytype;//隊列元素類型 void process(btnode* lnode[], int k) {for (int i = 0; i < k - 1; i++)lnode[i]->next = lnode[i + 1];lnode[k - 1]->next = NULL; } void trans2(btnode* b) {btnode* lnode[maxn];//用于存放一層的所有結點 其中下標表示的是層 lnode[i]是第i層的結點個數queue<qytype>qu;btnode* tem;int k=0;//k記錄lnode中結點個數if (b == nullptr) return;qytype m;m.p = b;m.lno = 1;qu.push(m);int h = 1;//從第一層開始while (!qu.empty()){qytype tt = qu.front();qu.pop();tem = tt.p;if (tt.lno == h){lnode[k] = tem;//如果該結點是第h層，則將該結點存入lnode中k++;//結點個數加一}else{//如果該結點不屬于第h層 則輸出上一層的所有結點process(lnode, k);k = 0; h++;//結點個數清空 層數加一lnode[k] = tem;//該層第一個結點是temk++;//結點個數加一}if (tt.p->lchild != nullptr)//p結點有左孩子 將其進隊{tem = tt.p->lchild;tt.lno = tt.lno + 1;qu.push(tt);}if (tt.p->rchild != nullptr)//有右孩子 進隊{tem = tt.p->rchild;tt.lno = tt.lno + 1;qu.push(tt);}}process(lnode, k);;//處理最后一層的所有結點的next指針 注意實在while循環的外面}3.22給定一個二叉樹及其兩其中的兩個node求公共父節點到兩節點距離之和最小
//給定一個二叉樹及其兩其中的兩個node(地址均非空） 給出這兩個node的一個公共父節點，使得這個父節點 //與兩個結點的路徑之和最小struct treenode {treenode* left;//指向左右子樹treenode* right;treenode* father;//指向父節點 };//二叉樹采用三叉鏈存儲結構，根結點的father為NULL,求兩個非空結點first second的層次，比較兩個層次大小//通過Father指針將它們的指針移到相同層次，然后查找公共祖先結點 #define max(x,y) ((x) > (y)?(x):(y))int level(treenode* p){int l = 1;if (p->father != nullptr){p = p->father;l++;}return l;}treenode* lowestcommom(treenode* first, treenode* second){int i;if (first == nullptr || second == nullptr) return nullptr;int l1 = level(first);int l2 = level(second);if (l1 < l2){for (int i = l1; i < l2; i++)second = second->father;//如果Second層次更大 則second在first下面部分}else if (l1 > l2){for (int i = 0; i < l1 - l2; i++)first = first->father;}while (first != second){first = first->father;second = second->father;}return first;}3.23樹中每一個結點放一個整數 函數返回這棵二叉樹中相差最大的兩個結點間差的絕對值
//編寫函數 樹中每一個結點放一個整數 函數返回這棵二叉樹中相差最大的兩個結點間差的絕對值//通過一次先序遍歷求出最大結點指max和最小結點指min 返回abs(max - min)void maxmin(btnode* p, int& max, int& min){//求最大最小值的函數if (p == nullptr) return;if (p->data > max)max = p->data;if (p->data < min)min = p->data;maxmin(p->lchild, max, min);maxmin(p->rchild, max, min);//遞歸處理左右子樹}int fun(btnode* b){if (b == nullptr) return 0;int max, min;max = min = b->data;//初始化最大最小值maxmin(b, max, min);return abs(max - min);}3.24 設計算法用遞歸實現輸出二叉樹的層次遍歷
//以二叉鏈存儲的二叉樹 設計算法用遞歸實現輸出二叉樹的層次遍歷 //采用一個全局兩層向量result存放先序遍歷結果 只是按結點b的層次h將其存放在result[h-1]向量元素中，然后 //一層一層輸出result即構成層次遍歷序列vector<vector<int>>result; void travel(btnode* b, int h) {if (b == NULL) return;if (h > result.size()){result.push_back(vector<int>());}result[h - 1].push_back(b->data);travel(b->lchild, h + 1);travel(b->rchild, h + 1);} void levelorder(btnode* b) {travel(b, 1);for (int i = 0; i < result.size(); i++)for (int j = 0; j < result[i].size(); j++)cout << result[i][j]<<" ";//輸出結果}3.25//設計算法釋放二叉樹
//設計算法釋放二叉樹 //只能用后序遍歷，不能前序或者中序，因為只有將子樹空間釋放后才能釋放根結點的空間，否則會丟失子樹 void deletetree(btnode* b) {if (b != nullptr){deletetree(b->lchild);deletetree(b->rchild);delete b;} }枚舉
你的朋友提議玩一個游戲：將寫有數字的"個紙片放入口袋中，你可以從口袋中抽取4次紙 片，每次記下紙片上的數字后都將其放回口袋中。如果這4個數字的和是機，就是你贏，否 則就是你的朋友贏。你挑戰了好幾回，結果一次也沒贏過，于是怒而撕破口袋，取出所有紙 片，檢查自己是否真的有贏的可能性。請你編寫一個程序，判斷當紙片上所寫的數字是k2, —,kn時，是否存在抽取4次和為m的方案。如果存在，輸yes;否則，輸出no
n = 3
m = 10
k = (1, 3, 5)
輸出
Yes （例如4次抽取的結果是1、1、3、5,和就是10 ）
(挑戰程序設計競賽）
請計算所有螞蟻落下竿子所需 的最短時間和最長時間。
當螞蟻爬到竿子的端點時就會掉落。 由于竿子太細，兩只螞蟻相遇時，它們不能交錯通過，只能各自反向爬回去。對于每只螞蟻, 我們知道它距離竿子左端的距離的，但不知道它當前的朝向。
輸入
L = 10
n = 3
x = {2, 6, 7)
輸出
min = 4 （左、右、右）
max = 8 （右、右、右）
首先對于最短時間，看起來所有螞蟻都朝向較 近的端點走會比較好。事實上，這種情況下不會發生兩只螞蟻相遇的情況，而且也不可能在比此 更短的時間內走到竿子的端點。事實上，可以知道兩只螞蟻相遇后，當它們保持原樣交錯而過繼續前進也不會有任何問題。這樣不論最長時間還是最短時間，都只要對每只螞蟻檢查一次就好了，
總結
- 上一篇： 职工管理系统
- 下一篇： 结构体数组实现的简易学生信息管理系统