数据结构实验报告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个也用这样的思路，用递归调用的算法实现圆盘的移动。三详细设计：四.调试分析：遇到的问题：移动时，步骤编号不变。解决方法：用时间复杂度：o(n);经验体会：递归可以把问题简单化，是个很好的方法。 五使用说明：输入盘子的数目即可。六测试结果：static使其成为静态变量。1 . mauedisk1-FromXtoz2 navedisk2.fromKtoy3 novedish1.fronZto$咗.novedisk3.FromtoE5.nouedisk1-FromJtoX6.nouedisk2_fro

3、mytoZ7. imouedisk1-fromXto2七源代码：#in clude#in clude void move(char a,i nt i,char b)static 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);elsehano i( n_1,x,z,y); move(x, n,z);hano i( n_1,y,x,z);/递归int mai n()char x,y,z;int n;sc

4、an f(%d, &n);x=x;y=y;z= z;hanoi(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;bs2.le ngth();b+)

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

6、在换行，即可。六.运算结果：abcdefgjhijk七源代码：#in clude #in clude using n amespace std; int substring(string s1,string s2)/s1 是字串int a=0,b,j=1,i; for(b=0;bs2.length();b+)i=b;for(;as1.length();a+)if(s1a!=s2i) j=0;continue;若si的字母和s2的字母有一个不同则进行下一个的比较else i+;j+;if(j=s2.length() return a-s2.length()+1;/ 如果匹配， 则返回母串中与字串

7、开始匹配的return 0;int main()string s1,s2;getline(cin,s1);/ 输入母串getline(cin,s2);/ 输入字串 coutsubstring(s1,s2)statueinfo=statueinfo;this-carnum=carnum;this-time=time; char gets()/ 取车的状态return statueinfo;int getcarnum()/ 车的编号return carnum;int gettime()/ 车离开或到达的时间return time;void settime(int time)/ 重新设置时间 thi

8、s-time=time;void setcarnum(int canum)/ 重新设置车的编号 this-carnum=carnum;void setcarnum(char statueinfo)/ 重新设计车的状态 this-statueinfo=statueinfo;2. 设计一个栈，用于停车或者暂时存放车辆。class stack:public car/ 栈car *base;car *top;int stacksize;public:stack()/ 初始化 stacksize=200;base=new carstacksize; top=base;stack(int stacksiz

9、e)/ 设计一个新的容量的栈 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-basestacksize) return 0; *top=e;top+; return top;car *pop()/ 弹出栈/if(top=base) retu

10、rn 0; top-;return top;3. 设计一个队列，用于存放没有停车位置的车。 class queue:public car/ 队列car *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;car *getrear()/ 取

11、队尾元素return rear;四调试分析：1. 怎样把车的所有信息绑在一起？解决方法：用一个类。2. 怎样把车所有的信息压入栈？解决方法：让栈直接在 car 的类上进行操作。3. 栈的压入出现问题，让 top 指针指向压入的元素，导致后来总出现联机错误，不能 输入数据。解决方法：修改 top 指针的指向。4. 一开始没有设队列，把所有的车停在栈里，后来仔细看题目，才觉得有点不对。解 决方法：设队列时间复杂度： o(n) 经验体会：做题要仔细分析，不要信服气躁。把数据压入栈后，要把指针向上移一个。 五用户使用说明：首先输入有几个停车车位，之后根据提示输入即可。六实验结果：please inpu

12、t ttie1 parKing- ?paqe :22ULCOME* tFe cliarffe of parking is 10 艸“n per* tine unit- please inv)ut i/our inf omat ion :1 -arrive or departure inf ornt ion ： A (arrive.IKdep艮日 J ；2-vour car numhep；B _youiv awive op dei).aptupe t ime :A 1 52tills ea* notj t0fk in pa 十 king lot an d. the NO. 1 pas it io

13、nWELCOME? the char of parhingf is 10 yuan pei tine unit- piease input i/our inf onat io n ：1 .survive oi* depaititie Inf oi*fnAt Ion : A (arr-yeF Dtdepaturej-endJ j2 _yoi_ir c*i* niiirihcT j3. your arrive er prturc tint =A 2 102thia car now stop in prhing lot and. the NQ.2 positionD 1 15 you should

14、pay 100ThAfik Vou op Voup Custom *WELCOME? theFis 10 L/uan pei* time unit-please input your infomation：1 _aii*iue oi* departure inFoi*nAtion：fi,DCdepatut*e,E；2 _yoUiP car* nunbej?!3 -yomr aiTive 01* dtepai?tuve ：ine Zn 3 202this cat rigu strop In paikingj lot cind tKie HO -2 posi七畳onWELCOME* 七h总 cha

15、rge F parking( is 10 yuan pei time unit- pleade Input j/qlu InFon&t ion -1 .aiKivc or depart uire info mat ion = AEcnd ； Gar nnber;3.9our arrive or deparcwie Cinc =h 4 25this car now stop in RAhcshift 屮口可d nd the NO丄 positionD 2 354 :3&you. sheuld P施250 ruan _ Tli日nit V dli f or Voui* Cus七on !UELCON

16、E? the change o parkingf is 10 uan per t inc un it . please input youi infomatlon -1. ar* depattute :LnDi*n6it; ion = AXcilFiuE、endl、匚2. yowr cr nnber；3your arrive or departuve tine =D 4 4B5 :49vou should pv 50 yu已n Thank You for Your Custom ?JELCONE? the charge of parking is IB yuan per t ime unit,

17、 please input vur infomation：1. arrive or departure infornation：fi,Eend)； Z. 9OU11 cai* niiinbei；3. youp ariiue or* depaptupe tine :E 8 0七源代码：#in cludeusing n amespace std;#defi ne STACK_INIT_SIZE 100;#defi ne STACKINCREMMNT 10;class carchar statue info;/停车状态。int carnum;/汽车编号int time;/汽车离开或到达的时间publ

18、ic:car()statue in fo=E;carnum=0;time=0;car(char statue in fo,i nt carnu m,i nt time) this-statuei nfo=statuei nfo; this-carnum=carnum; this-time=time;char gets()/ 取车的状态return statueinfo;int getcarnum()/ 车的编号return carnum;int gettime()/ 车离开或到达的时间return time;void settime(int time)/ 重新设置时间 this-time=ti

19、me;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=base; stack(int stacksize)/ 设计一个新的容量的栈 this-stacksize

20、=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-basestacksize) return 0; *top=e;top+; return top;car *pop()/ 弹出栈/if(top=base) return 0; top-;return top; ;clas

21、s queue:public car/ 队列 car *front;car *rear;public:queue()初始化 front=new car200; rear=front;queue()/ 解放队列car *en queue(car e)让车进入队列 *front=e; front+;return front;car *dequeue()让车出队列rear+; return rear;car *getfront()/ 取队头元素return front;car *getrear()取队尾元素return rear;int main()int n,carnum,time;int t10

22、0;char statueinfo;coutplease input the total parking space:n;stack s;stack s1(n);queue q;couts1.getsize()endl;while(1)coutWELCOME! the charge of parking is 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 arriv

23、e or departure time:nstatueinfocarnumtime;car car1(statueinfo,carnum,time);if(car1.gets()=A)/ 如果车辆到来if(s1.gettop()-s1.getbase()s1.getsize()/ 如果停车场还有位置sl.push(carl);/把车子停进停车场couts1.getsize()endl;tcar1.getcarnum()=car1.gettime();/ 把进停车场的时间记录下来 coutthis car now stop in parking lot and NO.(s1.gettop()-s

24、1.getbase() positionnendl;else/如果停车场没有位置q.e nqueue(carl);/把车停入便道中coutthis car now stop in makeshift road andNO.(q.getfront()-q.getrear() positionngetcarnum()!=car1.getcarnum()s.push(*(s1.gettop();s1.pop();/当它不是停在栈顶，则把其他的车退出来停入另一个栈中s1.pop();/弹出要离开的车while(s.gettop()!=s.getbase()s1.push(*(s.gettop();s.

25、pop();carthethe/把退出的车停回去if(q.getfront()!=q.getrear()/ 如果还有车在等停车tq.getrear()-getcarnum()=car1.gettime();/ 把他进入停车场的时间 记录下来coutgetcarnum() getcarnum()endl;s1.push(*(q.getrear();q.dequeue();/ 把等待进入停车场的车停入停车场coutyou should pay (car1.gettime()-tcar1.getcarnum()*10 yuan. Thank You for Your Custom !nendl;el

26、seif(statueinfo=E) break;else coutthere is something wrong.please input again!nendl;/ 结束delete &s1;delete &s;return 0;实验 4.程序分析一需求分析问题：读入一个 c 程序，统计程序中代码， 注释和空行的行数以及行数的个数以及平均 行数，并利用统计信息分析评价该代码的风格。输入：一个 c 程序的文件名。 输出：统计信息以及评价。测试的程序：#include #include#includeint strc(char a10,char b15,int n)int i;for(i=0

27、;in;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. 当遇到表一注释行，当一行中只有n表示空行，还需要设计一个计算函数的函数来计算程序中共有多少个函数三详细设计：1. 字符串比较的函数int strc(char a100,char b8,int n)/字

28、符串的比较。int i;for(i=0;in;i+)if(ai!=bi) return i;/返回到第一个不相等的字母的位置。2. 函数平均长度的评价表。 char G_Cclass(int s)/平均代码行的等级关系。 if(s=10) return A;else if(s=8)|(s=16&s=5&s=21&s=0.15&s=0.25) return A;else if(s=0.10)|(s=0.26&s=0.05&s=0.31&s=0.35) return C; elseif(s=0.05|s=0.35) return D;else return E; /以上条件都不满足，返回 E。4.

29、 判断是不是关键字int CS(char 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;istrlen(d)-2;i+) if(di=() a+;break;if(a=2) return 2;else return 0;/a 为标志。5. 判断是不是函数：int G_F(FILE *fp,char file) /判断函数的个数。char ch

30、,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(h)=2) a+; sa=b;i=0;if(tg=1&ch=/) tg=2;if(tg=2) ma+;tg=0;fclose(fp);/关闭文件。 sa

31、+1=b+1;for(j=0;j execut ion 七imie : 1G -297 sPiess ry key to cant inue *七源代码：#in clude#in clude#in cludestatic 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(i nt s)/平均代码行的等级关系。if(s=10) return A：elseif(s=8)|(s=16&s=5&s=21&s=0.15

32、&s=0.25) return A;else if(s=0.10)|(s=0.26&s=0.05&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) /判断语句的前一个单词是不是关键词。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;ist

33、rlen(d)-2;i+)if(di=() a+;break;if(a=2) return 2;else return 0;/a 为标志。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;i+;tg=0;else if(ch=n)b+;if

34、(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;ja;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

35、 t11=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);break; 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,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;case(E): strcpy(n,Poor);break; default: st