NOIP高中信息技术竞赛资料——数据结构.doc
《NOIP高中信息技术竞赛资料——数据结构.doc》由会员分享,可在线阅读,更多相关《NOIP高中信息技术竞赛资料——数据结构.doc(68页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第1章 绪论第1章 绪论程序设计就是使用计算机解决现实世界中的实际问题。对于给定的一个实际问题,在进行程序设计时,首先要把实际问题中用到的信息抽象为能够用计算机表示的数据;第二要把抽象出来的这些数据建立一个数据模型,这个数据模型也称为逻辑结构,即建立数据的逻辑结构;第三要把逻辑结构中的数据及数据之间的关系存放到计算机中,即建立数据的存储结构;最后在所建立的存储结构上实现对数据元素的各种操作,即算法的实现。本章就是要使大家了解计算机中的数据表示,理解数据元素、逻辑结构、存储结构和算法的有关概念;掌握基本逻辑结构和常用的存储方法,能够选择合适的数据的逻辑结构和存储结构;掌握算法及算法的五个重要特性
2、,能够对算法进行时间复杂度分析,从而选择一个好的算法,为后面的学习打下良好的基础。1.1基本概念和术语1.数据(data):是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。2.数据元素(data element):是数据的基本单位,在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项(data item)组成,数据项是数据不可分割的最小单位。3.数据结构(data structure):是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组,记为:data_structure=(D,S).其中D为数据元素的集合,S是D上关系的集合。数据
3、元素相互之间的关系称为结构(structure)。根据数据元素之间关系的不同特性,通常由下列四类基本结构:(1)集合:数据元素间的关系是同属一个集合。(图1)(2)线性结构:数据元素间存在一对一的关系。(图2)(3)树形结构:结构中的元素间的关系是一对多的关系。(图3)(4)图(网)状结构:结构中的元素间的关系是多对多的关系。(图4) 图1 图2 图3 图41.2 数据的逻辑结构和物理结构1.逻辑结构:数据元素之间存在的关系(逻辑关系)叫数据的逻辑结构。即上面给出的四种结构。2.物理结构:数据结构在计算机中的表示(映象)叫数据的物理结构,又称存储结构。一种逻辑结构可映象成不同的存储结构:顺序存
4、储结构和非顺序存储结构(链式存储结构和散列结构)。1.3算法及算法分析1. 算法:是对特定问题求解步骤的一种描述,是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。 2. 算法的重要特性 输入:一个算法应该有零个或多个输入。 有穷性:一个算法必须在执行有穷步骤后正常结束,而不能形成无穷循环。 确定性:算法中的每一条指令必须有确切的含义,不能产生多义性。 可行性:算法中的每一条指令必须是切实可执行的,即原则上可以通过已经实现的基本运算执行有限次来实现。 输出:一个算法应该有一个或多个输出,这些输出是同输入有某个特定关系的量。 3. 算法的时间复杂度定义:设问题的规模为n,把一个算法的
5、时间耗费T(n)称为该算法的时间复杂度,它是问题规模为n的函数。算法的渐进时间复杂度设T(n)为一个算法的时间复杂度,如果当n趋向无穷大时T(n)与函数f(n)的比值的极限是一个非零常数M,即记作T(n)=O(f(n),则称O(f(n)为算法的渐进时间复杂度,简称时间复杂度,也称T(n)与f(n)的数量级相同,通常,f(n)应该是算法中频度最大的语句的频度。常用的算法的时间复杂度的顺序O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)=0&(Ai!=k)(3)i-;(4)return i;此算法中的语句(3)的频度不仅与问题规模n有关,还与输入实例中A的各元素取值及K的取值有关:若
6、A中没有与K相等的元素,则语句(3)的频度f(n)=n;若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。 最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何情况下更长。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。 例1 求下列交换两个变量i和j的值的算法的时间复杂度。(1) i=10;(2) j=20;(3) t=i;(4) i=j;(5) j=t;解:各
7、行语句的执行次数均为1,所以该算法的时间耗费T(n)= 1+1+1+1+1=5,该算法的时间耗费T(n)与问题的规模n无关,因此,该算法的时间复杂度T(n)=O(1)。例2 求两个n阶方阵的乘积C=AB,其算法如下,计算该时间复杂度。程序段:(1) for(i=0; in; i+)(2) for(j=0; jn; j+)(3) cij=0;(4) for(k=0; kn; k+)(5) cij+=aik*bkj; 解:解法1计算程序段中的每一行的执行次数。第(1)行for(i=0; in; i+)中只考虑循环条件表达式in的执行次数(忽略初始化表达式i=0和修正表达式i+的执行次数,下同),表
8、达式in共执行n+1次(i为0到n-1时该表达式非零,共n次,i为n时该表达式为零,共1次,合计执行n+1次),所以,第(1)行共执行n+1次;第(2)行for(j=0; jn; j+),在第(1)行for(i=0; in; i+)中的表达式in非零时(共n次)都要执行一遍,而每一遍同样要执行n+1次,所以,第(2)行共执行n(n+1)次;第(3)行cij=0;在表达式in和jn均非零时执行,共执行n2次;第(4)行for(k=0; kn; k+)在表达式in和jn均非零时执行一遍,而每一遍同样要执行n+1次,所以,第(4)行共执行n2(n+1)次;第(5)行cij+=aik*bkj; 在表达
9、式in、jn和kn均非零时执行,共执行n3次;因此,各行执行次数分别为:n+1,n(n+1),n2,n2(n+1),n3。如果用T(n)表示该算法的时间耗费,则 T(n)= n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1由此可知,该算法的时间耗费T(n)是矩阵阶数n的函数,T(n)=O(n3)。解法2只计算执行频度最高的行。显然,在该程序段中,执行频度最高的行为cij+=aik*bkj; 在表达式in、jn和kn均非零时执行,而表达式in、jn和kn均有n次非零,所以,该行共执行n3次。因此,该算法的时间耗费T(n)是矩阵阶数n的函数,T(n)=O(n3)。【课堂实
10、践】分析并计算下面程序段执行的时间复杂度。i=1; k=0;while(i0,则除a1和an外,有且仅有一个直接前驱和一个直接后继,即ai(其中1 in)是线性表中第i个数据元素,在ai之前仅有一个数据元素ai-1,而在ai之后也仅有一个数据元素ai+1。称a1称为起始结点,an称为终端结点,i称为ai在线性表中的序号或位置。线性表中结点的之间的关系就是上述的邻接关系,由于该关系是线性的,我们称线性表是一种线性结构。2.线性表的基本运算(1)线性表初始化格式:InitList(L)初始条件:线性表L不存在。操作结果:构造一个空的线性表L。(2)求线性表的长度格式:LengthList(L)初始
11、条件:线性表L存在。操作结果:返回线性表L中所有元素的个数。(3)取表元格式:GetList(L,i)初始条件:线性表L存在,且1iLengthList(L)。操作结果:返回线性表L的第i个元素(ai)的值。(4)按值查找格式:LocateList(L,x)初始条件:线性表L存在,x有确定的值。操作结果:在线性表L中查找值为x的数据元素,并返回该元素在L中的位置。若L中有多个元素的值与x相同,则返回首次找到的元素的位置;若L中没有值为x的数据元素,返回一个特殊值(通常为-1)表示查找失败。(5)插入操作格式:InsertList(L,i,x)初始条件:线性表L存在,i为插入位置(1in+1,n
12、为插入前的表长)。操作结果:在线性表L的第i个元素(ai)位置上插入值为x的新元素,原序号为i,i+1, ,n的数据元素的序号插入后变为i+1,i+2, ,n+1,插入后表长=原表长+1。(6)删除操作格式:DeleteList(L,i)初始条件:线性表L存在,i(1in)为给定的待删除元素的位置值。操作结果:在线性表L中删除序号为i的数据元素(ai),删除后,原序号为i+1,i+2, ,n的数据元素的序号变为i,i+1, ,n-1,删除后表长=原表长-1。注:以上给出的是线性表的基本运算,并不是全部运算,其它运算可用这些基本运算来实现,这些运算都是定义在逻辑结构层次上的运算,只有确定了存储结
13、构之后,才能具体实现这些运算。例1 假设两个线性表LA,LB分别代表两个集合A和B:求A=A U Bvoid union(List &La ,List &Lb)/将所有在线性表Lb中,但不在La中的数插入到La中La.len=ListLength(La);Lb.len=ListLength(Lb); /求两表的长度for(i=1;i=Lb.len;i+) GetElem(Lb,i,e);/取Lb中第i个的元素复制给eIf(!LocateElem(La,e,equal)ListInsert(La,+La.len,e);/若其中不存在相同的,则插入/union例2 已知线性表la,lb中的数据元素
14、按值非递减有序排列,现要求将la,lb归并为一个新的线性表lc且lc按值非递减。例如 la=(3,5,8,11), Lb=(2,6,8,9,11,15,20)则lc=(2,3,5,6,8,8,9,11,11,15,20)分析:由于两表都是按照一定顺序进行排列,所有设置2个指针,分别指向a、b表,先分别比较比较最初指向的两数据,比较一下大小,谁小就放入到c表中,然后数小的指针向下移动,再进行比较。直到2表有一表结束,再将剩余的表存放到c中。Void MergeList(List La, List Lb,List &Lc)/已知线性表la和lb中的数据元素InitList(Lc);/初始化表cIn
15、t i=j=1;k=0;La.len=ListLength(La);Lb.len= ListLength(Lb);While(i= La.len)&( (j= Lb.len)GetElem(La,i,ai);GetElem(Lb,j,bj);/获取数值If(ai=bj)ListInsert(Lc,+k,ai);i+;elseListInsert(Lc,+k,bj);j+;/if结束/whie结束,其中一表结束;While(i=La.len)/表B数据全访问完,表a未到最后GetElem(La,i+,ai);ListInsert(Lc,+k,ai);While(j=Lb.len)/表a数据全访问
16、完,表b未到最后GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/程序结束分析:上述2个算法的时间复杂度(基本操作的执行时间),例1为O(ListLength(La)*ListLength(Lb),例2的时间复杂度为O(ListLength(La)+ListLength(Lb)。2.2 线性表的顺序存储结构线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。设线性表中每个元素需占用r个存储单元则 loc(ai+1 )=loc(ai)+r loc(ai)=loc(a1)+(i-1)*r线性表的这种机内表示称做线性表的顺序存储结构或顺序映像,通常,称这种
17、存储结构的线性表为顺序表。只要确定了存储线性表的起始位置,线性表中任一数据元素可随机存储,所以线性表的顺序结构是一种随机存储的存储结构。/=线性表的动态顺序存储结构#define LIST_INIT_SIZE 100 / 初始分配量#define LISTINCREMENT 10 /分配增量Typedef structElemtype *elem; /存储空间基址Int length; /当前长度Int listsize; /当前分配的存储容量SqList;Elem表示基地址,length指示线性表的当前长度。上述的含义是为顺序表分配一个预定义大小的数据空间,并将当前的长度设为0;Status
18、 InitList_sq(SqList &L)/=创建一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);/ ElemType指数据类型,malloc新分配空间If(!L.elem) exit(OVERFLOW);/存储分配失败L.length=0;/空表长度为0L.listsize= LIST_INIT_SIZE;/初始存储容量Return ok;/InitList_sq在这种存储方式下,容易实现对表的遍历。要在表的尾部插入一个新元素,也很容易。但是要在表的中间位置插入一个新元素,就必须先将其后面的所有元素都后移一个
19、单元,才能腾出新元素所需的位置。Status ListInsert_sq(SqList &L,int I,ElemType e)/在顺序表中插入一个新元素 eIf(iL.length+1) return Error;If(L.length= L.listsize)/当前存储空间已满,增加分配Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType);/ ElemType指数据类型,realloc再次分配,L.elem存储基地址/ifq=&(L.elemi-1);/q为插入位置for(p=&(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- NOIP 高中 信息技术 竞赛 资料 数据结构
限制150内