03-查找与序.ppt

江苏大学多媒体教学课件计算机软件技术基础;第一节 查找;特点： 1）可以采用从前向后查，也可采用从后向前查的方法； 2）在平均情况下，大约要与表中一半以上元素进行比较，效率较低，平均查找长度较大； 3）在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。;数据结构： struct STable { int key; DataType info; };（b） K=80;查找成功时的平均查找次数为: ASL=(1+2+3+4+……+n)/n=(n+1)/2 查找不成功时的比较次数为：n+1 优点：算法简单，无需排序，采用顺序和链式存储均可。 缺点：平均查找长度较大。;struct node { int data; struct node *next; }; strcut node *Searcb (struct node *head, int x) { struct node *m; m=head; while (( m != NULL) (m-data != x)) m=m-next; return(m); };　　基本思想：对有序文件，进行查找，先找“中间记录”，进行比较，根据不同情况，逐步缩小范围，直到找到或确认找不到该记录为止。 　　适用条件：必须在具有顺序存储结构的有序表中进行。;查找23和79的过程如下图：; int Search ( struct STable T[ ], int n, int key) { int low, high, mid; low=1; high=n; while( low = high ) { mid=( low+high )/2; if (T[mid].key == key) return( mid ); /* 成功 */ else if ( key T[mid].key ) high=mid-1; /*向前查找*/ else low = mid+1; /*向后查找*/ } return (0); /*不成功*/ }; 是顺序查找的一种改进方法，就是把被查找的表分成若干块，每块中记录的存放顺序是无序的，但块与块之间必须按关键字有序。即第一块中任一记录的关键字都小于第二块中任一记录的关键字，而第二块中任一记录的关键字都小于第三块中任一记录的关键字，依此类推。 该法要为被查找的表建立一个索引表，索引表中的一项对应于表中的一块，索引表中含有这一块中的最大关键字和指向块内第一个记录位置的指针，索引表中各项关键字有序。;索引表;查找方法比较;四、二叉排序树查找;2. 二叉排序树;3. 二叉排序树的生成;10;二叉排序树插入算法： struct TreeNode *InsertBT(struct TreeNode *t, int b) { if ( t == NULL ) { t = (struct TreeNode?)malloc(sizeof((struct TreeNode)); t-data = b; } else if (bt-data) t-Lchild = InsertBT(t-Lchild, b); else t-Rchild = InsertBT(t-Rchild, b); return (t) ; };4.删除二叉排序树上的结点;void DeleteBT(struct TreeNode *t, *p, *f ) { int fag = 0; struct TreeNode *s; /*fag是删除成功标志*/ if (p-Lchild == NULL) s = p-Rchild; /*p只有右子树*/ else if ( p-Rchild == NULL) s = p-Lchild; /*p只有左子树*/ else { q = p; s = p-Lchild; /*左右子树都非空*/