数据结构作业汇总.docx

《数据结构作业汇总.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业：分别以顺序表和单链表为存储结构，为线性表类添加一个成员函数，实现线性表中所有元素就地逆置。顺序表的就地逆置算法：templatevoidSeqList::Reverse(){for(inti=0;i

2、P所指结点作指针域前指操作。(1)逆置后原来指向后继结点的指针被破坏，需要保留；(2)逆置需要将P的前躯结点地址填入后继位置，为此需保存前躯结点地址；(3)全部逆置后，头结点的指针域应指向最后结点。templatevoidLinkList::Reverse(){p=first->next;pre=null;while(p){r=p->next;p->next=pre;pre=p;p=r;first-next=pre;}}算法二：利用头插法将单链表逆置。将原来表的头结点作为新链表的头结点，依次取原来表中的结点

3、插到新表的头结点之后。注意：后继结点会遭破坏，需暂存。voidLinkList::Reverse(){p=first->next;first->next=null;while(p){r=p->next;p->next=first->next;first->next=p;p=r;}}作业：设计一个时间复杂度为0(n)的算法，实现数组A[n]中所有元素循环左移k个位置。算法一：将数组中的前k个元素存放到一个临时数组中，再将余下的n-k个元素左移k个位置,最后将前k个元素从临时数组复制到原来数组中的后k个位置。时间复杂度0(n)

4、;空间复杂度0(k)算法二：先设计一个函数将数组向左循环移动一个位置，然后再调用这个函数k次，显然，该算法的时间复杂度0(n*k)算法三：将这个问题看做是把数组ab转换成数组ba,(aTbT)T=baVoidconverse(intA[],intn,intk){Reverse(A,0,k-1);Reverse(A,k,n-1);Reverse(A,0,n-1);}VoidReverse（intA[],intfrom,intto）{For（i=0;i<（to-from+1）/2;i++）{A[from+i]<->A[to-i];{

5、}}作业：约瑟夫环问题描述：设有编号为1,2,…n的n（n>0）个人围坐成一个圈，每个人持有一个密码m,从第1个人开始报数，报到m停止，报m的人出圈，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。要求：（1）分析问题,建立数据模型；（2）设计适合的存储结构；（3）设计相应算法；（4）分析算法时间和空间复杂度；（5）调试算法,上机实现。解：（1）由约瑟夫环问题的求解过程可以把问题的输入（即n个人的编号）看成是一个线性序列,每个人的编号看成是一个数据元素。因此,问题抽象的数据模型是“线性表”；（2

6、）线性表有两种基本的存储结构——顺序存储和链接存储;（3）A.用顺序存储结构实现约瑟夫问题voidJosephus（inta[],intn,intm）{//约瑟夫环初始化：for（inti=0;i1）//每出圈一次表长减1{s=(s+m-1)%length;cout<

7、;cout<data=a[0];rear=first;for(inti=1;idata=a[i];rear->next=s;rear=s;}r

8、ear->next=first;//由删除操作输出出圈序列Node*pre,*p,*q;intcount=2;pre=first;p=first->next;while(pre!=p){if(count==m){cout<data<