




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
數(shù)據(jù)結(jié)構(gòu)講師:第一章緒論課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的專業(yè)基礎(chǔ)課
公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課在教學(xué)計劃中的地位:核心、承上啟下
前導(dǎo)課:高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計語言后續(xù)課:數(shù)據(jù)庫、操作系統(tǒng)、編譯原理……屬于武術(shù)中的“練功”科目
“練武不練功,到頭一場空”考研:專業(yè)課必考教學(xué)目標(biāo)掌握基本的數(shù)據(jù)結(jié)構(gòu)
工具箱→復(fù)用、修改、重組培養(yǎng)算法設(shè)計能力、程序設(shè)計能力
算法——程序的靈魂問題求解過程:問題→想法→算法→程序程序設(shè)計研究的層次:算法→方法學(xué)→語言→工具培養(yǎng)算法分析能力
評價算法、改進(jìn)算法學(xué)編程的境界學(xué)會寫程序?qū)W會高效地寫程序?qū)W會寫高效的程序?qū)W會設(shè)計算法學(xué)會設(shè)計有用的算法
學(xué)習(xí)要求循序漸進(jìn),切忌心浮氣躁提高課外學(xué)習(xí)的時間和內(nèi)容理解科學(xué)而不是背誦科學(xué)→讀書正確對待考試作習(xí)題
華羅庚:“學(xué)數(shù)學(xué)不做習(xí)題等于入寶山而空返”
作實驗
計算機學(xué)科是一門科學(xué)性與工程性并重的學(xué)科,表現(xiàn)為理論和實踐緊密結(jié)合的特征。
第1章緒論數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用本書討論的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念算法及算法分析本章的基本內(nèi)容是:1938年出生,25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系,博士畢業(yè)后留校任教,28歲任副教授。30歲時,加盟斯坦福大學(xué)計算機系,任教授。從31歲起,開始出版他的歷史性經(jīng)典巨著:TheArtofComputerProgramming,他計劃共寫7卷,然而出版三卷之后,已震驚世界,使他獲得計算機科學(xué)界的最高榮譽——圖靈獎,此時,他年僅36歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努思1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用程序設(shè)計的實質(zhì)是什么?數(shù)據(jù)表示:將數(shù)據(jù)存儲在計算機(內(nèi)存)中數(shù)據(jù)處理:處理數(shù)據(jù),設(shè)計方案(算法)數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計
1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用利用計算機求解問題的一般過程?計算機不能分析問題并產(chǎn)生問題的解決方案,必須由人來分析問題,確定問題的解決方案,編寫程序,然后讓計算機執(zhí)行程序最終獲得問題的解。1.1數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的作用例1-1手機電話號碼查詢問題將電話號碼集合組織成線性結(jié)構(gòu)和樹結(jié)構(gòu),查找操作的效率不同,當(dāng)數(shù)據(jù)量較大時差別就更大。1.2本書討論的主要內(nèi)容計算機求解問題:
問題→抽象出問題的模型→求模型的解問題——數(shù)值問題、非數(shù)值問題數(shù)值問題→數(shù)學(xué)方程非數(shù)值問題→數(shù)據(jù)結(jié)構(gòu)例1-2學(xué)籍管理問題完成什么功能?各表項之間是什么關(guān)系?1.2本書討論的主要內(nèi)容例1-3人——機對弈問題如何實現(xiàn)對弈?各格局之間是什么關(guān)系?1.2本書討論的主要內(nèi)容例1-4七巧板涂色問題
如何表示區(qū)域之間的鄰接關(guān)系?1.2本書討論的主要內(nèi)容本書討論非數(shù)值問題的數(shù)據(jù)組織和處理,主要內(nèi)容如下:(1)數(shù)據(jù)的邏輯結(jié)構(gòu):線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu),其核心是如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系;(2)數(shù)據(jù)的存儲結(jié)構(gòu):如何將線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)存儲到計算機的存儲器中,其核心是如何有效地存儲數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系;(3)算法:如何基于數(shù)據(jù)的某種存儲結(jié)構(gòu)實現(xiàn)插入、刪除、查找等基本操作,其核心是如何有效地處理數(shù)據(jù);(4)常用數(shù)據(jù)處理技術(shù):查找技術(shù)、排序技術(shù)、索引技術(shù)等。1.2本書討論的主要內(nèi)容1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù):所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。數(shù)值數(shù)據(jù):整數(shù)、實數(shù)等非數(shù)值數(shù)據(jù):圖形、圖象、聲音、文字等數(shù)據(jù)元素:數(shù)據(jù)的基本單位,在計算機程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)項:構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)結(jié)構(gòu)的基本概念學(xué)號姓名性別出生日期政治面貌0001陸宇男1986/09/02團員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團員數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項之間的關(guān)系包含關(guān)系:數(shù)據(jù)由數(shù)據(jù)元素組成,數(shù)據(jù)元素由數(shù)據(jù)項組成。數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位,其中的數(shù)據(jù)項一般不予考慮。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素關(guān)系數(shù)據(jù)結(jié)構(gòu):相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同,數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu):指數(shù)據(jù)元素之間邏輯關(guān)系的整體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念關(guān)聯(lián)方式或鄰接關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型學(xué)籍管理問題中,表項之間的邏輯關(guān)系指的是什么?人機對弈問題中,格局之間的邏輯關(guān)系指的是什么?教學(xué)計劃編排問題中,課程之間的邏輯關(guān)系指的是什么?數(shù)據(jù)結(jié)構(gòu):相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同,數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu):指數(shù)據(jù)元素之間邏輯關(guān)系的整體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)在形式上可定義為一個二元組:Data_Structure=(D,R)其中D是數(shù)據(jù)元素的有限集合,R是D上關(guān)系的集合。數(shù)據(jù)結(jié)構(gòu):相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同,數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu):指數(shù)據(jù)元素之間邏輯關(guān)系的整體。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念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>}數(shù)據(jù)結(jié)構(gòu):相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同,數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。邏輯結(jié)構(gòu):指數(shù)據(jù)元素之間邏輯關(guān)系的整體。存儲結(jié)構(gòu):又稱為物理結(jié)構(gòu),是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念內(nèi)存存儲結(jié)構(gòu)實質(zhì)上是內(nèi)存分配,在具體實現(xiàn)時依賴于計算機語言。數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類:⑴集合:數(shù)據(jù)元素之間就是“屬于同一個集合”;1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類:⑴集合:數(shù)據(jù)元素之間就是“屬于同一個集合”;⑵線性結(jié)構(gòu):數(shù)據(jù)元素之間存在著一對一的線性關(guān)系;1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類:⑴集合:數(shù)據(jù)元素之間就是“屬于同一個集合”;⑵線性結(jié)構(gòu):數(shù)據(jù)元素之間存在著一對一的線性關(guān)系;⑶樹結(jié)構(gòu):數(shù)據(jù)元素之間存在著一對多的層次關(guān)系;1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)從邏輯上分為四類:⑴集合:數(shù)據(jù)元素之間就是“屬于同一個集合”;⑵線性結(jié)構(gòu):數(shù)據(jù)元素之間存在著一對一的線性關(guān)系;⑶樹結(jié)構(gòu):數(shù)據(jù)元素之間存在著一對多的層次關(guān)系;⑷圖結(jié)構(gòu):數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲結(jié)構(gòu):1.順序存儲結(jié)構(gòu):用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素,數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示。…batcateat…起始地址例:(bat,cat,eat)1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念通常有兩種存儲結(jié)構(gòu):1.順序存儲結(jié)構(gòu):用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素,數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示。2.鏈接存儲結(jié)構(gòu):用一組任意的存儲單元存儲數(shù)據(jù)元素,數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。例:(bat,cat,eat)1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念0200020803000325…………bat0200cat0325eat∧邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖,是面向問題的,反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式;數(shù)據(jù)的存儲結(jié)構(gòu)屬于具體實現(xiàn)的視圖,是面向計算機的。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲,而采用不同的存儲結(jié)構(gòu),其數(shù)據(jù)處理的效率往往是不同的。
1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型1.數(shù)據(jù)類型(DataType):一組值的集合以及定義于這個值集上的一組操作的總稱。
例如:C++中的整型變量
2.抽象(Abstract):抽出問題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)。
例如:地圖、駕駛汽車3.抽象數(shù)據(jù)類型(AbstractDataType,ADT):一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。1.3數(shù)據(jù)結(jié)構(gòu)的基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型在設(shè)計ADT時,把ADT的定義、設(shè)計和實現(xiàn)分開來。定義部分只包含數(shù)據(jù)的邏輯結(jié)構(gòu)和所允許的操作集合,一方面,ADT的使用者依據(jù)這些定義來使用ADT,即通過操作集合對該ADT進(jìn)行操作;另一方面,ADT的實現(xiàn)者依據(jù)這些定義來完成該ADT各種操作的具體實現(xiàn)。ADT抽象數(shù)據(jù)類型名Data數(shù)據(jù)元素之間邏輯關(guān)系的定義Operation
操作1
前置條件:執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài)
輸入:執(zhí)行此操作所需要的輸入
功能:該操作將完成的功能
輸出:執(zhí)行該操作后產(chǎn)生的輸出
后置條件:執(zhí)行該操作后數(shù)據(jù)的狀態(tài)操作2
…………操作n……endADT
1.3數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型1.3數(shù)據(jù)結(jié)構(gòu)的基本概念(小結(jié))數(shù)據(jù)的操作:插入、刪除、修改、檢索、排序等數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)順序存儲鏈?zhǔn)酱鎯暇€性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)非數(shù)值問題數(shù)據(jù)表示算法的相關(guān)概念1.算法(Algorithm):是對特定問題求解步驟的一種描述,是指令的有限序列。2.
算法的五大特性:⑴
輸入:一個算法有零個或多個輸入。⑵輸出:一個算法有一個或多個輸出。⑶有窮性:一個算法必須總是在執(zhí)行有窮步之后結(jié)束,且每一步都在有窮時間內(nèi)完成。⑷確定性:算法中的每一條指令必須有確切的含義,對于相同的輸入只能得到相同的輸出。⑸可行性:算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。1.4算法及算法分析
歐幾里德算法(有窮性、確定性、可行性)mnr例:歐幾里德算法——輾轉(zhuǎn)相除法求兩個自然數(shù)m
和n
的最大公約數(shù)1.4算法及算法分析算法的描述方法——自然語言優(yōu)點:容易理解缺點:冗長、二義性使用方法:粗線條描述算法思想
注意事項:避免寫成自然段1.4算法及算法分析步驟1:將m除以n得到余數(shù)r;步驟2:若r等于0,則n為最大公約數(shù),算法結(jié)束;否則執(zhí)行步驟3;步驟3:將n的值放在m中,將r的值放在n中,重新執(zhí)行步驟1;例:歐幾里德算法自然語言1.4算法及算法分析優(yōu)點:流程直觀缺點:缺少嚴(yán)密性、靈活性使用方法:描述簡單算法注意事項:注意抽象層次算法的描述方法——流程圖1.4算法及算法分析N開始輸入m和n
r=m%nr=0m=n;n=r輸出n結(jié)束Y流程圖例:歐幾里德算法1.4算法及算法分析優(yōu)點:能由計算機執(zhí)行缺點:抽象性差,對語言要求高使用方法:算法需要驗證注意事項:將算法寫成子函數(shù)算法的描述方法——程序設(shè)計語言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;}程序設(shè)計語言例:歐幾里德算法1.4算法及算法分析偽代碼(Pseudocode):介于自然語言和程序設(shè)計語言之間的方法,它采用某一程序設(shè)計語言的基本語法,操作指令可以結(jié)合自然語言來設(shè)計。優(yōu)點:表達(dá)能力強,抽象性強,容易理解使用方法: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++的函數(shù)來描述。例:歐幾里德算法1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}1.4算法及算法分析對C++語言進(jìn)行了如下簡化:⑴局部變量可以不聲明;⑵寫出子函數(shù)即可,子函數(shù)不用在主函數(shù)中調(diào)用,省略主函數(shù);⑶所有的包含函數(shù)(頭函數(shù).h)可以省略;⑷交換兩個變量的語句可以簡寫為a←→b。算法分析度量算法效率的方法:
事后統(tǒng)計:將算法實現(xiàn),測算其時間和空間開銷。
缺點:⑴編寫程序?qū)崿F(xiàn)算法將花費較多的時間和精力;⑵所得實驗結(jié)果依賴于計算機的軟硬件等環(huán)境因素。
事前分析:對算法所消耗資源的一種估算方法。1.4算法及算法分析算法分析算法分析(AlgorithmAnalysis):對算法所需要的計算機資源——時間和空間進(jìn)行估算。時間復(fù)雜性(TimeComplexity)空間復(fù)雜性(SpaceComplexity)1.4算法及算法分析算法的時間復(fù)雜度分析1.4算法及算法分析算法分析算法的執(zhí)行時間=每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間指令系統(tǒng)、編譯的代碼質(zhì)量單位時間每條語句執(zhí)行次數(shù)之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語句的執(zhí)行次數(shù)問題規(guī)模:輸入量的多少?;菊Z句:是執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的操作指令。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問題規(guī)模:n基本語句:x++1.4算法及算法分析算法分析定義
若存在兩個正的常數(shù)c和n0,對于任意n≥n0,都有T(n)≤c×f(n),則稱T(n)=O(f(n))。n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×f(n)當(dāng)問題規(guī)模充分大時在漸近意義下的階。1.4算法及算法分析算法分析——大O符號定理:若A(n)=amnm+am-1nm-1++a1n+a0是一個m次多項式,則A(n)=O(nm)。說明:在計算算法時間復(fù)雜度時,可以忽略所有低次冪和最高次冪的系數(shù)。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算法及算法分析算法分析最好情況、最壞情況、平均情況例:在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素(假設(shè)該數(shù)組中有且僅有一個元素值為k)。
intFind(intA[],intn)
{for(i=0;i<n;i++)if(A[i]==k)break;returni; }1.4算法及算法分析基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關(guān)?最好情況:出現(xiàn)概率較大時分析最差情況:實時系統(tǒng)平均情況:已知輸入數(shù)據(jù)是如何分布的,通常假設(shè)等概率分布結(jié)論:如果問題規(guī)模相同,時間代價與輸入數(shù)據(jù)有關(guān),則需要分析最好情況、最壞情況、平均情況。1.4算法及算法分析最好情況、最壞情況、平均情況本章小結(jié)——知識結(jié)構(gòu)圖緒論數(shù)據(jù)結(jié)構(gòu)算法基本概念邏輯結(jié)構(gòu)存儲結(jié)構(gòu)⑴數(shù)據(jù)⑵數(shù)據(jù)元素⑶數(shù)據(jù)對象⑷ADT⑴邏輯結(jié)構(gòu)⑵數(shù)據(jù)結(jié)構(gòu)的分類⑴存儲結(jié)構(gòu)⑵常用存儲方法基本概念算法分析⑴算法⑵算法特性⑶評價算法⑷描述算法⑴問題規(guī)模⑵基本語句⑶時間復(fù)雜度⑷大O記號關(guān)系第二章線性表本章的基本內(nèi)容
線性表的邏輯結(jié)構(gòu)
線性表的順序存儲及實現(xiàn)
線性表的鏈接存儲及實現(xiàn)
順序表和鏈表的比較
線性表的其他存儲方法2.1線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么?2.1線性表的邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系是什么?現(xiàn)實生活中,許多問題抽象出的數(shù)據(jù)模型是線性表,如何存儲這種線性結(jié)構(gòu)并實現(xiàn)插入、刪除、查找等基本操作呢?線性表:簡稱表,是n(n≥0)個具有相同類型的數(shù)據(jù)元素的有限序列。線性表的長度:線性表中數(shù)據(jù)元素的個數(shù)??毡恚洪L度等于零的線性表,記為:L=()。非空表記為:L=(a1,a2,…,ai-1,ai,…,an)2.1線性表的邏輯結(jié)構(gòu)線性表的定義其中,ai(1≤i≤n)稱為數(shù)據(jù)元素;下角標(biāo)i表示該元素在線性表中的位置或序號。a1a3a4ana22.1線性表的邏輯結(jié)構(gòu)線性表的特性1.有限性:線性表中數(shù)據(jù)元素的個數(shù)是有窮的。2.相同性:線性表中數(shù)據(jù)元素的類型是同一的。3.順序性:線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1,ai),即ai-1是ai的前驅(qū),ai是ai-1的后繼;a1無前驅(qū),an無后繼,其它每個元素有且僅有一個前驅(qū)和一個后繼。
線性表的抽象數(shù)據(jù)類型定義ADTListData
線性表中的數(shù)據(jù)元素具有相同類型,相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitList
前置條件:表不存在輸入:無
功能:表的初始化輸出:無
后置條件:建一個空表2.1線性表的邏輯結(jié)構(gòu)DestroyList
前置條件:表已存在
輸入:無
功能:銷毀表
輸出:無
后置條件:釋放表所占用的存儲空間Length
前置條件:表已存在
輸入:無
功能:求表的長度
輸出:表中數(shù)據(jù)元素的個數(shù)
后置條件:表不變2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Get
前置條件:表已存在
輸入:元素的序號i
功能:在表中取序號為i的數(shù)據(jù)元素
輸出:若i合法,返回序號為i的元素值,否則拋出異常
后置條件:表不變Locate
前置條件:表已存在
輸入:數(shù)據(jù)元素x
功能:在線性表中查找值等于x的元素
輸出:若查找成功,返回x在表中的序號,否則返回0
后置條件:表不變2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Insert
前置條件:表已存在
輸入:插入i;待插x
功能:在表的第i個位置處插入一個新元素x
輸出:若插入不成功,拋出異常
后置條件:若插入成功,表中增加一個新元素Delete
前置條件:表已存在
輸入:刪除位置i
功能:刪除表中的第i個元素
輸出:若刪除成功,返回被刪元素,否則拋出異常
后置條件:若刪除成功,表中減少一個元素2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義Empty
前置條件:表已存在
輸入:無
功能:判斷表是否為空
輸出:若是空表,返回1,否則返回0
后置條件:表不變ADT進(jìn)一步說明:(1)線性表的基本操作根據(jù)實際應(yīng)用是而定;(2)復(fù)雜的操作可以通過基本操作的組合來實現(xiàn);(3)對不同的應(yīng)用,操作的接口可能不同。2.1線性表的邏輯結(jié)構(gòu)線性表的抽象數(shù)據(jù)類型定義2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表——線性表的順序存儲結(jié)構(gòu)例:(34,23,67,43)342367434存儲要點用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表——線性表的順序存儲結(jié)構(gòu)例:(34,23,67,43)34236743存儲空間的起始位置4用什么屬性來描述順序表?順序表的容量(最大長度)順序表的當(dāng)前長度2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表——線性表的順序存儲結(jié)構(gòu)例:(34,23,67,43)342367434如何實現(xiàn)順序表的內(nèi)存分配?順序表一維數(shù)組0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表一般情況下,(a1,a2,…,ai-1,ai,…,an)的順序存儲:數(shù)組的長度Max線性表的長度Length數(shù)組的長度大于等于當(dāng)前線性表的長度如何求得任意元素的存儲地址?0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑長度2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表一般情況下,(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)時間內(nèi)存取數(shù)據(jù)元素2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表一般情況下,(a1,a2,…,ai-1,ai,…,an)的順序存儲:cLoc(ai)Loc(a1)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)存儲結(jié)構(gòu)是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計算機中的表示;存取結(jié)構(gòu)是在一個數(shù)據(jù)結(jié)構(gòu)上對查找操作的時間性能的一種描述。存儲結(jié)構(gòu)和存取結(jié)構(gòu)“順序表是一種隨機存取的存儲結(jié)構(gòu)”的含義為:在順序表這種存儲結(jié)構(gòu)上進(jìn)行的查找操作,其時間性能為O(1)。順序表類的聲明constintMaxSize=100;template<classDataType>//模板類classSeqList{public:SeqList();//構(gòu)造函數(shù)
SeqList(DataTypea[],intn);~SeqList();//析構(gòu)函數(shù)intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:DataTypedata[MaxSize];intlength;};2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)操作接口:SeqList()
算法描述:SeqList<DataType>
::SeqList(){length=0;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——無參構(gòu)造函數(shù)
datalength0操作接口:SeqList(DataTypea[],intn)順序表的實現(xiàn)——有參構(gòu)造函數(shù)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表
數(shù)組a351224334253512243342template<classDataType>SeqList<DataType>
::SeqList(DataTypea[],intn){if(n>MaxSize)throw"參數(shù)非法";
for(i=0;i<n;i++)
data[i]=a[i];length=n;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——有參構(gòu)造函數(shù)算法描述:操作接口:voidInsert(inti,DataTypex)插入前:(a1,…,ai-1,ai,…,an)插入后:(a1,…,ai-1,x
,ai,…,an)順序表的實現(xiàn)——插入2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化33例:(35,12,24,42),在i=2的位置上插入33。表滿:length>=MaxSize合理的插入位置:1≤i≤length+1(i指的是元素的序號)2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——插入435122442a1a2a3a401234422412335什么時候不能插入?注意邊界條件1.如果表滿了,則拋出上溢異常;2.如果元素的插入位置不合理,則拋出位置異常;3.將最后一個元素至第i個元素分別向后移動一個位置;4.將元素x填入位置i處;5.表長加1;算法描述——偽代碼2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——插入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線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——插入基本語句?最好情況(i=n+1):基本語句執(zhí)行0次,時間復(fù)雜度為O(1)。最壞情況(i=1):基本語句執(zhí)行n+1次,時間復(fù)雜度為O(n)。平均情況(1≤i≤n+1):時間復(fù)雜度為O(n)。時間性能分析2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——插入?+-+=11)=1(niiinp?+-++=11)=1(11niinn2n=O(n)操作接口:DataTypeDelete(inti)刪除前:(a1,…,ai-1,ai,ai+1,…,an)刪除后:(a1,…,ai-1,ai+1,…,an)
順序表的實現(xiàn)——刪除2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化例:(35,33,12,24,42),刪除i=2的數(shù)據(jù)元素。仿照順序表的插入操作,完成:1.分析邊界條件;2.分別給出偽代碼和C++描述的算法;3.分析時間復(fù)雜度。2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——刪除535a1a2a3a401234422412334a5122442順序表的實現(xiàn)——按位查找操作接口:DataTypeGet(inti)
2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)0…i-2i-1…n-1Max-1a1…ai-1ai…an空閑
n算法描述:template<classDataType>DataTypeSeqList<DataType>
::Get(inti){
if(i>=1&&i<=length)returni-1;}時間復(fù)雜度?順序表的實現(xiàn)——按值查找操作接口:intLocate(DataTypex)
2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)535a1a2a3a40123442241233a5例:在(35,33,12,24,42)
中查找值為12的元素,返回在表中的序號。iii注意序號和下標(biāo)之間的關(guān)系template<classDataType>intSeqList<DataType>
::Locate(DataTypex){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)順序表的實現(xiàn)——按值查找算法描述:時間復(fù)雜度?順序表的優(yōu)缺點順序表的優(yōu)點:⑴無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間;⑵隨機存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。
順序表的缺點:⑴插入和刪除操作需要移動大量元素;⑵表的容量難以確定,表的容量難以擴充;⑶造成存儲空間的碎片。
2.2線性表的順序存儲結(jié)構(gòu)及實現(xiàn)單鏈表:線性表的鏈接存儲結(jié)構(gòu)。存儲思想:用一組任意的存儲單元存放線性表的元素。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表靜態(tài)存儲分配順序表事先確定容量鏈表動態(tài)存儲分配運行時分配空間連續(xù)不連續(xù)零散分布0200020803000325…………存儲特點:邏輯次序和物理次序不一定相同。
2.元素之間的邏輯關(guān)系用指針表示。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)例:(a1,a2
,a3,a4)的存儲示意圖單鏈表a10200a20325a30300a4∧2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧結(jié)點數(shù)據(jù)域指針域單鏈表是由若干結(jié)點構(gòu)成的;單鏈表的結(jié)點只有一個指針域。data:存儲數(shù)據(jù)元素next:存儲指向后繼結(jié)點的地址datanext單鏈表的結(jié)點結(jié)構(gòu):數(shù)據(jù)域指針域template<classDataType>structNode{DataTypedata;Node<DataType>*next;};
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表datanext單鏈表的結(jié)點結(jié)構(gòu):如何申請一個結(jié)點?s=newNode<int>;template<classDataType>structNode{DataTypedata;Node<DataType>*next;};
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表datanext單鏈表的結(jié)點結(jié)構(gòu):……sNodes=newNode<int>;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表datanext……sNode如何引用數(shù)據(jù)元素?s->data;*s.data;data如何引用指針域?nexts->next;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表重點在數(shù)據(jù)元素之間的邏輯關(guān)系的表示,所以,將實際存儲地址抽象。什么是存儲結(jié)構(gòu)?2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表頭指針:指向第一個結(jié)點的地址。尾標(biāo)志:終端結(jié)點的指針域為空。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不統(tǒng)一,缺點?如何將空表與非空表統(tǒng)一?頭結(jié)點:在單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點,以便空表和非空表處理統(tǒng)一。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表非空表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線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——遍歷操作操作接口:
voidPrintList();核心操作(關(guān)鍵操作):工作指針后移。從頭結(jié)點(或開始結(jié)點)出發(fā),通過工作指針的反復(fù)后移而將整個單鏈表“審視”一遍的方法稱為掃描(或遍歷)。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1pa2pan∧aippp單鏈表的實現(xiàn)——遍歷操作操作接口:
voidPrintList();2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)template<classDataType>voidLinkList<DataType>::PrintList(){p=first->next;while(p!=NULL){cout<<p->data;p=p->next;}}p++能否完成指針后移?a1a2pp++p->next單鏈表的實現(xiàn)——按位查找操作接口:
DataTypeGet(inti);2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1a2an∧aipp查找失敗1.工作指針p初始化;累加器count初始化;2.重復(fù)執(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的初始化和返回值之間的關(guān)系}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——按位查找算法描述——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線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)——按值查找算法描述——C++描述單鏈表的實現(xiàn)———插入操作接口:
voidInsert(inti,DataTypex);
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)如何實現(xiàn)結(jié)點ai-1、x和ai之間邏輯關(guān)系的變化?pxsfirsta1ai-1an∧ai算法描述:s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;注意分析邊界情況——表頭、表尾。
單鏈表的實現(xiàn)———插入2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1an∧aipxs算法描述:s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;pxs∧由于單鏈表帶頭結(jié)點,表頭、表中、表尾三種情況的操作語句一致。
算法描述——偽代碼
1.工作指針p初始化;
2.查找第i-1個結(jié)點并使工作指針p指向該結(jié)點;
3.若查找不成功,則插入位置不合理,拋出插入位置異常;否則,3.1生成一個元素值為x的新結(jié)點s;
3.2將新結(jié)點s插入到結(jié)點p之后;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———插入
template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;//工作指針p應(yīng)指向頭結(jié)點
while(p!=NULL&&count<i-1){//查找第i–1個結(jié)點p=p->next;
count++;}if(p==NULL)throw"位置";//沒有找到第i–1個結(jié)點
else{s=newNode;s->data=x;//申請一個結(jié)點ss->next=p->next;p->next=s;//結(jié)點s插入結(jié)點p之后
}}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———插入基本語句?時間復(fù)雜度?單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)頭插法:將待插入結(jié)點插在頭結(jié)點的后面。算法描述:first=newNode<DataType>;first->next=NULL;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組a3512243342初始化first∧單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)頭插法:將待插入結(jié)點插在頭結(jié)點的后面。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組a3512243342算法描述:s=newNode<DataType>;s->data=a[0];s->next=first->next;first->next=s;插入第一個元素結(jié)點first∧35s∧單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)頭插法:將待插入結(jié)點插在頭結(jié)點的后面。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)數(shù)組a3512243342算法描述:s=newNode<DataType>;s->data=a[1];s->next=first->next;first->next=s;依次插入每一個結(jié)點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線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)尾插法:將待插入結(jié)點插在終端結(jié)點的后面。
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)算法描述:first=newNode<DataType>;rear=first;數(shù)組a3512243342初始化firstrear尾插法:將待插入結(jié)點插在終端結(jié)點的后面。
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)算法描述:s=newNode<DataType>;s->data=a[0];rear->next=s;rear=s;數(shù)組a3512243342插入第一個元素結(jié)點firstrear35srear尾插法:將待插入結(jié)點插在終端結(jié)點的后面。
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)算法描述:s=newNode<DataType>;s->data=a[1];rear->next=s;rear=s;數(shù)組a3512243342依次插入每一個結(jié)點first35rear12srear尾插法:將待插入結(jié)點插在終端結(jié)點的后面。
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)操作接口:LinkList(DataTypea[],intn)算法描述:rear->next=NULL;數(shù)組a3512243342最后一個結(jié)點插入后first3542srear∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode;//生成頭結(jié)點
r=first;//尾指針初始化for(i=0;i<n;i++){s=newNode;s->data=a[i];
r->next=s;r=s;}r->next=NULL;}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———構(gòu)造函數(shù)算法描述:單鏈表的實現(xiàn)———刪除操作接口:
DataTypeDelete(inti);
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)p如何實現(xiàn)結(jié)點ai-1和ai之間邏輯關(guān)系的變化?firsta1ai-1ai+1ai算法描述:q=p->next;x=q->data;p->next=q->next;deleteq;q單鏈表的實現(xiàn)———刪除2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法描述:q=p->next;x=q->data;p->next=q->next;deleteq;注意分析邊界情況——表頭、表尾。
pqpq表尾的特殊情況:雖然被刪結(jié)點不存在,但其前驅(qū)結(jié)點卻存在。p->next=NULLfirsta1ana2∧算法描述——偽代碼1.工作指針p初始化;2.查找第i-1個結(jié)點并使工作指針p指向該結(jié)點;3.若p不存在或p不存在后繼結(jié)點,則拋出位置異常;否則,3.1暫存被刪結(jié)點和被刪元素值;3.2摘鏈,將結(jié)點p的后繼結(jié)點從鏈表上摘下;3.3釋放被刪結(jié)點;3.4返回被刪元素值;
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———刪除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線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表的實現(xiàn)———刪除單鏈表的實現(xiàn)——析構(gòu)函數(shù)析構(gòu)函數(shù)將單鏈表中所有結(jié)點的存儲空間釋放。
2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)操作接口:~LinkList();firsta1a2an∧aiq算法描述:q=first;first=first->next;deleteq;first注意:保證鏈表未處理的部分不斷開
單鏈表的實現(xiàn)——析構(gòu)函數(shù)template<classDataType>LinkList<DataType>::~LinkList(){while(first!=NULL){q=first;
first=first->next;
deleteq;}}2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)算法描述:啟示:算法設(shè)計的一般過程算法設(shè)計的一般步驟:第一步:確定入口(已知條件)、出口(結(jié)果);第二步:根據(jù)一個小實例畫出示意圖;第三步:①正向思維:選定一個思考問題的起點,逐步提出問題、解決問題;②逆向思維:從結(jié)論出發(fā)分析為達(dá)到這個結(jié)論應(yīng)該先有什么;③正逆結(jié)合;第四步:寫出頂層較抽象算法,分析邊界情況;第五步:驗證第四步的算法;第六步:寫出具體算法;第七步:進(jìn)一步驗證,手工運行。循環(huán)鏈表firsta1ai-1an∧aip從單鏈表中某結(jié)點p出發(fā)如何找到其前驅(qū)?將單鏈表的首尾相接,將終端結(jié)點的指針域由空指針改為指向頭結(jié)點,構(gòu)成單循環(huán)鏈表,簡稱循環(huán)鏈表。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)循環(huán)鏈表空表和非空表的處理一致附設(shè)頭結(jié)點first空循環(huán)鏈表firsta1ai-1anai非空循環(huán)鏈表2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)firsta1ai-1anai循環(huán)鏈表——插入xspxspxsp算法描述:s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)
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線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)循環(huán)條件:p!=NULLp!=firstp->next!=NULLp->next!=first循環(huán)鏈表循環(huán)鏈表中沒有明顯的尾端如何避免死循環(huán)2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)如何查找開始結(jié)點和終端結(jié)點?循環(huán)鏈表firsta1ai-1anai開始結(jié)點:first->next終端結(jié)點:將單鏈表掃描一遍,時間為O(n)2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)reara1ai-1anai開始結(jié)點:rear->next->next終端結(jié)點:rear循環(huán)鏈表帶尾指針的循環(huán)鏈表一個存儲結(jié)構(gòu)設(shè)計得是否合理,取決于基于該存儲結(jié)構(gòu)的運算是否方便,時間性能是否提高。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表如何求結(jié)點p的直接前驅(qū),時間性能?firsta1ai-1anaip為什么可以快速求得結(jié)點p的后繼?如何快速求得結(jié)點p的前驅(qū)?2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表:在單鏈表的每個結(jié)點中再設(shè)置一個指向其前驅(qū)結(jié)點的指針域。雙鏈表結(jié)點結(jié)構(gòu):priordatanextdata:數(shù)據(jù)域,存儲數(shù)據(jù)元素;prior:指針域,存儲該結(jié)點的前趨結(jié)點地址;next:指針域,存儲該結(jié)點的后繼結(jié)點地址。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)template<classDataType>structDulNode{DataTypedata;DulNode<DataType>*prior,*next;};
雙鏈表啟示?時空權(quán)衡——空間換取時間priordatanext定義結(jié)點結(jié)構(gòu):2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;ai-1ai操作接口:
voidInsert(DulNode<DataType>*p,DataTypex);
pxs注意指針修改的相對順序2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)雙鏈表的操作——刪除(p->prior)->next=p->next;
(p->next)->prior=p->prior;
操作接口:
DataTypeDelete(DulNode<DataType>*p);
ai-1aipai結(jié)點p的指針是否需要修改?deletep;2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)存儲分配方式比較順序表采用順序存儲結(jié)構(gòu),即用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素,數(shù)據(jù)元素之間的邏輯關(guān)系通過存儲位置來實現(xiàn)。鏈表采用鏈接存儲結(jié)構(gòu),即用一組任意的存儲單元存放線性表的元素,用指針來反映數(shù)據(jù)元素之間的邏輯關(guān)系。2.4順序表和鏈表的比較2.4順序表和鏈表的比較時間性能比較
時間性能是指實現(xiàn)基于某種存儲結(jié)構(gòu)的基本操作(即算法)的時間復(fù)雜度。
按位查找:順序表的時間為O(1),是隨機存??;鏈表的時間為O(n),是順序存取。插入和刪除:順序表需移動表長一半的元素,時間為O(n);鏈表不需要移動元素,在給出某個合適位置的指針后,插入和刪除操作所需的時間僅為O(1)。2.4順序表和鏈表的比較空間性能比較
空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。
定義結(jié)點的存儲密度:數(shù)據(jù)域占用的存儲量整個結(jié)點占用的存儲量存儲密度=結(jié)點的存儲密度:順序表:結(jié)點的存儲密度為1(只存儲數(shù)據(jù)元素),沒有浪費空間;鏈表:結(jié)點的存儲密度<1(包括數(shù)據(jù)域和指針域),有指針的結(jié)構(gòu)性開銷。2.4順序表和鏈表的比較空間性能比較
空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。
定義結(jié)點的存儲密度:數(shù)據(jù)域占用的存儲量整個結(jié)點占用的存儲量存儲密度=結(jié)構(gòu)的存儲密度:順序表:需要預(yù)分配存儲空間,如果預(yù)分配得過大,造成浪費,若估計得過小,又將發(fā)生上溢;鏈表:不需要預(yù)分配空間,只要有內(nèi)存空間可以分配,單鏈表中的元素個數(shù)就沒有限制。結(jié)論⑴若線性表需頻繁查找卻很少進(jìn)行插入和刪除操作,或其操作和元素在表中的位置密切相關(guān)時,宜采用順序表作為存儲結(jié)構(gòu);若線性表需頻繁插入和刪除時,則宜采用鏈表做存儲結(jié)構(gòu)。⑵當(dāng)線性表中元素個數(shù)變化較大或者未知時,最好使用鏈表實現(xiàn);而如果用戶事先知道線性表的大致長度,使用順序表的空間效率會更高。2.4順序表和鏈表的比較總之,線性表的順序?qū)崿F(xiàn)和鏈表實現(xiàn)各有其優(yōu)缺點,不能籠統(tǒng)地說哪種實現(xiàn)更好,只能根據(jù)實際問題的具體需要,并對各方面的優(yōu)缺點加以綜合平衡,才能最終選定比較適宜的實現(xiàn)方法。靜態(tài)鏈表:用數(shù)組來表示單鏈表,用數(shù)組元素的下標(biāo)來模擬單鏈表的指針。靜態(tài)鏈表2.5線性表的其它存儲方法data:存儲放數(shù)據(jù)元素;next:也稱游標(biāo),存儲該元素的后繼在數(shù)組的下標(biāo)。數(shù)組元素(結(jié)點)的構(gòu)成:datanext數(shù)據(jù)域指針域例:線性表(張,王,李,趙,吳)的靜態(tài)鏈表存儲張2王3李4趙5吳-101234567878-112.5線性表的其它存儲方法datanext靜態(tài)鏈表firstavailfirst:靜態(tài)鏈表頭指針,為了方便插入和刪除操作,通常靜態(tài)鏈表帶頭結(jié)點;avail:空閑鏈表頭指針,空閑鏈表由于只在表頭操作,所以不帶頭結(jié)點;2.5線性表的其它存儲方法靜態(tài)鏈表靜態(tài)鏈表的存儲結(jié)構(gòu)定義如下:constintMaxSize=100;//100只是示例數(shù)據(jù)template<classDataType>structSNode{DataTypedata;//DataType表示不確定的數(shù)據(jù)類型
intnext;//指針域(也稱游標(biāo))}SList[MaxSize];在線性表(張,王,李,趙,吳)中“王”之后插入“孫”張2王3李4趙5吳-101234567878-112.5線性表的其它存儲方法datanext靜態(tài)鏈表張2王
6李4趙5吳-1012345678孫
38-11datanext王之后插入孫2.5線性表的其它存儲方法靜態(tài)鏈表假設(shè)結(jié)點s插在結(jié)點p之后,則修改指針的操作為:
s=avail;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年心理咨詢師考試實戰(zhàn)案例探討及試題及答案
- 中國主廚用刀白皮書 2025
- 學(xué)前兒童心理健康教育探討
- 中醫(yī)康復(fù)的實證研究試題及答案
- 常見心理咨詢方法介紹試題及答案
- 物理“力的分解”說課稿
- 2024年語文考綱解析試題及答案
- 初中語文文本細(xì)讀能力試題及答案
- 2024年昆明市殯儀館招聘筆試真題
- 2025年不透明石英爐襯項目建議書
- 神奇的電家長課堂
- 幼兒園大班健康:《不吃垃圾食品》課件
- 山西省安裝預(yù)算定額說明及計算規(guī)則
- 2022年廣東省深圳市中考化學(xué)真題試卷
- 部編版四年級語文下冊第二單元全套精美課件(統(tǒng)編版)
- 計算機視覺全套課件
- 民航機場燈光
- T∕CAMDI 048-2020 一次性使用輸液接頭消毒蓋帽
- 六甲集合住宅設(shè)計研究(課堂PPT)
- (完整word版)古籍樣式排版模板
- 中國胰腺癌診治指南2021更新(全文)
評論
0/150
提交評論