數(shù)據結構導引

數(shù)據結構導引第1頁，課件共28頁，創(chuàng)作于2023年2月數(shù)據結構

數(shù)據結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間關系和操作的學科。圖書館檢索書簽查閱圖書目錄卡片：按書名編排的、按作者編排的、按分類編排的…計算機檢索時，處理的對象便是這些目錄卡片上的書目信息。001高等數(shù)學樊映川S01……002理論力學羅遠祥L01……003高等數(shù)學華羅庚S01……004線性代數(shù)欒汝書S02…………………高等數(shù)學001，003…理論力學002，…線性代數(shù)004，……樊映川S01……華羅庚S01……欒汝書S02……………第2頁，課件共28頁，創(chuàng)作于2023年2月人機對奕計算機之所以能和人對奕，策略事先存入計算機。對奕過程在一定規(guī)則下隨機進行，為使計算機靈活對奕，就必須對所有可能發(fā)生的情況以及相應的對策都考慮周全，還應能預測發(fā)展趨勢，甚至最后結局。第3頁，課件共28頁，創(chuàng)作于2023年2月田徑賽田徑賽的時間安排問題設有六個比賽項目，規(guī)定每個選手至多可參加三個項目，有五人報名參加比賽（如下表所示）設計比賽日程表，使得在盡可能短的時間內完成比賽。第4頁，課件共28頁，創(chuàng)作于2023年2月解決方法(無向圖的著色問題)設用如下六個不同代號代表不同的項目：跳高跳遠標槍鉛球100米200米ABCDEF用頂點代表比賽項目不能同時進行比賽的項目之間連上一條邊。某選手比賽的項目必定有邊相連（不能同時比賽）。

F

B王五

A

F

D李四

F

E

C張三

D

C馬二

E

B

A丁一項目3項目2項目1姓名AEBFDCF4E3B，D2A，C1比賽項目比賽時間第5頁，課件共28頁，創(chuàng)作于2023年2月課程主要內容主要內容包括

數(shù)組、鏈接表、棧和隊列、遞歸、樹與森林、圖、堆與優(yōu)先隊列、集合與搜索結構、排序與散列等。課程基本要求掌握數(shù)據結構的概念、使用方法及實現(xiàn)技術；理解算法分析方法（時間代價、空間代價）學習方法預習+復習上課跟著幻燈片充分利用實驗課課后必須自己練！第6頁，課件共28頁，創(chuàng)作于2023年2月TextbookTextbook《DataStructuresandAlgorithmAnalysisinC》

MarkAllenWeissReferencebook《FundamentalofDataStructureinC》EllisHorowitz

UniversityofsouthernCalifornia《數(shù)據結構C語言版》嚴蔚敏清華大學出版社《數(shù)據結構的C++偽碼實現(xiàn)》

RichardF.Gilberg&BehrouzA.Forouzan，人民郵電出版社數(shù)據結構算法與應用-C++語言描述,SartejSahni,機械工業(yè)出版社Others/imediaEmail:zmyuan@第7頁，課件共28頁，創(chuàng)作于2023年2月PatternsofteachingScheduleofteaching以《DataStructuresandAlgorithmAnalysisinC》的順序講解，但內容不限于該書！在網上有每次課的幻燈片可下載,請適當記筆記!Methodsofteaching原版教材,英語講稿/imedia網上課堂進行作業(yè)上交，答疑可以在Wiki上討論!ProgrammingExperiment3節(jié)上課，2節(jié)上機所有程序均由C語言編寫，環(huán)境：VisualC++作業(yè)平時作業(yè)Exercises上機作業(yè)Programming第8頁，課件共28頁，創(chuàng)作于2023年2月TimeDemand[ThetimeofProgrammingExperimentinLab]DeadlineofExperimental–get100%scoreAweeklater–get30%scoreMorethanaweeklater–0score[ThetimeofHomework]DeadlineofHomework–get100%scoreAweeklater–get50%scoreTwoweekslater–0score第9頁，課件共28頁，創(chuàng)作于2023年2月[TheformatofProgrammingReport]

ExperimentalTitleExperimentalDemandDataStructureDescribe(ADTinC)AlgorithmsDescribe(Flowchartisthebetter)Keycodes(FunctionsinC)DebuggingrecordsResultsComments(Summarizeandsuggestions)Sourcecodefiles第10頁，課件共28頁，創(chuàng)作于2023年2月Score平時成績routine考勤（上課，上機）平時作業(yè)Exercises（2星期交一次,每周五上課結束時交）期中成績midsemester期末成績semester實驗成績實驗單獨是一門課，單獨記學分！實驗課完成情況Routine實驗報告ProgrammingReport期末實驗考核ProgrammingTestLastScore=routine*20%+midsemester*20%+semester*60%LastScore=Routine*20%+Report*30%+Test*50%第11頁，課件共28頁，創(chuàng)作于2023年2月Chapter1Introduction第12頁，課件共28頁，創(chuàng)作于2023年2月1.1OverviewDatastructure+Algorithm=ProgrammingThetoolsandtechniquestodesignandimplementlarge-scalecomputersystems:DataabstractionAlgorithmspecificationPerformanceanalysisPerformancemeasurement第13頁，課件共28頁，創(chuàng)作于2023年2月SystemlifecycleThesystemdevelopmentprocess第14頁，課件共28頁，創(chuàng)作于2023年2月BasicConceptofdatastructure數(shù)據：

是信息的載體，是描述客觀事務的數(shù)、字符以及所有能輸入計算機中并被計算機程序識別和處理的符號的集合。數(shù)據的分類：數(shù)值性數(shù)據非數(shù)值性數(shù)據數(shù)據對象：

將數(shù)據按其性質歸類到一起，稱為數(shù)據對象（dataobject),是數(shù)據的子集。數(shù)據元素：

數(shù)據對象中的數(shù)據成員稱為數(shù)據元素，它們具有相同的性質，是數(shù)據的基本單位。（例如：結點、頂點、記錄等）第15頁，課件共28頁，創(chuàng)作于2023年2月DatastructureDataStructure={D,R}數(shù)據結構由某一數(shù)據對象及該對象中所有數(shù)據成員之間的關系組成。D為某一數(shù)據對象R是該對象中所有數(shù)據成員之間的關系的有限集合定義1數(shù)據元素之間的相互關系稱為結構，帶有結構的數(shù)據元素的集合稱為數(shù)據結構。定義2按某種邏輯關系組織起來的一批數(shù)據（或稱帶結構的數(shù)據元素的集合）應用計算機語言并按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的集合。第16頁，課件共28頁，創(chuàng)作于2023年2月數(shù)據結構關心的三方面內容邏輯結構數(shù)據元素間抽象化的相互關系（簡稱為數(shù)據結構）。與數(shù)據的存儲無關，獨立于計算機，它是從具體問題抽象出來的數(shù)學模型。存儲結構（物理結構）數(shù)據元素及其關系在計算機存儲器中的存儲方式。是邏輯結構用計算機語言的實現(xiàn)它依賴于計算機語言。算法第17頁，課件共28頁，創(chuàng)作于2023年2月邏輯結構-1線性結構Linearstructure僅有一個開始元素，僅有一個最后元素；其余都是內部元素，且都有且僅有一個直接前驅和一個直接后繼。線性表B={K，R}K={K0，K1，…，Kn-1}R={r}，r={<ki-1,ki>|ki∈K,1<i<n}線性結構的元素存取方式直接存取結構：不用訪問元素前驅和后繼即可訪問該元素，如數(shù)組。順序存取結構：只能從表的第一個元素按順序訪問，如鏈表。詞典結構（廣義索引）：字典與數(shù)組有相同之處，數(shù)組通過下標訪問，字典通過關鍵碼（key)進行索引訪問。第18頁，課件共28頁，創(chuàng)作于2023年2月邏輯結構-2非線性結構Nonlinearstructure各個數(shù)據成員不再保持在一個線性序列中。

每個數(shù)據成員可能與零個或多個其他數(shù)據成員發(fā)生聯(lián)系?？煞譃閷哟谓Y構和群結構。層次結構按層次劃分的數(shù)據元素的集合，指定層次上的元素，可以有零個或多個處于下一層次上的，直接的所屬元素。例如：樹結構（樹、二叉樹、堆）群結構所有元素之間無順序關系。例：集合就是一種群結構。圖結構也屬于群結構。第19頁，課件共28頁，創(chuàng)作于2023年2月存儲結構存儲結構兩方面的內容數(shù)據元素自身值的表示（數(shù)據域）該結點與其它結點關系的域（鏈域）四種基本的存儲結構順序存儲方法（結構）

sequentialaccess鏈接存儲方法（鏈式存儲結構）

Linkedaccess索引存儲方法

Indexingaccess散列存儲方法同一種邏輯結構可采用不同的存儲方法（以上四種之一或組合），這主要考慮的是運算方便及算法的時空要求。第20頁，課件共28頁，創(chuàng)作于2023年2月索引存儲第21頁，課件共28頁，創(chuàng)作于2023年2月aprogrammingperformsforreasonablylargeinput

question1.SelectionProblem

agroupofN

todeterminetheKthlargestnumbers

question2.Wordpuzzle

atwodimensionalarrayofletters

alistofwordstofindthewordsinthepuzzle

HowtoestimatetherunningrimeofaprogramforlargeinputsHowtocomparetherunningtimesoftwoprogramswithoutactuallycodingthem.第22頁，課件共28頁，創(chuàng)作于2023年2月question1.SelectionProblemagroupofNnumbers,todeterminetheKthlargestoneway:(bad)toreadtheNnumbersintoanarraysortthearrayindecreasingorderbysomesimplealgorithmreturntheelementinpositionkanotherway:(better)

toreadthefirstKelementintoanarraysortthearrayindecreasingorderbysomesimplealgorithm(bubblesort)readremainingelementonebyoneifnewelement<theKthelementinthearray

thenignoreit

elseplaceitinitscorrectspotinthearray,bumpingoneoutofthearray.

Untilnoelement

ReturntheKthelementinthearray?N=millionK=500,000第23頁，課件共28頁，創(chuàng)作于2023年2月question2.Wordpuzzleatwodimensionalarrayofletters,alistofwords,tofindthewordsinthepuzzle

Oneway:

ForeachwordinthelistCheckeachordertriple(row,column,orientation)Anotherway:

Foreachquadruple(row,column,orientation,numberofcharacters)Testwhetherthewordindicatedisinthewordlist第24頁，課件共28頁，創(chuàng)作于2023年2月

Recursivealgorithm【Definition】functionthatisdefinedintermsofitselfiscalledrecursive.

FACTORIALn!=n·(n-1)n>1(0!=1)n!=n·(n-1)·(n-2)…3·2·1MULTIPLYa·b=a·(b-1)+a(a·1=a)a·b=a·(b-1)+a=a·(b-2)+a+a=a·(b-3)+a+a+a…=a+a+…+a+a(btimesaddition)FIBONACCINUMBERfib(n)=nn=0orn=1fib(n)=fib(n-2)+fib(n-1)otherwise第25頁，課件共28頁，創(chuàng)作于2023年2月Twofundamentalrulesofrecursion

１.Basecases.Youmustalwayshavesomebasecases,whichcanbesolvedwithoutrecursion.２.Makingprogress.Forthecasesthataretobesolvedrecursively,therecursivecallmustalwaysbetoacasethatmakesprogresstowardabasecase.#include<stdio.h>

int

F(intX)

{

/*1*/

if(X==0)

/*2*/

return0;

else

/*3*/

return2*F(X-1)+X*X;

}

main()

{

printf("F(5)=%d\n",F(5));

return0;

}#include<stdio.h>

intBad(u