23年青島大學910數據結構強化班第一課時，學長帶你走進算...

青大考研校

歡迎大家來聽910數據結構專業強化班第一課時，第一節課是講算法的時間復雜度。

一定要牢記一句話，將算法章基本操作的執行次數作為算法時間復雜度的度量。

常用的時間復雜度比較關系：O(1)< O(logn) < O(n) < O(nlogn) < O(n2)。

計算時間復雜度，具體步驟：

第一步、確定基本操作基本題規模。

第二步、根據基本操作計算出規模的函數F（n），并確定要實行復雜度O（F（N））中最快的一項。

第一步找基本操作，又是以求時間復雜度的為目的前提下重復直銷次數和算法的執行時間成正比的操作。一般來說，這種操作組成的算法，當他們都執行完的時候，算法已經結束了，多數情況下取最深從循環內的語句做所描述的操作作為基本操作。

多數情況下最深層循環內的語句所描述的操作作為基本操作：

第一步、確診問題的規模。這要具體問題具體分析具體問題，如何度量一個算法的時間復雜度，首先應該與運行該算法的機器編譯器無關，不能在一臺電腦上套算法時間發動和另一臺電腦上套算法時間發動不同。

第二步、與解決的問題規模n有關。

在此它應該與算法的“1步”所執行的工作量無關。所以，在描述算法的時間性能時，只考慮宏觀間接形式，即當輸入問題規模n充分大的時候，觀察算法復雜度隨著n的增長趨勢：當n變量不斷能加時，解決問題所需要的時間的增長關系。比如線性增長T（n）=cn，即問題的規模n增長到2倍、3倍......時，解決問題需要時間n也增長到兩倍三倍誰無關？五平方增長這個c的n次方C乘n的屏幕包，那么問題微博n增長到2倍3倍......（與c無關）平方增長T（n）=cn2即問題規模增長到2倍、3倍....時，解決問題所需要的時間T（n）增長到4倍9倍....（與c無關）。如果我們最后求出來的復雜度基本操作f（n）=an2+n，則O（n）=n2

++x處于最基本內層，那么就是取++x作為基本操作。顯然n為規模，++x的執行次數為f（n）=n（n-1）/2，變化最快的項為n2/2，則時間復雜度為O(n2)k。

第二個函數同樣的，n為規模，++i和s=s+i為基本操作，重點：假設執行次數m此結束，則有s1=1，s2=1+2=3，s3=1+2+3=6.....Sm=m（m+1）/2，則有m（m+1）/2+K=n，（K為修正常數），再倒推m=（-1+根號（8n+1-8k））/2，則時間復雜度為O（根號n）。

算法用五個特性：

1、有窮性：算法必須保證執行有限步驟之后結束；

2、確定性：每一步都必須有確定的含義；

3、輸入：有零個或者多個輸入；

4、輸出：多輸出或多或少輸出。

5、可行性。

線性表示具有相同特性數據原則的一個有限序列。線性表中所按元素的個數叫做線性表的長度，用n來表示。一般來說，n可以等于0，表示一個空表。線性結構是最常用，最簡單的一種數據結構。線性表是一種典型的線性結構，

基本特點是線性表中的數據元素是有序且是有限的，這種結構中：

1、存在一個唯一的，被稱為“第一個”的數據元素；

2、存在一個被稱為“最后一個”的數據元素；

3、除第一個元素之外，每一個元素均有唯一一個直接前驅；

4、除最后一個元素外，每個元素均有唯一一個直接后期畫圖表示的話。

比如在一對學生啊。學生人數對應了線性表的長度，那么學生人數是有限的，表示一個有限序列，那么隊伍中所有人的身份都是學生體現了現象表中的數據源頭，具有相同的特性。線性表示可以是有序的，也可以是無序的。如果按照學生的身高量排隊，s在前沿高的在后就體現了有序性，那么在這一對學生中，只有一個學生在對頭，同樣也只有一個學生在對尾對頭的學生前面，沒有其他學對尾。學生后面沒有其他學生。除了對頭和對尾的學生以外，對于其他的每一個學生，緊挨著站在前面的和后面的學生都只有一個了。

NO.1

線性表

線性表也是這樣，只有一個比較多元素和一個標本元素，表頭元素沒有前驅表為元素，沒有后繼除表頭和表對元素之外，其他元素只有一個，直接前驅也只有一個，直接后繼。

線性表的邏輯結構，還有一個對象的存儲結構。先看線性表的定義，邏輯結構，線性表（Linear List）是由n（n≥0）個數據元素（結點）a1 ，a2 ，…，an 組成的有限序列。

① 數據元素的個數n定義為表的長度（n=0時稱為空表）。
② 將非空的線性表（n＞0）記作：（a1 ，a2 ，…，an ）
③ 數據元素ai （1≤i≤n）只是個抽象符號，其具體含義在不同情況下可以不同。

特性：

1、有限性：線性表中數據元素是無窮的。

2、相同性：線性表中數據元素類型是同一的。

3、順序性：線性表中相鄰元素的數據元素存在序偶關系。

順序表：Loc（ai）=Loc(a1)+(i-1)c。c就是儲存，一個元素的空間。隨機儲存在O1的時間內儲存數據元素。

順序儲存，把線性表的節點按邏輯順序依次存放在一組地址連續的存儲單元里，用這種方法存儲的線性表簡稱順序表。

順序儲存的線性表的特點：線性表的邏輯順序與物理順序一致，數據元素之間的關系是以元素在計算機內物理位置相鄰來體現。即邏輯上相鄰的在物理上也相鄰轉的特點，順序表要求占有連續的存儲空間，那么存儲空間只能預先進行，一旦分配好在對其操作的過程中始終不變。在內存中用地址連續的一塊儲存空間順序存放線性表的各元素。一維數組在內存中占用的存儲空間就是一組連續的存儲區域。

順序表上實現的基本運算

插入：

1、找出可以讓順序表保持有序的插入位置，

2、將找出的位置上以及氣候的元素往后移動一個位置，然后將X放置騰出的位置上。

具體算法描述：

順序表刪除操作過程：

在順序表上實現刪除運算必須移動結點，才能反映出結點間的邏輯關系的變化。若i=n，則只要簡單地刪除終端結點，無須移動結點；若1≤i≤n-1，則必須將表中位置i+1，i+2，…，n的結點，依次前移到位置i，i+1，…，n-1上，以填補刪除操作造成的空缺。其刪除過程

具體算法描述：

拆除操作中的躲移是從對左邊的元素開始移動。比如說要刪除第二位，主要將只要移動覆蓋掉，不可以后面的一個移，也就是刪除辦法主線，延長合法性，然后往前移動移動元素后面的約束往前移動。順序表示線性表的順序特殊結果，那同樣的還有練表練表就是它的練，也是它的結果。數據結構也是實現復雜數據結構的重要手段。不按照線性的順序，它就是數據，而是由若干個同一結構類型的節點一直串記而成及每一個節點。

NO.2

鏈表

鏈表是一種重要的基礎數據結構，也是實現復雜數據結構的重要手段，它不按照信息的順序存儲數據，而是由若干個同一結構類型的節點依次串接而成的集美一個節點里保存著下一個節點的地址。

列表又分為單向鏈表，雙向鏈表以及循環鏈表。

存儲思想：用一組任意的儲存單元存放線性表的元素，有連續、不連續、零散分布之分。

單鏈表：在每個節點中除包含有數據以外，只設置一個指針與用于指向其后繼節點，這樣構成的鏈接表稱為線性單向鏈接表簡稱單鏈表。單鏈表是由若干節點構成的，單鏈表的節點只有一個指針域。（date next）

1、如何引用數據元素？*s.date；或者s->date；

2、如何引用指針域？s->next

儲存特點：

1、邏輯次序和物理次序不一定相同

2、元素之間的邏輯關系用指針表示

帶頭結點和不帶頭結點

帶頭結點：頭指針head指向頭結點，那么頭接點的指針域不含任何信息，從頭接點的后續接點開始攜帶信息。head->next=NULL

不帶頭結點：所有結點都不含有信息。head==NULL

（1）單鏈表數據類型定義：

（2）單鏈表常見操作：

（3）單鏈表的遍歷

（4）鏈表的建立

有兩種常見的插入節點方式，一在鏈表的頭上不斷插入性節點，二在列表的尾部不斷插入性節點，

如果是后者，一般需要有一個臨時的節點指針，一直指向當前鏈表的最后一個節點，以方便性節點的插入。

尾插法建立單鏈表

頭插法建立單鏈表

頭節點在單鏈表的第1個元素節點之前復設一個類型相同的節點，以便空表和非空表處理統一，以指向頭節點的指針為鏈表的頭指針。

（5）頭指針頭節點與首元節點的關系：

頭節點是為了操作的統一與方便而設立的方便，第1個元素節點之前，其數據域一般無意義當然，有些情況下也可以存放鏈表的長度，用作監視哨等等，有了頭節點后，對在第1個元素節點前插入節點和刪除第1個節點，其操作與其它節點的操作統一首元節點，也就是第1個元素的節點，它的頭節點后面的第1個節點，在線性表的鏈式儲存結構中，頭指針是指鏈表指向第1個節點的指針，如果鏈表有頭節點，則頭指針就是指向鏈表頭節點的指針。

（6）線性表的鏈式儲存實現:

不要求邏輯上相鄰的兩個數據元素，物理上也是通過鏈建立起與數據元素之間的邏輯關系，因此對線性表的插入刪除不需要移動數據元素，只需要修改鏈。

（7）求表長

（8）核心操作（關鍵操作）：工作指針，后移從頭節點，開始或開始，節點通過工作指針的反復后移，而將整個單鏈表審視一遍的方法，稱為掃描（或編歷）。

1、按序號查找

2、按值查找

（9）線性表的插入操作的實現

（9）插入新節點步驟，在鏈表的第i個結點后插入一個值為x的新結點，

①先構造一個新結點，用temp指向

?再找到鏈表的第i-1個點，用pre指向

③然后修改指針，插入結點（pre之后插入新結點是temp）

（10）刪除（刪除鏈表的第i個位置上的結點）

①先找到鏈表的第i-1個節點，用pre指向

?再用指針tmp指向要被刪除的結點（pre的下一個結點)

③然后修改指針,刪除tmp所指結點

④最后釋放tmp所直結點的空間

（11）查找列表c帶頭節點中是否存在一個值為x的節點，若存在則刪除點并返回1，否則返回0。