一米碰、數(shù)據(jù)結(jié)構(gòu)
1.1 數(shù)據(jù)結(jié)構(gòu)定義
? ? ? ? ? ?數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲补憾、組織數(shù)據(jù)的方式叛拷。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或者多種特定關(guān)系的數(shù)據(jù)元素的集合报亩。數(shù)據(jù)結(jié)構(gòu)=物理結(jié)構(gòu)+邏輯結(jié)構(gòu)
1.2 數(shù)據(jù)結(jié)構(gòu)的基本數(shù)據(jù)單位
1浴鸿、數(shù)據(jù)：是描述客觀事物的符號，是計算機(jī)中可以操作的對象弦追，是能被計算機(jī)識別赚楚，并輸入給計算機(jī)處理的符號集合。數(shù)據(jù)不僅僅包括整型骗卜、實型等數(shù)值類型宠页，還包括字符及聲音、圖像寇仓、視頻等非數(shù)值類型笤虫。
?2、數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的組合蔼紧、是數(shù)據(jù)的子集拨拓。
3、數(shù)據(jù)元素：組成數(shù)據(jù)的服猪，且有一定意義的基本單位供填，在計算機(jī)中通常作為整體處理。
4罢猪、數(shù)據(jù)項：一個數(shù)據(jù)元素有多個數(shù)據(jù)項組成近她。
關(guān)系圖如下：
數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)單位
1.3 數(shù)據(jù)結(jié)構(gòu)
? ? ? ? ? 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。
1.3.1邏輯結(jié)構(gòu)
邏輯結(jié)構(gòu)：數(shù)據(jù)對象中的數(shù)據(jù)元素之間的相互關(guān)系膳帕。邏輯結(jié)構(gòu)分為四種粘捎，分別是集合結(jié)構(gòu)、線性結(jié)構(gòu)危彩、樹形結(jié)構(gòu)攒磨、圖形結(jié)構(gòu)。
集合結(jié)構(gòu)
集合結(jié)構(gòu)
集合結(jié)構(gòu)中數(shù)據(jù)元素之間并沒有什么聯(lián)系汤徽，只是多個數(shù)據(jù)元素集合了在一起娩缰。
線性結(jié)構(gòu)
線性結(jié)構(gòu)
線性結(jié)構(gòu)中數(shù)據(jù)元素存在著先后順序的關(guān)系，一對一谒府。常用的線性結(jié)構(gòu)有：線性表拼坎，棧浮毯，隊列，雙隊列演痒，數(shù)組亲轨，串。
樹形結(jié)構(gòu)
樹形結(jié)構(gòu)
樹形結(jié)構(gòu)中數(shù)據(jù)元素之間一對多鸟顺，常見的樹形結(jié)構(gòu): 二叉樹,B樹,哈夫曼樹,紅黑樹等.
圖形結(jié)構(gòu)
圖形結(jié)構(gòu)
圖形結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系多對多惦蚊。常見的圖形結(jié)構(gòu): 鄰近矩陣,鄰接表.
1.3.2物理結(jié)構(gòu)
物理結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)的存儲形式.
物理結(jié)構(gòu)有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。
二讯嫂、數(shù)據(jù)結(jié)構(gòu)與算法
2.1.1算法
算法就是解決特定問題求解步驟的描述蹦锋，在計算機(jī)中表現(xiàn)為指令的有限序列，并且每個指令表示一個或者多個操作欧芽。
2.1.2算法特性
有輸入和輸出莉掂、有窮性、確定性千扔、可行性
2.1.3算法的設(shè)計要求
正確性憎妙、可讀性、健壯性曲楚、時間效率高和存儲量低
2.1.4常見的時間復(fù)雜度
時間復(fù)雜度
2.1.5算法空間復(fù)雜度
算法設(shè)計有一個重要原則厘唾，即空間/時間權(quán)衡原則（space/time tradeoff）。
算法的空間復(fù)雜度通過計算算法所需的存儲空間實現(xiàn),算法空間復(fù)雜度的計算公式記做: S(n) = n(f(n)),其中,n為問題的規(guī)模,f(n)為語句關(guān)于n所占存儲空間的函數(shù).
一般情況下, 一個程序在機(jī)器上執(zhí)行時,除了需要寄存本身所用的指令,常數(shù),變量和輸入數(shù)據(jù)外,還需要一些對數(shù)據(jù)進(jìn)行操作的輔助存儲空間. 其中,對于輸入數(shù)據(jù)所占的具體存儲量取決于問題本身,與算法無關(guān). 這樣**==只需要分析該算法在實現(xiàn)時所需要的輔助空間就可以了==**.
如果算法執(zhí)行時所需要的輔助空間相對于輸入數(shù)據(jù)量是一個常數(shù),則成這個算法原地工作,輔助空間為O(1).
