HNND《数据结构》课件(C语言).ppt

每天早晨，叫起你的不是闹钟，而是梦想 习近平语 “人的一生只有一次青春。现在，青春是用来奋斗的；将来，青春是用来回忆的……青年时代，选择吃苦也就选择了收获，选择奉献也就选择了高尚。青年时期多经历一点摔打、挫折、考验，有利于走好一生的路……只有进行了激情奋斗的青春，只有进行了顽强拼搏的青春，只有为人民作出了奉献的青春，才会留下充实、温暖、持久、无悔的青春回忆。” 如何学好这门课 考试方式 闭卷笔试 平时成绩（40%东方，30%本部） 到课率 作业 上机实习 期终考试（60%，70%） 课程设计（单独测试） 东方一周，本部两周 设计报告（30%），程序（40%），答辩（30%） 参考文献 教材：严蔚敏，吴伟民。数据结构（C语言版），清华大学出版社，2013.4 配套习题：数据结构题集（C语言版），严蔚敏等编，清华大学出版社，2013.4 参考教材： 数据结构（C++版），王艳华，戴小鹏编，武汉大学出版社，2007.4 数据结构（C++）复习题要与上机指导，王艳华，戴小鹏，武汉大学出版社，2007.4 数据结构考研指导，李春葆等编，清华大学出版社，2003.1 注意：请参看相关的C/C++的教材 知识体系 计算机主要解决的问题-计算 计算的模式问题 C/S计算模式（Client/Server 二层结构） B/S计算模式（Bowser/Server 三层结构）加上数据库 P/G计算模式（Pervasive/Grid）云计算 计算中的数据解决 数据描述问题（数据结构）例如人脸识别 数据存储问题 计算的方法 算法 （算法的实现，算法的可行性，时间复复杂度、空间复杂度） （1） S=(D, R) D={ a, b, c, d, e, f } R={a,e, b,c,(c,a, e,f, f,d} d1 d5 d2 d4 d3 解:假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有 因T(n)=E≤(n+1)/2 ≤ c*n,其中c为常数，所以该算法的等概率平均时间复杂度为 T(n)= O(n)。 例13: 对比在数据元素个数为30000时，冒泡排序算法和快速排序算法的实际耗时。 根据问题的要求，设计测试程序，并在计算机上实际运行。 程序运行结果：冒泡排序: 6.00 秒；快速排序: 0.00 秒 程序运行结果说明：系统中的difftime (end,start)函数以秒为单位计时，快速排序的实际耗时少于0.5 秒，所以输出显示为0.00 秒。程序运行结果说明，当数据元素个数足够大时，理论分析的快速排序算法优于冒泡排序算法的结果，和程序的实际测试结果吻合。 算法耗时的实际测试 算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可实际使用的算法；而具有指数时间复杂度（如O(2n)、O(nn)、O(n！)等）的算法，是理论上可以计算，但实际上不可计算的问题，通常称作难解的问题。 对于具有多项式时间复杂度的算法，无论数据元素个数多大（只要是有限的数值），算法都可以在有限的时间内运行完成；而对于难解的问题，当n足够小时，算法可以在有限的时间内运行完成，当n比较大时，其运行时间将是一个天文数字！ 数据元素个数和时间复杂度 常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 ……… K次方阶 指数阶 常见的时间复杂度，按数量级递增排序： ●存储空间需求 4、算法的描述和算法分析 算法所需存储空间的度量——空间复杂度（性） 算法的空间复杂度S(n)就是一个算法或程序所需要的存储单元数。 一个非递归程序，并且不含有动态数据结构，在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而只统计与问题大小有关的数组等结构变量所需的内存量，有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统计。 含有动态数据结构的程序应统计内存分配过程的次数乘以该过程产生的动态变量所占单元的大小。递归调用情况较复杂，所需内存单元数等于递归调用的最大深度乘以该递归过程本身所需的内存量，后者包括简单变量、参数变量、调用时系统所需的辅助内存量等。 第四问题如何分析算法的