datastructure数据结构第1章

《datastructure数据结构第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构DATASTRUCTURE——使用C语言学时数：40教材：数据结构—使用C语言西安交通大学出版社朱战立，刘天时数据结构的基本概念数据类型和抽象数据类型C语言的数据类型用C语言描述算法的注意事项算法设计目标和算法效率度量第一章绪论1.1数据结构的基本概念数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}学生数据对象:初等项（不可分割）、组合项（可再划分）数据元素

2、：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位）数据类型：具有相同性质的计算机数据集合及在这个集合上的一组操作。数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构依据视点的不同，分为数据逻辑结构和物理结构：逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视

3、图，是面向计算机的。关系：物理结构是逻辑数据的存储映象逻辑结构：线性结构非线性结构物理结构：顺序存储链接存储索引存储散列存储“学生”表格“课程”表格线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素)例：电话号码查询问题方法1：顺序存储，顺序查找方法2：有序顺序存储，二分查找姓名地址李1李2……张1张2……王1王2……方法3：部分有序，建立索引表姓名地址李1李2……张1张2……王1王2……姓地址李张……非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个选课单包含如下信息学号课程编号成绩时间学生选课系统中实体构

4、成的网状关系UNIX文件系统的系统结构图树形结构树二叉树二叉搜索树堆结构“最大”堆“最小”堆图结构网络结构例：田径赛的时间安排问题姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M跳高跳远标枪铅球200M100M1、任一选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。本课程讨论：在解决问题时可能遇到的典型的逻辑结构（数据结构）逻辑结构的存储映象（存储实现）数据结构的相关操作及其实现。1.2数据类型和抽象数据类型数据类型定义：一个数据的集合,以及定义于这

5、个数据集合上的一组操作的总称。C语言中的数据类型基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型抽象数据和抽象数据类型(ADTs:AbstractDataTypes)由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离（物理实现封装）ADT：抽象数据类型名数据对象：数据对象的定义数据关系：数据逻辑关系的定义基本操作：基本操作的定义抽象数据类型的定义：操作名（参数表）操作结果：操作结果描述基本操作的定义：抽象数据类型1.3C语言的数据类型1、基本数据类

6、型intshort;long;unsignedfloatfloat;double;longdouble2、指针类型3、数组类型4、字符串5、结构体类型6、共用体类型7、枚举类型8、自定义类型1.4用C语言编写算法的注意事项1、避免使用出现二义性的表达式i++;i=++i;i=1;j=i+++i--;2、避免使用转向语句3、避免使用预处理4、避免函数返回值隐含说明1.5算法设计目标和算法效率度量定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列特性：输入有0个或多个输入输出有一个或多个输出(处理结果)确定性每步定义都是确切、无歧义的有

7、穷性算法应在执行有穷步后结束有效性每一条运算应足够基本算法的描述:c++,c,PASCAL等语言算法有这样一些特点：1、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。2、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。3、有零个或多个输入4、有一个或多个输出5、有效性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。例如：被零除的计算动作是不能被有效执行的。设计算法的基本方法:把一个具体问题转变成一个算法事例学习：选择排序问题明确问题：非递减排序解决方案：逐个选择最

8、小数据算法框架：for(inti=0;i