数据结构实验报告2讲解

1、数据结构实验报告实验 1.汉诺塔的实现一需求分析题目：假设有三个命名为 X，Y，Z 的塔座，在塔座 X 上插有 n个直径大小各不相同、 依小到大编号为 1,2,， n的圆盘。现按照要求将 X 轴上的 n个圆盘移至塔座 Z 上， 并仍按同样顺序叠排，圆盘移动时必须遵守以下规则：1，每次只能移动一个； 2，圆盘 可以插在 XYZ 中的任一塔座上； 3，任何时刻都不能将一个较大的圆盘压在较小的圆 盘上。需要输入的值：圆盘的个数。 输出：从 X 塔座上移至 Z 塔座上的顺序。测试数据： 3 ，输出结果预测： x y,x z,y z,x y,z y,z x,y x,y z,x y,x z,y z (箭头

2、符号表示圆盘移动的次序)移动结束。二概要设计： 本实验主要运用递归的思想，先把上面的 n-1 个拿到 Y 盘，把最下面的一个 Z 盘，然 后剩下的 n-1 个也用这样的思路，用递归调用的算法实现圆盘的移动。三详细设计：四调试分析： 遇到的问题：移动时，步骤编号不变。解决方法：用 static 使其成为静态变量。 时间复杂度： o(n);经验体会：递归可以把问题简单化，是个很好的方法。五使用说明： 输入盘子的数目即可。六测试结果：七源代码：#include<stdio.h>#include<string.h>void move(char a,int i,char b) s

3、tatic int c=0;printf("%i.move disk %i. from %c to %cn",+c,i,a,b); / 移动void hanoi(int n,char x,char y,char z) if(n=1) move(x,1,z); elsehanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z);/ 递归int main()char x,y,z; int n; scanf("%d",&n); x='x' y='y' z='z'hano

4、i(n,x,y,z);/ 调用 return 0;实验 2.字符串匹配 一需求分析： 输入一母串，另输入一字符串， 判断该字符串是不是母串的字串， 若是字串，则返回母 串中字串的起始位置，否则输出不是字串。输入：两串字符； 输出：返回值或 0。 测试数据： abcdefgijk efg 预测结果： 4二概要设计： 用查找的方法，如果遇到第一个相同的字母，则字串母串同时往后移一个。三详细设计：int substring(string s1,string s2)/s1 是字串int a=0,b,j=1,i; for(b=0;b<s2.length();b+) i=b;for(;a<s1

5、.length();a+)if(s1a!=s2i) j=0;continue;/ 若 s1 的字母和 s2的字母有一个不同则进行下一个的 比较else i+;j+;if(j=s2.length() return a-s2.length()+1;/ 如果匹配， 则返回母串中与字串开始匹配的return 0;四调试分析：遇到的问题： 跳出循环时没有考虑到如果字串与母串相匹配则字串的字母也要向后移动 一个。解决方法：字串同时后移一个如果前一个相匹配。时间复杂度： o(n2); 经验体会：设计算法时，即使是很简单的算法，也不能掉以轻心。五用户使用说明： 输入一字符串，换行，再输入一字符串，再换行，在换

6、行，即可。六运算结果：七源代码：#include<iostream> #include<string> using namespace std; int substring(string s1,string s2)/s1 是字串int a=0,b,j=1,i; for(b=0;b<s2.length();b+)i=b;for(;a<s1.length();a+)if(s1a!=s2i) j=0;continue;/ 若 s1 的字母和 s2的字母有一个不同则进行下一个的 比较else i+;j+;if(j=s2.length() return a-s2.le

7、ngth()+1;/ 如果匹配， 则返回母串中与字串开始匹配的return 0;int main()string s1,s2; getline(cin,s1);/ 输入母串 getline(cin,s2);/ 输入字串 cout<<substring(s1,s2)<<endl; return 0;实验 3.停车场管理 一需求分析：问题： 用栈模拟停车场， 汽车到达时记录下汽车的编号以及进停车场时间， 离开时，记 录下离开时间并结算停车费。需要输入的数据： 汽车离开还是到达的信息， 汽车的标号， 以及汽车的到达或者离的时 间。需要输出的数据：到达：汽车停在哪里，离开：汽车

8、需要交多少钱。测试数据： n=2(即有多少停车位 )。('A',1，5),(A',2,10),( D',1，15),(A',3,20),(A',4，25),(A',5，30),(D',2，35),(D',4,40),(E',0,0)。 二设计概要：1. 需要设计两个栈，一个作为停车场，一个作为把车退出来时，暂时停车的地方。还需 设计个队列，用来停放等进停车场的车。2. 当停车场中有空位时，才可以让其他的车进去，此时，来的车需要在便道上等待。另 外，要车子进停车场时，才计算时间。在栈底的汽车退出来时，栈顶的车需要退出

9、来， 让栈底汽车退出来，在进入停车场，再从便道上取一辆等待停车的汽车。三详细设计 :1. 汽车需要做成一个结构体或类：class carchar statueinfo;/ 停车状态。int carnum;/ 汽车编号int time;/ 汽车离开或到达的时间public:car()statueinfo='E'carnum=0;time=0;car(char statueinfo,int carnum,int time)this->statueinfo=statueinfo;this->carnum=carnum;this->time=time;char get

10、s()/ 取车的状态return statueinfo;int getcarnum()/ 车的编号return carnum;int gettime()/ 车离开或到达的时间return time;void settime(int time)/ 重新设置时间 this->time=time;void setcarnum(int canum)/ 重新设置车的编号 this->carnum=carnum;void setcarnum(char statueinfo)/ 重新设计车的状态 this->statueinfo=statueinfo;2. 设计一个栈，用于停车或者暂时存放

11、车辆。class stack:public car/ 栈car *base;car *top;int stacksize;public:stack()/ 初始化 stacksize=200;base=new carstacksize; top=base;stack(int stacksize)/ 设计一个新的容量的栈 this->stacksize=stacksize; base=new carstacksize; top=base;stack()/ 解放栈的空间car *gettop()/ 取栈顶return top-1;car *getbase()/ 取栈底return base-1

12、;int getsize()/ 取栈的大小return stacksize;car *push(car e)/ 压入栈/if(top-base>stacksize) return 0; *top=e;top+; return top;car *pop()/ 弹出栈/if(top=base) return 0; top-;return top;3. 设计一个队列，用于存放没有停车位置的车。 class queue:public car/ 队列car *front;car *rear;public:queue()/初始化 front=new car200; rear=front;queue(

13、)/ 解放队列car *enqueue(car e)/ 让车进入队列*front=e;front+;return front;car *dequeue()/ 让车出队列rear+;return rear;car *getfront()/ 取队头元素return front;car *getrear()/ 取队尾元素return rear;四调试分析：1. 怎样把车的所有信息绑在一起？解决方法：用一个类。2. 怎样把车所有的信息压入栈？解决方法：让栈直接在 car 的类上进行操作。3. 栈的压入出现问题，让 top 指针指向压入的元素，导致后来总出现联机错误，不能 输入数据。解决方法：修改 to

14、p 指针的指向。4. 一开始没有设队列，把所有的车停在栈里，后来仔细看题目，才觉得有点不对。解 决方法：设队列时间复杂度： o(n) 经验体会：做题要仔细分析，不要信服气躁。把数据压入栈后，要把指针向上移一个。 五用户使用说明：首先输入有几个停车车位，之后根据提示输入即可。六实验结果：9七源代码：#include<iostream>using namespace std;#define STACK_INIT_SIZE 100; #define STACKINCREMMNT 10;class carchar statueinfo;/ 停车状态。int carnum;/ 汽车编号int

15、 time;/ 汽车离开或到达的时间public:car() statueinfo='E' carnum=0; time=0;car(char statueinfo,int carnum,int time) this->statueinfo=statueinfo; this->carnum=carnum; this->time=time;10char gets()/ 取车的状态return statueinfo;int getcarnum()/ 车的编号return carnum;int gettime()/ 车离开或到达的时间return time;void

16、 settime(int time)/ 重新设置时间 this->time=time;void setcarnum(int canum)/ 重新设置车的编号 this->carnum=carnum;void setcarnum(char statueinfo)/ 重新设计车的状态 this->statueinfo=statueinfo;class stack:public car/ 栈car *base;car *top;int stacksize;public:stack()/ 初始化 stacksize=200; base=new carstacksize; top=ba

17、se;11 stack(int stacksize)/ 设计一个新的容量的栈 this->stacksize=stacksize; base=new carstacksize; top=base;stack()/ 解放栈的空间car *gettop()/ 取栈顶 return top-1;car *getbase()/ 取栈底return base-1;int getsize()/ 取栈的大小return stacksize;car *push(car e)/ 压入栈/if(top-base>stacksize) return 0; *top=e;top+; return top;

18、car *pop()/ 弹出栈/if(top=base) return 0;top-; return top;class queue:public car/ 队列 12car *front;car *rear;public:queue()/初始化front=new car200; rear=front;queue()/ 解放队列car *enqueue(car e)/ 让车进入队列*front=e; front+; return front;car *dequeue()/ 让车出队列 rear+; return rear;car *getfront()/ 取队头元素return front;c

19、ar *getrear()/ 取队尾元素 return rear;int main()int n,carnum,time;int t100;char statueinfo;cout<<"please input the total parking space:"<<endl; cin>>n;stack s;stack s1(n);13queue q;cout<<s1.getsize()<<endl;while(1)cout<<"WELCOME! the charge of parking is

20、 10 yuan per time unit.nplease input your infomation:n1.arrive or departure information:A(arrive),D(depature),E(end);n2.your number;n3.your arrive or departure time:n"<<endl;cin>>statueinfo>>carnum>>time;car car1(statueinfo,carnum,time);if(car1.gets()='A')/ 如果车辆到

21、来if(s1.gettop()-s1.getbase()<s1.getsize()/ 如果停车场还有位置s1.push(car1);/把车子停进停车场 cout<<s1.getsize()<<endl;tcar1.getcarnum()=car1.gettime();/ 把进停车场的时间记录下来 cout<<"this car now stop in parking lot and NO."<<(s1.gettop()-s1.getbase()<<" positionn"<<e

22、ndl;else/如果停车场没有位置q.enqueue(car1);/把车停入便道中cout<<"this car now stop in makeshift road and NO."<<(q.getfront()-q.getrear()<<" positionn"<<endl;elseif(car1.gets()='D')/ 如果车子离开while(s1.gettop()->getcarnum()!=car1.getcarnum()s.push(*(s1.gettop();s1.p

23、op();/ 当它不是停在栈顶，则把其他的车退出来停入另一个栈中 s1.pop();/弹出要离开的车while(s.gettop()!=s.getbase()s1.push(*(s.gettop();s.pop();/ 把退出的车停回去carthethe14if(q.getfront()!=q.getrear()/ 如果还有车在等停车tq.getrear()->getcarnum()=car1.gettime();/ 把他进入停车场的时间 记录下来cout<<q.getrear()->getcarnum()<<" "<<tq.

24、getrear()->getcarnum()<<endl;s1.push(*(q.getrear();q.dequeue();/ 把等待进入停车场的车停入停车场cout<<"you should pay "<<(car1.gettime()-tcar1.getcarnum()*10<<" yuan. Thank You for Your Custom !n"<<endl;elseif(statueinfo='E') break;else cout<<"

25、there is something wrong.please input again!n"<<endl;/ 结束delete &s1;delete &s;return 0;15实验 4.程序分析一需求分析 问题：读入一个 c 程序，统计程序中代码， 注释和空行的行数以及行数的个数以及平均 行数，并利用统计信息分析评价该代码的风格。输入：一个 c 程序的文件名。 输出：统计信息以及评价。测试的程序： #include<stdio.h> #include<stdlib.h> #include<string.h>int st

26、rc(char a10,char b15,int n) int i;for(i=0;i<n;i+)if(ai!=bi) return i; /查找到第一个不同的字母则返回/字符串比较int main() char a10;/char b15;int n; scanf("%s",a);/输入一字符串 n=strc(a,"void ",6);printf("%dn",n);/输出结果 return 0;二概要设计 :1. 需要用到文件的输入输出相关的知识，当遇到n'表示一行，与这种方法计算行数2. 当遇到 '表一注释

27、行，当一行中只有 n'表示空行，还需要设计一个计算函数 的函数来计算程序中共有多少个函数三详细设计：1.字符串比较的函数int strc(char a100,char b8,int n)16/字符串的比较。int i;for(i=0;i<n;i+)if(ai!=bi) return i; /返回到第一个不相等的字母的位置。 2.函数平均长度的评价表。 char G_Cclass(int s)/平均代码行的等级关系。 if(s<=15&&s>=10) return 'A'elseif(s<=9&&s>=8)|(

28、s>=16&&s<=20) return 'B'else if(s>=5&&s<=7)|(s>=21&&s<=24) return 'C' else if(s=5|s=24) return 'D' else return 'E'/如果以上条件都不满足，则返回 E.3. 占总行数比率的评价关系： char G_ZBclass(double s)/注释行以及空白行的等级关系。if(s>=0.15&&s<=0.25) retu

29、rn 'A'else if(s<=0.14&&s>=0.10)|(s>=0.26&&s<=0.30) return 'B' else if(s>=0.05&&s<=0.09)|(s>=0.31&&s<=0.35) return 'C' elseif(s=0.05|s=0.35) return 'D'17 else return 'E' /以上条件都不满足，返回 E。4. 判断是不是关键字int CS(ch

30、ar d) /判断语句的前一个单词是不是关键词。int a=0,i;if(strc(d,"void",5)=4|strc(d,"int",5)=3|strc(d,"char",5)=4|strc(d,"double",8)=6|strc(d,"f loat",6)=5|strc(d,"bool",5)=4)a+; for(i=0;i<strlen(d)-2;i+) if(di='(') a+;break;if(a=2) return 2;else ret

31、urn 0;/a 为标志。5. 判断是不是函数：int G_F(FILE *fp,char file) /判断函数的个数。char ch,h100;int i=0,a=0,b=0,s100,tg=0,m20=0,j,n=1; if(fp=fopen(file,"r")=NULL) /打开文件。printf("Can not open file.n");exit(0); while(!feof(fp) /读文件。 ch=fgetc(fp); if(ch!='n') hi=ch;18 i+;tg=0;else if(ch='n'

32、;)b+; if(tg=1) tg=2; else tg=1; if(CS(h)=2) a+; sa=b;i=0;if(tg=1&&ch='/') tg=2;if(tg=2) ma+;tg=0;fclose(fp);/关闭文件。 sa+1=b+1;for(j=0;j<a;j+) n=n+sj+2-sj+1-mj+1;gl=n;/gl 为总的行数的代码行。return a;/返回值为总的函数个数。6. 主函数：int main()FILE *f;char filename20,ch,zc,bc,fc; int tl=1,tg=0,bk=0,cl,zl=0,f

33、n,tag=0; double codep,comp,sp,al; printf("please input your file name :n"); scanf("%s",filename); if(f=fopen(filename,"r")=NULL) printf("Can not open file.n"); exit(0);19/打开文件。while(!feof(f)ch=fgetc(f);if(ch='n')if(tg=1) bk+;tl+;tg=1/tag 为标志 ;else if(c

34、h='/')if(tag=1) zl+;tag+;else tag=1;else tg=0;tag=0; /判断文件的注释行与空行的行数。 fclose(f);/关闭文件。 fn=G_F(f,filename);/ 计算函数的个数 fc=G_Cclass(fn);/ 计算平均函数行数的等级 al=gl*1.0/fn;/ 计算平均行数cl=tl-bk-zl;codep=cl*1.0/tl;/ 代码行占总行数的比率comp=zl*1.0/tl;/ 注释行占总行数的比率 sp=bk*1.0/tl;/ 空白行占总行数的比率 zc=G_ZBclass(comp);bc=G_ZBclass

35、(sp);/ 计算等级 show(filename,cl,zl,bk,codep,comp,sp,fn,al,fc,zc,bc);/ 打印 return 0;四. 调试分析： 遇到的问题： 1.不知道怎样表示空行。解决办法：设一个标志，当遇到一个转行符时，标志变成1，当标志位 1 且再次遇到一个转行符时，则表示遇到一个空行2.文件打不开。解决方法：写文件名时要写路径。3. 怎么计算函数个数？解决方法：找关键字及括号。 时间复杂度： O( 1)20经验体会：知道了怎样打开文件，不会的要会去找资料，不要遇到一点困难就退缩。五. 用户使用说明：只要输入文件名即可，一定要输路径和后缀！六. 实验结果：

36、七源代码：#include<stdio.h>#include<stdlib.h>#include<string.h> static int gl;int strc(char a100,char b8,int n) /字符串的比较。int i;for(i=0;i<n;i+)if(ai!=bi) return i;/返回到第一个不相等的字母的位置。 char G_Cclass(int s) /平均代码行的等级关系。 if(s<=15&&s>=10) return 'A' else21 if(s<=9&

37、;&s>=8)|(s>=16&&s<=20) return 'B'else if(s>=5&&s<=7)|(s>=21&&s<=24) return 'C' elseif(s=5|s=24) return 'D'else return 'E' /如果以上条件都不满足，则返回E.char G_ZBclass(double s) /注释行以及空白行的等级关系。if(s>=0.15&&s<=0.25) retur

38、n 'A'else if(s<=0.14&&s>=0.10)|(s>=0.26&&s<=0.30) return 'B'else if(s>=0.05&&s<=0.09)|(s>=0.31&&s<=0.35) return 'C' elseif(s=0.05|s=0.35) return 'D'else return 'E' /以上条件都不满足，返回 E。int CS(char d) /判断语句的前一个单

39、词是不是关键词。int a=0,i;if(strc(d,"void",5)=4|strc(d,"int",5)=3|strc(d,"char",5)=4|strc(d,"double",8)=6|strc(d,"float", 6)=5|strc(d,"bool",5)=4)a+;for(i=0;i<strlen(d)-2;i+)22if(di='(') a+;break;if(a=2) return 2;else return 0;/a 为标志。int

40、 G_F(FILE *fp,char file) /判断函数的个数。char ch,h100;int i=0,a=0,b=0,s100,tg=0,m20=0,j,n=1; if(fp=fopen(file,"r")=NULL) /打开文件。printf("Can not open file.n");exit(0);while(!feof(fp)/读文件。ch=fgetc(fp);if(ch!='n')hi=ch;i+;tg=0;else if(ch='n')b+;if(tg=1) tg=2;else tg=1;if(CS(

41、h)=2)a+; sa=b;i=0;if(tg=1&&ch='/') tg=2;if(tg=2) ma+;tg=0;23 fclose(fp); /关闭文件。 sa+1=b+1; for(j=0;j<a;j+) n=n+sj+2-sj+1-mj+1;gl=n;/gl 为总的行数的代码行。return a; /返回值为总的函数个数。void show(char file,int a,int b,int c,double d,double e,double f,int g,double h,char i,char j,char k) /输出函数。char t1

42、1="ss",m11,n11;switch(i) case('A'):strcpy(t,"Excellent");break; case('B'):strcpy(t,"Great") ;break; case('C'):strcpy(t,"General");break; case('D'):strcpy(t,"Bad");break; case('E'):strcpy(t,"Poor");bre

43、ak; default: strcpy(t,"xxxx");break;switch(j)case('A'): strcpy(m,"Excellent");break;case('B'): strcpy(m,"Great");break;case('C'): strcpy(m,"General");break;case('D'): strcpy(m,"Bad");break;case('E'): strcpy(m,&

44、quot;Poor");break;default: strcpy(m,"xxxx");break;switch(k)case('A'): strcpy(n,"Excellent");break;case('B'): strcpy(n,"Great");break;case('C'): strcpy(n,"General");break;case('D'): strcpy(n,"Bad");break;24case('E'): strcpy(n,"