數據結構實驗報告-魔方陣

1、 實驗報告實驗名稱：（一）魔方陣（二）本科生導師制問題實驗類型：設計性實驗班級：20100631學號：2010063114姓名：萬星含（一）魔方陣1.問題描述魔方陣是一個古老的智力問題，它要求在一個m×m的矩陣中填入1m2的數字（m為奇數），使得每一行、每一列、每條對角線的累加和都相等，如圖1所示。 基本要求l輸入魔方陣的行數m，要求m為奇數，程序對所輸入的m作簡單的判斷，如m有錯，能給出適當的提示信息。l實現魔方陣。l輸出魔方陣。實現提示本實驗使用的數據結構是數組。解魔方陣問題的方法很多，這里采用如下規(guī)則生成魔方陣。l由1開始填數，將1放在第0行的中間位置。l將魔方陣想象成上下、左

2、右相接，每次往左上角走一步，會有下列情況：²左上角超出上方邊界，則在最下邊相對應的位置填入下一個數字；²左上角超出左邊邊界，則在最右邊相應的位置填入下一個數字；²如果按上述方法找到的位置已填入數據，則在同一列下一行填入下一個數字。以3×3魔方陣為例，說明其填數過程，如圖2所示。 由三階魔方陣的生成過程可知，某一位置(x,y)的左上角的位置是(x-1,y-1),如果x-10，不用調整，否則將其調整為x-1+m；同理，如果y-10，不用調整，否則將其調整為y-1+m。所以，位置(x,y)的左上角的位置可以用求模的方法獲得，即：x=(x-1+m)%my=(y-

3、1+m)%m如果所求的位置已經有數據了，將該數據填入同一列下一行的位置。這里需要注意的是。此時的x和y已經變成之前的上一行上一列了，如果想變回之前位置的下一行同一列，x需要跨越兩行，y需要跨越一列，即：x=(x+2)%my=(y+1)%m思考l可以考慮使用其他方法生成魔方陣。任何算法都有不同的實現方法，通過采用不同實現方法來重新實現算法，這要比單純學習算法的效果好得多。2.實驗要求（1） 認真閱讀和掌握和本實驗相關的教材內容、算法和設計程序。（3） 上機運行程序。（4） 保存和打印出程序的運行結果，并結合程序進行分析。3.實驗目的（1）設計數據結構；（2）設計算法完成任意n階魔方陣的填數；（3

4、）分析算法的時間復雜度。4. 程序源代碼#include <stdio.h>#include <stdlib.h>#define MAX_NUM 500 /*這里可以修改最大階*/int main() int rows = 0, center = 0, iArrayMAX_NUMMAX_NUM; int RowSet = 0, LineSet = 0, newRowSet = 0, newLineSet = 0; int i = 0, j = 0; int okNum = 0; / set the items of array "iArray" to

5、 be 0 for ( i = 0; i < MAX_NUM; i+ ) for ( j = 0; j < MAX_NUM; j+ ) iArrayij = 0; / get the rows number while ( 1 ) printf("輸入行數:n"); scanf("%d", &rows); if ( rows <= MAX_NUM ) rows -= 1; break; else printf("行數必須在 0 和 %d 之間, 請重新", MAX_NUM); / set number 

6、9;1' center = rows / 2; iArray0center = 1; / initialize the okNum, RowSet and LineSet okNum = 1; RowSet = 0; LineSet = center; / set each item in "iArray" while ( okNum < (rows + 1) * (rows + 1) ) if ( RowSet = 0 && LineSet = rows ) RowSet += 1; else newRowSet = (RowSet = 0)

7、 ? rows : RowSet - 1; newLineSet = (LineSet = rows) ? 0 : LineSet + 1; if ( iArraynewRowSetnewLineSet != 0 ) / there is already a number here! RowSet = (RowSet = rows) ? 0 : RowSet + 1; /RowSet += 1; else RowSet = newRowSet; LineSet = newLineSet; iArrayRowSetLineSet = +okNum; / print the "iArra

8、y" for ( i = 0; i <= rows; i+ ) for ( j = 0; j <= rows; j+ ) printf("%5d", iArrayij); printf("n"); system("pause"); return 0; 6.調試結果（2） 本科生導師制問題1.問題描述在高校的教學改革中，有很多學校實行了本科生導師制。一個班級的學生被分給幾個老師，每個老師帶n個學生，如果該老師還帶研究生，那么研究生也可直接帶本科生。本科生導師制問題中的數據元素具有如下形式：l導師帶研究生（老師，（研

9、究生1，（本科生1，本科生m1），（研究生2，（本科生1，本科生m2）l導師不帶研究生（老師，（本科生1，本科生m）導師的自然情況只包括姓名、職稱；研究生的自然情況只包括姓名、班級；本科生的自然情況只包括姓名、班級?；疽笠笸瓿梢韵鹿δ埽簂建立：建立導師廣義表。l插入：將某位本科生或研究生插入到廣義表的相應位置。l刪除：將某本科生或研究生從廣義表中刪除。l查詢：查詢導師、本科生（研究生）的情況。l統(tǒng)計：某導師帶了多少個研究生和本科生。l輸出：將某導師所帶學生情況輸出。l退出：程序結束。2.設計思路 本實驗使用的數據結構是廣義表，廣義表采用頭尾鏈表存儲結構來實現。定義教師、學生結點結構體如下

10、：typedef struct GLNode char name100; /*教師或學生的姓名*/ char prof100; /*教師結點表示職稱，學生結點表示班級*/ int type; /*結點類型：0-教師，1-研究生，2-本科生*/struct struct GLNode *hp, *tp; ptr; /*hp指向同級的下一結點，tp指向下級的首結點*/GList;人員信息的表示形式為：高老師-教授-0、李剛-二班-1、李明-二班-2.人員信息中的姓名、職稱、班級、人員類型用“-”隔開，如高老師-教授-0，“高老師”表示姓名，“教師”表示職稱，“0”表示人員的類型是教師；李剛-二班-

11、1，“李剛”表示姓名，“二班”表示班級，“1”表示人員的類型是研究生；李明-二班-2，“李明”表示姓名，“二班”表示班級，“2”表示人員的類型是本科生。廣義表（高老師-教授-0，（李明-一班-2，王平-二班-2），（李老師-副教授-0，（白梅-二班-1，（李剛-一班-2）可以用圖3表示。 3. 功能要求 要求完成以下功能： 插入：將某位本科生或研究生插入到廣義表的相應位置； 刪除：將某本科生或研究生從廣義表中刪除； 查詢：查詢導師、本科生（研究生）的情況； 統(tǒng)計：某導師帶了多少個研究生和本科生； 輸出：將某導師所帶學生情況輸出。4. 源代碼#include <stdio.h>#in

12、clude <string.h>#include <malloc.h>typedef char DataType;#include "GList.h"void main() char str1="(a,b,c),(d),e)" char str2="(a,b,c),(d),e)" char hstr100; GLNode *h, *p; int depth, number, length; h=CreatGList(str1); printf("廣義表str1=%s",str2); Deco

13、mposeStr(str2, hstr); printf("n表頭=%s",hstr); printf(" 表尾=%s",str2); depth=GListDepth(h); printf("n深度depth=%d",depth); length=GListLength(h); printf("n深度length=%d", length); number=GListAtomNum(h); printf("n原子元素個數number=%d", number); p=GListSearch(h,&

14、#39;d'); if (p!=NULL) printf("n數據元素%c在廣義表中", p->val.atom); else printf("n廣義表中不存在要查找的數據元素n"); DestroyGList(h);頭文件：typedef struct GListNodeint tag; union DataType atom; /原子元素域 struct subGL struct GListNode *head; /頭指針 struct GListNode *tail; /尾指針 subList; /子表域 val;GLNode;voi

15、d DecomposeStr(char str, char hstr) int i, j, tag, n = strlen(str); char ch; ch = str0; tag = 0; for(i = 0; i <= n-1; i+) if(stri = ',' && tag = 1 ) break;/搜索最外層的第一個逗號 ch = stri; if(ch = '(') tag+; if(ch = ')') tag-; if(i <= n-1 && stri = ',') /廣

16、義表表尾部分非空時 for(j = 0; j < i-1; j+) hstrj = strj+1;/取表頭字符串 hstrj = '0' /添加結束符 if(stri = ',') i+; str0 = '(' /添'(' for(j = 1; i <= n-2; i+, j+) strj = stri; /取表尾字符串 strj = ')' /添')' str+j = '0' /添加結束符 else /廣義表表尾部分空時 str+; /路過最左邊的'('

17、 strncpy(hstr,str, n-2);/不復制右邊的')' hstrn-2 = '0' /添加結束符 str-; /恢復字符串指針位置 strcpy(str, "()"); /表尾部分為空 GLNode* CreatGList(char str) GLNode *h; char hstr200; int len = strlen(str); if(strcmp(str, "()") = 0) h = NULL; else if(len = 1) /建立原子結點 h = (GLNode *)malloc(sizeo

18、f(GLNode); h->tag = 0; h->val.atom = str0; else /建立子表 h = (GLNode *)malloc(sizeof(GLNode); h->tag = 1; DecomposeStr(str, hstr); h->val.subList.head = CreatGList(hstr); if(strcmp(str, "()") != 0) /表尾非空時 h->val.subList.tail = CreatGList(str); else h->val.subList.tail = NULL

19、; /賦值空指針 return h;int GListDepth(GLNode *h) int max, dep; GLNode *pre; if(h = NULL) return 1;/遞歸出口，空表深度為1 if(h->tag = 0) return 0; /遞歸出口，原子元素深度為0/遞歸求廣義表深度 pre = h; for(max = 0; pre != NULL; pre = pre->val.subList.tail) dep = GListDepth(pre->val.subList.head); /求表頭深度 if(dep > max) max = d

20、ep; return max + 1; int GListLength(GLNode *h) int number = 0; GLNode *p; for(p = h; p != NULL; p = p->val.subList.tail) number+; return number; int GListAtomNum(GLNode *h) if(h = NULL) return 0; else if(h->tag = 0) return 1; else return GListAtomNum(h->val.subList.head) + GListAtomNum(h->val.subList.tail); GLNode *GListSea