數(shù)據(jù)結(jié)構(gòu)實驗報告2講解

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗 1.漢諾塔的實現(xiàn)一需求分析題目：假設(shè)有三個命名為 X，Y，Z 的塔座，在塔座 X 上插有 n個直徑大小各不相同、 依小到大編號為 1,2,， n的圓盤?，F(xiàn)按照要求將 X 軸上的 n個圓盤移至塔座 Z 上， 并仍按同樣順序疊排，圓盤移動時必須遵守以下規(guī)則：1，每次只能移動一個； 2，圓盤 可以插在 XYZ 中的任一塔座上； 3，任何時刻都不能將一個較大的圓盤壓在較小的圓 盤上。需要輸入的值：圓盤的個數(shù)。 輸出：從 X 塔座上移至 Z 塔座上的順序。測試數(shù)據(jù)： 3 ，輸出結(jié)果預(yù)測： x y,x z,y z,x y,z y,z x,y x,y z,x y,x z,y z (箭頭

2、符號表示圓盤移動的次序)移動結(jié)束。二概要設(shè)計： 本實驗主要運用遞歸的思想，先把上面的 n-1 個拿到 Y 盤，把最下面的一個 Z 盤，然 后剩下的 n-1 個也用這樣的思路，用遞歸調(diào)用的算法實現(xiàn)圓盤的移動。三詳細(xì)設(shè)計：四調(diào)試分析： 遇到的問題：移動時，步驟編號不變。解決方法：用 static 使其成為靜態(tài)變量。 時間復(fù)雜度： o(n);經(jīng)驗體會：遞歸可以把問題簡單化，是個很好的方法。五使用說明： 輸入盤子的數(shù)目即可。六測試結(jié)果：七源代碼：#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);/ 調(diào)用 return 0;實驗 2.字符串匹配 一需求分析： 輸入一母串，另輸入一字符串， 判斷該字符串是不是母串的字串， 若是字串，則返回母 串中字串的起始位置，否則輸出不是字串。輸入：兩串字符； 輸出：返回值或 0。 測試數(shù)據(jù)： abcdefgijk efg 預(yù)測結(jié)果： 4二概要設(shè)計： 用查找的方法，如果遇到第一個相同的字母，則字串母串同時往后移一個。三詳細(xì)設(shè)計：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;四調(diào)試分析：遇到的問題： 跳出循環(huán)時沒有考慮到如果字串與母串相匹配則字串的字母也要向后移動 一個。解決方法：字串同時后移一個如果前一個相匹配。時間復(fù)雜度： o(n2); 經(jīng)驗體會：設(shè)計算法時，即使是很簡單的算法，也不能掉以輕心。五用戶使用說明： 輸入一字符串，換行，再輸入一字符串，再換行，在換

6、行，即可。六運算結(jié)果：七源代碼：#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.停車場管理 一需求分析：問題： 用棧模擬停車場， 汽車到達時記錄下汽車的編號以及進停車場時間， 離開時，記 錄下離開時間并結(jié)算停車費。需要輸入的數(shù)據(jù)： 汽車離開還是到達的信息， 汽車的標(biāo)號， 以及汽車的到達或者離的時 間。需要輸出的數(shù)據(jù)：到達：汽車停在哪里，離開：汽車

8、需要交多少錢。測試數(shù)據(jù)： 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)。 二設(shè)計概要：1. 需要設(shè)計兩個棧，一個作為停車場，一個作為把車退出來時，暫時停車的地方。還需 設(shè)計個隊列，用來停放等進停車場的車。2. 當(dāng)停車場中有空位時，才可以讓其他的車進去，此時，來的車需要在便道上等待。另 外，要車子進停車場時，才計算時間。在棧底的汽車退出來時，棧頂?shù)能囆枰顺?/p>

9、來， 讓棧底汽車退出來，在進入停車場，再從便道上取一輛等待停車的汽車。三詳細(xì)設(shè)計 :1. 汽車需要做成一個結(jié)構(gòu)體或類：class carchar statueinfo;/ 停車狀態(tài)。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()/ 取車的狀態(tài)return statueinfo;int getcarnum()/ 車的編號return carnum;int gettime()/ 車離開或到達的時間return time;void settime(int time)/ 重新設(shè)置時間 this->time=time;void setcarnum(int canum)/ 重新設(shè)置車的編號 this->carnum=carnum;void setcarnum(char statueinfo)/ 重新設(shè)計車的狀態(tài) this->statueinfo=statueinfo;2. 設(shè)計一個棧，用于停車或者暫時存放

11、車輛。class stack:public car/ 棧car *base;car *top;int stacksize;public:stack()/ 初始化 stacksize=200;base=new carstacksize; top=base;stack(int stacksize)/ 設(shè)計一個新的容量的棧 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. 設(shè)計一個隊列，用于存放沒有停車位置的車。 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;四調(diào)試分析：1. 怎樣把車的所有信息綁在一起？解決方法：用一個類。2. 怎樣把車所有的信息壓入棧？解決方法：讓棧直接在 car 的類上進行操作。3. 棧的壓入出現(xiàn)問題，讓 top 指針指向壓入的元素，導(dǎo)致后來總出現(xiàn)聯(lián)機錯誤，不能 輸入數(shù)據(jù)。解決方法：修改 to

14、p 指針的指向。4. 一開始沒有設(shè)隊列，把所有的車停在棧里，后來仔細(xì)看題目，才覺得有點不對。解 決方法：設(shè)隊列時間復(fù)雜度： o(n) 經(jīng)驗體會：做題要仔細(xì)分析，不要信服氣躁。把數(shù)據(jù)壓入棧后，要把指針向上移一個。 五用戶使用說明：首先輸入有幾個停車車位，之后根據(jù)提示輸入即可。六實驗結(jié)果：9七源代碼：#include<iostream>using namespace std;#define STACK_INIT_SIZE 100; #define STACKINCREMMNT 10;class carchar statueinfo;/ 停車狀態(tài)。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()/ 取車的狀態(tài)return statueinfo;int getcarnum()/ 車的編號return carnum;int gettime()/ 車離開或到達的時間return time;void

16、 settime(int time)/ 重新設(shè)置時間 this->time=time;void setcarnum(int canum)/ 重新設(shè)置車的編號 this->carnum=carnum;void setcarnum(char statueinfo)/ 重新設(shè)計車的狀態(tài) 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)/ 設(shè)計一個新的容量的棧 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();/ 當(dāng)它不是停在棧頂，則把其他的車退出來停入另一個棧中 s1.pop();/彈出要離開的車while(s.gettop()!=s.getbase()s1.push(*(s.gettop();s.pop();/ 把退出的車?；厝arthethe14if(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;/ 結(jié)束delete &s1;delete &s;return 0;15實驗 4.程序分析一需求分析 問題：讀入一個 c 程序，統(tǒng)計程序中代碼， 注釋和空行的行數(shù)以及行數(shù)的個數(shù)以及平均 行數(shù)，并利用統(tǒng)計信息分析評價該代碼的風(fēng)格。輸入：一個 c 程序的文件名。 輸出：統(tǒng)計信息以及評價。測試的程序： #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);/輸出結(jié)果 return 0;二概要設(shè)計 :1. 需要用到文件的輸入輸出相關(guān)的知識，當(dāng)遇到n'表示一行，與這種方法計算行數(shù)2. 當(dāng)遇到 '表一注釋

27、行，當(dāng)一行中只有 n'表示空行，還需要設(shè)計一個計算函數(shù) 的函數(shù)來計算程序中共有多少個函數(shù)三詳細(xì)設(shè)計：1.字符串比較的函數(shù)int strc(char a100,char b8,int n)16/字符串的比較。int i;for(i=0;i<n;i+)if(ai!=bi) return i; /返回到第一個不相等的字母的位置。 2.函數(shù)平均長度的評價表。 char G_Cclass(int s)/平均代碼行的等級關(guān)系。 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. 占總行數(shù)比率的評價關(guān)系： char G_ZBclass(double s)/注釋行以及空白行的等級關(guān)系。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. 判斷是不是關(guān)鍵字int CS(ch

30、ar d) /判斷語句的前一個單詞是不是關(guān)鍵詞。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 為標(biāo)志。5. 判斷是不是函數(shù)：int G_F(FILE *fp,char file) /判斷函數(shù)的個數(shù)。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);/關(guān)閉文件。 sa+1=b+1;for(j=0;j<a;j+) n=n+sj+2-sj+1-mj+1;gl=n;/gl 為總的行數(shù)的代碼行。return a;/返回值為總的函數(shù)個數(shù)。6. 主函數(shù)：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 為標(biāo)志 ;else if(c

34、h='/')if(tag=1) zl+;tag+;else tag=1;else tg=0;tag=0; /判斷文件的注釋行與空行的行數(shù)。 fclose(f);/關(guān)閉文件。 fn=G_F(f,filename);/ 計算函數(shù)的個數(shù) fc=G_Cclass(fn);/ 計算平均函數(shù)行數(shù)的等級 al=gl*1.0/fn;/ 計算平均行數(shù)cl=tl-bk-zl;codep=cl*1.0/tl;/ 代碼行占總行數(shù)的比率comp=zl*1.0/tl;/ 注釋行占總行數(shù)的比率 sp=bk*1.0/tl;/ 空白行占總行數(shù)的比率 zc=G_ZBclass(comp);bc=G_ZBclass

35、(sp);/ 計算等級 show(filename,cl,zl,bk,codep,comp,sp,fn,al,fc,zc,bc);/ 打印 return 0;四. 調(diào)試分析： 遇到的問題： 1.不知道怎樣表示空行。解決辦法：設(shè)一個標(biāo)志，當(dāng)遇到一個轉(zhuǎn)行符時，標(biāo)志變成1，當(dāng)標(biāo)志位 1 且再次遇到一個轉(zhuǎn)行符時，則表示遇到一個空行2.文件打不開。解決方法：寫文件名時要寫路徑。3. 怎么計算函數(shù)個數(shù)？解決方法：找關(guān)鍵字及括號。 時間復(fù)雜度： O( 1)20經(jīng)驗體會：知道了怎樣打開文件，不會的要會去找資料，不要遇到一點困難就退縮。五. 用戶使用說明：只要輸入文件名即可，一定要輸路徑和后綴！六. 實驗結(jié)果：

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) /平均代碼行的等級關(guān)系。 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) /注釋行以及空白行的等級關(guān)系。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、詞是不是關(guān)鍵詞。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 為標(biāo)志。int

40、 G_F(FILE *fp,char file) /判斷函數(shù)的個數(shù)。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); /關(guān)閉文件。 sa+1=b+1; for(j=0;j<a;j+) n=n+sj+2-sj+1-mj+1;gl=n;/gl 為總的行數(shù)的代碼行。return a; /返回值為總的函數(shù)個數(shù)。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) /輸出函數(shù)。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,"