还剩23页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
ENDP;PROC DELQUEUEVAR cq:cyclicqueue;｛cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空｝｛则将队头元素出队｝IF cq.tag=0THEN returnfalse｛队空｝ELSE[cq.front:=cq.front+1MOD m;IF cq.front=cq.rear THEN cq.tag:=0｛队空｝ENDP;CONST m=niaxlen;｛队列长度｝TYPEeyelicqueue二RECORD｛只设尾指针和队列长度的循环队列｝elem:ARRAY[
0..m-l]OF elemtype;rear:
0..m-1;length:
0..m;｛队列长度｝END;PROC INITqueueVAR q:cyclicqueue;｛初始化｝q.rear:=0;q.length:=0;ENDP;FUNC addqueue VARq:cyclicqueue;x:elemtype:boolean;｛q是由尾指针和长度标志的循环队列，本算法是入队操作，若队列不满，｝｛将x插入到队尾｝IF q.length=mTHEN addqueue:=false｛队列满｝ELSE[q.rear:=q.rear+1mod m;q.elem[q.rear]:=x;q.length;=q.length+1;add_queue:=true｛入队成功｝ENDF;FUNC dd_queueVAR q:cyclicqueue;x;elemtype:boolean;｛q是由尾指针和长度标志的循环队列，本算法是出队操作，若队列不空，｝｛将将队头元素出列，并赋给X,队长度减1｝IF q.length=0THEN dd_queue:二false｛队空｝ELSE[front;=q.rear-q.length+l+m modm x:二q.elem[front]ENDF;第四章串、内容提要
1、
1、是数据元素为字符的线性表，串的定义及操作
2、
2、的根本操作，编制算法求串的其它操作
3、
3、的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题静态和动态块链结构，堆结构存储的优缺点
4、
4、朴素模式匹配算法及改良KMP算法
二、学习重点
1、
1、串的根本操作，编写串的其他操作如index,replace等
2、在串的模式匹配中，求匹配串的nextval函数值
3、尽管朴素的模式匹配的时间复杂度是m*n,KMP算法是Oni+n,但在一般情况下，前者实际执行时间近似Om+n,因此至今仍被采用KMP算法仅在主串与模式串存在许多“局部匹配〃时才显得比前者块的多，其主要优点是主串不回喇
5、
5、串操作在存储结构下的实现
三、例题解析
1、利用串的如下根本运算create s,assign s,t,length s,substr s,start,len,concat si,s2,编写操作replace的算法PROC replaceVARs:string;t,v:string;｛本算法实现串的置换操作，用串v置换串s中所有非重叠的t串｝i:=INDEXs,t;｛判s中有无t｝IF i0THEN[CREATE temp,｛t为临时串变量，存放局部结果｝m:二LENGTH t;n:=LENGTH s;WHILE i0DO[ASSIGN temp,CONCATtemp,SUBSTRs,1,i-1,v;｛用v替换t形成局部结果｝ASSIGN s,SUBSTRs,i+m,n-i-m+1;｛t串以后形成新s串｝n:二n-i-l-m;i:二INDEX s,t;ASSIGN s,CONCATtemp,s;｛将剩余s连接临时串t再赋给s｝]ENDP;FUNC indexsi:string;t:string:integer;｛本算法求串t在串S中的第一次出现结果是若t在S中，则给出串t的第一个字符在串S中的位置，若不存在，则返回0｝j=1;m:=lengths;n:=lengtht;eq:=true;WHILE j=m-n+l ANDeq DOIFequalsubstr s,j,n,tTHEN eq:=falseELSE j:=j+l；IF j=m+n-l THENindex:=jELSE index:=0ENDF；{index}【讨论】此题是用给定的根本操作，编写其它操作的算法这种类型题较多，必须严格按题的要求来做，不准选择具体存储结构否则，即使全对，也很难得分22设目标为t=abcaabbabcabaacbacba,模式串p=abcabaa,1计算P的NEXTVAL函数值；2不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；【解答】1P的NEXTVAL函数值如下；模式Pnextvaljc b a cba第一趟匹配第二趟匹配第三趟匹配第四趟匹配成功【讨论】为写NEXTVAL方便，可先写出NEXT函数值,
3、在由此求NEXTVAL.字符串s满足下式，其中HEAD和TA字的定义同广义表类似，如HEA和XYZ二X,TAIL XYZ=YZ-则S=concatheadtails,headtailtails=,de，求字符串So可供选择的答案是A abedB aebdC aedbD adeb正确答案是Do第五章数组和广义表
一、内容提要1,b数组的逻辑结构定义及存储，2,2,稀疏矩阵含特殊矩阵的存储及运算3,3,广义表的定以及存储4,4,广义表运算的递归算法
二、学习重点1,1,数组主要是二维在以行序为主的存储中的地址计算方法2,2,特殊矩阵在压缩存储时的下标变换3,3,稀疏矩阵的三元组表存储结构及矩阵移植的算法4,4,稀疏矩阵的十字链表存储方法及十字链表生成算法5,5,广义表的HEAD和TAIL运算6,6,给定广义表画出其存储结构
三、例题解析7,7,从广义表的递归算法，掌握如何编写递归算法
1、字符串二维数组A[
0.・8,L.10],每个元素由6个字符组成，每个字符占一个存储单元，则1存放A需要多少个字节？2A的第8列和第5行共占多少字节？3按行序存储时，A[8,5]和按列存储时哪个元素时的地址相同？【解答】154021083A[3,10]
2、编写算法，将自然数一步按蛇形填入n xn矩阵中例如，1—42如右图所示【分析】此题要求在N的方阵中填人M个数，关键是控制下标设坐标原点在矩阵的左上角，且i是向下增长，j向右增长原点的坐标为1,1【算法】PROC sqrmgcVAR a:arr;n:integer;本算法将自然数1—n按蛇形填入N XN矩阵中,a是二维数组｝i:=1;j:=1;k:=1;WHILE i=n AND j=n DO[WHILE i=n AND j0DO[a[i,j]:=k;i:=i+1;j:=jT;k:=k+1]IF jlTHEN IF i〈=n THENj:二lELSE[j:=j+2;i:=n]ELSE[i:=n;j:=j+2]WHILE i0ANDj=N DO[a[i,j]:=k;i:=i-l;j:=j+l；k:=k+1]IF ilTHEN IFj=n THENi:=lELSE[i:=i+2;j:=n]ELSE[j:=n;i:=i+2]ENDP;{sqrmgc
3、求以下广义表操作结果11HEAD TAILHEAD a,b,c,d22TAILHEADTAILa,b,c,d【解答】⑴b2d
4、利用广义表的HEAD和TAIL操作，写出如上题的表达式，把原子banana从以下广义表中别离出来11L1=apple,pear,banana,orange;22L2=apple,pear,banana,orange;【解答】1HEAD HEADHEAD TAILTAIL LI3HEADHEADTAILHEADTAILLI第六章树和二叉树
一、内容提要
1、树是复杂的非线性数据结构，树，二叉树的递归定义，根本概念，术语
2、二叉树的性质，存储结构
3、二叉树的遍历算法（递归，非递归）
4、线索二叉树
5、树的存储结构，树、森林的遍历及和二叉树的相互转换
6、二叉树的应用表达式求值、判定问题及哈夫曼树和哈夫曼编码
二、学习重点（本章内容是本课程的重点）
1、二叉树性质及证明方法，并能把这种方法推广到K叉树
2、二叉树遍历的递归算法，本书中介绍了三种（先、中、后序）方法，另三种也应会用前序和中序的非递归遍历遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为
0、
1、2的结点数,二叉树的相似、全等、复制等等的算法
3、由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树，手工模拟及编写算法由前序和后序序列不能唯一确定一棵二叉树
4、二叉树线索化的实质是建立结点在相应序列中的前驱和后继之间的直接联系在何序（前、中、后）下进行何种（全、前驱、后继）线索化，并求某结点相应的前驱和后继
5、完全二叉树的性质，顺序存储结构和二叉树链表存储结构的相互转换
6、树的双亲表示法和孩子兄弟表示法间的相互转换
7、树、森林和二叉树间的相互转换（“连线〃、“切线”和旋转〃）
8、哈夫曼树的定义、构造及求哈夫曼编码
三、例题及分析在二叉树中查找其数据域为x的结点如存在，返回该结点指针，否则返回空指针【分析】可采用递归遍历算法【算法】PROC search（bt:bitreptr;x:datatype）;{bt是bitreptr型的二叉树，x是待查找数据值，本算法递归遍历二叉树，在遍历中进行查找算法中p是调用本过程的过程中定义的变量，初值为NIL,查找成功后，p指向数据域为x的结点found是初值为false的变量从本过程返回后，测试found以确定是否查找成功}IF（btONIL）AND NOT foundTHEN[IF btdata=xTHEN[p:=bt;found:=true]search（bt\Ichild,x）;search（bt二rchild,x）;ENDP;{serch）【讨论】本算法核心语句有三个（即第一个THEN后的语句第一个语句是“访问〃根结点.后两个语句是递归遍历（相对位置不变）在这三个语句中，由“访问〃语句所处位置不同（前、中、后），形成三种递归遍历方法前序、中序和后序Found是为查到x就立即不再遍历未遍历结点而设立的若要再考虑本算法的优化，则在两个调用语句中可加上If bt\IchildONIL AND NOT found和If bt\rchildNIL AND NOT found其优点是在左右为空时不必再调用，且一旦找到x就立即退出
2.设二叉树采用二叉链表作为存储结构，试编写算法求二叉树的结点数【分析】计算二叉树结点数的数学模型如下f bt=0若bt=nilf bt=f bt二Ichild+f bt二rchild+1否则【算法】FUNC nodesbt:bitreptr:integer;IF bt=nilTHEN nodes:=0ELSE[nl:=nodesbt\Ichildn2:=nodesbt二rchildnodes:=ni+n2+lENDF｛nodes【讨论】二叉树由根、左子树、右子树三局部组成，很多问题如求叶子、度
1、度2结点数，可分解到三局部求解，上面写出数学递归模型是有普遍意义的例如
1.二叉树相似ftl,t2=true若tl=t2=NILf tl,t2=false若tl,t2中只有一个为NILf tl,t2=f tl\Ichild,t2\Ichild ANDf tl\rchild,t2\rchild若tl,t2均不为NIL2求二叉树的叶子结点数fbt=0当bt=nilfbt=l当bt左右子树均为空f bt=f bt.Ichild+f bt二rchild否则3求二叉树所有叶子结点的最大枝长0若bt^・Ichild=nil且bt二rchild=nilmaxibt二Ichild+1若bt二rchild=nilmax=maxibt^.rchild+1若bt\Ichild=nilmax maxi bt\rchild+1,maxibt\rchild+1否则
3.打印二叉树中结点x假定存在的所有祖先结点【分析】在二叉树的递归遍历等算法中，只有后序遍历才是最后访问根结点，因此有可能保存从根结点到待查结点的踪迹，这时可用栈，存放从根结点到x结点路径中的各祖先结点【算法】PROC printansctrbt:bitreptr;x:datatype;｛bt是bitreptr型的二叉树，x是待查找数据值，本算法输出X结点的各祖先结点S是工作栈，存放X的祖先结点查到X后，依次输出S中数据即可｝initstacks;p:=bt;pushs,p;WHILE NOTempty sDO[WHILE NOTempty sAND p\dataOx DO[pushs,p;p:=p\ichild]IF p.data=xTHEN WHILE NOT emptysDO[p:=pops;writep.data]ELSE｛需要到右分枝去查x结点｝[q:=nil;rend:二true;｛rend是为了在右分枝不空时就退出循环｝WHILE NOTempty sAND rendDO[p:=pops;q二p｛右分枝为空时退栈｝IF p\r-q THEN pushs,p;p:=p^.rchild;rend:=false]ELSE[ENDP；｛printansctr第七章图
一、内容提要图的存储结构
1.
1.图的定义，概念、术语及根本操作最短路经图的遍历图的应用连通分量，最小生成树，拓扑排序，关键路经,
二、学习重点图是应用最广泛的一种数据结构，本章是这门课程的重点11根本概念中，连通分量，生成树，邻接点是重点22图是复杂的数据结构，也有顺序和链式两种存储结构数组表示法重点是邻接距阵和邻接表这两种存储结构对有向图和无向图均适用十字链表是有向图的另一种表示，将有向图的邻接表和逆邻接表合一邻接多重表是无向图邻接表的改良，将边结点的数量减少一半正好等于边的数量33图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历，手工模拟图的遍历中栈和队列指针状态的变化44在强连通图中，主过程一次调用深宽度优先遍历过程dfs/bfs,即可遍历完全部顶点，故可以用此方法求出连通分量的个数，并能画出遍历中形成的深宽度优先生成树55连通图的最小生成树不是唯一的,但最小生成树边上的权值之和是唯一的应熟练掌握prim和kruscal算法，特别是手工分步模拟生成树的生成过程66拓扑排序是在有向图上对入度先后为零的顶点的一种排序，结果不唯一关键路经是在拓扑有序的前提下求出来的，从源点到汇点的最长路径应能掌握这两种算法，并熟练手工模拟理解“减少关键活动时间能缩短工期〃，是指该活动为所有关键路径所共有，且减少到尚未改变关键路经的前提下才有效77从单源点到其他顶点，以及各个顶点间的最短路经问题，掌握算法，并熟练手工模拟
1、用邻接多重表实现图的各种运算
三、例题解析【分析】在邻接多重表中，每条边用一个结点表示，不象在邻接表中那样用两条边来表示这在图的操作中，要比其他的存储结构要复杂的多PROC crt_graphvar g:adjmulist;｛g为教材中已定义的adjmulist类型变量，本算法建立有n个结点e条边的图的存储结构｝FOR I:=1TO n DO[read g[i].data;g[i].firstedge:=nil]｛建立顶点向量，各顶点所指向的第一条边指针为nil｝FOR r:=1TO eDO[read vi,vj;｛读两结点｝i:=loc_vertexg,vi;j:=loc_vertexg,vjnewp;p\ivex:=i;p\jvex:=j;p\ilink:=g[i].firstedge;g[i].firstedeg:=p｛将边vi,vj分别插入顶点vi,vj的边结点链表中｝ENDP;｛crt graph｝【讨论】在本算法中，设输入的边不含有重复边，即输入vi,vj后，即不应再输入vi,vj,也不应再输入vj,vio否则，本算法应添加查询功能即下面search过程查询成功时该边不再参加到图的存储结构中FUNC searchg:adjmulist;I,j:
1..vtxnum:edgeptr;｛本算法在图g中查询顶点vi,vj间的边结点是否已建立如是，则返回该边结点的指针，否则返回nilP*=g[i].firstedge;found:二falseWHILE pONILAND NOT found DOIF p\ivex=i｛结点中ivel,jvex域均可能为i｝THEN IF p\jvex=jTHEN found:=trueELSE p:=p^.ilink｛顺ilink下找｝ELSE IFp\ivex=j｛p二jvex二i｝THEN found:=trueELSE p:=p\jlink｛顺只ink下找｝;ENDF;｛search｝PROC insert_edge VAR g:adjmulist;vi,vj:vtxptr;｛本算法在邻接多重表中插入边vi,vji:=loc_vertexg,vi;j:=loc_vertexg,vj;fp:=searchg,i,j;IF fp:=nil｛若边vi,vj在图中不存在｝THEN[newp;p^.ivex:=i;p\jvex:=j;p\ilink:=g[i].firstedge;g[i].firstedge:=p;p\jlink:=g[j].firstedge;g[j].firstedge:=p;]ENDP;｛insert｝PROC insertvertexVAR g:adjmulist;v:vtxptr;｛本算法在邻接多重表中插入顶点V设顶点向量足够大，插入一顶点也就是加一个向量元素，设m是已有顶点数，贝｝g[m+l].data:=v;g[m+l].firstedge:=nil;ENDP;｛insertvertex｝PROC deleteedgeVAR g:adjmulist;vi,vj:vtxptr;｛本算法注邻接多重表g中删除边vi,vji:=loc vertexg,vi;j:=loc_vertexg,vj;fp:=searchg,i,j;IF fpnilTHEN[p:=g[i].firstedge;q:二nil;｛修改i的链表边结点vi,vj的前驱的指针｝WHILE pfp DO【q二P；IFp\ivex=iTHEN p:=p\ilinkELSE p:二p\jlink]IFq=nil｛删除的边是顶点vi的第一边结点｝THEN IFp\ivex二iTHEN g[i].firstedge:=p\ilinkELSE g[i].firstedge:=p\jlinkELSE｛所删除的不是vi的第一边结点｝IF q\ivex=iTHEN IFp\ivex=i THENq\ilink:=p\ilinkELSE q\ilink:=p\jlinkELSE IFp\ivex=i THENq\jlink:=p\ilinkELSE q\jlink:二p二jlink;P=g[j].firstedge;q:=nil;｛修改j的链表边结点vi,vj的前驱的指针｝｛从vj的边结点链表中找到vi,vj边，修改前驱指针，算法同上，故略｝dispose fp;
2、编写对图的深度优先非递归遍历算法【分析】使用栈，调用过程的算法同教材，对被调用过程编写如下PROC dfsg:adjlist;vO:vtxptr;｛本算法从顶点vO开始在图g中进行深度优先遍历算法中visited是在主过程中已赋值false的辅助数组，s是元素为边弧结点的工作栈｝initstack s;write vO;visited[vO]:=true;P-g[v].firstarc;WHILE pOnil ANDNOTempty sDO[WHILE pOnilDOIF visited[p.adjvex]THENp:=p.nextarcELSE[writep.adjvex;pushs,p;visited[p.adjvex]:=true;p:=g[p.adjvex].fistarc;IF NOTempty sTHEN[p:=pops;p:=p\nextarcENDP;｛dfs｝第八章动态存储管理、内容提要
1.
1.动态存储管理指的是在用户需要时给分配内存，而在用户结束使用时，系统要收回用户所占空间
2.
2.可利用空间表的三种结构形式结点固定大小；分几种规格；任意大小
3.
3.可利用空间表的两种组织形式目录表，链表
4.
4.可利用空间表的分配方式首次拟合法，最正确拟合法，最差拟合法
5.
5.可利用空间表的分配和回收的两种根本实现方法边界标识法，伙伴系统
6.
6.无用单元回收和紧缩存储的概念
二、学习重点
1、概念可利用空间表及分配方式，紧缩存储，伙伴系统，等
2、边界表示法的分配及回收算法
3、伙伴系统的分配及回收算法
三、例题解析设有大小为512字节的存储，有6个用户申请大小分别为23,45,52,100,11和19字节的存储空间，然后再顺序释放大小为45,52和11的占用空间假设以伙伴系统实现动态存储管理
1.
1.画出可利用空间表的初始化状态
2.
2.画出为6个用户分配的存储空间后可利用空间表的状态，以及每个用户得到的存储块的起始地址
3.
3.画出在3个占用块回收后可利用空间表的状态【解答】
1.
1.因为512二29,所以初始化为2,123=25=32,所以要分配25字节一块占用块首址0因无25空闲块，故原先2块分裂为
28、、2\2%2,各一块，首址依次为256,128,64,320—31给了申请23的用户245=26=64,故将26空闲块64—127给了该用户，其首址为643因52〈二26二64,这时已无2‘大小空闲块，故将27块分裂，一块大小给了用户128-129,起始地址128,其伙伴起始地址192192—255挂到2‘空闲块链表中4100〈二2,=128,因无2,空闲块，2块产生分裂，其中首址256256—383的一半分给用户，其伙伴首址384挂到2,空闲块链表中511〈二16二2，因无2空闲块，产生分裂，一半首址3232-47分给用户，其伙伴首址48挂到2,大小的空闲块链块表619〈=32=
2、因无空闲块，2‘块分裂，一半首址192192—223分给用户，其伙伴首址224挂到2$空闲块链表中总之，6个用户占用块首址依次为0,64,128,256,32和192,这时可利用空间表的状态为2°2122人0423rv212526八272829z\
3、回收1145=26=64,其首址为64,因64MOD26+1=26,所以其伙伴地址为64-64二0不空其伙伴占用，故仅将此结点挂到空闲块链表中2252=2=64,其首址为128,因128MOD26+1=0,所以，伙伴地址二128+64=192占用，故仅将此块挂到2‘空闲块链表中3311=24=16,首址32因32MOD21+1=0,伙伴地址32+2=48空闲，故合并成块因32MOD25旬二2,新伙伴地址为32-32二0不空，故将2,一块挂于的空闲块链表中2°ZV2/V22ZV2321ZV25第九章查找2627
一、内容提要28八29/V
1、
1、本章介绍的查找表是称为集合的数据结构是元素间约束力最差的数据结构元素间的关总之，三块释放后空闲表状态如下:系是元素仅共在同一个集合中
2、查找表的操作查找，检索，插入，删除，成员关系判断
3、静态查找表顺序表，有序表，静态树表，索引顺序表
4、动态查找表二叉排序树，平衡二叉树，B-树，B+树，键树
5、哈希表
二、学习重点
1、查找表是称为集合的数据结构因元素间关系非常松散，其操作需借助其它数据结构来实现本章列举了三种方法静态查找表，动态查找表，哈希表实现查找表的运算
2、顺序表因引设置了监视哨使查找效率大大提高有序表的平均查找长度不超过树的深度，其判定树是唯一的索引顺序查找综合了上述二者的优点，既能较快速的查找，又能适应动态变化的要求
3、二叉排序树的形态取决于元素的输入顺序按中序遍历可得到结点的有序序列，应熟练掌握其建立、查找，插入和删除算法
4、
4、最正确二叉排序树是平均查找长度最短的二叉排序树，平衡二叉树是介于最正确和一般间的折中，应熟练掌握手工绘制平衡二叉树
5、
5、键树中每个结点是关键字的一个字符，该树是有序树同层兄弟间从左到右递增，最小是结束符号$
6、
6、哈希表是查找表集合的又一表示方法，根据选定的哈希函数和处理冲突的方法，将关键字映像到哈希表中冲突是不可防止的
7、
7、哈希表中关键字的查找只能用哈希函数来计算，不能顺序、折半查找元素删除也只能作标记，不能物理的删除
三、例题解析
1.设二叉排序树中元素均为整数，试编写算法从大到小输出各元素值【分析】中序遍历二叉排序树可得元素的有升序序列【算法】PROC bstoutput bst:bitreptr；{bst是二叉排序树根结点指针，本算法从大到小输出二叉排序树的各结点的值}IF bstONILTHEN[bstoutput bst t.rchild;write bstt.data:5；bstoutputbstt-Ichild;ENDP；{bstoutput}【讨论】课本中讨论了二叉树的三种递归遍历算法，另三种并非没用此题就是先中序遍历右子树，再访问根结点，最后中序遍历左子树此题另一种解法是在中序遍历二叉排序树，访问根结点时将结点值进栈保存，遍历结束后依次弹出栈中元素，直至栈空，所得结果亦符合要求，但多用了一个栈，不如这里所采用的算法简单
2.编写在二叉排序树上插入结点s的算法【分析】二叉排序树上插入结点都是在叶子上插入【算法】PROC insertVAR bst:bitreptr;；s:bitreptr;{本算法在二叉排序树bst上插入结点s}IF bst=NILTHEN bst:=sELSE IFbst.datas t.dataTHEN insertbst f.Ichild,sELSE insertbstt-rchild,s;ENDP;{insert【讨论】这是最简洁的递归算法
3.编写在索引顺序表中查找数据k的算法【分析】索引顺序查找又称分块查找，设表中共有n个记录，每块中有s个记录，故共有b二r n/s-I上取整块现设一索引表，其结构如下TYPEidxtbl=RECORDkey:keytype;low,high:integer;END;Index=ARRAY[L.b]OF idxtbl;记录中三个域key为索引所指块中最大关键字，low和high指该块中最低下标值和最高低标值先折半查找索引表，再顺序在索引所指的某块内查找【算法】FUNC indxblkr:seqlisttp:idx:index;k:keytype:integer;｛本算法在索引顺序表r中，查找其关键字值为待查元素值k的元素Idx是索引表｝low:二l;high:二b；｛在索引表中折半查找其值二k的最小元素｝found:=false;WHIEL low〈二high ANDNOTfoundDO[mid=low+high DIV2;CASEr[mid].key=klow:二mid;found:=true;r[mid].keyk:high:=mid-l;r[mid].keyk:low:=mid+l;ENDC；｛若查找失败low值即为所求｝IF lowbTHEN low:=b;｛取最后一块｝l:=idx[low].low;｛取待查块在r中的最低和最高低标｝h:=idxlow,high;i:=1;WHILE r[i].keyk ANDi=h DOi:=i+l;IF r[i].key=kTHEN idxblk:=iELSE idxblk:=o;ENDF；｛indxblk
4.一个含有100个记录的表，关键字是中国人名的拼音请给出此表的一个哈希表设计方案要求在等概率情况下查找成功的平均查找长度不超过3o【分析】1根据平均查找长度不超过3,确定装填因子；snl心1/21+1/1-｛使用线性探测再散列解决冲突｝因snl=3,所以a至少为
0.8,取a=
0.
8.2根据a确定表长由Q二表中添入的记录数/哈希表的长度所以哈希表的长度=100/a=125取表长二150；3选取哈希函数Hkey二key MOD1494key的选取方法设大写字母在表中用I..26表示，小写字母用27—52表示每个人的姓名取四个字母两字姓名取首尾两个字母，三字姓名取各字拼音第一个字母，中间字取首尾两个拼音字母将前两个拼音字母的序号并起来，后两个也并起来，然后相加形成关键字要求姓名的第一个拼音字母要大写，如姓名‘王丽明‘拼音为‘Wang liming,取出四个拼音字母为此1,i,m,个字母序号依次为23383539,组成关键字为2338+3539=5877,该姓名的哈希地址为5877MOD149=66o55用线性探测再散列处理冲突1数据结构研究的内容2根本概念数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型3算法的定义及五个特征4算法描述类PASCAL语言5算法设计要求6算法分析
二、学习重点1数据结构的“三要素〃逻辑结构、物理存储结构及在这种结构上所定义的操作运算2抽象数据类型的定义、表示和实现方法3类PASCAL书写标准，过程函数中值参和变参的差异，过程调用规则4用计算语句频度来估算算法的时间复杂度
三、例题解析1写出以下各语句执行次数左边括号内数字为语句序号1FOR i:=l TOn DO2FOR j:=l ton DO3[c[I,j]:=0;4FOR k:=l TOn DO5c[I,j]:=c[I,j]+a[I,k]*b[k,j][答案]:各语句执行次数频度分别为n+1,nn+l,n2,n2n+l,n3[分析]:最容易发生的错误，是将第一个语句的执行次数答成n2编写最优算法，从小到大依次输出顺序读入的三个整数PROC asscending;｛本算法对读入的三个整数进行排序，然后按从小到大输出｝｛算法中核心语句如下｝read a,b,c;IF abTHEN[t:=a;a:=b;b:=t];｛a,b按正序排序｝IF bcTHEN[t:=c;c:=b;｛c为最大｝IF atTHEN b:二t｛b为中间值｝ELSE[b:=a;a:=t]｛a,b正序｝WRITELNa:4,b:4,c:4;ENDP;｛assending[分析]:此题正确算法有多种，但上面是最优算法最好情况下只经过两次比较且无数据移动，而在最坏情况下，也只是经过三次比较，七个赋值语句就完成了排序在本课程教学中，强调“好〃的算法，不仅仅是结果正确，而且是最优的算法这与PASCAL语言教学中的要求有很大不同算法是供人来阅读的，必须牢记这一点算法中语句的书写格式采用缩进规则，保存字用大写,其余标识符小写，提高了算法的易读性第二章线性表
一、内容提要
1.线性表是元素间约束力最强的一类数据结构
2.线性表的逻辑结构定义，对线性表定义的操作
3.线性表的存储结构顺序存储结构和链式存储结构
4.线性表的操作在两种存储结构中的实现
5.一元多项式的线性表表示方法，及高次（稀疏）多项式的抽象数据类型定义、表示和加法的实现
二、学习重点
1.
1.线性表的逻辑结构，指线性表的数据元素间存在着线性关系在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的
2.
2.顺序存储结构用向量一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构
3.
3.尽管“只要知道某结点的指针就可以存取该元素〃，但因链表的存取都需要从头指针开始，顺链而行,故链表不属于随机存取结构
4.
4.链表是本章学习的重点和难点要理解头结点，首元结点和元素结点的差异理解头结点是为了在插入、删除等操作时，为了算法的统一而设立的若无头结点，则在第一元素前插入元素或删除第一元素时,链表的头指针总在变化掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作
5.
5.链表操作中应注意不要使链意外“断开〃因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针
6.
6.从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点
7.
7.静态链表是又一重点和难点应和链表进行比较、理解例如，在有头结点的链表情况下，第一元委是p:=la\
三、例题解析next,而在静态链表中则i:=sa[O].next；相对p:=p\next,有i:=sa[i].next来找到第i个元素的后继
1.设线性表以顺序存储结构存于aL.n中，试编写算法将该线性表就地逆置【分析】向量逆置有几种方法，如逆向读入到另一数组中，在正向对应赋值，即FOR i:=n DOWNTO1DO b[n-i+l]:=a[i];FOR i:=lT0nDO a[i]:=b[i];这里要求“就地逆置〃，即不能另用一数组空间【算法】PROC invertVAR a:arr;n:integer;｛a是存储线性表的一维数组，有n个元素，本算法将a逆置｝FOR i:=lT0n DIV2DOa[i]^a[n-i+l];endp;【讨论】将n个元素的一维数组逆置，为什么循环控制变量用n div2,而不用n
2.编写在单链表上进行排序的算法【分析】这里使用插入排序链表中插入元素要知道待插入元素位置的前驱，以pre表示之结束的条件是链表为空【算法】PROC insertsortVAR la:linklist;｛la是带头结点的单链表的指针，本算法将链表中元素正序排序算法的根本思想是先假定第一个元素有序，然后从第二个元素开始，依次插入到有序的表中，直到全部元素插入完为止｝p=la二next二next;｛假定链表非空，即至少有一个结点｝la\next二next:二nil;｛设有序链表中当前只有一个结点｝found:=false;WHILE pOnilANDNOTfoundDO[s:=p\next;｛记住下一个结点｝pre:二la;q:=la\next;found:=false;WHILE qOnil ANDNOTfound DOIFq.datap.data THEN[pre:=q;q:=q.next]ELSE found:=true;p\next:=q;pre\next:=p;｛p结点插入｝P=s;｛取下一个结点｝ENDP;｛insertsort【讨论】算法中found为一布尔变量，为的是在链表到尾前，如找到p的插入位置，即可退出WHILE循环这里循环条件未写成pOnilANDq\datap\data因为若q=nil,则再引用鼠.data是无意义的请记住这种退出循环，引入布尔变量的作法
3.设两个非递减有序的线性表各有m和n个元素n0,n0，分别存于一维数组a和b中，且a的存储空间足够大试编写算法将两线性表合并成一线性表，结果仍是非递减有序，要求算法的时间复杂度是om+no【分析】两个有序线性表合并成一个有序表，教材中已有讨论，算法非常简单本算法要求复杂度为0m+n,这是着重点题目叙述中有“a的空间足够大〃，暗示出若将m+n个元素合并到a中,不会溢出为使数据移动次数最少，应先将两表中最大元素置于m+n的位置上，然后相应指针减1,再比较之，直到两表中有一个指针减到3则结束，否则，将b中剩余元素传到a中相应位置即可【算法】PROC unionVARa:seqlisttpjb:seqlisttp;｛a,b是两个非递减有序表，顺序存储结构存储，各有m和n个元素，本算法将两表合并到a中，仍为有序表，算法时间复杂度为0m+n｝i:=m;j:=n;k:=m+n;｛i,j,k分别为表a,b和结果表的指针｝WHILE i0ANDj0DOIF a[i]b[j]THEN[a[k]:=a[i];i:=i-l;k:=k-l]ELSE[a[k]:=b[j];j:=j-l;k:=k-l];WHILE j0DO[a[k]:=b[j];k:=k-l];｛若b表中尚有元素，则传至a中相应位置｝【讨论】本算法至多比较m+n次，往a中赋值m+n次最好情况是比较n次，往a中赋值n次，该种情况是b中最小元素不小于a中最大元素问题为什么在退出第一个WHILE循环后，不讨论即没有WHILE i0的情况？第三章栈和队列
一、内容提要
1.
1.从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型
2.
2.栈的定义及操作栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端
3.
3.栈的顺序和链式存储结构，及在这两种结构下实现栈的操作
4.
4.栈的应用表达式求值，递归过程及消除递归
5.
5.队列的定义及操作，队列的删除在一端（尾），而插入则在队列的另一端（头）因此在两种存储结构中，都需要队头和队尾两个指针
6.
6.链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法
二、学习重点
1.栈和队列操作在两种存储结构下的实现
2.中缀表达式转成前缀、后缀表达式并求值
3.用递归解决的问题定义是递归的，数据结构是递归的，及问题的解法是递归的，掌握典型问题的算法
4.
4.链队列删除时为空的处理（令队尾指针指向队头）特别是仅设尾指针的循环链队列的各种操作的实现
5.
5.循环队列队空定义为队头指针等于队尾指针，队满则可用一个单元（教材中所示）及设标记方法（下面例题）这里特别注意取模运算
6.
6.在后续章节中要注意栈和队列的应用，如串中心对称的判定，二叉树遍历的递归和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的宽度优先遍历等则用到队列
三、例题解析
1.
1.两栈共享一向量空间，编写入栈和出栈算法TYPETwoWayStack=RECORD｛双栈共享一向量空间｝elem:ARRAY[
1..m]OF elemtype;top:ARRAY[
0..1]OF
0..m+1;｛两个栈顶指针｝END;PROC inistackVARtws:TwoWayStack;｛初始化｝｛初始化双向栈tws为空｝tws.top
[0]:=0;｛左端栈指针｝tws.top[l]:=m+l;｛右端栈指针｝ENDP;｛inistack｝PROC PUSHVARtws:TwoWayStack;i:
0..1;x:elemtype;VAR ofw:boolean;｛若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为falseIF tws.top
[1]-tws.top
[0]1THEN｛栈未满｝CASE iOF0:tws.top
[0]:=tws・top
[0]+l;tws.elem[tws.top
[0]]:=x;ofw:=true1:tws.top[l]:=tws.top[l]~l;tws.elem[tws.top[l]]:二x;ofw:二true ENDCELSEofw:二false;栈满ENDP;｛push｝PROC POPVARtws:TwoWayStack;i:
0..1;VAR x:elemtype;VAR underflow:boolean;｛若双向栈tws非空，则将i端退栈,栈空时underflow为trueCASE iOF0:IF tws.top
[0]=0｛栈空｝THEN[underflow:=true;returnunderflow]ELSE[tws.top
[0]:=tws.top
[0]-1;x:=tws.elem[tws.top
[0]+l];｛弹出元素｝
1.IF tws.top[l]=m+l｛栈空｝THEN[underflow:=true;returnunderflow]ELSE[tws.top[l]:=tws.top[l]+l;x:=tws.elem[tws.top[l]-l];｛弹出元素｝ENDCENDP;｛pop｝【讨论】上面算法中用0和1代表两端，且按操作在哪端来分两种情况进行讨论，逻辑清楚也可用一个公式表示插入进栈和删除退栈指针位置例如,插入时top=top+1-2*i,删除时top=top-l+2*i表达简洁，但不如上面清楚易读
2.
2.将中缀表达式转换成后缀表达式，并进行表达式求值PROC trnssufixVARexp2:string;s:stack;expl:string;｛本算法将中缀表达式expl转为后缀表达式exp2,使用运算符栈s｝｛算法根本思想是依次从中缀表达式读入字符w若w是变量，直接送入结果表达式，若w是运算符，则与栈顶运算符比较，若级别高，则进栈；若低，则栈顶元素退栈，并送入结果表达式，再取栈顶运算符比较，重复以上步骤；若w=，则栈元素依次退栈，并送入结果表达式，直至退栈｝initstringexp2;initstacks;pushs,#;+\一」*1/W7｛操作符集合｝OP=1readw;WHILE NOTw=，#，AND GETTOPOPTR=#9DOIF NOTw INop THEN[insertexp2,w;readw];ELSE CASEprecedeGETTOPs,w OF:[PUSHS,w;read w];二IFw=THEN｛遇右括号后，运算符退栈并送结果表达式，直至左括号｝[x:=POP S;WHILE x〈〉DO[insertexp2,x;x:=POPS]read w];:[b:=POPS;insert exp2,b];END;ENDP;PROC sufixevalVARexp2:string;s:stack;VAR sn:stack;｛本算法对后缀表达式exp2求值，使用运算符栈s和操作数栈sn｝｛算法根本思想是逐字符从左到右顺序读入后缀表达式若读入的字符w是数，则直接压入栈sn中；若w是运算符，则与栈顶运算符比较，若级别高，则进栈；否则，从运算数栈弹出两个操作数，和从运算符栈弹出的一个运算符进行相应运算，结果存入操作数栈中w运算符再与栈顶运算符比较优先级直至后缀表达式处理完毕这时sn栈中只剩一个数，即表达式结果｝initstringsn;initstacks;=「+,T;｛操作符集合｝OPread w;｛从左到右顺序读入后缀表达式｝WHILENOTempty exp2DOIF NOTw INop THEN[PUSHsn,w;readw];ELSE CASEprecedeGETTOPs,w OF:[PUSH s,w;read w];[a:=P0Psn;b:=P0Psn;theta:=POPs;PUSH sn,operatea thetab];END;ENDP;｛sufixeval
3、用设标记来判定循环队列满，编写入队和出队的算法｛本算法用设标记tag的方法，解决循环队列队满和队列空的判断问题,tag-0表示队列空，tag-1表示队列不空｝TYPEcyclicqueue=RECORD｛设头尾指针和标志域的循环队列｝elem:=ARRAY[O..m-1]OF elemtype;rear,front:
0..m-1tag:
0..1;｛0为空，1为非空｝END;PROC INITQUEDEVARcq:cyclicqueue;｛初始化｝cq.tag:=0;cq.tear:=cq.front:=0;ENDP;PROC ENQUEUEVARcq:cyclicqueue;x:elemtype;｛cq是由头尾指针和标志域的循环队列，本算法是入队操作，若队列不满，｝｛则将x插入到队尾｝IF cq.tag=lANDcq.front=cq.rearTHEN returnfalse｛队满｝ELSE[cq.rear:=cq.rear+1MOD m;cq.elemcq.rear:=r;IF cq.tag=0THENcq.tag:=l｛由空变不空标记｝。
个人认证
优秀文档
获得点赞 0
