理学数据结构PPTPPT学习教案

1、会计学1理学数据结构理学数据结构PPT2第1页/共86页3第2页/共86页4集合名集合名 指针指针0 S11 S22 S30427681935第3页/共86页5n一个集合中一个集合中,可用可用 Union(S, i, j)将它们合并到一个集合中。将它们合并到一个集合中。第4页/共86页6parent集合集合 和和 的双亲表的双亲表示示- -4 4 - -3 2 - -3 2 0 0 0 40 1 2 3 4 5 6 7 8 90768419235第5页/共86页7 parent集合集合 和和 的双亲表的双亲表示示- -7 4 - -3 2 0 2 0 0 0 40 1 2 3 4 5 6 7

2、8 907684194190876第6页/共86页8并查集的结构定义并查集的结构定义const int SetSize = 50; /并查集元素个数typedef struct /并查集结构定义 int parentSetSize; /集合元素数组 UFSets;void InitUFSets (UFSets *S) /集合初始化 for ( int i = 0; i parenti = -1; /每一个自成一个单元素集合第7页/共86页950123Find (S,4)Find (S,3) = 3 Find (S,2) =2 Find (S,1) = 1Find (S,0) = 0 = - -

3、5 parent x parent x ); -5 0 1 2 35 0 1 2 3Parent4 =3 Parent3 =2Parent2 =1Parent1 =0Parent0 =-50 1 2 3 4第9页/共86页11n n 成的森林，成的森林，S-parenti = - -1。做处理做处理Union(n- -2, n- -1), ,Union(1, 2), Union(0, 1)后，将后，将产生退化的树。产生退化的树。第10页/共86页1211111350313322Union(0,1)23412Union(1,2)Union(2,3)Union(3,4)第11页/共86页13nin

4、i12OO)()(第12页/共86页14111111107252223323302Union(2, 0)第13页/共86页15void WeightedUnion (UFSets *S, int Rt1, int Rt2 ) 按Union的加权规则改进的算法 int temp = S-parentRt1 + S-parentRt2; if ( S-parentRt2 parentRt1 ) S-parentRt1 = Rt2; /Root2中结点多 S-parentRt2 = temp; /Root1指向Root2 else S-parentRt2 = Rt1; /Root1中结点多 S-pa

5、rentRt1 = temp; /Root2指向Root1 第14页/共86页16000000002221223323302Union(2, 0)第15页/共86页170067867819193535从 i = 5 压缩路径第16页/共86页18int CollapsingFind (UFSets *S, int i ) /使用折叠规则的搜索算法 int j = i; while ( S-parentj = 0 ) j = S-parentj; /让 j 循双亲指针走到根 while ( i != j ) /换 parenti 到 j int temp = S-parenti; S-paren

6、ti = j; i = temp; return j;第17页/共86页19第18页/共86页20第19页/共86页21第20页/共86页22#define MaxSize 100 /搜索表最大尺寸typedef int DataType; /搜索数据的类型 typedef struct /搜索表结点定义 DataType key; /关键码域 other; /其他数据域 ListNode;typedef struct dataList /搜索表结点定义 ListNode dataMaxSize; /数据存储数组 int n; /数组当前长度第21页/共86页23n另外衡量一个搜索算法还要考另

7、外衡量一个搜索算法还要考虑算法所需要的存储量和算法虑算法所需要的存储量和算法的复杂性等问题。的复杂性等问题。第22页/共86页24n关键码与关键码与x相等的对象相等的对象, 则搜索则搜索失败。给出失败信息。失败。给出失败信息。第23页/共86页25int LinearSearch ( dataList A, DataType x ) /在数据表A.data1.n中顺序搜索关键码为 x/的数据对象, A.data0.key 作为控制搜索自动/结束的“监视哨”使用 A.data0.key = x; int i = A.n; /将x送0号位置设置监视哨 while ( A.datai.key !=

8、x ) i- ; /从后向前顺序搜索 return i;第24页/共86页26 1010niiniiisuccpcpASL) 1 ( .)(11inpASLniisucc第25页/共86页27.)()(nisuccnnnninnASL12121111第26页/共86页28int SequentSearch ( dataList A, dataType x, int& loc ) /在数据表 A.data0.n- -1 中搜索其关键码与/给定值匹配的对象, 函数返回其表中位置。/参数 loc 是在表中开始搜索位置 if ( loc = A.n ) return -1; /搜索失败 else if

9、 ( A.dataloc.key = x ) return loc; /搜索成功 else return SequentSearch ( A, x, loc+1 ); /递归搜索第27页/共86页29int SequentSearch ( dataList A, DataType x ) /在数据表 A.data0.n- -1 中顺序搜索关键码为 x 的数据对象 for ( int i = 0; i x ) break; return -1; /顺序搜索失败, 返回失败信息第28页/共86页301050602030402716150isucciASL727617150iunsucciASL第2

10、9页/共86页31象，仍未找到想要搜索的对象，象，仍未找到想要搜索的对象，则搜索失败。则搜索失败。第30页/共86页32搜索成功的例子搜索成功的例子- -1 0 1 3 4 6 8 10 1260 1 2 3 4 5 6 7 8lowmidhigh6 6 8 10 125 6 7 8low midhigh665low mid high6第31页/共86页33搜索失败的例子搜索失败的例子- -1 0 1 3 4 6 8 10 1250 1 2 3 4 5 6 7 8lowmidhigh5 6 8 10 125 6 7 8low midhigh655low mid high5第32页/共86页34

11、int BinarySearch ( dataList A, DataType x, int low, int high ) int mid = -1; if ( low = high ) mid = ( low + high ) / 2; if ( A.datamid.key x )mid = BinarySearch ( A, x, low, mid -1 ); return mid;第33页/共86页35int BinarySearch ( dataList A, DataType x ) int high = A.n-1, low = 0, mid; while ( low = hig

12、h ) mid = ( low + high ) / 2; if ( A.datamid.key x ) high = mid - 1; /左缩搜索区间 else return mid; /搜索成功 return -1; /搜索失败第34页/共86页36105030204060ASLunsucc = (2*1+3*6)/7 = 20/7 ASLsucc = (1+2*2+ 3*3)/6 = 14/6 第35页/共86页37即即pi= 1/n，则搜索成功的平均，则搜索成功的平均搜索长度为搜索长度为第36页/共86页38)221)(23 2211111221101hhniin0iiisucchh

13、(nCnCpASL121)(221)( 2322111221hhhhhh11)(log11)(log1 )1)(1)log(11)21)(1 222nnnnnnnnhnASLhsucc第37页/共86页39定义定义 第38页/共86页40351545504025102030第39页/共86页4151*2*34*5*6*41C13133*2122133132123123123 132 213 231 312 321第40页/共86页42typedef char DataType; /树结点数据类型typedef struct node /搜索树结点定义 DataType data; struct

14、 node *leftChild, *rightChild; BstNode;typedef BstNode *BST; /二叉搜索树定义第41页/共86页43351545504025102030第42页/共86页44第43页/共86页4535154550251020302245第44页/共86页46BstNode * Find ( BstNode *ptr, DataType x ) /二叉搜索树的迭代的搜索算法 if ( ptr != NULL ) BstNode * p = ptr; /从根搜索 while ( p != NULL ) if ( p-data = x ) return p

15、; if ( p-data rightChild; /右子树 else p = p-leftChild; /左子树 return NULL; /搜索失败 第45页/共86页4735154550402510203028插入新结点插入新结点28第46页/共86页48void Insert ( DataType x, BstNode * & ptr) /将新元素x插到以*ptr为根的二叉搜索树中第47页/共86页49 if ( ptr = NULL ) /空二叉树 ptr = new BstNode; /创建结点 if ( ptr = NULL ) cout “存储不足 data = x; ptr-

16、leftChild = ptr-rightChild = NULL; else if ( x data ) /在左子树插入 Insert ( x, ptr-leftChild ); else if ( x ptr-data ) /在右子树插入 Insert ( x, ptr-rightChild );第48页/共86页50 535378537865537865175378658717537865091787537865811787095378651517870981第49页/共86页51void CreateBST ( BstNode *& T, DataType Refvalue ) 输入数

17、据, 建立二叉搜索树。RefValue 是输入/结束标志。这个值应取不可能在输入序列中/出现的值, 例如输入序列的值都是正整数时, /取RefValue为0或负数。 dataType x; T = NULL; cin x; while ( x != RefValue ) if ( Find (T, x) = NULL ) Insert ( x, T ); cin x; 第50页/共86页52123111132223323第51页/共86页53n结点顶替它的位置，再释放它。结点顶替它的位置，再释放它。第52页/共86页545378651787092345删除45缺右子树, 用左子女顶替53786

18、517870923第53页/共86页558853788817940923删除78缺左子树, 用右子女顶替53948817092353788117940945删除78在右子树上找中序下第一个结点填补2365538188179409452365第54页/共86页56 n增加了外部结点的二叉搜索树增加了外部结点的二叉搜索树称为扩充二叉搜索树。称为扩充二叉搜索树。Cnnn211第55页/共86页57第56页/共86页58doiftodoiftoq0q1p1q2p2q3p3q0q1q2q3p1p2p3(a)(b)第57页/共86页59doiftoq0q1p1q2p2q3p3doiftoq0q1p1q2p

19、2q3p3(d)(c)doiftoq0q1p1q2p2q3p3(e)第58页/共86页60).(*1p1i liASLnisuccnjunsuccjljASL0q. *第59页/共86页61第60页/共86页62第61页/共86页63.nisucciASL121log.1nniunsucciASL212log第62页/共86页64doiftodoiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05q0=0.15q1=0.1q2=0.05q3= 0.05p1=0.5p2=0.1p3=0.05(a)(b)第63页/共86页65doifto q0=0.

20、15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(d)(c)图图(b) :ASL = 1.9; 图图(d) :ASL = 2.15;第64页/共86页66doiftoq0=0.15q1=0.1p1=0.5q2=0.05p2=0.1q3=0.05p3=0.05(e)第65页/共86页67 ABCABCDEDE第66页/共86页68, n 可保持在可保持在O(log2n),平均搜索长平均搜索长度也可保持在度也可保持在O(log2n)。第67页/共86页69typedef int DataType; /结点数据类型typedef struct node /AVL树结点定义 DataType data; /结点数据域 int balance; /结点平衡因子域 struct node *leftChild, *rightChild; /结点左、右子女指针域结点左、右子女指针域 AVLNode;typedef AVLNode * AVLTree; /AVL树第68页/共86页70根的路径回溯根的路径