【文档说明】新版计算机考研小组(100)培训课件.ppt，共(108)页，1.161 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77613.html

以下为本文档部分文字说明：

计算机考研小组(100)2010年计算机考研基础班讲义精选1第一章绪论什么是数据结构直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。数据结构是指数据之间的关系按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储

器中，并在这些数据上定义一个运算集合，这就是数据结构。精选2学习数据结构的重要性1.“数据结构”在计算机科学中是一门综合性的专业基础课,在考研中占很大的分值。2.数据结构是介于数学、计算机硬件和计算机软件三者之间的一门

核心课程。3.数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。精选3§1.2数据结构的概念一、基本概念数据：能输入计算机且被能计算机处理的一切对象。数据元素：对现

实世界中某独立个体的数据描述。数据项：具有独立意义的最小数据单位。数据类型：每个数据项必须属于某确定的数据类型。基础精选4§1.3数据的逻辑结构一、基本概念数据对象：具有相同特征的数据元素的集合。

关系：在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。精选5§1.3数据的逻辑结构二、数据的逻辑结构设D表示数据元素的集合，R表示D上的关系的集合，则一个数

据结构B可表示为：B=（D，R）由此可见数据结构由两部分构成（1）表示各元素的信息D（2）表示数据之间关系的信息R一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素，则二元

组<a,b>表示a是b的前驱，b是a的后继。精选6§1.3数据的逻辑结构三、数据结构的分类线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。树状结构：除了一个根结点外，各结点有唯一的

前驱；所有的结点都可以有多个后继。网状结构：各结点可以有多个前驱或多个后继。精选7§1.4数据的存储结构数据结构在计算机中的表示称为数据的存储结构。数据结构包括结点的值及结点之间的关系，其存储结构

除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。四种基本的存储方式：1、顺序方式顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不

存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。精选8§1.4数据的存储结构2、链接方式链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。3、索引方式在线性结构中，

各结点可以依前驱、后继关系排成一个序列（a1,a2,a3,……an)。每个结点ai在序列中都对应一个序号i序号i也称为结点ai的索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。精选9§1.4数

据的存储结构4、散列方式利用该结点的值确定该结点的存储单元地址。精选10§1.5数据运算和算法1、数据运算按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。1）插入：往数据结构中

添加新的结点称为插入。2）删除：把指定的结点从数据结构中删除。3）更新：改变指定结点的值或者改变某些结点的关系称为更新。4）查找：在数据结构中查找某些满足条件的结点。5）排序：对线性表的各结点，按指定数据项的

值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。精选11§1.5数据运算和算法2、算法算法是对特定问题求解步骤的一种描述。算法应具有的几个特征：1）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。2）确定性：

算法的每一步骤应定义明确，没有二义。3）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。精选12§1.5数据运算和算法3、算法的评价对算法评价的几个指标空间复杂度空间复杂度是指执行算法所需要的辅助空间大小。时间复杂度时间复杂度是指执行完算法所需的运算次数

。精选13第二章线性表线性表是一种最简单、最常用的数据结构。线性表的主要存储结构有两种：顺序存储结构和链接存储结构。精选14§2.1线性表的定义及基本运算一、线性表的定义线性表是由n(n≥0)个性质相同的数据元素a1,a2,a3,…an组成的有限序列，记为(a1,

a2,a3,…an)。二、线性表的基本运算（1）置线性表为空表；（2）求线性表的长度；（3）读取线性表中的第i个元素；（4）修改线性表中的第i个元素；（5）查找线性表中具有某个特征值的数据元素；精选15§2

.1线性表的定义及基本运算二、线性表的基本运算（6）在线性表的第i个数据元素之前或之后插入一个新的数据元素；（7）删除线性表中第i个数据元素或满足给定条件的第一个数据元素；（8）对线性表中的所有元素按照给定的关键字大小进行排序。精选16§2.2

线性表的顺序存储结构及运算一、线性表的顺序存储结构线性表的顺序存储结构是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，即把线性表中相邻的结点存放在地址相邻的内存单元中。线性表在c语言中用一维数组表示。c语言的描述TypedefintET;#definem

axlen1000ETs[maxlen];精选17§2.2线性表的顺序存储结构及运算一、线性表的顺序存储结构线性表C语言描述的说明：在C语言中，数组的下标是从0开始的，数据结构中的结点的序号是从一开始的。因此在

线性表中的第一个元素是指S[0]。两个相邻结点ai和ai+1的存储位置记为LOC（ai）和LOC（ai+1），则结点满足以下关系LOC（ai+1）=LOC（ai）+1精选18§2.2线性表的顺序存储结构及运算二、线性表的运算1、插入运算的算法描述：intinsert

qlist(inti,ETx,ETs[],int*np){intj,n;n=*np;if((i<1)||(i>n+1))return(0);else{for(j=n;j>=i;j--)s[j]=s[j-1];s[j]=x;*np=++n;return(1);}

}精选19§2.2线性表的顺序存储结构及运算二、线性表的运算2、删除运算的算法描述：intdelqlist(inti,ETs[],int*np){intj,n;n=*np;if((i<1)||(i>n))return(0);else{for(j=i;j<n;j++)

s[j-1]=s[j];*np=--n;return(1);}}精选20§2.2线性表的顺序存储结构及运算二、线性表的运算3、查找运算的算法描述：intfincl(ETx,ETs[],intn){intj;for(i=0;i<n;i++)if(x==s[

i])break;if(i==n)return(0);return(i+1)}精选21§2.3线性表的链接存储结构及运算一、线性链表用链接方式存储的线性表称线性链表，简称链表。线性表的链接存储结构是用一组地址任意的存储单元来存放表中的数据元素，这组存储单元可以是连

续的，也可以是不连续的。数据指针数据域指针域单链表结点结构精选22§2.3线性表的链接存储结构及运算一、线性链表结点的数据定义形式：typedefstructnode{ETdata;structnode*link;}NODE;结点的内存

分配：（NODE*)malloc(sizeof(NODE))精选23§2.3线性表的链接存储结构及运算二、单链表及其运算线性链表的每一个结点只含有一个指针域，这样的线性链表称为单链表。单链表的运算：建表、查找、插入、删除以及判断是否为空表。

1、建立单链表首先生成表头结点，形成一个空链表，然后在表中逐一增加新的结点。（1）使用malloc函数，开辟新的存储单元q；（2）读入新结点数据，新结点的指针域为空（3）把新结点链接到链表上去。精选24建立

单链表的算法描述：NODE*create(intn){NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));p->data=0;p->link=NULL;head=p;for(i=1;i<=n;i++){q=(NOD

E*)malloc(sizeof(NODE));scanf("%d",&q->data);q->link=NULL;p->link=q;p=p->link;}return(head);}精选25§2.3线性表的链接存储结

构及运算2、查找链表中的X查找链表中是否存在结点X，算法的基本思想为：从表头指针指向的第一个结点开始，依次把表中结点的数据域和给定值X进行比较，直到某个结点的数据域的值等于给定值X（既查找成功），则返回该结点的地址；如果查找到表尾仍未找到（既查找失败），则返回

NULL。精选26查找单链表中结点X的算法描述：NODE*found(NODE*head,ETx){NODE*p;p=head->link;while((p!=NULL)&&(p->data!=x))p=p

->link;return(p);}精选27§2.3线性表的链接存储结构及运算3、在单链表中插入新结点X在链表中的某一结点p之后插入一个数据为X的新结点。过程如下：（1）生成一个新结点q，将X赋给q->data;（2）修改有关结点的指针域：将原p结点的后继作为q结点的后继

，q结点作为p结点的后继。精选28在单链表中插入新结点X的算法描述：voidinsert(NODE*head,NODE*p,ETx){NODE*q;q=(NODE*)malloc(sizeof(NODE));q

->data=x;if(head->link==NULL){head->link=q;q->link=NULL;}else{q->link=p->link;p->link=q;}}精选29§2.3线性表的链接存储结构及运算4、删除单链表中的结点

X删除单链表中的结点X，并由系统收回其占用的存储空间。过程如下：（1）设定两指针p和q，p指针指向被删除结点；q为跟踪结点，指向被删除结点的前驱结点;（2）p从表头指针head指向的第一个结点开始向后依次进行搜索。当p->data等于X时，被删除结点找到。（3

）修改p的前驱结点q的指针域：使被删除结点的后继结点成为其前驱结点的后继结点，既q->link=p->link，p结点被删除，然后再释放存储空间。精选30在单链表中删除结点X的算法描述：voiddelete(NODE*head,ETx){NO

DE*p,*q;p=head;q=p;p=p->link;while((p!=NULL)&&(p->data!=x)){q=p;p=p->link;}if(p==NULL)printf("Notfound!\n");els

e{q->link=p->link;free(p);}}精选31§2.3线性表的链接存储结构及运算三、循环链表链表中的最后一个结点的指针指向链表中第一个结点，使链表形成一个环行，此链表称循环链表。循环链表是线性链表的一种变形。其优点是从链表中任何一个结点出

发都可以访问到表中的所有结点。在循环链表中为了使空表和非空表处理一致，可以附加一个表头结点。精选32§2.3线性表的链接存储结构及运算三、循环链表非空表（a)headhead空表（b)精选33(1)在头指针为head的循环链表查找值为x的前驱结点。NODE*lookno

de(head,x)ETx;NODE*head;{NODE*p;p=head;while((p->link!=head)&&(((p->link)->data)!=x))p=->link;return(p);}精选34

(2)在头指针为head的循环链表在值为x的结点之前插入一个值为b的新结点。NODEinsnode(head,x,b)ETx,b;NODE*head;{NODE*p,*q;p=(NODE*)malloc(sizeof(NODE));p->data

=b;q=looknode(head,x);p->link=q->link;q->link=p;return;}精选35(3)在头指针为head的循环链表中，删除值为x的结点。Voiddelnode(head,x)ETx;NODE*head;{NODE*p,*q;q=looknode(hea

d,x);if(q->link==head){printf(“Nothisnodethelist!\n”)return;}p=q->link;q->link=p->link;free(p);return;}精选36§2.3线性表的链接存储结构及运算四、循环链表一个

链表的每一个结点含有两个指针域，一个指针指向其前驱结点，另一个指针指向其后继结点，这样的链表称为双向链表。精选37五、双向链表head∧∧llinkrlinkdata带头结点的双向链表双向链表的结点结构精选

38§2.4数组一、数组的定义数组是由一组类型相同的数据元素构造而成。若数组元素只含有一个下标，这样的数组称为一维数组。当一个数组的每一个数组元素都含有两个下标时，该数组称为两维数组。精选39§2.4数组二、数组

的存储结构数组是一种顺序存储结构。也就是将数组元素顺序地存放在一片连续的存储单元中。三、规则矩阵的压缩存储有时矩阵中包含大量的零元素（或某一确定值的元素），为了节省存储空间，可以对这类矩阵采用压缩存储。所谓压缩存

储是指对零元素不分配存储空间，而只对非零元素进行存储。压缩存储必须能够体现矩阵的逻辑结构。精选40§2.4数组四、稀疏矩阵及存储当一个矩阵的非零元素的个数远远少于零元素的个数时，称该矩阵为稀疏矩阵。对稀

疏矩阵的存储方式常采用压缩存储。方法有两种：三元组表和十字链表。1、在稀疏矩阵中，每一个非零元素可以用它所在的行号i、列号j以及元素值aij组成的三元组(i,j,aij)来表示。三元组的结点定义：typedefstructnode{intr,c;ETv;

}NODE;精选41§2.4数组4001000200900000000700050556114141232319457545rcvMa[0]Ma[1]Ma[2]Ma[3]Ma[4]Ma[5]Ma[6]A=精选42§2.4数组40900000000200010005000705561

14139322411455547rcvMb[0]Mb[1]Mb[2]Mb[3]Mb[4]Mb[5]Mb[6]B=精选43§2.4数组实现矩阵转置的算法：intsyz(NODEma[],NODEmb[])inti,j,n

,t,k;{if(ma[0].v==0)return(0);n=ma[0].c;t=ma[0].v;mb[0].r=n;mb[0].c=ma[0].r;mb[0].v=t;k=1;for(j=1;j<=n;j++)for(i=1;i<=t

;i++)if(ma[i].c==j){mb[k].r=ma[i].c;mb[k].c=ma[i].r;mb[k].v=ma[i].v;k++;}return(1);}精选44§2.4数组2、稀疏矩阵的链接存储稀

疏矩阵的链接存储是一种即带行指针又带列指针的链接存储结构。对稀疏矩阵的链接存储是对其相应的三元组线性表进行链接存储，链接表中的每一结点表示一个非零元素的三元组，每一个结点即处于同一行的单链表中又处于同一列的单链表中，即处于所在行的单链表和所在列单链表的交叉点处，

整个稀疏矩阵由十字交叉链表结构组成，故称为十字链表。RowColvalDownright行域列域值域向下域向右域精选45§2.4广义表一、广义表的定义广义表是线性表的推广，简称为表。它是由n(n≥0)个元素的有限序列。记为：A=(a1,a2,a3,……an)。其中A为表名；n表示广义表的

长度，既元素的个数；元素ai可以是数据元素，称为单元素；也可以是表，称为子表或表元素。广义表是一种递归的数据结构。精选46第三章栈与队列栈与队列是线性表中最重要的、实际应用最广泛的特例。栈和队列的逻辑结构和线性表相同，只是运算规则有更多的限制。本章的基本内容：1、栈和队列的定义；2、

栈和队列的存储表示；3、栈和队列基本运算的实现算法以及栈和队列的应用。精选47§3.1栈一、栈的定义栈(Stack)是一种特殊的线性表，栈的插入和删除操作均在表的一端进行。允许插入和删除的一端称为栈顶(Top)

，另一端称为栈底(Bottom)。若给定栈S=(a0,a1,a2,a3,…ai,…an-1),则称an-1栈顶元素，称a0为栈底元素。an-1a1a0栈底Bottom栈顶Top精选48§3.1栈栈的主要运算有：(1)进栈，向栈顶插入一个新元素；(2)出栈，删除栈顶元

素；(3)读栈，读取栈顶元素；(4)置空栈，将栈置为空栈；(5)判栈空，判断一个栈是否为空。精选49§3.1.2栈的存储结构及其运算1、栈的顺序存储结构及运算与第二章讨论的一般的顺序存储结构的线性表一样，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也称为顺序栈。

因此，我们可以使用一维数组s[MAXLEN]来作为栈的顺序存储空间。设指针top指向栈顶元素的当前位置，以数组小下标的一端作为栈底，通常以top=-1时为空栈，在元素进栈时指针top不断地加1，当top等于数组的最大下标值时则栈满。精选50§3.1.2栈的存储结构及其运算用C语言定义的顺序存储结构

的栈如下：#defineMAXLEN/*最大元素数*/ints[MAXLEN];inttop;鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈时，应设栈顶指针top=-1时为空栈。假设有一个栈T=(a,b,c,d,e,

f),则栈T所对应的顺序存储结构用图形表示如下：精选51§3.1.2栈的存储结构及其运算……fedcbagfedcbaedcbaTop-1012345012345012345012346TopTopTopMAXLEN-1MAXLEN-1MAXLEN-1MAXLEN-1精选52§3.1.

2栈的存储结构及其运算(1)置空栈voidstack(s)ints[];{top=-1;}(2)判定空栈intempty(s)ints[];{if(top==-1)return(1);elsereturn(0);}精选53§3.1.2栈的

存储结构及其运算(3)进栈intpush(s,x)ints[],x;{if(top==MAXLEN-1){printf(“stackoverflow!\n”);return(1);}elsetop=top+1;s[top]=

x;return(0);}精选54§3.1.2栈的存储结构及其运算(4)出栈intpopsh(s,y)ints[],*y;{if(top==-1){printf(“stackunderflow!\n”);return(1);}el

se{*y=s[top];top=top-1;return(0);}}精选55§3.1.2栈的存储结构及其运算多栈共享邻接空间在计算机系统软件中，各种高级语言的编译系统都离不开栈的使用。常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈预先

分配一个足够大的存储空间，但实际中很难准确地估计。另一面方面，若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使它们的存储空间互补。这就是栈的共享邻接空间。精选56§3.1.2栈的存

储结构及其运算双向栈在一维数组中的实现栈的共享中最常见的是两栈的共享。假设两个栈共享一维数组stack[MAXLEN]，则可以利用栈的“栈底位置不变，栈顶位置动态变化”的特性，两个栈底分别为-1和MAXLEN-1，而它们的栈顶都往中间方向延伸。因此，只要整个数组stack[MAXL

EN]未被占满，无论哪个栈的入栈都不会发生上溢。自由区lefttoprighttop0MAXLEN-1精选57§3.1.2栈的存储结构及其运算2、栈的链式存储结构栈也可以采用链式存储结构表示，这种结构的栈简称为链栈。在一个链栈中，栈底就是

链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top唯一确定，当top为NULL时，是一个空栈。链栈的结点类

型C语言定义为：typedefstructnode{ETdata;structnode*link;}NODE;精选58§3.1.2栈的存储结构及其运算(1)入栈新元素x入栈的C语言描述：NODE*pushstack(NODE*top,ETx){NODE

*p;p=(NODE*)malloc(sizeof(NODE));p->data=x;p->link=top;top=p;return(top);}精选59§3.1.2栈的存储结构及其运算(2)出栈栈顶元素出栈算法的C语言描述：NODE*po

pstack(NODE*top,ET*p){NODE*q;if(top!=NULL){*q=top;*p=top->data;top=top->link;free(q);}return(top);}精选60§3.1.2栈的存储结构及其运

算3、栈的应用举例表达式求值是程序设计语言编译中的一个最基本问题。它的实现方法是栈的一个典型的应用实例。(1)中缀算术表达式：将运算符置于两个操作数中间的算术表达式，称中缀表达史。（2）后缀表达式：将运算符置于两个操作数的后面的算术表达式称为后缀表达式。这种表达式

不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行。计算机在处理这种表达式时，只需对其扫描一遍，就可完成计算。精选61§3.2队列在日常生活中队列很常见，如，我们经常排队购物或购票，排队是体

现了“先来先服务”（即“先进先出”）的原则。队列在计算机系统中的应用也非常广泛。例如：操作系统中的作业排队。在多道程序运行的计算机系统中，可以同时有多个作业运行，它们的运算结果都需要通过通道输出，若通道尚未完成输出，

则后来的作业应排队等待，每当通道完成输出时，则从队列的队头退出作业的输出操作，而凡是申请该通道输出的作业都从队尾进入该队列。精选62§3.2队列计算机系统中输入输出缓冲区的结构也是队列的应用。在计算机系统中经常会遇到两个设备之间的数据传输

，不同的设备通常处理数据的速度是不同的，当需要在它们之间连续处理一批数据时，高速设备总是要等待低速设备，这就造成计算机处理效率的大大降低。为了解决这一速度不匹配的矛盾，通常就是在这两个设备之间设置一个缓冲区。这样

，高速设备就不必每次等待低速设备处理完一个数据，而是把要处理的数据依次从一端加入缓冲区，而低速设备从另一端取走要处理的数据。精选63§3.2队列一、队列的定义及运算队列也是一种特殊的线性表，它是只允许在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为

队尾，允许删除的一端称为队首。若给定队列q=(a0,a1,a2,a3,a4,……,an-1)，我们称a0是队首元素，an-1是队尾元素。a0,a1,a2,a3,a4,……,ai……an-1出队入队精选64第四章递

归递归是程序设计中一个重要的算法设计方法和技术。递归子程序是通过调用自身来完成与自身要求相同的子问题的求解,并利用系统内部功能自动实现调用过程中信息的保存与恢复，而省略了程序设计中的许多细节操作，简化了程序设计过程,使程序

设计人员可以集中注意力于主要问题求解上。精选65§4.1递归的定义递归就是一个事件或对象部分由自己组成。递归算法包括递推和回归两部分（1）递推：就是为得到问题的解，将其推倒比原来问题简单的问题的求解。（2）就是指当“简单的问题得

到解后，回归到原问题的解上。精选66§4.2递归的实现1、采用递归算法具备的条件（1）所需解决的问题可以转化成另一个问题，而解决新问题的方法与原始问题的解法相同。（2）必须具备终止递归的条件。程序中不能出现无终止的递归调用，而只能出现有限次的，有终止的递归调用。精

选67§4.2递归的实现2、递归算法示例:n！（阶乘）算法的求解。intfact(intn){if(n==0){s=1;return1;}else{s=n*fact(n-1);returns;}}voidmain(){intn;n=fact(5);printf(“n=%d\n”

,n}精选684.3阶乘递归的实现main()参数表返回地址活动记录进退栈示意图fact(5)5ReLoc1fact(4)4ReLoc2fact(3)3ReLoc3fact(2)2ReLoc4fact(1)1ReLoc50ReL

oc6s=fact(1)=1*fact(0)=1s=fact(2)=2*fact(1)=2s=fact(3)=3*fact(2)=6s=fact(4)=4*fact(3)=24s=fact(5)=5*fact(4)=120fact(0)=1调用者

精选69主函数mani()N=fact(5)第一层调用n=5s=5*fact(4)第二层调用n=4s=4*fact(3)第三层调用n=3S=3*fact(2)第四层调用n=2S=2*fact(1)第五层调用n=1S=1fact(1)=1fact(2)=2fact(3)=6fa

ct(4)=24fact(5)=120输出s=120.00递归调用过程示意图从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为

主函数调用，其它则为在fact函数内调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact结果为1，然后再一一返回计算，最终得到结果。精选70例汉诺塔传说在创世纪时，在一个叫Brahma的寺庙里，有三个

柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。移动时的规则：•每次只能移动一个盘子；•只能小盘子在大盘子上面；•可以使用任一柱子。当工作做完之后，就标志着世界永远和平。xyznn–1精选71分析：设三根柱子分别为x，y,z,盘子在x柱上

，要移到z柱上。1、当n=1时，盘子直接从x柱移到z柱上；2、当n>1时,则①设法将前n–1个盘子借助z，从x移到y柱上，把盘子n从x移到z柱上；②把n–1个盘子从y移到z柱上。精选72Hanoi问题voidHanoi(intn,charx,chary,charz){//将n个编号

从上到下为1…n的盘子从x柱，借助y柱移到z柱if(n==1)move(x,1,z);//将编号为1的盘子从x柱移到z柱else{//将n-1个编号从上到下为1…n-1的盘子从x柱，借助y柱移到z柱Ha

noi(n-1,x,z,y);move(x,n,z);//将编号为n的盘子从x柱移到z柱//将n-1个编号从上到下为1…n-1的盘子从y柱，借助x柱移到z柱Hanoi(n-1,y,x,z);}}//Hanoi精选73第五章串在计算机的各方面应用中

，非数值处理问题的应用越来越多。如程序源代码，在事务处理系统中，用户的姓名和地址及货物的名称、规格等，都是作为一种字符串数据进行处理的。字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串

的数据对象约束为字符集。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。精选74§5.1串的基

本概念串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作s=〃a0a1a2…an-1〃(n≥0)其中：s为串名，用双引号括起来的字符序列是串的值；ai(0≤i≤n-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部

分；字符串字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Nullstring），如：s=〃〃，它的长度为零；仅由空格组成的的串称为空格串，如：s=〃└┘〃；若串中含有空格，在计

算串长时，空格应计入串的长度中，如：s=〃I’mastudent〃的长度为13。精选75§5.2串的存储结构一、顺序存储和线性表一样，可以用一组连续的存储单元依次存放串中各字符。利用字符单元地址的顺序表示串中字符的相邻关系。struct

string{charch_string[maxlen];intlen;};当计算机按字(Word)为单位编址时，一个存储单元由若干字节组成。这时，顺序存储结构有紧凑格式和非紧凑格式两种。精选76§5.3串的基本运算串的基本运算有赋值、串连接、求串长、取子串、子串定位、判断两个串

是否相等、插入子串，删除子串等。在本节中，我们尽可能以C语言的库函数表示其中的一些运算，若没有库函数，则用自定义函数说明。structstring{charch_string[maxlen];intlen;};精选771、串连接所谓串连接就是把一个串连接在另一个串

的末尾，组成一个新串。Structstringconcat(s1,s2)structstrings1,s2;{structstrings;inti;if(s1.len+s2.len<=maxlen){for(i=0;i<s1.len;i++)s.ch_string[i]=s1

.ch_string[i];for(i=0;i<s2.len;i++)s.ch_string[s1.len+i]=s2.ch_string[i];s.len=s1.len+s2.len;}elses.le

n=0;return(s);}精选782、串相等判断当两个串的长度相等且各对应位置上的字符都相等时，两个字符串才相等。intequal(s1,s2)structstrings1,s2;{inti;if(s1.len!=s2.len)return(0)

;else{for(i=0;i<s1.len;i++)if(s1.ch_string[i]!=s2.ch_string[i])return(0);return(1);}精选793、取子串所谓取子串就是在给定字符串中从指定位置开始连续取出

若干字符，然后将取出的字符作为子串的值。structstringsubstr(s,n1,n2)structstrings;intn1,n2;{structstringsub;inti;if((n1>=1)&&(

n1<=s.len)&&(n2>=1)&&(n2<=s.len-n1+1)){for(i=0;i<=n2;i++)sub.ch_string[i]=s.ch_string[n1+i]sub.len=n2;}elsesub.len=0;return(sub);}精选804、插入子串所谓

插入子串就是在指定位置上插入一个子串。structstringinsert(s,s1,n)structstrings,s1;intn;{structstringsub1,sub2,str;if((s.

len+s1.len<=maxlen)&&(n>=1)&&(n<=s.len+1)){sub1=substr(s,1,n-1);sub2=substr(s,n,s.len-n+1);str=concat(concat(sub1,s1),s

ub2);}elsestr.len=0;return(str);}精选815、子串定位所谓子串定位就是给出子串在母串中的位置。子串的定位操作也称模式匹配。intindex(s,s1)structstrings,s1;{in

ti,j,k;i=0;while(i<=s.len–s1.len){j=i;k=0;while((k<s1.len)&&(s.ch_s[j]==s1.ch_s[k])){j=j+1;k=k+1;}if(k==s1.len)ret

urn(i+1);elsei=i+1;}return(0);}精选82第七章树形结构数据结构可分为线性结构和非线性结构两大类树形结构：是一类非常重要的非线性结构，它用于描述数据之间的层次关系本章主要介绍树、二叉树的定义、性质及存储结

构精选83§7.1树1、树的定义树(Tree)是包含n(n>0)个结点的有穷集合K，且在K中定义了一个关系N，N满足以下条件：(1)有且仅有一个结点K0它对于关系N来说没有前驱，称K0为树的根结点；(2)除K0外，K中的每一个结点对于关系N来说有且仅有一个前驱；(3)K

中各结点对关系N来说可以有m个后继精选84§7.2树的常用术语树的结点：包含一个数据元素及若干指向其子树的分支结点的度：结点所拥有的子树的个数称为该结点的度叶子：度为零的结点，又称终端结点树的深度：树中各结点层次的最大值称为该树的深度精选85§7.3二叉树二叉数的定义二叉数的

存储结构：顺序存储结构、链式存储结构二叉数的遍历：就是按某一种规则访问树中的每一个结点，且使得每个结点均被访问一次，而且仅被访问一次。二叉数的遍历方法：前序遍历、中序遍历、后序遍历精选86第九章查找查找(Searching)又称检索。就是从一个数据元素集合

中找出某个特定的数据元素；它是数据处理中经常使用的一种重要的操作，尤其是当所涉及的数据量较大时，查找算法的优劣对整个软件的效率影响很大；本章首先介绍关于查找的基本概念，然后讨论查找的各种方法，最后对各种查找方法作一比较。精选87§9.1查找的基本概念查找表(SearchTabl

e)是由同一类型的数据元素(或记录)构成的集合对查找表进行的操作有以下四种(1)查询某个特定的数据元素是否在查找表中(2)检索某个特定的数据元素的各种属性(3)在查找表中插入一个数据元素(4)从查找表中删除某个数据元素精选88§9.1查找的基本概念静态查找表(Stati

cSearchTable)若只对查找表进行查找和检索两种操作,则称此查找表为静态查找表动态查找表(DynamicSearchtable)若再查找过程中同时插入查找表中不存在的记录,或从查找表中删除已存在的某个记录,则称此类表为动态查找表关

键字(Key)标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素(或记录)精选89§9.2线性表的查找顺序查找(sequentialSearch)也称线性查找,是一种最简单的查找方法,它属于静态查找顺序查找方法顺序查找的基本思想:从表的一端开始

,顺序扫描线性表,依次用待查找的关键字值与线性表里各结点的关键字值逐个比较,若在表中找到了某个记录的关键字与待查找的关键字值相等,表明查找成功;如果找遍所有结点也没有与待查找的关键字值相等,则表明查找失败精选90§9.2线性表的查找main(){inta[100]

={0,12,5,36,58,21,61,15,16,32,17};inti,key;printf("InputtheKey:");scanf("%d",&key);a[0]=key;for(i=10;a[i]!=ke

y;i--);if(i==0)printf("SearchingFail!\n");else{printf("SearchingSuccess!\n");printf("a[%d]=%d\n",i,key);}}精选91§9.2线性表的查找折半查找(binar

ySearch)也称为二分查找,是一种效率较高的查找方法,查找时要求表中的结点按关键字的大小排序折半查找方法折半查找的基本思想:首先用要查找的关键字值与中间位置结点的关键字值相比较(这个中间结点把线性表分成了两个子表).比较结果相等,则查找成功;若不相等,再

根据要查找的关键字值与该中间结点关键字值的大小确定下一步查找在哪个子表中进行精选92#include<stdio.h>main(){inta[100]={0,5,13,19,22,37,56,64,75,80,88,92};intlow=1,high=11,mid,key,fla

g=0;printf("InputtheKey:");scanf("%d",&key);while(low<=high){mid=(low+high)/2;if(key==a[mid]){printf("SearchingSuccess!");pr

intf("a[%d]=%d\n",mid,key);flag=1;break;}elseif(key<a[mid])high=mid-1;elselow=mid+1;}if(flag==0)printf("SearchingFail!\n");}精选93§第十章排序排序是在数据处理中经常使用的

一种重要的算法。如何进行排序，特别是高效率的排序是计算机应用中的重要课题。排序的目的：是方便查找排序分为：内部排序、外部排序本章主要介绍几种常用的内部排序方法：插入排序、选择排序、交换排序的基本思想、排序步骤及实现方法精选94§10.1排序的基本概念关键字(Key)标志数据元素(或记

录)中某个数据项的值,用它可以标识一个数据元素(或记录)排序(Sorting)是将一组记录按照记录中某个关键字进行有序（递增或递减）排列过程精选95§10.2内部排序插入排序插入排序就是按关键字大小将一个记录插入到一个有序的文件中的适当位置，并且插入后使

文件仍然有序。直接插入排序每一趟将一个待排序的记录，按关键字的大小插入到已经排序的部分文件中适当位置，直到全部插入完成精选96main(){inta[100]={0,19,1,23,17,19,55

,84,15};inti,j;for(i=2;i<=8;++i)if(a[i]<a[i-1]){a[0]=a[i];for(j=i-1;a[0]<a[j];--j)a[j+1]=a[j];a[j+1]=a[0];}for(i=1;i<=8;i++

)printf("%d",a[i]);printf("\n");}精选97§10.2内部排序折半插入排序由于插入排序的基本操作是在一个有序表中进行查找和插入，而查找操作可利用折半查找来实现，由此进行的插

入排序称之为折半插入排列（BinaryInsertionSort），又称为二分法插入排序。精选98main(){inta[100]={0,19,1,23,17,19,55,84,15};inti,j,low,high,m;for(i=2;i<=8;++i)if(a[i]<a[i-1]){a[

0]=a[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;if(a[0]<a[m])high=m-1;elselow=m+1;}for(j=i-1;j>=high+1;--j)a[j+1]=a[j

];a[high+1]=a[0];}for(i=1;i<=8;i++)printf("%d",a[i]);printf("\n");}精选99§10.2内部排序冒泡排序冒泡排序的基本思想：将待排序的序列中的关键字r1.key与第二个关键字r2.

key进行比较（从小到大），如果r1.key>r2.key则交换r1和r2记录序列中的位置，否则不交换，然后再接着对当前序列中的第二个和第三个记录作同样的比较，依次类推，直到序列中最后两个记录处理完为止。精选10

0main(){inta[100]={0,5,7,3,8,2,9,1,4};inti,j,flag,temp;flag=1;for(i=1;i<9&&flag==1;i++){flag=0;for(j=0;j<9-i;j++)if(a[j]>a[j+1]){flag

=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}for(i=1;i<=8;i++)printf("%d",a[i]);printf("\n");}精选101§10.2内部排序快速排序快速排序是由冒泡排序改进而得的，是一种分区交换

排序方法排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。精选1

02voidq_sort(int*a,intleft,intright){intpartition;/*分割元素*/inttemp,i,j,k;if(left<right)/*是否继续分割*/{i=left;/*分割的最左*/j=right+1;/*分割的最右*/partition=a[left

];/*取第一个元素*/do{do{/*从左往右找*/i++;}while(a[i]<partition);do{/*从右往左找*/j--;}while(a[j]>partition);if(i<j){temp=a[i];a[i]=a[j];a[j]=temp;}/*交换

数据*/}while(i<j);temp=a[left];a[left]=a[j];a[j]=temp;/*交换数据*/printf("输出结果:");for(k=left;k<=right;k++)/*输出处理数据*/printf("%d",a[k]);print

f("\n");/*换行*/q_sort(a,left,j-1);/*快速排序递归调用*/q_sort(a,j+1,right);/*快速排序递归调用*/}}精选103§10.2内部排序选择排序直接选择排序的基本思想：从待排序的所有记录中，选取关键字最小的记录

并将它与原始序列的第一个记录交换位置，然后从去掉了关键字最小的记录的剩余记录中选择关键字最小的记录与原始记录中的第二个记录交换位置。精选104main(){inta[100]={0,5,7,3,8,2,9,1,4};inti,j,k,w;for(i

=1;i<8;i++){k=i;for(j=i+1;j<9;j++)if(a[j]<a[k])k=j;if(k!=i){w=a[i];a[i]=a[k];a[k]=w;}}for(i=1;i<=8;i++)printf("%d",a[i]);printf("\n")

;}精选105§10.2内部排序快速排序快速排序是由冒泡排序改进而得的，是一种分区交换排序方法排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键

字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。精选106§10.2内部排序快速排序快速排序是由冒泡排序改进而得的，是一种分区交换排序方法排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆

序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。精选107§10.2内部排序快

速排序快速排序是由冒泡排序改进而得的，是一种分区交换排序方法排序的基本思想：一趟快速排序采用从两头向中间扫描的办法，同时交换与基准记录逆序的记录。在待排序的n个记录中任取一个记录，把该记录放入最终位置后，序列被这个记录分割成两部分，所有关键字比该记录关键字小的放置在前

一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间。精选108