北工大初试复试数据结构绪论.pptxVIP

1数据结构北京理工大学高春晓

2上课时间及安排《数据结构》上课时间（4-19周）学时安排课堂教学：40学时上机实验：16学时主讲教师：高春晓中心教学楼1045室

3教材和参考资料教材《数据结构（C语言版）》

——严蔚敏，吴伟民.清华大学出版社参考书《数据结构C++语言描述》

——刘卫东，沈官林译.清华大学出版社《数据结构与算法》 ——张铭，王腾蛟，赵海燕编.高等教育出版社习题参考数据结构题集（C语言版）

——严蔚敏，吴伟民.清华大学出版社

4第一章绪论

5ListofContents1.1数据结构的定义1.2数据结构的基本概念1.3算法和算法的量度

61.1数据结构的定义计算机程序处理输入数据输入结果计算机处理数学模型算法程序用计算机解决问题的过程（程序设计）程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:数据的组织与操作

71.1数据结构的定义NiklausWirth：Algorithm+DataStructures=ProgramsDataStructures=DataSet+Relations+Operations数据集+关系+操作VeryImportant！

数据结构研究的主要内容计算机处理的问题计算机处理数据的种类和能力数字(整数，实数)字符、文字、图形、图象、声音计算机应用数值领域?数值计算问题非数值领域?非数值计算问题8

9数值计算问题举例数值计算的程序设计问题例1：物体从100米高的塔顶落到地面的时间——二次方程例2：结构静力分析计算——线性代数方程组建模：涉及对象：高度h，时间t，重力加速度g（g=9.8）对象之间的关系：h=?gt2设计求解问题的方法：t=sqrt(2h/g)编程：main(){ floatt,h,g;g=9.8; scanf(”%f”,h);t=aqrt(2*h/g);printf(”Thefallingtimeis%f\n”,t);

}

10非数值计算的程序设计问题1例1：求一组整数(假设5个)中的最大值建模：涉及对象：5个整数对象之间的关系：大小关系设计求解问题的方法：基本操作是“比较两个数的大小”首先将第一个数记为当前最大值，然后依次比较其余n-1个整数，如果该某个整数大于当前最大值，就更新当前最大值。编程：

非数值计算的程序设计问题1例1：求一组整数(5个)中的最大值11main(){ intd[5],i,max; for(i=0;i5;i++) scanf(”%d”,d[i]);max=d[0];for(i=1;i5;i++) if(maxd[i])max=d[i];printf(”Themaxnumberis%f\n”,max);

}

12非数值计算的程序设计问题2例2已知研究生的选课情况，试设计安排课程的考试日程的程序。要求在尽可能短的时间内完成考试。ABCDEF算法分析形式语言计算机图形学模式识别网络技术人工智能杨润生石磊魏庆涛马耀先齐砚生选修1ACCDB选修2BDEFF选修3EFA

13非数值计算问题举例2:建模建立模型涉及对象：课程约束关系：同一学生选修的课程不能安排在同一时间考试模型：图——表达课程之间的约束关系ABCDEF算法分析形式语言计算机图形学模式识别网络技术人工智能杨润生石磊魏庆涛马耀先齐砚生选修1ACCDB选修2BDEFF选修3EFA

14杨润生石磊魏庆涛马耀先齐砚生选修1ACCDB选修2BDEFF选修3EFADCEBAF非数值计算问题举例2:建模图：顶点：表示课程；边：同一学生选修的课程用边连接

15非数值计算问题举例2:求解（着色法）每种颜色代表一个考试时间，用尽量少的颜色为顶点着色；着色原则：相邻顶点着不同颜色;不相邻顶点着相同颜色；着相同颜色的顶点（课程）安排在同一时间考试；考试日程：1:A,C2:B,D3:E4:FDCEBAFDCEBAF不冲突课程组{A,C}{B,D}{E}{F}

16非数值计算问题举例2:求解（着色法）求解考试日程的流程1)i=1;V={图中所有顶点的集合}

2)若V非空DO

置NEW为空集合；

在V中取一点，找出所有与之“不相邻”的顶点；将这些顶点加入NEW，从V中去掉这些顶点

（第i天考试