关于数据结构的基本介绍和基础内容

《关于数据结构的基本介绍和基础内容》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构信息与计算科学专业一、任课教师简介姓名：郭荣伟联系电话：13173006561二、课程要求1、本课程总评成绩的计算算法：总成绩=平时成绩*30%+期末成绩*70%；平时成绩（100分）=出勤（30）+作业（40）+随堂上机（30）；2、出勤的统计方法是随机抽查和全查，无故缺勤一次扣10分，累计三次无考试资格；请假必须提前通知任课老师，并具有班主任或者辅导员签字的假条，视具体情况扣分，原则上不会超过5分，补假无效。三、本课程简介数据结构是信息与计算专业的一门专业基础课，其目的是要学习和逐步掌握各种数据结构和算法，培养设计算法和开发程序的能力，达到能够根据实际问题的需要，选择适当

2、的数据结构及设计出相应的算法，并通过上机实验，编写出程序。本课程的主要任务是进一步锻炼学生的动手能力，提高学生分析和解决实际问题的能力。本课程的主要内容有各种线性表的介绍，如栈和队列，串；树的介绍和应用，图的介绍和应用，各种查找和排序算法以及相应的算法设计和分析。本课程达到的要求是掌握各种数据结构的逻辑机构和物理结构，以及相应的各种算法。达到对给定一个具体的问题，能设计出合适的数据结构，选择恰当的算法，并且编写出具体的实现程序，同时还能书写出规范的程序说明书。第1章绪论本章主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常用术语教学重点：熟悉数据结构常用术语，掌握

3、基本概念，了解算法时间复杂度和空间复杂度的分析与评价教学难点：数据元素间的4种结构关系。主要内容：1.1什么是数据结构1.2算法描述1.3算法分析与评价计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：1.信息的表示,2.信息的处理而信息的表示又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多

4、数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数

5、据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题见课本通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。1.2基本概念和术语数据(Data):是对信

6、息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据类型：在一种程序设计语言中，变量所具有的数据种类。例、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举

7、型、自定义数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。四类数据基本结构的示意图：(a)集合结构(b)线性结构(c)树型结构(d)图形结构数据结构的形式定义为：数据结构是一个二元组：Data-Stru