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

目录目录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 算法描述：类PASCAL语言。5 算法设计要求。6 算法分析。 二、学习重点1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算） 。2 抽象数据类型的定义、表示和实现方法。3 类PASCAL书写规范，过程（函数）中值参和变参的差别，过程调用规则。4 用计算语句频度来估算算法的时间复杂度。 三、例题解析1 写出以下各语句执行次数（左边括号内数字为语句序号）(1) FOR i:=1 TO n DO(2) FOR j:=1 to n DO(3) cI,j := 0;(4) FOR k:=1 TO n DO(5)                                       cI,j:=cI,j+aI,k*bk,j 答案：各语句执行次数（频度）分别为n+1，n(n+1), n2 , n2(n+1), n3 分析：最容易发生的错误，是将第一个语句的执行次数答成n。  2 编写最优算法，从小到大依次输出顺序读入的三个整数PROC asscending;本算法对读入的三个整数进行排序，然后按从小到大输出算法中核心语句如下 read(a,b,c); IF a>b THEN t:=a; a:=b; b:=t; a,b按正序排序 IF b>c THEN t:=c; c:=b; c为最大 IF a<t THEN b:=t b为中间值 ELSE b:=a; a:=t a,b正序 WRITELN(a: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:=sa0.next；相对p:=p.next,有i:=sai.next来找到第i个元素的后继。 三、例题解析 设线性表以顺序存储结构存于a(1.n)中，试编写算法将该线性表就地逆置。【分析】向量逆置有几种方法，如逆向读入到另一数组中，在正向对应赋值，即：FOR i:=n DOWNTO 1 DO bn-i+1:=ai; FOR i:=1TO n DO ai:=bi;这里要求“就地逆置”，即不能另用一数组空间。【算法】PROC invert(VAR a:arr; n:integer); a是存储线性表的一维数组，有n 个元素，本算法将a逆置。FOR i:=1TO (n DIV 2) DO aian-i+1;endp;【讨论】将n个元素的一维数组逆置，为什么循环控制变量用n div 2，而不用n？ 编写在单链表上进行排序的算法【分析】这里使用插入排序。链表中插入元素要知道待插入元素位置的前驱，以pre表示之。结束的条件是链表为空。 【算法】PROC insertsort(VAR la:linklist); la是带头结点的单链表的指针，本算法将链表中元素正序排序。算法的基本思想是先假定第一个元素有序，然后从第二个元素开始，依次插入到有序的表中，直到全部元素插入完为止p:= la.next.next;假定链表非空，即至少有一个结点la.next.next:=nil;设有序链表中当前只有一个结点 found:=false;WHILE (p<>nil)AND NOT found DO s:=p.next;记住下一个结点pre:=la; q:=la.next; found:=false; WHILE(q<>nil)AND NOT found DO IF q.data<p.data THEN pre:=q; q:=q.next ELSE found:=true;p.next:=q;pre.next:=p;p结点插入p:=s;取下一个结点ENDP; insertsort【讨论】算法中found为一布尔变量，为的是在链表到尾前，如找到p的插 入位置，即可退出WHILE循环。这里循环条件未写成： （p<>nil）AND (q.data<p.data)因为若q=nil ，则再引用q.data是无意义的。请记住这种退出循环，引入布尔变量的作法。 3设两个非递减有序的线性表各有m和n个元素（m>0,n>0）,分别存于一维数组a和b中，且a 的存储空间足够大。试编写算法将两线性表合并成一线性表，结果仍是非递减有序，要求算法的时间复杂度是o(m+n)。 【分析】 两个有序线性表合并成一个有序表，教材中已有讨论，算法非常简单。本算法要求复杂度为O(m+n)，这是着重点。题目叙述中有“a的空间足够大”，暗示出若将m+n个元素合并到a中，不会溢出。为使数据移动次数最少，应先将两表中最大元素置于m+n的位置上，然后相应指针减1，再比较之，直到两表中有一个指针减到0，则结束，否则，将b中剩余元素传到a中相应位置即可。 【算法】 PROC union(VAR a:seqlisttp;b:seqlisttp); a,b是两个非递减有序表，顺序存储结构存储，各有m和n个元素，本算法将两表合并到a中，仍为有序表，算法时间复杂度为O(m+n) i:=m; j:=n ;k:=m+n; i,j,k分别为表a,b和结果表的指针 WHILE (i>0) AND (j>0) DO IF ai>bj THEN ak:=ai; i:=i-1; k:=k-1 ELSE ak:=bj; j:=j-1; k:=k-1; WHILE (j>0) DO ak:=bj; j:=j-1; k:=k-1; 若b表中尚有元素，则传至a中相应位置【讨论】 本算法至多比较m+n次，往a中赋值m+n次。最好情况是比较n次，往a中赋值n次，该种情况是b中最小元素不小于a中最大元素。问题：为什么在退出第一个WHILE循环后，不讨论（即没有）WHILE i>0的情况？  第三章 栈和队列   一、内容提要 1 1从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。2 2栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。3 3栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。4 4栈的应用：表达式求值，递归过程及消除递归。5 5队列的定义及操作，队列的删除在一端（尾），而插入则在队列的另一端（头）。因此在两种存储结构中，都需要队头和队尾两个指针。6 6链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。   二、学习重点  1栈和队列操作在两种存储结构下的实现。 2中缀表达式转成前缀、后缀表达式并求值。3用递归解决的问题：定义是递归的，数据结构是递归的，及问题的解法是递归的， 掌握典型问题的算法。 4 4  链队列删除时为空的处理（令队尾指针指向队头）。特别是仅设尾指针的循环链队 列的各种操作的实现。5 5  循环队列队空定义为队头指针等于队尾指针，队满则可用一个单元（教材中所示） 及设标记办法（下面例题）。这里特别注意取模运算。 6 6  在后续章节中要注意栈和队列的应用，如串中心对称的判定，二叉树遍历的递归 和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的宽度优先遍 历等则用到队列。 三、例题解析 1 1两栈共享一向量空间，编写入栈和出栈算法。 TYPE TwoWayStack=RECORD 双栈共享一向量空间 elem:ARRAY1.m OF elemtype; top:ARRAY0.1 OF 0.m+1; 两个栈顶指针 END; PROC inistack(VAR tws:TwoWayStack); 初始化 初始化双向栈tws为空 tws.top0:=0; 左端栈指针 tws.top1:=m+1; 右端栈指针ENDP; inistack  PROC PUSH(VAR tws:TwoWayStack;i:0.1; x:elemtype;VAR ofw:boolean); 若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为false IF(tws.top1-tws.top0)<>1 THEN 栈未满 CASE i OF 0:tws.top0:=tws.top0+1;tws.elemtws.top0:=x;ofw:=true 1:tws.top1:=tws.top1-1;tws.elemtws.top1:=x;ofw:=true ENDC ELSE ofw:=false;( 栈满) ENDP; pushPROC POP(VAR tws:TwoWayStack;i:0.1;VAR x:elemtype;VAR underflow:boolean); 若双向栈tws非空,则将i端退栈,栈空时underflow为true CASE i OF 0:IF tws.top0=0 栈空 THENunderflow:=true;return(underflow) ELSE tws.top0:=tws.top0-1; x:=tws.elemtws.top0+1; 弹出元素 ; 1:IF tws.top1=m+1 栈空 THENunderflow:=true;return(underflow) ELSE tws.top1:=tws.top1+1; x:=tws.elemtws.top1-1; 弹出元素 ;ENDCENDP; pop 【讨论】 上面算法中用0和1代表两端，且按操作在哪端来分两种情况进行讨论，逻辑清楚。也可用一个公式表示插入（进栈）和删除（退栈）指针位置。例如，插入时top=top+1-2*i,删除时top=top-1+2*i。表达简洁，但不如上面清楚易读。 2 2将中缀表达式转换成后缀表达式，并进行表达式求值。PROC trnssufix(VAR exp2:string;s:stack; exp1:string); 本算法将中缀表达式exp1转为后缀表达式exp2,使用运算符栈s算法基本思想是依次从中缀表达式读入字符w： 若w是变量，直接送入结果表达式，若w是运算符，则与栈顶运算符比较，若级别高，则进栈； 若低，则栈顶元素退栈，并送入结果表达式，再取栈顶运算符比较，重复以上步骤；若w),则栈元素依次退栈，并送入结果表达式，直至)退栈 initstring(exp2); initstack(s);push(s,#); op:='+','-','*','/','(',')','#' 操作符集合 read(w); WHILE NOT (w='#') AND (GETTOP(OPTR)='#') DO IF NOT (w IN op) THEN insert(exp2,w); read(w); ELSE CASE precede(GETTOP(s),w) OF '<': PUSH(S,w); read(w) ; '=': IF w=) THEN 遇右括号后，运算符退栈并送结果表达式，直至左括号 x:=POP(S); WHILE x<>( DO insert(exp2,x);x:=POP(S) read(w) ; '>': b:=POP(S); insert(exp2,b); END;ENDP;PROC sufixeval(VAR exp2:string;s:stack; VAR sn:stack); 本算法对后缀表达式exp2求值，使用运算符栈s和操作数栈sn算法基本思想是逐字符从左到右顺序读入后缀表达式。若读入的字符w是数，则直接压入栈 sn中；若w是运算符，则与栈顶运算符比较，若级别高，则进栈；否则，从运算数栈弹出两个操作数，和从运算符栈弹出的一个运算符进行相应运算，结果存入操作数栈中。w运算符再与栈顶运算符比较优先级。直至后缀表达式处理完毕。这时sn栈中只剩一个数，即表达式结果。 initstring(sn); initstack(s); op:='+','-','*','/','(',')','#' 操作符集合 read(w); 从左到右顺序读入后缀表达式 WHILE NOT empty(exp2) DO IF NOT (w IN op) THEN PUSH(sn,w); read(w); ELSE CASE precede(GETTOP(s),w) OF '<': PUSH(s,w); read(w) ; '>': a:=POP(sn);b:=POP(sn); theta:=POP(s); PUSH(sn,operate(a theta b) ; END;ENDP; sufixeval3、用设标记来判定循环队列满，编写入队和出队的算法。 本算法用设标记tag的办法，解决循环队列队满和队列空的判断问题,tag=0表示队列空，tag=1表示队列不空 TYPE cyclicqueue=RECORD 设头尾指针和标志域的循环队列 elem:=ARRAY0.m-1 OF elemtype; rear,front:0.m-1 tag:0.1;为空，为非空 END; PROC INITQUEDE(VAR cq:cyclicqueue);初始化 cq.tag:=0;cq.tear:=cq.front:=0; ENDP;PROC ENQUEUE(VAR cq:cyclicqueue; x: elemtype);cq是由头尾指针和标志域的循环队列，本算法是入队操作，若队列不满，则将x插入到队尾 IF (cq.tag=1) AND (cq.front=cq.rear) THEN return(false) 队满 ELSEcq.rear:=(cq.rear+1) MOD m; cq.elem(cq.rear):=r; IF cq.tag=0 THEN cq.tag:=1 由空变不空标记 ENDP;PROC DELQUEUE(VAR cq:cyclicqueue);cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空则将队头元素出队 IF cq.tag=0 THEN return(false) 队空 ELSEcq.front:=(cq.front+1) MOD m; IF cq.front=cq.rear THEN cq.tag:=0 队空 ENDP; CONST m=maxlen;队列长度 TYPE cyclicqueue=RECORD只设尾指针和队列长度的循环队列 elem: ARRAY0.m-1 OF elemtype; rear: 0.m-1; length: 0.m;队列长度 END; PROC INIT_queue(VAR q:cyclicqueue);初始化 q.rear:=0; q.length:=0;ENDP;FUNC add_queue(VAR q:cyclicqueue;x:elemtype):boolean;q是由尾指针和长度标志的循环队列，本算法是入队操作，若队列不满，将x插入到队尾 IF q.length=m THEN add_queue:=false 队列满 ELSE q.rear:=(q.rear+1) mod m; q.elemq.rear:=x; q.length;=q.length+1; add_queue:=true 入队成功 ENDF;FUNC dd_queue(VAR q:cyclicqueue; x;elemtype):boolean;q是由尾指针和长度标志的循环队列，本算法是出队操作，若队列不空，将将队头元素出列，并赋给x，队长度减 IF q.length=0 THEN dd_queue:=false 队空 ELSE front;=(q.rear-q.length+1+m) mod m x:=q.elemfront q.length:=q.length-1 ENDF;    第四章    串一、内容提要 1、 1、  是数据元素为字符的线性表，串的定义及操作。2、 2、  的基本操作，编制算法求串的其它操作。3、 3、  的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。静态和动态（块链结构，堆结构）存储的优缺点。 4、 4、  朴素模式匹配算法及改进（KMP）算法。 二、学习重点 1、 1、  串的基本操作，编写串的其他操作（如index,replace等）。2、在串的模式匹配中，求匹配串的nextval 函数值。3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。5、 5、  串操作在存储结构下的实现。 三、例题解析 1、利用串的如下基本运算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法PROC replace(VAR s:string; t,v:string); 本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。 i:=INDEX(s,t); 判s中有无t IF i<>0 THEN CREATE (temp, ); t为临时串变量，存放部分结果 m:=LENGTH(t); n:=LENGTH(s); WHILE i<>0 DO ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i-1),v); 用v替换t形成部分结果 ASSIGN (s,SUBSTR(s, i+m, n-i-m+1); t串以后形成新s串 n:= n-(i-1)-m; i:=INDEX(s,t); ASSIGN (s,CONCAT(temp,s); 将剩余s连接临时串t再赋给s ENDP;FUNC index(s1:string; t:string):integer; 本算法求串t在串s中的第一次出现。 结果是：若t在s中 ，则给出串t的第一个字符在串s中的位置，若不存在，则返回0 j:=1;m:=length(s); n:=length(t); eq:=true; WHILE (j<=m-n+1) AND eq DO IF equal(substr(s,j,n),t) THEN eq:=false ELSE j:=j+1；IF j<=m+n-1 THEN index:=j ELSE index:=0ENDF；index 【讨论】 本题是用给定的基本操作，编写其它操作的算法。这种类型题较多，必须严格按题的要求来做，不准选择具体存储结构。否则，即使全对，也很难得分。 2 2         设目标为 t=abcaabbabcabaacbacba,模式串 p=abcabaa;(1)计算P的NEXTVAL函数值；(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；【解答】 （1）P的 NEXTVAL 函数值如下；j 1 2 3 4 5 6 7 _模式p a b c a b a anextval(j) 0 1 1 0 1 0 2 (2)a b c a a b b a b c a b a a c b a c b a a b c a b 第一趟匹配a b c 第二趟匹配a 第三趟匹配a b c a b a a 第四趟匹配成功【讨论】 为写NEXTVAL方便，可先写出NEXT函数值，在由此求NEXTVAL. 3、字符串s 满足下式，其中HEAD 和 TAIL的定义同广义表类似，如HEAD(XYZ)=X,TAIL(XYZ)=YZ,则S=concat(head(tail(s),head(tail(tail(s)=dc求字符串s。 可供选择的答案是（A） abcd (B) acbd (C) acdb (D) adcb 正确答案是（D）。 第五章 数组和广义表 一、 内容提要 1， 1，  数组的逻辑结构定义及存储，2， 2，  稀疏矩阵（含特殊矩阵）的存储及运算。3， 3，  广义表的定以及存储。4， 4，  广义表运算的递归算法。 二、学习重点 1， 1，  数组（主要是二维）在以行序为主的存储中的地址计算方法。2， 2，  特殊矩阵在压缩存储时的下标变换。3， 3，  稀疏矩阵的三元组表存储结构及矩阵移植的算法。4， 4，  稀疏矩阵的十字链表存储方法及十字链表生成算法。5， 5，  广义表的HEAD和TAIL 运算。6， 6，  给定广义表画出其存储结构。7， 7，  从广义表的递归算法，掌握如何编写递归算法。 三、例题解析 1、字符串二维数组A0.8,1.10 ，每个元素由6个字符组成，每个字符占一个存储单元，则（1）存放A需要多少个字节？（2）A的第8列和第5行共占多少字节？(3) 按行序存储时，A8,5和按列存储时哪个元素时的地址相同？【解答】 （1） 540 （2） 108 （3） A3,10 2、编写算法，将自然数1-n2按蛇形填入n x n矩阵中。 例如，（142）如右图所示。 【分析】本题要求在N的方阵中填人N2个数，关键是控制下标。设坐标原点在矩阵的左上角，且i是向下增长，j向右增长 。原点的坐标为（1，1）。 【算法】 PROC sqrmgc(VAR a:arr;n:integer); 本算法将自然数1-n2 按蛇形填入N X N 矩阵中,a是二维数组i:=1; j:=1; k:=1; WHILE (i<=n) AND (j<=n) DO WHILE (i<=n) AND (j>0) DO ai,j:=k; i:=i+1; j:=j-1; k:=k+1 IF j<1 THEN IF i<=n THEN j:=1 ELSE j:=j+2;i:=n ELSE i:=n; j:=j+2 WHILE (i>0) AND (j<=N) DO ai,j:=k; i:=i-1; j:=j+1; k:=k+1 IF i<1 THEN IF j<=n THEN i:=1 ELSE i:=i+2;j:=n ELSE j:=n; i:=i+2 ENDP; sqrmgc 3、求下