《算法设计习题(完整)》由会员分享，可在线阅读，更多相关《算法设计习题(完整)（15页珍藏版）》请在金锄头文库上搜索。
1、本文算法设计题涉及的顺序表和线性链表的类型定义如下：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElem Type *elem;int length;int listsize;SqList;typedef struct LNodeELem Type data;Struct LNode *next;LNode,*LinkList;算法设计习题1、 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。void Insert(Sqlist &L,int e) /把e插入到递
2、增顺序表L中int i;int *newbase;if(L.length=L.listsize) /va空间不足 newbase=(int *)malloc(LISTINCREMENT+L.listsize)*sizeof(int); /分配空间 if(!newbase) exit(OVERFLOW); /分配空间不成功则返回 L.elem=newbase; /新基址 L.listsize=L.listsize+LISTINCREMENT; /增加存储容量 for(i=L.length-1; (i=0)&(L.elemie); i-) L.elemi+1=L.elemi; /大于e的元素依次后
3、移L.elemi+1=e; /插入eL.length+; /长度+12、 设A=(a1,.am)和B=(b1,bn)均为顺序表，A和B分别为A和B中除去最大共同前缀后的子表(例如，A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z),则两者中最大的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为A=(x,z)和B=(y,x,x,z)。若A=B=空表，则A=B；若A=空表，而B空表，或者两者都不为空表，且A的首元小于B的首元，则AB。试写一个比较A,B大小的算法（请注意：在算法中，不要破坏原表A和B，并且，也不一定先求得A和B才进行比较）。char comp
4、are(SqList A, SqList B) /比较顺序表A,B int shortest;int i = 0; if(A.length B.length) shortest = B.length;else shortest = A.length; for(i = 0; i B.elemi)return; /以短表的长度作循环 if(A.elemi B.elemi)return B.length)return; if(A.length B.length)returnnext; n+; return(n);4、已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试
5、写一算法将这两个链表连接在一起（即令其中一个表的首结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。LinkList Link( LinkList &L1 , LinkList &L2 ,LinkList &L3,int m,int n) /将两个单链表连接在一起,m,n分别为L1与L2的长度LNode *p , *q ;p=L1-next;q=L2-next;if(m=n)while ( q-next ) q=q-next; /查找短链表终端结点q-next=p;/长的放在短的后面L3-next=L
6、2-next;elsewhile ( p-next ) p=p-next; /查找短链表终端结点p-next=q;/长的放在短的后面L3-next=L1-next;return L3 ;时间复杂度为o(min(m.n)5、已知指针la和lb分别指向两个无头结点单链表中的首结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之前。试问次算法是否正确？若有错，则请改正之。Status DeleteAndInsertSub (LinkedList la,LinkedList lb,int I,int j,int len) if(i0|j0|len0) retu
7、rn INFEASIBLE;p=la;k=1; /p，q没有定义，ListNode *p , *q ;, while(knext;k+;q=p;while(knext;k+;s=lb;k=1;while(knext;k+;s-next=p;q-next=s-next;return OK;/DeleteAndInsertSub直接给出正确版本Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len) LinkList p,s,q,w; p=la;s=lb;w=NULL; int a=1,b=1,c=1;
8、 if(i=0|j=0|len=0) return INFEASIBLE; while(p&anext;a+; /建立一个w的空链表来存放la的数据 if(!p) return INFEASIBLE; q=p; while(q&bnext; b+; if(!q) return INFEASIBLE; if(!w) la=q-next; /i=1的情况，删除len个元素后，将len+1号元素移到第一个结点存放，其他元素向前移 else w-next=q-next; /将删除了len个元素后的其他元素跟前面链接起来 if(j=1) q-next=lb;lb=p; else while(s&cnex
9、t;c+; if(!s) return INFEASIBLE; q-next=s-next; s-next=p; return OK;6、 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态链表上实现相同操作的算法进行比较。Status Insert(LinkList &L,int i,int b)/在无头结点链表L的第i个元素之前插入元素b p = L; q = (LinkList)malloc(sizeof(LNode); q.data = b; if (i = 1) q.next = p; L = q; /插入在链表头部 else whil
10、e(-i1) p=p-next; q-next = p-next; p-next = q; /插入在第i个元素的位置 /Insert7、 试写一个算法，实现顺序表的就地逆转，即利用原表的存储空间将线性表(a1,a2,.,an)逆置为(an,an-1,.a1)。void reverse(SqList &A) 顺序表的就地逆置 int q; for(i=0,j=A.length;inext; if(p=NULL| p-next=NULL) return OK;/空表和表中只有一个结点时，不用逆置。 while(p-next!=NULL) q= p-next; p-next=q-next; /删除结
11、点q，但未释放 q-next=L-next; L-next=q; /将q插入头结点之后 /reverse可运行的C程序代码如下：#include #include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define OVERFLOW -2typedef structint *elem;int length;int listsize;SqList;typedef struct LNodeint data;struct LNode *next;LNode,*LinkList;typedef struct LNodebstruct LNode *head;LNodeb;void insert(SqList &L,int e); /题目1char compare(SqList A, SqList B);/题目2int length(LNode *head);/题目3LinkList link( LNodeb &L1 , LNodeb &L2 ,LNode *p1,int
