资源描述:
《一些简单的常用的数据算法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、1.编写一个算法,利用栈将一个非负的十进制整数N转换为一个二进制整数。基本思想:十进制整数N化为二进制整数的方法是,首先将N反复除以2,直到整数商为0,然后逆取余。因为“逆取余”正好符合“后进先出”原则,所以用栈保存运算过程中得到的各个余数。typedefintdatatype;//顺序栈的类型定义#definemaxsize1024typedefstruct{datatypedata[maxs
2、ize];inttop;}seqstack;voidtran(seqstack*s,intn){s->top=-1;//置空栈while(n!=0)//当n不为0时反复“除基逆取余”{s->top++;s->data[s->top]=n%2;//余数进栈n=n/2;//计算整数商}}2.设计算法,实现统计单链表中具有给定值x的所有元素的个数。基本思想:从左往右扫描带头结点的单向链表,每见到一个值为x的元素,都使计数器增1。算法://结点类型定义typedefintdatatype;typedefstructnode{datatyp
3、edata;structnode*next;}linklist;intcountx(linklist*head,datatypex){intn=0;head=head->next;//跳过头结点while(head!=NULL){if(head->data==x)n++;head=head->next;}returnn;}3.设计算法,实现在非递减有序的单链表中删除值相同的多于结点。基本思想:用指针变量head从左往右扫描带头结点的单向链表。对每个当前结点*head,都检查它与后继结点的值是否相等:若相等,则删除后继结点,head
4、不动;否则,移动head。算法://结点类型定义typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;voiddeletedyys(linklist*head){linklist*p;head=head->next;//指向第一个结点if(head!=NULL){p=head->next;while(p!=NULL)if(head->data==p->data){head->next=p->next;free(p);p=head->n
5、ext;}else{head=p;p=head->next;}}}4.设记录的关键字集合K={23,9,39,5,68,12,62,48,33},给定的增量序列D={4,2,1},请写出对K按希尔排序时各趟排序结束时的结果。第一趟结果:23,9,39,5,33,12,62,48,68第二趟结果:23,5,33,9,39,12,62,48,68第三趟结果:5,9,12,25,33,39,48,62,685.设一个字符串用一个带头结点的单链表存储。请设计一个算法,删除字符串中所有字符‘a’。结点类型名为linkstring,结点结构如
6、下:datanext6.二叉树采用二叉链表存储,设计一个算法求一棵给定二叉树中没有左孩子的结点数。结点类型名为bitree,结点结构如下:lchilddatarchild 7.设有两个字符的集合A,B,分别用带头结点的单链表表示。请设计一个算法,利用原有结点空间实现集合A与B的并运算A∪B。结点类型名为linkstring,结点结构如下:datanext voidmerge1(LinkList&A,LinkList&B,LinkList&C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 { p=A->ne
7、xt;q=B->next;C=A; while(p&&q) { s=p->next;p->next=q;//将B的元素插入 if(s) { t=q->next;q->next=s;//如A非空,将A的元素插入 } p=s;q=t; }//while }//merge1 8.二叉树采用二叉链表存储。设计一个算法求一棵二叉树中data域值等于x的结点个数。要求:利用层次遍历,或使用其它的非递归方法。结点类型名为bitree,结点结构如下:lchilddatarchild采用深度优先的示例:voidcountl(bi
8、treptrr,datatypex,int&k){if(!bitreptrr)return;if(bitreptrr->value==x){k++;}countl((bitreptrr->left,x,k);countl((bitreptrr->r