C++数据结构上机作业DS作业和实验参考答案总汇解读.doc

2013级DS作业和实验参考答案总汇目第一次作业：复习C++：顺序表插入和删除操作顺序表查找操作和单链表建立单链表操作特殊线性表栈操作：特殊线性表队列操作第七次作业：二叉树的顺序存储第八次作业：复制二叉树第九次作业：二叉树的高度宽度：图的邻接矩阵及遍历：图的生成树第十二次作业：图的最短路径：顺序表：顺序表2：单链表：链表第六次实验：二叉树的建立及遍历第七次实验：二叉树的结点第八次实验：二叉树的存储转换第九次实验：哈夫曼编码：图的邻接表及度：图的存储转换： ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 第一次作业：复习C++9000:矩形面积 ?Problem Description 声明一个名为rect的矩形类，其属性为矩形的左下角和右上角两个点的x和y坐标，该类有效矩形只存在于直角坐标系的第一象限内。若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 ?Input 输入的第一行为一个数字n，表示下面有n组数据，每组数据包括2行；每组数据中的第一行表示矩形左下角点的x和y坐标，第二行表示矩形右上角点的x和y坐标。 ?Output 若所构成的矩形有效，则计算矩形的面积；若所构成的矩形无效，则输出“data error”。 ?Sample Input 2 2 2 4 4 1 2 3 4 ?Sample Output 4 4#includeiostream using namespace std; class rect{ public: rect(int a,int b,int c,int d); ~rect() {} int area(); private: int x1,y1,x2,y2; }; rect::rect(int a,int b,int c,int d){ x1=a;y1=b;x2=c;y2=d;} int rect::area(){return (x2-x1)*(y2-y1);} int main(){ int a,b,c,d,n; cinn; while(n--) { cinabcd; if(a0||b0||c0||d0||a=c||b=d) coutdata errorendl; else { rect r(a,b,c,d); coutr.area()endl;} } return 0; } 9002:数组的循环移位 ?Problem Description 对于一个给定的字符型数组循环左移i位，要求尽量不申请空间，实现“原地”操作。 ?Input 输入的第一行为一个数字n,代表接下来有n组数据，每组数据包括2行；每组数据中的第一行为一个字符串（长度不超过50），第二行为一个数字m，代表要左移的位数。 ?Output 循环左移后的字符型数组内容。 ?Sample Input 1 abcdefgh 3 ?Sample Output defghabc #includeiostream using namespace std; #define N 20 void Reverse(char a[],int from,int to) { int i,j;char t;i=from;j=to; while(ij) {t=a[i];a[i]=a[j];a[j]=t;i++;j--;} } void Converse(char a[],int n,int i) { Reverse(a,0,i-1);Reverse(a,i,n-1);Reverse(a,0,n-1);} int main() { char a[N];int m,n,i;cinm; while(m--){ cinai; n=strlen(a);i=i%n; Converse(a,n,i); coutaendl; } return 0; } 第二次作业：顺序表插入和删除操作003:合并顺序表 ?Problem Description 假设有两个由小到大有序的有序顺序表A和B，现要求将表B并入表A中，且A表仍保持由小到大的有序性。若合并后的顺序表表长超过总容量20，则输出“not enough”。 ?Input 第一行为一个数字n,表示下面有n组数据，每组数据包括4行；每组数据中的第一行表示表A的表长，第二行表示表A的数据元素，第三行表示表B的表长，第四行表示表B的数据元素。 ?