數據結構演算法問題

Ⅰ 數據結構有哪些基本演算法

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法

Ⅱ 數據結構 設計高效演算法問題

// 要求是刪除順序表中在范圍[x, y]內的元素。
// 按常規思路，每刪除一個順序表元素，則要將其後的元素整體前移一個位置。這種演算法用到了雙重for循環，時間復雜度為O(n^2)。
// 以下的演算法只用到了單重for循環，時間復雜度為O(n)。原理是把所有不在范圍[x, y]內的元素依次保存到順序表的前部，而不處理本來要刪除的、在范圍[x, y]內的元素。當把所有不需要刪除的元素都保存到了順序表前部，只需要重新設置一下順序表的長度為「前部」的最大下標+1，就模擬了刪除操作。

void fun(SqList *&L, ElemType x)
{
// i為循環計數器。
// j為不需要刪除的元素個數，初始化為0。
int i, j = 0;

// 依次遍歷順序表的每個元素
for (i = 0; i < L->length; ++i)
{
// 只處理不需要刪除的元素，即不屬於區間[x, y]的元素
if (!(L->data[i] >= x && L->data[i] <= y))
{
// 每找到一個不需要刪除的元素，就把該元素保存到下標j的位置。
L->data[j] = L->data[i];
// 隨後令j自增1。之前j代表的是處理後的順序表的最大下標，現在j代表的是處理後的順序表的長度。由於下標從0開始，所以長度永遠比最大下標大1。
++j;
}
}

// 設置順序表的長度為j，這樣以後遍歷順序表只能訪問前j個元素。即使下標j之後可能還存在屬於[x, y]的元素，但是不會訪問到它們，自然相當於「刪除」了。
L->length = j;
}

Ⅲ 設計一個好的演算法通常要考慮哪些要求

數據結構中評價一個好的演算法，應該從四個方面來考慮，分別是：

一、演算法的正確性。

二、演算法的易讀性。

三、是演算法的健壯性。

四、是演算法的時空效率（運行）。

演算法的設計取決於數據（邏輯）結構，演算法的實現取決於所採用的存儲結構。數據的存儲結構本質上是其邏輯結構在計算機存儲器中的實現。為了全面反映一個數據的邏輯結構，它在內存中的影像包括兩個方面，即數據元素之間的信息和數據元素之間的關系。

不同的數據結構有相應的操作。數據的操作是在數據的邏輯結構上定義的操作演算法，如檢索、插入、刪除、更新和排序。

(3)數據結構演算法問題擴展閱讀

該演算法的一般性質包括：

1．通用性對於任何符合輸入類型的輸入數據，都可以根據演算法解決問題，並且包保證了計算結構的正確性。

2．演算法的每一條指令都必須能夠被人或機器執行。

3．確定性演算法應該在每一步之後都有明確的下一步指示。也就是說，確保每個步驟都有下一步行動的指示，不缺少或只包含含糊的下一步行動指示。

4．有限演算法的執行必須在有限步結束。

Ⅳ 數據結構中演算法分析的問題

第一個第二個問題，就相當於你高中學的f(x)，沒什麼實際意義，也不用糾結
為什麼用T表示呢，代表時間

而一般所說的時間復雜度，都是用大O表示的
你學過函數應該知道，次數最高的那項對函數的增長影響最大，所以這里可以忽略其他低次項
前面的系數也可以省去，對於這個程序的就是O(n2)