数据结构作业汇总.pdf

《数据结构作业汇总.pdf》由会员分享，可在线阅读，更多相关《数据结构作业汇总.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 作业：分别以顺序表和单链表为存储结构，为线性表类添加一个成员函数，实现线性表中 所有元素就地逆置。顺序表的就地逆置算法：template void SeqList:Reverse()for(int i=0;ilength/2;i+)int temp=datai;datai=datalength-i-1;datalength-i-1=temp;单链表的就地逆置算法：算法一：要修改每个结点的指针域，即把指向后继结点的指针改为指向前躯结点，现办法就是在扫描遍历过程中，对工作指针 P所指结点作指针域前指操作。(1)逆置后原来指向后继结点的指针被破坏，需要保留；(2)逆置需要将P的前躯结点地址填入后继

2、位置，为此需保存前躯结点地址；(3)全部逆置后，头结点的指针域应指向最后结点。template void LinkList:Reverse()p=first-next;pre=null;while(p)r=p-next;p-next=pre;pre=p;p=r;first-next=pre;具体实 需注意事项 算法二：利用头插法将单链表逆置。将原来表的头结点作为新链表的头结点，依次取原来 表中的结点插到新表的头结点之后。注意：后继结点会遭破坏，需暂存。void LinkList:Reverse()p=first-next;first-next=null;while(p)r=p-next;p-n

3、ext=first-next;first-next=p;p=r;作业：设计一个时间复杂度为 O(n)的算法，实现数组 An 中所有元素循环左移 k 个位置。算法一：将数组中的前k个元素存放到一个临时数组中，再将余下的n-k个元素左移k个位置,最后将前k个元素从临时数组复制到原来数组中的后 k个位置。时间复杂度 O(n);空间复杂度 O(k)算法二：先设计一个函数将数组向左循环移动一个位置，然后再调用这个函数 k次，显然，该算法的时间复杂度 O(n*k)算法三：将这个问题看做是把数组 ab转换成数组ba,(aTbT)T=ba Void converse(int A,int n,int k)Rev

4、erse(A,0,k-1);Reverse(A,k,n-1);Reverse(A,0,n-1);Void Reverse（int A,int from,int to）For（i=0;i（to-from+1）/2;i+）Afrom+iAto-i;作业：约瑟夫环问题描述：设有编号为1,2,n的n（n0）个人围坐成一个圈，每个人持有一个密码 m,从第1个 人开始报数，报到 m停止，报m的人出圈，如此下去，直到所有人全部出圈为止。当任意给 定n和m后，设计算法求n个人出圈的次序。要求：（1）分析问题,建立数据模型；（2）设计适合的存储结构；（3）设计相应算法；（4）分析算法时间和空间复杂度；（5）调试

5、算法,上机实现。解：（1）由约瑟夫环问题的求解过程可以把问题的输入（即n个人的编号）看成是一个线性序 列,每个人的编号看成是一个数据元素。因此,问题抽象的数据模型是“线性表”；（2）线性表有两种基本的存储结构顺序存储和链接存储;（3）A.用顺序存储结构实现约瑟夫问题 void Josephus（int a,int n,int m）/约瑟夫环初始化：for（int i=0;i1）/每出圈一次表长减 1 s=(s+m-1)%length;cout as;s为第m个人 for(int i=s+1;ilength;i+)ai-1=ai;删除第m个人 length-;coutdata=a0;rear=f

6、irst;for(int i=1;idata=ai;rear-next=s;rear=s;rear-next=first;/由删除操作输出出圈序列 Node*pre,*p,*q;int count=2;pre=first;p=first-next;while(pre!=p)if(count=m)coutdatanext;pre-next=p;delete q;count=1;else pre=p;p=p-next;count+;coutdataendl;delete p;delete pre;delete first;delete rear;时间复杂度 O(n*m)；空间复杂度 O(n)作业：

7、设顺序栈s中有2n个元素，从栈顶到栈底的元素一次为 a2n,a2n-1,a1,要求通过一个 循环队列重新排列栈中的元素，使得从栈顶到栈底的元素依次 a2n,a2n-2,a2,a2n-1,a2n-3,al，请设计算法实现该操作；要求空间复杂度和时间复杂度均为 O(n)。算法步骤：(1)将所有元素出栈入队；(2)依次将队列元素出队，如果是偶数结点则再入队；如果是奇数结点则入栈；(3)将奇数结点出栈并入队；(4)将偶数结点出队并入栈；(5)将所有元素出栈并入队；(6)将所有元素出队并入栈。作业：设计算法，把十进制整数转换为二进制至九进制之间的任一进制输出。分析：N=(N/D)*D+N%D 先得到的余

8、数为低位，后输出；后得到的余数为高位，后输出；因此，可将余数放入栈中，再将栈元素依次输出。void decimaltor(int num,int r)top=-1;while(num!=0)k=num%r;s+top=k;num=num/r;while(top!=-1)printf(stop-);作业：设计算法，判断给定模式是否为两个主串的公共子序列。分析：调用两次子序列判定函数即可。子序列判定函数伪代码如下 1 初始化比较的起始位置,i=0,j=0;2.length仁字符串A的长度，length2=字符串B的长度；3.当 ile ngthl&jle ngth2,重复下面操作 3.1 if A

9、i=Bj,i+,j+3.2 else i+;4.if j=length2,说明 B 中字符匹配成功，return 1;else return 0;作业：若在矩阵A中存在一个元素是第i行中最小值，又是第j列中最大值，则称此元素为该 矩阵的一个鞍点。假设以二维数组存储矩阵 A，设计算法求矩阵中的所有鞍点，并分析最坏 情况下的时间复杂度。void andian(int a,int n,int m)for(i=0;in;i+)min=aiO;k=0;/min 为 i行中的最小值 for(p=0;pm;j+)If(aipmin)min=aip;k=p;aik为第i行最小值 for(q=0;qmin)br

10、eak;If(q=n)cout“输出鞍点：”ikaik;复杂度分析：O(nm+n 2)作业：编写非递归算法，统计二叉树中叶子结点个数 方法一：const int maxsize=100;template struct BiNode DataType data;BiNode*lchild;BiNode*rchild;template int BiTree:LeafNumber(BiNode*root)int num=0;int top=-1;while(root!=NULL|top!=-1)while(root!=NULL)coutdata;if(root-lchild=NULL&root-rc

11、hild=Null)num+;s+top=root;root=root-lchild;if(top!=-1)root=stop-;root=root-rchild;return num;BiNode*smaxsize;方法二：int getleafnum(BiNode*root)int num=0;BiNode*p=root;SeqStack s;s.Init();s.push(p);while(!s.empty()while(p=s.gettop()&p!=NULL)s.push(p-lchlid);if(!s.empty()p=s.pop();if(p-lchild=NULL&p-rchi

12、lid=NULL)num+;else s.push(p-rchild);return num;作业：设计哈夫曼树构造算法中的 SELECT 函数 void Select(element huffTree ,int&i1,int&i2)int j,t=0;while(huffTreet.parent!=-1)t+;i1=t;for(j=0;j2*n-1,j+)if(huffTreej.parent=-1&huffTreej.weighthuffTreei1.weight)i1=j;/以上找到最小值，下面代码查找次小值 t=0;while(huffTreet.parent!=-1|t=i1)t+;i2=t;for(j=0;j2*n-1,j+)if(huffTreej.parent=-1&huffTreej.weighthuffTreei2.weight&j!=i1)作业：对一个整型数组设计一个递增排序算法，并分析算法复杂度 void selectsort(int r,int n)/简单选择算法 for(i=0;in-1;i+)int index=i;for(j=i+1;jn;j+)if(rjrindex)index=j;if(index!=i)ririndex;时间复杂度为 O(n2),空间复杂度为 O(1)i2=j;