算法试题

1、HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL)解：ElemTypeDeleFront(LNode*&HL){if(HL==NULL){cerr空表endl;exit(1);}LNode*p=HL;HL=HL-next;ElemTypetemp=p-data;deletep;returntemp;}2、统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex)解：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;}//CountX3、设计判断单链表中结点是否关于中心对称算法。解：1、pedefstruct{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);}return(1);}设计在链式存储结构上建立一棵二叉树的算法。解：2、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);}设计判断一棵二叉树是否是二叉排序树的算法。3、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);}}4、有一组初始记录关键字序列（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用链式存储结构表示。解：pedefstructnode{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;}}}5、设计在单链表中删除值相同的多余结点的算法。解：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);}6、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。解：pedefchardatatype;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));}7、设计判断两个二叉树是否相同的算法。解：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));}设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。解：voidinverse(LinkList&L){//逆置带头结点的单链表Lp=L-next;L-next=NULL;while(p){q=p-next;//q指向*p的后继p-next=L-next;L-next=p;//*p插入在头结点之后p=q;}}8、设计在顺序有序表中实现二分查找的算法。解：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;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt-lchild);if(minnumbt-key)flag=0;minnum=bt-key;inorder(bt-rchild);}}在链式存储结构上设计直接插入排序算法解：voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head-next==0)return;elsefor(q=head,p=head-next;p!=0;p=q-next){for(s=head;s!=q-next;s=s-next)if(s-datap-data)break;if(s==q-next)q=p;else{q-next=p-next;p-next=s-next;s-next=p;t=p-data;p-data=s-data;s-data=t;}}}9、设计在链式结构上实现简单选择排序算法。解：voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head-next==0)return;for(q=head;q!=0;q=q-next){min=q-data;s=q;for(p=q-next;p!=0;p=p-next)if(minp-data){min=p-data;s=p;}if(s!=q){t=s-