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