数据结构及算法84061

《数据结构及算法84061》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构及算法课程名称：数据结构及算法预修课程:C语言,高等数学教材：1.《数据结构》(C语言版)清华大学出版社19972.《数据结构题集》(C语言版)清华大学出版社1999教师：徐镜春xjcsj01@dlc.zju.edu.cn关于习题与实验题教材中习题放在每章结束,但学生在每周都应该完成与上课内容相应的部分小题有精力的同学应该思考《数据结构题集》中未列为必做的练习,这会有助于理解课程内容习题包括理论习题和上机实验题实验题要求用C语言编写,并在计算机上调试通过实验报告至少应包括题目算法步骤源程序(不太多时写在作业本上)运算结果及分析调试过程与体会第一章绪论1．1什么是数

2、据结构1．2基本概念和术语1．3抽象数据类型的表示与实现1．4算法和算法分析1．4．1算法1．4．2算法设计的要求1．4．3算法效率的度量1．4．4算法的存储空间需求1.1什么是数据结构计算机解决问题的步骤实际问题---数学模型---算法---程序---结果工程师数学家程序员计算机的用途科学计算(数值运算):解方程(组),函数求值,概率统计等非数值运算:字符,表格,图象,声音等计算机的用途---数值运算水库大坝的应力计算预报人口增长天气预报计算机的用途---非数值运算书目检索系统多叉路口的交通灯管理问题有连线的节点用不同的颜色标记,表示不能同时通行.要求使用的颜色数尽可能

3、少,以使减少等待时间.图论中的四色问题.多叉路口的交通灯管理问题不能同时通行的通路用连线把它们连起来,它们有:A->B通路:CA,BD,BCA->D通路:CB,BCB->C通路:AB,ADB->D通路:AB,CBC->A通路:ABC->B通路:BD,AD计算机的用途---非数值运算计算机与人对奕问题数据结构的定义描述非数值计算问题的模型是---如表、树、图之类的数据结构数据结构是---研究计算机的操作对象(数据)以及它们之间的关系和操作等的学科.学科《数据结构》在计算机科学中所处的地位综合性的专业基础课1.2基本概念和术语数据：计算机程序处理的符号的总称。数据元素：数据的

4、基本单位。通常作为一个整体进行处理。数据项：数据的不可分割的最小单位。一个数据元素可以由若干个数据项构成。数据对象：性质相同的数据元素的集合。数据结构：相互间存在一种或多种关系的数据元素的集合。数据元素相互关系-----称为“结构”四类基本结构集合线性结构树型结构图状结构（网状结构）数据结构的数学定义数据结构是一个二元组Data_Structure=(D,S)D–数据元素的有限集合S–定义在D上的关系的有限集合例如Complex=(C,R)C={(c1,c2)

5、c1,c2是实数}R={P

6、P是定义在C上的关系，表示c1是实部,c2是虚部}逻辑结构和物理结构

7、逻辑结构:数据元素之间的逻辑关系物理结构:数据结构在计算机中的表示,又称存储结构算法的设计取决于选定的逻辑结构算法的实现依赖于采用的存储结构数据类型与抽象的数据类型数据类型（DataType）：值的集合以及定义在这个集合上的一组操作。例如:C语言中的整数类型抽象数据类型(ADT)数学模型以及定义在该模型上的一组操作。与其在计算机中的表示和实现无关。ADT可用三元组表示：（D,S,P）D–数据对象;S–D上的关系;P–对D的基本操作集抽象数据类型的定义格式：ADT抽象数据类型名{数据对象：＜数据对象的定义＞数据关系：＜数据关系的定义＞基本操作：＜基本操作的定义＞｝ADT抽

8、象的数据类型名基本操作的定义格式为：基本操作名（参数表）初始条件：＜初始条件描述＞操作结果：＜操作结果描述＞抽象数据类型三元组的定义ADTTriplet{数据对象：D={e1,e2,e3

9、e1,e2,e3属于Elemset(定义了关系的某个集合)}数据关系：R1={＜e1,e2＞

10、＜e2,e3＞}基本操作：InitTriplet(&T,v1,v2,v3)初始条件:操作结果:构造三元组T,元素e1,e2和e3分别被赋予参数v1,v2和v3的值。抽象数据类型三元组的定义(2)DestroyTriplet(&T)初始条件:三元组T已经存在。操作结果:销毁三元组T。Get(T

11、,i,&e)初始条件:三元组T已经存在,1<=i<=3。操作结果:用e返回三元组T的第i个元素。Put(&T,i,e)初始条件:三元组T已经存在,1<=i<=3。操作结果:用e值取代三元组T的第i个元素。抽象数据类型三元组的定义(3)IsAscending(T)初始条件:三元组T已经存在。操作结果:如果三元组T的三个元素按升序排列,则返回TRUE;否则返回FALSE。IsDescending(T)初始条件:三元组T已经存在。操作结果:如果三元组T的三个元素按降序排列,则返回TRUE;否则返回FALSE。抽象数据类型三元组的定义