数据结构作业汇总

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 (p

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

4、, 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）分析问题,建立数据模型；（2）设计适合的存储结构；（3）设计

5、相应算法；（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为第m个人for (int i=s+1; ilength; i+)ai-

6、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; count+;coutdataendl;delete p;delete pre;d

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

8、。作业：设计算法，把十进制整数转换为二进制至九进制之间的任一进制输出。分析 ： 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- -);作业：设计算法，判断给定模式是否为两个主串的公共子序列。分析 ：调用两次子序列判定函数即可。子序列判定函数伪代码如下1 初始化比较的起始位置 , i=0,j=0;2

9、. length仁字符串A的长度，length2=字符串B的长度；3. 当 ile ngthl &jle ngth2,重复下面操作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 andian (int a , int n, int m)for (i=0; in ; i+)min=ai

10、O; 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;BiNode *rchild;template int BiTree:LeafNumber(BiNode *root

11、) 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;return num;方法二：int getleafnum( BiNode* root)int num=0;B

12、iNode* 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 (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+)i2=j;if (huffTreej.parent=-1 & huffTreej.weighthuffTreei2.weigh