数据结构作业汇总

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) 逆置

2、需要将 P的前躯结点地址填入后继位置，为此需保存前躯结点地址；(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

3、 (p)r=p-next;p-next=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=baVoid conv

4、erse ( int A, int n, int k)Reverse (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）分析问

5、题，建立数据模型；（2）设计适合的存储结构；（3）设计相应算法；（4）分析算法时间和空间复杂度；（5）调试算法，上机实现。解：（1）由约瑟夫环问题的求解过程可以把问题的输入 （即 n个人的编号） 看成是一个线性序 列，每个人的编号看成是一个数据元素。因此，问题抽象的数据模型是“线性表”；（ 2） 线性表有两种基本的存储结构顺序存储和链接存储 ;（ 3） A. 用顺序存储结构实现约瑟夫问题void Josephus （int a , int n, int m）/约瑟夫环初始化：for （int i=0; i1） / 每出圈一次表长减 1s=( s+m-1)% length;cout as;/s

6、为第 m个人for (int i=s+1; ilength; i+)ai-1=ai;/删除第 m个人length-;coutdata=a0;rear=first;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;elsepre=p; p=p-next; co

7、unt+;coutdataendl;delete p;delete pre;delete first; delete rear;时间复杂度 O(n*m) ； 空间复杂度 O(n)作业：设顺序栈 s中有 2n个元素，从栈顶到栈底的元素一次为a2n,a2n-1, a1,要求通过一个循环队列重新排列栈中的元素，使得从栈顶到栈底的元素依次 a2n,a2n-2, a2, a2n-1, a2n-3, a1，请设计算法实现该操作；要求空间复杂度和时间复杂度均为O（ n）。算法步骤：（1） 将所有元素出栈入队；（2）依次将队列元素出队，如果是偶数结点则再入队；如果是奇数结点则入栈；（3）将奇数结点出栈并入队；

8、（4）将偶数结点出队并入栈；（5）将所有元素出栈并入队；（6）将所有元素出队并入栈。 作业：设计算法，把十进制整数转换为二进制至九进制之间的任一进制输出。分析 ：N=（N/D）*D+N%D 先得到的余数为低位，后输出；后得到的余数为高位，后输出； 因此，可将余数放入栈中，再将栈元素依次输出。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- -）;作业：设计算法，判断给定模式是否为两个主串的公共子序列。分析 ：调用两次子序列判定

9、函数即可。子序列判定函数伪代码如下1 初始化比较的起始位置 , i=0,j=0;2 length1= 字符串 A的长度， length2= 字符串 B的长度；3 当 ilength1&jlength2, 重复下面操作3.1 if Ai=Bj, i+, j+3.2 else i+;4. if j=length2, 说明 B 中字符匹配成功， return 1; else return 0;作业：若在矩阵 A 中存在一个元素是第 i行中最小值，又是第 j列中最大值，则称此元素为该 矩阵的一个鞍点。假设以二维数组存储矩阵A，设计算法求矩阵中的所有鞍点，并分析最坏情况下的时间复杂度。void andi

10、an (int a , int n, int m)for (i=0; in ; i+)min=ai0; k=0;/ min 为 i行中的最小值for (p=0; pm; j+)If (aipmin) min=aip; k=p; /aik 为第 i 行最小值for (q=0; qmin) break;If (q= =n) cout “输出鞍点：” ikaik;复杂度分析： O(nm+n 2)作业：编写非递归算法，统计二叉树中叶子结点个数方法一：const int maxsize=100;template struct BiNodeDataType data;BiNode *lchild;BiNo

11、de *rchild;template int BiTree:LeafNumber(BiNode *root) int num=0;BiNode* smaxsize;/采用顺序栈，并假定不会发生上溢int top = -1;while (root != NULL | top != -1)while (root != NULL)coutdata;if( root-lchild=NULL & root-rchild=Null) num+; s+top = root;root = root-lchild;if (top != -1) root = stop-;root = root-rchild;r

12、eturn num;方法二：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-rchilid=NULL) num+;elses.push (p-rchild);return num;作业：设计哈夫曼树构造算法中的 SELECT 函数void Select (el

13、ement 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+)i2=j;if (huffTreej.parent=-1 & huffTreej.weighthuffTreei2.we