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

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

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

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

+Algorithm使用最適當(dāng)?shù)摹緮?shù)據(jù)結(jié)構(gòu)】，才能夠設(shè)計(jì)出最有效率的【算法】，進(jìn)而轉(zhuǎn)換成為有效率的【程序】。qualto這句話從此就成了計(jì)算機(jī)學(xué)科的一句名言，數(shù)據(jù)結(jié)構(gòu)是一門和程序設(shè)計(jì)密切相關(guān)的課程DataStructureMainlyContent87352545電子商務(wù)學(xué)院電話號碼130012長春工程學(xué)院郵編510103780618748身份證號碼例1：87352545130012510103780618748結(jié)論1. 雜亂的數(shù)據(jù)不能表達(dá)和交流信息例2: 電話號碼簿(a1，b1)(a2，b2)…(an，bn)其中：ai為某人姓名，bi為該人的電話號碼。要求：設(shè)計(jì)一個(gè)算法，給定一個(gè)姓名時(shí)，能查出此人的電話號碼。如果姓名和電話號碼的排列次序無規(guī)律，則只能逐一比較姓名進(jìn)行查找如果姓名按字典順序組織，則查找就快捷多了結(jié)論2. 數(shù)據(jù)之間是有聯(lián)系的這些聯(lián)系常常影響算法的選擇和效率?！禗S》就是要研究數(shù)據(jù)之間的聯(lián)系。DataStructureMainlyContent例3：大學(xué)學(xué)生管理機(jī)構(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è)每個(gè)書目含：書名，作者，登錄號，分類，出版年月對圖書目錄常有如下操作：查找：某書在書庫中是否存在？插入：購進(jìn)新書時(shí)的登錄；刪除：報(bào)廢或丟失的書，需從目錄中去掉；結(jié)論４． 在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運(yùn)算《DS》要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算。DataStructureMainlyContent綜上所述：《DS》主要研究內(nèi)容：數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系；對每種結(jié)構(gòu)定義相適應(yīng)的各種運(yùn)算；設(shè)計(jì)出相應(yīng)的算法；分析算法的效率。

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

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

前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語言后續(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è)計(jì)能力、程序設(shè)計(jì)能力

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

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

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

作實(shí)驗(yàn)

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

成績組成平時(shí)成績

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

20％：出勤＋程序＋報(bào)告期末考試成績

70％Chapter1:IntroductionHistoryofDataStructureResearchobjectsBasicconceptsAlgorithmandalgorithmanalysisbasiccontent：1938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming他計(jì)劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎，此時(shí)，他年僅36歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努思1.1History程序設(shè)計(jì)的實(shí)質(zhì)是什么?datapresentation：將數(shù)據(jù)存儲在計(jì)算機(jī)中dataprocessing：處理數(shù)據(jù)，求解問題數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計(jì)

實(shí)例：學(xué)生成績管理系統(tǒng)數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計(jì)的發(fā)展而發(fā)展計(jì)算機(jī)學(xué)科的飛速發(fā)展是其他任何學(xué)科所無法比擬的。Nostructurestage:20世紀(jì)40~60年代,計(jì)算機(jī)主要用于科學(xué)計(jì)算.ApplicationField：科學(xué)計(jì)算；Processeddata：數(shù)值型數(shù)據(jù)Therelationshipamongdata：數(shù)學(xué)方程或數(shù)學(xué)模型1.1History2.Structuredstage：數(shù)據(jù)結(jié)構(gòu)＋算法＝程序ApplicationFields：科學(xué)計(jì)算與非數(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è)計(jì)求解問題的方法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ī)則決定。對弈的過程就是從樹根沿樹杈到某個(gè)葉子的過程。

Theprocessofchessisfromtheroottoaleafalongthecrotch.

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

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

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

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

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

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

問題涉及的對象：room

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

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

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

問題涉及的對象：

electivecourse

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

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

每一種顏色代表一個(gè)考試時(shí)間，著上相同顏色的頂點(diǎn)是可以安排在同一時(shí)間考試的課程；

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

求解考試日程的流程

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

V是圖G中所有尚未著色的頂點(diǎn)集合。

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

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

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

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

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

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

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

wide

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

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

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

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

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

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

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

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

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

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

整數(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ù)項(xiàng)組成。數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。DataStructure——thesetofdataelementswithsomespecialrelationships.按照視點(diǎn)的不同，數(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)系指的是什么？人機(jī)對弈問題中，格局之間的邏輯關(guān)系指的是什么？考試計(jì)劃編排問題中，課程之間的邏輯關(guān)系指的是什么？DataStructure——thesetofdataelementswithsomespecialrelationships.P31datastructureisdividedintologicalstructureandstoragestructureLogicalStructure：指數(shù)據(jù)元素之間邏輯關(guān)系的整體。數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)據(jù)模型酒店管理問題中，客房之間的邏輯關(guān)系指的是什么？人機(jī)對弈問題中，格局之間的邏輯關(guān)系指的是什么？考試計(jì)劃編排問題中，課程之間的邏輯關(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ù)元素間除“同屬于一個(gè)集合”外，無其它關(guān)系Linearlist——one-to-one，如線性表、棧、隊(duì)列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上的一個(gè)二元關(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上的一個(gè)二元關(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ù)元素的集合。按照視點(diǎn)的不同，數(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)在計(jì)算機(jī)中的表示。

Alsoknownasthephysical,Isrepresentationofthedatawithitslogicalstructureinthecomputer.

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念內(nèi)存memory存儲結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語言。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同，數(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)在計(jì)算機(jī)中的表示。

1.3數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念內(nèi)存存儲結(jié)構(gòu)實(shí)質(zhì)上是內(nèi)存分配，在具體實(shí)現(xiàn)時(shí)，依賴于計(jì)算機(jī)語言。三、StorageStructure數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的實(shí)現(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)◆插入一個(gè)新數(shù)據(jù)元素◆刪除某個(gè)數(shù)據(jù)元素◆修改某個(gè)數(shù)據(jù)元素◆排序◆檢索Insertdeleteupdateselectsort1.2基本概念1.3數(shù)據(jù)結(jié)構(gòu)的基本概念（小結(jié)）數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合。按照視點(diǎn)的不同，數(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)在計(jì)算機(jī)存儲器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu)（取決于） 算法實(shí)現(xiàn) 存儲結(jié)構(gòu) （依賴于）存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)——借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯Y(jié)構(gòu)——借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系1.2基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲鏈?zhǔn)酱鎯€性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：1.2基本概念五、datatype

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

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

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

datatype原子類型（int,float,char）結(jié)構(gòu)類型（數(shù)組，結(jié)構(gòu)體）2、AbstractDataType(ADT)指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱.1.2基本概念2、AbstractDataType(ADT)指一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱.amathematicmodelandthesetofalloperationsdefinedonit.（其定義僅取決于它的一組邏輯特性,而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(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ù)類型的進(jìn)一步抽象抽象數(shù)據(jù)類型比數(shù)據(jù)類型的范疇更廣，它不再局限于固有數(shù)據(jù)類型，還包括用戶自己定義的數(shù)據(jù)類型ADT·邏輯結(jié)構(gòu)·操作集合數(shù)據(jù)結(jié)構(gòu)·存儲結(jié)構(gòu)·算法設(shè)計(jì)(a)使用視圖——ADT的定義(b)設(shè)計(jì)視圖——ADT的設(shè)計(jì)(c)實(shí)現(xiàn)視圖——ADT的實(shí)現(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：求兩個(gè)正整數(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é)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。2Doubtlessness對于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定。讀者不會產(chǎn)生二義性。3feasibility算法中的所有操作都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。4

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

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

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

Thereareseveralcommonmethodstodescribealgorithmsasfollows:

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

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

T(n)=O(f(n))Big-O它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和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]，其頻度為：

所以算法的時(shí)間復(fù)雜度為算法的時(shí)間復(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++，其頻度為：

例

一個(gè)沒有循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模n無關(guān),記作O(1),也稱作常數(shù)階。一個(gè)只有一重循環(huán)的算法的基本運(yù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)