數(shù)據(jù)結(jié)構(gòu)課程設(shè)計城市鏈表的設(shè)計與實現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目： 城市鏈表的設(shè)計與實現(xiàn) 二叉排序樹基本操作的實現(xiàn) 年級 專業(yè)：09計算機(jī)科學(xué)與技術(shù) 姓 名：陳 戧 學(xué) 號： e10914049 城市鏈表的設(shè)計與實現(xiàn)i. 設(shè)計要求1. 問題描述 將若干城市信息，存入一個帶頭結(jié)點(diǎn)的單鏈表。節(jié)點(diǎn)中的城市信息包括城市名、城市位置坐標(biāo)、城市人口、城市面積、城市特色等。要求能夠利用城市名和位置坐標(biāo)來進(jìn)行查找、插入、刪除、更新等操作。2. 需求分析1) 給定一個城市名，返回其位置坐標(biāo)。2) 給定一個中心位置坐標(biāo)p和一個距離d，返回所以與p距離小于等于d的城市。ii. 概要設(shè)計為了實現(xiàn)需求分析中的功能，可以從以下3方面著手設(shè)計。1. 主界面設(shè)計為了

2、實現(xiàn)城市鏈表的基本操作，設(shè)計一個包含多個菜單選項的主控制子程序以實現(xiàn)城市鏈表的各項子功能， 方便用戶的使用。 本系統(tǒng)的主控制菜單運(yùn)行界面如圖1所示。 圖1城市鏈表的主菜單2. 存儲結(jié)構(gòu)的設(shè)計本程序主要采鏈表結(jié)構(gòu)類型來表示城市鏈表的信息。其中二叉樹節(jié)點(diǎn)由7分量組成：城市的名稱、城市的位的橫坐標(biāo)、城市位置的縱坐標(biāo)、城市的面積、城市的人口、城市的特色，及指向自己結(jié)構(gòu)體的指針。3. 系統(tǒng)功能設(shè)計本程序設(shè)置了6個子功能菜單，其設(shè)計如下。1) 建立城市鏈表。根據(jù)系統(tǒng)提示，選擇功能項1，并根據(jù)提示逐個輸入城市的名稱、位置坐標(biāo)、人口、面積、特色等。該功能由void create()函數(shù)實現(xiàn)。2) 顯示全部城市

3、信息。根據(jù)系統(tǒng)提示，選擇功能項2,即可顯示全部的城市信息。該功能由print（）函數(shù)實現(xiàn)。3) 插入新的城市界節(jié)點(diǎn)信息。根據(jù)系統(tǒng)提示選擇功能項3，可每次插入一個節(jié)點(diǎn)信息，如果要插入多個城市信息，需多次選擇傳插入功能。該功能由insert ()函數(shù)實現(xiàn)。4) 查詢城市的信息。選擇功能項4，進(jìn)入查詢菜單，有兩種查詢方式。一是跟根據(jù)城市名稱查詢，二是根據(jù)城市的位置坐標(biāo)的距離查詢。該功能由searchmenu ()和void searchname()及void searchposition()函數(shù)實現(xiàn)。5) 更新城市鏈表中不正確后過時的信息?？梢酝ㄟ^城市名稱查詢到該節(jié)點(diǎn)，再以此輸入城市名稱坐標(biāo)、人口、

4、面積、特色等屬性。該功能由void updatecity()實現(xiàn)。6) 刪除城市鏈表的節(jié)點(diǎn)信息。根據(jù)提示可以對城市鏈表中不需要的節(jié)點(diǎn)進(jìn)行刪除，刪除的方式是輸入城市名稱，查詢到該節(jié)點(diǎn)后刪除。該功能由void delete ()函數(shù)實現(xiàn)。iii. 模塊設(shè)計1. 模塊設(shè)計本程序包含兩個模塊：主程序模塊和二叉排序樹操作模塊。其調(diào)用關(guān)系如圖2主程序模塊城市鏈表的操作模塊 圖2模塊調(diào)用示意圖2. 系統(tǒng)子程序及其功能設(shè)計本系統(tǒng)共設(shè)計了9個子程序，個程序的的函數(shù)名及其功能說明如下：1) void init(citylist lhead);/創(chuàng)建頭指針2) void create(citylist lhead)

5、;/創(chuàng)建城市鏈表3) int print(citylist lhead);/顯示全部信息4) void insert(citylist lhead);/插入新城市信息5) int searchmenu(citylist lhead);/查詢查詢菜單6) void searchname(citylist lhead);/按名稱查詢7) void searchposition(citylist lhead);/按坐標(biāo)查詢8) void updatecity(citylist lhead);/更新城市信息9) void delete(citylist lhead);/刪除城市信息3. 函數(shù)主要的調(diào)用

6、關(guān)系本系統(tǒng)9個子程序見的主要調(diào)用關(guān)系圖3.searchname main()initcreatesearchpositionprintsearhminsertinsertenuupdatadeletesearchnameiv. 詳細(xì)設(shè)計1. 數(shù)據(jù)類型定義本系統(tǒng)采用鏈表結(jié)構(gòu)存儲城市節(jié)點(diǎn)信息，節(jié)點(diǎn)定義如下： typedef struct citynodechar cityname30;/名稱float x;/橫坐標(biāo)float y;/縱坐標(biāo)int citypopulation;/人口float cityarea;/面積char citycharacteristic50;/特色struct cityn

7、ode *next;citynode,*citylist;2. 主要子程序的詳細(xì)設(shè)計1) 城市鏈表的創(chuàng)建函數(shù)，主要用來建立城市鏈表。 void create(citylist lhead) int n;printf(請輸入要創(chuàng)建的鏈表的城市個數(shù)：);scanf(%d,&n); for(int i=0;icityname);printf(請輸入城市坐標(biāo)x,y:t);scanf(%f%c%f,&newnode-x,&m,&newnode-y); printf(請輸入城市的人口（萬）: t);scanf(%d,&newnode-citypopulation);printf(請輸入城市的面積(平方公里

8、): t);scanf(%f,&newnode-cityarea);printf(請輸入城市的特色: t);scanf(%s,newnode-citycharacteristic);while(lhead-next != null)lhead = lhead-next;newnode-next = lhead-next;lhead-next = newnode;3) 城市信息查詢函數(shù)如下：/*根據(jù)名稱查詢*/ void searchname(citylist lhead) citylist p=lhead;char sname30;if(p-next)printf(請輸入您要搜索的城市名稱n)

9、;scanf(%s,sname);while(p-next != null & strcmp(p-next-cityname,sname)p = p-next;if(p-next = null)printf(您要搜索的城市不存在n);return;printf(城市坐標(biāo)為：n,p-next-x,p-next-y);elseprintf(鏈表未建立，請先建立鏈表n);/*根據(jù)坐標(biāo)查詢*/void searchposition(citylist lhead)char m;float x1;float y1;citylist p=lhead;int distance;if(p-next)printf

10、(請輸入中心坐標(biāo)x,yn);scanf(%f%c%f,&x1,&m,&y1);printf(請輸入距離:);scanf(%d,&distance);printf(距中心坐標(biāo)的城市的距離為,x1,y1); printf(%d的城市有:n,distance);p = p-next;while(p != null)if(x1-p-x)*(x1-p-x) + (y1-p-y)*(y1-p-y) cityname);printf(n,p-x,p-y);p = p-next;elseprintf(鏈表未建立，請先建立鏈表n);v. 測試分析1. 城市鏈表的建立首先進(jìn)入主菜單，如圖1。在主菜單下，用戶根據(jù)菜

11、單的選項輸入1，然后按照提示依次輸入城市節(jié)點(diǎn)的屬性。運(yùn)行的結(jié)果如圖4. 圖4城市鏈表的建立2. 打印城市鏈表的所有節(jié)點(diǎn)信息在主菜單下，用戶選擇2，可以打印出全部的節(jié)點(diǎn)信息。運(yùn)行的結(jié)果如圖5. 圖5全部節(jié)點(diǎn)信息3. 插入節(jié)點(diǎn)信息信息在主菜單下，用戶選擇3，可以插入一個新的節(jié)點(diǎn)信息。運(yùn)行的結(jié)果如圖6. 圖6插入新的節(jié)點(diǎn)4. 刪除城市鏈表的節(jié)點(diǎn)信息在主菜單下，用戶選擇6，首先通過輸入關(guān)鍵字查詢相關(guān)信息。運(yùn)行的結(jié)果如圖7. 圖7刪除節(jié)點(diǎn)信息5. 查找城市鏈表的節(jié)點(diǎn)在主菜單下，用戶選擇4，進(jìn)入查找菜單，有兩種查詢方式。運(yùn)行的結(jié)果如圖8.和圖9。 圖8按城市名稱查找節(jié)點(diǎn)信息 圖9按城市位置和距離查找vi.

12、 原程序清單 #include#include#include#include/*城市鏈表*/typedef struct citynodechar cityname30;/名稱float x;/橫坐標(biāo)float y;/縱坐標(biāo)int citypopulation;/人口float cityarea;/面積char citycharacteristic50;/特色struct citynode *next;citynode,*citylist;void init(citylist lhead);/創(chuàng)建頭指針void create(citylist lhead);/創(chuàng)建城市鏈表int print(

13、citylist lhead);/顯示全部信息void insert(citylist lhead);/插入新城市信息int searchmenu(citylist lhead);/查詢查詢菜單void searchname(citylist lhead);/按名稱查詢void searchposition(citylist lhead);/按坐標(biāo)查詢void updatecity(citylist lhead);/更新城市信息void delete(citylist lhead);/刪除城市信息/*初始化*/void init(citylist lhead)lhead-next = null

14、;/*創(chuàng)建城市鏈表*/void create(citylist lhead) int n;printf(請輸入要創(chuàng)建的鏈表的城市個數(shù)：);scanf(%d,&n); for(int i=0;icityname);printf(請輸入城市坐標(biāo)x,y:t);scanf(%f%c%f,&newnode-x,&m,&newnode-y); printf(請輸入城市的人口（萬）: t);scanf(%d,&newnode-citypopulation);printf(請輸入城市的面積(平方公里): t);scanf(%f,&newnode-cityarea);printf(請輸入城市的特色: t);sc

15、anf(%s,newnode-citycharacteristic);while(lhead-next != null)lhead = lhead-next;newnode-next = lhead-next;lhead-next = newnode;/*顯示全部城市信息*/int print(citylist lhead)citylist p=lhead;if(p-next)p=p-next;printf( 全部城市信息為 :n);printf(*n);printf(名稱t坐標(biāo)t人口t面積t特色n);while(p)printf(%st,p-cityname);printf(%.f,%.f)

16、t,p-x,p-y);printf(%dt,p-citypopulation);printf(%.ft,p-cityarea);printf(%sn,p-citycharacteristic);p = p-next;elseprintf(鏈表未建立，請先建立鏈表n);return 0;/*查詢城市信息*/int searchmenu(citylist lhead)citylist p=lhead;int s; printf(#n);printf(| 查詢菜單 |n); printf(|n);printf(| 1.按名稱查詢 |n);printf(| 2.按坐標(biāo)查詢 |n);printf(| 3

17、.返回上級菜單 |n);printf(#n);scanf(%d,&s); switch(s)case 1:searchname(p);break;case 2:searchposition(p);break;case 3:break;default:printf(輸入錯誤,請重新輸入n);break;return 0;/*根據(jù)名稱查詢*/void searchname(citylist lhead) citylist p=lhead;char sname30;if(p-next)printf(請輸入您要搜索的城市名稱n);scanf(%s,sname);while(p-next != null

18、 & strcmp(p-next-cityname,sname)p = p-next;if(p-next = null)printf(您要搜索的城市不存在n);return;printf(城市坐標(biāo)為：n,p-next-x,p-next-y);elseprintf(鏈表未建立，請先建立鏈表n);/*根據(jù)坐標(biāo)查詢*/void searchposition(citylist lhead)char m;float x1;float y1;citylist p=lhead;int distance;if(p-next)printf(請輸入中心坐標(biāo)x,yn);scanf(%f%c%f,&x1,&m,&y1

19、);printf(請輸入距離:);scanf(%d,&distance);printf(距中心坐標(biāo)的城市的距離為,x1,y1); printf(%d的城市有:n,distance);p = p-next;while(p != null)if(x1-p-x)*(x1-p-x) + (y1-p-y)*(y1-p-y) cityname);printf(n,p-x,p-y);p = p-next;elseprintf(鏈表未建立，請先建立鏈表n);/*更新城市*/void updatecity(citylist lhead)char updname30;printf(請輸入您要更新的城市名:n);s

20、canf(%s,updname);while(strcmp(lhead-next-cityname,updname)lhead = lhead-next;printf(請輸入城市新名n);scanf(%s,lhead-next-cityname);printf(請輸入城市新坐標(biāo)n);scanf(%f,&lhead-next-x);scanf(%f,&lhead-next-y);printf(請輸入城市的新人口（萬）n);scanf(%d,&lhead-next-citypopulation);printf(請輸入城市的新面積（平方公里）n);scanf(%f,&lhead-next-citya

21、rea);printf(請輸入城市的新特色n);scanf(%s,lhead-next-citycharacteristic);/*刪除城市*/void delete(citylist lhead)char delname30;printf(請輸入要刪除的城市名稱:n);scanf(%s,delname);while(strcmp(lhead-next-cityname,delname)lhead = lhead-next;lhead -next = lhead-next-next;void main() system(color 1e);citylist lhead;int select;l

22、head = (citylist )malloc(sizeof(citynode);/建立頭指針 init(lhead); citylist p= lhead; while(select!=8) printf(#n); printf(# 歡迎使城市鏈表系統(tǒng) #n); printf(|n); printf(|* 1.創(chuàng)建城市鏈表 *|n); printf(|* 2.顯示全部城市信息 *|n); printf(|* 3.插入新的城市 *|n); printf(|* 4.查詢城市信息 *|n); printf(|* 5.更新城市信息 *|n); printf(|* 6.刪除城市信息 *|n); pr

23、intf(|* 7.退出 *|n); printf(#n); scanf(%d,&select); switch(select) case 1:create(p);break;case 2:print(p);break;case 3:insert(p);break;case 4:searchmenu(p);break;case 5:updatecity(p);break;case 6:delete(p);break; case 7: break;default:printf(輸入錯誤,請重新輸入n);break; vii. 用戶手冊執(zhí)行本程序后，即進(jìn)入系統(tǒng)的主菜單。用戶可以根據(jù)菜單的提示選擇相

24、應(yīng)的數(shù)字，進(jìn)入相應(yīng)的子菜單。本系統(tǒng)沒有提供一次刪除或依次插入多個城市信息功能，如果要一次操作多個城市信息，需多次選擇相同的步驟。較為麻煩。viii. 小結(jié) 本系統(tǒng)能較好的實現(xiàn)城市鏈表的基本操作，但由于過于簡單存在許多不足，特別是在功能上。再調(diào)試本程序時，出現(xiàn)了諸如，鏈表的操作，指針的應(yīng)用等一些數(shù)據(jù)結(jié)構(gòu)和c語言面基礎(chǔ)性的錯誤，消耗了較多時間?？傊舜握n設(shè)讓我深刻認(rèn)識到了理論和實踐的巨大差異，對自己今后的職業(yè)生涯有一定的幫助。二叉排序樹的基本操作的實現(xiàn)ix. 設(shè)計要求3. 問題描述 從磁盤讀入一組數(shù)據(jù)，建立二叉排序樹并對其進(jìn)行查找、遍歷、插入、刪除等基本操作。4. 需求分析建立二叉排序樹并對其進(jìn)行

25、查找，包括成功和不成功兩種情況。x. 概要設(shè)計為了實現(xiàn)需求分析中的功能，可以從以下3方面著手設(shè)計。4. 主界面設(shè)計為了方便對二叉排序樹的基本操作，設(shè)計一個包含多個菜單選項的主控制子程序以實現(xiàn)二叉排序樹的各項功能。本系統(tǒng)的主控制菜單運(yùn)行界面如圖1所示。圖1二叉排序樹的基本操作的主菜單5. 存儲結(jié)構(gòu)的設(shè)計本程序主要采二叉樹結(jié)構(gòu)類型來表示二叉排序樹。其中二叉樹節(jié)點(diǎn)由1個表示關(guān)鍵字的分量組成，還有指向該左孩子和右孩子的指針。6. 系統(tǒng)功能設(shè)計本程序設(shè)置了5個子功能菜單，其設(shè)計如下。1) 建立二叉排序樹。根據(jù)系統(tǒng)提示，輸入節(jié)點(diǎn)的關(guān)鍵字，并以0作為結(jié)束的標(biāo)識符。該功能由bstree create()函數(shù)實

26、現(xiàn)。2) 插入二叉排序新的節(jié)點(diǎn)信息。每次只能夠插入一個節(jié)點(diǎn)信息，如果該節(jié)點(diǎn)已經(jīng)存在，則不插入。該功能由bstree insert(y)函數(shù)實現(xiàn)。3) 查詢二叉排序樹的信息。每次進(jìn)行查詢，成功則顯示“查詢到該節(jié)點(diǎn)”，不成功則“顯示查詢不到該節(jié)點(diǎn)“該功能由bstree search()函數(shù)實現(xiàn)。4) 刪除二叉排序樹的節(jié)點(diǎn)信息?？梢詫Χ媾判驑渲胁恍枰墓?jié)點(diǎn)進(jìn)行刪除，刪除的方式是輸入關(guān)鍵字，查詢到該節(jié)點(diǎn)后刪除。該功能由bstree delete()函數(shù)實現(xiàn)。 5) 遍歷二叉排序樹。遍歷二叉排序樹可以顯示該二叉排序樹的全部節(jié)點(diǎn)信息。該功能由void traverse()實現(xiàn)。xi. 模塊設(shè)計4. 模塊

27、設(shè)計本程序包含兩個模塊：主程序模塊和二叉排序樹操作模塊。其調(diào)用關(guān)系如圖2主程序模塊二叉排序樹操作模塊 圖2模塊調(diào)用示意圖5. 系統(tǒng)子程序及其功能設(shè)計本系統(tǒng)共設(shè)計了5個子程序，個程序的的函數(shù)名及其功能說明如下：1) bstree create(); /創(chuàng)建二叉排序樹2) bstree insert(bstree tree,int key); /插入3) bstree search(bstree tree,int key); /查找4) void traverse(bstree tree); /遍歷5) bstree delete(bstree tree,int key); /刪除信息6. 函數(shù)主

28、要的調(diào)用關(guān)系本系統(tǒng)9個子程序見的主要調(diào)用關(guān)系圖3.main()main()insert()search( )traverse ()delete ()xii. 詳細(xì)設(shè)計3. 數(shù)據(jù)類型定義本系統(tǒng)采用二叉樹結(jié)構(gòu)存儲節(jié)點(diǎn)信息，節(jié)點(diǎn)定義如下： typedef struct bstnodeint key;struct bstnode *lchild,*rchild;bstnode,* bstree;4. 主要子程序的詳細(xì)設(shè)計1) 二叉排序樹的創(chuàng)建函數(shù)，主要用來建立二叉排序樹。 bstree create() int key;bstree tree=null; /初始化空樹scanf(%d,&key); w

29、hile(key!=0)tree=insert(tree,key); /逐個插入節(jié)點(diǎn)scanf(%d,&key);return tree;2) 二叉排序插入函數(shù)如下： bstree insert(bstree tree,int key)bstree p=tree;bstree s,f;while (p!=null)f=p; if(key=p-key) return tree; if(keykey) p=p-lchild; else p=p-rchild;s=(bstree)malloc(sizeof(bstnode);s-key=key;s-lchild=null;s-rchild=null;

30、if(tree=null) return s; /新節(jié)點(diǎn)為二叉排序樹的根if(keykey) f-lchild=s; else f-rchild=s; return tree; 3) 二叉排序樹查詢函數(shù)如下： bstree search(bstree tree,int key)bstree p=tree; int flag=0; while(p!=null) if(p-key=key) printf(查詢到該節(jié)點(diǎn)！);flag=1;return(p);break;if (keykey) p=p-lchild; else p=p-rchild; if(flag=0)printf(查詢不到關(guān)鍵字為

31、%d的節(jié)點(diǎn)！,key);return null; xiii. 測試分析6. 二叉排序樹的建立首先進(jìn)入主菜單，如圖1。在主菜單下，用戶根據(jù)菜單的選項輸入1，然后按照提示建立二叉排序樹，并以0未結(jié)束符。運(yùn)行的結(jié)果如圖4. 圖4二叉排序樹的建立7. 遍歷二叉樹的節(jié)點(diǎn)信息在主菜單下，用戶選擇4，可以打印出全部的節(jié)點(diǎn)信息。運(yùn)行的結(jié)果如圖5. 圖5遍歷二叉排序樹8. 插入節(jié)點(diǎn)信息信息在主菜單下，用戶選擇2，可以插入一個新的節(jié)點(diǎn)信息。運(yùn)行的結(jié)果如圖6.圖6插入新的節(jié)點(diǎn)9. 查詢二叉樹的節(jié)點(diǎn)信息在主菜單下，用戶選擇3，首先通過輸入關(guān)鍵字查詢相關(guān)信息。運(yùn)行的結(jié)果如圖7. 圖7查詢節(jié)點(diǎn)信息10. 刪除二叉樹的節(jié)點(diǎn)

32、在主菜單下，用戶選擇5，可以通過輸入要刪除的關(guān)鍵字來刪除該節(jié)點(diǎn)的全部信息。運(yùn)行的結(jié)果如圖8. 圖8刪除二叉排序樹的節(jié)點(diǎn)xiv. 原程序清單#include#include#include/*二叉排序樹的數(shù)據(jù)結(jié)構(gòu)*/typedef struct bstnodeint key;struct bstnode *lchild,*rchild;bstnode,* bstree;bstree create(); /創(chuàng)建二叉排序樹bstree insert(bstree tree,int key); /插入bstree search(bstree tree,int key); /查找void travers

33、e(bstree tree); /遍歷bstree delete(bstree tree,int key); /刪除/*創(chuàng)建二叉排序樹*/bstree create() int key;bstree tree=null; /初始化空樹scanf(%d,&key); while(key!=0)tree=insert(tree,key); /逐個插入節(jié)點(diǎn)scanf(%d,&key);return tree;/*插入*/ bstree insert(bstree tree,int key)bstree p=tree;bstree s,f;while (p!=null)f=p; if(key=p-ke

34、y) return tree; if(keykey) p=p-lchild; else p=p-rchild;s=(bstree)malloc(sizeof(bstnode);s-key=key;s-lchild=null;s-rchild=null;if(tree=null) return s; /新節(jié)點(diǎn)為二叉排序樹的根if(keykey) f-lchild=s; else f-rchild=s; return tree;/*查找*/bstree search(bstree tree,int key)bstree p=tree; int flag=0; while(p!=null) if(p

35、-key=key) printf(查詢到該節(jié)點(diǎn)！);flag=1;return(p);break;if (keykey) p=p-lchild; else p=p-rchild; if(flag=0)printf(查詢不到關(guān)鍵字為%d的節(jié)點(diǎn)！,key);return null; /*遍歷*/void traverse(bstree tree)if(tree) traverse(tree-lchild); printf(%4d,tree-key); traverse(tree-rchild); /*刪除*/bstree delete(bstree tree,int key)bstree p=tr

36、ee; bstree f,s,q; f=null;while(p) /查找關(guān)鍵字為key的節(jié)點(diǎn)if(p-key=key) break; f=p; if(p-keykey) p=p-lchild;else p=p-rchild;if (p=null) return tree; if (p-lchild=null)|(p-rchild=null) if(f=null) if(p-lchild=null) tree=p-rchild;else tree=p-lchild;else if (p-lchild=null) if(f-lchild=p) f-lchild=p-rchild; else f-rchild=p-rchild; else if(f-lchild=p) f-lchild=p-lchild; else f-lchild=p-lchild; free(p);el