導(dǎo)論：

與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)

通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致

數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位

數(shù)據(jù)元素是數(shù)據(jù)的基本單位

一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是：有序表

數(shù)據(jù)結(jié)構(gòu)中，樹是非線性數(shù)據(jù)結(jié)構(gòu)

算法的五個特征：輸入，輸出，確定性，有窮性，可行性

算法設(shè)計的基本要求：正確性、可讀性、健壯性、通用性、效率與存儲量的需求

時間復(fù)雜度：一個語句的頻度是指該語句在算法中被重復(fù)執(zhí)行的次數(shù)。

最壞時間復(fù)雜度

平均時間復(fù)雜度

最好時間復(fù)雜度

空間復(fù)雜度：對一個算法在運(yùn)行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。

簡單選擇、冒泡排序、插入排序的時間復(fù)雜度均為O（n的二次方）

算法原地工作是指算法所需輔助空間是常量，即O（1）。

常見的漸進(jìn)時間復(fù)雜度

線性表

數(shù)據(jù)的邏輯結(jié)構(gòu)

線性結(jié)構(gòu)

一般線性表

受限線性表

棧和隊(duì)列

串

線性表推廣

數(shù)組

廣義表

非線性結(jié)構(gòu)

集合

樹形結(jié)構(gòu)

一般樹

二叉樹

圖形結(jié)構(gòu)

有向圖

無向圖

線性結(jié)構(gòu)：

線性表：含n個相同數(shù)據(jù)類型的數(shù)據(jù)元素的有序序列，稱為線性表

線性表L=(a1，a2,……an)，除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。

線性表的兩種存儲

順序存儲和鏈?zhǔn)酱鎯?/span>

順序表

優(yōu)點(diǎn)：可以進(jìn)行隨機(jī)存取

缺點(diǎn)：插入和刪除操作需要移動大量元素

求表長、定位這兩種運(yùn)算在采用順序存儲結(jié)構(gòu)時實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實(shí)現(xiàn)的效率低

順序存儲的線性表可以隨機(jī)存取

由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活

插入：

在n個元素的順序表中，第i個位置插入一個結(jié)點(diǎn)，共n-i+1個元素向下移動一個位置，時間復(fù)雜度為O（n）

刪除：

在n個元素的順序表中，第i個元素刪除，共n-i個元素向下移動一個位置，時間復(fù)雜度為O（n）

查找：

位置和長度

鏈?zhǔn)?/span>

單鏈表：

數(shù)據(jù)域-指針域

用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，用這種方法存儲的線性表簡稱線性鏈表，而每一個結(jié)只包含一個指針域的鏈表，稱為單鏈表

了解插入，刪除的指向，先右后左

單列表的查找【按序號查找-按值查找】

雙向鏈表

指針域-數(shù)據(jù)域-指針域

鏈接存儲的存儲結(jié)構(gòu)所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針

線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址連續(xù)或不連續(xù)都可以

線性表Ｌ在（需不斷對Ｌ進(jìn)行刪除插入）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。

單鏈表的存儲密度小于1

將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是n

在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（ ?n-i+1 ）個元素。

在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（ ?s->next=p->next; p->next=s; ）

大部分都是定理。

參考文章:

https://blog.csdn.net/liu17234050/article/details/106315650