搜索
习题七7.1画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：依题意，假设长度为10的有序表为a，进行二分查找的判定树如图10.3所示。查找成功的平均查找长度：ASL=(1×1+2×2+3×4+4×3)/10=2.97.2假设按下述递归方法进行顺序表的查找：若表长≤10，则进行顺序查找，否则进行折半查找。试画出对表长n＝50的顺序表进行上述查找时，描述该查找的判定树，并求出在等概率情况下查找成功的平均查找长度。解：查找的判定树如下（结点从0开始，升序顺序查找）：结点所在树深度即为查找次数，由此可计算平均查找长度为ASL=(1×1+2×2+4×3+8×4+8×5+8×6+8×7+8×8+3×9)/50=5.687.3一组有序的关键字如下：15，17，22，28，33，41，51，67，90。设法画出一棵具有平衡性的二叉排序树。如果对每一个关键字的查找概率相等，计算平均查找长度ASL。进一步写出解决该问题的算法。（提示：以中间位置元素为根）。ASL=（1×1＋2×2＋3×4＋4×2）/9=2.787.4已知下列关键字和它们对应的哈希函数值(哈希表长度未知,α无法求解)KeyZhaoSunLiWangChenLiuZhangH(Key)6574164由此构造哈希表，用线性探测法解决冲突，计算该哈希表的装填系数α和平均查找长度ASL。若用拉链法解决冲突情况又如何？解：线性探测法(哈希表长度大于8时)ASL(7)=(1×5＋3＋6)/7=2哈希表长度等于8时ASL(7)=(1×5＋3＋7)/7=2.14α=表中填入的记录数/哈希表的长度拉链法ASL(7)=(1×5＋2×2)/7=1.287.5已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。解：将姓氏中的每一个字母换成字母表中的位置，将所有位置两两相乘再相加的和作为key值如周zhou,字母位置为26,8,15,21则key=(26×8＋15×21)%1000＝5237.6试编写一个开放地址法解决冲突的哈希表删除算法。解：/************************************************************************************//*基本思想*//*将哈希表中最后一个与删除关键字key相同的关键字覆盖删除关键字*//*例如123451535,删除5后，12343515*//************************************************************************************/#includestdio.h#defineSIZE10/*最大表长度*/#defineM10/*冲突处理函数*//*****************************************************************************/voidcreat_hash(int*);/*建立哈希表*/voiddel_hash(int*,int);/*删除元素*/voidoutput(int*);/*显示哈希表*//*****************************************************************************/voidmain(void){inthash[SIZE]={0};/*哈希表，初始化为0，表示没有元素*/intk;/*删除的元素*/printf(\n=====================DelHashList=====================\n);creat_hash(hash);output(hash);printf(\nInputthedelkey:);scanf(%d,&k);del_hash(hash,k);output(hash);getch();}/*****************************************************************************/voidcreat_hash(int*hash)/*建立哈希表*/{intm,n,i;printf(Inputdata(most%d,-1isend):\n,SIZE);for(i=0;iSIZE;i++)/*输入元素，并填入哈希表*/{scanf(%d,&m);if(m==-1)break;/*输入元素是-1结束*/n=m%M;/*求key*/while(*(hash+n))n=++n%SIZE;/*线性探测再散列，查找填入位置*/*(hash+n)=m;/*填入哈希表*/}}/*****************************************************************************/voiddel_hash(int*hash,intk)/*删除元素*/{inti,n,m,l;/*i当前元素下标，n同一组key的第一个元素*//*m记录同一组key的最后一个元素，l删除元素下标*/l=m=n=k%M;for(i=(n+1)%SIZE;i!=n;)/*循环处理整个哈希表*/{if(n==*(hash+i)%M)m=i;/*如果key值相同，则记入m*/if(*(hash+i)==k)l=i;/*元素值相同，记入l*/i=++i%SIZE;/*改变i}*(hash+l)=*(hash+m);/*将同一组key的最后一个元素覆盖删除元素*/*(hash+m)=0;/*删除最后一个元素*/}/*****************************************************************************/voidoutput(int*hash)/*显示哈希表*/{inti;printf(HashList:\n);printf(Position);for(i=0;iSIZE;i++)printf(%4d,i);putchar('\n');printf(Data);for(i=0;iSIZE;i++)if(*(hash+i))printf(%4d,*(hash+i));elseprintf();}第七章上机内容7.1、编程实现在一个无序表A中采用顺序查找算法查找值为x的元素，返回其位置。解：#includestdio.h#defineSIZE10/************************************************************************/intsearch(int*,int);/************************************************************************/voidmain(void){inti,k,m;inta[SIZE];printf(\nInputdata:\n);for(i=0;iSIZE;i++)scanf(%d,a+i);printf(Inputsearchdata:);scanf(%d,&k);m=search(a,k);if(m==-1)printf(Nothisdata\n);elseprintf(Thepositionis%d,m);getch();}/************************************************************************/intsearch(int*a,intk){inti;for(i=0;iSIZE;i++)if(*(a+i)==k)returni;return-1;}7.2、编写一个算法，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。解：/*基本思想*//*使用二分查找递归法找到插入的位置，再移动数据，达到插入的目的*/#includestdio.h#includestring.h#defineMAXNUM20/************************************************************************************/intinput(int*);/*输入数据*/intsearch(int*,int,int);/*查找插入位置*/voidplug(int*,int,int);/*插入数据*//************************************************************************************/voidmain(void){intdata[MAXNUM],m;intinsert=1;m=input(data);printf(Inputtheinsertnum:);scanf(%d,data);/*输入插入数据存放在data数组0号位置*/insert=search(data,1,m);/*返回插入位置*/plug(data,insert,m);for(insert=1;insert=m+1;insert++)/*显示数据*/printf(%3d,*(data+insert));getch();}/************************************************************************************/intinput(int*data)/*输入数据*/{inti,m;printf(\nInputthemaxnum:);scanf(%d,&m);printf(Inputdata\n);for(i=1;i=m;i++)scanf(%d,data+i);returnm;}/************************************************************************************/intsearch(int*data,intlow,inthigh)/*递归查找插入位置*/{/*low低地址，high高地址*/intmid;/*中间位置*/if(lowhigh)returnlow;/*没找到插入数据，返回low*/else{mid=(low+high)/2;if(*(data+mid)==*data)returnmid;/*找到插入数据，返回mid*/elseif(*(data+mid)*data)low=mid+1;elseif(*(data+mid)*data)high=mid-1;}search(data,low,high);}/***************************************************************************/voidplug(int*data,intinsert,intm)/*移动并插入数据*/{inti;for(i=m;i=insert;i--)*(data+i+1)=*(data+i);*(data+insert)=*data;}7.3、编写一个算法，求出利用二分查找算法查找任意一个元素所比较的次数。解：/*基本思想*//*用二分查找法查找元素，同时用一个计数器计数*/#includestdio.h#includestring.h#defineMAXNUM20/***************************************************************************/intinput(int*);/*输入数据*/intsearch(int*,int);/*查找数据*//****************************