数据结构和算法总结new

《数据结构和算法总结new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构和算法总结计算机科学是通过使用计算机解决各种问题的研究领域。为了使用计算机解决给出的问题，您需要为其设计算法。算法的效率可以通过数据结构来改善。选择并实现合适的数据结构和算法来解决特定的编程问题。一、算法和数据结构简介二、实现排序算法（选择、冒泡、插入、快排、堆。。。）三、执行搜索算法线性搜索二叉搜索散列搜索四、使用链接列表解决编程问题单链接列表双链接列表循环链接列表五、使用堆栈解决编程中的问题使用数组实现一个堆栈使用链接列表实现一个堆栈六、使用队列解决编程问题七、使用树结构解决编程问题八、使用图解决编程问题一、算法和数据结构简介算法：解决问题的逐

2、步程序算法的5个属性：有限性、明确性、输入、输出、有效性数据结构：在内存中互相组织各个数据元素的方式标准数据结构有：数组、链接表、堆栈、队列、树和图表；当然你也可以创建尽可能多的数据结构。数据结构的类型：从物理上分：静态、动态从逻辑上分：线性结构、树、图、集合设计算法的技巧：分治法、贪婪法（1）分治法将问题细分为子问题（可使用递归帮助细分）（2）贪婪法每次选择最佳可能选项。因此适用于解决优化问题。缺：通常找不出全局最优解决方案，会给出最优值的良好近似值。影响程序效率的因素：包括机器速度、编译器、操作系统、编程语言和输入大小。当然，还有算法喽！算法消耗的主要

3、资源：时间：执行算法所需的CPU时间空间：执行算法所用的内存量时间/空间权衡：你可以在程序执行速度较慢时可以减少使用的内存或在使用内存的成本高时减少运行的时间。而内存通常感觉可以扩展，因为可以增加计算机的内存量，单时间是不可以扩展的。因此通常考虑时间要比考虑内存的情况多。算法的总运行时间直接与算法中涉及的比较次数成比例。算法的增长阶：O（1）

4、&id=54783二、执行搜索算法线性搜索：按顺序逐一比较。最佳效率O（1），最差O（n）;缺：不适合搜索大列表二叉搜索：二分法最佳效率O（1），最差O（logn）；优：适用搜索大列表缺：前提是列表时排好序的。散列搜索：优：明显提高搜索速度缺：两个键产生相同的散列值，冲突；不能顺序访问散列表中的项。最佳效率O（1），散列的效率取决于散列函数的质量。详细信息：http://student.csdn.net/space.php?uid=253515&do=blog&id=55041三、使用链接列表解决编程问题链接列表的类型：单链接列表、双链接列表、循环链接列表

5、、双循环链接列表操作：插入、删除、遍历和搜索通过定义两个类，在程序中表示链接列表：Node类的声明：------------------CodeinC#---------------------------classNode{publicintroll_no;publicstringname;publicNodenext;}---------------CodeinC++------------------classNode{public:introll_no;charname[50];Node*next;}----------------------Co

6、de---------------------------List类：由对链表的一组操作组成，还包含变量/指针START的声明---------------------CodeinC#-------------------------classList{privateNodeSTART;List(){START=NULL;}publicvoidaddNode(intelement){}publicboolsearch(intelement,refNodeprevious,refNodecurrent){}publicbooldelNode(inteleme

7、nt){}publicvoidtraverse(){}};---------------------------------CodeinC++---------------------------------------------------classList{Node*START;Public:List(){START=NULL;}VoidaddNode(intelement);boolsearch(intelement,Node*previous,Node*current);BooldelNode(intelement);Voidtravious()

8、;};------------------------------