第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-全國鐵路交通咨詢模擬
數(shù)據(jù)庫課程設(shè)計(jì)
—全國鐵路咨詢系統(tǒng)
目錄
一．需求分析****************************************** 3
二．概要設(shè)計(jì)******************************************
三．儲(chǔ)存結(jié)構(gòu)設(shè)計(jì)**************************************
四．詳細(xì)設(shè)計(jì)******************************************
五．用戶手冊******************************************
六．測試數(shù)據(jù)******************************************
七．心得體會(huì)****************************************** 8 11 17 18 26
一、需求分析
1、問題描述
由于不同目的的旅客對(duì)交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的時(shí)間盡可能短，出門旅游的游客則期望旅費(fèi)盡可能省。編制一個(gè)全國城市間的交通咨詢程 序，為旅客提供兩種最優(yōu)決策的交通咨詢。
根據(jù)鐵路的特征，數(shù)據(jù)的儲(chǔ)存需要使用圖的結(jié)構(gòu)。每個(gè)城市之間有不同的車次，每個(gè)車次的始發(fā)站、路過車站和終點(diǎn)站都不一樣，所以兩個(gè)城市之間就有指向明確的邊，是一個(gè)有向圖；而由于車次的不一樣，所以發(fā)車時(shí)間，到站時(shí)間，價(jià)格等也會(huì)不一樣；所以每兩個(gè)點(diǎn)之間不止兩條邊，可能存在不同的多條邊。
2、功能需求
鐵路咨詢的對(duì)象是用戶，所以，需要一個(gè)對(duì)用戶友好的功能菜單，根據(jù)用戶可能需要的實(shí)際需求，功能菜單中可能會(huì)包括以下要點(diǎn)：
1：顯示所有車站信息
2: 顯示所有車次信息（包括時(shí)刻表）
3: 查詢車站信息
4: 查詢兩個(gè)城市之間的鐵路信息
5: 增加或刪除車站
6: 增加或刪除鐵路信息
7: 增加、刪除或修改時(shí)刻表、距離和價(jià)格
8：尋找兩城市間最省錢的一條路徑
9：尋找兩城市間最省時(shí)間的一條路徑 10：尋找兩城市間所有路徑(按費(fèi)用從低到高排序輸出)
11：尋找兩城市間所有路徑(按所用時(shí)間從少到多排序輸出)
12：退出咨詢系統(tǒng)
圖的初始數(shù)據(jù)從文本中讀入，文本是老師給的標(biāo)準(zhǔn)數(shù)據(jù)。
3、輸入及輸出格式
(1):輸入格式：
A：圖的初始數(shù)據(jù)輸入
數(shù)據(jù)的初始化是需要從文本中讀入的，所以不需要有專門的文本輸入函數(shù)，只需要給出讀文本的函數(shù)input（）；使用input（）函數(shù)從測試數(shù)據(jù)的三個(gè)文本中讀入數(shù)據(jù)，然后使用創(chuàng)建圖的函數(shù)CreateGraph（）創(chuàng)建起整個(gè)圖。初始數(shù)據(jù)的讀入，分別是從station.txt中讀入每個(gè)城市站點(diǎn)的名稱的城市編號(hào)，從iinformation.txt中讀入每個(gè)城市間的鐵路信息，從railway.txt中讀入所有鐵路線的信息。
如：
以下從station.txt中節(jié)選部分
0 北京廣州石家莊鄭州武漢長沙
以下從information.txt中節(jié)選部分
出發(fā)城市編號(hào) 到達(dá)城市編號(hào) 車次 里程
費(fèi)用
出發(fā)時(shí)刻
到達(dá)時(shí)刻
0
1000 287
62.5
0000
0246
0
1016 287
0060
0275
0
1001 137
23.5
0000
0117
0
1017 137
28.5
0060
0163
0
1002 1199 156.5 0000
1028
1008 1257 162.5 0000
1077
以下從railway.txt中節(jié)選部分
各條鐵路線上城市編號(hào)（此行可去掉）
京廣線 0 2 3 4 5 6 1
京九線 0 13 14 12
京滬線 0 8 9 10 11 7
隴海線 18 10 3 20 24 19
B：用戶要求輸入
用戶在使用本程序時(shí)，會(huì)要求用戶輸入各種數(shù)據(jù)，如城市編號(hào)id、抉擇選項(xiàng)y/n等；用戶只需要按照程序菜單的要求輸入即可。如城市編號(hào)id就是初始化數(shù)據(jù)（文本數(shù)據(jù)）中每個(gè)城市就有的編號(hào)，用戶在不知道城市編號(hào)之前先查看一下城市信息就可以清楚明了的知道城市id了。
(2):輸出格式
在系統(tǒng)的管理下，為了用戶的查詢方便，需要有多重輸出方式。如每條鐵路線上信息的輸出。這里面就包括了，在每條鐵路上所有車次信息，每個(gè)車次始發(fā)站信息、過站信息和終點(diǎn)站信息。
樣例如下：
蘭新線中有以下車次：
1005次列車運(yùn)行情況：
出發(fā)城市
到達(dá)城市
車次
距離(km)出發(fā)時(shí)間
到達(dá)時(shí)間
費(fèi)用(元)
蘭州
酒泉
1005
748
0：0
10：41
酒泉
烏魯木齊
1005
797
10：51 22：14
152.5
烏魯木齊
阿拉山口
1005
477
22：24
5：13
64.5
1013次列車運(yùn)行情況：
出發(fā)城市
到達(dá)城市
車次
距離(km)出發(fā)時(shí)間
到達(dá)時(shí)間
費(fèi)用(元)
阿拉山口
烏魯木齊
1013
477
0： 0
6：49
64.5
烏魯木齊
酒泉
1013
797
6：59
18：22
152.5
酒泉
蘭州
1013
748
18：32
5：13
對(duì)于每個(gè)城市信息的輸出，只需要輸出經(jīng)過每個(gè)城市的鐵路新路即可，當(dāng)然必須得輸出城市站點(diǎn)的id，方便用戶的查詢和管理
樣例如下：
城市編號(hào)
城市名稱
過站鐵路線
0
北京
京廣線
京九線
京滬線
廣州
京廣線
石家莊
京廣線
鄭州
京廣線
隴海線
武漢
京廣線
長沙
京廣線
株洲
京廣線
滬昆線
上海
京滬線
滬昆線
二、概要設(shè)計(jì)
1.數(shù)據(jù)特性分析
（1）：整體結(jié)構(gòu)分析
鐵路交通咨詢模擬系統(tǒng)管理的是全國的各個(gè)城市間的鐵路信息。對(duì)于整體的全
國鐵路信息來說，每一個(gè)城市站點(diǎn)就是一個(gè)頂點(diǎn)節(jié)點(diǎn)，城市與城市之間的每一個(gè)車
次信息就是一條有向邊。所有整個(gè)咨詢系統(tǒng)應(yīng)該是一個(gè)有向圖結(jié)構(gòu)。從A城市出發(fā)
到B城市，可能會(huì)有多個(gè)車次。
如下例：
出發(fā)城市
到達(dá)城市
車次
距離(km)出發(fā)時(shí)間
到達(dá)時(shí)間
費(fèi)用(元)
北京
石家莊
1000
287
0： 0
4： 6
62.5
北京
石家莊
1016
287
1： 0
4：35
所以每兩個(gè)城市頂點(diǎn)之間就可能會(huì)有多條有向邊，所以這個(gè)圖也不會(huì)是 一個(gè)有
向簡單圖了。為了城市節(jié)點(diǎn)能夠動(dòng)態(tài)的擴(kuò)充和刪除不受影響，我對(duì)于頂點(diǎn)的儲(chǔ)存采
用鏈表結(jié)構(gòu)不使用順序表結(jié)構(gòu)，定義一個(gè)頂點(diǎn)鏈表類VertexList。這樣，雖然鏈表查
詢和其節(jié)點(diǎn)的刪除的時(shí)間復(fù)雜度受到了一定的影響，但這樣設(shè)計(jì)出來的鐵路網(wǎng)圖才
更具有一般性個(gè)實(shí)用性。對(duì)于查找的時(shí)間復(fù)雜度問題的解決，我在后面也會(huì)給出方案。
（2）：城市頂點(diǎn)分析
對(duì)于每一城市來說，在全國的鐵路網(wǎng)中，它就是一個(gè)火車站節(jié)點(diǎn)。每一個(gè)火車，它都應(yīng)該會(huì)有自己的名字，過站的鐵路線等。為了咨詢系統(tǒng)管理和維護(hù)的方便，在 文本數(shù)據(jù)中，我們就人為的給每一個(gè)城市都編上序號(hào)id，每一個(gè)不同id對(duì)應(yīng)了一
個(gè)不同的城市節(jié)點(diǎn)。由于每個(gè)城市的id都是唯一的，所以在頂點(diǎn)的鏈表結(jié)構(gòu)里面，完全可以定義一個(gè)哈希表haxi[n]，對(duì)于haxi[i]來說，它存儲(chǔ)的就是id為i的城市
在內(nèi)存中地址。這樣，頂點(diǎn)鏈表在哈希表的支持下，就能完美解決查找、添加、刪除的時(shí)間復(fù)雜度問題了。
在整個(gè)鐵路網(wǎng)中，每一個(gè)城市就是頂點(diǎn)，每一個(gè)頂點(diǎn)，就是應(yīng)該有一個(gè)邊鏈表
用于儲(chǔ)存此城市能到達(dá)所有城市的各個(gè)不同車次的信息，也就是各個(gè)不同的邊。如：
出發(fā)城市編號(hào) 到達(dá)城市編號(hào) 車次 里程
費(fèi)用
出發(fā)時(shí)刻
到達(dá)時(shí)刻
0
1000 287
62.5
0000
0246
0
1016 287
0060
0275
從上例我們可以看出，對(duì)于每個(gè)頂點(diǎn)的不同邊來說，每一個(gè)不同的邊就有一個(gè)獨(dú)有
的車次。所以這樣，對(duì)于邊的儲(chǔ)存，我們也可以采用哈希表結(jié)構(gòu)。經(jīng)觀察發(fā)現(xiàn)，每 一車次都大于1000，所以，哈希表的id=車次-1000；對(duì)于編號(hào)為a的城市節(jié)點(diǎn)haxi[k]
來說，它儲(chǔ)存的是為城市a中車次為：1000+k的一條邊，邊里面就有到達(dá)城市、出發(fā)和到達(dá)時(shí)間、費(fèi)用、距離等等。
（3）：邊數(shù)據(jù)分析
對(duì)于圖來講，邊就是一個(gè)邏輯結(jié)構(gòu)，溝通頂點(diǎn)與頂點(diǎn)之間的關(guān)系。同時(shí)了，邊還有其物理特性。他需要儲(chǔ)存邊的權(quán)值等，它需要開辟儲(chǔ)存空間來存儲(chǔ)數(shù)
據(jù)。在鐵路網(wǎng)中，每兩個(gè)城市之間不同的車次信息就是一條不同的邊，所以，我需要把物理特性給單獨(dú)列出來，成為一個(gè)類LineInformation，用于表示邊
的物理信息。對(duì)于圖中抽象的邊，也需要定義一個(gè)類EdgeNode，用于溝通
圖中原本孤立的頂點(diǎn)，使之變成一個(gè)完整的圖
2.整體概要設(shè)計(jì)
前面，我提到了有頂點(diǎn)類station、頂點(diǎn)鏈表類VertexList、邊的物理類LineInformation和邊的邏輯類EdgeNode、火車線路類railway；對(duì)于整個(gè)完整的圖類來說，還有兩個(gè)主要的類沒有提及，那就是圖類RailwayNet和管理圖類的類management。當(dāng)然對(duì)于圖中需要完成各個(gè)不同功能的時(shí)候，我還寫了許多的輔助類。如查找兩個(gè)車站之間所有路徑時(shí)需要用到的LinStack，當(dāng)然還有LinStack的類的基石StackNode類。整個(gè)咨詢系統(tǒng)還有許多的結(jié)構(gòu)體，這些結(jié)構(gòu)體的功能我就不一一敘述了，詳細(xì)可見源代碼的注釋。下面我就列出各個(gè)類的關(guān)系圖
三．儲(chǔ)存結(jié)構(gòu)設(shè)計(jì)
1、存儲(chǔ)結(jié)構(gòu)的確定
數(shù)據(jù)結(jié)構(gòu)的目的是有效組織和處理數(shù)據(jù)。為了有效組織和處理數(shù)據(jù)，先要分析多項(xiàng)式操作的特點(diǎn)和指針?biāo)伎臻g比例，然后確定最優(yōu)的存儲(chǔ)結(jié)構(gòu)。
1.鐵路網(wǎng)是由鐵路和火車站構(gòu)成，每個(gè)火車站相當(dāng)于一個(gè)定點(diǎn)，每新建一條鐵路就相當(dāng)于新建定點(diǎn)之間的邊
2.車站之間可以任意到達(dá)，可直接相連，也可以間接相連，且怎么連接是不固定的。3.綜上所述，資源管理器的存儲(chǔ)結(jié)構(gòu)采用樹形結(jié)構(gòu)。
2、類的結(jié)構(gòu)設(shè)計(jì)圖：
management類圖：
RailWay類圖：
VertexList類圖：
RailWay類圖：
LineInformation類圖：
EdgeNode結(jié)構(gòu)圖：
Station類圖；
四、詳細(xì)設(shè)計(jì)
1.管理類management
class management{ private:
vector
void NextDisplay(EdgeNode* edge, LinStack
//私有的函數(shù)，以深度優(yōu)先遍歷的方式尋找兩點(diǎn)之間的所有路徑
void DepthFirstSearchPath(vector
//私有函數(shù)，以Dijkastra算法尋找最節(jié)省時(shí)間的路徑
void ShortestCost(vector
void QuickSort(vector
};
VertexList & Vertex(){ return vertex;} vector
void InsertVertex(station* s);//在頂點(diǎn)v1和v2之間插入一條邊(邊的起點(diǎn)為v1，終點(diǎn)為v2)void InsertEdge(int v1, int v2, EdgeNode* & ed);//刪除編號(hào)為id的城市頂點(diǎn) void DeleteVertex(int id);//刪除邊edge
void DeleteEdge(int v1, int v2);//創(chuàng)建一個(gè)鄰接表圖
void CreateGraph(RailwayNet & graph, vector
void display(RailwayNet & graph);//返回頂點(diǎn)v1和v2的第一條邊
EdgeNode* const GetFirstEdge(int v1, int v2);//獲取起點(diǎn)origin到終點(diǎn)terminal的最少費(fèi)用
float GetShortestCost(int origin, int terminal, LineInformation & edge);//獲取邊路徑path中的用時(shí)
int GetPathTime(vector
float GetPathCost(vector
void GetAllPath(vector
//頂點(diǎn)鏈表類 class VertexList{ private:
station *head;//頭指針
int size;//鏈表的大?。ㄔ氐膫€(gè)數(shù)）
station* haxi[1000];//哈希表，內(nèi)存有節(jié)點(diǎn)的地址(哈希表中的下標(biāo)與對(duì)應(yīng)城市節(jié)點(diǎn)的ID相等)public:
};VertexList();~VertexList();station* & GetHead(){ return head;} int & GetSize(){ return size;} //按照id從小到大的順序?qū)ity插入鏈表中 void insert(station* city);//刪除城市編號(hào)為id的節(jié)點(diǎn) void Delete(int id);//根據(jù)城市的id獲取城市節(jié)點(diǎn) station* GetVertex(int id);station** GetVertexHaxi(){ return haxi;} int IsVertexExist(int id);
4.頂點(diǎn)類
class station{ private:
int m_size;//邊鏈表的大小
EdgeNode* haxi[100];//以此車站為始發(fā)站的邊的哈希表(下標(biāo)為：車次-1000)vector
station(string na, int i);//構(gòu)造函數(shù) station(const station & sta);//復(fù)制構(gòu)造函數(shù) void Delete();//刪除函數(shù) //接口函數(shù) station* prior;//指向上一個(gè)車站 station *next;//指向下一個(gè)車站 EdgeNode *head;//指向第一條邊節(jié)點(diǎn) string m_name;int m_id;vector
};string & GetName(){ return m_name;} int & GetId(){ return m_id;} vector
LineInformation information;EdgeNode *next;//下一個(gè)邊結(jié)點(diǎn) EdgeNode *prior;//上一個(gè)邊節(jié)點(diǎn)
};
6.邊物理類LineInformation
class LineInformation{ private:
int m_DepartId;//出發(fā)城市編號(hào) int m_ArriveId;//到達(dá)城市編號(hào) int m_TrainNumber;//車次 int m_distance;//車程 float m_cost;//費(fèi)用 int m_DepartTime;//出發(fā)時(shí)間 int m_ArriveTime;//到達(dá)時(shí)間
//默認(rèn)構(gòu)造函數(shù) int DepartId=0, int ArriveId=0，LineInformation(int DepartId = 0, int ArriveId = 0, int Train = 0, int distance =-1, //復(fù)制構(gòu)造函數(shù)
LineInformation(const LineInformation & l);~LineInformation(){};LineInformation operator=(const LineInformation& e);//接口函數(shù)
int & GetDepartTime(){ return m_DepartTime;} int & GetArriveTime(){ return m_ArriveTime;} int & GetTrainNumber(){ return m_TrainNumber;} public: float cost = 0, int DepartTime =-1, int ArriveTime =-1);
};int & GetDepartId(){ return m_DepartId;} int & GetArriveId(){ return m_ArriveId;} int & GetDistance(){ return m_distance;} float & GetCost(){ return m_cost;}
7.火車線路類railway
class railway{ private:
};string m_name;//火車線名
vector
8.自定義棧類
template
};
template
//定義類LinStack
//數(shù)據(jù)元素 private: StackNode
//指針
//前視定義,否則友元無法定義
//模板類型為T
public: //構(gòu)造函數(shù)1,用于構(gòu)造頭結(jié)點(diǎn)
StackNode(StackNode
StackNode(const T& item, StackNode
};StackNode
//頭指針 //數(shù)據(jù)元素個(gè)數(shù) //構(gòu)造函數(shù) public: LinStack(void);~LinStack(void);T Pop(void);
//析構(gòu)函數(shù) //入棧 //出棧 //取棧頂元素 //堆棧非空否 void Push(const T& item);T GetTop(void)const;
int NotEmpty(void)const;
bool IsInStack(T a);//判斷元素a是否在棧中 void Empty();//清空棧
int GetSize();//獲取棧中元素的個(gè)數(shù) void display();//輸出棧中元素
五、用戶手冊
1.本程序運(yùn)行在Windows操作系統(tǒng)下，VS2013，按F7編譯，F(xiàn)5運(yùn)行。
2.在程序運(yùn)行前有預(yù)設(shè)函數(shù)，最好選擇預(yù)設(shè)函數(shù)，然后進(jìn)行測試。
3.在菜單中選擇你想進(jìn)的功能，然后輸入前面的數(shù)字即可。
用戶菜單如下：
*****************************全國鐵路交通咨詢模擬**************************** 1: 顯示所有車站信息
2: 顯示所有車次信息（包括時(shí)刻表）
3: 查詢車站信息“
4: 查詢兩個(gè)城市之間的鐵路信息
5: 增加或刪除車站
6: 增加或刪除鐵路信息
7: 增加、刪除或修改時(shí)刻表、距離和價(jià)格
8: 尋找兩城市間最省錢的一條路徑
9: 尋找兩城市間最省時(shí)間的一條路徑
10:尋找兩城市間所有路徑(按費(fèi)用從低到高排序輸出)
11:尋找兩城市間所有路徑(按所用時(shí)間從少到多排序輸出)
12: 退出咨詢系統(tǒng)”
*****************************************************************************"
六、測試數(shù)據(jù)
1.用戶菜單
在輸入指令一欄輸入你想要使用的功能的數(shù)字編號(hào)。如：輸入1 功能為：顯示所有車站信息
由于數(shù)據(jù)過多，這里只截取部分輸出
輸入指令：2 功能：查詢所有車次信息
數(shù)據(jù)量太大，也只截取部分輸出。
輸入指令：3 功能：查詢車站信息
車站信息有：
1.從此車站出發(fā)各個(gè)車次信息。2.從其他車站出發(fā)到達(dá)此車站的信息
輸入指令：4 功能：查詢兩個(gè)車站之間的信息
查詢的時(shí)候，是由先后順序的，先輸入的是出發(fā)城市，后輸入的到達(dá)城市
輸入指令：5 功能：增加或刪除車站
樣例1：增加成功
樣例2：增加失敗
錯(cuò)誤原因：編號(hào)輸入錯(cuò)誤 編號(hào)id為12：九龍
所以此編號(hào)已有城市占用，輸入錯(cuò)誤
樣例3：刪除成功
現(xiàn)在可查詢廣州的信息
發(fā)現(xiàn)廣州此時(shí)已不存在，刪除成功
樣例4：刪除失敗
錯(cuò)誤原因：id為31 的城市不存在
輸入指令：6 功能：增加或刪除鐵路信息
樣例1：增加失敗
失敗原因：id為1的城市已刪除，不能再城市1余城市6之間增加鐵路
樣例2：增加成功
此時(shí)新建鐵路狀態(tài)：還有鐵路線，沒有車次 注：想要鐵路線有火車運(yùn)行，必須補(bǔ)充車次信息
樣例3：刪除成功
樣例4：刪除失敗
失敗原因：不存在從城市9到城市13的鐵路
輸入指令：7 功能：增加、刪除或修改時(shí)刻表、距離和價(jià)格
測試樣例：
可查詢修改后的價(jià)格 出發(fā)城市：6 株洲 到達(dá)城市：5 長沙
車次為：1022的信息中 價(jià)格：999 修改成功！
輸入指令：8 功能：尋找兩城市間最省錢的路勁
輸入指令：9 功能：尋找兩城市間最省時(shí)間的路勁
輸入指令：10 功能：尋找兩城市間所有路徑(按費(fèi)用從低到高排序輸出)
數(shù)據(jù)過多，取前二十條顯示，我也只截取前一部分?jǐn)?shù)據(jù)
輸入指令：11 功能：尋找兩城市間所有路徑(按所用時(shí)間從少到多排序輸出)
數(shù)據(jù)過多，取前二十條顯示，我也只截取前一部分?jǐn)?shù)據(jù)
注：后面的測試時(shí)前面面修改后的結(jié)果，所以，計(jì)算的結(jié)果和初始化數(shù)據(jù)計(jì)算的結(jié)果可能會(huì)不一致，這是因?yàn)橹皇强赡苡?jì)算會(huì)用到我修改后的數(shù)據(jù)，所以存在不一致的問題。
七、心得體會(huì)
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)校園導(dǎo)游咨詢
9、校園導(dǎo)游咨詢 問題描述：
設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)?；疽螅?/p>
⑴設(shè)計(jì)華東交通大學(xué)的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，⑵存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。⑶為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。⑷為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡單路徑。
#include
//最大頂點(diǎn)個(gè)數(shù) #define INF 32767
//用32767表示∞ #include
//調(diào)用函數(shù)system改變字體顏色的頭文件
typedef int InfoType;#define MAXV 100
//最大頂點(diǎn)個(gè)數(shù) //以下定義鄰接矩陣類型 typedef struct {
int no;
//頂點(diǎn)編號(hào)
InfoType info;
//頂點(diǎn)其他信息 } VertexType;
//頂點(diǎn)類型 typedef struct
//圖的定義 {
int edges[MAXV][MAXV];//鄰接矩陣
int vexnum,arcnum;
//頂點(diǎn)數(shù)，弧數(shù)
VertexType vexs[MAXV];//存放頂點(diǎn)信息 } MGraph;
void ecjtumap()//建立華東交通大學(xué)地圖
{ printf(“t|------------------------------|n”);printf(“t|
|n”);printf(“t|
|n”);printf(“t|
----------
|n”);printf(“t|
==============================| 國防生宿舍|
|n”);printf(“t|。
----------
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|
|南區(qū)四食堂|
----------
|n”);printf(“t|。
|南區(qū)禮堂 |
|n”);printf(“t|。
----------
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
--------。
|n”);printf(“t|
================| 校訓(xùn)牌|。。。。
|n”);printf(“t|
=
--------
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
--------
---------
|n”);printf(“t|----| 南區(qū)后門 |---------| 南區(qū)大門 |------------------------|n”);printf(“t|
--------
---------
|n”);printf(“t|
---------
|n”);printf(“t|-------------------------| 北區(qū)大門 |------------------------|n”);printf(“t|
--------
|n”);printf(“t|。
--------------
|n”);printf(“t|
===========================| 15棟綜合教學(xué)樓 |
|n”);printf(“t|
=
--------------
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
=
----------
|n”);printf(“t|
===============================| 經(jīng)管食堂 |
|n”);printf(“t|
=
----------
|n”);printf(“t|
=
=
|n”);printf(“t|
=
=
|n”);printf(“t|
-----------
=
|n”);printf(“t|
|軌道交通食堂|====================| 學(xué)生宿舍 |
|n”);printf(“t|
------------
|n”);printf(“t|
|n”);printf(“t|------------------------------|n”);printf(“n”);} void DispMat(MGraph g)
//輸出鄰接矩陣g，即輸出地圖各景點(diǎn)的圖的距離 { int i,j;for(i=0;i for(j=0;j if(g.edges[i][j]==INF) printf(“%3s”,“∞”);//這里分別用%3s和%3d控制輸出字符∞或數(shù)字寬度為3個(gè)字符 else printf(“%3d”,g.edges[i][j]);//這樣比較方便觀看景點(diǎn)的圖的鄰接矩陣g printf(“n”);} } void listmap()//建立 景點(diǎn)的相關(guān)信息的總瀏覽表 { printf(“t 華東交通大學(xué)景點(diǎn)一覽 nn”);printf(“t|--------|n”);printf(“t| 1：南區(qū)大門 |n”);printf(“t|--------|n”);printf(“t| 2：校訓(xùn)牌 |n”);printf(“t|--------|n”);printf(“t| 3：圖書館 |n”);printf(“t|--------|n”);printf(“t| 4：南區(qū)一食堂 |n”);printf(“t|--------|n”);printf(“t| 5：孔目湖 |n”);printf(“t|--------|n”);printf(“t| 6：北區(qū)大門 |n”);printf(“t|--------|n”);printf(“t| 7：15棟教學(xué)樓 |n”);printf(“t|--------|n”);printf(“t| 8：北區(qū)食堂 |n”);printf(“t|--------|n”);printf(“t| 9：科技樓 |n”);printf(“t|--------|n”);printf(“t| 10：北區(qū)籃球場 |n”);printf(“t|--------|n”);} void introduce()//根據(jù)上面的瀏覽表，對(duì)應(yīng)出相關(guān)信息 { int a=1;printf(“n”);printf(“請(qǐng)輸入要查看的景點(diǎn):n”);printf(“輸入1~10的數(shù)字選擇景點(diǎn)，其他數(shù)字返回上一級(jí)n”);while(0 switch(a) {case 1:printf(“1：南區(qū)大門是進(jìn)入華東交通大學(xué)南區(qū)的正門n”);break; case 2:printf(“2：校訓(xùn)牌是激勵(lì)我們大學(xué)生積極向上n”);break; case 3:printf(“3：圖書館是給我們大學(xué)生豐富知識(shí)的海洋n”);break; case 4:printf(“4：南區(qū)一食堂是南區(qū)學(xué)生的吃飯的地方n”);break; case 5:printf(“5：孔目湖是華東交通大學(xué)最迷人的地方n”);break; case 6:printf(“6：北區(qū)大門是進(jìn)入華東交通大學(xué)北區(qū)的正門n”);break; case 7:printf(“7：15棟教學(xué)樓是一棟綜合型的教學(xué)樓n”);break; case 8:printf(“8：北區(qū)食堂是北區(qū)學(xué)生吃飯的地方n”);break; case 9:printf(“9：科技樓是大學(xué)生上機(jī)做實(shí)驗(yàn)的教學(xué)樓n”);break; case 10:printf(“10：北區(qū)籃球場是大學(xué)生鍛煉身體的地方n”);break; } } } void show_didian(int n)//根據(jù)算法求出的整型數(shù)，對(duì)應(yīng)出地點(diǎn)//根據(jù) xx算法求出的數(shù)字，轉(zhuǎn)化為文字描述 { switch(n){case 0:printf(“1.南區(qū)大門”);break;case 1:printf(“2.校訓(xùn)牌”);break;case 2:printf(“3.圖書館 ”);break;case 3:printf(“4.南區(qū)一食堂”);break;case 4:printf(“5.孔目湖”);break;case 5:printf(“6.北區(qū)大門”);break;case 6:printf(“7.15棟教學(xué)樓”);break;case 7:printf(“8.北區(qū)食堂”);break;case 8:printf(“9.科技樓”);break;case 9:printf(“10.北區(qū)籃球場”);break;} } void ppath(int path[][MAXV],int i,int j)//求最短路徑經(jīng)過的地點(diǎn) { int k=path[i][j];if(k==-1)return;ppath(path,i,k);show_didian(k);printf(“->> ”);ppath(path,k,j);} void put_shortdistance(int x,int y,int A[][MAXV],int path[][MAXV],int n){ int i,j;for(i=0;i for(j=0;j if(A[i][j]==INF) { if(i!=j)printf(“從%d到%d沒有路徑n”,i,j); } else { if(i==x&&j==y) { printf(“最短路徑為：從--”); show_didian(i); printf(“--到--”); show_didian(j); printf(“--路徑為--:n”); show_didian(i);//輸出起點(diǎn) printf(“->>”); ppath(path,i,j);//求最短路徑經(jīng)過的中間路徑，若沒有則不輸出 show_didian(j);//輸出 終點(diǎn) printf(“nt路徑長度為:%dn”,A[i][j]); } } } void shortdistance(MGraph g,int x,int y)//求最短路徑用的是弗洛伊德算法 { int A[MAXV][MAXV],path[MAXV][MAXV];//path為中間路徑不包括 起點(diǎn) 終點(diǎn) int i,j,k,n=g.vexnum;for(i=0;i //給A數(shù)組置初值 for(j=0;j { A[i][j]=g.edges[i][j];path[i][j]=-1; } for(k=0;k //計(jì)算Ak { for(i=0;i for(j=0;j //這里的3個(gè)for循環(huán) if(A[i][j]>(A[i][k]+A[k][j]))//所以時(shí)間復(fù)雜度O(n3) { A[i][j]=A[i][k]+A[k][j];path[i][j]=k; } } put_shortdistance(x,y,A,path,n);} void menu(MGraph g)//建立 菜單 頁面，可以無數(shù)次選擇菜單，當(dāng)輸入5時(shí)退出系統(tǒng) { int m=1,x=1,y=1;//m的菜單選擇的功能x,y分別表示從x到y(tǒng)的問路查詢 while(m!=5){ printf(“ttt|------------------------|n”); printf(“ttt|----------菜單----------|n”); printf(“ttt| 1：查看地圖 |n”); printf(“ttt| 2：地圖詳解 |n”); printf(“ttt| 3：景點(diǎn)一覽表 |n”); printf(“ttt| 4：問路查詢 |n”); printf(“ttt| 5：退出 |n”); printf(“ttt|------------------------|n”); printf(“請(qǐng)輸入1~5的數(shù)字n”); scanf(“%d”,&m); switch(m) {case 1:ecjtumap();break; case 2:listmap(); introduce();break; case 3:listmap(); introduce(); printf(“n”);break; case 4:listmap(); printf(“請(qǐng)輸入起點(diǎn):”); scanf(“%d”,&x);x+=-1; printf(“請(qǐng)輸入終點(diǎn):”); scanf(“%d”,&y);y+=-1; shortdistance(g,x,y);break; case 5:printf(“ttt感想使用本系統(tǒng)，歡迎下次繼續(xù)使用n”);break; } } } void main(){ system(“color 0a”);//輸出字體為綠色 int i,j;MGraph g;int A[MAXV][10]={ {INF, 1,INF,INF,INF, 1,INF,INF,INF,INF}，{ 1,INF, 5, 6, 7,INF,INF,INF,INF,INF}，{INF, 5,INF,INF, 2,INF,INF,INF,INF,INF}，{INF, 6,INF,INF, 5,INF,INF,INF,INF,INF}，{INF, 7, 2, 5,INF,INF,INF,INF,INF,INF}，{ 1,INF,INF,INF,INF,INF, 3,INF, 5,INF}，{INF,INF,INF,INF,INF, 3,INF, 2,INF,INF}，{INF,INF,INF,INF,INF,INF, 2,INF, 8, 10}，{INF,INF,INF,INF,INF, 5,INF, 8,INF, 2}，{INF,INF,INF,INF,INF,INF,INF, 10, 2,INF}};g.vexnum=11;g.arcnum=11;for(i=0;i for(j=0;j g.edges[i][j]=A[i][j];printf(“n”);printf(“ttt華東交通大學(xué)導(dǎo)游咨詢系統(tǒng)n”);menu(g);//進(jìn)入導(dǎo)游系統(tǒng)，執(zhí)行菜單功能 } 數(shù) 據(jù) 結(jié) 構(gòu) 課程設(shè)計(jì)報(bào)告 題 目： 一元多項(xiàng)式計(jì)算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級(jí)： 2012級(jí)普本班 學(xué) 號(hào)： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時(shí) 間： 一、課程設(shè)計(jì)題目分析 本課程設(shè)計(jì)要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。 二、設(shè)計(jì)思路 本程序采用C語言來完成課程設(shè)計(jì)。 1、首先，利用順序存儲(chǔ)結(jié)構(gòu)來構(gòu)造兩個(gè)存儲(chǔ)多項(xiàng)式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運(yùn)算分成五個(gè)主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。 3、然后各個(gè)模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時(shí)錯(cuò)誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對(duì)多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。 三、設(shè)計(jì)算法分析 1、相關(guān)函數(shù)說明： (1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項(xiàng)式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項(xiàng)式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項(xiàng)式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項(xiàng)式，void Print(Polyn P) 銷毀多項(xiàng)式函數(shù)釋放內(nèi)存，void Destroy(Polyn p) 主函數(shù)，void main（） 2、主程序的流程基函數(shù)調(diào)用說明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個(gè)結(jié)構(gòu)體變量中coef表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對(duì)象名。 (2)當(dāng)用戶輸入兩個(gè)一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲(chǔ)這兩個(gè)多項(xiàng)式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xiàng)式申請(qǐng)足夠的存儲(chǔ)空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn) 這就建立一元多項(xiàng)式的關(guān)鍵步驟 (3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對(duì)多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對(duì)指數(shù)大小的比較，對(duì)各種情況進(jìn)行處理，此處由于反復(fù)使用指針對(duì)各個(gè)結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)： 在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實(shí)現(xiàn)；對(duì)于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲(chǔ)所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計(jì)算模塊的主要功能。 (5)另一個(gè)子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計(jì)算合并的鏈表逐個(gè)結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計(jì)算式計(jì)算結(jié)果。由于考慮各個(gè)結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。 四、程序新點(diǎn) 通過多次寫程序，發(fā)現(xiàn)在程序在控制臺(tái)運(yùn)行時(shí)總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺(tái)背景顏色，0是控制臺(tái)輸出字體顏色。 五、設(shè)計(jì)中遇到的問題及解決辦法 首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時(shí)候易腦子混亂出錯(cuò)，對(duì)于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4 代碼編寫。 其次是，在寫除法模塊時(shí)比較復(fù)雜，自己通過查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過本次應(yīng)用C語言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語言程序設(shè)計(jì)的知識(shí)，以前對(duì)指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計(jì)對(duì)指針理解的比較深刻了。而且對(duì)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計(jì)開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對(duì)自己以后學(xué)習(xí)其他語言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。 八、指導(dǎo)老師評(píng)語及成績 附錄：（課程設(shè)計(jì)代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點(diǎn) else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數(shù)為0的話釋放結(jié)點(diǎn) { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時(shí)將結(jié)點(diǎn)插入 } 7 } //建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf(“請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn) } return head;} //銷毀多項(xiàng)式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項(xiàng)式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項(xiàng)數(shù)計(jì)數(shù)器 if(!q)//若多項(xiàng)式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng) 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空 } //求解并建立多項(xiàng)式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) } return headc;} //求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項(xiàng)式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn) hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng) } } return hf;} //求解并建立多項(xiàng)式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn),存儲(chǔ)商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)，存儲(chǔ)余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請(qǐng)輸入A(x)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請(qǐng)輸入B(x)的項(xiàng)數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項(xiàng)式B printf(“n”);printf(“**********************************************n”);printf(“* 多項(xiàng)式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項(xiàng)式A(x):“);Print(pa);*n”); printf(“多項(xiàng)式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項(xiàng)式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項(xiàng)式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項(xiàng)式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 1.赫夫曼編碼器 設(shè)計(jì)一個(gè)利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。要求： 1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個(gè)字符和26個(gè)權(quán)值（統(tǒng)計(jì)一篇英文文章中26個(gè)字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實(shí)現(xiàn)屏幕輸出，然后實(shí)現(xiàn)文件輸出）； 5)界面優(yōu)化設(shè)計(jì)。 代碼如下： #include typedef struct HTNode //結(jié)構(gòu)體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權(quán)值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進(jìn)行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請(qǐng)輸入權(quán)值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對(duì)結(jié)點(diǎn)進(jìn)行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第三篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)