数据结构复习要点

a熟练掌握b理解c了解第一章：绪论1. 基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。c四类数据组织结构：集合、线性表、树形、图状结构c数据的存储方式：顺序存储和链式存储。b2. 算法和分析算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度b本章重点：分析算法时间复杂度例 1. 下面关于算法说法错误的是（）a. 算法最终必须由计算机程序实现b. 为解决某问题的算法同为该问题编写的程序含义是相同的c. 算法的可行性是指指令不能有二义性d.以上几个都是错误的d例 2. 以下那一个术语与数据的存储结构无关？（）a栈b. 哈希表c.线索树d.双向链表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-1);， merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为o(n) 。解：分析得到的时间复杂度的递归关系：t( n)o(1)2t(n / 2)n1o(n)n1o(n) 为 merge （）所需的时间，设为cn （c 为常量）。因此t( n)2( n / 2)cn2(2t (n / 22 )cn / 2)cn22 t( n / 22 )2cn.2k t(n / 2 k )kcnn令2k1 ，有 klog 2 nlog 2 n有 t( n)2o (1)cn log 2 nncn log 2 no(n log 2 n)第二章：线性表1. 线性表的基本运算：.c2. 线性表的顺序存储（利用静态数组或动态内存分配）。相应的表示与操作a3. 线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。a4. 顺序存储与链式存储的比较：基于时间的考虑- 分别适用于静态的和动态的操作：比如静态查找和插入删除） ；基于空间的考虑-.b这也适用于后面用两种方式存储的其他数据结构。本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。例 4 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 题目分析 因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。void union(linklist la, linklistlb)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;pa=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 还回原指向位置；这与我们原来不改变pa 或 pb 的指向，增加一个q=pa 或 pb 作为摘取结点进行添加操作起到的作用一样。（2） ） 此处要完成逆序插入操作故用头插法（基于头指针la 或 lb），注意尾插法（附设一个尾指针，基于该指针插入）的可完成顺序插入。（注意：逆序另一种方式也要掌握！）练习：练习题 2编程 1 67. 判断带头结点双向循环链表l 是否对称相等.8. 设计一个算法判断单链表（带头结点）是否是递增的（注意比排序算法应该简单，链表排序也要会实现）9. 设计一个算法判断有序表a 是否是有序表b 的子集（即表 a 中的元素在b 中）。（思考：如果递归程序怎么写？）第三章：栈与队列1. 两种特殊线性表：分别有后进先出、先进先出的特性。 b2. 栈的顺序表示与实现（利用静态数组或动态内存分配）a 注意栈顶指针的初始位置不同，进出栈，栈空栈满的实现语句有差别！ 举例：若定义typedef struct selemtype*base;selemtype*top;intstacksize;/ 当前栈能使用的最大容量 sqstack;sqstacks;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=*s.top若定义：typedef struct selemtypebasemaxsize; int top;sqstack;sqstacks;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(对比顺序栈，实质不带头结点的链表在头指针处插入和删除)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.front队列长度： (q.rear-q.front+maxsize)%maxsize6. 队列的链式表示与实现b本章重点 ：顺序栈的初始条件、操作，循环队列的初始条件、操作没有预设容量的限制例 6计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈s1 中，运算符放入栈s2 中，但每次扫描到运算符时，要把它同 s2 的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈s1 的栈顶和次栈顶的两个元素，以及栈s2 的栈顶运算符进行运算将结果放入栈s1 中（得到的结果依次用t1 、t2 等表示）。为方便比较，假设栈s2 的初始栈顶为 ? （ ? 运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式：a-b*c/d+e/f。写出栈s1 和 s2 的变化过程。步骤栈 s1栈 s2输入的算术表达式（按字符读入）初始?a-b*c/d+e/f?1a?a-b*c/d+e/f?2a? -b*c/d+e/f?3ab? -b*c/d+e/f?本章难点：栈的设计与使用，队列的设计与使用（主要结合后面树和图中的应用复习） 例 5 链栈与顺序栈比起来优势在于。4ab? -*c/d+e/f ?5abc? -*c/d+e/f ?6at1 （注： t1=b*c ）? -/d+e/f ?7at1d? -/d+e/f ?8at2（注： t2=t1/d ）t3 （注： t3=a-t2 ）? -? +e/f ?9t3e? +e/f ?10t3e? +/f?11t3ef? +/f?12t3t4 （注： t4=e/f ）? +?t5 （ 注： t5=t3+?t4 ）例 7 将两个栈存入数组 v1.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 时为两栈全空。当 top1-top0=1 时为栈满。入栈核心操作s1: v+top0=x1;s2:v-top1=x2出栈核心操作s1: x1=vtop0-;s2:x2=vtop1+例 8如果用一个循环数组base0.max-1表示队列时，该队列只有一个队列头指针front ， 不设队列尾指针rear ，而改置计数器count 用以记录队列中结点的个数。（ 1）编写实现队列的三个基本运算：判空、入队、出队（ 2）队列中能容纳元素的最多个数是多少typedefstruct elemtype basemax;int front,count;/front 是指向队头元素针，count 是队列中元素个数。cqueue;/ 定义类型标识符。(1) 判空： int empty(cqueueq)/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.front+q.count)%max=x;/x 入队q.count+;return (1);/ 队列中元素个数增加1, 入队成功。出队 : int delqueue(cqueue q, elemtype &x)if (q.count=0)printf(“队空n ”)； return (0);x=q.baseq.front;q.front=(q.front+1)%max;/计算新的队头指针q.count-;return (1);(2) 队列中能容纳的元素的个数为max 。第四章：串1. 串的基本概念c2. 串的顺序表示与实现（两种存储方式）a特别的模式匹配算法之kmp 算法b 本章重点：串的定长顺序存储和堆分配存储、掌握一些常规的串操作（自己会用和会编写） 本章难点：串的模式匹配快速算法（kmp ）例 9. 串的定长顺序存储缺点在于存在情况。截断例 10 已知 u= xyxyxyxxyxy； t=xxy ； assign （ s， u）；assign （ v， substr （ s， index （ s，t ），len （ t） +1 ） ；assign （ m ，ww ）求 replace （， m ）= 。xyxyxywwy 例 11 14 设字符串s= aabaabaabaac， p= aabaac（1 ）给出 s 和 p 的 next 值和 nextval值；（ 2 ）若 s 作主串， p 作模式串，试给出利用bf 算法和 kmp 算法的匹配过程。（ 1 ）（ 1） p 的 next 与 nextval值分别为012123 和 002003 。（ 2）利用 bf 算法的匹配过程： 第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaa(i=3,j=2)第三趟匹配：aabaabaabaaca(i=3,j=1)第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac利用 kmp 算法的匹配过程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6,nextval(j)=3)第二趟匹配：aabaabaabaac(aa)baac (i=9,j=6)第三趟匹配：aabaabaabaac(成功 ) (aa)baac(i=13,j=7)o(m* n)o( mn)例 12 一般串定位函数index(s,t,pos),设 s 的串长为n，t 的串长为m, 则最坏时间复杂度；而改进的index_kmp(s,t,pos)时间复杂度为。第五章：数组和广义表1. 数组的存储结构：以行为主序、以列为主序的地址映像函数b 2 矩阵的压缩存储：（1） ）特殊阵：包括对称阵、三角阵、带状阵（利用其特性压缩存储到一维数组）b（2） ）稀疏阵利用的是三元组顺序表来表示b用十字链表表示c（本次考试不做要求）3. 广义表定义与存储表示b （本次考试不做要求） 本章重点：地址映像函数的计算（包括数组和特殊矩阵）例 13 已知 n 阶下三角矩阵a（即当 ij 时，有 aij =0 ），按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组b 中，请写出从第一列开始采用列序为主序分配方式时在b 中确定元素a ij 的存放位置的公式。答： n 阶下三角矩阵元素aij （ 1=i,j=j）。第 1 列有 n 个元素，第j 列 有 n-j+1 个元素，第 1 列到第 j-1 列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而 a ij 在第 j 列上的位置是为 i-j+1 。所以 n 阶下三角矩阵a 按列存储，其元素a ij 在一维数组b 中的存储位置k 与 i 和j 的关系为：k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i第六章：二叉树与树1. 二叉树的定义和性质：b几个特殊的二叉树：满二叉树、完全二叉树、二叉排序树、平衡二叉树b2. 二叉树的顺序存储：c3. 二叉树的链式存储：用二叉链表表示与实现a4. 二叉树的遍历：先（中、后）序遍历及应用，相应递归算法和非递归算法a5. 线索化二叉树 （利用二叉链表n+1 空指针域来存放某遍历下指向该结点的直接前驱或直接后继，使得蕴含更多信息）b6. 二叉树的应用：算术表达式，霍夫曼树（最优二叉树），判定树b7. 树的定义和存储表示：.b8. 树和森林和二叉树的转换b9. 树与森林的遍历b本章重点：很熟悉二叉树（在二叉链表表示下）的基本操作的递归算法和遍历的非递归算法，请仔细复习。本章难点：二叉树（含排序树、平衡树）的递归算法和非递归算法。线索化二叉树及相应操作，重在理解，不考编程！例 14 引入二叉线索树的目的是（） a将非线性序列转化成某种线性序列；加快查找结点的前驱或后继的速度b为了能在二叉树中方便的进行插入与删除c为了能方便的找到双亲d 使二叉树的遍历结果唯一a例 15 二叉链表在线索化后，仍不能有效求解的问题是（）。 a前（先）序线索二叉树中求前（先）序后继b 中序线索二叉树中求中序后继c中序线索二叉树中求中序前驱d 后序线索二叉树中求后序后继d例 16 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为a, 并已知 a 的左孩子的平衡因子为-1 右孩子的平衡因子为0, 则应作 () 型调整以使其平衡。（平衡因子= 左子树深度 -右子树深度）a. ll（单向右旋）b. lr（先左后右双向旋转）c. rl（先右后左双向旋转）d. rr（单向左旋）b例 17 一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使前序序列与后序序列相反，图示如下：例 18 ： 已知二叉树结点结构如下： 用 c 语言表示typedef struct binodeelemtype data;struct binode *lchild,*rchild; int val;binode,*bitree;其中 val 域表示该结点的子孙（含孩子结点）的个数。开始时，val 域值均为 0 ，t 为指向某二叉树根结点的指针。请写算法填写该二叉树中每个结点的val 域。递归算法如下：int writeval(binode *root)if(root=null)root-val=0;else if(root-lchild=null&root-rchild=null) root-val=1;elseroot-val=writeval(root-lchild)+writeval(root-rchild); return root-val;例 19 编写一个算法，将指针s 所指的结点插入到根结点指针为t 的二叉排序树中，若已存在则不再插入返回0 ；否则返回1。（递归的算法见教材）int insert_bst( bitree &t, bitnode s ) bitreep, q;/p 指向当前访问的结点if(!t) t=s;else p=t;while ( p )q = p;/q 指向 p 结点的双亲结点if (s-data.key data.key)p = p-lchild; else if(s-data.key p-data.key) p = p-rchild;elsep=null;if (s-data.key = q-data.key)return 0;if (s-data.key data.key)q-lchild = s; else q-rchild = s;return 1;例 20 编写一个算法，计算平衡二叉树中所有结点的平衡因子解：计算一个结点bt 的 bf 的值递归模型如下：f(bt): bt-bf不存在当 bt=nullf(bt): bt-bf=0当 bt-lchild=null&bt-rchild=null f(bt): bt-bf=bt的右子树的高度左子树的高度其它情况可选用先序的方式统计出各个结点的平衡因子如何求高度呢？递归模型如下：f(bt):不存在当 bt=nullf(bt):当 bt-lchild=null&bt-rchild=null f(bt):bt 的左子树和右子树的高度的最大值其它情况int height(bstnode *bt)/求树的高度int max1,max2; if(bt=null) return 0;else if(bt-lchild=null&bt-rchild=null) return 1;elsemax1=height(bt-lchild); max2=height(bt-rchild);return max1max2?max1+1:max2+1;void countbf(bstnode *&bt) /求所有结点的bf if(bt!=null)if(bt-lchild=null&bt-rchild=null) bf-bf=0;elsecountbf(bt-lchild);countbf(bt-rchild);bt-bf= height(bt-rchild)-height(bt-lchild);实质上可以将上面求bf 和求高度合二为一。int countbf1(bstnode *&bt)/求所有结点的bf, 返回对应结点高度值int max1,max2;if(bt=null) return 0;if(bt-lchild=null&bt-rchild=null) bf-bf=0;return1;elsemax1=height(bt-lchild); max2=height(bt-rchild); bt-bf= max2-max1;return max1max2?max1+1:max2+1;例 21 设给出一段报文：castcastsatatatasa ；字符集合是 c, a, s, t ，各个字符出现的频度(次数 )是 w 2, 7, 4, 5 ；试设计赫夫曼编码，画出赫夫曼树。 若给每个字符以等长编码a : 00t : 10c : 01s : 11 ；试说明赫夫曼编码比此方案的优越之处。 (编码最短 )解答见 ppt练习1. 设计一个算法，删除该二叉树，释放所有结点2. 设计一算法判断二叉链表存储的二叉树是否结构对称（左右子树结点结构对称相同）3. 试写出复制一棵二叉树的算法。二叉树采用标准链接结构。4. 习题六编程（除打星号的部分）5. 设计一个算法， 寻找二叉树中满足特定数值x 的第一个结点 ( 相应的变形： 寻找最小值， 寻找父结点，寻找兄弟)6. 设计一个算法，统计二叉树中满足特定数值x 结点的个数（相应的变形：统计度为0 ，1， 2 的结点）第七章图1. 图的定义、基本概念：b2. 图的存储方式：邻接矩阵和邻接表a3. 图的遍历深度优先和广度优先a4. 图的连通性和生成树b带权图的最小生成树及算法b5. 图的最短路径问题b6. 拓扑排序、 aoe 网中的关键路径b本章重点： 熟悉邻接矩阵和邻接表的表示方法，学会编写遍历算法深度优先和广度优先遍历算法以及一些遍历算法的应用。请仔细复习。本章难点：图的一些算法（如最小生成树、最短路径、关键路径；这部分重在理解算法思想和设计过程）例 22 将邻接矩阵g 装换为邻接表g ( 邻接表的表示方法) void mattolist(mgragh g,alglink &g)int i,j, n=g.n;/n表 示 顶 点 数 arcnode *p; g=(algraph*)malloc(sizeof(algraph);for(i=0;iverticesi.data=g.vexsi; g-verticesi.firstedge=null;for(i=0;i=0;j-)/对第 i 个顶点进行建立链表（由后向前添加）if(g.edgesij!=0)p=(arcnode *)malloc(sizeof(arcnode);/新建结点p-adjvex=j;p-info=g.edgesij;/存放边的权值p-next=g-verticesi.firstedge;/前插g-verticesi.firstedge=p;g-n=n; g-e=g.e;例 23 试利用深度优先遍历dfs 判断该图（在邻接表存储下）是否是连通的，若是连通的返回，若是不连通的返回图的连通分量个数，空图则返回。(图的遍历 )int vistedmaxnum; /全局数组void dfs (algraph* g, int i)/*以 vi 为出发点对邻接表图进行dfs */ arcnode *p;printf(visit data:%dn,g-verticesi.data);/访问顶点vi visitedi=1;/标记 vi 已访问，标志为 p= g-verticesi.firstarc;/取 vi 边表的头指针while(p) / 依次搜索vi 的邻接点vj，if (!visitedp-adjvex) /若 vj 尚未访问，则以vj 为出发点向纵深搜索dfs (g,p-adjvex); p=p-next;/*判断无向图是否连通，若连通返回1*/ intconnects(algraph*g)int i,flag=1;/flag 为标记是否连通for (i=0;ivexnum;i+)visitedi=0 ;/标志向量visted 初始化，标志为dfs(g,0);for (i=0;ivexnum;i+)if (visitedi=0) / 还有 vi 未访问过，修改标记flag 量flag=0;break;return flag;例 24 下面是求连通网的最小生成树的prim 算法：集合vt，et 分别放顶点和边，初始为（ 1 ），下面步骤重复n-1 次: a：（ 2 ）； b：（ 3 ）；最后：（ 4 ）。（ 1） a vt ，et 为空b vt 为所有顶点， et 为空c vt 为网中任意一点，et 为空d vt 为空， et 为网中所有边（ 2） a.选 i 属于 vt ，j 不属于 vt ，且（ i， j）上的权最小 b 选 i 属于 vt ， j 不属于 vt ，且（ i，j）上的权最大 c 选 i 不属于 vt， j 不属于 vt，且（ i， j）上的权最小d 选 i 不属于 vt， j 不属于 vt，且（ i， j）上的权最大（ 3） a 顶点 i 加入 vt ，（ i,j）加入 etb.顶点 j 加入 vt ，（ i,j）加入 etc.顶点 j 加入 vt ，（ i,j ）从 et 中删去d 顶点 i,j 加入 vt ，（ i,j）加入 et（ 4）a et中为最小生成树b不在 et 中的边构成最小生成树c et 中有 n-1 条边时为生成树，否则无解d et 中无回路时，为生成树，否则无解c a b a例 25 p182算法7.12 （思考：用邻接矩阵存储怎么实现？）练习1. 假设有向图以邻接表存储，计算vi 顶点的出度和入度。2. 在有向无环图中，试利用深度优先遍历dfs 求出一个拓扑排序序列。提示：由某点出发进行深度优先遍历，退出dfs 函数调用时记录此时顶点序号，最先退出dfs函数的顶点是拓扑序列中的最后一个顶点，依次下去.得到一个逆向拓扑有序序列；再将此顶点序号反向输出即可。3. 设计一个深度优先搜索算法，以判断用邻接表方式存储的有向图中是否存在由顶点vi 到顶点 vj（ ij ）的路径。第八章查找基本概念c静态查找表中常用的方法：顺序查找、折半查找、分块查找（分别适用于一般、有序、分块有序的表）相应算法和性能分析a动态查找表：二叉排序树的建立、查找、删除；a二叉平衡树 哈希表：哈希函数的构造和冲突处理方法本章重点：查找树的建立和查找（含静态折半查找、动态查找树）、哈希函数和冲突方法本章难点：二叉排序树删除；平衡排序树的插入例 26 在有序表a1.12 中，采用二分查找算法查等于a12 的元素，所比较的元素下标依次为 。6,9,11,12例 27 设散列表为ht0.12, 即表的大小为m=13 。现采用双散列法解决冲突。散列函数和再散列函数分别为：h 0(key)=key % 13;注:% 是求余数运算(=mod)h i=(h i-1 +rev(key+1)%11+1) % 13;i=1,2,3,m-1其中，函数rev （ x）表示颠倒10 进制数 x 的各位，如rev （ 37 ）=73 ，rev （ 7）=7 等。若插入的关键