数据结构导引

数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作的学科。图书馆检索书签查阅图书目录卡片：按书名编排的、按作者编排的、按分类编排的…计算机检索时，处理的对象便是这些目录卡片上的书目信息。001高等数学樊映川S01……002理论力学罗远祥L01……003高等数学华罗庚S01……004线性代数栾汝书S02…………………高等数学001，003…理论力学002，…线性代数004，……樊映川S01……华罗庚S01……栾汝书S02……………人机对奕计算机之所以能和人对奕，策略事先存入计算机。对奕过程在一定规则下随机进行，为使计算机灵活对奕，就必须对所有可能发生的情况以及相应的对策都考虑周全，还应能预测发展趋势，甚至最后结局。田径赛田径赛的时间安排问题设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。解决方法(无向图的着色问题)设用如下六个不同代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。某选手比赛的项目必定有边相连（不能同时比赛）。

F

B王五

A

F

D李四

F

E

C张三

D

C马二

E

B

A丁一项目3项目2项目1姓名AEBFDCF4E3B，D2A，C1比赛项目比赛时间课程主要内容主要内容包括

数组、链接表、栈和队列、递归、树与森林、图、堆与优先队列、集合与搜索结构、排序与散列等。课程基本要求掌握数据结构的概念、使用方法及实现技术；理解算法分析方法（时间代价、空间代价）学习方法预习+复习上课跟着幻灯片充分利用实验课课后必须自己练！TextbookTextbook《DataStructuresandAlgorithmAnalysisinC》

MarkAllenWeissReferencebook《FundamentalofDataStructureinC》EllisHorowitz

UniversityofsouthernCalifornia《数据结构C语言版》严蔚敏清华大学出版社《数据结构的C++伪码实现》

RichardF.Gilberg&BehrouzA.Forouzan，人民邮电出版社数据结构算法与应用-C++语言描述,SartejSahni,机械工业出版社Others/imediaEmail:zmyuan@PatternsofteachingScheduleofteaching以《DataStructuresandAlgorithmAnalysisinC》的顺序讲解，但内容不限于该书！在网上有每次课的幻灯片可下载,请适当记笔记!Methodsofteaching原版教材,英语讲稿/imedia网上课堂进行作业上交，答疑可以在Wiki上讨论!ProgrammingExperiment3节上课，2节上机所有程序均由C语言编写，环境：VisualC++作业平时作业Exercises上机作业ProgrammingTimeDemand[TheformatofProgrammingReport]ScoreLastScore=routine*20%+midsemester*20%+semester*60%LastScore=Routine*20%+Report*30%+Test*50%Chapter1Introduction1.1OverviewDatastructure+Algorithm=ProgrammingThetoolsandtechniquestodesignandimplementlarge-scalecomputersystems:DataabstractionAlgorithmspecificationPerformanceanalysisPerformancemeasurementSystemlifecycleThesystemdevelopmentprocessBasicConceptofdatastructure数据：

是信息的载体，是描述客观事务的数、字符以及所有能输入计算机中并被计算机程序识别和处理的符号的集合。数据的分类：数值性数据非数值性数据数据对象：

将数据按其性质归类到一起，称为数据对象（dataobject),是数据的子集。数据元素：

数据对象中的数据成员称为数据元素，它们具有相同的性质，是数据的基本单位。（例如：结点、顶点、记录等）DatastructureDataStructure={D,R}数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。D为某一数据对象R是该对象中所有数据成员之间的关系的有限集合定义1数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。数据结构关心的三方面内容逻辑结构数据元素间抽象化的相互关系（简称为数据结构）。与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型。存储结构（物理结构）数据元素及其关系在计算机存储器中的存储方式。是逻辑结构用计算机语言的实现它依赖于计算机语言。算法逻辑结构-1线性结构Linearstructure仅有一个开始元素，仅有一个最后元素；其余都是内部元素，且都有且仅有一个直接前驱和一个直接后继。线性表B={K，R}K={K0，K1，…，Kn-1}R={r}，r={<ki-1,ki>|ki∈K,1<i<n}线性结构的元素存取方式直接存取结构：不用访问元素前驱和后继即可访问该元素，如数组。顺序存取结构：只能从表的第一个元素按顺序访问，如链表。词典结构（广义索引）：字典与数组有相同之处，数组通过下标访问，字典通过关键码（key)进行索引访问。逻辑结构-2非线性结构Nonlinearstructure各个数据成员不再保持在一个线性序列中。

每个数据成员可能与零个或多个其他数据成员发生联系。可分为层次结构和群结构。层次结构按层次划分的数据元素的集合，指定层次上的元素，可以有零个或多个处于下一层次上的，直接的所属元素。例如：树结构（树、二叉树、堆）群结构所有元素之间无顺序关系。例：集合就是一种群结构。图结构也属于群结构。存储结构存储结构两方面的内容数据元素自身值的表示（数据域）该结点与其它结点关系的域（链域）四种基本的存储结构顺序存储方法（结构）

sequentialaccess链接存储方法（链式存储结构）

Linkedaccess索引存储方法

Indexingaccess散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。索引存储aprogrammingperformsforreasonablylargeinput

question1.SelectionProblem

agroupofN

todeterminetheKthlargestnumbers

question2.Wordpuzzle

atwodimensionalarrayofletters

alistofwordstofindthewordsinthepuzzle

HowtoestimatetherunningrimeofaprogramforlargeinputsHowtocomparetherunningtimesoftwoprogramswithoutactuallycodingthem.question1.SelectionProblemagroupofNnumbers,todeterminetheKthlargestoneway:(bad)toreadtheNnumbersintoanarraysortthearrayindecreasingorderbysomesimplealgorithmreturntheelementinpositionkanotherway:(better)

toreadthefirstKelementintoanarraysortthearrayindecreasingorderbysomesimplealgorithm(bubblesort)readremainingelementonebyoneifnewelement<theKthelementinthearray

thenignoreit

elseplaceitinitscorrectspotinthearray,bumpingoneoutofthearray.

Untilnoelement

ReturntheKthelementinthearray?N=millionK=500,000question2.Wordpuzzle

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)otherwiseTwofundamentalrulesofrecursion

１.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(unsignedintN)

{

/*1*/

if(N==0