计算机软件技术基础

2.5查找

查找就是在数据结构中找出满足某种条件的数据元素。若在数据结构中找到了这样的元素，则称查找成功，否则称查找失败。2.5.1线性查找法1.顺序查找法其查找过程为：从表的第一个元素开始，将给定的值与表中各元素的关键字逐个进行比较，一直到找到相等的关键字，则查找成功；否则就是表中没有要找的元素，查找失败。

seqsrch(inta[],intn,intk){inti=0；

while(a[i]!=k&&i<n)i++;if(i<n)return(i);elsereturn(-1);}链表的查找：#include<stdio.h>structnode{intdata;structnode*link;}head;structnode*seqe(struct*head,intv){for(;head!=NULL&&head->data!=v;)head=head->link;return(head);}2.对半查找法：只适用于有序线性表以顺序方式存放的有序表的查找可采用对半查找。将被查关键字k与线性表中间位置m上的数据元素的关键字进行比较：（1）若k==a[m]，则查找成功，过程结束。（2）若k>a[m],则取表的后半部分作为新表再去查找。（3）若k<a[m],则取表的前半部分作为新表再进行查找。这个过程一直进行到查找成功或子表的长度为0为止。

binsrch(inta[],intn,intk){intl,h,m;l=0;h=n-1;while(l<=h){m=(l+h)/2;if(a[m]==k)return(m);elseif(a[m]<k)l=m+1;elseh=m-1;}return(-1);}二分查找法要比顺序查找法快得多！3.分块查找(又称索引顺序查找）“分块有序”表

(1)表中数据分块(2)每块中的数据不必有序(需知最大关键字)(3)块之间有序“分块有序”表的结构有两部分：

(1)顺序存储结构的线性表(2)索引表分块查找过程：

(1)用对半查找法查找索引表，确定待查项x所在的块。

(2)在相应的块中用顺序查找法查找待查项x。2.5.2二叉排序树及其查找对半查找是基于关键字比较的最优方法。但如果在查找失败时，想把待查关键字k所对应的元素插入到表中，或者在查找成功时，想把所查到的元素从表中删除，对半查找就不太合适，因为它要化费大量的时间来移动有序表中的元素，以达到插入、删除的目的。二叉排序树定义：它或是一棵空树，或具有如下性质：（1）若它的左子树不空，则左子树上所有的关键字均小于它的根结点的关键字；（2）若它的右子树不空，则右子树上所有的关键字均大于或等于它的根结点的关键字；（3）它的左、右子树也是二叉排序树。

如果按中序遍历二叉排序树，那未就得到一个排好序的结点序列。10,17，18，20，40，50二叉排序树的查找算法在给定的二叉排序树t中查找给定待查关键字K：1.如果树t为空，那么查找失败。算法结束；否则，转2。2.如果t->data等于K，则查找成功。算法结束。否则转3。3.如果K<t->data，那么t=t->lchild，转（1）。

否则t=t->rchild，转（1）。递归算法structbnode{intdata;structbnode*lchild;structbnode*rchild;}structbnode*bansrch1(intk，structbnode*t){if(t==NULL)return(NULL);elseif(t->data==k)return(t);elseif(t->data>k)return(k,bansrch1(t->lchild));elsereturn(bansrch1(k,t->rchild));}非递归算法structbnode{intdata;structbnode*lchild;structbnode*rchild;}structbnode*bansrch2(intk，structbnode*t){structbnode*p;p=t;while((p!=NULL)&&(p->data!=k)){if(p->data>k)p=p->lchild;elsep=p->rchile;}return(p);}二叉排序树的插入过程

若二叉排序树为空，则插入结点应为新的根结点，否则根据关键字比较的结果确定是在左子树还是在右子树中继续查找，直至某个结点的左子树或右子树空为止，则插入结点应为该结点的左孩子或右孩子。1.递归算法insbtree(intk,structbnode**t){if(*t==NULL){structbnode*p;p=(structbnode*)malloc(sizeof(structbnode));p->lchild=NULL;p->rchild=NULL;p->data=k;*t=p;}elseif((*t)->data>k)insbtree(&(*t)->lchild,k);elseinsbtree(&(*t)->rchild,k);}2.非递归算法structbnode*insbtree(intk,structbnode*t){structbnode*p,*q;q=(structbnode*)malloc(sizeof(structbnode));q->lchild=q->rchild=NULL;q->data=k;if(t==NULL){t=q;return(t);}p=t;while((p->lchild!=q)&&(p->rchild!=q)){if(k<p->data){if(p->lchild!=NULL)p=p->lchild;elsep->lchild=q;}/*插入到左子树*/

else{if(p->rchild!=NULL)p=p->rchild;elsep->rchild=q;}/*插入到右子树*/}

return(t);}

二叉排序树的构造就是从空树出发，依次输入表中的元素作为结点，逐个插入二叉排序树的过程。

如果给定一个数据元素的集合，则数据元素的读入顺序不同，其构造出的二叉排序树的形态也不同。例.序列(53,61,12,37,90,100,3,78,45)，(61,37,90,45,100,78,12,3,53),(3,12,37,45,53,61,78,90,100)构造的二叉排序树分别为图1，图2和图3。531261337904578100613790124535378100图1图2312374553617890100图3删除结点的算法：1.首先调用search（），从而确定被删结点在树中的位置。2.如果被删结点不在树中，则算法结束。3.如果被删结点在树中。则进行下面的删除：(i)如果被删结点是根结点，那么(a)若被删点无左子结点,则用被删结点的右子树作为删除后的树。(b)若被删点有左子结点,则用被删结点的左子结点为根结点，同时把被删结点的右子树作为被删结点的左子树按中序最后一个结点的右子树。(ii)如果被删结点是不是根结点，那么(a)若被删结点无左子树，则(1)如果被删结点是它的父结点的左子结点，那么把被删结点的右子树作为被删结点的父结点的左子树。(2)如果被删结点是它的父结点的右子结点，那么把被删结点的右子树作为被删结点的父结点的右子树。(b)若被删点有左结点，则把被删结点的右子树作为删结点的左子树按中序最后一个结点的右子树。同时进行（1）如果被删结点是它的父结点的左子结点，那么把被删结点的左子树作为被删结点的父结点的左子树。（2）如果被删结点是它的父结点的右子结点，那么把被删结点的左子树作为被删结点的父结点的右子树。（iii)回收被删结点的存储单元，算法结束。以上的删除算法并不是唯一的，可以采用其它算法，只要在删除结点后，使得树仍然是一棵查找树就行。

删除结点算法

structbnode*destree(structbnode*t,structbnode*p,structbnode*f){structbnode*s,*q;if(p->l==NULL)/*被删结点p没有左子树*/{if(p==t)t=p->r;elses=p->r;}elseif(p->r==NULL)/*被删结点p没有右子树*/{if(p==t)t=p->l;elses=p->l;}else/*被删结点p有左、右子树*/{q=p；/*找左子树中的极右结点代替删去结点的位置*/s=q->l;while(s->r!=NULL){q=s;s=s->r;}s->r=p->r;

if(q!=p){q->r=s->l;s->l=p->l;}if(p==t)t=s;}if(p!=t){if(p==f->l)f->l=s;elsef->r=s;}free(p);return(t);}

注：t——

指向根结点指针

f——

指向被删除结点的双亲结点的指针

p——

指向被删结点的指针2.6排序

就是将一个数据元素的无序序列，按其关键字的大小重新排列，最后变成一个有序序列。内部排序：整个排序过程都在计算机内存中进行。外部排序：排序过程必须借助外存储器进行。2.6.1选择排序基本思想：每一趟在n-i-1个记录中选出关键字最小的记录作为有序序列的第i个记录。1.直接选择排序

基本方法是：每次从待排序的文件中，选出关键字最小的(或最大的)记录，放在已排序的记录的后面，直到全部排好序为止。

具体操作为：先在待排序文件中选出关键字最小的记录，把它与第一个记录交换存储位置，然后在余下的记录中再选出关键字次最小的记录与第二个记录交换，重复此过程，直至所有记录为有序序列为止。初始状态

4521341952603424

第一趟[19]21344552603424

第二趟[1921]344552603424

第三趟[192124]4552603434

第四趟[19212434]52604534

第五趟[1921243434]604552

第六趟[192124343445]6052

第七趟[19212434344552]60

有序文件1921243434455260具体算法描述如下:selsort(inta[],intn){inti,j,k,x;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(a[j]<a[k])k=j;if(k!=i){x=a[i];a[i]=a[k];a[k]=x;}}}2.堆排序

堆排序是对选择排序的改进。

基本思想：当用n-1次比较选择出最小的一个关键字后，在余下的关键字选择中，若能利用前面己进行的比较所得的有用信息，则可以减少关键字的比较次数。堆：对于树T中的任一结点的值不大于它的左子结点的值，且不大于它的右子结点的值，那么称树T是一个堆。即对任意i，若R2i+1,R2i+2

存在，并且满足

Ki<=K2i+1Ki<=K2i+2i=0,1,2…[n/2]则称之为堆。

从定义可以看出，堆顶记录的关键字K0，必是所有记录中关键字最小的一个。则从根结点开始，从上到下，从左到右，对顺序二叉树进行遍历，所得结点序列就是一个从小到大的序列。这样的处理过程为堆排序。堆的输出：先输出堆顶记录之后，用堆中最后一个记录代替。如下图(A)所示，此时根结点的左、右子树均为堆。比较左、右子树的根结点，由于右子树的根结点的值小，交换根结点和右子树根结点的值，如下图(B)所示的状态。对右子树重复上述过程，直至叶子结点。这时便建成了一个新堆，如下图(C)所示。(A)(B)(C)堆{5,20,10,40,30,50,25,60}形成的顺序二叉树。堆排序的基本思想是：将一组待排序的关键字，按堆的定义排成一个序列，这就找到了最小关键字。然后将最小关键字取出，用余下的关键字再建堆，便得到了次最小的关键字。如此反复，直到将全部关键字排好序为止。

从堆顶至叶子的调整过程称为筛选。一般地，如果以a[s+1],a[s+2],a[s+3],…a[t]为根的子树都是堆，则将a[s]筛选到合适位置，使得以a[s],a[s+1],a[s+2],a[s+3],…a[t]为根的子树都是堆。堆的筛选算法：soft(inta[],ints,intt){inti=s,j=2*i+1,k=a[i];while(j<=t){if(j<t&&a[j]>a[j+1])j++;/*j为两叶子结点中小结点的下标*/

if(k>a[j]){a[i]=a[j];i=j;j=2*i+1;}/*如果根大于叶子结点，则交换*/elsej=t+1;/**/}a[i]=k;}

建堆过程：对一棵顺序二叉树，各叶子结点没有孩子，它们自然符合堆的定义。对具有n个结点的顺序二叉树来说，最后一个非终端结点是第[n/2]个记录。我们从第[n/2]个记录起开始筛选，直到第1个记录止，则a[n]就是一个堆。

heepsort(inta[],intn){inti,k;for(i=n/2;i>=0;i--)soft(a,i,n-1);/*将a[0..n-1]建成一个堆*/for(i=n-1;i>0;i--){k=a[i];a[i]=a[0];a[0]=k;/*将堆顶和未排序子序列a[0..i-1]中最后一个记录相交换*/soft(a,0,i-1);}/*将a[0..i-1]重新调整为堆*/for(i=0;i<n/2;i++)/*建的堆是从大到小排序，再交换*/{k=a[i];a[i]=a[n-1-i];a[n-1-i]=k;}}例：有序列a(15,17,33,22,51,41,90,28,67)利用堆排序过程。首先将序列a建成堆：a(15,17,33,22,51,41,90,28,67)第8次：a[0]与a[8]交换为：a(67,17,33,22,51,41,90,28,15)

再建堆为：a(17,22,33,28,51,41,90,67,15)第7次：a[0]与a[7]交换为：a(67,22,33,28,51,41,90,17,15)

再建堆为：a(22,28,33,67,51,41,90,17,15)第6次：a[0]与a[6]交换为：a(90,28,33,67,51,41,22,17,15)

再建堆为：a(28,51,33,67,90,41,22,17,15)第5次:堆为：a(33,51,41,67,90,28,22,17,15)第4次:堆为：a(41,51,90,67,33,28,22,17,15)第3次:堆为:a(51,67,90,41,33,28,22,17,15)第2次:堆为:a(67,90,51,41,33,28,22,17,15)第1次:堆为:a(90,67,51,41,33,28,22,17,15)最后交换得:a(15,17,22,28,33,41,51,67,90)2.6.2交换排序基本方法：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对，直至全部满足为止。1.冒泡排序将待排序文件中的记录两两比较，若为逆序，则进行交换。按此方法将文件从头到尾处理一遍称作一趟起泡。一趟起泡的结果是将关键字最大的记录交换到了表尾。对余下n-1个记录，重复此过程，直至文件排好序为止。若某一趟起泡过程中没有任何交换发生，则表明此时文件已经排好序了，不必再继续重复起泡过程。初始状态[4521341952603424]第一趟[21341945523424]60第二趟[211934453424]5260第三趟[1921343424]455260第四趟[19213424]34455260第五趟[192124]3434455260第六趟1921243434455260具体算法：bubsort(inta[],intn){inti,j,k,s;k=1;j=n-1;while(k==1&&j>=0){k=0;for(i=0;i<j;i++)if(a[i]>a[i+1]){k=1;s=a[i];a[i]=a[i+1];a[i+1]=s;}j--;}}开关量K的作用是当其趟无交换时，即终止程序的运算。2.快速排序

基本思想:通过一趟分割将线性表分成两部分，其中前一部分的所有元素值均不大于后一部分中的每一元素值；然后对每一部分再进行分割，直到整个线性表有序为止。具体算法：设置两个指针i和j，其初始状态分别指向文件中第一个记录和最后一个记录。先将第一个记录移向辅助变量x中，然后从j所指位置起向前搜索第一个关键字小于x的记录，找到后，将a[j]移至a[i]的位置；再从i所指向的位置后搜索第一个关键字大于x的记录，找到后，将a[i]移至a[j]的位置；重复这两步过程，直至i==j，最后将x送至a[i]中去。至此一趟排序完成，文件划分为两个子文件。初始状态4521341952603424

i

j一次交换2421341952603424

i→

j二次交换2421341952603452

i

←j三次交换242134193460

3452

i→

j[2421341934]45[6052]

ij(a)一趟排序初始状态[4521341952603424]第一趟[2421341934]45[6052]第二趟[1921]24[3434]第三趟1921第四趟3434第五趟5260有序文件1921243434455260(b)全部快速排序一趟快速排序算法：inti,j;qkpass(ints,intt,inta[]){intx,i,j;i=s;j=t;x=a[i];do{while(i<j&&a[j]>=x)j--;/*自右向左扫描*/if(i<j){a[i]=a[j];i++;}while(i<j&&a[i]<=x)i++;/*自左向右扫描*/

if(i<j){a[j]=a[i];j--;}}while(i!=j);a[i]=x;returni;}递归算法qksort(inta[],ints,intt){inti;if(s<t){i=qkpass(s,t,a);qksort(a,s,i-1);qksort(a,i+1,t);}}非递归算法:qksort1(inta[],intn){intl=0,p=n-1;top=-1;push(s,l,p);while(top!=-1){pop(s,&l,&p);while(l<p){qkone(a,l,p);push(s,i+1,p);p=i-1;}}}2.6.3归并排序前面介绍的几种排序方法，对排序文件的初始状态都不作任何要求，而归并排序是另一种类型的排序方法。基本思想:采用二路归并技术，即每次将数组a中两个相邻的有序序列归并为一个有序序列。类似地还有三路归并技术和多路归并技术。整个排序过程为：假设待排序文件含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列，再两两归并。如此重复，直到得到一个长度为n的有序文件为止。初始状态[45][21][34][19][52][60][34][24]┕━━┙┕━━┙┕━━┙┕━━┙第一趟[2145][1934][5260][2434]┕━━┙┕━━┙第二趟[19213445][24345260]┕━━━━━━┙第三趟1921243434455260二路归并排序过程示例有序文件a[s..m]和a[m+1...t]归并为b[s..t]的算法:merge(inta[],ints,intm,intt,intb[]){inti,j,k;i=s;j=m+1;k=s-1;while(i<=m&&j<=t){k++;if(a[i]<=a[j]){b[k]=a[i];i++;}else{b[k]=a[j];j++;}}if(i>m)for(;j<=t;j++){k++;b[k]=a[j];}elsefor(;i<=m;i++){k+