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

《《数数据据结结构构》》课课程程实实习习题题目目实实习习一一1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。2、设有一个单位的人员工资，有如下信息：name、department、basepay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的basepay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。实实习习二二1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为48521376.实实习习三三编写建立一个由单链表组织存储的整数序列的程序，链表中每个结点存储一个整型数值，以此为基础完成将整数b插入到该链表中第一个数值为a的结点之前的程序。实实习习四四采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。实实习习五五对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。实实习习六六假设有一个数据类型为整型的一维数组A，A中的数据元素呈无序状态，编写一个采用堆排序法将A中的数据元素按由小到大进行排序的程序。《数据结构》答案（答案仅供参考）实验一1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。#includestdio.h#includemalloc.hstructstr{charch;structstr*next;};voidmain(){chartem;structstr*p,*h,*s;h=malloc(sizeof(structstr));h-next=NULL;if(h!=NULL){printf(请输入一个字符：);//scanf(%c,&tem);tem=getchar();h-ch=tem;while(tem!='$'){printf(请继续输入：);s=malloc(sizeof(structstr));if(s!=NULL){tem=getchar();//scanf(%c,&tem);s-ch=tem;}if(tem=='$')free(s);else{if(h-next==NULL)h-next=s;elsep-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、basepay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的basepay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。#includeiostream.h#includefstream.h#includestdlib.hvoidmain(){charname[40];chardepartment[40];floatbasepay;floatallowance;floattotal;fstreaminstuf,outstuf;outstuf.open(c:\\paydata.txt,ios::out);if(!outstuf){coutFilecouldnotopen!endl;abort();}cout请输入员工的姓名，部门，基本工资，津贴，总计工资：endl;while(cinnamedepartmentbasepayallowancetotal){outstufname''department''basepay''allowance''total'\n';}outstuf.close();instuf.open(c:\\paydata.txt,ios::in);if(!instuf){coutFilecouldnotopen!endl;abort();}while(instufnamedepartmentbasepayallowancetotal){coutname''department''basepay+100''allowance''total+100endl;}instuf.close();}实验二1、试用分别用线性表的向量存储结构和链表存储结构来实现约瑟夫(Josephu)问题。约瑟夫问题如下：设有n个人围坐圆桌周围。从某个位置上的人开始从1报数，数到m的人便出列，下一个人(第m+1个)又从1报数开始，数到m的人便是第2个出列的人，依次类推，直到最后一个人出列为止，这样就可以得到一个人员排列的新次序。例如，n=8,m=4,从第1个人数起，得到的新次序为48521376.1、数组#includestdio.hvoidmain(){intJosephu[1000],m,n,i,j=0,c1=0,c2=1,t;printf(请输入总人数n:);scanf(%d,&n);printf(请输入m:);scanf(%d,&m);t=n;for(i=0;in;i++){Josephu[i]=i+1;}while(c1t){if((c2)%m==0){printf(%d\t,Josephu[j]);c1++;n=n-1;for(i=j;in;i++){if(Josephu[i+1]!=0)Josephu[i]=Josephu[i+1];}j=j-1;}c2++;j++;if(j==n)j=0;}}2、链表#includestdio.h#includemalloc.hstructJosephu{intnum;structJosephu*next;};voidmain(){inti=1,m,n,count=1;structJosephu*head,*s,*t;head=(structJosephu*)malloc(sizeof(structJosephu));head-num=1;head-next=NULL;printf(请输入总人数n:);scanf(%d,&n);printf(请输入循环数m:);scanf(%d,&m);t=head;while(in){s=(structJosephu*)malloc(sizeof(structJosephu));s-num=i+1;t-next=s;t=s;i++;}t-next=head;t=head;while(t!=NULL){if(count%m==0){printf(%d\t,t-num);if(t-next!=t){s-next=t-next;t=t-next;count+=1;}elset=NULL;}else{s=t;t=t-next;count++;}}}实验三编写建立一个由单链表组织存储的整数序列的程序，链表中每个结点存储一个整型数值，以此为基础完成将整数b插入到该链表中第一个数值为a的结点之前的程序。#includeiostream.hstructdata{intmen;structdata*next;};voidmain(){voidshow(data*st);data*creat();data*insert(data*h,inttem1,intlocal);data*head;intb,a;head=creat();show(head);cout请输入要插入的数据：endl;cinb;cout请输入要插入的位置：endl;cina;head=insert(head,b,a);show(head);}data*creat(){data*h,*t,*s;intchoice;h=newdata;cout请输入数据：endl;cinh-men;t=h;cout请选择：1、继续输入2、退出endl;cinchoice;while(choice!=2){s=newdata;cout请输入数据：endl;cins-men;t-next=s;t=s;cout请选择：1、继续输入2、退出endl;cinchoice;}t-next=NULL;returnh;}data*insert(data*h,inttem1,intlocal){data*t,*s,*bt;bt=newdata;bt-men=tem1;t=h;if(h-men==local){bt-next=h;h=bt;}else{while(t-next!=NULL&&t-men!=local){s=t;t=t-next;}if(t-men==local){s-next=bt;bt-next=t;}elsecout位置输入错误！endl;}returnh;}voidshow(data*st){data*p;p=st;while(p!=NULL){coutp-men\t;p=p-next;}coutendl;}实验四采用llink-rlink方式存储二叉排序树，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。#includeiostream.hstructtree{intnum;structtree*llink;structtree*rlink;};voidmain(){tree*create();voidshow(tree*);tree*head;head=create();show(head);}tree*create(){voidinsert(tree*h,tree*t);tree*h=NULL,*s,*t;intchoice;cout请选择：1、输入数据2、退出endl;cinchoice;while(choice!=2){s=newtree;s-llink=NULL;s-rlink=NULL;cout请输入数据：endl;cins-num;if(h==NULL){h=s;t=h;}elseinsert(h,s);cout请选择：1、输入数据2、退出endl;cinchoice;}returnh;}voidshow(tree*h){if(h!=NULL){show(h-llink);couth-num'\t';show(h-rlink);}}voidinsert(tree*h,tree*t){if(h-numt-num){if(h-rlink==NULL)h-rlink=t;elseinsert(h-rlink,t);}else{if(h-llink==NULL)h-llink=t;elseinsert(h-llink,t);}}实验五对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。#includestdio.h#includestdlib.h#includemalloc.h#defineMAX50structnode{intadjvex;intdut;str