数据结构常考算法大全

数据结构常考算法大全HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL){if(HL==NULL){cerr空表endl;exit(1);}LNode*p=HL;HL=HL-next;ElemTypetemp=p-data;deletep;returntemp;}统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P-data==x)i++;p=p-next;}//while,出循环时i中的值即为x结点个数returni;}//CountX写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为,an，an-1，……a1。Voidcontrary(Lnode*&HL){Lnode*P=HL;HL=NULL;While(p!=null){Lnode*q=p;P=p→next;q→next=HL;HL=q;}}34．阅读下列函数arrange()intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(iwhile(i=x)j--；while(i=x)i++；if(i{t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]；elsereturni－1；}（1）写出该函数的功能；（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。五、算法设计题（本题共10分）34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。（2）intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p；returnp－q；}}设计判断单链表中结点是否关于中心对称算法。typedefstruct{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstackstack;stack.top=-1;lklist*p;for(p=head;p!=0;p=p-next){stack.top++;stack.s[stack.top]=p-data;}for(p=head;p!=0;p=p-next)if(p-data==stack.s[stack.top])stack.top=stack.top-1;elsereturn(0);return(1);}设计在链式存储结构上建立一棵二叉树的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt){charch;scanf(%c,&ch);if(ch=='#'){bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt-data=ch;createbitree(bt-lchild);createbitree(bt-rchild);}设计判断一棵二叉树是否是二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt-lchild);if(minnumbt-key)flag=0;minnum=bt-key;inorder(bt-rchild);}}设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(ij){while(ij&&r[j]x)j=j-1;if(ij){r[i]=r[j];i=i+1;}while(ij&&r[i]x)i=i+1;if(ij){r[j]=r[i];j=j-1;}}r[i]=x;}设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next){for(q=hb;q!=0;q=q-next)if(q-data==p-data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-next=hc;hc=t;}}}设计在单链表中删除值相同的多余结点的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p-next){for(q=p-next,s=q;q!=0;)if(q-data==p-data){s-next=q-next;free(q);q=s-next;}else{s=q,q=q-next;}}}设计一个求结点x在二叉树中的双亲结点算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt-data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt-lchild,x);preorder(bt-rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i=r;i++)if(q[i]-lchild-data==x||q[i]-rchild-data)break;if(flag==0)printf(notfoundx\n);elseif(i=r)printf(%c,bt-data);elseprintf(notparent);}设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p-next;p-next=0;if(p-data='A'&&p-data='Z'){p-next=ha;ha=p;}elseif(p-data='0'&&p-data='9'){p-next=hb;hb=p;}else{p-next=hc;hc=p;}}}计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt-lchild);swapbitree(bt-rchild);p=bt-lchild;bt-lchild=bt-rchild;bt-rchild=p;}在链式存储结构上建立一棵二叉排序树。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt-key=key;bt-lchild=bt-rchild=0;}elseif(bt-keykey)bstinsert(bt-lchild,key);elsebstinsert(bt-rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i=n;i++)bstinsert(bt,random(100));}设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1-data!=bt2-data)return(0);elsereturn(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild));}设计两个有序单链表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha-datadata){if(s==0)hc=s=ha;else{s-next=ha;s=ha;};ha=ha-next;}else{if(s==0)hc=s=hb;else{s-next=hb;s=hb;};hb=hb-next;}if(ha==0)s-next=hb;elses-next=ha;}设计在顺序有序表中实现二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].keyk)high=mid-1;elselow=mid+1;}return(0);}设计判断二叉树是否为二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structno