数据结构经典例题

数据结构经典例题1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。voidsplit(LinkList*&L,LinkList*&L1,LinkList*&L2){LinkList*p=L-next,*q,*r1;//p指向第1个数据节点L1=L;//L1利用原来L的头节点r1=L1;//r1始终指向L1的尾节点L2=(LinkList*)malloc(sizeof(LinkList));//创建L2的头节点L2-next=NULL;//置L2的指针域为NULLwhile(p!=NULL){r1-next=p;//采用尾插法将*p(data值为ai)插入L1中r1=p;p=p-next;//p移向下一个节点(data值为bi)q=p-next;//由于头插法修改p的next域,故用q保存*p的后继节点p-next=L2-next;//采用头插法将*p插入L2中L2-next=p;p=q;//p重新指向ai+1的节点}r1-next=NULL;//尾节点next置空}2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。typedefstructLNode{intdata;structLNode*link;}*LinkList;intSearchk(LinkListlist,intk){LinkListp,q;intcount=0;p=q=list-link;while(p!=NULL){if(countk)count++;elseq=q-link;p=p-link;}if(countk)return(0);else{printf(%d,q-data);return(1);}}3.假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。设str1和str2分别指向两个单词所在单链表的头节点请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置。typedefstructNode{chardata;structNode*next;}SNODE;SNODE*Findlist(SNODE*str1,SNODE*str2){intm,n;SNODE*p,*q;m=Listlen(str1);//求单链表str1的长度mn=Listlen(str2);//求单链表str2的长度nfor(p=str1;mn;m--)//若m大，则str1后移m-n+1个节点p=p-next;for(q=str2;mn;n--)//若n大，则str1后移n-m+1个节点q=q-next;while(p-next!=NULL&&p-next!=q-next){p=p-next;//p、q两步后移找第一个指针值相等的节点q=q-next;}returnp-next;}intListlen(SNODE*head)//求单链表的长度{intlen=0;while(head-next!=NUL){len++;head=head-next;}returnlen;}4.设计一个算法，删除一个单链表L中元素值最大的节点。voiddelmaxnode(LinkList*&L){LinkList*p=L-next,*pre=L,*maxp=p,*maxpre=pre;while(p!=NULL)//用p扫描整个单链表,pre始终指向其前驱节点{if(maxp-datap-data)//若找到一个更大的节点{maxp=p;//更改maxpmaxpre=pre;//更改maxpre}pre=p;//p、pre同步后移一个节点p=p-next;}maxpre-next=maxp-next;//删除*maxp节点free(maxp);//释放*maxp节点}5.有一个带头节点的单链表L（至少有一个数据节点），设计一个算法使其元素递增有序排列。voidsort(LinkList*&L){LinkList*p,*pre,*q;p=L-next-next;//p指向L的第2个数据节点L-next-next=NULL;//构造只含一个数据节点的有序表while(p!=NULL){q=p-next;//q保存*p节点后继节点的指针pre=L;//从有序表开头进行比较,pre指向插入*p的前驱节点while(pre-next!=NULL&&pre-next-datap-data)pre=pre-next;//在有序表中找插入*p的前驱节点*prep-next=pre-next;//将*pre之后插入*ppre-next=p;p=q;//扫描原单链表余下的节点}}6.有一个带头节点的双链表L，设计一个算法将其所有元素逆置，即第1个元素变为最后一个元素，第2个元素变为倒数第2个元素，…，最后一个元素变为第1个元素。voidreverse(DLinkList*&L)//双链表节点逆置{DLinkList*p=L-next,*q;//p指向开好节点L-next=NULL;//构造只有头节点的双链表Lwhile(p!=NULL)//扫描L的数据节点{q=p-next;//用q保存其后继节点p-next=L-next;//采用头插法将*p节点插入if(L-next!=NULL)//修改其前驱指针L-next-prior=p;L-next=p;p-prior=L;p=q;//让p重新指向其后继节点}}7.编写出判断带头节点的双向循环链表L是否对称相等的算法。intEqueal(DLinkList*L){intsame=1;DLinkList*p=L-next;//p指向第一个数据节点DLinkList*q=L-prior;//q指向最后数据节点while(same==1)if(p-data!=q-data)same=0;else{if(p==q)break;//数据节点为奇数的情况q=q-prior;if(p==q)break;//数据节点为偶数的情况p=p-next;}returnsame;}8.假设有两个有序表LA和LB表示，设计一个算法，将它们合并成一个有序表LC。要求不破坏原有表LA和LB。voidUnionList(SqList*LA,SqList*LB,SqList*&LC){inti=0,j=0,k=0;//i、j分别为LA、LB的下标,k为LC中元素个数LC=(SqList*)malloc(sizeof(SqList));//建立有序顺序表LCwhile(iLA-length&&jLB-length){if(LA-data[i]LB-data[j]){LC-data[k]=LA-data[i];i++;k++;}else//LA-data[i]LB-data[j]{LC-data[k]=LB-data[j];j++;k++;}}while(iLA-length)//LA尚未扫描完,将其余元素插入LC中{LC-data[k]=LA-data[i];i++;k++;}while(jLB-length)//LB尚未扫描完,将其余元素插入LC中{LC-data[k]=LB-data[j];j++;k++;}LC-length=k;}9.设有4个元素a、b、c、d进栈，给出它们所有可能的出栈次序。解：所有可能的出栈次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba10.编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。boolsymmetry(ElemTypestr[]){inti;ElemTypee;SqStack*st;InitStack(st);//初始化栈for(i=0;str[i]!='\0';i++)//将串所有元素进栈Push(st,str[i]);//元素进栈for(i=0;str[i]!='\0';i++){Pop(st,e);//退栈元素eif(str[i]!=e)//若e与当前串元素不同则不是对称串{DestroyStack(st);//销毁栈returnfalse;}}DestroyStack(st);//销毁栈returntrue;}11.编写一个算法判断输入的表达式中括号是否配对（假设只含有左、右圆括号）boolMatch(charexp[],intn){inti=0;chare;boolmatch=true;SqStack*st;InitStack(st);//初始化栈while(in&&match)//扫描exp中所有字符{if(exp[i]=='(')//当前字符为左括号,将其进栈Push(st,exp[i]);elseif(exp[i]==')')//当前字符为右括号{if(GetTop(st,e)==true){if(e!='(')//栈顶元素不为'('时表示不匹配match=false;elsePop(st,e);//将栈顶元素出栈}elsematch=false;//无法取栈顶元素时表示不匹配}i++;//继续处理其他字符}if(!StackEmpty(st))//栈不空时表示不匹配match=false;DestroyStack(st);//销毁栈returnmatch;}12.在链串中,设计一个算法把最先出现的子串ab改为xyz。voidRepl(LiString*&s){LiString*p=s-next,*q;intfind=0;while(p-next!=NULL&&find==0)//查找'ab'子串{if(p-data=='a'&&p-next-data=='b')//找到子串{p-data='x';p-next-data='z';//替换为xyzq=(LiString*)malloc(sizeof(LiString));q-data='y';q-next=p-next;p-next=q;find=1;}elsep=p-next;}}13.含n个节点的三次树的最小高度是多少？最大高度是多少？解：设含n个节点的（为完全三次树时高度最小）的三次树的最小高度为h，则有：1+3+9+…+3h-2＜n≤1+3+9+…+3h-1(3h-1-1)/2＜n≤(3h-1)/23h-1＜2n+1≤3h即：h=log3(2n+1)最大高度为n-2。14.假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。voidPathAll(ALGraph*G,intu,intv,intpath[],intd)//d是到当前为止已走过的路径长度，调用时初值为-1{intw，i;ArcNode*p;visited[u]=1;d++;//路径长度增1path[d]=u;//将当前顶点添加到路径中if(u==v&&d1)//输出一条路径{printf();for(i=0;i=d;i++)printf(%d，path[i]);printf(\n);}p=G-adjlist[u].firstarc;//p指向u的第一条边while(p!=NULL){w=p-adjvex;//w为u的邻接顶点if(visited[w]==0)//若顶点未标记访问，则递归访问之PathAll(G,w,v,path,d);p=p-nextarc//找u的下一个邻接顶点}visited[u]=0;//恢复环境}voidmain(){intpath[MAXV],u=1,v=4,i,j;MGraphg;ALGraph*G;g.n=5;g.e=6;intA[MAXV][MAXV]={{0,1,0,1,0}，{1,0,1,0,0}，{0,1,0,1,1}，{1,0,1,0,1}，{0,0,1,1,0}};for(i=0