數(shù)據(jù)結(jié)構(gòu)常見筆試題-在線瀏覽
2025-05-12 03:01本頁面
【正文】 量－（front－rear）；當rearfront時，元素個數(shù)＝rear－front。比如一個鏈表是這樣的：12345通過反轉(zhuǎn)后成為54321。源代碼如下：法一：typedef struct LNode{int data。} LNode, *LinkList。head){if (head == NULL)return。p = head。while (p != NULL){q = p。qnext = head。}LNode *pre, *cur, *nex。cur = headnext。curnext = pre。cur = nex。head = pre。這種方法的基本思想是在反轉(zhuǎn)當前節(jié)點之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點。因為要改變head指針，所以我用了引用。head){if (p == NULL || pnext == NULL){head = p。}else{LNode *tmp = Reverse(pnext, head)。pnext = NULL。}}，例如下面這個鏈表就存在一個環(huán)：例如N1N2N3N4N5N2就是一個有環(huán)的鏈表，環(huán)的開始結(jié)點是N5這里有一個比較簡單的解法。每次循環(huán)p1向前走一步，p2向前走兩步。如果兩個指針相等則說明存在環(huán)。找環(huán)入口：根據(jù)所得環(huán)長Y，設(shè)置指針指向頭部，另一指針先向前走Y。struct Node{int data。}。if (head == NULL || headnext == NULL){return false。p2 = p2nextnext。amp。amp。if (p1 == p2)return true。}：給定兩個排好序的數(shù)組，怎樣高效地判斷這兩個數(shù)組中存在相同的數(shù)字？這個問題首先想到的是一個O(nlogn)的算法。用C++實現(xiàn)代碼如下：bool FindCommon(int a[], int size1, int b[], int size2){int i。 i size1。while (start = end){mid = (start + end)/2。else if (a[i] b[mid])end = mid 1。}}return false。因為兩個數(shù)組都是排好序的。首先設(shè)兩個下標，分別初始化為兩個數(shù)組的起始地址，依次向前推進。bool FindCommon2(int a[], int size1, int b[], int size2){int i = 0, j = 0。amp。if (a[i] b[j])j++。}return false。例如：整數(shù)序列2,11,4,13,5,2,5,3,12,9的最大子序列的和為21。利用三重循環(huán)，依次求出所有子序列的和然后取最大的那個。顯然這種方法不是最優(yōu)的，下面給出一個算法復雜度為O(n)的線性算法實現(xiàn)，算法的來源于Programming Pearls一書。其實這個算法只是對窮舉算法稍微做了一些修改：其實子序列的和我們并不需要每次都重新計算一遍。利用這一個遞推，我們就可以得到下面這個算法：int MaxSub(int a[], int size){int i, j, v, max = a[0]。 i size。for (j = i。 j++){v = v + a[j]。}}return max。先看一下源代碼實現(xiàn)：int MaxSub2(int a[], int size){int i, max = 0, tempSum = 0。 i size。if (tempSum max)max = tempSum。}return max。例
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1