数据结构(C语言)

《数据结构(C语言)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、广东交通职业基数学院计算机系课件设计数据结构（C语言）DATASTRUCTURE第页教材数据结构（C语言）曲建民刘元红郑陶然清华大学出版社参考教材1数据结构（C语言版）严蔚敏吴伟民清华大学出版社2数据结构题集（C语言版）严蔚敏吴伟民清华大学出版社第页课程特点及课时分配难度大综合性强必须下苦功学习课程说明考试每周4节，共20周评分标准：平时成绩20％（包括考勤、课堂回答问题等）、期中成绩30％，期末成绩50％第页教学内容第一章绪论第二章线性表第三章栈和队列第四章数组和串第五章树第六章图第七章内部排序第

2、八章查找第九章文件第页第一章绪论第页1.1什么是数据结构1.2基本概念和术语1.3运算、算法和算法分析主要知识点第页数据处理的种类和能力数据数值数据：数(整数,实数)非数值数据：字符字符串文字图形图象声音数据：客观对象的符号表示数学中的整数、实数，课程名，地名、书名1.1什么是数据结构数据结构要解决的问题第页数值问题与非数值问题1）数值问题例1已知：游泳池的长len和宽wide，求面积area◆设计求解问题的方法◆编程main(){intlen,wide,area;scanf(“%d%d%

3、”,&l,&w);area=len*wide;printf(“area=%d”,area);}◆建模型：问题涉及的对象：游泳池的长len宽wide，面积area；对象之间的关系：area=lenwide1.1什么是数据结构第页学号姓名性别出生日期籍贯入学成绩所在班级00201杨润生男82/06/01广州56100计算机200102石磊男83/12/21汕头51200计算机100202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机32）非数值问题

4、例2已知某级学生情况,要求分班按入学成绩排列顺序。在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性模型。1.1什么是数据结构第页城市间交通网问题1.1什么是数据结构第页数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。本课程讨论的问题：应用中常用的几种数据间的结构关系，及如何表示,如何存储，如何处理。1.1什么是数据结构第页数据：客观对象的符号表示。例如：学号，姓名，班名都是数据。数据元素：数据的基本单位。相当于“记录”,在

5、计算机程序中通常作为一个整体考虑和处理数据项:相当于记录的“域”,是数据的不可分割的最小单位。如：学号数据对象：性质相同的数据元素的集合.例如:所有班名相同的记录集合数据结构：是相互间存在关系的数据元素集合。1.2基本概念和术语第页对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：指对数据结构的加工处理数据的存储结构(物理结构)：数据结构在计算机内存中的表

6、示数据结构基本操作的实现：基本操作在计算机上的实现（方法)1.2基本概念和术语第页数据的逻辑结构通常有四种基本结构：集合线性结构树型结构图结构1.2基本概念和术语第页一、运算加工型运算插入运算删除运算更新运算应用型运算查找运算读取运算1.3运算、算法和算法分析第页二、算法及其描述算法是对求解某个问题的步骤的一种描述方法或操作序列。算法的基本特征：1）输入：0个或多个输入；2）输出：1个或多个输出；3）有穷性：算法必须在有限步内结束；4）确定性：组成算法的操作必须清晰无二义性。5）可行性：组成算法的操作必

7、须能够在计算机上实现。求两个正整数m，n中的最大数MAX的算法（1）若m>n则max=m（2）若m<=n则max=n例1.3运算、算法和算法分析第页描述算法的书写规则所有算法均以函数形式给出,算法的输入数据来自参数表参数表的参数在算法之前均进行类型说明有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明1.3运算、算法和算法分析第页评价算法标准算法的正确性，易读性，可维护性，健壮性，高效率等。算法时间复杂度T（n）本课程采用以求解问题的基本操作的执行次数作为算法时间的度量算法的空间复杂度S(

8、n)一个算法所需要辅助存储空间的多少为空间复杂度O（n3）称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；n阶矩阵相乘的算法For(i=1;i<=n;i++)For(j=1;j<=n;j++){c[i][j]=0;For(k=1;k<=n;k++)c[i][j]+=a[i][k]*b[k][j]}乘法加法执行次数均为n3例1.3运算、算法和算法分析第页有些算法，基本操作执行次数