数据结构重修辅导.ppt

1、数据结构重修辅导,主讲人：郭世懿,设单链表L是一个递增有序表，试写一个算法将x插入其中后，仍保持L的有序性。,Void LinkListInsert(LinkedList L,int x) q=L; p=q-next; while(p!=Null) ,例 递归的执行情况分析,递归过程及其实现 递归：函数直接或间接的调用自身叫 实现：建立递归工作栈,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); printf(“/n”); ,运行结果： 1， 2，2， 3，3，3，,队空： Q.f

2、ront =Q. rear 队满： Q.front =(Q.rear + 1) % maxSize 入队: Q.rear = (Q.rear + 1) % maxSize 出队: Q.front = (front + 1) % maxSize; 求队长: (Q.rear-Q.front+maxSize)%maxSize,循环队列,【例】设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？,答：用队列长度计算公式： (Q.rear-Q.front+maxSi

3、ze)%maxSize L=（401911）% 40=8 L=（401119）% 40=32,int Test() /判别输入的字符串是否回文序列,是返回1,否返回0 Stack S;Queue Q ;char a,b; InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK; ,1、试写一个算法判别读入的一个以为结束符的字符序列是否是“回

4、文”。,二叉树的存储结构 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点：1、结点间关系蕴含在其存储位置中 2、浪费空间，只适于存满二叉树和完全二叉树,假设一棵二叉树的后序遍历序列为 D G J H E B I F C A，中序遍历序列为 D B G E H J A C I F，画出这棵二叉树,并转换为森林.,树的存储结构 1、双亲表示法(父指针表示法),-1,1,2,2,3,5,5,5,1,0号单元不用或 存结点个数,孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和右边下一个兄弟结点 特点 操

5、作容易 破坏了树的层次,将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,可利用二叉树设计前缀编码：

6、,某通讯系统只使用8种字符a、b、c、d、e、f、g、h，其使用频率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，利用二叉树设计一种不等长编码： 1）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树； 2）将该二叉树所有左分枝标记0，所有右分枝标记1； 3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；,a: 0001 b: 10 c: 1110 d: 1111 e: 110 f: 01 g: 0000 h: 001,构造以字符使用频率 作为权值的哈夫曼树,0.05, 0.29, 0.07, 0.08, 0.14, 0.23

7、, 0.03, 0.11,例：考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。现把9个数1，2，3，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。,线性探查法解决冲突的散列表如图9-11所示，,从图9-11可以得到线性探查法的成功平均查找长度为： ASL=（1+1+2+1+3+2+1+8）/8=2.375； 不成功：（7+6+5+4+3+2+1+8）/11=36/11,11，78，10，1，3，2，4，21,散列函数H(k)=k%11,0 1 2 3 4 5 6 7 8 9 10,拉链法解决冲突的散列表,从图

8、9-12可以得到拉链法的成功平均查找长度为： ASL=(1*6+2*2)/8=1.25。,图9-12 拉链法的散列表,不成功：(1+2+1+1+1+2)/11=8/11,G2 图示,有序对 ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向 边或弧；,G2= V2=v0 v1,v2,v3 E2= , , ,图的基本概念,1 图的邻接矩阵表示,在邻接矩阵表示中，包括一个顺序存储顶点信息的顶点表，和一个存储顶点之间关系的关系矩阵组成。,G的邻接矩阵是满足如下条件的n阶矩阵：,Ai,j=,1 若（i,j）E(G)或i,jE(G) 0 其它情形,例,2 有向图的邻接表和逆邻接表 1）有向图的邻

9、接表 顶点：用一维数组存储（按编号顺序） 以同一顶点为起点的弧：用线性链表存储,类似于无向图的邻接表， 所不同的是： 以同一顶点为起点的弧： 用线性链表存储,例,2）有向图的逆邻接表 顶点：用一维数组存储（按编号顺序） 以同一顶点为终点的弧：用线性链表存储,类似于有向图的邻接表， 所不同的是： 以同一顶点为终点弧： 用线性链表存储,例,已知图G=(V，E)，V=V1，V2，V3，V4，V5，V6，E=，试给出画出此图的邻接矩阵；画出此图的邻接表；画出此图的逆邻接表。,普里姆算法,1 普里姆(prim)算法思想, 普鲁姆算法基本步骤 设G=（V，E）为一个具有n个顶点的带权的连通网络， T=（U