《算法设计题复习》word版

《《算法设计题复习》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法设计题复习1、有一个带头结点的单链表L（至少有一个结点），设计算法将L逆置。StatusListOppose_L(LinkList&L){LinkListp,q;p=L->next;//p指向单链表第一个结点L->next=NULL;//形成空的单链表while(p){//采用头插入法将p结点插入到头结点的后面实现逆置q=p;p=p->next;q->next=L->next;L->next=q;}returnOK;}2、试写一高效的算法，删除有序单链表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度

2、。解：voidListDelete_LSameNode(LinkList&L){LinkListp,q,pre;pre=L;p=pre->next;//pre是p的前驱，p是pre的后继while(p){pre=p;p=p->next;if(p&&p->data==pre->data){pre->next=p->next;//删除相同的元素q=p;p=p->next;free(q);}}}3、已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完

3、成连接运算。请分析你的算法的时间复杂度。voidMergeList_L(LinkList&ha,LinkList&hb,LinkList&hc，intm,intn){if(m>n){hc=hb;p=hb->next;q=ha->next;}else{hc=ha;p=ha->next;q=hb->next;}while(p->next!=NULL)p=p->next;if(q==ha->next)free(ha);elsefree(hb);p->next=q;}}4、试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。intPalindrome_Test()

4、//判别输入的字符串是否回文序列,是则返回1,否则返回0{  InitStack(S);InitQueue(Q);  while((c=getchar())!='@')  {    Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构  }  while(!StackEmpty(S))  {    Pop(S,a);DeQueue(Q,b));    if(a!=b)returnERROR;  }  returnOK;}//Palindrome_Test5、用单链表表示集合，集合中的元素递增有序排列，设计算法求两个集合的交集。要求不破坏原有的结点。S

5、tatusListCross_L(LinkList&A,LinkList&B,LinkList&C){pa=A->next;pb=B->next;C=(LinkList)malloc(sizeof(LNode));C->next=NULL;r=C;while(pa&&pb){if(pa->datadata)pa=pa->next;elseif(pa->data>pb->data)pb=pb->next;else{s=(LinkList)malloc(sizeof(LNode));s->data=pa->data;s->next=NULL;r->next=s;r=

6、s;pa=pa->next;pb=pb->next;}}r->next=NULL;}以上题目如果要求利用原有空间完成交集运算，则算法修改为：StatusListCross_L(LinkList&A,LinkList&B,LinkList&C){C=A;pa=A->next;pb=B->next;pc=A;while(pa&&pb){if(pa->datadata){q=pa;pc->next=pa->next;pa=pa->next;free(q);}elseif(pa->data>pb->data)pb=pb->next;else//pa->data=pb->

7、data{pc=pa;pa=pa->next;pb=pb->next;}}}6、用单链表表示集合，集合中的元素递增有序，设计算法求两个集合的并集。要求不破坏原有的存储空间。StatusListUnion_L(LinkList&A,LinkList&B,LinkList&C){pa=A->next;pb=B->next;C=(LinkList)malloc(sizeof(LNode));C->next=NULL;r=C;while(pa&&pb){if(pa->datadata){s=(LinkList)malloc(