《数据结构复习要点》由会员分享，可在线阅读，更多相关《数据结构复习要点（15页珍藏版）》请在金锄头文库上搜索。
1、A熟练掌握B理解C了解第一章：绪论1. 基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。C 四类数据组织结构：集合、线性表、树形、图状结构 C 数据的存储方式：顺序存储和链式存储。B2. 算法和分析 算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度 B 本章重点：分析算法时间复杂度例 1. 下面关于算法说法错误的是( )A. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的D例 2. 以下那一个术语与数据的存储结构无关？( )A.栈B.哈希表 C.线索树D.双向链
2、表A.例 3. 求下段程序的时间复杂度：void mergesort(int i, int j)int m;if(i!=j)m=(i+j)/2; mergesort(i,m); mergesort(m+1,j);merge(i,j,m);其中mergesort()用于对数组an归并排序，调用方式为mergesort(0,n-l);, merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为0(n)。解：分析得到的时间复杂度的递归关系：t (n)二O(1)n 二 12t(n /2) + O(n)n 1O(n)为merge ()所需的时间，设为cn (c为常量)。因此t (n) = 2(
3、n /2) + cn = 2(2t (n/22) + cn /2) + cn=221 (n /22) + 2cn =.=2kt(n/2k)+kcnn令 k =1，有 k = log2 n有t(n) = 2iog2O(1)+ cnlog n = n + cnlog n = O(nlog n) 2 2 2第二章：线性表1. 线性表的基本运算：. C2. 线性表的顺序存储(利用静态数组或动态内存分配)。 相应的表示与操作 A3. 线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。 A4. 顺序存储与链式存储的比较：基于时间的考虑-分别适用于静态的和动态的操作：比如静态查找和插入删除)；基于
4、空间的考虑- .B这也适用于后面用两种方式存储的其他数据结构。本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表 上进行一些算法设计(与基本操作类似的操作或组合)，请仔细复习。例 4假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将 这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结 点存放归并后的单链表。题目分析因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比 较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排 列。故在合并的同时，将链表结点逆置。void Unio
5、n(LinkList la, LinkList lb)la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将 两链表合并成一个按元素值递减次序排列的单链表。 pa=la-next; pb=lb-next;pa, pb 分别是链表 la 和 lb 的工作指针la-next=null;la作结果链表的头指针，先将结果链表初始化为空。while(pa!=null & pb!=null) 当两链表未访问结束if(pa-datadata) q=pa-next; 将pa的后继结点暂存于q。pa-next=la-next;将pa结点链于结果表中，同时逆置。la-next=pa;p
6、a=q;恢复pa为当前待比较结点。elseq=pb-next;将pb的后继结点暂存于q。pb-next=la-next; 将pb结点链于结果表中，同时逆置。la-next=pb;pb=q; 恢复pb为当前待比较结点。while(pa!=null) 将la表的剩余部分链入结果表，并逆置。q=pa-next; pa-next=la-next; la-next=pa; pa=q; while(pb!=null)q =pb-next; pb-next=la-next; la-next=pb; pb=q; 算法Union结束。注意：(1) 此处q用作暂存后继结点，操作后pa或pb还回原指向位置；这与我们
7、原来不改变pa 或pb的指向，增加一个q=pa或pb作为摘取结点进行添加操作起到的作用一样。(2) 此处要完成逆序插入操作故用头插法(基于头指针la或lb)，注意尾插法(附设一个 尾指针，基于该指针插入)的可完成顺序插入 (注意：逆序另一种方式也要掌握！)练习：练习题2 编程 167判断带头结点双向循环链表L是否对称相等.8. 设计一个算法判断单链表（带头结点）是否是递增的（注意比排序算法应该简单，链 表排序也要会实现）9. 设计一个算法判断有序表A是否是有序表B的子集（即表A中的元素在B中）。思考: 如果递归程序怎么写？）第三章：栈与队列1. 两种特殊线性表：分别有后进先出、先进先出的特性。
8、 B2. 栈的顺序表示与实现（利用静态数组或动态内存分配）A注意栈顶指针的初始位置不同，进出栈，栈空栈满的实现语句有差别！举例：若定义typedef struct SElemType *base;SElemType *top;intstacksize;/当前栈能使用的最大容量 SqStack;SqStack s;top 的初始值指向栈底，即 top=base；栈空条件：s. top =s. base此时不能出栈栈满条件： s.top-s.base=s.stacksize进栈操作：*s.top+=e;或*s.top=e; s.top+;退栈操作： e=*-s.top； 或 s.top-； e=*
9、s.top若定义：typedef struct SElemType baseMAXSIZE;int top;SqStack;SqStack s;top 的初始值为0 时:栈空条件： s. top =0 此时不能出栈栈满条件： s.top = MAXSIZE进栈操作： s.bases.top+=e;退栈操作： e=s.base-s.toptop 的初始值为-1 时:栈空条件： s. top = -1 此时不能出栈栈满条件： s.top = MAXSIZE-1进栈操作： s.base+s.top=e;退栈操作： e=s.bases.top-3. 栈的链式表示与实现 B （对比顺序栈，实质不带头结点
10、的链表在头指针处插入和删除）4. 队列的顺序表示与实现循环队列 A设两个指针：Q.front指向队列头元素；Q.rear指向队列尾元素的下一个位置 注意队中若Q.rear指向队列尾元素，进出队，实现语句有差别！ 初始状态（空队列）： Q.front = Q.rear=0队头指针进1: Q.front = （Q.front + 1）% MAXSIZE 队尾指针进1: Q.rear = （Q.rear + 1）% MAXSIZE;队列初始化：Q.front = Q.rear = 0;队空条件：Q.front = Q.rear;队满条件： （Q.rear + 1） % MAXSIZE = Q.fro
11、nt队列长度： （Q.rear-Q.front+MAXSIZE）%MAXSIZE6.队列的链式表示与实现B本章重点：顺序栈的初始条件、操作，循环队列的初始条件、操作 本章难点：栈的设计与使用，队列的设计与使用（主要结合后面树和图中的应用复习） 例5.链栈与顺序栈比起来优势在于。没有预设容量的限制例 6计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右 扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时， 要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符 的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2
12、的栈顶运算符进行运算将 结果放入栈S1中（得到的结果依次用Tl、T2等表示）。为方便比较，假设栈S2的初始栈 顶为 （运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。步骤栈S1栈S2输入的算术表达式（按字符读入）初始A-B*C/D+E/F1AA-B*C/D+E/F2A-B*C/D+E/F3AB-B*C/D+E/F4AB-*C/D+E/F5ABC-*C/D+E/F6AT1 （注：T1=B*C）-/D+E/F7AT1D-/D+E/F8AT2 （注：T2=T1/D）T3 （注：T3=A-T2）-+E/F9T3E+E/F10T
13、3E+/F11T3EF+/F12T3T4 （注：T4=E/F）T5（注：T5= T3+ T4）+例7.将两个栈存入数组Vl.m应如何安排最好？这时栈空、栈满的条件是什么？，入栈 和出栈的操作是什么？分析：为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时， 应将两栈的栈底分别设在内存空间的两端，这样只有当两栈顶指针相邻(即值之差的绝对值 为1 时才产生溢出。设栈S1和栈S2共享向量V1.m，初始时，栈S1的栈顶指针top0=0,栈S2的栈顶指针 top1=m+1,当 top0=0 为栈 S1 空，top1=m+1 为栈 S2 空；当 top0=0 并且 top1=m+1
14、时为两 栈全空。当 top1-top0=1 时为栈满。入栈核心操作 S1: V+top0=x1;S2: V-top1=x2出栈核心操作 S1: x1=Vtop0-;S2: x2=Vtop1+例8.如果用一个循环数组baseO.MAX-l表示队列时，该队列只有一个队列头指针front, 不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。(1) 编写实现队列的三个基本运算：判空、入队、出队(2) 队列中能容纳元素的最多个数是多少 typedef struct ElemType baseMAX;int front,count; /front 是指向队头元素针， count 是队列中元素个数。CQueue;/定义类型标识符。(1)判空：int Empty(CQueue q)/q是 CQueue 类型的变量if(q.count=0)return(1)；else return (0) ; /空队列入队: int EnQueue(CQueue q， ElemType x)if (q.count=MAX)printf( “队满n”)； exit(0); q.base(q.
