兰州大学数据结构上机实验题目及答案.doc

《数据结构》课程实习题目 实习一 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资，有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 实习二 1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下： 设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序 实习三 编写建立一个由单链表组织存储的整数序列的程序，链表中每个结点存储一个整型数值，以此为基础完成将整数b插入到该链表中第一个数值为a的结点之前的程序。 实习四 采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。 实习五 对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。 实习六 假设有一个数据类型为整型的一维数组A，A 中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。 《数据结构》答案 （答案仅供参考） 实验一 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。#includestdio.h #includemalloc.h struct str { char ch; struct str *next; }; void main() { char tem; struct str *p,*h,*s; h=malloc(sizeof(struct str)); h-next=NULL; if(h!=NULL) { printf(请输入一个字符：); //scanf(%c,tem); tem=getchar(); h-ch=tem; while(tem!=$) { printf(请继续输入：); s=malloc(sizeof(struct str)); if(s!=NULL) { tem=getchar();//scanf(%c,tem); s-ch=tem; } if(tem==$) free(s); else { if(h-next==NULL) h-next=s; else p-next=s; p=s; } } p-next=NULL; } printf(字符串逆序输出为：\n); while(h-next!=\0) { p=h; while(p-next!=\0) { s=p; p=p-next; } printf(%c,p-ch); s-next=\0; } printf(%c,h-ch); printf(\n); } 2、设有一个单位的人员工资，有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 #include iostream.h #include fstream.h #include stdlib.h void main() { char name[40]; char department[40]; float basepay; float allowance; float total; fstream instuf,outstuf; outstuf.open(c:\\paydata.txt,ios::out); if(!outstuf) { coutFile could not open!endl; abort(); } cout请输入员工的姓名，部门，基本工资，津贴，总计工资：endl; while(cinnamedepartmentbasepayallowancetotal)