數據結構課件

數據結構講師：第一章緒論課程性質數據結構是計算機專業(yè)的專業(yè)基礎課

公共基礎課、專業(yè)基礎課、專業(yè)方向課、專業(yè)選修課在教學計劃中的地位：核心、承上啟下

前導課：高等數學、離散數學、程序設計語言后續(xù)課：數據庫、操作系統、編譯原理……屬于武術中的“練功”科目

“練武不練功，到頭一場空”考研：專業(yè)課必考教學目標掌握基本的數據結構

工具箱→復用、修改、重組培養(yǎng)算法設計能力、程序設計能力

算法——程序的靈魂問題求解過程：問題→想法→算法→程序程序設計研究的層次：算法→方法學→語言→工具培養(yǎng)算法分析能力

評價算法、改進算法學編程的境界學會寫程序學會高效地寫程序學會寫高效的程序學會設計算法學會設計有用的算法

學習要求循序漸進，切忌心浮氣躁提高課外學習的時間和內容理解科學而不是背誦科學→讀書正確對待考試作習題

華羅庚：“學數學不做習題等于入寶山而空返”

作實驗

計算機學科是一門科學性與工程性并重的學科，表現為理論和實踐緊密結合的特征。

第1章緒論數據結構在程序設計中的作用本書討論的主要內容數據結構的基本概念算法及算法分析本章的基本內容是：1938年出生，25歲畢業(yè)于加州理工學院數學系，博士畢業(yè)后留校任教，28歲任副教授。30歲時，加盟斯坦福大學計算機系，任教授。從31歲起，開始出版他的歷史性經典巨著：TheArtofComputerProgramming，他計劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計算機科學界的最高榮譽——圖靈獎，此時，他年僅36歲。數據結構的創(chuàng)始人——克努思1.1數據結構在程序設計中的作用程序設計的實質是什么?數據表示：將數據存儲在計算機（內存）中數據處理：處理數據，設計方案（算法）數據結構問題起源于程序設計

1.1數據結構在程序設計中的作用利用計算機求解問題的一般過程?計算機不能分析問題并產生問題的解決方案，必須由人來分析問題，確定問題的解決方案，編寫程序，然后讓計算機執(zhí)行程序最終獲得問題的解。1.1數據結構在程序設計中的作用例1-1手機電話號碼查詢問題將電話號碼集合組織成線性結構和樹結構，查找操作的效率不同，當數據量較大時差別就更大。1.2本書討論的主要內容計算機求解問題:

問題→抽象出問題的模型→求模型的解問題——數值問題、非數值問題數值問題→數學方程非數值問題→數據結構例1-2學籍管理問題完成什么功能?各表項之間是什么關系？1.2本書討論的主要內容例1-3人——機對弈問題如何實現對弈?各格局之間是什么關系？1.2本書討論的主要內容例1-4七巧板涂色問題

如何表示區(qū)域之間的鄰接關系？1.2本書討論的主要內容本書討論非數值問題的數據組織和處理，主要內容如下：（1）數據的邏輯結構：線性表、樹、圖等數據結構，其核心是如何組織待處理的數據以及數據之間的關系；（2）數據的存儲結構：如何將線性表、樹、圖等數據結構存儲到計算機的存儲器中，其核心是如何有效地存儲數據以及數據之間的邏輯關系；（3）算法：如何基于數據的某種存儲結構實現插入、刪除、查找等基本操作，其核心是如何有效地處理數據；（4）常用數據處理技術：查找技術、排序技術、索引技術等。1.2本書討論的主要內容1.3數據結構的基本概念數據：所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。數值數據：整數、實數等非數值數據：圖形、圖象、聲音、文字等數據元素：數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數據項：構成數據元素的不可分割的最小單位。數據結構的基本概念學號姓名性別出生日期政治面貌0001陸宇男1986/09/02團員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團員數據項數據元素數據、數據元素、數據項之間的關系包含關系：數據由數據元素組成，數據元素由數據項組成。數據元素是討論數據結構時涉及的最小數據單位，其中的數據項一般不予考慮。1.3數據結構的基本概念數據結構數據元素關系數據結構：相互之間存在一定關系的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關系的整體。1.3數據結構的基本概念數據結構的基本概念關聯方式或鄰接關系數據的邏輯結構是從具體問題抽象出來的數據模型學籍管理問題中，表項之間的邏輯關系指的是什么？人機對弈問題中，格局之間的邏輯關系指的是什么？教學計劃編排問題中，課程之間的邏輯關系指的是什么？數據結構：相互之間存在一定關系的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關系的整體。1.3數據結構的基本概念數據結構的基本概念數據的邏輯結構在形式上可定義為一個二元組：Data_Structure=(D,R)其中D是數據元素的有限集合，R是D上關系的集合。數據結構：相互之間存在一定關系的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關系的整體。1.3數據結構的基本概念數據結構的基本概念Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={<A,B>,<A,E>,<A,F>,<B,C>,<B,D>,<C,D>,<D,E>,<D,G>,<E,F>,<E,G>}數據結構：相互之間存在一定關系的數據元素的集合。按照視點的不同，數據結構分為邏輯結構和存儲結構。邏輯結構：指數據元素之間邏輯關系的整體。存儲結構：又稱為物理結構，是數據及其邏輯結構在計算機中的表示。1.3數據結構的基本概念數據結構的基本概念內存存儲結構實質上是內存分配，在具體實現時依賴于計算機語言。數據結構從邏輯上分為四類：⑴集合：數據元素之間就是“屬于同一個集合”；1.3數據結構的基本概念數據結構的基本概念數據結構從邏輯上分為四類：⑴集合：數據元素之間就是“屬于同一個集合”；⑵線性結構：數據元素之間存在著一對一的線性關系；1.3數據結構的基本概念數據結構的基本概念數據結構從邏輯上分為四類：⑴集合：數據元素之間就是“屬于同一個集合”；⑵線性結構：數據元素之間存在著一對一的線性關系；⑶樹結構：數據元素之間存在著一對多的層次關系；1.3數據結構的基本概念數據結構的基本概念數據結構從邏輯上分為四類：⑴集合：數據元素之間就是“屬于同一個集合”；⑵線性結構：數據元素之間存在著一對一的線性關系；⑶樹結構：數據元素之間存在著一對多的層次關系；⑷圖結構：數據元素之間存在著多對多的任意關系。1.3數據結構的基本概念數據結構的基本概念通常有兩種存儲結構：1.順序存儲結構：用一組連續(xù)的存儲單元依次存儲數據元素，數據元素之間的邏輯關系由元素的存儲位置來表示?！璪atcateat…起始地址例：（bat,cat,eat）1.3數據結構的基本概念數據結構的基本概念通常有兩種存儲結構：1.順序存儲結構：用一組連續(xù)的存儲單元依次存儲數據元素，數據元素之間的邏輯關系由元素的存儲位置來表示。2.鏈接存儲結構：用一組任意的存儲單元存儲數據元素，數據元素之間的邏輯關系用指針來表示。例：（bat,cat,eat）1.3數據結構的基本概念數據結構的基本概念0200020803000325…………bat0200cat0325eat∧邏輯結構和存儲結構之間的關系數據的邏輯結構屬于用戶視圖，是面向問題的，反映了數據內部的構成方式；數據的存儲結構屬于具體實現的視圖，是面向計算機的。一種數據的邏輯結構可以用多種存儲結構來存儲，而采用不同的存儲結構，其數據處理的效率往往是不同的。

1.3數據結構的基本概念抽象數據類型1.數據類型（DataType）：一組值的集合以及定義于這個值集上的一組操作的總稱。

例如：C++中的整型變量

2.抽象（Abstract）:抽出問題本質的特征而忽略非本質的細節(jié)。

例如：地圖、駕駛汽車3.抽象數據類型（AbstractDataType，ADT）:一個數據結構以及定義在該結構上的一組操作的總稱。1.3數據結構的基本概念1.3數據結構的基本概念抽象數據類型在設計ADT時，把ADT的定義、設計和實現分開來。定義部分只包含數據的邏輯結構和所允許的操作集合，一方面，ADT的使用者依據這些定義來使用ADT，即通過操作集合對該ADT進行操作；另一方面，ADT的實現者依據這些定義來完成該ADT各種操作的具體實現。ADT抽象數據類型名Data數據元素之間邏輯關系的定義Operation

操作1

前置條件：執(zhí)行此操作前數據所必須的狀態(tài)

輸入：執(zhí)行此操作所需要的輸入

功能：該操作將完成的功能

輸出：執(zhí)行該操作后產生的輸出

后置條件：執(zhí)行該操作后數據的狀態(tài)操作2

…………操作n……endADT

1.3數據結構的基本概念抽象數據類型1.3數據結構的基本概念（小結）數據的操作：插入、刪除、修改、檢索、排序等數據的邏輯結構數據的存儲結構順序存儲鏈式存儲集合線性結構樹結構圖結構非數值問題數據表示算法的相關概念1.算法（Algorithm）:是對特定問題求解步驟的一種描述，是指令的有限序列。2.

算法的五大特性：⑴

輸入：一個算法有零個或多個輸入。⑵輸出：一個算法有一個或多個輸出。⑶有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。⑷確定性：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出。⑸可行性：算法描述的操作可以通過已經實現的基本操作執(zhí)行有限次來實現。1.4算法及算法分析

歐幾里德算法（有窮性、確定性、可行性）mnr例：歐幾里德算法——輾轉相除法求兩個自然數m

和n

的最大公約數1.4算法及算法分析算法的描述方法——自然語言優(yōu)點：容易理解缺點：冗長、二義性使用方法：粗線條描述算法思想

注意事項：避免寫成自然段1.4算法及算法分析步驟1：將m除以n得到余數r；步驟2：若r等于0，則n為最大公約數，算法結束；否則執(zhí)行步驟3；步驟3：將n的值放在m中，將r的值放在n中，重新執(zhí)行步驟1；例：歐幾里德算法自然語言1.4算法及算法分析優(yōu)點：流程直觀缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次算法的描述方法——流程圖1.4算法及算法分析N開始輸入m和n

r=m%nr=0m=n；n=r輸出n結束Y流程圖例：歐幾里德算法1.4算法及算法分析優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數算法的描述方法——程序設計語言1.4算法及算法分析#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}程序設計語言例：歐幾里德算法1.4算法及算法分析偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。優(yōu)點：表達能力強，抽象性強，容易理解使用方法：7±2算法的描述方法——偽代碼1.4算法及算法分析1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;偽代碼上述偽代碼再具體一些，用C++的函數來描述。例：歐幾里德算法1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}1.4算法及算法分析對C++語言進行了如下簡化：⑴局部變量可以不聲明；⑵寫出子函數即可，子函數不用在主函數中調用，省略主函數；⑶所有的包含函數（頭函數.h）可以省略；⑷交換兩個變量的語句可以簡寫為a←→b。算法分析度量算法效率的方法：

事后統計：將算法實現，測算其時間和空間開銷。

缺點：⑴編寫程序實現算法將花費較多的時間和精力；⑵所得實驗結果依賴于計算機的軟硬件等環(huán)境因素。

事前分析：對算法所消耗資源的一種估算方法。1.4算法及算法分析算法分析算法分析（AlgorithmAnalysis）：對算法所需要的計算機資源——時間和空間進行估算。時間復雜性（TimeComplexity）空間復雜性（SpaceComplexity）1.4算法及算法分析算法的時間復雜度分析1.4算法及算法分析算法分析算法的執(zhí)行時間＝每條語句執(zhí)行時間之和執(zhí)行次數×執(zhí)行一次的時間指令系統、編譯的代碼質量單位時間每條語句執(zhí)行次數之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語句的執(zhí)行次數問題規(guī)模：輸入量的多少?；菊Z句：是執(zhí)行次數與整個算法的執(zhí)行次數成正比的操作指令。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問題規(guī)模：n基本語句：x++1.4算法及算法分析算法分析定義

若存在兩個正的常數c和n0，對于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))。n0問題規(guī)模n執(zhí)行次數n0之前的情況無關緊要T(n)c×f(n)當問題規(guī)模充分大時在漸近意義下的階。1.4算法及算法分析算法分析——大O符號定理：若A(n)=amnm+am-1nm-1++a1n+a0是一個m次多項式，則A(n)=O(nm)。說明：在計算算法時間復雜度時，可以忽略所有低次冪和最高次冪的系數。1.4算法及算法分析算法分析——大O符號例1-5

++x;例1-6

for(i=1;i<=n;++i)++x;例1-7for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;

例1-8for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;1.4算法及算法分析算法分析例1-9for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}例1-10for(i=1;i<=n;i=2*i) ++x;Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)1.4算法及算法分析算法分析最好情況、最壞情況、平均情況例：在一維整型數組A[n]中順序查找與給定值k相等的元素（假設該數組中有且僅有一個元素值為k）。

intFind(intA[],intn)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }1.4算法及算法分析基本語句的執(zhí)行次數是否只和問題規(guī)模有關？最好情況：出現概率較大時分析最差情況：實時系統平均情況：已知輸入數據是如何分布的，通常假設等概率分布結論：如果問題規(guī)模相同，時間代價與輸入數據有關，則需要分析最好情況、最壞情況、平均情況。1.4算法及算法分析最好情況、最壞情況、平均情況本章小結——知識結構圖緒論數據結構算法基本概念邏輯結構存儲結構⑴數據⑵數據元素⑶數據對象⑷ADT⑴邏輯結構⑵數據結構的分類⑴存儲結構⑵常用存儲方法基本概念算法分析⑴算法⑵算法特性⑶評價算法⑷描述算法⑴問題規(guī)模⑵基本語句⑶時間復雜度⑷大O記號關系第二章線性表本章的基本內容

線性表的邏輯結構

線性表的順序存儲及實現

線性表的鏈接存儲及實現

順序表和鏈表的比較

線性表的其他存儲方法2.1線性表的邏輯結構數據元素之間的關系是什么？2.1線性表的邏輯結構數據元素之間的關系是什么？現實生活中，許多問題抽象出的數據模型是線性表，如何存儲這種線性結構并實現插入、刪除、查找等基本操作呢？線性表：簡稱表，是n（n≥0）個具有相同類型的數據元素的有限序列。線性表的長度：線性表中數據元素的個數?？毡恚洪L度等于零的線性表，記為：L=()。非空表記為：L＝（a1,a2,…,ai-1,ai,…,an)2.1線性表的邏輯結構線性表的定義其中，ai（1≤i≤n）稱為數據元素；下角標i表示該元素在線性表中的位置或序號。a1a3a4ana22.1線性表的邏輯結構線性表的特性1.有限性：線性表中數據元素的個數是有窮的。2.相同性：線性表中數據元素的類型是同一的。3.順序性：線性表中相鄰的數據元素ai-1和ai之間存在序偶關系(ai-1,ai)，即ai-1是ai的前驅，ai是ai-1的后繼；a1無前驅，an無后繼，其它每個元素有且僅有一個前驅和一個后繼。

線性表的抽象數據類型定義ADTListData

線性表中的數據元素具有相同類型，相鄰元素具有前驅和后繼關系OperationInitList

前置條件：表不存在輸入：無

功能：表的初始化輸出：無

后置條件：建一個空表2.1線性表的邏輯結構DestroyList

前置條件：表已存在

輸入：無

功能：銷毀表

輸出：無

后置條件：釋放表所占用的存儲空間Length

前置條件：表已存在

輸入：無

功能：求表的長度

輸出：表中數據元素的個數

后置條件：表不變2.1線性表的邏輯結構線性表的抽象數據類型定義Get

前置條件：表已存在

輸入：元素的序號i

功能：在表中取序號為i的數據元素

輸出：若i合法，返回序號為i的元素值，否則拋出異常

后置條件：表不變Locate

前置條件：表已存在

輸入：數據元素x

功能：在線性表中查找值等于x的元素

輸出：若查找成功，返回x在表中的序號，否則返回0

后置條件：表不變2.1線性表的邏輯結構線性表的抽象數據類型定義Insert

前置條件：表已存在

輸入：插入i；待插x

功能：在表的第i個位置處插入一個新元素x

輸出：若插入不成功，拋出異常

后置條件：若插入成功，表中增加一個新元素Delete

前置條件：表已存在

輸入：刪除位置i

功能：刪除表中的第i個元素

輸出：若刪除成功，返回被刪元素，否則拋出異常

后置條件：若刪除成功，表中減少一個元素2.1線性表的邏輯結構線性表的抽象數據類型定義Empty

前置條件：表已存在

輸入：無

功能：判斷表是否為空

輸出：若是空表，返回1，否則返回0

后置條件：表不變ADT進一步說明:（1）線性表的基本操作根據實際應用是而定；（2）復雜的操作可以通過基本操作的組合來實現；（3）對不同的應用，操作的接口可能不同。2.1線性表的邏輯結構線性表的抽象數據類型定義2.2線性表的順序存儲結構及實現順序表——線性表的順序存儲結構例：（34,23,67,43）342367434存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數據元素2.2線性表的順序存儲結構及實現順序表——線性表的順序存儲結構例：（34,23,67,43）34236743存儲空間的起始位置4用什么屬性來描述順序表？順序表的容量（最大長度）順序表的當前長度2.2線性表的順序存儲結構及實現順序表——線性表的順序存儲結構例：（34,23,67,43）342367434如何實現順序表的內存分配？順序表一維數組0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度2.2線性表的順序存儲結構及實現順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：數組的長度Max線性表的長度Length數組的長度大于等于當前線性表的長度如何求得任意元素的存儲地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度2.2線性表的順序存儲結構及實現順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：cLoc(ai)Loc(a1)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度Loc(ai)=Loc(a1)+(i-1)×c隨機存?。涸贠(1)時間內存取數據元素2.2線性表的順序存儲結構及實現順序表一般情況下，(a1，a2，…,ai-1，ai,…,an)的順序存儲：cLoc(ai)Loc(a1)2.2線性表的順序存儲結構及實現存儲結構是數據及其邏輯結構在計算機中的表示；存取結構是在一個數據結構上對查找操作的時間性能的一種描述。存儲結構和存取結構“順序表是一種隨機存取的存儲結構”的含義為：在順序表這種存儲結構上進行的查找操作，其時間性能為O(1)。順序表類的聲明constintMaxSize=100;template<classDataType>//模板類classSeqList{public:SeqList();//構造函數

SeqList(DataTypea[],intn);~SeqList();//析構函數intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:DataTypedata[MaxSize];intlength;};2.2線性表的順序存儲結構及實現操作接口：SeqList()

算法描述：SeqList<DataType>

::SeqList(){length=0;}2.2線性表的順序存儲結構及實現順序表的實現——無參構造函數

datalength0操作接口：SeqList(DataTypea[],intn)順序表的實現——有參構造函數2.2線性表的順序存儲結構及實現順序表

數組a351224334253512243342template<classDataType>SeqList<DataType>

::SeqList(DataTypea[],intn){if(n>MaxSize)throw"參數非法";

for(i=0;i<n;i++)

data[i]=a[i];length=n;}2.2線性表的順序存儲結構及實現順序表的實現——有參構造函數算法描述：操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x

,ai,…,an)順序表的實現——插入2.2線性表的順序存儲結構及實現ai-1和ai之間的邏輯關系發(fā)生了變化順序存儲要求存儲位置反映邏輯關系存儲位置要反映這個變化33例：（35，12，24，42），在i=2的位置上插入33。表滿：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序號）2.2線性表的順序存儲結構及實現順序表的實現——插入435122442a1a2a3a401234422412335什么時候不能插入？注意邊界條件1.如果表滿了，則拋出上溢異常;2.如果元素的插入位置不合理，則拋出位置異常;3.將最后一個元素至第i個元素分別向后移動一個位置；4.將元素x填入位置i處；5.表長加1；算法描述——偽代碼2.2線性表的順序存儲結構及實現順序表的實現——插入template<classDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length>=MaxSize)throw"上溢";

if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];data[i-1]=x;length++;}算法描述——C++描述2.2線性表的順序存儲結構及實現順序表的實現——插入基本語句？最好情況（i=n+1）：基本語句執(zhí)行0次，時間復雜度為O(1)。最壞情況（i=1）：基本語句執(zhí)行n+1次，時間復雜度為O(n)。平均情況（1≤i≤n+1）：時間復雜度為O(n)。時間性能分析2.2線性表的順序存儲結構及實現順序表的實現——插入?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)操作接口：DataTypeDelete(inti)刪除前：(a1,…,ai-1,ai,ai+1,…,an)刪除后：(a1,…,ai-1,ai+1,…,an)

順序表的實現——刪除2.2線性表的順序存儲結構及實現ai-1和ai之間的邏輯關系發(fā)生了變化順序存儲要求存儲位置反映邏輯關系存儲位置要反映這個變化例：（35,33,12,24,42），刪除i=2的數據元素。仿照順序表的插入操作，完成：1.分析邊界條件；2.分別給出偽代碼和C++描述的算法；3.分析時間復雜度。2.2線性表的順序存儲結構及實現順序表的實現——刪除535a1a2a3a401234422412334a5122442順序表的實現——按位查找操作接口：DataTypeGet(inti)

2.2線性表的順序存儲結構及實現0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑

n算法描述：template<classDataType>DataTypeSeqList<DataType>

::Get(inti){

if(i>=1&&i<=length)returni-1;}時間復雜度？順序表的實現——按值查找操作接口：intLocate(DataTypex)

2.2線性表的順序存儲結構及實現535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值為12的元素，返回在表中的序號。iii注意序號和下標之間的關系template<classDataType>intSeqList<DataType>

::Locate(DataTypex){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}2.2線性表的順序存儲結構及實現順序表的實現——按值查找算法描述：時間復雜度？順序表的優(yōu)缺點順序表的優(yōu)點：⑴無需為表示表中元素之間的邏輯關系而增加額外的存儲空間；⑵隨機存取：可以快速地存取表中任一位置的元素。

順序表的缺點：⑴插入和刪除操作需要移動大量元素；⑵表的容量難以確定，表的容量難以擴充；⑶造成存儲空間的碎片。

2.2線性表的順序存儲結構及實現單鏈表：線性表的鏈接存儲結構。存儲思想：用一組任意的存儲單元存放線性表的元素。2.3線性表的鏈接存儲結構及實現單鏈表靜態(tài)存儲分配順序表事先確定容量鏈表動態(tài)存儲分配運行時分配空間連續(xù)不連續(xù)零散分布0200020803000325…………存儲特點：邏輯次序和物理次序不一定相同。

2.元素之間的邏輯關系用指針表示。2.3線性表的鏈接存儲結構及實現例：(a1,a2

,a3,a4)的存儲示意圖單鏈表a10200a20325a30300a4∧2.3線性表的鏈接存儲結構及實現單鏈表0200020803000325…………a10200a20325a30300a4∧結點數據域指針域單鏈表是由若干結點構成的；單鏈表的結點只有一個指針域。data：存儲數據元素next：存儲指向后繼結點的地址datanext單鏈表的結點結構：數據域指針域template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3線性表的鏈接存儲結構及實現單鏈表datanext單鏈表的結點結構：如何申請一個結點？s=newNode<int>;template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3線性表的鏈接存儲結構及實現單鏈表datanext單鏈表的結點結構：……sNodes=newNode<int>;2.3線性表的鏈接存儲結構及實現單鏈表datanext……sNode如何引用數據元素？s->data;*s.data;data如何引用指針域？nexts->next;2.3線性表的鏈接存儲結構及實現單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表重點在數據元素之間的邏輯關系的表示，所以，將實際存儲地址抽象。什么是存儲結構？2.3線性表的鏈接存儲結構及實現單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表頭指針：指向第一個結點的地址。尾標志：終端結點的指針域為空。2.3線性表的鏈接存儲結構及實現單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不統一，缺點？如何將空表與非空表統一？頭結點：在單鏈表的第以一個元素結點之前附設一個類型相同的結點，以便空表和非空表處理統一。2.3線性表的鏈接存儲結構及實現單鏈表非空表firsta1a2an∧空表first∧template<classDataType>classLinkList{public:LinkList()；LinkList(DataTypea[],intn);~LinkList();intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);voidPrintList();private:Node<DataType>*first;};單鏈表類的聲明2.3線性表的鏈接存儲結構及實現單鏈表的實現——遍歷操作操作接口：

voidPrintList();核心操作（關鍵操作）：工作指針后移。從頭結點（或開始結點）出發(fā)，通過工作指針的反復后移而將整個單鏈表“審視”一遍的方法稱為掃描（或遍歷）。2.3線性表的鏈接存儲結構及實現firsta1pa2pan∧aippp單鏈表的實現——遍歷操作操作接口：

voidPrintList();2.3線性表的鏈接存儲結構及實現template<classDataType>voidLinkList<DataType>::PrintList(){p=first->next;while(p!=NULL){cout<<p->data;p=p->next;}}p++能否完成指針后移？a1a2pp++p->next單鏈表的實現——按位查找操作接口：

DataTypeGet(inti);2.3線性表的鏈接存儲結構及實現firsta1a2an∧aipp查找失敗1.工作指針p初始化;累加器count初始化;2.重復執(zhí)行下述操作，直到p為空：

2.1工作指針p后移;2.2count++;3.返回累加器count的值；pcount=1pcount=2p查找成功count=itemplate<classDataType>intLinkList<DataType>::Length(){p=first->next;count=0;while(p!=NULL){p=p->next;count++;}returncount;//注意count的初始化和返回值之間的關系}2.3線性表的鏈接存儲結構及實現單鏈表的實現——按位查找算法描述——C++描述template<classDataType>intLinkList<DataType>::Locate(DataTypex){p=first->next;count=1;

while(p!=NULL){if(p->data==x)returncount;//查找成功，返回序號p=p->next;count++;}return0;//退出循環(huán)表明查找失敗}2.3線性表的鏈接存儲結構及實現單鏈表的實現——按值查找算法描述——C++描述單鏈表的實現———插入操作接口：

voidInsert(inti,DataTypex);

2.3線性表的鏈接存儲結構及實現如何實現結點ai-1、x和ai之間邏輯關系的變化？pxsfirsta1ai-1an∧ai算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;注意分析邊界情況——表頭、表尾。

單鏈表的實現———插入2.3線性表的鏈接存儲結構及實現firsta1an∧aipxs算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;pxs∧由于單鏈表帶頭結點，表頭、表中、表尾三種情況的操作語句一致。

算法描述——偽代碼

1.工作指針p初始化；

2.查找第i-1個結點并使工作指針p指向該結點；

3.若查找不成功，則插入位置不合理，拋出插入位置異常；否則，3.1生成一個元素值為x的新結點s；

3.2將新結點s插入到結點p之后；2.3線性表的鏈接存儲結構及實現單鏈表的實現———插入

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;//工作指針p應指向頭結點

while(p!=NULL&&count<i-1){//查找第i–1個結點p=p->next;

count++;}if(p==NULL)throw"位置";//沒有找到第i–1個結點

else{s=newNode;s->data=x;//申請一個結點ss->next=p->next;p->next=s;//結點s插入結點p之后

}}2.3線性表的鏈接存儲結構及實現單鏈表的實現———插入基本語句？時間復雜度？單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結點插在頭結點的后面。算法描述：first=newNode<DataType>;first->next=NULL;2.3線性表的鏈接存儲結構及實現數組a3512243342初始化first∧單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結點插在頭結點的后面。2.3線性表的鏈接存儲結構及實現數組a3512243342算法描述：s=newNode<DataType>;s->data=a[0];s->next=first->next;first->next=s;插入第一個元素結點first∧35s∧單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)頭插法：將待插入結點插在頭結點的后面。2.3線性表的鏈接存儲結構及實現數組a3512243342算法描述：s=newNode<DataType>;s->data=a[1];s->next=first->next;first->next=s;依次插入每一個結點12sfirst35∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode;first->next=NULL;for(i=0;i<n;i++){s=newNode;s->data=a[i];

s->next=first->next;first->next=s;}}2.3線性表的鏈接存儲結構及實現單鏈表的實現———構造函數尾插法：將待插入結點插在終端結點的后面。

2.3線性表的鏈接存儲結構及實現單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)算法描述：first=newNode<DataType>;rear=first;數組a3512243342初始化firstrear尾插法：將待插入結點插在終端結點的后面。

2.3線性表的鏈接存儲結構及實現單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)算法描述：s=newNode<DataType>;s->data=a[0];rear->next=s;rear=s;數組a3512243342插入第一個元素結點firstrear35srear尾插法：將待插入結點插在終端結點的后面。

2.3線性表的鏈接存儲結構及實現單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)算法描述：s=newNode<DataType>;s->data=a[1];rear->next=s;rear=s;數組a3512243342依次插入每一個結點first35rear12srear尾插法：將待插入結點插在終端結點的后面。

2.3線性表的鏈接存儲結構及實現單鏈表的實現———構造函數操作接口：LinkList(DataTypea[],intn)算法描述：rear->next=NULL;數組a3512243342最后一個結點插入后first3542srear∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode;//生成頭結點

r=first;//尾指針初始化for(i=0;i<n;i++){s=newNode;s->data=a[i];

r->next=s;r=s;}r->next=NULL;}2.3線性表的鏈接存儲結構及實現單鏈表的實現———構造函數算法描述：單鏈表的實現———刪除操作接口：

DataTypeDelete(inti);

2.3線性表的鏈接存儲結構及實現p如何實現結點ai-1和ai之間邏輯關系的變化？firsta1ai-1ai+1ai算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;q單鏈表的實現———刪除2.3線性表的鏈接存儲結構及實現算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;注意分析邊界情況——表頭、表尾。

pqpq表尾的特殊情況：雖然被刪結點不存在，但其前驅結點卻存在。p->next=NULLfirsta1ana2∧算法描述——偽代碼1.工作指針p初始化；2.查找第i-1個結點并使工作指針p指向該結點；3.若p不存在或p不存在后繼結點，則拋出位置異常；否則，3.1暫存被刪結點和被刪元素值；3.2摘鏈，將結點p的后繼結點從鏈表上摘下；3.3釋放被刪結點；3.4返回被刪元素值；

2.3線性表的鏈接存儲結構及實現單鏈表的實現———刪除template<classDataType>DataTypeLinkList<DataType>::Delete(inti){p=first;count=0;

while(p!=NULL&&count<i-1){p=p->next;count++;}if(p==NULL||p->next==NULL)

throw"位置";else{q=p->next;x=q->data;p->next=q->next;deleteq;returnx;}}2.3線性表的鏈接存儲結構及實現單鏈表的實現———刪除單鏈表的實現——析構函數析構函數將單鏈表中所有結點的存儲空間釋放。

2.3線性表的鏈接存儲結構及實現操作接口：~LinkList();firsta1a2an∧aiq算法描述：q=first;first=first->next;deleteq;first注意：保證鏈表未處理的部分不斷開

單鏈表的實現——析構函數template<classDataType>LinkList<DataType>::~LinkList(){while(first!=NULL){q=first;

first=first->next;

deleteq;}}2.3線性表的鏈接存儲結構及實現算法描述：啟示：算法設計的一般過程算法設計的一般步驟：第一步：確定入口（已知條件）、出口（結果）；第二步：根據一個小實例畫出示意圖；第三步：①正向思維：選定一個思考問題的起點，逐步提出問題、解決問題；②逆向思維：從結論出發(fā)分析為達到這個結論應該先有什么；③正逆結合；第四步：寫出頂層較抽象算法，分析邊界情況；第五步：驗證第四步的算法；第六步：寫出具體算法；第七步：進一步驗證，手工運行。循環(huán)鏈表firsta1ai-1an∧aip從單鏈表中某結點p出發(fā)如何找到其前驅？將單鏈表的首尾相接，將終端結點的指針域由空指針改為指向頭結點，構成單循環(huán)鏈表，簡稱循環(huán)鏈表。2.3線性表的鏈接存儲結構及實現循環(huán)鏈表空表和非空表的處理一致附設頭結點first空循環(huán)鏈表firsta1ai-1anai非空循環(huán)鏈表2.3線性表的鏈接存儲結構及實現firsta1ai-1anai循環(huán)鏈表——插入xspxspxsp算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;2.3線性表的鏈接存儲結構及實現

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;

while(p!=first&&count<i-1){p=p->next;count++;}if(p==NULL)throw"位置";else{s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;}}循環(huán)鏈表——插入與單鏈表的插入操作相比，差別是什么？2.3線性表的鏈接存儲結構及實現循環(huán)條件：p!=NULLp!=firstp->next!=NULLp->next!=first循環(huán)鏈表循環(huán)鏈表中沒有明顯的尾端如何避免死循環(huán)2.3線性表的鏈接存儲結構及實現如何查找開始結點和終端結點？循環(huán)鏈表firsta1ai-1anai開始結點：first->next終端結點：將單鏈表掃描一遍，時間為O(n)2.3線性表的鏈接存儲結構及實現reara1ai-1anai開始結點：rear->next->next終端結點：rear循環(huán)鏈表帶尾指針的循環(huán)鏈表一個存儲結構設計得是否合理，取決于基于該存儲結構的運算是否方便，時間性能是否提高。2.3線性表的鏈接存儲結構及實現雙鏈表如何求結點p的直接前驅，時間性能？firsta1ai-1anaip為什么可以快速求得結點p的后繼？如何快速求得結點p的前驅？2.3線性表的鏈接存儲結構及實現雙鏈表：在單鏈表的每個結點中再設置一個指向其前驅結點的指針域。雙鏈表結點結構：priordatanextdata：數據域，存儲數據元素；prior：指針域，存儲該結點的前趨結點地址；next：指針域，存儲該結點的后繼結點地址。2.3線性表的鏈接存儲結構及實現template<classDataType>structDulNode{DataTypedata;DulNode<DataType>*prior,*next;};

雙鏈表啟示？時空權衡——空間換取時間priordatanext定義結點結構：2.3線性表的鏈接存儲結構及實現雙鏈表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;ai-1ai操作接口：

voidInsert(DulNode<DataType>*p,DataTypex);

pxs注意指針修改的相對順序2.3線性表的鏈接存儲結構及實現雙鏈表的操作——刪除(p->prior)->next=p->next;

(p->next)->prior=p->prior;

操作接口：

DataTypeDelete(DulNode<DataType>*p);

ai-1aipai結點p的指針是否需要修改？deletep;2.3線性表的鏈接存儲結構及實現存儲分配方式比較順序表采用順序存儲結構，即用一段地址連續(xù)的存儲單元依次存儲線性表的數據元素，數據元素之間的邏輯關系通過存儲位置來實現。鏈表采用鏈接存儲結構，即用一組任意的存儲單元存放線性表的元素，用指針來反映數據元素之間的邏輯關系。2.4順序表和鏈表的比較2.4順序表和鏈表的比較時間性能比較

時間性能是指實現基于某種存儲結構的基本操作（即算法）的時間復雜度。

按位查找：順序表的時間為Ｏ(1)，是隨機存取；鏈表的時間為Ｏ(n)，是順序存取。插入和刪除：順序表需移動表長一半的元素，時間為Ｏ(n)；鏈表不需要移動元素，在給出某個合適位置的指針后，插入和刪除操作所需的時間僅為Ｏ(1)。2.4順序表和鏈表的比較空間性能比較

空間性能是指某種存儲結構所占用的存儲空間的大小。

定義結點的存儲密度：數據域占用的存儲量整個結點占用的存儲量存儲密度＝結點的存儲密度：順序表：結點的存儲密度為1（只存儲數據元素），沒有浪費空間；鏈表：結點的存儲密度<1（包括數據域和指針域），有指針的結構性開銷。2.4順序表和鏈表的比較空間性能比較

空間性能是指某種存儲結構所占用的存儲空間的大小。

定義結點的存儲密度：數據域占用的存儲量整個結點占用的存儲量存儲密度＝結構的存儲密度：順序表：需要預分配存儲空間，如果預分配得過大，造成浪費，若估計得過小，又將發(fā)生上溢；鏈表：不需要預分配空間，只要有內存空間可以分配，單鏈表中的元素個數就沒有限制。結論⑴若線性表需頻繁查找卻很少進行插入和刪除操作，或其操作和元素在表中的位置密切相關時，宜采用順序表作為存儲結構；若線性表需頻繁插入和刪除時，則宜采用鏈表做存儲結構。⑵當線性表中元素個數變化較大或者未知時，最好使用鏈表實現；而如果用戶事先知道線性表的大致長度，使用順序表的空間效率會更高。2.4順序表和鏈表的比較總之，線性表的順序實現和鏈表實現各有其優(yōu)缺點，不能籠統地說哪種實現更好，只能根據實際問題的具體需要，并對各方面的優(yōu)缺點加以綜合平衡，才能最終選定比較適宜的實現方法。靜態(tài)鏈表：用數組來表示單鏈表，用數組元素的下標來模擬單鏈表的指針。靜態(tài)鏈表2.5線性表的其它存儲方法data：存儲放數據元素；next：也稱游標，存儲該元素的后繼在數組的下標。數組元素（結點）的構成：datanext數據域指針域例：線性表(張，王，李，趙，吳)的靜態(tài)鏈表存儲張2王3李4趙5吳-101234567878-112.5線性表的其它存儲方法datanext靜態(tài)鏈表firstavailfirst：靜態(tài)鏈表頭指針，為了方便插入和刪除操作，通常靜態(tài)鏈表帶頭結點；avail：空閑鏈表頭指針，空閑鏈表由于只在表頭操作，所以不帶頭結點；2.5線性表的其它存儲方法靜態(tài)鏈表靜態(tài)鏈表的存儲結構定義如下：constintMaxSize=100;//100只是示例數據template<classDataType>structSNode{DataTypedata;//DataType表示不確定的數據類型

intnext;//指針域（也稱游標）}SList[MaxSize];在線性表(張，王，李，趙，吳)中“王”之后插入“孫”張2王3李4趙5吳-101234567878-112.5線性表的其它存儲方法datanext靜態(tài)鏈表張2王

6李4趙5吳-1012345678孫

38-11datanext王之后插入孫2.5線性表的其它存儲方法靜態(tài)鏈表假設結點s插在結點p之后，則修改指針的操作為：

s=avail;