数据结构-项目1

数据结构项目一共分为二个任务项目一数据结构导论任务一数据结构入门任务二算法与算法分析任务一数据结构入门一、基本术语二、数据的逻辑结构三、数据的存储结构四、数据类型一、基本术语1．数据2．数据元素3．数据项4．数据对象5．数据结构1．数据数据（data）是对客观事物的符号表示，在计算机科学中，是指所有能输入到计算机中并被计算机程序处理的符号的总称。2．数据元素数据元素（dataelement）是数据的基本单位，一个数据元素可由若干个数据项组成，此时的数据元素通常称为记录（record）。3．数据项数据项（dataitem）是数据不可再分的最小单位，如学生信息记录中的学号、姓名等。4．数据对象数据对象（dataobject）是性质相同的数据元素的集合，是数据的一个子集。5．数据结构数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。一般包括三个方面的内容：①

数据的逻辑结构

②

数据的物理结构

③

数据的运算及实现

二、数据的逻辑结构数据元素之间除了同属于一个集合外，别无其他关系。数据元素之间是一对一的关系。每个数据元素都有唯一的前驱（第一个元素除外）和后继（最后一个元素除外）。数据元素之间是一对多的关系。在树形结构中，最上面的结点称为根节点，最下面的结点称为叶子结点。数据元素之间是多对多的关系。每个结点都可以有多个前驱或后继。三、数据的存储结构数据的存储结构或物理结构是指数据在计算机中的表示或存储方式，是逻辑结构在计算机中的实现，包括数据元素的表示和关系的表示。1．顺序存储结构2．链式存储结构1．顺序存储结构顺序存储结构是指逻辑上相邻的数据元素，其结点的物理位置（内存中的位置）也相邻，结点间的逻辑关系由存储单元的邻接关系体现。2．链式存储结构在链式存储结构中，结点间的逻辑关系由附加的指针字段来指示的，因此，链式存储结构通常借助于程序设计语言中的指针数据类型来实现。四、数据类型1．数据类型2．抽象数据类型1．数据类型数据类型（datatype）是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用来描述操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个确定的数据类型。2．抽象数据类型抽象数据类型（abstractdatatype，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。ADT抽象数据类型名{数据元素：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>}ADT抽象数据类型名其格式定义如下：任务二算法与算法分析一、算法的概念二、算法的特性三、算法的描述方法四、算法设计的要求五、算法性能分析六、类C语言简介一、算法的概念在计算机领域，根据所要处理的问题，在数据的逻辑结构和物理结构基础上，在有限步骤内解决这一问题所采用的一组指令序列。在实际生活中，算法就是为解决某一问题所采取的方法和步骤。二、算法的特性有限性：有限步骤之内正常结束，不能形成无穷循环。确定性：算法中的每一个步骤必须有确定含义，不能有二义性。可行性：算法中的每一个步骤都应当能有效执行，并得到确切结果。输入：有0个或多个输入。输出：至少有一个或多个输出。三、算法的描述方法1．自然语言2．流程图3．伪代码4．程序设计语言【例】要求一组数据中的最大数和最小数。1．自然语言③重复步骤②，与第4、5等数进行比较，直至结束。①将第1个数和第2个数相比较，记录最大数与最小数。②将最大数和最小数与第3个数比较，记录最大数与最小数。2．流程图3．伪代码开始置i的初值为2置Min和Max的初值为a1当i≤n时，执行如下操作如果Min>ai,则使Min=ai

如果Max<ai,则使Max=ai

i=i+1（循环体到此结束）打印Max和Min值结束4．程序设计语言main(){

inta[5]={50,23,89,12,90};//定义含有五个整数元素的数组

inti=1;//i为指示器，初始指向第2个数组元素

intMax,Min;//定义两个变量，用来保存当前的最大值和最小值

Max=a[0];//令当前的最大值为第1个数组元素

Min=a[0];//令当前的最小值为第1个数组元素

while(i<=4)//i≤4时循环

{if(Min>a[i])//如果当前数组元素小于当前最小值，则将当前数组元素值赋于当前最小值变量

Min=a[i];if(Max<a[i]) //如果当前数组元素大于当前最大值，则将当前数/组元素值赋于当前最大值变量

Max=a[i];i=i+1; //循环变量递增1}printf("themaximumis%d,theminimumis%d",Max,Min);}四、算法设计的要求正确性：“正确”的含义可以分为三个层次：①对于几组输入数据能够得出满足要求的结果。②对于精心选择的典型、苛刻且带有刁难性的几组输入数据能够得到满足要求的结果。③对于一切合法的输入数据都能产生满足要求的结果。可读性：算法主要是为了人的阅读与交流，其次才是机器执行。因此，可读性好有助于人对算法的理解。高效率低存储量：通俗地说，效率指的是算法执行的时间。对于同一个问题，若有多个算法可以解决，执行时间短的算法效率就高。存储量指的是算法执行过程中所需要的最大存储空间。稳健性：当输入数据非法时，算法也能做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。五、算法性能分析算法分析是每个程序设计人员应该掌握的技术。评价一个算法的优劣主要看执行这个算法所需的时间（时间复杂度）和存储空间（空间复杂度）。1．时间复杂度2．空间复杂度1．时间复杂度时间复杂度是指该算法的运行时间与问题规模的对应关系，记作T(n)＝O(f(n))其中，n表示问题的规模；T(n)表示算法中语句的执行次数（称为语句频度或时间频度）；f(n)为辅助函数；O(f(n))表示f(n)是T(n)的同数量级函数。2．空间复杂度一个程序在计算机上执行时，除了需要存储本身所用的指令、常数和输入数据以外，还需要一些对数据进行操作的辅助存储空间。因此，一个算法（程序）的空间复杂度是指程序运行从开始到结束所需的存储空间，记作