数据结构与算法绪论

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

1、数据结构与算法¢授课教师：张岩/李秀坤¢答疑地点：综合楼416/格物楼203¢办公电话：86413213/86403146¢E-mail：zhangy@hit.edu.cnlixiukun@hit.edu.cn数据结构与算法第1章绪论数据结构与算法¢教学目的:¢(1)学会分析和研究计算机处理的数据对象的特性,掌握常用数据结构内在的逻辑关系、在机内的存储表示,掌握常用数据结构上的运算操作的动态性质和执行算法.¢(2)能够为实际应用选择适当的数据结构、存储结构和相应算法；¢(3)初步掌握算法性能的分析方法。参考书目¢[美]SartajSahni著，汪诗林孙晓东等译

2、：《数据结构、算法与应用》C++语言描述，机械工业出版社，2000年1月¢高质量C++/C编程指南http://man.chinaunix.net/develop/c&c++/c/c.htm#_Toc520634058实验中注意的一些问题¢注意指针的初始化初始化为0或NULL。¢在.h文件中函数的声明必须与.cpp文件中函数的定义相匹配包括函数名返回值类型参数类型和参数数量！¢同一工程中不能有两个main函数，否则会build错误！¢cannotopenDebug/XXX.exe这个是因为有一个XXX.exe正在运行！¢标识符使用之前一定要定义尽量使用有意义的

3、标识符！¢注意C或C++中数组下标是从0开始，最后一个元素的下标是length-1¢把自己修改过的地方加上注释，最好有一个大概思路。¢在叫助教之前请先按Ctrl+aALT+F8格式化代码¢大家可以学学基本的VC调试的方法掌握调试的几个基本功能：设置/取消断点运行到下一个断点单步执行和递归的进入函数。主要内容¢问题求解¢数据结构及抽象数据类型¢算法的特性及分类¢算法的效率度量¢数据结构的选择和评价问题求解¢阶段和步骤ß获取需求（问题），以保证解决的问题正是需要的（solvetherightproblem）；ß分析问题，将其分解为粒度更小的部分；ß针对问题（子问题

4、）给出相应的解决方案，易于理解和修改；ß估算解决方案的开销，以事先判断其可行性；¢利用数学等工具的辅助得到正确且简洁的解决方案ß维护和演化问题求解问题求解设计方法描述语言数据结构算法理论数据模型问题求解¢通过¢问题抽象¢数据抽象¢算法抽象分析问题，应用数据结构和算法来设计和实现高效的程序问题求解¢实质ß描述问题域中实际对象的数据及其相互关系ß映射到计算机的存储器上ß编写算法模拟对象领域中的求解过程问题求解¢计算机科学就是“一种关于信息结构转换的科学”(Wegnor)¢计算机科学是“算法的学问”(D.Knuth)¢其实数据结构与算法两者互为存在（数据结构离不开施

5、于其上的操作，同时算法也必然离不开作为其处理对象和结果的数据）问题求解¢例子：ß从一组人中找出最高、最矮，及身高最适中的人。ß有12个外表完全相同的球，只有一个不标准，或轻或重，要求用天平以最少的次数找出该球，并判定其轻重。ß计算机专业课程安排。¢问题抽象、数据抽象、算法抽象数据结构¢数据的逻辑结构逻辑结构ß图⊇树⊇二叉树⊇线性表¢数据的存储结构存储结构逻存ß顺序方法、链接方法辑数据储ß索引方法、散列方法结构¢数据的运算运算运ß增、删、查、改算ß排序、检索数据结构¢一类按照一定逻辑关系组织起来的数据的表示及其相关操作ß逻辑结构：表示数据元素之间的逻辑关系；ß存

6、储结构：数据结构在计算机存储器中的表示，也称存储表示；ß运算（结构的行为特征）：作用于数据结构上的运算。常见的基本数据结构：线性表，字符串，堆栈与队列，树与二叉树，字典，图数据的逻辑结构¢二元组B=(K,R)–K：结点（初等或组合类型）的有限集合–R:K上的有穷关系的集合（一组二元关系）ßK中每个结点都代表一个数据或一组有明确结构的数据ß关系集R中的每个关系(relation)r（r∈R）都是K×K上的二元关系，用以描述结点之间的逻辑关系–例如,r={

7、k∈K,1

8、，而全部人员组成结点集Kß家族的各类亲属关系就是一组关系R，其中如母系血缘关系r、远亲关系r*、和非血缘的亲情关系r’等等，每一个关系要给出具体人员的关系元组ß例如：母子关系（戴爱莲，张远）兄弟关系（张远，张立）妯娌关系（戴爱莲，李美英）结点类型：基本数据类型¢整数类型(integer)：规定了所能表示的整数范围，计算机一般用1个字节到4个字节来存储整数¢实数类型(real)：计算机的浮点数据类型所能表示的数值范围和精度是有限的。机器一般使用4到8个字节来存储浮点数¢布尔类型(boolean)：取值为真(true)和假(false)，在C++语言中一般使用整数

9、0表示false，用非0表示true结