数据结构高分笔记天勤

大部分同学在学习数据结构时，想必对数据结构里的伪代码多多少少有点不是很清楚，特别是自己在动手编写算法的时候，明明知道算法的思路，但是编写出来的程序就是不标准，可能在考试的时候就会吃大亏。所以在开始数据结构的旅程之前，我觉得有必要将一些基本功提前告知，掌握了这些东西，在本章以后的章节中，才能以此为基础来。▲对于考研数据结构，需要C与C++语言作为基础，但是又不需要太多，因此此处讲解▲为什么要特别注重这一块的讲解？在09年批阅数据结构算法那道题的时候，由于当时牛人写出更完美的算法，却得了最低的分。也许是为了避免这种的再次出现，10年▲（0<P<n）R中的数据由{X0,X1......Xn-1 #defineN int int cout<<R[i]<<" 第1和3句，在我们大学里写的程序中，几乎都要用到，是耳熟能详的，考试2句，定义了一个常量，如果你的题目中要用一个常量，在你用到的地方加上一句卷整洁，这是最好的解决办法，因此第2句去掉。你把它用给别人看（主函数中的调用，就是用这个函数解决问题的过程26经过以上删减，就是以下程序段了，看着是不是简洁了很多 int R[],intn,intp)就包含一个接口，它是原材料的一个。括号里所描述的就是原材C&C++语言，而不是单一的一种，是因为本书有些程序的书写包含体介绍针对考研数据结构的C和C++语言基础。aMAX个整型变量摆在一起，其中各整typedef{ floatb3TypeAa;a，只a中第一，第二，第三个元素的值，两者十分相似。可以类比为哪一种数组呢？显然我们可以把它类比成一个二维数组，比如intb[3][3];定义了一个名字为b的二维数组。二维数组可以看成其数组元素是一维数组的一维数组，中的位置，就像一个指示方向的指针，了某个变量的位置，因此叫做指针型。int*a; //对比一下定义int型变量的语句：inta;char*b; //对比一下定义char型变量的语句：charb;float*c;//对比一下定义float型变量的语句：floatc;TypeA*d;//对比一下定义TypeA型变量的语句：TypeAx=b;，&bba中，即大家常说的指针ab。结点的位置，如图1.2所示。typedefstruct{int a这个结构型的名字Node。与之前定义的结构型TypeA进行比较一下，会发现这里的结构型Node在定义方法上的不同。typedefstruct{typedefstruct{ structBTNode*lchild;structBTNode比链表结点多了一个指针而已无需特意的去。说明：对于结构型，用来实现构造结点的语法有很多不同的表述，我们完全没必要全部掌握。刚刚上边讲到的那些语法用来构造结点已经足够用了，所以我这里建议大家，熟练掌握以上两种构造结点的结构体定义的写法，其他的写法不予理睬。有些语法对我们考typedefstruct{ structBTNode*lchild;structBTNode可以看到在最后又多了个*btnodep的时候，BTNode*p;等价于btnodep;对于定义结点指针，BTNode*p;这种写法是何等的顺理成章，因为它继承了之前int*a;char*b;char*c;TypeA*d;这些指针定义的一般规律，使得我们起来非常方便，何苦再弄个btnodep;这种写法来增加不必要的负担呢？因①BTNode②BTNode*BT;中所有类型结点的内存分配都可用malloc()来完成，模式固定，容易。。xx=BT.data;x=BT->data;一般来说，用结构体变x，*p，*BTBT指向的变量，因此可以写成(*BT).data;（(*BT).data;BT->data是等价的。注意*BT外边要用括号括起来，不要写成*BT.dataCC++语言中这有的书上在定义变量的时候会出现一些你在程序设计中从来没见过的诡异的数据类型，比如严书上就有类似于ElemtypeA;的变量定义语句，这里的Elemtype是用到过，如typedefstruct{……}TypeA;即为给“struct{……}”起了一个名字TypeA，就好比你制作了计算机中的整型，给他起了个名字为int。并且如果给intA,typedefintA;xAx;就等价于intx;在考研中typedef用的最多的地方就在结构型的定义过，其他的必要，有的同学可以去查下资料，查完你会发现，typedef对程序设计的贡献很大，returnERRORreturnOK；之类的语句，对于经常在编译器上数操作结果的。严初衷是想把0,1这种常作为函数返回标记的数字定义成ERROR和前边去加上#defineMAX50这一句，原因前边已经讲过。是站在学生的角度把上用过于严谨以及专业化的词语描述的思想用通俗易懂的语言表void{}void{}intvoidf(int{}a=0;//①f(a);//②变量a只是把自己的值赋给了一个在f()的过已经定义好的整形变量，可以把这此a的值在执行完①,②两句之后不变。比较麻烦且容易出错，因此这里采用C++的语法，其函数方法如下：voidf(int{}voidf(int*&x{}voidf(intx[],int{}voidf(intx[][MAX]，int{}第二维长度也得是MAX，否则出错，比如：voidf（int{}intintb[10][3];f(a);//参数正确f(b);//都是型的。intf(int{return}STATUSf(ELEMTYPE{if(a>=0)returnERROR; returnOK;}都什么东西，其实严在离这个函数很远的地方写过这些语句：#defineERROR#defineOKtypedefSTATUS typedefELEMTYPEboolf(intaintf(int{if(a>=0)return return}一是上边那个自己另起的类型名或者常量名，都有着实际的意义，STATUS代表状态，OK代表程序执行成功，ERROR代表出错，这样代码写的就更人性化。二是，如果我们在写一个大工程，对于其中的一个变量，在整个工都已经用int型定义过了，但是工程现在char即可，这无疑是十分方便的事情，这就是typedef对于程序设计的意义所在n，可以称为问题的规模，比如要处理的数组元素的个数为n，而基本操作所执行的次数是n的一个函数f(n)f(n)n增大增长此项的系数，比如f(n)=2n3+4n2+100，则其时间复杂度为为nT(n)=O(1)f(n)n是线性关系时，T(n)=O(n)；是平方≤≤≤≤≤≤≤≤ሻ根据基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为般我们依照使得基本操作执行次数最多的输入来计算时间复杂度，即将的情况作为算voidfun(intn){{}}参数n有关，因此参数n就是我们所说的规模n。因为K为常数，所以这样做不会影响最终时间复杂度的计算，解得m=(n-1-K)/2，即f(n)=(n-1-K)/2，可以发现其中增长最快的项为n/2,因此时间复杂度T(n)=O(n)。voidfun(intn){inti，j，x=0；}执行次数为f(n)=n(n-1)/2，变化最快的项为n2，因此时间复杂度为T(n)=O(n2)。voidfun(intn){{}}候s的值则有m(m+1)/2+K=n（K为起修正作用的常数）由求根得：െ1൅√8n൅1െ

݉ ݉ሺnሻെെ1൅√8n൅1െ算法的空间复杂度指算法在运行时所需空间的度量，主要考虑在算法运行过临时占用的空间的大小（和时间复杂度一样，以数量级的形式给出。说明：这一部分在理解了各种数据的结构及其操作之后更容易理解。因此于这一部分，将在后边的章节中以题目的形式给出讲解。数据元素是数据的基本单位，在计算机程序中通常将其作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成；例如，一本书的书目信息为一个数据元素，而书目信息的每一项（如书名，作者名等）为一个数据项。数据项是数据结构中讨论的最小单位，是数据记录中最基本的，不可分的数据单是一个数据对象，大写字母数据对象是集合{’A’,’B’……’Z’}数据的逻辑结构是对数据之间关系的描述，它与数据的结构无关，同一种逻辑结构可以有多种结构。归纳起来数据的逻辑结构主要有两大类。线性结构简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：集合中必存在唯一的一个“第一个元素”集合中必存在唯一的一个“最后的元素”除最后元外，其它数据元素均有唯一的“后继”除第一元外，其它数据元素均有唯一的“前驱”数据结构中线性结构指的是数据元间存在着“一对一”的线性关系的数据结如（a1,a2,a3,an）,a1为第一个元素，an为最后一个元素，此集合即为一个线性结构的集合。与线性结构不同，非线性结构中的结点存在着一对多的关系，它又可以细分为树形结构和图形结构。数据的物理结构又称为结构，是数据的逻辑结构在计算机中的表示（又称映像。它包括数据元素的表示和关系的表示。当数据元素是由若干数据项构成的时候，数据项的表示称为数据域；比如一个链表结点，结点包含值域和指针域，这里结点可以看做一个数据元素，其中的值域和指针域都是这个数据元素的数据域。数据元间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像。对应的两种不同的结构分别是顺序结构和链式结构。顺序映像是借助数据元素在器中的相对位置来表示数据元间的逻辑关系；非顺序映像是借助指针表示数据元间的逻辑关系。实际上，在数据结构中有以下4种常用的方法。顺序方顺序结构是结构类型中的一种，该结构是把逻辑上相邻的结点在物理位置上相邻的单元中，结点之间的逻辑关系由单元的邻接关系来体现。由此得到的结构为顺序结构，通常顺序结构式借助于计算机程序设计语言（例如C/C++）的数组来描述的。链式方该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的表示称为链式结构，通常借助于计算机程序设计语言（例如C/C++）的指针类型来描述它。索引方该方法在结点信息时除建立结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式一般是<关键字，地址>。关键字标识唯一一个结点：地址作为指向结点的指针。散列（或哈希）方该方法的基本思想是根据结点的关键字通过哈希函数直接计算出该结点的地址。这种方法本质上是顺序方法的扩展。数据类型是一个值的集合以及定义在这个值集上的一组操作。变量是用来值的所在处，它们有名字和数据类型。变量的数据类型决定了如何将代表这些值的位到计算机的内存中。在变量时也可指定它的数据类型。所有变量都具有数据类型，以决定能够哪种数据。算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列。一个算法应该具有以下五个重要的特征：有穷性一个算法必须保证执行有限步之后结束。确定性算法的每一步骤必须有确定的定义。一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身确定了初始条件。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。可行性算法中的所有操作都必须可以通过已经实现的基本操作机型运算，并在有限次内实现，而且人们用笔和纸做有限次运算后也可完成。算法设计目标为正确性、可读性、健壮性和算法效率。其中算法效率通过算法的时间复杂度和空间复杂度来描述。正确性要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的可读性要求算法易于人的理解。健壮性要求算法有很好的容错性，能够对不合理的数据进行检查。高效率与低量需算法的效率主要是指算法的执行时间。对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高。算法的量指的是算法执行过所需要的最大空间。高效率和低量这两者都与问题的规模有关。算法的计算量的大小称为算法的 B.复杂 C.现实 D.难 B.待处理数据的初 C.A和 B.排序方 C.解决问题的步骤序 D.调度方C.确定性、有穷性、稳定 D.易读性、稳定性、安全一个算法应该是 C．要满足五个基本特 下面说法错误的是 以下哪一个术语与数据的结构无关 9．在下面的程序段中，对x的赋值语句的频度为（

2A． 210for(i=n-1;i>=1;i其中n为正整数，则最后一行的语句频度在情况下是 A.O（n） B.O(nlogn) C.O(n3) （ A．一定连续B．一定不连续C．不一定连续 B.哈希表

D.： 分别写出相应的大O表示的运算时间。 mergesort执行的时间复杂度为多少?假设函数调用被写voidmergesort(inti,intj){intm;{}}将其大小作为算法的时间复杂度，因此选B。况要快。本题选C。B选项A计算机程序只是实现算法的一种，人用手工也可以完成B算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤。程序选项C明显错误，概念中已经讲过))也就是O(f(n))给出了函数f(n)的一个上界。看看这种结构到底有没有具体到使用顺序还是链式，如果已经具体到了那就一定是和数据的结构有关，比如A选项中的栈并没有说明是用顺序栈还是用链栈来实现，本题考查数据的物理结构。顺序结构要开辟一片连续的空间，结合本操作次数可设为cn，mergesort函数基本操作次数设为f(n)，则有： 作者的话：假如你是一个很新的新手（至少要稍微有一点C或C++语言基础，如果连这个都没有的话，先去读强的C），到这里为止，我已经把考研数据结构要用到的全部基本功教给你了，对于考研数据结构，要想拿高分，有很多学习的风格，本书则走了一种让广大考生都容易接受的风格，希望读者能适应这种风格，这样你的学习会变的轻松。下面就让我们从下一章开始，把考纲所要求的知识点一一击破。▲▲（n≥0顺序表就是把线性表中的所有元素按照其逻辑顺序，依次到器中从指定第i+1个元素的位置紧接在第i个元素的位置的后面。在链表中，每个结点不仅包含所存元素本身的信息，还包含元间逻辑关系的6是确定的，当我们在地皮上布置新的房间或者拆掉老的房间（即对顺序表的操作过再看链表，如图所示，房间是散落存在的，每个房间的右边有下一个房间的方向指：图2.2结点的单链所示，即为结点的单链表。这里要区分一下结点的单链表和不结点的单链表。1）结点的单链表中头指针head指向头结点，头结点的值域不含任何信息，从头2当head等于NULL的时侯链表为空。注意：在题目中要区分头结点和头指针，不论是结点的链表还是不结点的链表，头指针都指向链表中第一个结点，即图2.2中的head指针。而头结点是结点的问题我们构造了双链表。如图2.3所示，即为结点的双链表。双链表就是在单链表结头结点的双链表head->next为NULL的时候链表为空。不结点的双链表head为NULL的时候链表为空。发后只能这个结点本身及其后边的所有结点。结点的循环单链表当head等于head->next;时链表为空；不结点的循环单链表当head等于NULL时链表为空。 /itm.htm?id 双链表同样有结点和不结点之分。结点的循环双链表当head->next和NULL的时候为空。和一般链表中next指针的地位是同等的。 密度=结点数据域所占的量/结点结构所占的总量)： 密度=1。链表的密度<1（因为结点中有指针域顺序表可以随机存取，也可以顺序存取（对于顺序表一般只答随机存取即可对顺序表进行插入和删除算法时间复杂度分析因为题目要计算平均移动个数，这就是告诉我们要计算移动个数的期望。对于本题要计算期望的话就要知道在所有可能的位置插入元素时所对应的元素移动个数以及在每个位因为插入位置的选择是随机的，所以所有位置入的可能性都是相同的，有n个可插入位置，所以任何一个位置入元素的概率都为p=1/n。动一个位置，因此移动元素个数为n-i。即要移动近一半元素，由此即可以知道，插入和删除算法的平均时间复杂度为O(n)#defineMAX typedef{intdata[MAX];//存放顺序表元素的数组（intint 个数的变量length。intn;typedefstruct{int structLNode*next;// typedefstruct{int structDLNode*prior;//指向后继结点的指针structDLNode 2.9C语言描述，希望考生牢记并且可以默写，长不会大于MAX。1开始，0号空位置不L中的元素是递增排列，所以我们可以从小到大逐个扫描表中元intLocateElem(SqlistL,int{inti;if(x<L.data[i])// return }return }voidinsert(Sqlist&L,intx)//因为L本身要发生改变，所以要用型{int //将x放在插入位置p上。}

intLocateElem(SqlistL,int{intreturn 0return }个位置，腾出一个空位置插入新元素，顺序表长度增加1，插入操作成功，返回1。intinsert(Sqlist&L,intp,int{intreturn0; //将x放在插入位置p上。 return }{

listDelete(Sqlist&L,intp,intinti;

//e。)// return}

length0。voidInitList(Sqlist&L)//L本身要发生改变所以用{}int em（SqlistL,intp,int&e）//要改变所以用{ return0;return1;}3AB是两个单链表（带表头结点voidmerge(LNode*&A,LNode*&B,LNode{LNode*p=A->nextp来A的最小值结点。LNode*q=B->nextq来B的最小值结点。LNode*r;//rC的终端结点。 //r指向C，因为此时头结点也是终端结点。while(p!=NULL&&q!=NULL)//pqpq所指结点中的较小 /*ifelse语句中，r始终指向当前链表的终端节点，作为接纳新结点的一个媒介，通过它新结点被入C并且重新指向新的终端结点以便于接受下一个新{}{}}}例题.3中涵盖了两个知识点，一是法建立单链表，二是单链表的归并操作。上边void istR(LNode*&C,inta[],intn)//要改变的变量用型{LNode*s,*rsrCint {s->data=a[i];//a }

r->next=NULL;//aC中，C}void istF(LNode*&C,inta[],int{inti;{}}voidmerge(LNode*&A,LNode*&B,LNode{LNode*p=A->next;LNode*q=B->next;LNode*s;{/*ifelse语句体现了链表的头插法*/{}{s=q;q=q->next;}}{}{}}p指向一个结点，要将s所指结点插入p所指结点之后的操作如下：p->next=s;s->next=p->next;呢？显然是不可以的，因为第一句p->next=s;虽然将s在p之后，但是同时也丢失s->next中，因而p后继结点的地址依然可以找到足将s插入链表的要求。i个结点删去，必须先p的指针域next指向原来p的下一个结点的下一个结点即可。即（q）;//调用q所指结点的内存空间。x的结点；二是将找到的结点删除。问否为x，是则证明找到，不是则继续检测下一个结点。intSearchAndDelete(LNode*&C,int{{}{return1;}}说明：以上程序中之所以要使p除结点本身，是因为要删除一个结点必须知道其前驱结点的位置，这在之前删除操作的讲到此为止考研中对于顺序表和单链表算法操作部分所涉及的最重要的知识点都已经讲采用法建立双链voidCreateDlistR(DLNode*&L,inta[],int{inti;r=Lr{s=(DLNode*)malloc(sizeof(DLNode)创建新结点}}到这样的结点，则返回结点指针，否则返回NULL。算法代码如下：DLNode*Finfnode(DLNode*C,int{{}}说明：不知道大家有没有注意到在插入时，如果按照上面的顺序来插入，可以看成是边了， 递增有序，后n个元素递增有序，设计一个算法，使得整个顺序表有序。RA[m+1]temptemp逐个与A[m],A[m-1],…,A[1]temp<A[j]（1≤j≤m）A[j]后移一位；最终A[]中元素整体有序。voidInsert(intA[],intm,int{intinttemp; { //在j+1位置插入temp。}}解q后移一位；如果两者所指结点的值相同，则删除ppq任一指针为NULL的时候算法结束。voidDifference(LNode*&A,LNode{LNode*p=A->next,*q=B->next;//p和q分别是链表A和BLNode*r;{

//pre为A中p{ } {

}}}所在的链表，循环执行m+n次。即时间复杂度为O(m+n)。下述哪一条是顺序结构的优点 下面关于线性表的叙述中，错误的是哪一个 线性表是具有n个 ）的有限序列表元 顺序 单链 B．不结点的单循环链 D．不结点且有尾指针的单循环链静态链表中指针指示的是 内存地 A．L==NULLB．L->next==NULLC．L->next!=NULLD. A．O(1)B．O(n)C.O(n2)执行（）操作与链表的长度有关。在一个双链表中，在p结点之后插入结点q的操作是 A．q->prior=p;p->next=q;p->next->prior=q;q->next=p->next;B．q->next=p->next;p->next->prior=q;p->next=q;q->prior=p;C．p->next=q;q->prior=p;q->next=p->next;p->next->prior=q;D．q->prior=p;p->next=q;q->next=p->next;p->next->prior=q; p->prior=q;q->next=p;p->prior->next=q;q->prior=p- q->next=p;p->next=q;q->prior->next=q;q- （A．p->prior->next=p->next;p->next->prior=p->prior;B．p->prior=p->prior->prior;p->prior->prior=p;C．p->next->prior=p;p->next=p->next->next; C.L- D.L->prior==L||L-线性表是 线性表采用链表时，其地址 线性表的静态链表结构，与顺序结构相比其优点是 所有的操作算法实现简单 D.便于利用零散的空间n个元素，以下操作中（）在顺序表上实现比在链表上实现效率更据元间的逻辑关系，则应采用（ 顺 需要分配较大的空间插入和删除不需要移动元素的线性表其结构

与单链表相比，双链表的优点之一是

B.可以进行随机 D.前后相邻结点更灵活在顺序表中插入一个元素的时间复杂度为 在顺序表中删除一个元素的时间复杂度为 D.结点的循环双链表 ，的链表是非循环的，以h2为头结点指针的链表是循环的，则（。B.对于两个链表来说，删除终端结点的操作，其时间复杂度都是O(n)。h1h2是不同类型的变量。所有元素，假定i,j都是合法的。整数放半部分，大于的整数放在后半部分，数组从下表1开始。本题考查顺序表与链表的对比。顺序表不像链表一样在结点中存在指针域，因此此本题选B对于B项，不结点的单循环链表在最后一个元后插入一个元素的情况和单链表相同，时间复杂度是O(n)。对于删除表中第一个元素的情况，同样需要找到终端结点，即删除结点的时间复杂度也是O(n)，因为终端结点的指针next指向开始结点，首先需要遍历整个链表找到终端结点，然后执行p->next=q->next;r=q;q=q->next; 以省去了B选项中链表的遍历过程，因此删除和插入结点的时间复杂度为O(1)。态链表等同于顺序表，而误选B项。顺序表，剩下的L2中的元素就不需要比较。2n-1L1L2与表各一个2n-2次，这时还需进行一次比较就有一个表变为空表，至此所有比较结束，因此总的比较次数是2n-1次。本题考查结点的单链表和不结点的单链表基本操作的区别。结点的单链O(n)O(1)，整个过程时间复杂度为O(n)。h所指的头结点，因此无论链表多长删除其中第一个结点的操作都是p=h->next;h->next=p->next;(p);这三D选项尾结点地址已知，在其后插入新结点的操作与链表长度无关。当链表为空时，pp->next==L。当本题考查线性表的定义。线性表是具有相同特性数据元素的一个有限序列。该序列中n（n≥0n。续的；当然如果连续的申请一片空间来链表结点也未尝不可。因此本题选D。需要移动较多的元素，这是优于顺序表的地方，因此本题选C。链表则为O(n)，因此A正确。出n个元素的值，两者时间复杂度均为O(n)，因此C不对。此时间复杂度为O(n)，D不对。要执行3次操作。遇到这种题目的时候要选择“更准确”的一项，显然比起B项来说，A项更准确。在逻辑关系，因此本题选B。态链表同时还具有一般链表的特点，即插入和删除操作不需要移动元素。因此本题选B。本题考查顺序表的特点。较之其他三种结构，顺序表找到表中第i个元素的时间链表中只能快速任何一个结点的后继结点。因此本题选D。插入算法元素平均移动次数大约为n/2次，因此时间复杂度为O(n)。删除算法平均元素移动次数大约为n/2次，因此时间复杂度为O(n)。因此本题选C。4D能通过头结点指针直接获得最后一个结点的相邻结点的地址，因此本题选D。本题考查链表的基本操作。r的循环单链表中，在最后一个结点之后p=r->next;r->next=p->next;(p);O(1)D。其时间复杂度都是O(n)。直到ij相遇时结束，此时顺序表L中的元素已经逆置。voidreverse(Sqlist&L)//L要改变，用{intinttemp辅助变量，用于交换{}}完成删除i~j之间的所有元素。voidDelete(Sqlist&L,inti,intj)//L要改变，用型{int {} }

①i并且i后移一位，准备开始i的扫描）③⑤⑥⑦有比2大的元素被移到了2后边。j停在当前位置不动，i开始移动，如此交替直到i==j。voidmove(Sqlist&L)//L要改变所以用{int{ //检测看是否已仍满足i<j L.data[i]=L.data[j];//移动元素。 }while(i<j&&L.data[i]<tempi++;//{

}}}

p指向后继结点，重复以上过程，直到p的后继结点为空。{

delsl1(LNode //L是指针且要改变因此用指针{{}}}以上过程。当q为空的时候，释放从p之后的所有结点空间。voiddelsl2(LNode{{{}}{}}{

delminnode(LNodeLNode*pre=L,*p=pre->next,*minp=p,*minpre=pre; {{}}minpre->next=minp->next;//删除*minp}L中的元素作为插入L中，这样新的L中的元素顺序正好是逆序的。voidReversel(LNode{ { //q结点作为辅助结点来记录pp->next=L->next;//p }}为偶数的结点则取下，插入链表B中。要用头插法还是用法呢，因为题目要求保持原来数据元素的相对顺序，所以要用法来建立B链表。{

split2(LNode*&A,LNodeLNodeB=(LNode*)malloc(sizeof(LNode))B { p->next=q->next从链表中取下这个结点} }}i用来控制循环和一个始终记录当前所通常题目中i和min两者实现的功能。本题一种可行的办法如下：voidFindMin(intA[],int&i)//i{ {{ i=i+A[i/10];//个位上的数字换成A[i/10]。} } }voidreprint(LNode{{cout<<L->data<<"";//打印开始结点中数据。}}第三章▲▲栈和队列的顺序结▲栈和队列的链式结▲▲（FILO在表的另一端进行删除。进行插入的一端称作队尾（rear，进行删除的一端称为队头（front（FIFOtypedef{intdata[MAX];//存放栈中元素inttop; }SqStack; typedefstruct{intdata; structLNode typedef{intint int typedefstruct{intdata;

*next typedef{QNode*front; QNode

st.top==-1。考试中有时会出现其他规定，1的进栈操作，其实本质一样，考生注xx=st.data[st.top];st.top--;（进栈操作次序决定了出栈操理解和加深）voidinitStack(Sqstack&st)//{ }intStackEmpty(SqStackst){return1;return}intPush(SqStack&st,int{if(st.top==MAX-1这里要注意，栈满不能进栈。return0;return}

intPop(SqStack&st,int{if(st.top==-1注意，如果栈空则不能出栈return0;return}说明：在考试中，栈常常作为一个工具来解决其他问题，因此一般情况下，栈的intstack[MAX];inttop=-1;这两句话连带初始化都有了2与3点需注意的地方是，当前栈是否为空，空时不出；是否为满，满时不进。这些栈元素不多，而MAX足够大，就无需考虑入栈操作会产生溢出。通过2与3两点，来稍微复 下C语言基础。top++与++top（--top与top--的情况类似）的不同可以用几句话来说清楚。前者是先将top赋值给接收它的变量，然后top自增1，而后者是先top自增之后，再把值赋给接收它的变量。比如a=top++;中a中x存放到top变化之后所指示的位置上（一下看不懂可以拆开看。第一步：top先自增1。第二步：自增后的top把自己的数值放在stack[]的括号内而了将要保存元素的等价于top++;stack[top]=x;而x=stack[top--];等价于x=stack[top];top--;表的删除操作

; voidInitStack(LNode {}intStackEmpty(LNode*lst{return1;return}void{

*&lst,intLNode }在栈不空的情况下可以执行，返回1；否则返回0，代码如下：intPop(LNode*&lst,int&x)//需要改变的变量要用型{LNode returnreturn}说明：对于链式栈，和顺序栈一样，在应对考试的时候，不必要像以上那样严格的写出其操作的函数，只需要其中必要的语句组合在自己的题目代码中即可，具体思路类似于顺序栈中的讲解。大家还需注意在考研中链栈的应用要远比顺序栈少的多。顺序栈声07份用在顺序栈的题目上，3要用栈来解决，栈具有的功能，这是栈的FILO特性所延伸出来的一种特性。intmatch(charexp[],int{charstack[MAX];inttop=-1;//两句完成栈的和初始化，考inti;{ {return0; }}return

return0;}

其对应，分别是ab+c+和abc++。此必须先存起来，这符合例题1中粗体字所描述的情形，因此可以用栈来解决。{{if(b==0)//0 return}return}}intcom(char{

int intstack[MAX];inttop=-1;//栈的初始化和，注意元素类型必须为int型，不能//运算过可能产生多位的数字，因此要用整型charOp;{

stack[++top]=exp[i]-'0';//注意字符型和整形的转（后边讲解。 { //将两个操作数结合运算符Op进行运算，结果保存在c }}return}补充：假设有一个字符‘5’，如果定义一个整型变量a，执行a=‘5’;此时aaa=‘5’-‘0’;即可。同理，如果把一个整型数字(a)，a0~910个数字。这个小技巧在voidInitStackl(LNode*&lst{}intStackEmptyl(LNode*lst)//{return1;return}voidPushl(LNode*&lst,intx{LNode}{

Popl(LNode*&lst,int&x)//元素出栈LNode*p; return0; return}rearfront指针指向刚出队的元素位置。因此元素进队的时候，rear要向后移动，元素出队的时候，front也题，我们可以把数组弄成一个环，让rear和front沿着环走，这样就不会出现两者3.4满和队空（rear的情况和front类似。3.5的条件也成了front==rear，和队空条件相同而无法区分了。说明：本书中，元素入队时，先移动指针，后存入元素；元素出队时，也是先移动指针再取出元素。其他书上可能有不同的次序，其实本质是一样的，考生只需去适应一种写法，对于程序设计题目已经足够。对于选择题，则可根据题目描述确定是先存取元素，再voidInitQueue(SqQueue{qu.front=qu.rear=00}intQueueEmpty(SqQueue{

return}{

enQueue(SqQueue&qu,intif((qu.rear+1)%MAX==qu.front)//队满的判断条件，满则不能入队。return0;qu.rear=(qu.rear+1)%MAX;//先移动指针。 return1;}intdeQueue(SqQueue&qu,int{ return return1;}或者 3.6{}{return1;return}voidenQueue(LiQueue*&lqu,int{QNode*p;{lqu->rear->next=p;//将新结点到队尾，rear指向它}}intdequeue(LiQueue*&lqu,int{QNode return0;}特殊矩阵是指非0元素或者0元素的分布有一定规律的矩阵。为了节省空间，可以利用特殊矩阵的规律，对其进行压缩，使多个相同的非零元素共享同一个单元，由于对称矩阵中的元素关于主对角线对称，因此在时只对称矩阵中上三角或者下三角的元素，使得对称的元素共个空间。这样就可将n2个元素压缩到元素ai,j和sa[k]之间存在着如下对应关系： i൅jkെቐ୨ሺ୨ଵሻ൅ i൅jଶ

୧ሺଶ୬ଵሻ൅jെ1,i൅jെቐ୬ሺ୬ଵሻ ,i൅j（െቐ୧ሺ୧ଵሻ൅ji൅j三角矩阵：kെቐ୬ሺ୬ଵሻଶ ,i൅j（数u为：u=m×n-2×[ቔ୫ቕ+(ቔ୫ቕ-1)+……+1]=m×n- k=(ቔ୫ቕ+1)×i+j- 数组方式的区别，即按行与按列的区别，这在一些题目中是常用的，这一点由上图可知，对于行优先，a[2][3]2之前的行所有元之前有例题:设二维数组A[6][10],4个单元，若按行优先顺序存放的数组元素A[3][5]的地址是1000，则A[0][0]的地址是。分析：A[][]数组按行，则对于A[3][5]，行标3之前的所有元素都已经填满，1033所指的行中元素个数由列标指示，有6个元素。因此A[3][5]之前一共有10×3+5=35个元素，A[3][5]的地址为1000，则A[0][0]的地址为1000-35×4=860。考生要把上述两幅图装在脑子中，图中箭头指示了不同优先次序的不同方法，明白了这个，只要带有按照“行优先”或者按照“列优先”这样字眼的求数组中元素实际地S0,S1int型。要求：PUSH(ST,x)：元素x入ST栈；Sempty(ST)：判ST栈是否为空。如何利用栈的运算来实现该队列的三个运算：enqueue:dequeue:元素出队列；queue_empty：判断队列是否为空，空返回1不，空返回0。要求：解然后存入元素；出栈操作为：先取出栈顶元素，top1再自增1。typedef{intelem[MAX];//栈空间，MAXint {{ {return }{

return }elsereturn }elsereturn } // {{

return }elsereturn}

else { {return }elsereturn }}

return 列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1列的出队，实现了先进先出。只有栈s2为空且s1也为空，才算是队列空。①intenqueue(SqStack&s1,int{int {return0; elseif(Sempty(s2))//s2s1s2{{}return1;}}{return1;}}②intdequeue(SqStack&s2,SqStack&s1,int{int {return1}{

return0; {{} }}}

③intqueue_empty(SqStacks2,SqStack{ return0;}

return1;// CD在作进栈运算时，应先判别栈是否（），在作退栈运算时应先判别栈是否（② ③应将两栈的（）分别设在这片内存空间的两端，这样当（）①,空BCDB.C.D.BCD⑤A两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇.第i(1<=i<=n)个元素是（ A.不确 B.n- C. D.n- Ai-j- Bi- C.j- 有六个元素6,5,4,3,2,1 A.5,4,3,6,1,2B. C.3,4,6,5,2,1D.输入序列为A,B,C，可以变为C,B,A时，经过的栈操作为（ A.top=top+1; B.V[top]=x;C.top=top-1; A.|top2- B.C. D.栈在）BCD. B. C. D.- C.线性表的链式结对于链队，在进行删除运算时

仅修改队头指 B.仅修改队尾指C.队头、队尾指针都要修 D.队头、队尾指针都可能要修递归过程或函数调用时处理参数及返回地址要用一种称 的数据结构队 C. D.

rear A.1和 B.2和 C.4和 D.5和 B.rear==front 栈和队列的共同点是 都是先进先 B.都是先进后C.只允许在端点处插入和删除元 D.没有共同栈和队都是 顺序的线性结 B.链式的非线性结C.限制存取点的线性结 D.限制存取点的非线性结是（。 ，栈底元素是 经过以下栈的操作后，x的值为 InitStack(st);Push(st,a);Push(st,b);Pop(s,x); InitStack(st);Push(st,a);Push(st,b);Pop(s,x); 1,2,3,……,n则p2的值（。2B1C.最不适合用做链栈的链表是（以下链表没有头结点（如果以链表作为栈的结构，则元素出栈的时候（

设循环队列的下标范围是0~n-其头尾指针分别为f和则其元素个数 最不适合用做队列的链表是 用单链表（含有头结点）表示的队列的队头在链表的 ）位置 用单链表表示的链队的队尾在链表的 ）位置 （charch[]中，操作序列以’\0’为结束front==rear作为队满的条件。要求设计队列的结构和相关基本运算算法（队列元素为int型。栈的栈底是不变的，因此④处应该选D。确定了栈底，则两栈栈顶必在空间内，显然当两栈顶相遇的时候，空间被用尽，会产生上溢，⑤处选C。为n-i+1。因此本题选B。操作序列为IIIOIOI则