数据结构对象的基本概念

PAGEPAGE73目录TOC\o"1-3"\u目录 1第一章绪论 3一、内容提要 3二、学习重点 3三、例题解析 3第二章

线性性表 5一、内容提要要 5二、学习重点点 5三、例题解析 5第三章栈和队队列 8一、内容提要 8二、学习重点 8三、例题解析 8第四章

串 12一、内容提要 12二、学习重点 12三、例题解析 12第五章数组和和广义表 14一、内容提要要 14二、学习重点 14三、例题解析 14第六章树和和二叉树 16一、内容提要要 16二、学习重点 16三、例题及分析析 16第七章图 19一、内容提要 19二、学习重点 19三、例题解析 20第八章动态态存储管理 22一、内容提要 22二、学习重点 22三、例题解析 22第九章查找找 24一、

内容提要要 24二、学习重点 24三、例题解析 25第十章

内内部排序 27一、内容提要 27二、学习要点 27二、例题解析 27第十一章外外部排序 30一、内容提要 30二、学习要点 30三、习题解析 30第十二章文件件 32一、内容提要 32二、学习重点 32第一章绪绪论一、内容提要1数据结构研研究的内容。2基本概念：：数据、数据据元素、数据据对象、数据据结构、数据据类型、抽象象数据类型、多多形数据类型型。3算法的定义义及五个特征征。4算法描述：：类PASCCAL语言。5算法设计要要求。6算法分析。

二、学习重点1数据结构的的“三要素”：逻辑结构构、物理（存存储）结构及及在这种结构构上所定义的的操作（运算算）。2抽象数据类类型的定义、表表示和实现方方法。3类PASCCAL书写规规范，过程（函函数）中值参参和变参的差差别，过程调调用规则。4用计算语句句频度来估算算算法的时间间复杂度。

三、例题解析1写出以下各各语句执行次次数（左边括括号内数字为为语句序号）(1)FOORi::=1TOOnDO(2)FORRj::=1toonDO(3)[c[[I,j]:=0;;(4)FORRk::=1TOnnDOO(5)

c[I,jj]:=c[[I,j]++a[I,kk]*b[kk,j]][答案]：各语语句执行次数数（频度）分分别为n+11，n(n+11),n22,n22(n+1)),n3[分析]：最容容易发生的错错误，是将第第一个语句的的执行次数答答成n。

2编写最优算算法，从小到到大依次输出出顺序读入的的三个整数PROCaasscennding;;{本算法对读入入的三个整数数进行排序，然然后按从小到到大输出}{算法中核心语语句如下}rread(aa,b,c));IIFa>bbTHHEN[[t:=a;;a:=bb;b:==t];{{a,b按正正序排序}IIFb>ccTHHEN[[t:=c;;c:=bb;{c为为最大}IFaa<tTTHENb:=t{{b为中间值值}ELLSE[[b:=a;;a:=tt]{a,,b正序}WRITEELN(a::4,b:44,c:4));ENDP;{asseendingg}

[分析]：本题题正确算法有有多种，但上上面是最优算算法：最好情情况下只经过过两次比较且且无数据移动动，而在最坏情况下，也只只是经过三次次比较，七个个赋值语句就就完成了排序序。在本课程教学中中，强调“好”的算法,不仅仅是是结果正确,,而且是是最优的算法法。这与PAASCAL语语言教学中的的要求有很大大不同。算法是供供人来阅读的的，必须牢记记这一点。算算法中语句的的书写格式采采用缩进规则则，保留字用用大写，其余标识符小小写，提高了了算法的易读读性。

第二章

线性性表

一、内容提要要1．线性表是元元素间约束力力最强的一类类数据结构。2．线性表的的逻辑结构定定义，对线性性表定义的操操作。3．线性表的存存储结构：顺顺序存储结构构和链式存储储结构。4．线性表的操操作在两种存存储结构中的的实现。5．一元多项式式的线性表表表示方法，及及高次（稀疏疏）多项式的的抽象数据类类型定义、表表示和加法的的实现。

二、学习重点点1．

线性表表的逻辑结构构，指线性表表的数据元素素间存在着线线性关系。在在顺序存储结结构中，元素素存储的先后后位置反映出出这种线性关关系，而在链链式存储结构构中，是靠指指针来反映这这种关系的。2．

顺序存存储结构用向向量（一维数数组）表示，给给定下标，可可以存取相应应元素，属于于随机存取的的存储结构。3．

尽管“只要知道某某结点的指针针就可以存取取该元素”，但因链表表的存取都需需要从头指针针开始，顺链链而行，故链链表不属于随随机存取结构构。4．

链表是是本章学习的的重点和难点点。要理解头头结点，首元元结点和元素素结点的差别别。理解头结结点是为了在在插入、删除除等操作时，为为了算法的统统一而设立的的（若无头结结点，则在第第一元素前插插入元素或删删除第一元素素时，链表的的头指针总在在变化）。掌掌握通过画出出结点图来进进行链表的生生成、插入、删删除、遍历等等操作。5．

链表操操作中应注意意不要使链意意外“断开”。因此，若若在某结点前前插入一个元元素，或删除除某元素，必必须知道该元元素的前驱结结点的指针。6．

从时间间和空间复杂杂度的角度综综合比较线性性表在顺序和和链式两种存存储结构下的的特点。7．

静态链链表是又一重重点和难点。应应和链表进行行比较、理解解。例如，在在有头结点的的链表情况下下，第一元素素是p:=lla^.neext，而在在静态链表中中则i:=ssa[0]..next；；相对p:==p^.neext,有i:=saa[i].nnext来找找到第i个元素的后后继。

三、例题解析

１．设线性表以以顺序存储结结构存于a((1..n))中，试编写写算法将该线线性表就地逆逆置。【分析】向量逆置有有几种方法，如如逆向读入到到另一数组中中，在正向对对应赋值，即即：FORi:==nDOWWNTO11DOb[n-ii+1]:==a[i];;FORRi:=11TOnDOa[[i]:=bb[i];这里要求“就地地逆置”，即不能另另用一数组空空间。【算法】PRROCiinvertt(VARa:arrr;n:iintegeer);{a是存储线线性表的一维维数组，有nn个元素，本本算法将a逆置。}FORi:==1TO((nDIIV2))DOaa[i]↔aa[n-i++1];endp;【讨论】将nn个元素的一一维数组逆置置，为什么循循环控制变量量用ndiiv2，而而不用n？

２．编编写在单链表表上进行排序序的算法【分分析】这里里使用插入排排序。链表中中插入元素要要知道待插入入元素位置的的前驱，以pre表示之之。结束的条条件是链表为为空。【算算法】PROCinserrtsortt(VARla:liinklisst);{la是是带头结点的的单链表的指指针，本算法法将链表中元元素正序排序序。算法的基基本思想是先先假定第一个个元素有序，然然后从第二个个元素开始，依依次插入到有有序的表中，直直到全部元素素插入完为止止}p:=lla^.neext^.nnext;{{假定链表非非空，即至少少有一个结点点}la^.nnext^..next::=nil;;{设有序链链表中当前只只有一个结点点}fouund:=ffalse;;WHILEE(p<>>nil)AANDNOOTfouundDOO[s:=pp^.nexxt;{记住住下一个结点点}pree:=la;;q:=lla^.neext;ffound::=falsse;WWHILE((q<>niil)ANDDNOTfounddDOIFq^^.dataa<p^.ddataTTHEN[[pre:==q;q::=q^.nnext]ELSEEfounnd:=trrue;p^.nextt:=q;pre^.neext:=pp;{p结点点插入}p:=s;{取取下一个结点点}]ENDP;{inseertsorrt}【讨论】算法中中foundd为一布尔变变量，为的是是在链表到尾尾前，如找到到p的插入位置，即可退退出WHILLE循环。这这里循环条件件未写成：（p<>niil）AND((q^.daata<p^^.dataa)因为若q=niil，则再再引用q^..data是是无意义的。请请记住这种退退出循环，引引入布尔变量量的作法。3．设设两个非递减减有序的线性性表各有m和n个元素（m>>0,n>00）,分别存于一一维数组a和b中，且a的存储空空间足够大。试试编写算法将将两线性表合合并成一线性性表，结果仍仍是非递减有有序，要求算算法的时间复复杂度是o((m+n)。【分析】两个有序线线性表合并成成一个有序表表，教材中已已有讨论，算算法非常简单单。本算法要要求复杂度为为O(m+nn)，这是着着重点。题目目叙述中有“a的空间足够够大”，暗示出若若将m+n个元素素合并到a中，不会溢溢出。为使数数据移动次数数最少，应先先将两表中最最大元素置于于m+n的位置置上，然后相相应指针减11，再比较之之，直到两表表中有一个指指针减到0，则结束，否否则，将b中剩余元素素传到a中相应位置置即可。【算法】PRROCuunion((VARaa:seqllisttpp;b:seeqlistttp);{a,bb是两个非递递减有序表，顺顺序存储结构构存储，各有有m和n个元素，本本算法将两表表合并到a中，仍为有有序表，算法法时间复杂度度为O(m++n)}i:==m;j::=n;kk:=m+nn;{i,,j,k分别别为表a,bb和结果表的的指针}WHHILE((i>0)AND((j>0)DOIFa[i]>>b[j]THEN[a[k]]:=a[ii];i::=i-1;;k:=kk-1]ELSEE[a[kk]:=b[[j];jj:=j-11;k:==k-1];;WHIILE(jj>0)DDO[a[[k]:=bb[j];j:=j--1;k::=k-1]];{若b表中尚有元元素，则传至至a中相应位置置}【讨论】本算法至多比较m+n次，往a中赋值m+n次。最好情况是比较n次，往a中赋值n次，该种情况是b中最小元素不小于a中最大元素。问问题：为什么么在退出第一一个WHILLE循环后，不不讨论（即没没有）WHIILEi>>0的情况？？

第三章栈和和队列

一、内容提提要

1．从数据结构构角度讲，栈栈和队列也是是线性表，其其操作是线性性表操作的子子集，属操作作受限的线性性表。但从数数据类型的角角度看，它们们是和线性表表大不相同的的重要抽象数数据类型。2．栈的定义及及操作。栈是是只准在一端端进行插入和和删除操作的的线性表，该该端称为栈的的顶端。3．栈的顺序和和链式存储结结构，及在这这两种结构下下实现栈的操操作。4．栈的应用：：表达式求值值，递归过程程及消除递归归。5．队列的定义义及操作，队队列的删除在在一端（尾），而而插入则在队队列的另一端端（头）。因因此在两种存存储结构中，都都需要队头和和队尾两个指指针。6．链队列空的的条件是首尾尾指针相等，而而循环队列满满的条件的判判定，则有队队尾加1等于队头和设标记两两种方法。

二、学习重重点

1．栈栈和队列操作作在两种存储储结构下的实实现。2．中中缀表达式转转成前缀、后缀表达式式并求值。3．用递归解决决的问题：定定义是递归的的，数据结构构是递归的，及及问题的解法法是递归的，掌握典型型问题的算法法。4．

链队列列删除时为空空的处理（令令队尾指针指指向队头）。特特别是仅设尾尾指针的循环环链队列的各种种操作的实现现。5．

循环队队列队空定义义为队头指针针等于队尾指指针，队满则则可用一个单单元（教材中中所示）及设标记办办法（下面例例题）。这里里特别注意取取模运算。6．

在后续续章节中要注注意栈和队列列的应用，如如串中心对称称的判定，二二叉树遍历的的递归和非递归归算法，图的的深度优先遍遍历等都用到到栈，而树的的层次遍历、图的宽度优优先遍历等则用用到队列。

三、例题解析

1．两栈共享一一向量空间，编编写入栈和出出栈算法。TYYPETwoWaayStacck=RECCORD{双栈栈共享一向量量空间}elem::ARRAYY[1..mm]OFelemttype;top:AARRAY[[0..1]]OF00..m+11;{两两个栈顶指针针}ENND;PRROCinisttack(VVARtwws:TwooWaySttack);;{初始始化}{初始化化双向栈twws为空}twws.topp[0]:==0;{左端端栈指针}twws.topp[1]:==m+1;{右端端栈指针}ENDP;{inisstack}}

PROCPPUSH(VVARtwws:TwooWaySttack;ii:0..11;x:eelemtyype;VAARofww:boollean);;{若双向向栈tws不不满,则将xx插入到i端端,成功时oofw为trrue,失败败为falsse}IFF(tws..top[11]-twss.top[[0])<>>1THENN{栈栈未满}CCASEiiOF0::tws.ttop[0]]:=twss.top[[0]+1;;tws.eelem[ttws.toop[0]]]:=x;oofw:=ttrue1::tws.ttop[1]]:=twss.top[[1]-1;;tws.eelem[ttws.toop[1]]]:=x;oofw:=ttrueEENDCELSSEofww:=fallse;(栈满)ENDDP;{{push}}PROCPOOP(VARRtws::TwoWaayStacck;i:00..1;VVARx::elemttype;VVARunnderfllow:boooleann);{若双向栈栈tws非空空,则将i端端退栈,栈空空时undeerfloww为truee}CAASEiOF0:IFtws.ttop[0]]=0{栈空}THENN[undeerfloww:=truue;retturn(uunderfflow)]]ELSEE[twss.top[[0]:=ttws.toop[0]--1;x:==tws.eelem[ttws.toop[0]++1];{弹出元素素}];1:IFtws.ttop[1]]=m+1{栈栈空}THENN[undeerfloww:=truue;retturn(uunderfflow)]]ELSEE[twss.top[[1]:=ttws.toop[1]++1;x:==tws.eelem[ttws.toop[1]--1];{弹出元素素}];ENDCENDP;{pop}【讨论】上面面算法中用00和1代表两两端，且按操操作在哪端来来分两种情况况进行讨论，逻逻辑清楚。也也可用一个公公式表示插入入（进栈）和和删除（退栈栈）指针位置置。例如，插插入时topp=top++1-2*ii,删除时ttop=toop-1+22*i。表达达简洁，但不不如上面清楚楚易读。

2．将中缀表达达式转换成后后缀表达式，并并进行表达式式求值。PROCtrrnssuffix(VAARexpp2:strring;ss:stacck;exxp1:sttring));｛本算法将中缀缀表达式exxp1转为后后缀表达式eexp2,使使用运算符栈栈s｝｛算法基本思想想是依次从中中缀表达式读读入字符w：：若w是变变量，直接送送入结果表达达式，若w是是运算符，则则与栈顶运算算符比较，若若级别高，则则进栈；若若低，则栈顶顶元素退栈，并并送入结果表表达式，再取取栈顶运算符符比较，重复复以上步骤；；若w＝’)’,则栈元素素依次退栈，并并送入结果表表达式，直至至＇)＇退栈栈｝innitstrring(eexp2);;inittstackk(s);ppush(ss,’#’);opp:=['++','-'','*',,'/',''(','))','#''];{操操作符集合}}reead(w));WHIILENOOT((ww='#'))AND(GETTTOP(OPPTR)=''#'))DOIFFNOT(wINNop)THEN［inssert(eexp2,ww);reead(w))］;ELSEECASEEpreccede(GGETTOPP(s),ww)OF''<':[[PUSHH(S,w));reaad(w)];''=':IIFw=’’)’THENN{遇右括括号后，运算算符退栈并送送结果表达式式，直至左括括号}[xx:=POPP(S);WWHILEx<>’(‘DO[[inserrt(expp2,x);;x:=POOP(S)]]rread(ww)];''>':[[b:=PPOP(S));inssert(eexp2,bb)];END;;ENDP;PROCsuufixevval(VAARexpp2:strring;ss:stacck;VAARsn::stackk);｛本算法对后缀缀表达式exxp2求值，使使用运算符栈栈s和操作数数栈sn｝｛算法基本思想想是逐字符从从左到右顺序序读入后缀表表达式。若读读入的字符ww是数，则直直接压入栈sn中；若若w是运算符符，则与栈顶顶运算符比较较，若级别高高，则进栈；；否则，从运运算数栈弹出出两个操作数数，和从运算算符栈弹出的的一个运算符符进行相应运运算，结果存存入操作数栈栈中。w运算算符再与栈顶顶运算符比较较优先级。直直至后缀表达达式处理完毕毕。这时snn栈中只剩一一个数，即表表达式结果。｝｝innitstrring(ssn);iinitsttack(ss);opp:=['++','-'','*',,'/',''(','))','#''];{操操作符集合}}reead(w));{从左左到右顺序读读入后缀表达达式}WHIILENOOTemppty(exxp2)DDOIFFNOT(wINNop)THEN［PUSSH(sn,,w);rread(ww)］;ELSEECASEEpreccede(GGETTOPP(s),ww)OF''<':[[PUSHH(s,w));reaad(w)];''>':[[a:=PPOP(snn);b:==POP(ssn);ttheta::=POP((s);PUSHH(sn,ooperatte(atthetab))]];END;;ENDP;{suffixevaal}3、用设标记来来判定循环队队列满，编写写入队和出队队的算法。{本算法法用设标记ttag的办法法，解决循环环队列队满和和队列空的判判断问题,ttag=0表表示队列空，ttag=1表表示队列不空空}TYPEEcycliicqueuue=RECCORD{设头尾指针和标标志域的循环环队列}eelem:==ARRAYY[0..mm-1]OOFeleemtypee;rrear,ffront::0..m--1ttag:0...1;｛０为空，１１为非空｝ENDD;PROCIINITQUUEDE(VVARcqq:cycllicqueeue);｛初始化化｝cq.taag:=0;;cq.teear:=ccq.froont:=00;ENDPP;PROCENNQUEUEE(VARcq:cyyclicqqueue;;x:eelemtyype);｛ccq是由头尾尾指针和标志志域的循环队队列，本算法法是入队操作作，若队列不不满，｝｛则则将x插入到到队尾｝IF(ccq.tagg=1)AAND(ccq.froont=cqq.rearr)TTHENrreturnn(falsse){队队满}EELSE[ccq.reaar:=(ccq.reaar+1)MODmm;ccq.eleem(cq..rear)):=r;IIFcq..tag=00THENNcq.ttag:=11{由空空变不空标记记}]ENNDP;PROCDEELQUEUUE(VARRcq:ccycliccqueuee);｛ccq是由头尾尾指针和标志志域的循环队队列，本算法法是出队操作作，若队列非非空｝｛则则将队头元素素出队｝IFccq.tagg=0TTHENrreturnn(falsse){队队空}EELSE[ccq.froont:=((cq.frront+11)MODDm;IIFcq..frontt=cq.rrearTTHENccq.tagg:=0{队空}}]ENNDP;CONSSTm=mmaxlenn;｛队队列长度｝TYPEEccycliccqueuee=RECOORD｛只设尾尾指针和队列列长度的循环环队列｝ellem:AARRAY[[0..m--1]OFFelemmtype;;reear:00..m-11;leength::0..mm;｛队队列长度｝END;;PROCIINIT_qqueue((VARqq:cycllicqueeue);｛初始化化｝q.rrear:==0;q..lengtth:=0;;ENDP;FUNCaddd_queeue(VAARq:ccycliccqueuee;x:ellemtyppe):boooleann;｛q是是由尾指针和和长度标志的的循环队列，本本算法是入队队操作，若队队列不满，｝｝｛将xx插入到队尾尾｝IFqq.lenggth=mTTHENadd_qqueue::=falsse{{队列满}EELSE[[q.reear:=((q.reaar+1)modmm;q.ellem[q..rear]]:=x;q.leength;;=q.leength++1;add__queuee:=truue{入队成成功}]EENDF;FUNCddd_queeue(VAARq:ccycliccqueuee;x;eelemtyype):bbooleaan;｛qq是由尾指针针和长度标志志的循环队列列，本算法是是出队操作，若若队列不空，｝｝｛将将将队头元素素出列，并赋赋给x，队长长度减１｝IFqq.lenggth=0TTHENddd_queeue:=ffalse{{队空}EELSE[[frontt;=(q..rear--q.lenngth+11+m)mmodmx:=q..elem[[frontt]q.lenngth:==q.lenngth-11]]EENDF;

第四章

串一、内容提要

1、

是数据据元素为字符符的线性表，串串的定义及操操作。2、

的基本本操作，编制制算法求串的的其它操作。3、

的存储储结构，因串串是数据元素素为字符的线线性表，所以以存在“结点大小“的问题。静静态和动态（块块链结构，堆堆结构）存储储的优缺点。4、

朴素模模式匹配算法法及改进（KKMP）算法法。

二、学习重点

1、

串的基基本操作，编编写串的其他他操作（如iindex,,replaace等）。2、在串的模式式匹配中，求求匹配串的nnextvaal函数值值。3、尽管朴素的的模式匹配的的时间复杂度度是O(m**n),KKMP算法是是O(m+nn),但在一一般情况下，前前者实际执行行时间近似OO(m+n)),因此至今今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。5、

串操作作在存储结构构下的实现。

三、例题解析

1、利用串的如如下基本运算算creatte(s),,assiggn(s,tt),lenngth(ss),subbstr(ss,starrt,lenn),conncat(ss1,s2)),编写操作作replaace的算法法PROCrreplacce(VARRs:sttring;;t,v::strinng);{本本算法实现串串的置换操作作，用串v置换串s中所有非重重叠的t串。}i::=INDEEX(s,tt);{判判s中有无t}IFFi<>00THENN[CRREATE(tempp,‘’));{t为临时时串变量，存存放部分结果果}m::=LENGGTH(t));n::=LENGGTH(s));WHHILEi<>0DO[ASSSIGN(tempp,CONCCAT(teemp,SUUBSTR((s,1,ii-1),vv));{用v替换t形成部分结结果}ASSSIGN(s,SUUBSTR((s,i++m,nn-i-m++1));{t串以后后形成新s串}n::=n-((i-1)--m;i::=INDEEX(s,tt);]ASSIIGN(ss,CONCCAT(teemp,s)));{将将剩余s连接临时串串t再赋给s}]ENDP;;FUNCindexx(s1:sstringg;t:sstringg):intteger;;{本算法法求串t在串s中的第一次次出现。结果是：若若t在s中，则给出串串t的第一个字字符在串s中的位置，若若不存在，则则返回0}j:==1;m:==lengtth(s);;n:=llengthh(t);eq:=ttrue;WHIILE((j<=m--n+1)ANDeqDOIFeqqual(ssubstrr(s,j,,n),t))THEENeqq:=fallseELSEj:=j++1；IFj<=mm+n-1THENindeex:=jELSEindeex:=0ENDF；{iindex}}【讨论】本题是用给给定的基本操操作，编写其其它操作的算算法。这种类类型题较多，必必须严格按题题的要求来做做，不准选择择具体存储结结构。否则，即即使全对，也也很难得分。2

设目目标为t=’abbcaabbbabcabbaacbaacba’,,模式串p==’abcaabaa’;;(1)计算P的的NEXTVVAL函数值值；(2)不写出算算法，只画出出利用KMPP算法进行模模式匹配时每每一趟的匹配配过程；【解答】（1）P的NNEXTVAAL函数值值如下；j12334567_____________________________________模式pabccabaanextvall(j)001101002(2)abccaabbabcaabaacbaacbaabccab第一趟趟匹配abcc第二趟匹配配a第第三趟匹配abccabaa第四趟匹匹配成功【讨论】为写写NEXTVVAL方便，可可先写出NEEXT函数值值，在由此求求NEXTVVAL.

3、字符串s满足下式，其其中HEADD和TAILL的定义同广广义表类似，如如HEAD((‘XYZ’’)=’X’’,TAILL(‘XYZZ’)=’YYZ’,则S=concaat(heaad(taiil(s))),headd(taill(taill(s)))))=’dcc’求字符串s。

可供选择的答案案是（A）abcdd(B))acbdd(C))acdbb(D))adcbb正确答案是（DD）。第五章数组和广义义表

一、内容提要要

1，

数组的的逻辑结构定定义及存储，2，

稀疏矩矩阵（含特殊殊矩阵）的存存储及运算。3，

广义表表的定以及存存储。4，

广义表表运算的递归归算法。

二、学习重点

1，

数组（主主要是二维）在在以行序为主主的存储中的的地址计算方方法。2，

特殊矩矩阵在压缩存存储时的下标标变换。3，

稀疏矩矩阵的三元组组表存储结构构及矩阵移植植的算法。4，

稀疏矩矩阵的十字链链表存储方法法及十字链表表生成算法。5，

广义表表的HEADD和TAIL运算。6，

给定广广义表画出其其存储结构。7，

从广义义表的递归算算法，掌握如如何编写递归归算法。

三、例题解析

1、字符串二维维数组A[00..8,11..10]]，每个元元素由6个字符组成成，每个字符符占一个存储储单元，则（1）存放A需要多少个字节？（2）A的第88列和第5行共占多少少字节？(3)按行序序存储时，AA[8,5]]和按列存储储时哪个元素素时的地址相相同？【解答】（11）540（2）108（3）A[3,,10]

2、编写算法，将将自然数1n2按蛇形填入入nxnn矩阵中。例如，（11—42）如右图所所示。【分析】本本题要求在NN的方阵中填填人N2个数，关键键是控制下标。设坐标原原点在矩阵的的左上角，且且i是向下增长长，j向右增长。原点点的坐标为（1，1）。【算法】PROCsqrmggc(VARRa:arrr;n:iintegeer);{本算法将自自然数1n2按蛇形填填入NXN矩阵中中,a是二维维数组}i:=1;jj:=1;k:=1;;WHILEE(i<==n)ANND(j<<=n)DDO[WHILEE(i<==n)ANND(j>>0)DOO[aa[i,j]]:=k;i:=i++1;j::=j-1;;k:=kk+1]IFj<<1THEENIFi<=nTHENj:=1ELSE[j:=jj+2;i::=n]ELLSE[ii:=n;j:=j++2]WHILEE(i>00)ANDD(j<==N)DOO[a[i,jj]:=k;;i:=ii-1;jj:=j+11;k:==k+1]]IFi<<1THEENIFj<=nTHENi:=1ELSE[i:=ii+2;j::=n]EELSE[[j:=n;;i:=ii+2]]ENDP;{{sqrmggc}

3、求下列广义义表操作结果果：(1)

HEEAD(TAAIL(HEEAD((((a,b),,(c,d)))))(2)

TAAIL(HEEAD(TAAIL((((a,b),,(c,d)))))【解答】（11）b((2)((d)

4、利用广义义表的HEAAD和TAIL操作作，写出如上上题的表达式式，把原子bbananaa从下列广义义表中分离出出来。（1）

L11=（applee,(peaar),(((bananna)),((((oraange))))）;（2）

L22=(appple,(ppear,((bananna),orrange)));【解答】(1))HEADD(HEADD(HEADD(TAILL(TAILL(L1))))))(2)HHEAD(HHEAD(TTAIL(HHEAD(TTAIL(LL1))))))

第六章树和二叉树树

一、内容提要要

1、树是复杂的的非线性数据据结构，树，二二叉树的递归归定义，基本本概念，术语语。2、二叉树的性性质，存储结结构。3、二叉树的遍遍历算法（递递归，非递归归）。4、线索二叉树树5、树的存储结结构，树、森森林的遍历及及和二叉树的的相互转换。6、二叉树的应应用：表达式式求值、判定定问题及哈夫夫曼树和哈夫夫曼编码。

二、学习重点

（本章内容是本本课程的重点点）1、二叉树性质质及证明方法法，并能把这这种方法推广广到K叉树。2、二叉树遍历历的递归算法法，本书中介介绍了三种（先先、中、后序序）方法，另另三种也应会会用。前序和和中序的非递递归遍历。遍遍历是基础，由由此导出许多多实用的算法法，如求二叉叉树的高度、各各结点的层次次数、度为00、1、2的结点数，二二叉树的相似似、全等、复复制等等的算算法。3、由二叉树的的遍历的前序序和中序序列列或后序和中中序序列可以以唯一构造一一棵二叉树，手手工模拟及编编写算法。由由前序和后序序序列不能唯唯一确定一棵棵二叉树。4、二叉树线索索化的实质是是建立结点在在相应序列中中的前驱和后后继之间的直直接联系。在在何序（前、中中、后）下进进行何种（全全、前驱、后后继）线索化化，并求某结结点相应的前前驱和后继。5、完全二叉树树的性质，顺顺序存储结构构和二叉树链链表存储结构构的相互转换换。6、树的双亲表表示法和孩子子兄弟表示法法间的相互转转换。7、树、森林和和二叉树间的的相互转换（“连线”、“切线”和“旋转”）。8、哈夫曼树的的定义、构造造及求哈夫曼曼编码。

三、例题及分析析

在二叉树中查找找其数据域为为x的结点。如如存在，返回回该结点指针针，否则返回回空指针。【分析】可采采用递归遍历历算法。【算法】PROCssearchh(bt:bbitrepptr;x:dattatypee);{bt是是bitreeptr型的的二叉树，xx是待查找数数据值,本算法递归归遍历二叉树树，在遍历中中进行查找。算算法中p是调用本过过程的过程中中定义的变量量，初值为NNIL，查找找成功后，pp指向数据域域为x的结点。foound是初初值为fallse的变量量。从本过程程返回后，测测试founnd以确定是是否查找成功功。}IF(bbt<>NIIL)ANDNOTfounddTHHEN[IIFbt^^.dataa=xTHEEN[pp:=bt;;founnd:=trrue]]ssearchh(bt^^.lchiild,xx);ssearchh(bt^^.rchiild,xx);]]EENDP;{seerch}【讨论】本算法核心语句句有三个（即即第一个THHEN后的语语句：第一个个语句是“访问”根结点.后两个语语句是递归遍遍历（相对位位置不变）。在在这三个语句句中，由“访问”语句所处位位置不同（前前、中、后），形形成三种递归归遍历方法：：前序、中序序和后序。Found是为为查到x就立即（不不再遍历未遍遍历结点）而而设立的。若若要再考虑本本算法的优化化，则在两个个调用语句中中可加上IIf(btt^.lchhild<>>NIL)ANDNOTfoundd和IIf(btt^.rchhild<>>NIL)ANDNOTfoundd其优点是在左（右右）为空时不不必再调用，且且一旦找到xx就立即退出出。

２．设二叉树采采用二叉链表表作为存储结结构，试编写写算法求二叉叉树的结点数数。【分析】计算二二叉树结点数数的数学模型型如下：f(bt)=00若bt=niilf(bt)=ff(bt^..lchilld)+ff(bt^..rchilld)+11否否则【算法】FUNNCnoddes(btt:bitrreptr)):inteeger;IFbtt=nilTHEENnoddes:=00ELLSE[n1:=nnodes((bt^.llchildd)nn2:=noodes(bbt^.rcchild))nodess:=ni++n2+1]ENDFF{noddes}【讨论】二叉叉树由根、左左子树、右子子树三部分组组成，很多问问题（如求叶叶子、度１、度度２结点数），可可分解到三部部分求解，上上面写出数学学递归模型是是有普遍意义义的。例如：：（１）.二叉叉树相似：f(tt1,t2))=truee若t1=t22=NILf(t11,t2)==falsee若t11,t2中只只有一个为NNILf(t11,t2)==f(t1^^.lchiild,tt2^.lcchild))ANDf(t1^^.rchiild,t22^.rchhild)若t1,tt2均不为NILL(2)求二二叉树的叶子子结点数f(bt)=00当bt=niilf(bt)=11当bt左右子树树均为空f(bt)=ff(bt^..lchilld)+f((bt^.rrchildd)否则（３）求二叉树树所有叶子结结点的最大枝枝长：00若bt^.llchildd=nil且bt^.rrchildd=nilmmaxl(bbt^.lcchild))+1若若bt^.rrchildd=nilmax=maxl((bt^.rrchildd+1)若bt^.llchildd=nilmmax(maaxl(btt^.rchhild+11),maaxl(btt^.rchhild)))+1否则则３．打印二叉树树中结点x（假定存在在）的所有祖祖先结点。【分析】在在二叉树的递递归遍历等算算法中，只有有后序遍历才才是最后访问问根结点，因因此有可能保保留从根结点点到待查结点点的踪迹，这这时可用栈，存存放从根结点点到x结点路径中中的各祖先结结点。【算法】PROCpprintaansctrr(bt:bbitrepptr;x:dattatypee);{bt是是bitreeptr型的的二叉树，xx是待查找数数据值,本算法输出出X结点的各祖祖先结点。SS是工作栈，存存放X的祖先结点点。查到X后，依次输输出S中数据即可可。}initsstack((s);pp:=bt;;pushh(s,p));WHILEENOTTemppty(s))DO[WHILEENOTemptyy(s)AAND(pp^.datta<>x))DO[ppush(ss,p);p:=p^^.lchiild]IFFp^.ddata=xxTHENNWHILLENOTT(emppty(s)))DO[p:=ppop(s));wriite(p^^.dataa)]ELSEE{需要到到右分枝去查查x结点}[q:=nnil;rrend:==true;;{rennd是为了在在右分枝不空空时就退出循循环}WHILLENOTTemptty(s)ANDrrendDDO[[p:=poop(s);;IFp^^.r=qTHENq:=p{右分枝为为空时退栈}}ELLSE[push((s,p);;p:=p^^.rchiild;rrend:==falsee]]ENDP；{priintanssctr}

第七章图图

一、内容提要

1．图的定定义，概念、术术语及基本操操作。2．

图的存存储结构。3．

图的遍遍历。4．

图的应应用（连通分分量，最小生生成树，拓扑扑排序，关键键路经，最短短路经）。

二、学习重点图是应用最广广泛的一种数数据结构，本本章是这门课课程的重点。1

基本本概念中，连连通分量，生生成树，邻接接点是重点。2

图是是复杂的数据据结构，也有有顺序和链式式两种存储结结构：数组表表示法（重点点是邻接距阵阵）和邻接表。这两种存存储结构对有有向图和无向向图均适用。十十字链表是有有向图的另一一种表示，将将有向图的邻邻接表和逆邻邻接表合一。邻邻接多重表是是无向图邻接接表的改进，将将边结点的数数量减少一半半（正好等于于边的数量）。3

图的的遍历是图的的各种算法的的基础，应熟熟练掌握图的的深度、广度度优先遍历，手手工模拟图的的遍历中栈和和队列指针状状态的变化。4

在（强强）连通图中中，主过程一一次调用深（宽宽）度优先遍遍历过程（ddfs/bffs），即可可遍历完全部部顶点，故可可以用此方法法求出连通分分量的个数，并并能画出遍历历中形成的深深（宽）度优优先生成树。5

连通通图的最小生生成树不是唯唯一的，但最最小生成树边边上的权值之之和是唯一的的。应熟练掌握握prim和krusccal算法，特特别是手工分分步模拟生成成树的生成过过程。6

拓扑扑排序是在有有向图上对入入度（先后）为为零的顶点的的一种排序，结结果不唯一。关关键路经是在在拓扑有序的的前提下求出出来的，从源源点到汇点的的最长路径。应应能掌握这两两种算法，并并熟练手工模模拟。理解“减少关键活活动时间能缩缩短工期”，是指该活活动为所有关关键路径所共共有，且减少少到尚未改变变关键路经的的前提下才有有效。7

从单单源点到其他他顶点，以及及各个顶点间间的最短路经经问题，掌握握算法，并熟熟练手工模拟拟。

三、例题解析

1、用邻接多重重表实现图的的各种运算。【分析】在邻接接多重表中，每每条边用一个个结点表示，不不象在邻接表表中那样用两两条边来表示示。这在图的的操作中，要要比其他的存存储结构要复复杂的多。PROCcrrt_graaph(vargg:adjmmulistt);｛g为教材中中已定义的aadjmullist类型型变量，本算算法建立有nn个结点e条边的图图的存储结构构｝FORI::=1TOnnDO【reead(gg[i].ddata;g[i]..firsttedge::=nil))】｛建立顶点向量量，各顶点所所指向的第一一条边指针为为nil｝FORr::=1TOeeDO【read((vi,vjj);｛读读两结点｝i:=loc__verteex(g,vvi);j:=lloc_veertex((g,vj))new(p);;p^..ivex::=i;p^.jvvex:=jj;p^.ilinnk:=g[[i].fiirsteddge;g[i]].firsstedegg:=p｛将边（vi，vj）分别插插入顶点vii，vj的边结点点链表中。｝｝】ENDP;{ccrt_grraph}【讨论】在本算算法中，设输输入的边不含含有重复边，即即输入（vii，vj）后，即即不应再输入入（vi，vj），也也不应再输入入（vj，vi）。否则则，本算法应应添加查询功功能（即下面面searcch过程）。查查询成功时该该边不再加入入到图的存储储结构中。FUNCssearchh(g:addjmuliist;I,,j:1...vtxnuum):eddgeptrr;｛本算法在图gg中查询顶点点vi，vj间的边结结点是否已建建立。如是，则则返回该边结结点的指针，否否则返回niil｝p:=gg[i].ffirsteedge;foound:==falseeWHIILE((p<>NIIL)AANDNNOTffoundDOIFFp^..ivex==i{结结点中iveel，jvex域均可能为为i}THEENIFp^.jvvex=jTHEENfoound::=truueELSSEp::=p^.iilink｛顺ilinnk下找｝ELSSEIFFp^.iivex=jj｛p^.jvvex=i｝｝THEENfouund:==trueELLSEpp:=p^..jlinkk｛｛顺jlinnk下找｝;ENDF;{seaarch}PROCinnsert__edge(VARg:adjjmulisst;vii,vj:vvtxptrr);｛本算法在邻邻接多重表中中插入边（vi，vj）｝i:=loc__verteex(g,vvi);j:=loc__verteex(g,vvj);fp:=seaarch(gg,i,j));IFfp:==nil｛｛若边（vii，vj）在图图中不存在｝｝THEN【new(pp);p^.ivvex:=ii;p^^.jvexx:=j;p^.illink:==g[i]..firsttedge;;g[ii].firrstedgge:=p;;p^.jllink:==g[j]..firsttedge;;g[jj].firrstedgge:=p;;】ENDP;{inssert}

PROCinnsert__verteex(VVARg::adjmuulist;;v:vttxptr));｛本算法在邻接接多重表中插插入顶点V。设顶点向向量足够大，插插入一顶点也也就是加一个个向量元素，设设m是已有顶点点数，则｝gg[m+1]].dataa:=v;;g[m++1].fiirsteddge:=nnil;ENDP;{inssert_vvertexx}

PROCdeelete__edge(VARRg:addjmuliist;vvi,vj::vtxpttr);{本算法在邻接接多重表g中删除边（vvi，vj）｝ i:=loc__verteex(g,vvi);j:=loc__verteex(g,vvj);fp:=seaarch(gg,i,j));IFfp<>>nilTHEN【p:=gg[i].ffirsteedge;q:=niil;{修改改i的链表边结结点(vi,,vj)的前前驱的指针}}WHILEEp<>fpDOO【q::=p;IFp^^.ivexx=iTHENp::=p^.iilinkELSEp::=p^.jjlink】IFq=nnil{删删除的边是顶顶点vi的第一边边结点}THEENIFp^.ivvex=iTHHENgg[i].ffirsteedge:==p^.illinkELLSEgg[i].ffirsteedge:==p^.jllinkELLSE{{所删除的不不是vi的第一边边结点}IFq^^.ivexx=iTTHENIIFp^..ivex==iTHEENq^..ilinkk:=p^..ilinkkELSEEq^.iilink::=p^.jjlinkEELSEIIFp^..ivex==iTHHENq^^.jlinnk:=p^^.ilinnkELSSEq^^.jlinnk:=p^^.jlinnk;p:==g[j]..firsttedge;;q:=nnil;{{修改j的链表边结结点(vi,,vj)的前前驱的指针}}｛从vj的边结点点链表中找到到（vi，vj）边，修修改前驱指针针，算法同上上，故略｝disspose((fp);】ENDP；{ddeletee_edgee}PROCdeelete__verteex(VVARg::adjmuulist;;v:vttxptr));{删除顶点的算算法，该顶点点删除后，在在其顶点向量量数据域中作作标记，且要要删除与该顶顶点相关的所所有边}i:==loc_vverdexx(g,vv);p:==g[i]..firsttedge;;WWHILEp<>nnilDOO【IFFp^.iivex=IITHENNs:=pp^.iliink{{记住下一边边结点}ELSEs:=p^^.jlinnk;IIFi=pp^.iveexTHEENdellete_eedge((g:,v,,g[p^..jvex]].dataa)ELSEdelette_edgge(g::,v,g[[p^.ivvex].ddata)pp:=s】ENDP;{{delette_verrtex}

2、编写对图图的深度优先先非递归遍历历算法。【分析】使使用栈，调用用过程的算法法同教材，对对被调用过程程编写如下：：PROCCdfss(g:addjlistt;v00:vtxpptr);｛｛本算法从顶顶点v0开始。在在图g中进行深深度优先遍历历。算法中vvisiteed是在主过过程中已赋值值falsee的辅助数组组，s是元素为边边（弧）结点点的工作栈。｝｝initstaack(s));wrrite(vv0);visitted[v00]:=trrue;p:=g[v]].firsstarc;;WHILE(p<>nnil)ANDNOTemptyy(s)DO【WHILEp<>nnilDDOIFFvissited[[p^.addjvex]]THEENp::=p^.nnextarrcELSSE【writte(pp^.adjjvex);;pushh(s,p));vissited[p^.aadjvexx]:=trrue;p:==g[p^..adjveex].fiistarcc;】IFNOTemptyy(s)THEN【pp:=popp(s);p:=p^.nnextarrc】

】ENDP; {{dfs}第八章动态态存储管理

一、内容提要

1．

动态存存储管理指的的是在用户需需要时给分配配内存，而在在用户结束使使用时，系统统要收回用户所占空空间。2．

可利用用空间表的三三种结构形式式：结点固定定大小；分几几种规格；任任意大小。3．

可利用用空间表的两两种组织形式式：目录表，链链表。4．

可利用用空间表的分分配方式：首首次拟合法，最最佳拟合法，最最差拟合法。5．

可利用用空间表的分分配和回收的的两种基本实实现方法：边边界标识法，伙伙伴系统。6．

无用单单元回收和紧紧缩存储的概概念。

二、学习重点

1、概念：可利利用空间表及及分配方式，紧紧缩存储，伙伙伴系统，等等。2、边界表示法法的分配及回回收算法。3、伙伴系统的的分配及回收收算法。

三、例题解析

设有大小为5112字节的存存储，有6个用户申请请大小分别为为23，4