资源描述：
《chap01数据结构前言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构•任课老师：黄煜廉•邮箱：e_win2003@yahoo.com.cn课程要求•课堂讲授：提问、讨论、小测•实验课程：20个作业习题+3个大实验•课程成绩：实验(30%)+期末考试(70%)•期末考试：以实验内容为主(80%)参考书•计算机程序设计艺术(ArtofComputerProgramming)DonaldE.Knuth著译者:苏运霖出版社:国防工业出版社•数据结构C++语言描述WilliamFord著清华大学出版社•数据结构严尉敏,吴伟民著清华大学出版社问题求前n项的和值：1+2+…+
2、n=?方法一：数学公式法方法二：顺序处理法方法三：分解方法编程与数学的问题问题1:六名间谍被擒，已知懂汉语、法语和日语，懂德语、俄语和日语，懂英语和法语，懂西班牙语，懂英语和德语，懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。数学模型的建立•解：以六人为顶点，懂共同语言，则在顶点间连边得下图。因为图中没有长度为奇数的回路，所以是二部图，故至少应有两间房间即可。•问题2：田径赛的时间安排问题姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅
3、球200M跳高王5跳远200M数学模型的建立解：该问题归结为图顶点的上色问题，因此根据题目给定的已知条件建立起图模型。跳高跳远姓名项目1项目2项目3丁1跳高跳远100M100M马2标枪铅球张3标枪100M200M200M李4铅球200M跳高王5跳远200M铅球标枪问题3：7位客人入席,A只会讲英语,B会讲英,汉语,C会讲英,意大利,俄语,D会讲日,汉语,E会讲德,意大利语,F会讲法,日,俄语,G会讲法,德语.能否安排圆桌席位使每位客人与其左右邻不用翻译便可交谈?数学模型的建立解:首先建立无向图模型:结点
4、为客人;会共同语言的2结点相邻接.则问题归结为求此图的一条Hamilton回路.此图存在一条Hamilton回路是:(A,B,D,F,G,E,C,A).按此回路安排席位可满足要求.AG法英德FB英俄汉日意CED总结•首先建立数学模型；•接着思考如何设计算法实现该数学模型。有问•疑问：题啦？•（1）如何建立数学模型？可以建立什么方面的数学模型？•（2）如何设计算法呢？要考虑什么方面的问题呢？逻辑结构——数学模型•数据之间的相互关系称为逻辑结构。通常分为四类基本结构：•1.集合结构中的数据元素除了同属于一种
5、类型外，别无其它关系。•2.线性结构结构中的数据元素之间存在一对一的关系。•3.树型结构结构中的数据元素之间存在一对多的关系。•4.图状结构或网状结构结构中的数据元素之间存在多对多的关系。•逻辑结构的描述方法：数学方法（关系和关系图）线性结构结论：线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素)例：电话号码查询问题例：电话号码查询问题方法方法11：顺序存储，顺序查找：顺序存储，顺序查找非线性结构选课单包含如下信息学学号号课程编号课程编号成成绩绩时时间间学生选课系统中实体构
6、成的网状关系学生选课系统中实体构成的网状关系结论：非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个UNIX文件系统的系统结构图树形结构树树二叉树二叉树二叉搜索树二叉搜索树堆结构大根堆大根堆小根堆小根堆图结构图结构网络结构网络结构存储结构•数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。•存储结构的种类：•顺序存储•链式存储•索引存储•散列存储1.2算法和算法分析•算法：是对特定问题求解步骤的一种描述.算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性
7、：•（1）有穷性•（2）确定性•（3）可行性•（4）输入•（5）输出算法的描述方法•自然语言•程序设计语言•类语言算法的评价标准•评价一个好的算法有以下几个标准:•(1)正确性(Correctness)算法应满足具体问题的需求。•(2)可读性(Readability)算法应该好读。以有利于阅读者对程序的理解。(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。•(4)时间（时间复杂度）•(5)空间（空间复杂度）时间复杂度1.x=a;
8、a=b;b=x;2.s=0；for(i=0;i
