第一篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告--八皇后（寫寫幫整理）
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
1．實(shí)驗(yàn)要求
實(shí)驗(yàn)?zāi)康模豪脳＝Y(jié)構(gòu)實(shí)現(xiàn)八皇后問題
八皇后問題如下：八皇后問題是19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問題是，在8*8的棋盤上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行，同一列，同一斜線上。
實(shí)驗(yàn)內(nèi)容：利用所學(xué)的棧結(jié)構(gòu)用遞歸或非遞歸解決八皇后問題。
2.程序分析
程序使用程序最主要只是在主函數(shù)用了一個(gè)遞歸函數(shù)Queen。
Queen函數(shù)使用了三個(gè)參數(shù)m,flag[][],chess[][]。其中m是行數(shù)，flag[][]是判斷二維數(shù)組何處可以放置皇后，chess[][]是存儲(chǔ)字符串的二維數(shù)組。
主函數(shù)中對(duì)Queen函數(shù)中的形參數(shù)組flag[][],chess[][]進(jìn)行初始化，在Queen函數(shù)中再進(jìn)行各種操作。
Queen函數(shù)執(zhí)行代碼，首先行數(shù)m為0，當(dāng)m小于7時(shí)，通過if…else…語句，利用Queen(m+1,f,c)重新執(zhí)行遞歸函數(shù)到下一行。
2.1 存儲(chǔ)結(jié)構(gòu)
存儲(chǔ)結(jié)構(gòu)：數(shù)組存儲(chǔ)。
flag[][]數(shù)組存儲(chǔ)數(shù)字判斷輸出和儲(chǔ)能放置皇后,chess[][]數(shù)組存儲(chǔ)字符串即皇后和非皇后的形狀。
2.2 關(guān)鍵算法分析
1、關(guān)鍵算法： a．
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
f[i][j]=0;
c[i][j]='*';
說明：對(duì)棋盤進(jìn)行初始化 未放置皇后的為“*” b．
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
c[i][j]=chess[i][j];
f[i][j]=flag[i][j];
} 說明：對(duì)c[][]，f[][]進(jìn)行初始化。c．
for(i=0;i<8;i++)
for(j=0;j<8;j++)
{
if(f[i][j]==0 &&(i+j==m+k || m==i || k==j || m-k==i-j))
f[i][j]=-1;
}
c[m][k]='#';
說明：已放置皇后的行、列以及對(duì)角線都不能再放置皇后。
已放置皇后的顯示為“#”。d.if(m==7)
{
cout<<“算法的第”<<++count<<“個(gè)解為：”< for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cout< } cout< } cout< cout< return; } else Queen(m+1,f,c); 說明：首先判斷是否已執(zhí)行到最后一行 每輸出一個(gè)算法，count計(jì)數(shù)器加1 若沒有執(zhí)行到最后一行，m+1繼續(xù)執(zhí)行Queen函數(shù) 2.3 其他 要求程序在一開始創(chuàng)建一個(gè)統(tǒng)計(jì)算法解個(gè)數(shù)的加法器。 3.程序運(yùn)行結(jié)果 1、測(cè)試主函數(shù)流程：流程圖如圖所示 2、測(cè)試結(jié)論：輸出解決算法的個(gè)數(shù)及八皇后問題的圖解。 4.總結(jié) 一．問題及解決辦法 1.一開始編的時(shí)候?qū)ν恍?，同一列以及同一斜行不能排皇后的算法不能?zhǔn)確編寫，后來通過畫圖發(fā)現(xiàn)了這三個(gè)情況數(shù)組行標(biāo)和列標(biāo)的特點(diǎn)，從而解決了這個(gè)問題。 2.程序只能輸出從65至99的解，其他解不顯示，后來發(fā)現(xiàn)是因?yàn)榻缑嫣〉脑?。二．心得體會(huì) 對(duì)于剛學(xué)的棧表以及遞歸函數(shù)一定要多用才能熟悉，才能知道實(shí)現(xiàn)的具體細(xì)節(jié)問題。對(duì)一些出現(xiàn)的錯(cuò)誤一點(diǎn)要仔細(xì)分析，明白以后就會(huì)掌握的很牢固。對(duì)于遞歸函數(shù)一定要充分理解它的意義才能用好它。 在編寫代碼中如果對(duì)于一些抽象的算法構(gòu)思感到困難，可以通過畫圖，在紙上先進(jìn)行演算推導(dǎo)出各變量之間的關(guān)系，再進(jìn)行編寫可能會(huì)使問題變得簡(jiǎn)單明了一些。三．改進(jìn) 遞歸算法解決八皇后問題比較簡(jiǎn)單明了，下次可以嘗試不使用遞歸而用非遞歸編寫算法，這樣可能會(huì)更牢固更好的掌握棧的思想，鞏固已學(xué)的知識(shí)。 數(shù)據(jù)結(jié)構(gòu) 實(shí)習(xí)報(bào)告 專業(yè)：數(shù)字媒體技術(shù) 姓名：李義 年級(jí)：2013級(jí) 學(xué)號(hào)：201301052015 完成日期：2015.12.31 題目：八皇后問題 一、項(xiàng)目簡(jiǎn)介 八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8?8格的國際象棋棋盤上，安放八個(gè)皇后，要求沒有一個(gè)皇后能夠“吃掉”任何其他一個(gè)皇后，即任意兩個(gè)皇后都不能處于同一行、同一列或同一條對(duì)角線上，求解有多少種擺法。 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法得出結(jié)論，有92種擺法。 二、概要設(shè)計(jì) 2.1 主要模塊： 這個(gè)程序主要由4個(gè)模塊組成，分別是畫棋盤模塊，畫皇后模塊，輸出皇后擺法模塊，和解決如何擺置皇后模塊。這4個(gè)模塊隸屬于主函數(shù)模塊。既主函數(shù)通過對(duì)這4個(gè)模塊的合理調(diào)用解決“8皇后問題”，同時(shí)這4個(gè)模塊之間也互有調(diào)用。 2.2 程序設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)及其關(guān)系： 數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：數(shù)組a[i]：a [i]表示第i個(gè)皇后放置的列；i的范圍：1-8;對(duì)角線數(shù)組：b[j](主對(duì)角線),c[j]（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后；然后進(jìn)行數(shù)據(jù)的初始化。從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測(cè)試當(dāng)前位置(n,m)是否等于０（未被占領(lǐng)）:如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)(切記要橫列豎列斜列一起來)，接著進(jìn)行遞歸；如果不是，測(cè)試下一個(gè)位置(n,m+1)，但是如果當(dāng)時(shí)，卻發(fā)現(xiàn)此時(shí)已經(jīng)無法擺放時(shí)，便要進(jìn)行回溯。 三、詳細(xì)設(shè)計(jì) 3.1 定義相關(guān)的數(shù)據(jù)類型： 3.1.1 定義的相關(guān)數(shù)據(jù)類型： int A[21],B[21],C[21],Y[8];void *buff1,*buff2 3.1.2 設(shè)計(jì)思想： 本程序通過對(duì)子函數(shù)void qu(int i)的調(diào)用，將八皇后的問題關(guān)鍵通過數(shù)據(jù)結(jié)構(gòu)的思想予以了實(shí)現(xiàn)。雖然題目以及演算看起來都比較復(fù)雜，繁瑣，但在實(shí)際中，只要當(dāng)一只皇后放入棋盤后，在橫與列、斜線上沒有另外一只皇后與其沖突，再對(duì)皇后的定位進(jìn)行相關(guān)的判斷。即可完成。如果在這個(gè)程序中，我們運(yùn)用的是非遞歸的思想，那么將大量使用if等語句，并通過不斷的判斷，去推出答案，而且這種非遞歸的思想，大大的增加了程序的時(shí)間復(fù)雜度。如果我們使用了數(shù)據(jù)結(jié)構(gòu)中的算法后，那么程序的時(shí)間復(fù)雜度，以及相關(guān)的代碼簡(jiǎn)化都能取得不錯(cuò)的改進(jìn)。這個(gè)程序，我運(yùn)用到了數(shù)據(jù)結(jié)構(gòu)中的棧、數(shù)組，以及樹和回溯的方法。特別是在對(duì)于樹以及二叉樹的學(xué)習(xí)，更是為八皇后的問題提供了科學(xué)的解決方案，通過對(duì)樹的分析，把八皇后的問題看成了樹，而在衍生第一個(gè)變化后，上面的第一層八個(gè)變化就變成了八個(gè)結(jié)點(diǎn)，而這八個(gè)結(jié)點(diǎn)再繼續(xù)的衍生??，這樣比較形象的將八皇后的問題簡(jiǎn)單化了。然后再通過回溯法進(jìn)行設(shè)計(jì)，回溯法是設(shè)計(jì)遞歸過程的一個(gè)重要的方法。它的求解過程實(shí)質(zhì)上是一個(gè)先序遍歷一棵“狀態(tài)樹“的過程。在這個(gè)程序設(shè)計(jì)中，它先進(jìn)行判斷，棋盤上是否已經(jīng)得到一個(gè)完整的布局（即棋盤是否已經(jīng)擺上8個(gè)棋子），如果是，則輸出布局；如果不是則依次先根遍歷滿足約束條件的各棵子樹，流程即是： 判斷該子樹根的布局是否合法：如果合法的話，則先根遍歷該子樹；如果不合法的話，則剪去該子樹的分支。 3.2 相關(guān)代碼及算法 3.2.1 主模塊C碼算法： void main(void){ Queen Q; int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,“D://Win-TC”); SetQueen(&Q); setcolor(YELLOW); QueenPic(); cleardevice(); setcolor(LIGHTGREEN); settextstyle(0,0,3); outtextxy(180,10,“Eight Queens”); setcolor(WHITE); settextstyle(0,0,1); outtextxy(250,400,“2009.11.8 3:30pm”); QueenRe(&Q,0); getch(); closegraph();} 3.2.2 棋盤模塊C碼算法 void Checker(void) /* 畫棋盤函數(shù) */ { int i,k; for(k=0;k<8;k++) for(i=0;i<8;i++) if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE); setcolor(LIGHTBLUE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE); setcolor(WHITE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,WHITE);} } 3.2.3 皇后模塊C碼算法： void QueenPic(void) /* 畫皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ { int size，polypoints1[10]={9,1,11,1,20,20,1,20,9,1}，polypoints2[10]={29,1,31,1,40,20,21,20,29,1}; setfillstyle(SOLID_FILL,LIGHTBLUE); /* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE); rectangle(1,1,20,20); floodfill(10,10,LIGHTBLUE); setfillstyle(SOLID_FILL,WHITE); /* 畫白色棋格 */ setcolor(WHITE); rectangle(21,1,40,20); floodfill(30,10,WHITE); setfillstyle(SOLID_FILL,DARKGRAY); setcolor(YELLOW); drawpoly(5,polypoints1); drawpoly(5,polypoints2); floodfill(10,10,YELLOW); floodfill(30,10,YELLOW); size=imagesize(1,1,20,20); /* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */ buff1=(void *)malloc(size); buff2=(void *)malloc(size); getimage(1,1,20,20,buff1); getimage(21,1,40,20,buff2); cleardevice();} 3.2.4 八皇后擺放方法模塊C碼: void QueenRe(Queen *Q, int y) 八皇后的遞歸算法 {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])下一棵要遍歷的子樹由狀態(tài)數(shù)確定 { Q->Y[y]=x;放置皇后 Q->A[x+7]=1;標(biāo)記下次這里不能放置皇后 Q->B[x+y+7]=1;標(biāo)記下次這里不能放置皇后 Q->C[x-y+7]=1;標(biāo)記下次這里不能放置皇后 if(y==7) PrintQueen(Q);調(diào)用輸出圖形函數(shù) QueenRe(Q,y+1);進(jìn)入下一層遞歸 Q->A[x+7]=0;如果上次擺法導(dǎo)致后面不能繼續(xù)擺放則重置標(biāo)記為0 Q->B[x+y+7]=0; Q->C[x-y+7]=0; } } 3.2.5 初始化模塊C碼: void SetQueen(Queen *Q) /* 初始化 */ {int i; for(i=0;i<21;i++) {Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;初始化為0，表示可以放置皇后。} for(i=0;i<8;i++) Q->Y[i]=-1;} 3.2.6 圖形輸出： void PrintQueen(Queen *t) /* 圖形輸出函數(shù) */ {int k; char str[20]; static total=0; total++; setviewport(240,80,400,260,1); /* 設(shè)置窗口 */ sprintf(str,“NO.%d”,total); setcolor(GREEN); settextstyle(0,0,1); outtextxy(0,0,str); Checker(); for(k=0;k<8;k++) if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0) putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);else putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT); getch(); if(getch()==27)exit(0); clearviewport();} void QueenRe(Queen *Q, int y) /* 八皇后的遞歸算法 */ {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍歷的子樹由狀態(tài)數(shù)確定 */ {Q->Y[y]=x; Q->A[x+7]=1; Q->B[x+y+7]=1; Q->C[x-y+7]=1; if(y==7) PrintQueen(Q); QueenRe(Q,y+1); /* 進(jìn)入下一層遞歸 */ Q->A[x+7]=0; Q->B[x+y+7]=0; Q->C[x-y+7]=0;} } } 3.3函數(shù)調(diào)用圖 3.4項(xiàng)目流程圖 通過編譯連接后，程序基本上把八皇后的92種擺法的都進(jìn)行了演示； 但程 四、調(diào)試分析 序運(yùn)行中也出現(xiàn)了以下缺點(diǎn)： 因?yàn)榘嘶屎蟮谋憩F(xiàn)方法甚多，輸出后雖能全部顯示，但未能使屏幕停留，把一個(gè)一個(gè)的將其顯示出來,但是這樣便使得操作步驟太多,也會(huì)造成不必要的麻煩!所以只畫出了第一種和最后一種的輸出結(jié)果，演示如圖所示： 五、設(shè)計(jì)體會(huì) 該程序在調(diào)試的過程中出現(xiàn)了不少的問題！如數(shù)據(jù)溢出等（是自己過于粗心而造成的）。在調(diào)試的過程中出現(xiàn)的一個(gè)最大的問題就是：在運(yùn)行的時(shí)候出現(xiàn)解的個(gè)數(shù)大于自己所預(yù)計(jì)的。經(jīng)過不斷的查看內(nèi)存變量，操作次數(shù)但還是沒有找出問題的所在。終于在晚上十二點(diǎn)的時(shí)候，決定睡覺！但一關(guān)上電腦，躺在床上的時(shí)候，突然想到了一個(gè)問題：經(jīng)過讀了一些資料，知道八皇后問題有12組實(shí)質(zhì)解，92組全解——這說明在這12組實(shí)質(zhì)解中有其中的一組解是比其它的解要特殊一點(diǎn)的：其它的解經(jīng)過等價(jià)的變換之后都會(huì)產(chǎn)生8組等價(jià)的解，只有這個(gè)特殊的解只有4組等價(jià)的解。說不定我的問題就出在這里！我之前也寫了一些有關(guān)的代碼處理這個(gè)問題，但我之前以為這個(gè)特殊的解是一個(gè)完全中心對(duì)稱的圖形（每轉(zhuǎn)90度得到的圖形就是它自己本身），所以我的在這里的判斷就出現(xiàn)錯(cuò)誤了！后來經(jīng)過相關(guān)代碼的修改，問題終于解決了，程序正確運(yùn)行。 本課程設(shè)計(jì)本人的目的也是通過用WIN-TC程序設(shè)計(jì)平臺(tái)將一個(gè)８＊８的棋盤上放上８?jìng)€(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)．最終將其問題變得一目了然，更加易懂。 六、用戶使用說明 6.1 程序的使用平臺(tái)： 系統(tǒng)要求：windows2000以上操作系統(tǒng)； 語言開發(fā)平臺(tái)：WIN-TC； 6.2 源代碼分析： 首先對(duì)程序中的函數(shù)頭文件進(jìn)行引入，定位；在這個(gè)程序中，與其他C++的程序一樣，都是引入：#include 七、附錄 #include void *buff1,*buff2;typedef struct { int A[21],B[21],C[21],Y[8];} Queen;void SetQueen(Queen *Q) /* 初始化 */ { int i;for(i=0;i<21;i++){ Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;} for(i=0;i<8;i++)Q->Y[i]=-1;} void QueenPic(void) /* 畫皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ { int size, polypoints1[10]={9,1,11,1,20,20,1,20,9,1}, polypoints2[10]={29,1,31,1,40,20,21,20,29,1};setfillstyle(SOLID_FILL,LIGHTBLUE); /* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 畫白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();} void Checker(void) /* 畫棋盤函數(shù) */ { int i,k; for(k=0;k<8;k++)for(i=0;i<8;i++)if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);} } void PrintQueen(Queen *t) /* 圖形輸出函數(shù) */ {int k;char str[20];static total=0;total++;setviewport(240,80,400,260,1); /* 設(shè)置窗口 */ sprintf(str,“NO.%d”,total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k<8;k++)if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍歷的子樹由狀態(tài)數(shù)確定 */ {Q->Y[y]=x;Q->A[x+7]=1;Q->B[x+y+7]=1;Q->C[x-y+7]=1;if(y==7)PrintQueen(Q);QueenRe(Q,y+1); /* 進(jìn)入下一層遞歸 */ Q->A[x+7]=0;Q->B[x+y+7]=0;Q->C[x-y+7]=0;} } void main(void){ Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,“D://Win-TC”);SetQueen(&Q);setcolor(YELLOW);QueenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,“Eight Queens”);setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,“2009.11.8 3:30pm”);QueenRe(&Q,0);getch();closegraph();} 注意：實(shí)驗(yàn)結(jié)束后提交一份實(shí)驗(yàn)報(bào)告電子文檔 電子文檔命名為“學(xué)號(hào)+姓名”，如：E01214058宋思怡 《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告 （一）學(xué)號(hào)：姓名：專業(yè)年級(jí)： 實(shí)驗(yàn)名稱：線性表 實(shí)驗(yàn)日期：2014年4月14日 實(shí)驗(yàn)?zāi)康模?/p> 1、熟悉線性表的定義及其順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)； 2、熟練掌握線性表在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法； 3、熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表基本操作的方法； 4、掌握用 C/C++語言調(diào)試程序的基本方法。 實(shí)驗(yàn)內(nèi)容： 一、編寫程序?qū)崿F(xiàn)順序表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能： （1）初始化順序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）輸出順序表L； （4）輸出順序表L長度； （5）判斷順序表L是否為空； （6）輸出順序表L的第3個(gè)元素； （7）輸出元素24的位置； （8）在L的第4個(gè)元素前插入元素0； （9）輸出順序表L； （10）刪除L的第5個(gè)元素； （11）輸出順序表L。 源代碼 調(diào)試分析（給出運(yùn)行結(jié)果界面） 二、編寫程序?qū)崿F(xiàn)單鏈表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能： ???? ???? 小結(jié)或討論: （1）實(shí)驗(yàn)中遇到的問題和解決方法 （2）實(shí)驗(yàn)中沒有解決的問題 （3）體會(huì)和提高 南京信息工程大學(xué)實(shí)驗(yàn)（實(shí)習(xí)）報(bào)告 實(shí)驗(yàn)（實(shí)習(xí)）名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)（實(shí)習(xí)）日期 2011-11-2得分指導(dǎo)教師周素萍 系公共管理系專業(yè)信息管理與信息系統(tǒng)年級(jí)10級(jí)班次1姓名常玲學(xué)號(hào)2010230700 3實(shí)驗(yàn)一順序表的基本操作及C語言實(shí)現(xiàn) 【實(shí)驗(yàn)?zāi)康摹?/p> 1、順序表的基本操作及 C 語言實(shí)現(xiàn) 【實(shí)驗(yàn)要求】 1、用 C 語言建立自己的線性表結(jié)構(gòu)的程序庫，實(shí)現(xiàn)順序表的基本操作。 2、對(duì)線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應(yīng)的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個(gè)集合的并的結(jié)果存儲(chǔ)在一個(gè)新的線性表集合中，并輸出。 【實(shí)驗(yàn)內(nèi)容】 1、根據(jù)教材定義的順序表機(jī)構(gòu)，用 C 語言實(shí)現(xiàn)順序表結(jié)構(gòu)的創(chuàng)建、插入、刪除、查找等操作； 2、利用上述順序表操作實(shí)現(xiàn)如下程序：建立兩個(gè)順序表表示的集合（集合中無重 復(fù)的元素），并求這樣的兩個(gè)集合的并。 【實(shí)驗(yàn)結(jié)果】 [實(shí)驗(yàn)數(shù)據(jù)、結(jié)果、遇到的問題及解決] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的編號(hào)從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 將合并逆置后的結(jié)果放在C表中，并刪除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅(qū)指針 // 保存pb的前驅(qū)指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲(chǔ)在數(shù)組中，元素之間的關(guān)系直接通過相鄰元素的位置來表達(dá)。 優(yōu)點(diǎn)：簡(jiǎn)單，數(shù)據(jù)元素的提取速度快； 缺點(diǎn)：（1）靜態(tài)存儲(chǔ)，無法預(yù)知問題規(guī)模的大小，可能空間不足，或浪費(fèi)存儲(chǔ)空間；（2）插入元素和刪除元素時(shí)間復(fù)雜度高——O（n） 求兩個(gè)集合的并集 該算法是求兩個(gè)集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復(fù)制到s中，然后把s2中的每個(gè)元素依次插入到集合s中，當(dāng)然重復(fù)的元素不應(yīng)該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對(duì)應(yīng)的實(shí)際參數(shù)集合中得到并集。 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 一． 題目要求 1）編程實(shí)現(xiàn)二叉排序樹，包括生成、插入，刪除； 2）對(duì)二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷； 3）每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信息(至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng)),對(duì)比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對(duì)于前三個(gè)題目要求，我們用一個(gè)程序?qū)崿F(xiàn)代碼如下 #include typedefintElemType; //數(shù)據(jù)類型 typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//創(chuàng)建二叉樹函數(shù) BiTreebst=NULL;inti=0;while(i //數(shù)據(jù)域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子樹為空重接它的左子樹 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子樹空則重新接它的右子樹 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被刪除結(jié)點(diǎn)的前驅(qū) if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數(shù)，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函數(shù) printf(“ ---------------------二叉排序樹的實(shí)現(xiàn)-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節(jié)點(diǎn)個(gè)數(shù):”);scanf(“%d”,&num);printf(“依次輸入這些整數(shù)（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創(chuàng)建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示輸入操作符************************:”);printf(“n”);printf(“ 1:插入節(jié)點(diǎn) 2:刪除節(jié)點(diǎn) 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節(jié)點(diǎn):”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“樹狀圖為:n”); printtree(bst,layer); break; case 2: } printf(“輸入要?jiǎng)h除的節(jié)點(diǎn)”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst); printf(“后序遍歷:n”); PostOrderNoRec(bst); printf(“樹狀圖為:n”); printtree(bst,layer); break;case 5: printf(“程序執(zhí)行完畢!”); return 0;} goto loop;} return 0;對(duì)于第四小問，要儲(chǔ)存學(xué)生的三個(gè)信息，需要把上面程序修改一下，二叉樹結(jié)構(gòu)變?yōu)?typedefintElemType; //數(shù)據(jù)類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數(shù)據(jù)域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數(shù)不是key,而是另外三個(gè) intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數(shù) if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含參函數(shù)也類似 即可完成50個(gè)信息存儲(chǔ) 用數(shù)組存儲(chǔ)50個(gè)信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學(xué)生管理系統(tǒng)”< cout<<“該學(xué)號(hào)信息已經(jīng)存在，添加失敗”< break;} cout<<“重新輸入添加的學(xué)號(hào)”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“謝謝使用”< 二叉排序樹儲(chǔ)存數(shù)據(jù)界面（儲(chǔ)存學(xué)生信息略） 創(chuàng)建二叉樹： 插入節(jié)點(diǎn)： 刪除節(jié)點(diǎn)： 非遞歸遍歷： 退出： 數(shù)組儲(chǔ)存學(xué)生信息界面 分析查找效率： 因?yàn)槎鏄洳檎乙獎(jiǎng)?chuàng)建二叉樹，而數(shù)組查找只創(chuàng)建一個(gè)數(shù)組，二叉樹的創(chuàng)建時(shí)間比較長，所以對(duì)于數(shù)據(jù)量較少的情況下數(shù)組的查找效率比較高。但當(dāng)數(shù)據(jù)量增加時(shí)，二叉樹的查找優(yōu)勢(shì)就顯現(xiàn)出來。所以數(shù)據(jù)量越大的時(shí)候，二叉樹的查找效率越高。 四． 總結(jié)與改進(jìn) 這個(gè)實(shí)驗(yàn)工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進(jìn)。 一開始打算用棧實(shí)現(xiàn)非遞歸，但是根據(jù)書里面的偽代碼發(fā)現(xiàn)部分是在C++編譯器里運(yùn)行不了的（即使補(bǔ)充了頭文件和數(shù)據(jù)的定義），所以之后參考了網(wǎng)上的數(shù)組非遞歸，發(fā)現(xiàn)其功能和棧相似。 遞歸遍歷的實(shí)現(xiàn)比非遞歸的遍歷真的簡(jiǎn)單很多。 開始時(shí)只看到前三問，所以沒有寫到儲(chǔ)存學(xué)生數(shù)據(jù)的代碼，里面還可以用clock（）函數(shù)加一個(gè)計(jì)算查找所要數(shù)據(jù)時(shí)間的代碼，讓二叉樹查找與數(shù)組查找到效率比較更加直觀。第二篇：數(shù)據(jù)結(jié)構(gòu)八皇后問題實(shí)習(xí)報(bào)告（寫寫幫整理）
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告
點(diǎn)擊咨詢 