算法與數(shù)據(jù)結(jié)構(gòu)

1、12014 年秋季學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 課程設(shè)計課程設(shè)計題 目：集合運算問題、計算 1 的個數(shù)問題、 方程求解問題、圖的基本操作與實現(xiàn)2目目 錄錄摘摘 要要.3一集合運算問題一集合運算問題.41.采用類語言定義相關(guān)的數(shù)據(jù)類型.42.算法設(shè)計.43.函數(shù)的調(diào)用關(guān)系圖.64.調(diào)試分析.75.測試結(jié)果.76.源程序（帶注釋）.8二二計算計算 1 1 的個數(shù)的個數(shù)問題問題.131.數(shù)據(jù)結(jié)構(gòu).132.算法設(shè)計.143.調(diào)試分析.144.測試結(jié)果.145.源程序（帶注釋）.14三方程求解問題三方程求解問題.151.采用類語言定義相關(guān)的數(shù)據(jù)類型.152.算法設(shè)計.153函數(shù)的調(diào)用關(guān)系圖.154

2、.調(diào)試分析.155.測試結(jié)果.166.源程序（帶注釋）.16四四. .圖的基本操作與實現(xiàn)圖的基本操作與實現(xiàn) 171.數(shù)據(jù)結(jié)構(gòu) . 182.算法設(shè)計 183.運行結(jié)果 204.源程序（帶注釋） 20總總 結(jié)結(jié).25參考文獻(xiàn)參考文獻(xiàn).26致致 謝謝.263摘摘 要要第一個程序是編寫算法實現(xiàn)集合的相關(guān)操作包括集合的輸入、輸出、刪除集合中重復(fù)的元素、刪除、修改，求兩個集合的交、并、差。采用單鏈表對集合進(jìn)行操作、運行等。需要用到二叉樹思想、便利線性表和雙重循環(huán)結(jié)構(gòu)等完成問題。第二個程序是遞歸結(jié)構(gòu)計算 1 的個數(shù)問題，共分為兩種情況，奇數(shù)情況和偶數(shù)情況。第三個程序為方程求解問題，用 c 語言實現(xiàn)方程 A5

3、+B5+C5+D5+E5=F5剛好有一個滿足 0ABCDEF75 的整數(shù)解的問題。也可以將生活中的實際問題轉(zhuǎn)換成此類方程的求解，這樣進(jìn)行程序的迭代和功能的更新，就可以實現(xiàn)更多未知數(shù)、更高次、更多解的方程求解問題，和涉及此類方程求解的實際問題。第四個程序為圖的一些基本操作，內(nèi)容包括圖的存儲結(jié)構(gòu)、圖的深度優(yōu)先遍歷，廣度優(yōu)先遍歷，圖節(jié)點的度數(shù)等等。關(guān)鍵詞：關(guān)鍵詞： 集合，單鏈表，遞歸，替換，連通圖集合，單鏈表，遞歸，替換，連通圖 ，方程求解，數(shù)據(jù)結(jié)構(gòu)，圖，方程求解，數(shù)據(jù)結(jié)構(gòu)，圖的遍歷的遍歷4一集合運算問題一集合運算問題設(shè)計一個程序，實現(xiàn)兩個集合的并集、交集、差集、顯示輸出等，要求結(jié)果集合中的元素不重

4、復(fù)；實現(xiàn)一個集合的冪集的求解。1 1. .采采用用類類語語言言定定義義相相關(guān)關(guān)的的數(shù)數(shù)據(jù)據(jù)類類型型定義一個結(jié)構(gòu)體存儲結(jié)構(gòu)，用來生成求冪集的二叉樹只在求冪集函數(shù)內(nèi)使用 typedef struct /根節(jié)點結(jié)構(gòu)體（冪集使用） int dataMAX; int length; root; 定義一個二維數(shù)組，用來存儲節(jié)點選擇情況，其第一個下標(biāo)表示是左孩子還是右孩子，第二個表示節(jié)點當(dāng)前所處的層數(shù)int c2MAX; /c 構(gòu)造數(shù)據(jù)池2.2.算法設(shè)計算法設(shè)計1.并集：用兩個循環(huán)結(jié)構(gòu)為并集賦值，最后進(jìn)行重復(fù)元素檢查（check（） ） 。 for(i=0;in;i+) /A集合賦值 ci=ai; for(

5、i=0;i=m;i+) /B 集合賦值 cn+i=bi; k=n+m; /集合大小 k=check(c,k); /集合重復(fù)元素檢查 2.利用雙重循環(huán)判斷元素是否在 A、B 里面均存在，存在則賦值在 C 里面 for(i=0;i=n;i+) /在 A 里面檢查 for(j=0;j=m;j+) /在 B 里面檢查5 if(ai=bj) /元素在 A 和 B 里面均出現(xiàn) ck=ai; /賦值 k+; /C 集合容量加1 printf( %d,ck-1); /屏幕輸出 3.利用雙重循環(huán)判斷只在 A 里面出現(xiàn)過的元素，并把它們賦值到 C 里面 for(i=0;i=n;i+) /在 A 里面檢查 for(

6、j=0;jdatak=d; b-length+; k+; if(k=n) /遞歸建樹 shu(n,b,c1k,k); /左孩子 shu(n,b,-1,k); /右孩子 else printf(); for(i=0;idatai!=-1) printf(%d ,b-datai); printf(); printf(n); return 0; 3.3.函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖Union_set()Esit(o)Occur()MainShu()Difference_set()Power_set()Union_set()Esit(o)Occur()Main74.4.調(diào)試分析調(diào)試分析a、輸入集合

7、數(shù)據(jù)的時候必須要一個一個輸，不能依次輸入很多，否則會引起錯誤b、算法的時間復(fù)雜度 O(n2） 。5.5.測試結(jié)果測試結(jié)果輸入集合：并集：交集：8差集：6.6.源程序（帶注釋）源程序（帶注釋）#include#define MAXSIZE 10/線性表的最大長度typedef int ElemType;typedef struct/線性表的結(jié)構(gòu)體ElemType dataMAXSIZE;int length;SqList;/線性表的操作函數(shù) /void InitList(SqList *L)/初始化線性表L-data=NULL;L-length=0;int ListInsert(SqList *

8、L,int i,ElemType e) /向表中插入元素int k;if(ilength)/如果不在表尾插入for(k=L-length-1;k=i-1;k-)L-datak+1=L-datak;L-datai-1=e;L-length+;return 1;9else/如果在表尾插入L-datai-1=e;L-length+;return 1;void ErgList(SqList *L) /遍歷線性表并依次返回元素int j;ElemType res_date;for(j=0;jlength;j+)res_date=L-dataj;printf(%4d,res_date);printf(n)

9、;/該程序的操作函數(shù) /int menu()/菜單函數(shù)int m_cho;system(cls);printf(-MENU-n);printf(1-給集合L1和集合L2添加元素n);printf(2-查看集合L1，L2n);printf(3-求L1與L2的并集n);printf(4-求L1與L2的交集n);printf(5-求L1與L2的差集n);printf(6-求L1的冥集n);printf(7-求L2的冥集n);printf(8-退出系統(tǒng)n);printf(-n);printf(-請輸入序號: bb);scanf(%d,&m_cho);if(1=m_cho&m_cho=6

10、)return m_cho;elsesystem(cls);exit();return 0;void operate1(SqList *L1,SqList *L2)/處理序號1int i;ElemType ins_e5;printf(請輸入集合L1中的元素(僅限整數(shù)):n);10for(i=0;i5;i+)/接受集合L1的元素scanf(%d,&ins_ei);ListInsert(L1,i+1,ins_ei);printf(請輸入集合L2中的元素(僅限整數(shù)):n);for(i=0;i5;i+)/接受集合L2的元素scanf(%d,&ins_ei);ListInsert(L2,

11、i+1,ins_ei);void operate2(SqList *L1,SqList *L2)/處理序號2printf(-查看元素-n);printf(集合L1：);ErgList(L1);printf(集合L2：);ErgList(L2);printf(-n);void operate3(SqList *L1,SqList *L2,SqList *L3)/處理序號3int i,j;InitList(L3);/初始化L3*L3=*L1;for(i=0;ilength;i+)/將L2中的元素放入L3中且無重復(fù)元素for(j=0;jlength;j+)if(L3-dataj=L2-datai)/

12、選擇存在于L2但不存在于L3的元素break;elseif(j=L3-length-1)ListInsert(L3,L3-length+1,L2-datai);elsecontinue;printf(-求并集結(jié)果-n);ErgList(L3);printf(-n);void operate4(SqList *L1,SqList *L2,SqList *L3)/處理序號4int i,j;ElemType res_date;InitList(L3);/初始化L3for(i=0;ilength;i+)/將屬于L1同時也屬于L211的元素賦值給L3res_date=L1-datai;for(j=0;j

13、length;j+)if(res_date=L2-dataj)L3-dataL3-length=res_date;L3-length+;break;printf(-求交集結(jié)果-n);ErgList(L3);printf(-n);void operate5(SqList *L1,SqList *L2,SqList *L3)/處理序號5int i,j;ElemType res_date;InitList(L3);/初始化L3for(i=0;ilength;i+)/將屬于L1但不屬于L2的元素賦值給L3res_date=L1-datai;for(j=0;jlength;j+)if(res_date=

14、L2-dataj)break;elseif(j=L2-length-1)L3-dataL3-length=res_date;L3-length+;elsecontinue;printf(-求差集結(jié)果-n);ErgList(L3);printf(-n);void operate6(SqList *L1,SqList *L3) /處理序號6void operate7(SqList *L2,SqList *L3) /處理序號7int main()12int c;char res;SqList L1,L2,L3;/定義線性表L1，L2，L3InitList(&L1);/初始化線性表InitLi

15、st(&L2);InitList(&L3);start: c=menu();switch(c)/處理所選的操作case 1:operate1(&L1,&L2);printf(元素輸入成功！0_0n);printf(按ENTER 鍵返回. . .);scanf(%c,&res);scanf(%c,&res);goto start;case 2:operate2(&L1,&L2);printf(元素查看成功！0_0n);printf(按ENTER 鍵返回. . .);scanf(%c,&res);scanf(%c,&r

16、es);goto start;case 3:operate3(&L1,&L2,&L3);printf(L1與L2求并集成功！0_0n);printf(按ENTER 鍵返回. . .);scanf(%c,&res);scanf(%c,&res);goto start;case 4:operate4(&L1,&L2,&L3);printf(L1與L2求交集成功！0_0n);printf(按ENTER 鍵返回. . .);scanf(%c,&res);scanf(%c,&res);goto start;case 5:op

17、erate5(&L1,&L2,&L3);printf(L1與L2求差集成功！0_0n);printf(按ENTER 鍵返回. . .);13scanf(%c,&res);scanf(%c,&res);goto start;case 6:operate6(&L1,&L3);printf(求L1的冥集成功！0_0n);printf(按ENTER 鍵返回. . .);scanf(%c,&res);scanf(%c,&res);goto start;case 7:operate7(&L2,&L3);printf(求

18、L2的冥集成功！0_0n);printf(按ENTER 鍵返回. . .);scanf(%c,&res);scanf(%c,&res);goto start;return 0;2 2計算計算 1 1 的個數(shù)問題的個數(shù)問題計算 1 的個數(shù)問題。編寫遞歸程序，返回十進(jìn)制數(shù) N 的二進(jìn)制表示中 1 的個數(shù)。1.1.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)int count()/*計算 1 的個數(shù)*/long N;/*輸入的十進(jìn)制數(shù)*/142.2.算法設(shè)計算法設(shè)計int count(long N)/*計算 1 的個數(shù)*/if(N=0)return 0;else if(N%2=1)return (count(N

19、/2)+1);else return count(N/2); main() count()153.3.調(diào)試分析調(diào)試分析4.4.測試結(jié)果測試結(jié)果5.5.源程序（帶注釋）源程序（帶注釋）#include stdio.hint count(long N)/*計算 1 的個數(shù)*/if(N=0)return 0;else if(N%2=1)return (count(N/2)+1);else return count(N/2);void main()long N;printf(Enter N:);scanf(%d,&N);16printf(%dn,count(N);三方程求解問題三方程求解問題方

20、程 A5+B5+C5+D5+E5=F5剛好有一個滿足 0ABCDEF75 的整數(shù)解。請編寫一個求出該解的程序。1.1.采用類語言定義相關(guān)的數(shù)據(jù)類型采用類語言定義相關(guān)的數(shù)據(jù)類型將 ABCDEF 的五次方的值儲存在數(shù)組 p中2.2.算法設(shè)計算法設(shè)計首先建立數(shù)組，用來存儲整型 ABCDEF 五次方的值，然后利用 fo 嵌套循環(huán)，一次求 ABCDEF 五次方的值，接下來用 if 判斷語句，若 ABCDE 次方之和與 F 五次方的差為零，輸出 ABCDEF 的整數(shù)解。3 3函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖4.4.調(diào)試分析調(diào)試分析運行程序，是否可以輸出 ABCDEF 的整數(shù)解。程序沒有什么大問題，可以直接

21、運行，調(diào)試之后運行直接將小于 75 的所有可能整數(shù)解全部給出來。5.5.測試結(jié)果測試結(jié)果可以輸出 ABCDEF 的所有可能的整數(shù)解。運行結(jié)果：Key 函數(shù)Main 函數(shù)176.6.源程序（帶注釋）源程序（帶注釋）#include#include int key() /求方程的解 找到解返回否則返回 long p76; long A,B,C,D,E,F,i,flag=0; for(i=0;i=75;i+) pi=int(pow(i,5); /把的次方放在數(shù)組中，以便調(diào)用 for(A=0;A=60;A+) /循環(huán)窮舉找到方程的解 for(B=A;B=75;B+) for(C=B;C=75;C+)

22、for(D=C;D=75;D+) for(E=D;E=75;E+) for(F=E;F=75;F+) if(pA+pB+pC+pD+pE-pF=0) 18 printf(ttt%d5+%d5+%d5+%d5+%d5=%d5nn,A,B,C,D,E,F); printf(ttt%d %d %d %d %d %dnn,A,B,C,D,E,F); flag=1; if(flag=1) return 1; else return 0; int main() if(key()=0) printf(方程 A5+B5+C5+D5+E5=F5(0=A=BC=D=E=F只須將矩陣中第 i 行 j 列的元素改為

23、1 或相應(yīng)的權(quán)值即可。 2 鄰接表 ：一種鏈?zhǔn)酱鎯Y(jié)構(gòu)在鄰接表中對圖的每個頂點建立一個單鏈表，第 i 個單鏈表中包含第 i 個頂點的所有鄰接點，每一個單鏈表包含兩種結(jié)點，頭結(jié)點和表結(jié)點。在圖的鄰接表中，可以比較方便地查找一個頂點的邊（出邊）或鄰接點（出邊鄰接點），這只要首先從表頭向量中取出對應(yīng)的表頭指針，然后從表頭指針出發(fā)進(jìn)行查找即可。鄰接表則是以一數(shù)組(結(jié)構(gòu)體數(shù)組)的元素作為頭指針,后面鏈接和它相鄰的結(jié)點.3 鄰接矩陣表示法與鄰接表表示法的比較： 1）鄰接矩陣是唯一的，鄰接表不唯一； 2）存儲稀疏圖用鄰接表，存儲稠密圖用鄰接矩陣； 3）求無向圖頂點的度都容易，求有向圖頂點的度鄰接矩陣較方便；

24、 4）判斷是否是圖中的邊，鄰接矩陣容易，鄰接表最壞時間為 O(n)； 5）求邊數(shù) e，鄰接矩陣耗時為 O(n2)，與 e 無關(guān)，鄰接表的耗時2.2. 算法設(shè)計算法設(shè)計(1).鄰接矩陣存儲圖的基本思路：圖用鄰接矩陣表示后圖的某些操作的實現(xiàn)是很方便的，如求某一頂點 vi的第一鄰接點，只需在第 i 行找到第 1 個非零元即可。若求某一頂點 vi的度，對于無向圖來說，只須統(tǒng)計第 i 行的非零元個數(shù)或第 i 列的非零元個數(shù)（無向圖的鄰接矩陣是對稱的）；對于有向圖來說，第 i 行的非零元個數(shù)為該頂點的出度，第 i 列的非零元個數(shù)為該頂點的入度，兩者相加為該頂點的度。當(dāng)圖中頂點數(shù)確定，插入一條邊（vi,vj

25、）只須將矩陣中第 i 行 j 列和第 j 行 i 列的元素分別20改為 1 或相應(yīng)的權(quán)值；插入一條弧 i,vj只須將矩陣中第 i 行 j 列的元素改為 1或相應(yīng)的權(quán)值即可。（2）.鄰接表存儲圖的基本思路：若無向圖中有 n 個頂點 e 條邊，則鄰接表需要 n 個頭結(jié)點和 2e 個表結(jié)點。在邊稀疏的情況下，采用鄰接表比采用鄰接矩陣節(jié)省存儲空間。在無向圖的鄰接表中，頂點 vi的度恰好為第 i 個鏈表中的表結(jié)點數(shù)。若有向圖中有 n 個頂點 e 條弧，則鄰接表需要 n 個頭結(jié)點和 e 個表結(jié)點。在有向圖的鄰接表中，第 i 個鏈表中的結(jié)點數(shù)為頂點 vi的出度。為求頂點 vi的入度，需要遍歷整個鄰接表，在所

26、有鏈表中其鄰接點域的值為 i 的結(jié)點個數(shù)為頂點 vi的入度。在鄰接表中，容易找到任意一頂點的第一鄰接點和下一個鄰接點，但要判斷任意兩個頂點 vi和 vj之間是否有邊相連，則須搜索第 i 或 j 個鏈表，因此，不及鄰接矩陣方便。(3).深度優(yōu)先遍歷圖的基本思路是： 1.訪問圖中的指定起始點 v0； 2.從 v0出發(fā)，訪問一個與 v0鄰接的頂點 w1后，再從 w1出發(fā)，訪問與 w1鄰接的且未訪問的頂點 w2。然后從 w2出發(fā)，重復(fù)上述過程，直到找不到未被訪問的頂點為止。 3.回退到尚有未被訪問過的鄰接點的頂點，從該頂點出發(fā)，重復(fù)上面的步 驟，直到所有被訪問過的頂點的鄰接點都已訪問為止。(4).廣度

27、優(yōu)先遍歷是圖的實現(xiàn)思路是： 1.訪問圖中的指定起始點 v0； 2.從 v0出發(fā)，依次訪問 v0的未被訪問的鄰接點 w1,w2,w3,wn。然后依次訪問 w1,w2,w3,wn的未被訪問的鄰接點。 3.重復(fù)上面的第二步，直到所有頂點的鄰接點都已訪問為止。213.3. 運行結(jié)果運行結(jié)果4.4. 源程序源程序#include#include#define NULL 0#define maxsize 10typedef struct node int data; struct node *next;dnode;typedef structint vex; dnode *first;Node;typed

28、ef struct Node arrymaxsize; int num;graph;int visitmaxsize;graph creat()/創(chuàng)建鄰接表22 graph a; dnode *p; int i,x,y,e; printf(輸入頂點數(shù)和邊數(shù)（以空格分割） ：); scanf(%d%d,&a.num,&e); for(i=1;i=a.num;i+) a.arryi.first=NULL; a.arryi.vex=i; for(i=1;idata=y; p-next=a.arryx.first; a.arryx.first=p; p=(dnode*)malloc(s

29、izeof(dnode); p-data=x; p-next=a.arryy.first ; a.arryy.first=p; return a;void copy(graph b,int vmaxsize)/鄰接矩陣與鄰接表轉(zhuǎn)換 int i,j; dnode *p; for(i=1;i=b.num;i+) for(j=1;j=b.num;j+) vij=0; for(i=1;idata=1; p=p-next ; 23 for(i=1;i=b.num;i+) for(j=1;j=b.num;j+) printf(%d ,vij); printf(n); void vexdu(graph a)

30、/求度數(shù) dnode *p; int i,count; for(i=1;inext ; printf(%d 的度數(shù):%dn,a.arryi.vex,count); void clr() int i; for(i=1;idata)24 dfs(a,p-data ); p=p-next; void find1(graph a) int v; clr(); printf(輸入開始搜索節(jié)點：); scanf(%d,&v); dfs(a,v); printf(n);void find2(graph a) int x,i; dnode *p,*q; clr(); printf(輸入要查找刪除的點：

31、); scanf(%d,&x); for(i=1;ia.num) printf(沒找到！n); return; else printf(找到！n); q=p=a.arryi.first ; a.arryi.vex=0; if(p-data=x)p=p-next; else while(p) if(p-data=x) q-next=p-next; break; q=p;25 p=p-next; dfs(a,x); printf(n);void find3(graph a) int i; clr(); dfs(a,1); for(i=1;ia.num;i+) if(visiti=0) pr

32、intf(此圖不是連通的。n); return ; printf(此圖不是連通的。n); return;void find4(graph a) int vmaxsizemaxsize; copy(a,v); void main() graph h; h=creat(); vexdu(h); find1(h); find2(h); find3(h); find4(h);26總總 結(jié)結(jié)通過本次課程設(shè)計，我學(xué)到了很多。編程不像做其它事，它要求編程人員有非?？b密的思維，很好的整體把握能力和很好的調(diào)試程序的能力等。決定程序成功與否的往往不是程序的整體思路和整體算法，而是細(xì)節(jié)，細(xì)節(jié)錯誤往往是程序失敗的終級

33、殺手，我在此次課程設(shè)計中深有體會。一些小的語法錯誤，可能程序運行沒錯誤，可運行后卻得不到想要的結(jié)果。所以在程序排錯的時候費了很大的工夫才找出錯誤所在。同時我也認(rèn)識到編譯工具的重要性，我用的是 VC+6.0 環(huán)境，提高我編寫程序的效率，如按回車后，它能自動空出一定距離，體現(xiàn)出程序的結(jié)構(gòu)，不用人工輸入空格、制表符，還有它的調(diào)試功能，不用我人工輸出中間變量來查錯，就能看到中間變量。此次的稀疏矩陣算法我早就在其它學(xué)科中接觸過，但要將其轉(zhuǎn)化為程序算法，可不是輕而易舉的，要考慮什么數(shù)據(jù)結(jié)構(gòu)更適合那算法，本次就用三元組方式，因為本次有的操作是對矩陣中非零元進(jìn)行操作，對于零元素就可以免去，利用三元組對非零元進(jìn)行存儲，可大大簡化其算法。還有，算法的實現(xiàn)須要