数据结构与算法分析c++版课件_3.pdf

《数据结构与算法分析c++版课件_3.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法分析c++版课件_3.pdf（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Data Structures and Data Structures and Algorithms任课教师：程艳红任课教师：程艳红教师简介-1教师简介主讲教师：程艳红主讲教师：程艳红讲师，计算机（软件）学院讲师，计算机（软件）学院研究方向研究方向：无线网络无线网络研究方向研究方向：无线网络无线网络邮箱邮箱:课程网站课程网站：课程网站课程网站：请经常登录课程网站，查看最新消息、以及给出的请常录课程站看最新消息以及给出的资料等。QQ群群：？：？（网上答疑网上答疑）QQ群群：？：？（网上答疑网上答疑）教师简介-2教师简介助教：待定助教：待定Introduction Course name:Data

2、 structures and algorithms Course ID：311076040Course ID：311076040 Credit hour：4 Total period:64 class-hours Anteceding courses Anteceding courses：Discrete mathematicsProgram design methodology(C)Object-oriented programming(C+)Object-oriented programming(C+)教材教材教材中的错 教材中的错误订正：http:/people.cs.vt.edupp

3、p/shaffer/Book/errata.html 其中的部分错误已经改正改正Reference-1 数据结构与算法分析唐宁九主编 四川大学出版社 数据结构（用面向对象方法与C+描述）数据结构（用面向对象方法与C+描述）殷人昆主编 清华大学出版社D tSttAlithd Data Structures Algorithms and Applications in C+,Mcgraw-Hill,Sartej ppgjSahni 汪诗林等译 机械工业出版社Reference-2 C+数据结构与程序设计（英文版）Robert L.Kruse 高等教育出版社 Data Structures and

4、Algorithm Analysis in CData Structures and Algorithm Analysis in C Mark Allen Weiss 机械工业出版社Flid 大学上课视频 Florida大学上课视频：http:/www.cise.ufl.edu/academics/courses/preview/cop3530sahni/Grade Policy 1Grade Policy-1期末总成绩100分。平时平时(Attendance etc)10%平时平时(Attendance,etc)10%实验实验30%Mid-term exam20%Final Exam40%F

5、inal Exam 40%Grade Policy 2Grade Policy-2平时成绩平时成绩平时成绩平时成绩：?考勤不定期考勤，根据缺勤比例计算成绩，缺勤比例超过1/3，失去期末考试资格。?课堂表现课堂讨论、presentation、等课堂讨论p等?作业课后作业小程序等平均每周一次必须按时交课后作业、小程序等。平均每周次，必须按时交，不接收延迟提交。完成作业认真程度和提交次数不计算对错情况完成作业认真程度和提交次数，不计算对错情况。Grade Policy-3y实验：实验：?共3个题目，独立完成/小组完成。?分数主要由助教负责评定（必须分出档次抄袭0?分数主要由助教负责评定（必须分出档次

6、，抄袭0分），在规定的提交时间后一周内，完成评分。?每个同学可以查看自己的实验得分，如果你对分数有异议，请在一周内跟任课老师提出复查复查申请。数有异议，请在周内跟任课老师提出复查复查申请。?对于每个实验，会给出提交的最后期限最后期限，请大家认真关注提交期限认真关注提交期限。Grade Policy-4y关于关于延迟提交延迟提交：关于关于延迟提交延迟提交：?平时作业延迟提交一律平时作业延迟提交一律0分分。请不要找老师或助教给予特别照顾，我们不接受任何借口。去掉一次最差作业分数，已经给了大家一定的灵活性。分数，已经给了大家定的灵活性?实验延迟提交：实验延迟提交：每延迟提交一天，扣20%分数。如：根

7、据你的实验完成情况可以得90分如果延迟1天提根据你的实验完成情况，可以得90分，如果延迟1天提交，将只有90*0.8=72分；延迟2天提交，将只有90*0.6=54分。因此，即使是可以得100分，如果延迟5天后提交则本次实验只有0分天后提交，则本次实验只有0分。关于考试关于考试考试：考试：期中考试暂定于第9周（*月*日）内部排 期中考试暂定于第9周（月 日）。内部排序（第7章）已经讲完。期末考试时间会在学院网站上通知，大约安排在18周左右。安排在周抄袭处理 作业、实验抄袭者，一律记为作业、实验抄袭者，一律记为0分分。在老师和助教不能分辨哪个是抄袭者哪个是被抄袭者助教不能分辨哪个是抄袭者、哪个是

8、被抄袭者时，两者都为0分。我们提倡同学之间互相帮助，但不允许你直接使用其他人的成果不允许你直接使用其他人的成果。一些问题的解决方法可以通过同学之间互相交流、讨论来获得，但你需要将这些用你自己的方式表示出来，而不是直接copy。如果某个重要的解决方案是来自于某个同学的，或来自于某篇文献，或来自于网络，请在你的实验报告中某篇献来请在实报中通过“致谢”或“说明”“致谢”或“说明”的方式明确表明，这是一种非常好的科研习惯，不会降低你的分数，同时也可以惯会低避免你有抄袭的嫌疑。About this courseAbout this courseData structures is a core cour

9、se of computer science curriculum.It provides a rich context for the study of problem solving techniques and programproblem-solving techniques and program design and utilizes powerful programming constructs and algorithms.This course uses C+whose classes and OOThis course uses Cwhose classes and OO

10、constructs are specifically designed to efficiently implement data structuresefficiently implement data structures.Goals of this Course1Learn the commonly used data structures1.Learn the commonly used data structures.These form a programmers basic data structure toolkit structure toolkit.2.Reinforce

11、 the concept that costs and benefits exist for every data structure.3.Understand how to measure the cost of a data structure or program.pgThese techniques also allow you to judge the merits of new data structures that you ormerits of new data structures that you or others might invent.Course Summary

12、-1Course Summary-11 Learning the basic concepts of data1.Learning the basic concepts of data structures,including data objects,data types abstract data types classestypes,abstract data types,classes,methods and implementation.2.Learning to describe the methods of abstract data types with C+,and lear

13、ningabstract data types with C,and learning some important concepts in object-oriented programming such as encapsulationprogramming,such as encapsulation,template function,inheritance,virtual ftilhitfunctions,polymorphism,etc.Course Summary 2Course Summary-23 Learning the concepts declaration and3.L

14、earning the concepts,declaration and implementation about list,stack,queue,tree binary tree hash list graph file etctree,binary tree,hash list,graph,file,etc.4.Learning the basic searching and sorting algorithms,such as sequential searching,binary searching,tree searching,hash yg,g,searching,and sim

15、ple sorting,quick sorting,heap sorting,and merge sorting,sorting,heap sorting,and merge sorting,etc.Course Summary 3Course Summary-35 Learning some important applications and5.Learning some important applications and algorithms,such as Huffman algorithm,Dijkstra algorithm etcDijkstra algorithm,etc.6

16、.Learning the performance criteria,including space efficiency and computational efficiency,Big-O Notation.py,gUsing the Big-O Notation to evaluate all kinds of algorithms that are learned in thiskinds of algorithms that are learned in this course.Course Outline 1Course Outline-1Part1 PreliminariesCh

17、ap 1 Data structures and algorithms2hChap 1.Data structures and algorithms 2hChap 2.mathematical preliminaries 1hChap 3.Algorithm Analysis 3hCourse Outline 2Course Outline-2Part2 Fundamental Data StructuresChap 4 Lists Stacks and Queues8hChap 4.Lists,Stacks and Queues 8hDeclaration and implementatio

18、n of array-based and linked list,stack and queueYour turn:stack and queueYour turn:stack and queueCourse Outline 3Course Outline-3Ch5 BiT7hChap 5.Binary Trees 7hDefinition,Implementation and TraversalsDefinition,Implementation and TraversalsBinary search TreeHuffman TreeYour turn:Huffman treeYour tu

19、rn:Huffman treeChap 6.Non-Binary Trees 4hGeneral tree Definition,Implementation and Traversals a e sa sCourse Outline-4Course Outline 4Part 3 Sorting and searchingPart 3 Sorting and searchingChap 7.internal sorting 5hinsertion/bubble/selection/shell/quickinsertion/bubble/selection/shell/quick/merge/

20、Heap/radix sortYour turn:insertion/bubble/selection sortChap 8.file processing and external sortingChap 8.file processing and external sorting2hsecondary storage disk drivessecondary storage,disk drives buffers and buffer pools tltiexternal sorting Course Outline 5Course Outline-5Chap 9 searching3hC

21、hap 9.searching 3hsearching sorted arrays hashing Binary SearchingBinary Searching Your turn:binary searchingCh10 I di3hChap 10.Indexing 3hLinear Indexing,ISAM,2-3 Trees,B-treesg,Course Outline 6Course Outline-6Part 4 Applications and advanced topicsChap 11.Graph 9hppConnected Components Graph Class

22、 ImplementationGraph Class Implementation Graph Traversals Floyd Algorithm*Prim Algorithm gDijkstra AlgorithmClass ScheduleCourse outlineDateChap 1.Data structures and algorithms9.5algorithms Chap 2.mathematical 9.5ppreliminaries Chap 3 Algorithm Analysis9 12Chap 3.Algorithm Analysis9.12Chap 4.Lists,Stacks and Queues 9.19,9.26p,Chap 5.Binary Tree10.10,10.17Chap 6.Non-Binary TreeClass Schedule(cont.)Course outlineDateChap 7.Internal SortingChap 8.File Processing and external sortingChap 9.SearchingChap 10.IndexingChap 11 graphsChap 11.graphs