数据结构算法应用题.doc

《数据结构算法应用题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、举例说明二分查找的基本思想，并用类C语言设计算法实现二分查找(折半查找)。解：二分法查找的过程是：首先确定待查记录的范围，然后逐步缩小范围到直到找到或找不到该记录为止。例如：已知11个数据元素的有序表，（关键字为数据元素的值）：（05，13，19，21，37，56，64，75，80，88，92），现在查找关键字为21的数据元素。设指针low指向下界，high指向上界，mid=（low+high）」/2指向中间区域。所以此例种设low=1，则high=11，mid=6。首先取mid所指元素ST.elem[mid].key与给定值key

2、=21比较，因为56>21，说明所查key=21一定在56的左侧，则令high=mid-1，所以所查元素在[low，mid-1]之间即[1，5]范围，求出mid=（low+high）」/2=3，取mid所指元素19再与key的值21比较，因为19<21，所以所查元素必在21的右侧，则令low=mid+1，所以所查元素在[mid+1，high]之间即[4，5]范围，求mid=（low+high）」/2=4，取mid所指元素21再与key的值21比较，相等，查找成功，所查元素在表中序号为mid的值是4。按照以上方法若所查元素在表中不存在，则

3、会出现low>high的情况，因此当low>high说明查找不成功。算法如下：IntSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中查找值为key的元素，若找到，则函数值为该元素在表中的位置，否则为0low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;//找中间位置if(EQ(key,ST.elem[mid].key)returnmid;//找到返回元素在表中的位置elseif(LT(key,ST.elem[mid].key))h

4、igh=mid-1;//继续在前半区间找elselow=mid+1;//继续在后半区间找}Return0;//顺序表中不存在待查元素}//二分法查找算法二、将两个有序单链表合并为一个有序单链表通过比较不断后移指针合并链表。voidMergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc){//已知单链表La和Lb的元素按非递减排序，合并两表得到非递减排序的表Lcpa=La->next；pb=Lb->next；//分别指向第一个结点Lc=pc=La；//用La的头节点作为Lc的头节点while(pa&

5、&pb){if(pa->data<=pb->data){pc->next=pa；pc=pa；pa=pa->next；}else{pc->next=pb；pc=pb；pb=pb->next；}}pc->next=pa?pa:pb；//处理剩余部分free(Lb)；}三、假设表达式由单字母变量和双目四则运算符(+，-，*，/)构成，用类C语言设计算法将一个通常书写形式且书写正确的表达式转换为逆波兰式。voidChange(char*s1,char*s2)//将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式{StackR;//定义

6、用于暂存运算符的栈InitStack(R);//初始化栈Push(R,'@');//给栈底放入'@'字符，它具有最低优先级0inti,j;i=0;//用于指示扫描s1串中字符的位置，初值为0j=0;//用于指示s2串中待存字符的位置，初值为0charch=s1[i];//ch保存s1串中扫描到的字符，初值为第一个字符while(ch!='@'){//顺序处理中缀表达式中的每个字符if(ch=='+'

7、

8、ch=='-'

9、

10、ch=='*'

11、

12、ch=='/'){//对于四则运算符，使暂存在栈中的不低于ch优先级的运算符依次出栈并写入到s2中c

13、harw=top(R);while(Precedence(w)>=Precedence(ch)){//Precedence(w)函数返回运算符形参的优先级s2[j++]=w;Pop(R);w=top(R);}Push(R,ch);//把ch运算符写入栈中ch=s1[++i];}else{s2[j++]=ch;ch=s1[++i];}}//把暂存在栈中的运算符依次出栈并写入到s2串中while(！Empty(R)){s2[j++]=pop(R);}s2[j++]='';}求运算符优先级的Precedence函数为：intPrecede

14、nce(charop)//返回运算符op所对应的优先级数值{switch(op){case'+':case'-':return1;//定义加减运算的优先级为1case'*':case'/':return2;