数据结构(c语言版)第1章绪论.

第1章绪论数据结构卢冰邮箱：[e-mail]电话：[phone]第1章绪论参考书目•数据结构（C语言版）严蔚敏清华大学出版社•数据结构陈越高等教育出版社•数据结构与算法分析MarkAllenWeiss人民邮电出版社第1章绪论1.1什么是数据结构?1.2数据结构的基本概念和术语1.3算法和算法分析1.4关于学习数据结构第1章绪论第1章绪论数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。——严蔚敏《数据结构》数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。——百度百科在计算机科学或信息科学中，数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。——维基百科1.1什么是数据结构?第1章绪论例1：如何在书架上摆放图书？第1章绪论例1：如何在书架上摆放图书？图书的摆放要使得两个相关操作方便实现：操作1：新书怎么插入？操作2：怎么找到某本指定的书？第1章绪论例1：如何在书架上摆放图书？方法1：随便放操作1：新书怎么插入？哪里有空放哪里，一步到位！操作2：怎么找到某本指定的书？……累死！第1章绪论例1：如何在书架上摆放图书？方法2：按照书名的拼音字母顺序排放操作1：新书怎么插入？新进一本书《阿拉伯的劳伦斯》……操作2：怎么找到某本指定的书？二分查找！第1章绪论例1：如何在书架上摆放图书？方法3：把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放。操作1：新书怎么插入？先定类别，二分查找确定位置，移出空位操作2：怎么找到某本指定的书？先定类别，再二分查找！问题：空间如何分配？类别应该分多细？第1章绪论解决问题方法的效率，跟数据的组织方式有关第1章绪论例2：写程序实现一个函数PrintN，使得传入一个正整数参数N后，能顺序打印从1到N的全部正整数。voidPrintN(intN){inti;for(i=1;i=N;i++)printf(%d\n,i);return;}循环实现voidPrintN(intN){if(!N)return;PrintN(N-1);printf(%d\n,N);return;}递归实现令N=100,1000,10000,100000……第1章绪论循环实现递归实现#includestdio.hvoidPrintN(intN);intmain(){intN;scanf(%d,&N);PrintN(N);return0;}第1章绪论解决问题方法的效率，和空间的利用效率有关第1章绪论例3：求阶乘和第1章绪论#includestdio.hintmain(){inti,n,fact,sum;scanf(%d,&n);sum=0;fact=1;for(i=1;i=n;i++){fact*=i;sum+=fact;}printf(%d\n,sum);return0;}#includestdio.hintfact(intn);//自定义求阶乘函数intmain(){inti,n,sum;scanf(%d,&n);sum=0;for(i=1;i=n;i++){sum+=fact(i);}printf(%d\n,sum);return0;}这个程序如何？这个程序要比第一个好第1章绪论解决问题方法的效率，和算法的巧妙程度有关第1章绪论所以，到底什么是数据结构？数据对象在计算机中的组织方式逻辑结构物理存储结构数据对象必定与一系列加在其上的操作相关联完成这些操作所用的方法就是算法。第1章绪论1.2数据结构的基本概念和术语1.数据（Data数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。简而言之，数据就是计算机化的信息。第1章绪论2.数据元素（DataElement）数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成（DataItem）。表1.1学籍表学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京………………数据项记录第1章绪论3.数据对象（DataObject）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。第1章绪论综上1~3所述，再分析数据概念：第1章绪论4.数据结构（DataStructure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合，数据元素相互之间的关系称为结构（Structure），有四种基本结构。学校组织层次结构图学校系处研究机构教研室实验室第1章绪论交通流量图15342第1章绪论•逻辑结构：数据之间的相互关系(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。第1章绪论逻辑结构线性结构——线性表、栈、队、字符串、数组、广义表非线性结构——树、图第1章绪论数据结构是一个二元组Data_structure=(D,S)其中：D为数据结构的有限集，S是D上关系的有限集。数学模型抽象数据类型建立数据结构编写源程序逻辑结构第1章绪论例：一年四季名称所组成的数据结构可以表示为：B=(D,R)D={春，夏，秋，冬}R={春，夏,夏，秋,秋，冬}第1章绪论例：假设家庭成员组成的数据结构可以表示成：B=(D,R)D={祖父，叔叔，父亲，儿子，女儿，孙子}R={祖父，父亲,祖父，叔叔,父亲，儿子,父亲，女儿,儿子，孙子}第1章绪论•存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。第1章绪论逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。第1章绪论•顺序映象（顺序存储结构）顺序映象用元素在存储器中的相对位置表示数据元素之间的逻辑关系。•非顺序映象（非顺序存储结构）非顺序映像借助指示元素存储地址的指针表示元素之间的逻辑关系。用一维数组来描述顺序存储结构，用指针来描述链式存储结构。第1章绪论5.数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。第1章绪论6.抽象数据类型（AbstractDataType）数据类型数据对象集数据集合相关联的操作集抽象：描述数据类型的方法不依赖于具体实现与存放数据的机器无关与数据存储的物理结构无关与实现操作的算法和编程语言均无关ADT只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。第1章绪论例4：线性表的抽象数据类型定义ADTList{数据元素：D={ai|ai∈ElemSet,i=1,2,…，n,n≥0，ElemSet为某一数据对象}数据关系：Ｓ＝｛ai,ai+1|ai,ai+1∈D，i=1,2,…,n-1}基本操作：InitList（L）:初始化线性表。Length(L):求线性表的表长;Get(L,i):取线性表的第i个元素；Insert(L,i,b):在线性表的第i个位置插入元素b；Delete(L,i):删除线性表的第i个元素。}ADTList第1章绪论1.3算法和算法分析1.算法（Algorithm）算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。第1章绪论2.算法的特性(1)有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(2)确定性：组成算法的每条指令是清晰的，无歧义的。(3)可行性：原则上能精确进行，操作可通过已实现的基本运算执行有限次而完成。(4)输入：有多个或0个输入。(5)输出：至少有一个或多个输出。在算法的五大特性中，最基本的是有穷性、确定性和可行性。第1章绪论3.算法设计的要求１）算法的正确性(1)所设计的程序没有语法错误；(2)所设计的程序对于几组输入数据能够得出满足要求的结果；(3)所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。(4)程序对于一切合法的输入数据都能产生满足要求的结果。第1章绪论例如：求n个正整数的最大值问题，给出示意算法如下：max=0;for（i=1;i=n;i++）{scanf(″%d″,&x);if(xmax)max=x;}第1章绪论2）可读性3）健壮性4）高效率和低存储第1章绪论程序：程序与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的“有穷性”这个性质。例如：操作系统是一个在无限循环中执行的程序，因而不是一个算法。然而可把操作系统的各种任务看成是一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，该子程序得到输入结果后便终止。第1章绪论对算法作性能评价空间复杂度S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。时间复杂度T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。第1章绪论1）一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。第1章绪论2）语句频度是指该语句在一个算法中重复执行的次数。例：两个n×n阶矩阵相乘。第1章绪论3）原操作是指从算法中选取一种对所研究问题是基本运算的操作，用随着问题规模增加的函数来表征，以此作为时间量度。而对于算法分析，我们关心的是算法中语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级（OrderofMagnitude）。在这里，我们用“O”来表示数量级，这样我们可以给出算法的时间复杂度概念。所谓算法的渐进时间复杂度，即是算法的时间量度，记作：T(n)=O(f(n))第1章绪论T(n)=O(f(n))一般情况下，随n的增大，T(n)的增长较慢的算法为最优的算法。分析的基本策略是从内部（或最深层部分）向外展开工作。第1章绪论一般法则法则1：for循环一个for循环的运行时间至多是该for循环内语句的运行时间乘以迭代的次数。法则2：嵌套循环从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。法则3：顺序语句将各个语句的运行时间求和即可（这意味着，其中的最大值就是所得的运行时间）法则4：if-else语句一个if-else语句的运行时间从不超过判断再加上if部分和else部分中运行时间较长者的总的运行时间。第1章绪论例如：（1）x=x+1；其时间复杂度为O(1)，我们称之为常量阶；（2）for(i=1;i=n;i++)x=x+1;其时间复杂度为O(n)，我们称之为线性阶；（3）for(i=1;i=n;i++)for(j=1;j=n;j++)x=x+1;其时间复杂度为O(n2)，我们称之为平方阶。第1章绪论4）数据结构中常用的时间复杂度频率计数有7个：O(1)常数型O(n)线性型O(n2)平方型O(n3)立方型O(2n)指数型O(log2n)对数型O(nlog2n)一般情况下