計算機軟件及應(yīng)用chapter是

TeachingMaterialTextBookDataStructureAndAlgorithmsInC++——secondedition.Adam.DrozdekReferenceBook王紅梅.數(shù)據(jù)結(jié)構(gòu)（C＋＋版）.清華大學(xué)出版社MarkAllenWeiss.DataStructures&algorithmanalysisinC++(secondedition)嚴蔚敏.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社.1997StudyHighlightTimeComplexity(算法與時間復(fù)雜度)

k?m'pleksiti]LinearList(線性表)StackandQueue(棧和隊列）GeneralList(廣義線性表)TreeandBinaryTree(樹與二叉樹)Graph(圖)Searching(查找)Sorting(排序)算法與數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)的兩大支柱計算機科學(xué)早期定義為：研究算法的科學(xué)

近期定義為：研究數(shù)據(jù)的科學(xué)數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計的基礎(chǔ)是計算機科學(xué)中一門綜合性專業(yè)課程尼克勞斯．沃思（NiklausWirth）:瑞士計算機科學(xué)家。PASCAL之父，結(jié)構(gòu)化程序設(shè)計的首創(chuàng)者，獲得1984年圖靈獎。Program=DataStructure

+Algorithm使用最適當(dāng)?shù)摹緮?shù)據(jù)結(jié)構(gòu)】，才能夠設(shè)計出最有效率的【算法】，進而轉(zhuǎn)換成為有效率的【程序】。qualto這句話從此就成了計算機學(xué)科的一句名言，數(shù)據(jù)結(jié)構(gòu)是一門和程序設(shè)計密切相關(guān)的課程DataStructureMainlyContent87352545電子商務(wù)學(xué)院電話號碼130012長春工程學(xué)院郵編510103780618748身份證號碼例1：87352545130012510103780618748結(jié)論1. 雜亂的數(shù)據(jù)不能表達和交流信息例2: 電話號碼簿(a1，b1)(a2，b2)…(an，bn)其中：ai為某人姓名，bi為該人的電話號碼。要求：設(shè)計一個算法，給定一個姓名時，能查出此人的電話號碼。如果姓名和電話號碼的排列次序無規(guī)律，則只能逐一比較姓名進行查找如果姓名按字典順序組織，則查找就快捷多了結(jié)論2. 數(shù)據(jù)之間是有聯(lián)系的這些聯(lián)系常常影響算法的選擇和效率?！禗S》就是要研究數(shù)據(jù)之間的聯(lián)系。DataStructureMainlyContent例3：大學(xué)學(xué)生管理機構(gòu)長春工程學(xué)院 土木．．電信．．．

09級10級11級…

本科

?？茝埲钏慕Y(jié)論３． 數(shù)據(jù)之間是有結(jié)構(gòu)的例３中數(shù)據(jù)之間呈分層結(jié)構(gòu)（Tree）《DS》就是要研究數(shù)據(jù)之間的各類結(jié)構(gòu)。DataStructureMainlyContent例４：圖書目錄管理設(shè)每個書目含：書名，作者，登錄號，分類，出版年月對圖書目錄常有如下操作：查找：某書在書庫中是否存在？插入：購進新書時的登錄；刪除：報廢或丟失的書，需從目錄中去掉；結(jié)論４． 在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運算《DS》要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運算。DataStructureMainlyContent綜上所述：《DS》主要研究內(nèi)容：數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系；對每種結(jié)構(gòu)定義相適應(yīng)的各種運算；設(shè)計出相應(yīng)的算法；分析算法的效率。

常見的數(shù)據(jù)結(jié)構(gòu)有：表(linearlist)、數(shù)組(array)、串(string)、棧(stack)、隊列(queue)、樹(tree)、圖(graph)等。方法：查找（search）、排序(sort)StudyPurposeaboutDataStructure數(shù)據(jù)結(jié)構(gòu)課程的三級標(biāo)準1.掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲結(jié)構(gòu)2.提高閱讀和編寫算法的能力3.能針對給定問題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計和分析算法C++語言數(shù)據(jù)結(jié)構(gòu)軟件工程掌握基本編程方法掌握數(shù)據(jù)組織和數(shù)據(jù)處理的方法掌握大型軟件開發(fā)方法學(xué)習(xí)識字學(xué)習(xí)寫作文學(xué)習(xí)寫小說基本要求課程關(guān)系與語文學(xué)習(xí)過程類比本課程在計算機專業(yè)課程中所處的地位課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的專業(yè)基礎(chǔ)課

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

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

“練武不練功，到頭一場空”考研需要大家課后自己復(fù)習(xí)的內(nèi)容：

第0章預(yù)備知識學(xué)習(xí)目標(biāo)掌握基本的數(shù)據(jù)結(jié)構(gòu)

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

算法——程序的靈魂問題求解過程：問題→想法→算法→程序培養(yǎng)算法分析能力

評價算法、改進算法學(xué)習(xí)要求循序漸進，切忌心浮氣躁提高課外學(xué)習(xí)的時間和內(nèi)容理解科學(xué)而不是背誦科學(xué)→讀書正確對待考試作習(xí)題

華羅庚：“學(xué)數(shù)學(xué)不做習(xí)題等于入寶山而空返”

作實驗

計算機學(xué)科是一門科學(xué)性與工程性并重的學(xué)科，表現(xiàn)為理論和實踐緊密結(jié)合的特征。

成績組成平時成績

10％：出勤＋作業(yè)實驗成績

20％：出勤＋程序＋報告期末考試成績

70％Chapter1:IntroductionHistoryofDataStructureResearchobjectsBasicconceptsAlgorithmandalgorithmanalysisbasiccontent：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.1History程序設(shè)計的實質(zhì)是什么?datapresentation：將數(shù)據(jù)存儲在計算機中dataprocessing：處理數(shù)據(jù)，求解問題數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計

實例：學(xué)生成績管理系統(tǒng)數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計的發(fā)展而發(fā)展計算機學(xué)科的飛速發(fā)展是其他任何學(xué)科所無法比擬的。Nostructurestage:20世紀40~60年代,計算機主要用于科學(xué)計算.ApplicationField：科學(xué)計算；Processeddata：數(shù)值型數(shù)據(jù)Therelationshipamongdata：數(shù)學(xué)方程或數(shù)學(xué)模型1.1History2.Structuredstage：數(shù)據(jù)結(jié)構(gòu)＋算法＝程序ApplicationFields：科學(xué)計算與非數(shù)值處理；Processeddata：數(shù)值型數(shù)據(jù)和非數(shù)值型數(shù)據(jù)Therelationshipamongdata：產(chǎn)生了數(shù)據(jù)結(jié)構(gòu)，提出了程序結(jié)構(gòu)模塊化，開始注意數(shù)據(jù)表示和操作的結(jié)構(gòu)化。drawback：以數(shù)據(jù)為中心，不易應(yīng)對變化1.1History3.Object-orientedstage：(數(shù)據(jù)結(jié)構(gòu)＋算法)=程序ApplicationFields：更多地應(yīng)用于非數(shù)值處理；Processeddata：更多地處理非數(shù)值型數(shù)據(jù)Therelationshipamongdata：數(shù)據(jù)結(jié)構(gòu)發(fā)展到面向?qū)ο箅A段類和數(shù)據(jù)結(jié)構(gòu)之間的對應(yīng)關(guān)系：1.1History類屬性方法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)之間的關(guān)系基本操作對應(yīng)數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)1.2ResearchObjectsofDSstepsforsolvingproblemswithcomputer:Aproblem→Abstractaproblemmodel→FindoutthesolutionofthismodelProblem——Numericalproblemandnon-numericalproblem

Numericalproblem→MathematicalEquation

non-numericalproblem→DSKnown

lengthandwideofaswimmingpool,thenfindoutareaofthepool.

◆

Buildamodel問題涉及的對象：游泳池的長len、寬wide和面積area對象之間的關(guān)系Therelationshipamongobjects：area=len

wide◆設(shè)計求解問題的方法Designthemethodofsolvingtheproblem◆編程programming[n?un]['ε?ri?]example一、NumericalProblemsandnon-numericalproblem

NumericalproblemKnown

lengthandwideofaswimmingpool,thenfindoutareaofthepool.◆

Buildamodel問題涉及的對象：length,wideandarea.對象之間的關(guān)系:area=len

wide◆Designthemethodofsolvingtheproblem◆programmingexample一、NumericalProblemsandnon-numericalproblem

Numericalproblem#include<iostream.h>voidmain(){intlen,wide,area;cin>>len>>wide;area=len*wide;cout<<"area="<<area<<endl;}1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇2）non-numericalproblem

playchess……..……..…...…...…...…...◆Buildmodel

問題涉及的對象：theobjectofprobleminvolved:對弈過程中可能出現(xiàn)的棋盤格局；Checkerboardpatternthatmayoccurinthechessprocesscheckerboardpatterns樹即是一種數(shù)據(jù)結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇◆Buildmodel

問題涉及的對象:對弈過程中可能出現(xiàn)的棋盤格局；棋盤格局之間的關(guān)系：由比賽規(guī)則決定。對弈的過程就是從樹根沿樹杈到某個葉子的過程。

Theprocessofchessisfromtheroottoaleafalongthecrotch.

1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇棋盤格局之間的關(guān)系：Therelationshipamongthecheckerboardpatterns由比賽規(guī)則決定。Determinedbytherulesofthegame對弈的過程就是從樹根沿樹杈到某個葉子的過程。

Theprocessofchessisfromtheroottoaleafalongthecrotch.2）非數(shù)值問題酒店管理系統(tǒng)的客房分配問題Roomsallocatedforhotelmanagementsystem◆建模型：buildmodel

問題涉及的對象theobjectofprobleminvolved:：房間；room

房間之間的關(guān)系：Therelationshipbetweentherooms線性關(guān)系，一對一的關(guān)系

每個房間之間的磨損應(yīng)該是相同的frontrear

a1a2a3an入隊列出隊列線性結(jié)構(gòu)1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇2）非數(shù)值問題Roomsallocatedforahotel'?l?ukeit]◆buildamodel：

問題涉及的對象：room

對象之間的關(guān)系：Therelationshipbetweentherooms線性關(guān)系，一對一的關(guān)系

每個房間之間的磨損應(yīng)該是相同的frontrear

a1a2a3an入隊列出隊列Linearlist1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇非數(shù)值問題terminalexaminations已知研究生選課情況，安排課程考試的日程,要求在盡可能短的時間內(nèi)完成考試。研究生選課情況表姓名選修課1 選修課2選修課3楊潤生算法分析A形式語言B計算機網(wǎng)絡(luò)E石磊計算機圖形學(xué)C模式識別D魏慶濤計算機圖形學(xué)C計算機網(wǎng)絡(luò)E人工智能F馬耀先模式識別D人工智能F算法分析A齊硯生形式語言B人工智能F1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇◆建立模型：

問題涉及的對象：

electivecourse

課程之間的關(guān)系：同一研究生選修的課程之間有“沖突”關(guān)系。(同一個研究生選修的課程不能安排在同一時間內(nèi)考試)conflictCDEABF頂點：表示課程

同一研究生選修的課程用邊連接有邊連接的課程不能安排在同一時間考試1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇

每一種顏色代表一個考試時間，著上相同顏色的頂點是可以安排在同一時間考試的課程；

用盡可能少的顏色為圖的頂點著色，使相鄰的頂點著上不同的顏色；DBAEFCFBEACD課程考試可用圖的著色法求解問題第一天thefirstday算法分析(A)計算機圖形學(xué)(C)第二天thesecondday形式語言(B)模式識別（D)第三天計算機網(wǎng)絡(luò)(E)第四天人工智能(F)◆設(shè)計求解問題的方法

求解考試日程的流程

設(shè)G表示課程關(guān)系圖，

V是圖G中所有尚未著色的頂點集合。

NEW表示可以用新顏色著色的頂點集合。⑴i=1；V={圖中所有頂點的集合}⑵若V非空DO

①置NEW為空集合；②在V中找出所有“不相鄰”的頂點，將這些頂點加入NEW,從V中去掉這些頂點。

③i=i+1；⑶若V空,結(jié)束。DBAEFC第i天考試課程為NEW中頂點所對應(yīng)的課程）以某種形式輸出NEW中頂點所對應(yīng)的課程；1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECEDgraph每個圓圈代表一條通路黃燈亮的時候，只有DA,DB兩條路可通行◆建模型：

問題涉及的對象：每個圓圈（即每條通路）；

圓圈之間的關(guān)系：圓圈之間的沖突關(guān)系?！粼O(shè)計求解問題的方法：同上

數(shù)值問題numericalproblems*對象objects：len,wide,area

——用數(shù)值表示*對象之間的關(guān)系Therelationshipamongtheobjects：area=len

wide

——可用方程或函數(shù)表示*數(shù)據(jù)存儲datastorage：可用程序設(shè)計語言中的實型變量存儲數(shù)據(jù)；*問題求解方法：用某種計算方法求解；

k?m'p?ris?n]

非數(shù)值問題non-numericalproblems*對象objects：課程--用課程名表示*對象之間的關(guān)系：課程間有“沖突”關(guān)系*數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系存儲*問題求解方法不能用數(shù)值表示課程之間的這種關(guān)系不能用方程或函數(shù)表示二、數(shù)值問題與非數(shù)值問題的比較acomparisonbetweenthenumericalproblemsandnon-numericalproblems

1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇numericalproblems*objects：length,wide,area

——用數(shù)值表示*Therelationshipamongobjects：area=len

wide

——可用方程或函數(shù)表示*datastorage：可用程序設(shè)計語言中的實型變量存儲數(shù)據(jù)；*problemsolving：用某種計算方法求解；non-numericalproblems*objects：course--用課程名表示*Therelationshipamongobjects：課程間有“沖突”關(guān)系*datastorageandrelationshipamongobjectsstorage*problemsolving不能用數(shù)值表示課程之間的這種關(guān)系不能用方程或函數(shù)表示二、comparisonbetweennumericalproblemandnon-numericalproblem數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問題中計算機的操作對象以及它們之間的關(guān)系和操作的學(xué)科。datastructureisacourse,whichresearchoperationobjectofcomputer,therelationsbetweenthemandoperationaboutnon-numericalproblem1.2researchobjects數(shù)值問題是計算數(shù)學(xué)所要研究的問題。計算數(shù)學(xué)是研究數(shù)值計算方法的設(shè)計、分析和有關(guān)理論基礎(chǔ)的數(shù)學(xué)分支。

DataStructureisasubjectofstudyingthecomputeroperationalobjects,theirrelationshipsamongthemandoperationinthenon-numericalproblem.P301.2researchobjects數(shù)值問題是計算數(shù)學(xué)所要研究的問題。計算數(shù)學(xué)是研究數(shù)值計算方法的設(shè)計、分析和有關(guān)理論基礎(chǔ)的數(shù)學(xué)分支。1.3basicconcepts（1）data：所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。計算機能處理的數(shù)據(jù)集和是隨著計算機的發(fā)展而發(fā)展的，

numericaldata：整數(shù)、實數(shù)等

non-numericaldata：圖形、圖象、聲音、文字等

（一）basicconcepts1.3basicconcepts（1）data：所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。Data——thesetofnumbers,characters,whichdescribetheexternalobjects,andallinformationwhichcanbeinputintothecomputerandprocessedbycomputerprograms.SymbolSetwhichcanbeinputintothecomputerandbeidentifiedandprocessedbycomputerprograms.計算機能處理的數(shù)據(jù)集和是隨著計算機的發(fā)展而發(fā)展的，數(shù)值數(shù)據(jù)：整數(shù)、實數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等

（一）basicconcepts(2)dataelement—數(shù)據(jù)中的一個“個體”，an"individual"indata是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。但不是最小單位。Isthebasicunitofdata,butisnotthesmallestUnit;alsocallednodeorrecord.EachdataelementcanbeconsistofseveralDataItems(theminimalunitofData).數(shù)據(jù)項（dataitem）—數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。(theminimalunitofData).

數(shù)據(jù)元素是數(shù)據(jù)項的集合例如：一個學(xué)生的信息（數(shù)據(jù)元素）學(xué)號姓名性別出生日期政治面貌0001陸宇男1986/09/02團員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團員……………(2)dataelement—數(shù)據(jù)中的一個“個體”,是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。但不是最小單位。dataitem—數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。

數(shù)據(jù)元素是數(shù)據(jù)項的集合例如：一個學(xué)生的信息（數(shù)據(jù)元素）學(xué)號姓名性別出生日期政治面貌0001陸宇男1986/09/02團員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團員……………⑶dataobject：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。DataObject——thesetofdataelementswithsameattribute.ItisthesubsetofDataandcanbeeitherfiniteorinfinite.例如：

整數(shù)數(shù)據(jù)對象的集合：N={0,±1,±2,…}字母字符數(shù)據(jù)對象的集合：

C={‘A’,’B’,…,’Z’}⑶dataobject：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：

整數(shù)數(shù)據(jù)對象的集合：N={0,±1,±2,…}字母字符數(shù)據(jù)對象的集合：

C={‘A’,’B’,…,’Z’}relationshipsamongdata,dataelementanddataitem包含關(guān)系：數(shù)據(jù)是由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項組成。數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項一般不予考慮。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。DataStructure——thesetofdataelementswithsomespecialrelationships.按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。Accordingtothedifferentviewpoint,datastructureisdividedintologicalstructureandstoragestructure邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。LogicalStructure關(guān)聯(lián)方式或鄰接關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型酒店管理問題中，客房之間的邏輯關(guān)系指的是什么？人機對弈問題中，格局之間的邏輯關(guān)系指的是什么？考試計劃編排問題中，課程之間的邏輯關(guān)系指的是什么？DataStructure——thesetofdataelementswithsomespecialrelationships.P31datastructureisdividedintologicalstructureandstoragestructureLogicalStructure：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型酒店管理問題中，客房之間的邏輯關(guān)系指的是什么？人機對弈問題中，格局之間的邏輯關(guān)系指的是什么？考試計劃編排問題中，課程之間的邏輯關(guān)系指的是什么？數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型Logicalstructureofdataisadatamodelwhichisabstractedfromthespecificissues.

二、LogicalStructure數(shù)據(jù)元素之間的邏輯關(guān)系）(1)數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類：Set——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系Linearlist——one-to-one，如線性表、棧、隊列Tree——one-to-manygraph——多many-to-many1.2基本概念非線性結(jié)構(gòu)LogicalStructure1)Set2)Linearlist3)Trees4)GraphsStorageStructure1)SequentialStorage2)LinkedStorage3)IndexedStorage4)HashingStorage(2)數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義formaldefinitionoflogicalstructure二元組表示法two-tuplesnotation

Data_Structure=(D

,S)其中：

D----數(shù)據(jù)元素的有限集合。finitesetofdataelement

S----定義在D上的關(guān)系的有限集合。

finitesetofrelationshipwhichdefinedinD

S={r},r是D上的一個二元關(guān)系risabinaryrelationinD1.2基本概念(2)數(shù)據(jù)邏輯結(jié)構(gòu)的形式定義二元組表示法

Data_Structure=(D

,S)其中：

D----數(shù)據(jù)元素的有限集合。

S----定義在D上的關(guān)系的有限集合。

S={r},r是D上的一個二元關(guān)系1.2基本概念

L=(D,S)

其中：D={a1,a2,a3,...,an}

L=(D,S)

其中：D={a1,a2,a3,...,an}S={r}r={<a1,a2>,<a2,a3>,<a3,a4>…<an-1,an>}例1anai+1ai-1aia2a1……Linearlistset例2anai+1ai-1aia2a1……

T=(D,R)D={A，B，C，D，E，F(xiàn)，G，H，I，J}

R={r}

r={〈A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}

tree例3JIACBDHGFEG1=(V1,E1)V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}

V0

V4

V3

V1

V2

V0

V1

V2

V3G2=(V2,E2)V2={v0v1,v2,v3}E2={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>}GraphExmp4無向圖有無向圖P46,5題數(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)在計算機中的表示。

Alsoknownasthephysical,Isrepresentationofthedatawithitslogicalstructureinthecomputer.

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念內(nèi)存memory存儲結(jié)構(gòu)實質(zhì)上是內(nèi)存分配，在具體實現(xià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)系的整體。存儲結(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)時，依賴于計算機語言。三、StorageStructure數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)⑴SequentialStorage用一組連續(xù)的內(nèi)存單元依次存放數(shù)據(jù)元素。通過元素的存儲順序反映數(shù)據(jù)元素之間的邏輯關(guān)系a1a2……ai-1aiai+1……an⑵LinkedStorage用內(nèi)存中任意一組單元存放數(shù)據(jù)元素,通過保存元素的存儲位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。a1a2ai-1

aian四、Dataoperationscommonoperations◆建立數(shù)據(jù)結(jié)構(gòu)◆清除數(shù)據(jù)結(jié)構(gòu)◆插入一個新數(shù)據(jù)元素◆刪除某個數(shù)據(jù)元素◆修改某個數(shù)據(jù)元素◆排序◆檢索Insertdeleteupdateselectsort1.2基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器中的實現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān) 算法設(shè)計 邏輯結(jié)構(gòu)（取決于） 算法實現(xiàn) 存儲結(jié)構(gòu) （依賴于）存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)——借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈式存儲結(jié)構(gòu)——借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系1.2基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲鏈式存儲線性表棧隊列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：1.2基本概念五、datatype

andAbstractDataType1、datatype一個值的集合和定義在這個值集上的一組操作的總稱。allthedatacategoriesthateachvariablepossesseddefinedinoneprogramdesignlanguage.例如：整形變量，其值為某個區(qū)間上的整數(shù)，定義在其上的操作可以為加減乘除和取模等算術(shù)運算。

數(shù)據(jù)類型原子類型（int,float,char）結(jié)構(gòu)類型（數(shù)組，結(jié)構(gòu)體）五、datatype

andAbstractDataType1、datatype一個值的集合和定義在這個值集上的一組操作的總稱。例如：整形變量，其值為某個區(qū)間上的整數(shù)，定義在其上的操作可以為加減乘除和取模等算術(shù)運算。

datatype原子類型（int,float,char）結(jié)構(gòu)類型（數(shù)組，結(jié)構(gòu)體）2、AbstractDataType(ADT)指一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱.1.2基本概念2、AbstractDataType(ADT)指一個數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱.amathematicmodelandthesetofalloperationsdefinedonit.（其定義僅取決于它的一組邏輯特性,而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。）1.2基本概念A(yù)bstractDataType(ADT)——amathematicmodelandthesetofalloperationsdefinedonit.ADTcanbepresentedbyatriplet(D,S,P),while

Disdataobjects

SissetofrelationshiponD

PisoperationsinDDefinition:ADTname{Dataobjects:<definition>Datarelationships:<definition>Elementaryoperations:<definition>}ADTnameElementaryoperationname(parameterlist)initialcondition:descriptionresultofoperation:descriptionP50ADT可理解為對數(shù)據(jù)類型的進一步抽象抽象數(shù)據(jù)類型比數(shù)據(jù)類型的范疇更廣，它不再局限于固有數(shù)據(jù)類型，還包括用戶自己定義的數(shù)據(jù)類型ADT·邏輯結(jié)構(gòu)·操作集合數(shù)據(jù)結(jié)構(gòu)·存儲結(jié)構(gòu)·算法設(shè)計(a)使用視圖——ADT的定義(b)設(shè)計視圖——ADT的設(shè)計(c)實現(xiàn)視圖——ADT的實現(xiàn)

圖1-7

ADT的不同視圖類·成員變量·成員函數(shù)本書對ADT的定義包括抽象數(shù)據(jù)類型名、數(shù)據(jù)元素之間邏輯關(guā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……1.4算法和算法的分析AlgorithmandAlgorithmAnalysis一、算法（algorithm）的概念

算法是求解問題的操作序列。

AlgorithmistheoperationsequenceforsolvingproblemForexample：求兩個正整數(shù)m，n中的最大數(shù)MAX的算法⑴若m>n則max=m⑵若m<=n則max=n1.4AlgorithmandAlgorithmAnalysis一、difinitionofalgorithmAlgorithmistheoperationsequenceforsolvingaproblem.Forexample：thealgorithmistofindoutthemaximumnumberMAXoftwopositiveintegersmandn.⑴if

m>nthen

max=m⑵if

m<=nthen

max=n求正整數(shù)m，n中的最大數(shù)的算法Characteristicofalgorithms：1Finiteness對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間內(nèi)完成。2Doubtlessness對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定。讀者不會產(chǎn)生二義性。3feasibility算法中的所有操作都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之。4

input任何算法都有輸入，有些在程序運行過程當(dāng)中需要輸入數(shù)據(jù)，有些雖然沒有輸入，但其實已經(jīng)把輸入嵌入了算法當(dāng)中5output。Whatisagoodalgorithm?1correctness:火車站怎么走往北2readability:易于人的閱讀和理解多個人合作軟件時候。

3robustness:輸入數(shù)據(jù)非法時候，算法能做出相應(yīng)反應(yīng)。

4highEfficiency：TimeandSpace效率指算法的執(zhí)行時間，存儲量是執(zhí)行算法所需要最大存儲空間。1.4算法和算法的分析三、Descriptionofalgorithms

Thereareseveralcommonmethodstodescribealgorithmsasfollows:

NaturalLanguagePseudocodeProgramminglanguageFlowChartPseudocodebasedonC++languageisusedtodescribealgorithmsinourtextbook.本書采用基于C++語言的偽代碼來描述。TherearetwomethodtomeasuretheexecutiontimeofaprogramEstimateinadvanceTestaftertheevents1事后統(tǒng)計的方法缺點：必須先運行依據(jù)算法編制的程序所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣四、MeasurementofAlgorithmefficiencyTherearetwowaystomeasureexecutiontimeofprograms:TestaftertheeventEstimateinadvance四、Measurementofalgorithmsefficiency1Testaftertheeventsdrawback：必須先運行依據(jù)算法編制的程序所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣后三條和軟件及硬件有關(guān)，和設(shè)計算法沒關(guān)系，所以我們只考慮前兩條。2Estimateinadvance⑴strategy:算法采用的策略⑵scale:問題的規(guī)模⑶書寫程序的語言⑷編譯程序所產(chǎn)生的機器代碼的質(zhì)量⑸機器執(zhí)行指令的速度weevaluateanalgorithmfromthefollowingtwoaspects:TimeComplexitySpaceComplexity2Estimateinadvance（1）TimeComplexity

theexecutiontimesofthebasicoperation(basicstatement)forsolvingtheproblem.一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間復(fù)雜度記作:

T(n)=O(f(n))Big-O它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同。求解問題的基本操作（基本語句）的執(zhí)行次數(shù)Thestudyofalgorithmefficiencyfocusesonloops.

multiplicationofnordermatrices：C=A×B,Thealgorithmisasfollows：求n階矩陣的乘法#defineMAX100voidmaxtrixmult(intn,floata[MAX][MAX],b[MAX][MAX],floatc[MAX][MAX]){inti,j,k;floatx;for(i=1;i<=n;i++){//(1)for(j=1;i<=n;j++){//(2)x=0;//(3)for(k=1;k<=n;k++)//(4)x+=a[i][k]*b[k][j];//(5)c[i][j]=x;//(6)}}}calculatetimecomplexityofthealgorithm?e.g.算法中的基本操作語句為x+=a[i][k]*b[k][j]，其頻度為：

所以算法的時間復(fù)雜度為算法的時間復(fù)雜度是由嵌套最深層語句即基本操作的頻度決定的。Setthecoefficientofeachitemto1ExampleofBig-Oderivation5n4+10nlog2n+100log2nn4+nlog2n+log2nKeepthelargestiteminthefunctionanddiscardtheothers.O(n4)ThewaytoderiveBig-OexpressionIneachitem,setthecoefficientoftheitemto1.Keepthelargestiteminthefunctionanddiscardtheothers.Itemsarerankedfromthelowesttohighestasfollows:constant，log2n,n,nlog2n,n2,n3,…,

nk,2n,n!

Calculatetimecomplexityofthefollowingprogramsegment:s=0;for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<=i+j;k++)s++;解：該算法的基本操作是語句S++，其頻度為：

例

一個沒有循環(huán)的算法的基本運算次數(shù)與問題規(guī)模n無關(guān),記作O(1),也稱作常數(shù)階。一個只有一重循環(huán)的算法的基本運算次數(shù)與問題規(guī)模n的增長呈線性增大關(guān)系,記作O(n),也稱線性階。其余常用的還有平方階O(n2)、立方階O(n3)、對數(shù)階O(log2n)、指數(shù)階O(2n)等。各種不同數(shù)量級對應(yīng)的值存在著如下關(guān)系：

O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)例求階乘和：sum=1!+2!+3!+……+n!方法1：

floatsum1(intn){floats=0,p=1;inti;for(i=1;i<=n;i++){p=p*i;s=s+p}returns;}timecomplexity：T(n)=O(n)

方法2：

floatsum1(intn){floats=0,p=1;inti,j;for(i=1;i<=n;i++){p=1for(j=1;j<=i;j++)p=p*i;s=s+p;}returns;}timecomplexity：T(n)=O(n2)

T(n)===n-1+n-2+n-3+……+1=例

BubbleSort

algorithmvoidbubble_sort(inta[],intn)