资源描述：
《数据结构与程序设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构与算法林小拉电话：84112133Email:linxl@mail.sysu.edu.cn课程安排讲授3学时/周，实验2学时/周（分组）总成绩：平时（听课、作业、期中）+期末教学用书：RobertL.KruseandAlexanderJ.Ryba“DataStructuresandProgramDesigninC++”，高教出版社，2001年参考书：1．数据结构，许卓群，张乃孝，杨冬青，唐世渭，高等教育出版社，1987年2.数据结构–C++与面向对象的途径，张乃孝，裘宗燕，高等教育出版社，1998年3．数据结构(C语言版），严蔚敏、吴伟民，清华大学出版社，1997年4.数据结构与算法，
2、王若梅等著，中山大学出版社，2000年为什么学习数据结构计算机科学是--“一种关于信息结构转换的科学”(Wegnor)InputOutput--“算法的学问,算法是精确定义的一系列规则,指出怎样从给定的输入信息经过有限步骤产生所求的输出信息”(Knuth)信息结构(数据结构)和算法是计算机科学的核心课题.两者之间有着本质的联系.数据结构+算法=程序Computersystem程序=算法+数据结构数据结构：一种程序构件（programmingconstruct)、工具;编程中常用的数据组织形式及其操作的抽象；编程：数据结构的选择，算法的设计与度量教学目的掌握常用的数据结构及其应用学会合理地组织数
3、据，有效地表示数据和处理数据掌握算法设计技术和分析技术提高程序设计质量第一章概论什么是数据结构抽象数据类型算法的概念算法的度量数据结构示例数据结构的概念数据的逻辑结构数据的存储结构什么是数据结构-示例1例1图书馆的书目自动检索系统所处理的基本数据（数据元素）：每本书由（登录号，书名，作者，出版社,分类号)组成；数据元素间的关系（逻辑结构）：一个按登录号顺序排列的书目表和按书名、作者和分类号顺序排列的索引表；所需的操作：一组作用在这些表上的运算（查询、插入、修改等）；怎样存储这些数据及其关系使得上述操作容易实现—存储结构。什么是数据结构-示例2例2人机对弈问题（三子棋）。数据元素：格局（某时刻的
4、棋盘布局）；格局之间的关系：一个格局可以派生出几个下一个格局（树状结构， 博弈树）；操作：由某个格局出发，借助于以上的格局树（显式地或非显式地）找出计算机赢的步骤；存储结构：如何存储格局及其格局间的关系。什么是数据结构-示例3例3多岔路口的交通灯管理系统。BACDE数据元素：通路，如：A->B通路间的关系（图）：通路为结点，两节点相邻，如果两通路不能同时通行。操作：上图的着色问题：用最少的颜色，对每个节点着色，相邻节点着不同的颜色。存储：如何存储通路间的关系。第一章概论什么是数据结构抽象数据类型算法的概念算法的度量数据结构示例数据结构的概念数据的逻辑结构数据的存储结构数据结构的概念数据是客观事
5、物的符号表示，是信息的载体数据元素是数据的基本单位数据结构是相互间具有某些关系的数据元素的集合。它包括下面三方面的内容：1）数据的逻辑结构，表示数据元素间的关系；2）数据的运算，是数据元素集上所允许的操作；3）数据的存储结构，指如何在计算机上数据元素及其关系。第一章概论什么是数据结构抽象数据类型算法的概念算法的度量数据结构示例数据结构的概念数据的逻辑结构数据的存储结构数据的逻辑结构数据的逻辑结构是一个二元组（D,R),D是数据元素的有限集，R是D上关系的有限集；例如，在示例3中，D={AB,AC,AD,BA,BC,BD,DA,DB,DC,DA,EB,DC,ED}R={R1}R1={(AB,EA
6、),(AB,BD),(AB,DA),(AB,BC),…}逻辑结构的类型我们将讨论R含有一个关系的情况,即R={R1}.根据R1的特性,数据结构(D,{R1})可分为下列几种:D={d1,d2,…,dn}1.集合:数据元素同“属于一个集合”.R1={}2.线性结构:R1={(d1,d2),(d2,d3),…,(d(n-1),dn)},即除开始和终结节点d1,dn外,每个节点有一个前驱和一个后继3.树状结构:(D,{R1})构成树,即每个元素最多有一个前驱,可以有多个后继4.图状结构:(D,{R1})构成一个图.第一章概论什么是数据结构抽象数据类型算法的概念算法的度量数据结构示例数据结构的概念数据
7、的逻辑结构数据的存储结构数据的存储结构数据（逻辑）结构的存储包含数据元素的存储及其逻辑关系的存储设M为内存的一片存储区域.将数据结构存储到计算机内,我们需要建立一个映射(存储映像):S:D->M即对于D中的每个数据元素d,S(d)∈M,并且这个映射具有明显地或者隐含地体现R的能力.根据存储映像的特点,存储结构可分为:顺序存储结构、链式存储结构、索引和散列等。存储结构的分类:顺序结构顺序的方法:将逻
