《數(shù)據(jù)結(jié)構(gòu)C語言版》嚴蔚敏c1概論

《數(shù)據(jù)結(jié)構(gòu)c語言版》嚴蔚敏pptc1概論CATALOGUE目錄數(shù)據(jù)結(jié)構(gòu)基本概念與術(shù)語線性表及其順序存儲結(jié)構(gòu)鏈表及其基本操作實現(xiàn)棧和隊列及其應(yīng)用場景數(shù)組和廣義表存儲結(jié)構(gòu)樹和二叉樹基本概念與性質(zhì)01數(shù)據(jù)結(jié)構(gòu)基本概念與術(shù)語數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的基石，它使程序更加高效、易于理解和維護。選擇合適的數(shù)據(jù)結(jié)構(gòu)可以顯著提高算法的效率。重要性數(shù)據(jù)結(jié)構(gòu)定義及重要性數(shù)據(jù)元素數(shù)據(jù)的基本單位，通常作為一個整體進行考慮和處理。數(shù)據(jù)項構(gòu)成數(shù)據(jù)元素的不可分割的最小單位，如一個學(xué)生的學(xué)號、姓名、成績等。數(shù)據(jù)對象性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)類型一個值的集合和定義在這個值集上的一組操作的總稱。常用術(shù)語解釋一個數(shù)學(xué)模型以及定義在該模型上的一組操作，是對數(shù)據(jù)的抽象描述，強調(diào)了對數(shù)據(jù)的操作，而不是數(shù)據(jù)在計算機中的具體表示。抽象數(shù)據(jù)類型（ADT）通過選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)和算法來實現(xiàn)抽象數(shù)據(jù)類型中的操作。抽象數(shù)據(jù)類型的實現(xiàn)抽象數(shù)據(jù)類型介紹算法定義算法是解決特定問題的一系列步驟，它具有有限性、確定性、輸入項、輸出項和有效性等特性。算法分析對算法的正確性、可讀性和效率等性能進行研究和評估。主要關(guān)注算法的時間復(fù)雜度和空間復(fù)雜度。時間復(fù)雜度描述了算法執(zhí)行時間隨問題規(guī)模增長的變化趨勢，而空間復(fù)雜度描述了算法所需存儲空間隨問題規(guī)模增長的變化趨勢。算法和算法分析02線性表及其順序存儲結(jié)構(gòu)線性表是一種具有n個元素的有限序列，其中元素按照順序排列，每個元素有且僅有一個前驅(qū)和一個后繼（除首尾元素外）。線性表中的數(shù)據(jù)元素之間是一對一的關(guān)系；除首尾元素外，其他元素有且僅有一個前驅(qū)和一個后繼。線性表定義及特點線性表特點線性表定義順序存儲結(jié)構(gòu)定義順序存儲結(jié)構(gòu)是用一段連續(xù)的存儲空間來依次存放線性表的各個元素，通常以數(shù)組來實現(xiàn)。順序存儲結(jié)構(gòu)原理在順序存儲結(jié)構(gòu)中，線性表的邏輯順序和物理順序是一致的，即線性表中第i個元素的存儲位置與其邏輯序號i之間存在一一對應(yīng)的關(guān)系。順序存儲結(jié)構(gòu)實現(xiàn)原理初始化順序表為順序表分配存儲空間，并設(shè)置初始狀態(tài)（如元素個數(shù)為0等）。插入元素在順序表的指定位置插入一個新元素，需要移動插入位置及其后面的所有元素。刪除元素刪除順序表中的指定元素，需要移動被刪除元素后面的所有元素。查找元素在順序表中查找指定元素，可以從表頭或表尾開始遍歷，直到找到為止。順序表基本運算實現(xiàn)方法字符串處理字符串可以看作是一個特殊的線性表，其中每個元素表示一個字符。使用順序表可以方便地進行字符串的拼接、比較和查找等操作。多項式計算多項式可以看作是一個線性表，其中每個元素表示一個項，包括系數(shù)和指數(shù)。使用順序表可以方便地實現(xiàn)多項式的加減和乘法運算。稀疏矩陣壓縮存儲稀疏矩陣中大部分元素為0，只有少數(shù)元素非零?？梢詫⒎橇阍匕凑找欢ㄒ?guī)則存儲在一個順序表中，以節(jié)省存儲空間并提高計算效率。學(xué)生成績管理使用順序表可以方便地管理學(xué)生的成績信息，包括學(xué)號、姓名、成績等?？梢詫Τ煽冞M行排序、查找和統(tǒng)計等操作。順序表應(yīng)用舉例03鏈表及其基本操作實現(xiàn)

鏈表定義及分類概述鏈表是一種物理存儲單元上非連續(xù)的、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（每一個結(jié)點都包含數(shù)據(jù)和指向下一個結(jié)點的指針）組成，結(jié)點可以在運行時動態(tài)生成。鏈表分類：單向鏈表、雙向鏈表、循環(huán)鏈表等。03單鏈表的插入和刪除操作較為方便，只需修改相關(guān)結(jié)點的指針即可。01單鏈表由頭指針和一系列結(jié)點構(gòu)成，每個結(jié)點包含數(shù)據(jù)域和指針域。02單鏈表只能從頭結(jié)點開始，依次訪問后續(xù)結(jié)點，不能逆向訪問。單鏈表結(jié)構(gòu)與特點分析單鏈表的初始化單鏈表的遍歷單鏈表的插入單鏈表的刪除單鏈表基本運算實現(xiàn)方法創(chuàng)建一個空鏈表或帶頭結(jié)點的鏈表。在指定位置前插入一個新結(jié)點，需要修改前驅(qū)結(jié)點的指針域。從頭結(jié)點開始，依次訪問后續(xù)結(jié)點，并輸出結(jié)點的數(shù)據(jù)域。刪除指定位置的結(jié)點，需要修改前驅(qū)結(jié)點的指針域，使其指向后繼結(jié)點。循環(huán)鏈表和雙向鏈表簡介循環(huán)鏈表尾結(jié)點的指針域指向頭結(jié)點，形成一個環(huán)形結(jié)構(gòu)。循環(huán)鏈表可以從任意結(jié)點開始遍歷，訪問所有結(jié)點。雙向鏈表每個結(jié)點包含兩個指針域，一個指向前驅(qū)結(jié)點，一個指向后繼結(jié)點。雙向鏈表可以方便地訪問前驅(qū)結(jié)點和后繼結(jié)點，但需要更多的存儲空間。04棧和隊列及其應(yīng)用場景棧(Stack)定義01棧是一種特殊的線性表，其只允許在表的一端進行插入和刪除操作，通常稱這一端為棧頂(Top)，另一端為棧底(Bottom)。棧的特點02后進先出（LastInFirstOut，LIFO）。實現(xiàn)方式03?？梢杂脭?shù)組或鏈表來實現(xiàn)。數(shù)組實現(xiàn)的棧稱為順序棧，鏈表實現(xiàn)的棧稱為鏈式棧。棧定義、特點及實現(xiàn)方式棧在函數(shù)調(diào)用中應(yīng)用舉例01函數(shù)調(diào)用時，系統(tǒng)會在內(nèi)存中開辟一個棧幀來保存局部變量和返回地址。02當函數(shù)遞歸調(diào)用時，每次調(diào)用都會推入新的棧幀，每次返回則會彈出當前棧幀。表達式求值時，可以使用棧來保存操作數(shù)和運算符，實現(xiàn)后綴表達式求值等算法。03隊列(Queue)定義隊列是一種特殊的線性表，其只允許在表的一端進行插入操作，而在另一端進行刪除操作，通常稱插入的一端為隊尾(Rear)，刪除的一端為隊頭(Front)。隊列的特點先進先出（FirstInFirstOut，F(xiàn)IFO）。實現(xiàn)方式隊列可以用數(shù)組或鏈表來實現(xiàn)。數(shù)組實現(xiàn)的隊列稱為順序隊列，鏈表實現(xiàn)的隊列稱為鏈式隊列。此外，還可以使用循環(huán)隊列等數(shù)據(jù)結(jié)構(gòu)來優(yōu)化隊列操作。隊列定義、特點及實現(xiàn)方式123操作系統(tǒng)中的打印任務(wù)、網(wǎng)絡(luò)數(shù)據(jù)包的傳輸?shù)榷伎梢允褂藐犃衼磉M行管理。在多線程編程中，隊列也常用于線程間的通信和數(shù)據(jù)共享。在廣度優(yōu)先搜索（BFS）等算法中，隊列也扮演著重要的角色。隊列在操作系統(tǒng)中應(yīng)用舉例05數(shù)組和廣義表存儲結(jié)構(gòu)數(shù)組存儲結(jié)構(gòu)的原理數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，它的元素按照順序存儲在連續(xù)的內(nèi)存空間中，每個元素都可以通過下標進行訪問。數(shù)組存儲結(jié)構(gòu)的特點數(shù)組具有隨機訪問性，即可以在O(1)的時間復(fù)雜度內(nèi)訪問任意元素；但是，數(shù)組的插入和刪除操作需要移動大量元素，時間復(fù)雜度較高。數(shù)組存儲結(jié)構(gòu)原理及特點對稱矩陣壓縮存儲對于對稱矩陣，可以只存儲其上三角或下三角部分，從而節(jié)省存儲空間。三角矩陣壓縮存儲對于上三角矩陣或下三角矩陣，可以將其非零元素按照一定規(guī)律壓縮存儲到一維數(shù)組中。對角矩陣壓縮存儲對于對角矩陣，可以將其對角線上的元素和非零元素分別存儲，以進一步減少存儲空間。特殊矩陣壓縮存儲方法將稀疏矩陣的非零元素以三元組(行標,列標,值)的形式存儲，可以節(jié)省大量存儲空間。三元組表示法使用鏈表來存儲稀疏矩陣的非零元素，每個節(jié)點包含行標、列標和值，以及指向下一個非零元素的指針。鏈式存儲法針對稀疏矩陣的鏈式存儲進行優(yōu)化，通過添加額外的指針來提高矩陣運算的效率。十字鏈表法稀疏矩陣壓縮存儲方法廣義表定義及存儲結(jié)構(gòu)廣義表是線性表的擴展，它允許表中的元素本身也是一個廣義表。廣義表通常使用遞歸的方式來定義。廣義表的定義廣義表可以采用鏈式存儲結(jié)構(gòu)，每個節(jié)點包含數(shù)據(jù)域和指向子表的指針域。由于廣義表的元素可以是子表，因此需要遞歸地定義和處理節(jié)點。廣義表的存儲結(jié)構(gòu)06樹和二叉樹基本概念與性質(zhì)輸入標題02010403樹結(jié)構(gòu)定義及表示方法樹（Tree）是n（n≥0）個結(jié)點的有限集。當n=0時，稱為空樹。樹的表示方法有多種，常用的有孩子表示法、孩子兄弟表示法等。當n>1時，其余結(jié)點可分為m（m>0）個互不相交的有限集T1、T2、……、Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。在任意一棵非空樹中，有且僅有一個特定的稱為根（Root）的結(jié)點。VS在二叉樹的第i層上至多有2^(i-1)個結(jié)點（i≥1）；深度為k的二叉樹至多有2^k-1個結(jié)點（k≥1）；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1等。二叉樹的分類包括完全二叉樹、滿二叉樹、平衡二叉樹等。二叉樹的性質(zhì)包括二叉樹定義、性質(zhì)及分類遍歷二叉樹是指按照某種次序訪問二叉樹中的每個結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。常見的遍歷方式有先序遍歷、中序遍歷和后序遍歷。線索二叉樹是對二叉樹遍歷的一種優(yōu)化，利用空指針來存放指向結(jié)點在某種遍歷次序下的前驅(qū)結(jié)點和后繼結(jié)點的指針，這些指針稱為線索，加上線索的二叉樹稱為線索二叉樹。遍歷二叉樹和線索二叉樹010203樹轉(zhuǎn)換為二叉樹加線、去線