大学计算机基础第4章

《大学计算机基础第4章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章算法与基本数据结构基本概念基本数据结构常用算法一、数据结构概念1．什么是数据结构①数据：是对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储、加工的符号总称。第一节基本概念②数据元素：是数据的基本单位，由若干个数据项组成，在程序中作为一个整体而加以考虑和处理。数据元素具有完整确定的实际意义，有时也称为元素、结点、顶点或记录。③结构：是数据元素之间的关联关系。通俗地说：数据结构是带有结构的同性质数据元素的集合。2．数据结构研究的三个方面：逻辑结构、存储结构、和对数据的操作1）逻辑结构：数据元素之间逻辑上的

2、关系，它是数据的组织形式。通常将数据的逻辑结构简称为数据结构，数据的逻辑结构分成如下的四种结构：A：集合B：线性结构C：树型结构D：图状结构其中C、D为非线性结构集合线性结构树型结构图状结构2）存储结构：数据元素以及数据元素之间的逻辑关系在计算机内存中的表示。一般地，一个存储结构包括以下两个主要部分：①数据元素的存储：用一个存储单元(简称结点)存放每一个数据元素,每个存储单元称为一个结点。②数据元素之间关系的存储：也就是逻辑结构在计算机内部的表示。③数据的四种常用的存储结构：顺序存储方法链式存储方法索引存储方法散列存储方法3）数

3、据的运算：查找，排序、增加，修改，删除等，这些运算都是逻辑结构上的操作。二、算法的概念1、算法算法是对具体问题求解过程和步骤的一种描述。例1：比较两个数a,b，将两个数中大的数显示出来。操作步骤：1）输入两个数a,b的值2）比较a,b两个数，如果a大于b，则输出a的值；否则输出b的值。实现的代码：Input“输入a的值:”toaInput“输入b的值:”tobIfa>b?aElse?bEndif2、算法的5个特性。①有穷性②确定性③可行性④零个或多个的输入⑤有1个或多个的输出3．算法设计的要求①正确性②可读性③健壮性④效率高与低

4、存储量需求4、算法性能描述算法的时间复杂度和空间复杂度算法的时间性能时间复杂度：是指算法中所包含简单操作的执行次数。一般是算法中执行频度最大的语句频度。空间复杂度：指算法执行过程中所占用的存储空间。时间复杂度和空间复杂度都与问题的规模n有关，可以采用T(n),S(n)表示。常见的时间复杂度，按数量级递增排列依次为：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)。求1~100个数据的和值。main(){inti,s;i=1,s=0;while(){}Printf(“s=%

5、d”,s);}比较两个数据a,b，将大的数据保存在a变量中。Main(){inta,b,c;scanf(“%d%d”,&a,&b);if(a

6、r;}while(r!=0);printf(“%d”,m);}5、算法的描述方法：描述问题求解的执行过程及顺序。用自然语言描述用流程图描述：主要是采用一些图形符号和带箭头的流程线表示算法。图形符号参见课本P71。开始输入a,b的值a>b输出a的值输出b的值结束YN比较a,b的值，输出两个数中大的数的流程图第二节基本数据结构一、线性表1、线性表:是n(n≥O)个同类型数据元素(结点)的有穷序列。表示成：(a1，a2…，an)，n为0则为空表。例如：12344357627433239026个英文字母表（A,B,C,D,……Z）2、线

7、性表逻辑结构的基本特征①存在惟一的一个被称为“第一个”的数据元素；②存在惟一的一个被称为“最后一个”的数据元素；③除第一个结点外，其他结点有且仅有一个直接前趋；④除最后一个结点外,其他结点有且仅有一个直接后继。⑤所含结点的个数称为线性表的长度(简称表长)。表长为O的线性表称为空表。3、线性表的顺序存储结构用一组地址连续的存储单元依次存储线性表的数据元素，该结构称为顺序表。元素a1a2…………ai-1aiai+1……an相对地址12…………i-1i……n-1n特点：逻辑结构中相邻的结点在存储结构中仍相邻。102030405060…

8、…78若顺序存放10,20,30,40,50,60,其物理存储结构如下：3001300230033004300530063007……3200内存地址存储单元返回4、顺序表的插入和删除运算在顺序表上实现插入和删除运算必须移动结点才能够反映出结点间逻辑关系的变化。元