数据结构对象的基本概念44542.docx

《数据结构对象的基本概念44542.docx》由会员分享，可在线阅读，更多相关《数据结构对象的基本概念44542.docx（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录目录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二、学习重点

2、24三、例题解析25第十章 内内部排序27一、内容提要27二、学习要点27二、例题解析27第十一章 外外部排序30一、内容提要30二、学习要点30三、习题解析30第十二章 文件件32一、内容提要32二、学习重点32第一章 绪绪论一、内容提要1 数据结构研研究的内容。2 基本概念：数据、数据据元素、数据据对象、数据据结构、数据据类型、抽象象数据类型、多多形数据类型型。3 算法的定义义及五个特征征。4 算法描述：类PASCCAL语言。5 算法设计要要求。6 算法分析。二、学习重点1 数据结构的的“三要素”：逻辑结构构、物理（存存储）结构及及在这种结构构上所定义的的操作（运算算） 。2 抽象数据类类

3、型的定义、表表示和实现方方法。3 类PASCCAL书写规规范，过程（函函数）中值参参和变参的差差别，过程调调用规则。4 用计算语句句频度来估算算算法的时间间复杂度。三、例题解析1 写出以下各各语句执行次次数（左边括括号内数字为为语句序号）(1) FOOR i:=1 TOO n DO(2) FORR j:=1 too n DO(3) cI,j := 0;(4) FORR k:=1 TO nn DOO(5) cI,jj:=cI,j+aI,kk*bkk,j 答案：各语语句执行次数数（频度）分分别为n+11，n(n+11), n22 , n22(n+1), n3 分析：最容容易发生的错错误，是将第第一

4、个语句的的执行次数答答成n。2 编写最优算算法，从小到到大依次输出出顺序读入的的三个整数PROC aasscennding;本算法对读入入的三个整数数进行排序，然然后按从小到到大输出算法中核心语语句如下 rread(aa,b,c); IIF abb THHEN t:=a; a:=bb; b:=t; a,b按正正序排序 IIF bcc THHEN t:=c; c:=bb; c为为最大 IF aat TTHEN b:=t b为中间值值 ELLSE b:=a; a:=tt a,b正序 WRITEELN(a:4,b:44,c:4); ENDP; asseendingg分析：本题题正确算法有有多种，但上

5、上面是最优算算法：最好情情况下只经过过两次比较且且无数据移动动，而在最坏情况下，也只只是经过三次次比较，七个个赋值语句就就完成了排序序。在本课程教学中中，强调“好”的算法, 不仅仅是是结果正确, 而且是是最优的算法法。这与PAASCAL语语言教学中的的要求有很大大不同。 算法是供供人来阅读的的，必须牢记记这一点。算算法中语句的的书写格式采采用缩进规则则，保留字用用大写，其余标识符小小写，提高了了算法的易读读性。第二章 线性性表一 、内容提要要1线性表是元元素间约束力力最强的一类类数据结构。 2线性表的的逻辑结构定定义，对线性性表定义的操操作。3线性表的存存储结构：顺顺序存储结构构和链式存储储结

6、构。4线性表的操操作在两种存存储结构中的的实现。5一元多项式式的线性表表表示方法，及及高次（稀疏疏）多项式的的抽象数据类类型定义、表表示和加法的的实现。二 、学习重点点1 1 线性表表的逻辑结构构，指线性表表的数据元素素间存在着线线性关系。在在顺序存储结结构中，元素素存储的先后后位置反映出出这种线性关关系，而在链链式存储结构构中，是靠指指针来反映这这种关系的。2 2 顺序存存储结构用向向量（一维数数组）表示，给给定下标，可可以存取相应应元素，属于于随机存取的的存储结构。3 3 尽管“只要知道某某结点的指针针就可以存取取该元素”，但因链表表的存取都需需要从头指针针开始，顺链链而行，故链链表不属于

7、随随机存取结构构。4 4 链表是是本章学习的的重点和难点点。要理解头头结点，首元元结点和元素素结点的差别别。理解头结结点是为了在在插入、删除除等操作时，为为了算法的统统一而设立的的（若无头结结点，则在第第一元素前插插入元素或删删除第一元素素时，链表的的头指针总在在变化）。掌掌握通过画出出结点图来进进行链表的生生成、插入、删删除、遍历等等操作。5 5 链表操操作中应注意意不要使链意意外“断开”。因此，若若在某结点前前插入一个元元素，或删除除某元素，必必须知道该元元素的前驱结结点的指针。6 6 从时间间和空间复杂杂度的角度综综合比较线性性表在顺序和和链式两种存存储结构下的的特点。7 7 静态链链表

8、是又一重重点和难点。应应和链表进行行比较、理解解。例如，在在有头结点的的链表情况下下，第一元素素是p:=lla.neext，而在在静态链表中中则i:=ssa0.next；相对p:=p.neext,有i:=saai.nnext来找找到第i个元素的后后继。三、例题解析设线性表以以顺序存储结结构存于a(1.n)中，试编写写算法将该线线性表就地逆逆置。【分析】向量逆置有有几种方法，如如逆向读入到到另一数组中中，在正向对对应赋值，即即：FOR i:=n DOWWNTO 11 DO bn-ii+1:=ai; FORR i:=11TO n DO ai:=bbi;这里要求“就地地逆置”，即不能另另用一数组空空

9、间。【算法】PRROC iinvertt(VAR a:arrr; n:iintegeer); a是存储线线性表的一维维数组，有nn 个元素，本本算法将a逆置。FOR i:=1TO (n DIIV 2) DO aaiaan-i+1;endp;【讨论】将nn个元素的一一维数组逆置置，为什么循循环控制变量量用n diiv 2，而而不用n？编编写在单链表表上进行排序序的算法【分分析】这里里使用插入排排序。链表中中插入元素要要知道待插入入元素位置的的前驱，以pre表示之之。结束的条条件是链表为为空。 【算算法】PROC inserrtsortt(VAR la:liinklisst); la是是带头结点的

10、的单链表的指指针，本算法法将链表中元元素正序排序序。算法的基基本思想是先先假定第一个个元素有序，然然后从第二个个元素开始，依依次插入到有有序的表中，直直到全部元素素插入完为止止p:= lla.neext.nnext;假定链表非非空，即至少少有一个结点点la.nnext.next:=nil;设有序链链表中当前只只有一个结点点 fouund:=ffalse;WHILEE (pnil)AAND NOOT fouund DOO s:=pp.nexxt;记住住下一个结点点pree:=la; q:=lla.neext; ffound:=falsse; WWHILE(qniil)ANDD NOT found

11、d DO IF q.dataap.ddata TTHEN pre:=q; q:=q.nnext ELSEE founnd:=trrue;p.nextt:=q;pre.neext:=pp;p结点点插入p:=s;取取下一个结点点ENDP; inseertsorrt【讨论】算法中中foundd为一布尔变变量，为的是是在链表到尾尾前，如找到到p的插 入位置，即可退退出WHILLE循环。这这里循环条件件未写成： （pniil）AND (q.daata0,n00）,分别存于一一维数组a和b中，且a 的存储空空间足够大。试试编写算法将将两线性表合合并成一线性性表，结果仍仍是非递减有有序，要求算算法的时间复复

12、杂度是o(m+n)。 【分析】 两个有序线线性表合并成成一个有序表表，教材中已已有讨论，算算法非常简单单。本算法要要求复杂度为为O(m+nn)，这是着着重点。题目目叙述中有“a的空间足够够大”，暗示出若若将m+n个元素素合并到a中，不会溢溢出。为使数数据移动次数数最少，应先先将两表中最最大元素置于于m+n的位置置上，然后相相应指针减11，再比较之之，直到两表表中有一个指指针减到0，则结束，否否则，将b中剩余元素素传到a中相应位置置即可。 【算法】 PRROC uunion(VAR aa:seqllisttpp;b:seeqlistttp); a,bb是两个非递递减有序表，顺顺序存储结构构存储，

13、各有有m和n个元素，本本算法将两表表合并到a中，仍为有有序表，算法法时间复杂度度为O(m+n) i:=m; j:=n ;kk:=m+nn; i,j,k分别别为表a,bb和结果表的的指针 WHHILE (i0) AND (j0) DO IF aibj THEN ak:=aii; i:=i-1; k:=kk-1 ELSEE akk:=bj; jj:=j-11; k:=k-1; WHIILE (jj0) DDO ak:=bbj; j:=j-1; k:=k-1; 若b表中尚有元元素，则传至至a中相应位置置【讨论】 本算法至多比较m+n次，往a中赋值m+n次。最好情况是比较n次，往a中赋值n次，该种情况

14、是b中最小元素不小于a中最大元素。问问题：为什么么在退出第一一个WHILLE循环后，不不讨论（即没没有）WHIILE i0的情况？ 第三章 栈和和队列 一、内容提提要1 1从数据结构构角度讲，栈栈和队列也是是线性表，其其操作是线性性表操作的子子集，属操作作受限的线性性表。但从数数据类型的角角度看，它们们是和线性表表大不相同的的重要抽象数数据类型。2 2栈的定义及及操作。栈是是只准在一端端进行插入和和删除操作的的线性表，该该端称为栈的的顶端。3 3栈的顺序和和链式存储结结构，及在这这两种结构下下实现栈的操操作。4 4栈的应用：表达式求值值，递归过程程及消除递归归。5 5队列的定义义及操作，队队列

15、的删除在在一端（尾），而而插入则在队队列的另一端端（头）。因因此在两种存存储结构中，都都需要队头和和队尾两个指指针。6 6链队列空的的条件是首尾尾指针相等，而而循环队列满满的条件的判判定，则有队队尾加1等于队头和设标记两两种方法。 二、学习重重点 1栈栈和队列操作作在两种存储储结构下的实实现。 2中中缀表达式转转成前缀、后缀表达式式并求值。3用递归解决决的问题：定定义是递归的的，数据结构构是递归的，及及问题的解法法是递归的， 掌握典型型问题的算法法。 4 4 链队列列删除时为空空的处理（令令队尾指针指指向队头）。特特别是仅设尾尾指针的循环环链队 列的各种种操作的实现现。5 5 循环队队列队空定

16、义义为队头指针针等于队尾指指针，队满则则可用一个单单元（教材中中所示） 及设标记办办法（下面例例题）。这里里特别注意取取模运算。 6 6 在后续续章节中要注注意栈和队列列的应用，如如串中心对称称的判定，二二叉树遍历的的递归 和非递归归算法，图的的深度优先遍遍历等都用到到栈，而树的的层次遍历、图的宽度优优先遍 历等则用用到队列。三、例题解析1 1两栈共享一一向量空间，编编写入栈和出出栈算法。 TYYPE TwoWaayStacck=RECCORD 双栈栈共享一向量量空间 elem:ARRAYY1.mm OF elemttype; top:AARRAY0.1 OF 00.m+11; 两两个栈顶指针

17、针 ENND; PRROC inisttack(VVAR twws:TwooWaySttack); 初始始化 初始化化双向栈twws为空 twws.topp0:=0; 左端端栈指针 twws.topp1:=m+1; 右端端栈指针ENDP; inisstack PROC PPUSH(VVAR twws:TwooWaySttack;ii:0.11; x:eelemtyype;VAAR ofww:boollean); 若双向向栈tws不不满,则将xx插入到i端端,成功时oofw为trrue,失败败为falsse IFF(tws.top11-twss.top0)1 THENN 栈栈未满 CCASE i

18、i OF 0:tws.ttop0:=twss.top0+1;tws.eelemttws.toop0:=x;oofw:=ttrue 1:tws.ttop1:=twss.top1-1;tws.eelemttws.toop1:=x;oofw:=ttrue EENDC ELSSE ofww:=fallse;( 栈满) ENDDP; pushPROC POOP(VARR tws:TwoWaayStacck;i:00.1;VVAR x:elemttype;VVAR unnderfllow:boooleann); 若双向栈栈tws非空空,则将i端端退栈,栈空空时undeerfloww为truee CAASE

19、 i OF 0:IF tws.ttop0=0 栈空 THENNundeerfloww:=truue;retturn(uunderfflow) ELSEE twss.top0:=ttws.toop0-1; x:=tws.eelemttws.toop0+1; 弹出元素素 ; 1:IF tws.ttop1=m+1 栈栈空 THENNundeerfloww:=truue;retturn(uunderfflow) ELSEE twss.top1:=ttws.toop1+1; x:=tws.eelemttws.toop1-1; 弹出元素素 ;ENDCENDP; pop 【讨论】 上面面算法中用00和1代表

20、两两端，且按操操作在哪端来来分两种情况况进行讨论，逻逻辑清楚。也也可用一个公公式表示插入入（进栈）和和删除（退栈栈）指针位置置。例如，插插入时topp=top+1-2*ii,删除时ttop=toop-1+22*i。表达达简洁，但不不如上面清楚楚易读。2 2将中缀表达达式转换成后后缀表达式，并并进行表达式式求值。PROC trrnssuffix(VAAR expp2:strring;ss:stacck; exxp1:sttring); 本算法将中缀缀表达式exxp1转为后后缀表达式eexp2,使使用运算符栈栈s算法基本思想想是依次从中中缀表达式读读入字符w： 若w是变变量，直接送送入结果表达达式

21、，若w是是运算符，则则与栈顶运算算符比较，若若级别高，则则进栈； 若若低，则栈顶顶元素退栈，并并送入结果表表达式，再取取栈顶运算符符比较，重复复以上步骤；若w),则栈元素素依次退栈，并并送入结果表表达式，直至至)退栈栈 innitstrring(eexp2); inittstackk(s);ppush(ss,#); opp:=+,-,*,/,(,),#; 操操作符集合 reead(w); WHIILE NOOT (ww=#) AND (GETTTOP(OPPTR)=#) DO IFF NOT (w INN op) THEN inssert(eexp2,ww); reead(w); ELSEE

22、CASEE preccede(GGETTOPP(s),ww) OF : PUSHH(S,w); reaad(w) ; =: IIF w=) THENN 遇右括括号后，运算算符退栈并送送结果表达式式，直至左括括号 xx:=POPP(S); WWHILE x( DO inserrt(expp2,x);x:=POOP(S) rread(ww) ; : b:=PPOP(S); inssert(eexp2,bb); END;ENDP;PROC suufixevval(VAAR expp2:strring;ss:stacck; VAAR sn:stackk); 本算法对后缀缀表达式exxp2求值，使使用运

23、算符栈栈s和操作数数栈sn算法基本思想想是逐字符从从左到右顺序序读入后缀表表达式。若读读入的字符ww是数，则直直接压入栈 sn中；若若w是运算符符，则与栈顶顶运算符比较较，若级别高高，则进栈；否则，从运运算数栈弹出出两个操作数数，和从运算算符栈弹出的的一个运算符符进行相应运运算，结果存存入操作数栈栈中。w运算算符再与栈顶顶运算符比较较优先级。直直至后缀表达达式处理完毕毕。这时snn栈中只剩一一个数，即表表达式结果。 innitstrring(ssn); iinitsttack(ss); opp:=+,-,*,/,(,),#; 操操作符集合 reead(w); 从左左到右顺序读读入后缀表达达式

24、WHIILE NOOT emppty(exxp2) DDO IFF NOT (w INN op) THEN PUSSH(sn,w); rread(ww); ELSEE CASEE preccede(GGETTOPP(s),ww) OF : a:=PPOP(snn);b:=POP(ssn); ttheta:=POP(s); PUSHH(sn,ooperatte(a ttheta b) ; END;ENDP; suffixevaal3、用设标记来来判定循环队队列满，编写写入队和出队队的算法。 本算法法用设标记ttag的办法法，解决循环环队列队满和和队列空的判判断问题,ttag=0表表示队列空，tt

25、ag=1表表示队列不空空 TYPEE cycliicqueuue=RECCORD 设头尾指针和标标志域的循环环队列 eelem:=ARRAYY0.mm-1 OOF eleemtypee; rrear,ffront:0.m-1 ttag:0.1;为空，为非空 ENDD; PROC IINITQUUEDE(VVAR cqq:cycllicqueeue);初始化化 cq.taag:=0;cq.teear:=ccq.froont:=00; ENDPP;PROC ENNQUEUEE(VAR cq:cyyclicqqueue; x: eelemtyype);ccq是由头尾尾指针和标志志域的循环队队列，本算

26、法法是入队操作作，若队列不不满，则则将x插入到到队尾 IF (ccq.tagg=1) AAND (ccq.froont=cqq.rearr) TTHEN rreturnn(falsse) 队队满 EELSEccq.reaar:=(ccq.reaar+1) MOD mm; ccq.eleem(cq.rear):=r; IIF cq.tag=00 THENN cq.ttag:=11 由空空变不空标记记 ENNDP;PROC DEELQUEUUE(VARR cq:ccycliccqueuee);ccq是由头尾尾指针和标志志域的循环队队列，本算法法是出队操作作，若队列非非空则则将队头元素素出队 IF

27、ccq.tagg=0 TTHEN rreturnn(falsse) 队队空 EELSEccq.froont:=(cq.frront+11) MODD m; IIF cq.frontt=cq.rrear TTHEN ccq.tagg:=0 队空 ENNDP; CONSST m=mmaxlenn;队队列长度 TYPEE ccycliccqueuee=RECOORD只设尾尾指针和队列列长度的循环环队列 ellem: AARRAY0.m-1 OFF elemmtype; reear: 00.m-11; leength: 0.mm;队队列长度 END; PROC IINIT_qqueue(VAR qq:

28、cycllicqueeue);初始化化 q.rrear:=0; q.lengtth:=0;ENDP;FUNC addd_queeue(VAAR q:ccycliccqueuee;x:ellemtyppe):boooleann;q是是由尾指针和和长度标志的的循环队列，本本算法是入队队操作，若队队列不满，将xx插入到队尾尾 IF qq.lenggth=m TTHEN add_qqueue:=falsse 队列满 EELSE q.reear:=(q.reaar+1) mod mm; q.ellemq.rear:=x; q.leength;=q.leength+1; add_queuee:=truue

29、 入队成成功 EENDF;FUNC ddd_queeue(VAAR q:ccycliccqueuee; x;eelemtyype):bbooleaan;qq是由尾指针针和长度标志志的循环队列列，本算法是是出队操作，若若队列不空，将将将队头元素素出列，并赋赋给x，队长长度减 IF qq.lenggth=0 TTHEN ddd_queeue:=ffalse 队空 EELSE frontt;=(q.rear-q.lenngth+11+m) mmod m x:=q.elemfrontt q.lenngth:=q.lenngth-11 EENDF;第四章 串一、内容提要1、 1、 是数据据元素为字符符的

30、线性表，串串的定义及操操作。2、 2、 的基本本操作，编制制算法求串的的其它操作。3、 3、 的存储储结构，因串串是数据元素素为字符的线线性表，所以以存在“结点大小“的问题。静静态和动态（块块链结构，堆堆结构）存储储的优缺点。 4、 4、 朴素模模式匹配算法法及改进（KKMP）算法法。二、学习重点1、 1、 串的基基本操作，编编写串的其他他操作（如iindex,replaace等）。2、在串的模式式匹配中，求求匹配串的nnextvaal 函数值值。3、尽管朴素的的模式匹配的的时间复杂度度是O(m*n), KKMP算法是是O(m+nn),但在一一般情况下，前前者实际执行行时间近似OO(m+n),

31、因此至今今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。5、 5、 串操作作在存储结构构下的实现。三、例题解析1、利用串的如如下基本运算算creatte(s),assiggn(s,tt),lenngth(ss),subbstr(ss,starrt,lenn),conncat(ss1,s2),编写操作作replaace的算法法PROC rreplacce(VARR s:sttring; t,v:strinng); 本本算法实现串串的置换操作作，用串v置换串s中所有非重重叠的t串。 i:=INDEEX(s,tt); 判判s中有无t IFF i

32、00 THENN CRREATE (tempp, ); t为临时时串变量，存存放部分结果果 m:=LENGGTH(t); n:=LENGGTH(s); WHHILE i0 DO 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;FUNC indexx(s

33、1: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) AND eq DO IF eqqual(ssubstrr(s,j,n),t) THEEN eqq:=fallse ELSE j:=j+1；IF j=mm+n-1 THEN indeex:=j ELSE indeex:=0ENDF；iindex 【讨论】 本题是用给给定的基本操操作，编写其其它操作的算算法。这种类类型题较多，必必须严格按题题的要求来做做，不准选择择具体存储结结构。否则，即即使全对，也也很难得分。 2 2 设目目标为 t=abbcaabbbabcabbaacbaacba,模式串 p=abcaabaa;(1)计算P的的NEXTVVAL函数值值；(2)不写出算算法，只