NOIP高中信息技术竞赛资料数据结构
第1章绪论
程序设计就是使用计算机解决现实世界中的实际问题。对于给定的一个实际问题，在进行程序设计时，首先要把实际问题中用到的信息抽象为能够用计算机表示的数据；第二要把抽象出来的这些数据建立一个数据模型，这个数据模型也称为逻辑结构，即建立数据的逻辑结构；第三要把逻辑结构中的数据及数据之间的关系存放到计算机中，即建立数据的存储结构；最后在所建立的存储结构上实现对数据元素的各种操作，即算法的实现。
本章就是要使大家了解计算机中的数据表示，理解数据元素、逻辑结构、存储结构和算法的有关概念；掌握基本逻辑结构和常用的存储方法，能够选择合适的数据的逻辑结构和存储结构；掌握算法及算法的五个重要特性，能够对算法进行时间复杂度分析，从而选择一个好的算法，为后面的学习打下良好的基础。
1.1基本概念和术语
1.数据(data)：
是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。
2.数据元素(data element):
是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项（data item）组成，数据项是数据不可分割的最小单位。
3.数据结构(data structure):
是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为:
data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。
数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常由下列四类基本结构：
（1）集合:数据元素间的关系是同属一个集合。（图1）
（2）线性结构:数据元素间存在一对一的关系。（图2）
（3）树形结构：结构中的元素间的关系是一对多的关系。（图3）
（4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）
图1 图2
图3 图4
1.2 数据的逻辑结构和物理结构
1.逻辑结构：数据元素之间存在的关系（逻辑关系）叫数据的逻辑结构。即上面给出的四种结构。
2.物理结构：数据结构在计算机中的表示（映象）叫数据的物理结构，又称存储结构。
一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。
1.3算法及算法分析
1. 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。
2. 算法的重要特性
①输入：一个算法应该有零个或多个输入。
②有穷性：一个算法必须在执行有穷步骤后正常结束，而不能形成无穷循环。
③确定性：算法中的每一条指令必须有确切的含义，不能产生多义性。
④可行性：算法中的每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现。
⑤输出：一个算法应该有一个或多个输出，这些输出是同输入有某个特定关系的量。
3. 算法的时间复杂度
①定义：设问题的规模为n，把一个算法的时间耗费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) ④算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。 例如：在数组A[0...n-1]中查找给定值K的算法如下： (1)i=n-1; (2)while(i>=0&&(A[i]!=k)) (3) i--; (4)return i; 此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关： 若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; 解：各行语句的执行次数均为1，所以该算法的时间耗费T(n)= 1+1+1+1+1=5，该算法的时间耗费T(n)与问题的规模n无关，因此，该算法的时间复杂度T(n)=O(1)。 例2求两个n阶方阵的乘积C=A×B，其算法如下，计算该时间复杂度。 程序段： (1) for(i=0; i (2) for(j=0; j (3) {c[i][j]=0; (4) for(k=0; k (5) c[i][j]+=a[i][k]*b[k][j]; } 解：解法1 计算程序段中的每一行的执行次数。 第(1)行for(i=0; i 第(2)行for(j=0; j 第(3)行c[i][j]=0;在表达式i 第(4)行for(k=0; k 第(5)行c[i][j]+=a[i][k]*b[k][j]; 在表达式i 因此，各行执行次数分别为：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 只计算执行频度最高的行。 显然，在该程序段中，执行频度最高的行为c[i][j]+=a[i][k]*b[k][j]; 在表达式i T(n)=O(n3)。 【课堂实践】分析并计算下面程序段执行的时间复杂度。 i=1; k=0; while(i<=n-1) { k+=10*i; i++; } 第2章线性表 线性表是最常用且最简单的一种数据结构，一个线性表是n个数据元素的有序系列，每个数据元素可以是一个数或一个符号，也可以使一页书，甚至其他更复杂的信息。如26个字母的字母表：（A,B,C,D…..,Z）在复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为一个记录，含有大量记录的线性表又称文件。如图 综合上述例子，可以将线性表描述为： 线性表是由n个数据元素的有限序列(a1,a2,…,a n)组成的，其中每一个数据元素a i的具体含义可以按不同的情况和要求定义具体的内容，它可以是一个数、一个符号、一串文字，甚至是其他更复杂的信息。线性表中数据元素的个数n称为线性表的长度。 2.1 线性表的逻辑结构及基本运算 1.线性表简单的定义 n个数据元素的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。线性表中的数据元素不仅可以进行访问，还可进行插入和删除。 若n=0，则表示一个空表，即没有任何数据元素的线性表；若n>0，则除a1 和a n外，有且仅有一个直接前驱和一个直接后继，即a i(其中1< i 2.线性表的基本运算 （1）线性表初始化 格式：InitList(L) 初始条件：线性表L不存在。 操作结果：构造一个空的线性表L。 （2）求线性表的长度 格式：LengthList(L) 初始条件：线性表L存在。 操作结果：返回线性表L中所有元素的个数。 （3）取表元 格式：GetList(L，i) 初始条件：线性表L存在，且1≤i≤LengthList(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为插入位置（1≤i≤n+1，n为插入前的表长）。 操作结果：在线性表L的第i个元素(a i)位置上插入值为x的新元素，原序号为i,i+1, …,n的数据元素的序号插入后变为i+1,i+2, …,n+1，插入后表长=原表长+1。 （6）删除操作 格式：DeleteList(L，i) 初始条件：线性表L存在，i（1≤i≤n）为给定的待删除元素的位置值。 操作结果：在线性表L中删除序号为i的数据元素(a i)，删除后，原序号为i+1,i+2, …,n的数据元素的序号变为i,i+1, …,n-1，删除后表长=原表长-1。 注：以上给出的是线性表的基本运算，并不是全部运算，其它运算可用这些基本运算来实现，这些运算都是定义在逻辑结构层次上的运算，只有确定了存储结构之后，才能具体实现这些运算。 例1 假设两个线性表LA,LB分别代表两个集合A和B:求A=A U B void 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个的元素复制给e If(!LocateElem(La,e,equal)) ListInsert(La,++La.len,e);//若其中不存在相同的，则插入 }//union 例2 已知线性表la，lb中的数据元素按值非递减有序排列，现要求将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);//初始化表c Int 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++; }else{ ListInsert(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数据全访问完，表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（a i+1）=loc（a i）+r loc（a i）=loc（a1）+（i-1）*r 线性表的这种机内表示称做线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。只要确定了存储线性表的起始位置，线性表中任 一数据元素可随机存储，所以线性表的顺序结构是一种随机存储的存储结构。 //======线性表的动态顺序存储结构 #define LIST_INIT_SIZE 100 // 初始分配量 #define LISTINCREMENT 10 //分配增量 Typedef struct{ Elemtype *elem; //存储空间基址 Int length; //当前长度 Int listsize; //当前分配的存储容量 }SqList; Elem表示基地址，length指示线性表的 当前长度。上述的含义是为顺序表分配一个预定义大小的数据空间，并将当前的长度设为0； Status InitList_sq(SqList &L){ //====创建一个空的线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));// ElemType指数据类型，malloc 新分配空间 If(!L.elem) exit(OVERFLOW);//存储分配失败 L.length=0;//空表长度为0 L.listsize= LIST_INIT_SIZE;//初始存储容量 Return ok； }//InitList_sq 在这种存储方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。 Status ListInsert_sq(SqList &L,int I,ElemType e){ //在顺序表中插入一个新元素 e If(i<1||i>L.length+1) return Error; If(L.length>= L.listsize){//当前存储空间已满，增加分配 Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));// ElemType指数据类型，realloc再次分配，L.elem存储基地址 }//if q=&(L.elem[i-1]);//q为插入位置 for(p=&(L.elem[L.length-1]);p>=q;--p){ *(p+1)=*q; }//for *q=e;//插入e ++ L.length； Return ok； } 执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。这两种运算的时间复杂度均为O(n)n为表的长度。 Status ListDelete_sq(SqList &L,int I,ElemType &e){ //在顺序表中插入一个新元素 e If(i<1||i>L.length+1) return Error; p=&(L.elem[i-1]);//p为删除位置 e=*p; q=L.elem+L.length-1; for(++p;p<=q;++p){ *(p-1)=*p; }//for -- L.length； Return ok； } 2.3 线性表的链式存储结构 线性表顺序结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存储表中的任一元素，但是在插入删除时须移动大量元素。而线性表的链式存储由于其不要求逻辑上相邻，因此它没有顺序存储结构的弱点，但同时也失去了顺序表可随机存取的优点。 1.单链表 线性链表的特点是用一组任意的存储单元存储线性表的元素，用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。 为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域如图所示： 其中，存储单元由两部分构成，即数据域存 储数据元素，指针域存储下一个元素所在的单元如果表是a1,a2,…,a n，那么含有元素a i的那个单元中的指针应指向含有元素a i+1的单元(i=1,2,…,n-1)。含有a n的那个单元中的指针是空指针null。此外，通常 我们还为每一个表设置一个表头单元header，其中的指针指向开始元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。 上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链表。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元，即表头单元header，其中的指针是空指针null。 图1 单链表示意图 为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针，它所指向的单元是元素a i-1所在的单元，而不是元素a i所在的单元(i=2,3,…,n)。位置1是指向表头单元header的指针。位置End(L)是指向单链表L中最后一个单元的指针。这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。 单链表存储结构 Typedef struct Lnode{ ElemType data; Struct Lnode *next;//指向后继节点的指针 }Lnode, *LinkList;//线性链表的实质就是指针 基本运算 (1)ListInsert.L(L,i,e) 功能:在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,…,an，那么在执行Insert(x,p)后，表L变为a1,a2,…ap-1,x,ap,…,an 。若p为End(L)，那么表L变为 a1,a2,…,an,x 。若表L中没有位置p，则该运算无定义。 实现P为指向a节点的指针，s为指向X节点的指针:s->next=p->next; p->next=s; 上述算法中，链表指针的修改情况见图2 图2(a)是执行Insert运算之前的情况。我们要在指针p所指的单元之后插入一个新元素x。图2(b)是执行Insert运算以后的结果，其中的虚线表示新的指针。在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性容易判定。Insert运算所需的时间显然为O(1)。 (2)Delete(p) 功能:从表L中删除位置p的下一元素。例如，当L为a1,a2,…,a n时，执行Delete(p)后，L变为a1,a2,…,a p-1,a p+1,…,a n。当L中没有位置p或p=End(L)时，该运算无定义。实现:p.next=p.next.next; 这个过程很简单，其指针的修改如图3所示。 若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。Delete过程所需的时间显然也为O(1)。 2.静态链表 静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下: type jid=record data:datatype; next:integer; end; var alist=array[0..maxsize] of jid 游标即我们可以用游标来模拟指针, 对于一个表L，我们用一个整型变量Lhead(如Lhead=0)作为L的表头游标。。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。当i>1时，表示第i个位置的位置变量p i的值是数组alist中存储表L的第i-1个元素next值,用p:=alist(p).next后移。照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实 现的表称为静态链表。 3.循环链表 循环链表是另一种链式存储结构，特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，可由表中任一结点出发均可找到表中其他结点。如图6所示的是一个单链的循环链表或简称为单循环链表。 (a) 非空表 (b) 空表 图6单循环链表 在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^.next 指向空(nil)。在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，如果我们用指向表尾的指针表示一个表L时，我们就可以在O(1)时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O(1)时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算。 4.双链表 单循环链表中，只有一个指示直接后继的指针域，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。 图8 双链表 由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。 双链表的单元类型定义如下。